Schnorr signatures for privacy and storage improvements

[robert-zaremba]

Summary

Schnorr Signatures is are extremely well researched improve the privacy of users whilst also helping with issues of scaling at the same time. Currently, Cosmos SDK supports only ECDSA signatures. We started a work for adding ed25519. However it's not specified and lacking in depth analysis for batch verification, aggregation and specification for strickness for validation rules intended for consensus-critical contexts (--> tendermint issue for fixing it to provide guaranteess for cross-implementation consensus)

Background

Many Bitcoin derived blockchains use ECDSA for digital signatures. Schnorr Signatures algorithm patent was about to expire by the time Bitcoin paper was released. Now Schnorr is coming back to Bitocin with the MuSig update allowing better privacy and efficiency.

Problem Definition

ECDSA has a number of downsides compared to Schnorr signatures:

• Provable security: Schnorr signatures are provably secure. In more detail, they are strongly unforgeable under chosen message attack (SUF-CMA)
• There are claims saying that NSA used backdoor in ECDSA design.
• Non-malleability: The SUF-CMA security of Schnorr signatures implies that they are non-malleable. On the other hand, ECDSA signatures are inherently malleable[3]; a third party without access to the secret key can alter an existing valid signature for a given public key and message into another signature that is valid for the same key and message.
• Doesn't support aggregation.
• Doesn't support full privacy for multi-sign use-cases. With Schnorr Sig. we can combine all signatures and public keys in the transaction to a single key and a signature and nobody will find out that they correspond to multiple keys.
• Doesn't support batch verification.

Advantages of advanced Schnorr signatures

• Hidden feature: we can hide who signed the message
• Better UX than current multisig: no need to sign in a specific order
• Aggregated signatures (Schnorr aggregation) are more efficient: no need to attach a list of signatures: we have only one aggregated sig. So smaller size and faster verification

Proposal

Support Schnorr signatures for every use-case:

• simple signatures
• multisig
• coin-join scenarios (which is kind of double multisig).

Schnorr is extremely powerful for the privacy because we can make complex multi-sig transactions and even complex coinjoin transactions look like everyday normal transactions. This makes it difficult for chain analysis companies to analyse the transaction flows. In genera, aggregated signature scheme like Schnorr MuSig allows users to make a multisig output look like a standard user’s single sig output. This is a huge improvement compared to a normal multisig, where the users need to broadcast all of their public keys and signatures (requiring blockchain to validate and store it indefinitely. Instead, with a this proposal, the users do the enforcement themselves by constructing signatures between themselves resulting in a single final signature. Benefits:

• Onchain transaction size is reduced allowing for more transaction throughput. Schnorr aggregated signatures have constant size (no matter how many signatures we aggregate).
• Better privacy for participants of a Multi-Signature wallets
• Transaction validate faster.
• Combat certain forms of spam attacks

Drawbacks:

• Schnorr aggregation requires interaction between parties (2+ rounds of communication).

How (proposal)

• 64-byte Schnorr signatures over the elliptic curve based on BIP:340. This specification addresses many security traps caused by wrong implementation (like Rogue Key Attack).
• Implement MuSig2 is effectively a key aggregation scheme developed by Blockstream. Earlier version, MuSig1 (algorithm description). This sheme uses Schnorr Signatures and is designed for Bitcoin. secp256k1-zkp noted that they are implementing MuSig2.

Alternative:

• Two-Round Threshold Schnorr Signatures with FROST
• ed25519 aggregation based on Compact Multi-Signatures for Smaller Blockchains.
• sr25519
• Tree Signatures for multisig.
• Cothority CoSi -- EPFL (University of Lausanne) crypto framework with few nice solutions.

Notes:

• should support batch verification. Lib with ed25519 batch verification: https://github.com/oasisprotocol/ed25519

Note about BLS

BLS is another elegant solution for private signatures and aggregation. It's more optimal for scenarios where we need to aggregate thousands than signatures (for smaller use-cases Schnorr is faster). The Achilles' heel of BLS is pairing function are complicated, and it can become our foe if we are not careful enough. There is an attack on elliptic curve crypto systems, called MOV attack (named after Menezes, Okamoto, and Vanstone), that allows to reduce security of the system by using pairing functions.

TL;DR: if not needed, it's safer to use well researched Schnorr Signatures rather than BLS.

---

For Admin Use

• [x] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned

[robert-zaremba]

/cc @aaronc , @clevinson -- this could be very useful for many use cases.

[ValarDragon]

I mean we have Ed25519, which is ~basically Shnorr signatures restricted to one curve (some differences in how you hash things from the original Shnorr paper, but doesn't affect anything I'd see being used here). Aggregation techniques explicitly for Ed25519 look ~the same as for Shnorr, and have been specified for several years now. All usecases you listed can be done using Ed25519.

I don't see the benefit of adding direct Shnorr signatures, unless you explicitly want Shnorr secp256k1 for taproot compatability.

There is an attack on elliptic curve crypto systems, called MOV attack (named after Menezes, Okamoto, and Vanstone), that allows to reduce security of the system by using pairing functions.

All elliptic curves for use in cryptography are parameterized such that the MOV attack is infeasible. In the case of a pairing based curve, this (well really tower NFS attacks) is the central thing you parameterize security against.

[robert-zaremba]

The idea is to implement the BIP-340 for compatibility with secp256k1 keys AND appropriate aggregation schema. As you noticed, Ed25519 doesn't specify aggregation schema. Many SDK users are using secp256k1. We can reuse MuSig, or some other protocol for aggregation. In fact this is what Polkadot is using. W3F developed shnorrkel which implements a schema combining all features from BIP-340 with curve25519.

IFAICT, today there is no full support for ed25519 in SDK.

[robert-zaremba]

BTW, it seams that Tendermint is using Ed25519 directly. Does it implement measures against small-cofactor problems?

Implementation-defined behavior.Some systems, such as Ed25519 [7], do notspecify behavior when the inputs have a nonzeroh-torsion component. In par-ticular, Ed25519 signature verification can be different for batched vs singletonsignatures, or between different implementations. This can cause disruption inprotocols where all parties must agree on whether a signature is valid, such asa blockchain or Byzantine agreement. In other cases, it may make it easier tofingerprint implementations.

[tac0turtle]

BTW, it seams that Tendermint is using Ed25519 directly. Does it implement measures against small-cofactor problems?

See https://github.com/tendermint/spec/pull/144.

We are working on this.

[tac0turtle]

Note: sr25519 is supported in tendermint's crypto package. And is being used by a sdk based chain.

[hxrts]

Zcash Schnorr construction that enables concurrent signing. Maybe too early for our consideration, but linking anyway https://www.zfnd.org/blog/frost-update/

[robert-zaremba]

It seams that Bitcoin research is advancing as well. Recently they published MuSig2.

MuSig2 doesn't need interaction between the signers any more, which was a common hurdle in MuSig1 discussions.

[tac0turtle]

What is the status here? There isn't anything blocking this, right?

[aaronc]

5694/ADR 028 is blocking, but hopefully we can resolve that soon.

[tac0turtle]

WEN schnorr? 😄

[robert-zaremba]

when ready :D
Nobody expressed a need, so it's still in a backlog.

[robert-zaremba]

Added Two-Round Threshold Schnorr Signatures with FROST to alternatives

[alexanderbez]

I haven't seen concrete points made on what this buys us from a user perspective? I can only assume the main benefit is for multi-sigs, but apart from that, what else?

[robert-zaremba]

Updated the description by making it more explicit, added Advantages of advanced Schnorr signatures section.

[odeke-em]

Something up your alley and interests @elias-orijtech

[tac0turtle]

no need to work on this right now. Zondax is working on some cryptography things

[robert-zaremba]

Zondax is working on some cryptography things

Are there any details about it? Could you share a link?

[bizk]

We (@zondax) started working on this implementation following these specs https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki , we are also preparing a plan for improving the whole crypto module as well, once we have a draft we will be sharing it so we can all discuss it :)

[bizk]

I was thinking of usiing Kyber package implementation of schnor algorithm since it is a well known repository from a university, taking a look at the code, seems it satisfies the implementation. Any concerns with this approach?

[bizk]

Closing this issue since ed25519 is already implemented which is a pretty good algorithm. I played around with other variatns of schnorr but these ended up being more complex or less performant. Unless we want pure schnorr implementation.

We are putting our efforts on enabling ed25519, working over this issue

@tac0turtle

[tac0turtle]

i dont quite follow, why not add schnoor as an alternative here?

[robert-zaremba]

I second @tac0turtle . The goal of using Schnorr is to:

• allow easy signature aggregation (good alternative to BLS, when amount of signatures is low, eg < 50).
• compatibility with Bitcoin tools.

Let's reopen.

[bizk]

It was an assumption on my side that since ed25519 is an efficient variant of schnorr it wouldn't make sense to implement something less performant. After the discussion we had in the call, I realized that I was not having other aspects in mind as the ones both of you mentioned