Multisig support

[qdrn]

Study how to integrate multisig support.

I think you saw some codebased that support multisig with our signature scheme @Eitu33. Would you mind sharing them here ?

[Eitu33]

I can't remember the crate name I'll have to look for it again

[Leo-Besancon]

A quick search only prompted me with the following repo ZenGo-X/multi-party-eddsa.
I don't know if it is still really maintained, and it's not on crates.io.

[Leo-Besancon]

Here are some insights on what I could find.

What we currently use

Our signature scheme is Ed25519, the EdDSA signature scheme using SHA-512 and Curve25519.

Our KeyPair struct is a wrapper around the KeyPair struct of the ed25519-dalek crate (https://crates.io/crates/ed25519-dalek).

This crate is basically an API that provides the hashing/signing methods. These methods then call the lower-level crate curve25519-dalek (https://crates.io/crates/curve25519-dalek), that does the arithmetic operations over the curve (handling Points and Scalars on this curve).

Extract from the docs of this later crate:

curve25519-dalek is not intended to provide implementations of any particular crypto protocol.
Rather, implementations of those protocols (such as x25519-dalek and ed25519-dalek) should
use curve25519-dalek as a library.

State of the art on Rust multisig crates supporting ED25519:

ZenGo-X / multi-party-eddsa

The following repo proposes a multisig library over ED25519: https://github.com/ZenGo-X/multi-party-eddsa/.

Limitations:

• It directly uses the curv-kzen crate (https://crates.io/crates/curv-kzen) for lower-level arithmetic, and does not propose an API (e.g, it directly handles Points and Scalars, not byte arrays). This means we would have to implement the middleware ourselves, with security considerations.
• It does not seem to be maintained anymore (?)

diem_crypto::multi_ed25519

https://diem.github.io/diem/diem_crypto/multi_ed25519/index.html

Unless I'm mistaken, they follow the 'naive' approach to multi-sigs, where a MultiSig is basically just a Vec of Signatures, which is not suitable for us:

pub struct MultiEd25519Signature {
    signatures: Vec<Ed25519Signature>,
    bitmap: [u8; BITMAP_NUM_OF_BYTES],
}

Conclusions

I believe some additional research (and knowledge on the underlying cryptography) would be needed to properly design a solution, as existing crates do not seem to be enough for our needs.

[qdrn]

I think what @Eitu33 found was a crate used/developed by Polkadot. The issue was that there was a lot of dependencies. Maybe it's worth having a closer look.

[Leo-Besancon]

Thanks, in that case it may be https://github.com/w3f/schnorrkel (great crate name but a quick search does not find it haha). I'll take a look when I have some time.

[Leo-Besancon]

So looking into this crate, the API is basically the same of what we are currently using. The main differences are:

• Schnorrkel uses Ristretto points instead of Edward points. From what I gathered, the cryptography is the same (same curve and hash), but viewed a bit differently. When converting from Ristretto to Edward points, you have two branches available (similar to how the square root works) so there is no 1 to 1 mapping.
• Their SecretKey is what EdDSA/Ed25519 calls an ExtendedSecretKey (64 bytes)
• They call the EdDSA/Ed25519 SecretKey a MiniSecretKey (32 bytes)
• They implement a multisignature interactive scheme. It is a three-round version of MuSig (https://eprint.iacr.org/2018/068) multi-signature scheme to address some vulnerabilities in the original two-round version. In MuSig2 (https://eprint.iacr.org/2020/1261), which they do not implement, the two-round version is safe.

I managed to build the project using schnorkkel, but I have yet to:

• Deserialize and Serialize from the same format we currently use (if it's to much a hassle, we could just introduce a new keypair version to avoid incompatibilities)
• Implement a very basic PoC multi-sig implementation in our project.

[qdrn]

It would be interesting to know more how all these things work so that we are less naive about crypto. Maybe it's worth digging a bit and making a recap of what you learned along the way to the team ?

Some interesting resource (and resources therein): https://substrate.stackexchange.com/questions/4011/how-is-a-substrate-address-or-multisig-address-calcluated-from-private-key

[Leo-Besancon]

Sounds great! Thanks for the link.

[Leo-Besancon]

Here is a small follow-up regarding BLS Signatures.

BLS Signatures

Introduction

Some helpful info can be found here: https://hackmd.io/@benjaminion/bls12-381

Boneh-Lynn-Shacham (BLS) signatures rely on elliptic curve cryptography, so as to EdDSA / ECDSA signature schemes.
However, instead of using 1 elliptic curve to compute everything (secret and public keys, signatures), BLS rely on 2 "paired" elliptic curves, $G_1$ and $G_2$.

The curves used are mainly Barreto-Lynn-Scott : BLS curve BLS12-381. Same equation ($y^2=x^3+4$), but we are using 2 different subgroups.

Algos:
https://hackmd.io/@benjaminion/bls12-381#BLS-digital-signatures

TL;DR: We use one curve for public keys, one curve for signatures. We choose which one handles what task: "The trade-offs are execution speed and storage size. $G_1$ has small points and is fast; $G_2$ has large points and is slow."

Features

2 types of aggregations possible:

• Aggregation of signatures of different messages (like batching, for speedups of independant signatures)
• Aggregation of signatures of the same message (multisigs / threshold)

Rogue key attacks on aggregate schemes

• [CASE 1] If the messages are distinct, there is no problem
• If the messages are the same, then an attacker could bypass a signature by manipulating their public key.
  • [CASE 2] The main protection against this is to check a "Proof of Possession" of the public key used in the scheme for everyone involved.
    ETH uses this protection to verify the validator signed a message
  • [CASE 3] Some other schemes exist, base idea similar to MuSig, but quite different in my understanding (no need for interactivity?): https://eprint.iacr.org/2018/483.pdf

[CASE 2] Problem: it increases the needed storage, as we need to publish proofs for each signer (e.g. the signature of the pubkey)
But it may be fine if we reuse the aggregated public key and sigs (we only have to do it once, so it would be fine for a multisig with many transactions).

[CASE 3] Not much crates here? Or other tradeoffs.

Rust crates

The following website https://cryptography.rs compiles different Rust crates related to cryptography, quite useful to get a quick overview of the state of the art.

1. bls-signatures

[CASE 1] filecoin-project/bls-signatures#42

// Enforce that messages are distinct as a countermeasure against BLS's rogue-key attack. 
// See Section 3.1. of the IRTF's BLS signatures spec: 
// https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-02#section-3.1 

and https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-02#section-3

This implementation uses the basic scheme (section 3.1) for protection against rouge key attacks.

For O(1) number of parings, you would need Proof of Possession scheme described in Section 3.3 (also known as "Proof of knowledge of the secret key" in the other document), which this library currently doesn't implement.

2. bls_signatures_rs

[NO PROTECTION] https://docs.rs/bls-signatures-rs/latest/bls_signatures_rs/bn256/index.html

	Disclaimer

This module does not implement a defense against Rogue-key attacks, which means it should be used in protocols where the possession of the private key of each individual has been proven (i.e., by signing a message)

3. milagro_bls
   [CASE 2] https://github.com/sigp/milagro_bls

   "This library uses a Proof of Possession (PoP) variant as protection against rogue key attacks. A public key can be PoP verified by signing a hash of the public key. This must be done before a PublicKey may be used in any aggregate signatures."

4. multi-party-bls
   [CASE 3] https://github.com/ZenGo-X/multi-party-bls
   https://github.com/ZenGo-X/multi-party-bls/blob/main/examples/cli.rs

    Not a lot of repo activity
    But the given tests seem promissing.
    
    - What is the security status (the crate was not audited at all, they say to contact them if we want to use it)
    - What are performances compared to EDDSA? They have benchs!
   

   Keygen
   Mean: 158.4ms
   Std: 18.4ms
   Signing
   Mean: 45.5ms
   Std: 21.2ms

   Compared to ed25519-dalek: signing 15.017 µs

5. Rust bindings from blst ("Blast")

[CASE ?] https://github.com/supranational/blst/#general-notes-on-implementation
https://github.com/supranational/blst/blob/master/bindings/rust/benches/blst_benches.rs

Seems mid-level library, and I could not understand what assumption they make (CASE 1, CASE 2 or CASE 3)

6. bls-like
   [CASE 1+2+part(3)] https://github.com/w3f/bls

   "We provide aggregation techniques based on messages being distinct, on proofs-of-possession, and on delinearization, although we do not provide all known optimisations for delinearization.".
   If you lack proofs-of-possesion, then delinearized approaches are provided in the delinear module, but such schemes might require a more customised approach.

   Note: "Boneh-Lynn-Shacham (BLS) signatures have slow signing, very slow verification, require slow and much less secure pairing friendly curves, and tend towards dangerous malleability. Yet, BLS permits a diverse array of signature aggregation options far beyond any other known signature scheme, which makes BLS a preferred scheme for voting in consensus algorithms and for threshold signatures."

   https://github.com/w3f/bls/blob/master/src/delinear.rs

Conclusions

BLS signatures should probably not be considered right now to replace our current signature scheme. However, it could be nice to:

• Follow why and how Ethereum used them for their validators
• Follow the innovations in the field. Right now signature and verification times seem not suitable for our case, but iterative improvments and signature aggregation may change that in the future.

References

Base article for 3: (approach similar to MuSig, but no need for multi round?)
Compact: https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html
Full paper: https://eprint.iacr.org/2018/483.pdf

[damip]

Given the study, we conclude that it will be complicated to support multisig natively. We will leave it to the SC world