SEP: Multi/Threshold signature for Stronghold

[vuongDang]

Outline

We want Stronghold to propose multi-signature as a feature.
In this document we first give an overall presentation of multi-signature. Then we show how multi-signature can be used and integrated into Stronghold.

Finally choice of multi-signature scheme depends heavily on the use cases. Potential applications have to be decided and multiple questions are written at the end to help with the discussion.

Motivation

Purpose of multi-signature

Using multi-signature a group of signers $Signers$ is able to produce a collective signature $sig$ for a message $m$. Then $(m,s)$ can be sent and the receivers can verify the signature. If the verification is successful then the receiver have the guarantees that the signature was produced by $Signers$ and that the message $m$ has not been altered.

Multi-signature in Stronghold

Multi-signatures requires a collection of private keys (also called secret shares) to produce a collective signature of a message. This collective signature with its message can then be checked by anyone with the unique public key matching the collection of private keys.

With multi-signature a group of Strongold instances can each safely store a secret share necessary to produce a collective signature. Then a user can ask the Stronghold group to sign a message. Afterwards anyone knowing the public key corresponding to the collection of secret shares, the message can verify the signature.

Necessary functionalities for multi-signature in Stronghold:

• A Stronghold instance can create a group of signers which are all Stronghold instances
• A user can request a Stronghold instance part of a signing group to produce a collective signature of a message
• A user can ask a Stronghold instance to verify a signature with its corresponding message (user needs to provide the signing group public key)

Reference Level Explanation

Presentation of multi-signature

We present first single signature algorithm to facilitate understanding of multi-signature.

Single signature

Algorithm

$A$ sends $(m, sig)$ to $B$ where $m$ is a message and $sig$ a signature of $m$ by $A$.

1. Setup: $A$ has a secret/public key pair ($sk$, $pk$)
   • $sk$ is only known by $A$
   • $pk$ is public and is known by $B$
2. Signature: signature $sig$ of a message $m$ is produced by $A$ using its secret key $sk$ and message $m$.
3. Sending: $A$ sends $(m, sig)$ to $B$
4. Verification: $B$ can verify the signature $sig$ with $pk$ and $m$.

Properties
If the signature verification succeeds $B$ is guaranteed:

• Authentication: $(m, sig)$ was sent/approved by $A$
• Integrity: $m$ has not been tampered

Multi-signature

Multi-signature is the same concept as single signature except that the party $A$ becomes a group of $n$ parties $(A_0, \ldots, A_{n-1})$.

Algorithm

The group $(A_0, \ldots, A_{n-1})$ sends $(m, sig)$ to $B$ where $m$ is a message and $sig$ a signature of $m$ by $(A_0, \ldots, A_{n-1})$.

1. Setup: each $A_i$ has a share $sk_i$ of a secret key $sk$
   • $sk$ can be constructed from the shares $(sk_0, \ldots, sk_{n-1})$
   • there exists a public key $pk$ known by all such that $(sk, pk)$ is a pair of secret/public cryptographic keys
2. Signature: each $A_i$ signs message $m$ and produces partial signature $sig_i$
3. Sending: partial signatures $sig_i$ are combined into a signature $sig = (sig_0, \ldots, sig_{n-1})$ and $(m, sig)$ is sent to $B$
4. Verification: $B$ can verify the signature $sig$ with $pk$ and $m$.

Properties
If the signature verification succeeds $B$ is guaranteed:

• Authentication: $(m, sig)$ was sent/approved by $(A_0, \ldots, A_{n-1})$ send $(m, sig)$
• Integrity: $m$ has not been tampered

Threshold signature

Multi-signature requires $n$ partial signatures out of the $n$ signing parties to be able to produce a valid signature.
A extension of multi-signature called threshold signature enables the creation of a valid signature with only a subset of partial signatures.
Threshold signature $(t, n)$ can create a signature with only $t$ partial signatures out of $n$ parties.

Pros of threshold signature compared to multi-sig

• More flexible: signature can be done even if some parties are missing or are acting incorrectly
• Scale better: reasonable performance for less than 50 signers

Cons

• More complexity/slower in general
  • Require additional step such as key generation (DKG), the signing group can't use their own private keys
  • Signing is more complex

API

Multi-signature functionalities will be implemented as procedures.
Multi-signature should be added as a feature and only if the p2p feature is on

pub enum StrongholdProcedure {
  
  // Other procedures 
  ... 
  
  // Behind a feature flag
  #[cfg(all(feature = "multisig", feature = "p2p"))]
  
  // Initialize a multisig group of signers 
  // 1. Input the p2p coordinates for each Stronghold instance that 
  //    will be part of the signing group
  // 2. Generate and distribute a secret share for each member
  // 3. Generate the group public key corresponding to the
  //   secret shares
  // 4. Return the public key and the signing group
  MultiSigInit(MultiSig)
  
  // Ask a group of signers to collectively sign a message
  // 1. Input message that will be signed and the signing group that
  //    will execute the procedure
  // 2. Ask each member of the signing group a partial signature 
  //    of the same message
  // 3. Aggregate all the partial signatures received from 
  //    the signing group to get a complete signature
  // 4. Return signature and message
  MultiSigSignature(MultiSig)
  
  // Check the validity of a collective signature
  // 1. Input message, collective signature and group public key 
  //    for verification
  // 2. Return verification result
  MultiSigVerification(MultiSig)
  
  // Remove a previously established signing group
  // 1. Input a signing group 
  // 2. Request each member of the signing group to delete their 
  //    information 
  // 3. Delete any local information related to the signing group 
  // 4. Return success if all the members return success
  MultiSigDelete
}

Implementation Options

• Stronghold itself can be used as part / shard of a master key. Internally the passphrase and internal keys are being derive at initial key exchange
• Password rotation mechanism should be provided
• Multisig shall be opt-in and supported at build time setting respective feature flags to engable multisig functionality

Drawbacks

Drawbacks is to not have multi-signature feature.

Rationale and Alternatives

Multi-signature is a feature which is sought in the world of distributed systems. In particular in the blockchain world where committees has to sign and approve transactions.
Stronghold is a nice fit for this use-case with the additional P2P layer that have been added. Stronghold would allow both secure storage of the secret shares but also handle the communication between Stronghold instances for multi-signature.

A potential alternative would to have all the shares in the same Stronghold instance but not accessible with the same credentials. This kind of defeat the purpose of multi-signature where secret shares are kept separately.

Unresolved questions

• Discussion on the potential applications for multi-sign in Stronghold
• Technical question about multi-signature integration in Stronghold

Discussion on multi-signature requirements

The goal is to think of the possible applications of Stronghold with multi or threshold signatures. Questions are here to help with the discussion.

How is a group of signers formed?

Do we assume that all the parties are benevolent and do not display malicious behavior during the protocol?
Some protocols can tolerate the presence of malicious signers (want to create incorrect signature or leak secret shares) but are more complex.

Do we have performance or resources limitations?

• size of the collective signature (can be linear with the number of signers depending on the scheme)
• collective signature creation speed
• verification speed

Do we accept a threshold of partial signatures over which the multi signing succeeds?

We call a multi-signature $(n,n)$ if $n$ partial signatures from the $n$ signing parties are required to produce a valid signature.
An alternative is called threshold-signature $(t,n)$ which has a threshold $t$ such that any set of $t$ partial signatures out of the $n$ signing parties is able to produce the same valid signature.

Threshold signature is more flexible and allow the protocol to succeed even if some parties are not present.

Should protocol complete within an expected time?

Network may be unreliable or a party may be much slower that the others.
In those cases the protocol may take a long time to complete.
Should our protocol be able to timeout and retried later (synchronous setting)?
Should our protocol "eventually" completes and always produce a result (asynchronous setting)?

Asynchronous setting is better if we require the protocol to be able to complete regardless of the network state but is usually slower and more complex.
Synchronous setting is good if we are satisfied with the protocol working 99% of the time and may fail in rare cases.

Do we need the signers to use their own private key as secret share?

Some scheme require the secret shares to be related to produce a valid signature. In this case a distributed key generation (DKG) phase is required and adds more complexity.

Some other schemes allow the users to generate their own secret shares and DKG is not needed. However it may come as more costly in other phases or just prevent some features.

Is the signing group numerous?

There are multiple way to combine partial signatures into a signature.
The most simple one is just having all partial signatures grouped together and the verification process consists in verifying the partial signatures one by one. This is linearly slower with the number of partial signatures you have.

Another way is to compress the partial signatures into a single equal-sized signature. The verification is reduced to verifying a single signature as if it was a single signature scheme.

Do the members of the signing group remain the same?

If the signing group periodically change or if a party drops out then the multi-sig setup may have to re-initiated. Some schemes are more flexible and allows to swap out keys used in the signing group or change the number of parties in the signing group.

Integration of multi-signature in Stronghold

Would Multisig break the Snapshot format?

Either the reassembled key will remain in size, and trying to open the snapshot file will either succeed or fail.

Who is able to ask for a message to be signed?

Possible solutions:

• anyone can ask a signing group to sign a message
• only members of a signing group can ask for a message to be signed
• to each signing group a list of authorized parties is assigned

Future Possibilites

Not defined yet