Cosmos-sdk: 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.

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.

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.

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:

• 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.

[marbar3778]

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.

[marbar3778]

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.

[marbar3778]

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.