Multi-Party Signatures for Chrysalis

Second Layer

Standard Ed25519 signatures are generated in a process outside of the IOTA protocol:

• This requires no protocol changes.
• Solutions based on these approaches can be implemented once and then used for other coins as well.

Shamir’s Secret Sharing (SSS)

• One trusted dealer splits a secret (e.g. private key) into N unique parts and distributes them
• Any T of the shards are sufficient to reconstruct the secret
• This is not "true" multisig, since:
  • The private key must be generated to derive the shards
  • The private key must be reassembled from the shards before a transaction can be signed

Pros

• Works with any signature scheme
• Can be used to share/backup the master seed of a wallet
• Standardized in SLIP-39
• Allows re-generation of shards when N changes

Cons

• Not 100% trustless, as the dealer / signer knows the private key. However, trusted hardware could help mitigating this.

Threshold Ed25519

• Using a distributed key derivation: N parties participate in an interactive process that generates a secret key for each party and a single public key
• Any T parties can participate in an interactive process to produce a valid signature.
• It uses secret sharing, additively homomorphic encryption and zero-knowledge proofs to achieve trustlessness.
• Based on construction described in [Genaro and Goldfeder, 2019] adapted for Ed25519
• Go library for multi-party threshold ECDSA / EdDSA: https://github.com/binance-chain/tss-lib
• N-of-N signatures allow for a much easier process by simply aggregating the signatures (without using SSS, homomorphic encryption or ZKP). See [Boneh et al., 2018, Section 5.1].
  Note: (N - 1)-of-N schemes are equivalent to N-of-N when sharing pairs of secrets among members

Pros

• Generated signatures are indistinguishable from regular Ed25519. (Same size and validation time)
• Trustless
• Works for any coin using Ed25519 signatures

Cons

• Not standardized and rather new
• Signature aggregation relies on random number generator. (We cannot choose R deterministically as in Ed25519.)
• Key derivation as well as singing consist of several rounds of communication. (This could be annoying with cold storage.)
• Dealing with malicious actors is difficult, as they could potentially stall the signing. (However, there seems to be solutions for this.)

First Layer

Support multi-party signatures by introducing new signature schemes into the IOTA protocol:

• This requires changes of the current spec'ed Chrysalis protocol
• Once introduced, they have to remain in the protocol indefinitely and cannot be removed

Naive Multisig (Script)

• Generate N key pairs independently and share the public keys
• Use additional unlock script/type to supply and validate set of T public keys + signatures

Pros

• Trustless
• Signing can be done offline on cold storage (at least when the T parties are not malicious)
• Can support very complicated tree-like unlock conditions, e.g.
  ((3-of-5 multisig) AND (2-of-2 multisig)) OR (single master signature)

Cons

• Requires T signatures and T keys in the unlock block for validation
• Non-malleability is tricky especially with malicious actors
• Validation time is linear in N

Boneh-Lynn-Shacham (BLS) Threshold Signatures

• Use interactive, SSS-based key derivation for N parties
• Any T independent signatures can be aggregated into a valid transaction signature

Pros

• Trustless
• Signing can be done offline on cold storage
• The BLS signature scheme is deterministic and non-malleable

Cons

• Standardization still in draft stage
• Much slower validation than plain Ed25519 (but does not depend on N or T)

Overview

	SSS	t-Ed25519	Naive	BLS
Trustless
No protocol changes
Air gap signing
Complex unlock conditions
Deterministic
Multisig hidden
Unlock block size	constant	constant	linear (in T)	constant
Validation time	constant	constant	linear (in T)	constant (but 10x Ed25519)