Wamu: A Protocol for Computation of Threshold Signatures by Multiple Decentralized Identities
Technical Specification
1. Introduction
This document describes the Wamu protocol which augments a state-of-the-art non-interactive threshold signature scheme (e.g. CGGMP20 [1]) by cryptographically associating each signing party with a decentralized identity. This is achieved by:
- Splitting the secret share for each party between the party and the output of a signing operation by its associated decentralized identity, thus making the signing operation a requirement for reconstructing the party's secret share.
- Adding peer-to-peer decentralized identity authentication to the key generation and signing protocols (and optionally to the key refresh protocol) of the threshold signature scheme.
- Defining protocols for identity rotation, access structure modification (i.e. share addition and removal and threshold modification) and share recovery that build on top of the above 2 augmentations.
Wamu is designed to operate in a decentralized, trust-minimized and asynchronous setting with:
- no centralized or trust-based identity infrastructure.
- signing parties being mainstream consumer devices communicating asynchronously.
NOTE: For interoperability with existing wallet solutions, the only requirement for decentralized identity providers is the ability to compute cryptographic signatures for any arbitrary message in such a way that the output signature is 1) deterministic and 2) can be verified in a non-interactive manner.
2. Preliminaries
The rest of this document describes the Wamu protocol in technical detail. For these descriptions, we'll use the following notation:
- denotes a party.
- denotes a decentralized identity.
- denotes the verifying key (or address) of a decentralized identity.
- denotes the secret key of a decentralized identity.
- denotes a signing algorithm.
- denotes a signature verification algorithm.
- denotes the prime order of the cyclic group of the elliptic curve.
- denotes the set of verified decentralized identities for all parties.
- denotes the threshold (i.e. the minimum number of signatories required to jointly compute a valid signature using the threshold signature scheme).
- denotes a predefined prefix chosen to ensure that signatures computed for identity authentication cannot be valid transaction signatures.
- denotes concatenation using an unambiguous encoding scheme.
NOTE: While the augmenting protocols in this document are described in relation to the current (circa. 2023) state-of-the-art CGGMP20 [1] non-interactive threshold signature scheme for ECDSA signatures, Wamu is a generic protocol that can be adapted to any non-interactive threshold signature scheme (e.g. GG20 [2], CMP20 [3] and FROST20 [4]) that allows for asynchronous communication between signing parties.
3. Share Splitting and Reconstruction
Given a secret share for a party with an associated decentralized identity , the share splitting and reconstruction protocol describes how to split between and the output of a signing operation by so that the output of is required to reconstruct the secret share .
This is achieved by generating a message (we'll refer to this message as the "signing share") and computing a "sub-share" (i.e a share of the secret share ) in such a way that needs to be signed by using to produce another "sub-share" , such that and are shares of under Shamir's secret-sharing scheme [5].
NOTE: Share splitting and reconstruction is a single-party localized concern that happens after (and is not related to) the distributed key generation (DKG) protocol of the threshold signature scheme.
3.1. Share splitting
Given a secret share as input and access to the decentralized identity with secret key , the share splitting protocol proceeds as follows:
- Sample a random message (i.e. the signing share).
- Compute a signature .
- Compute the first sub-share of as the point .
- Generate a line (i.e a polynomial of degree 1) such that is a point on the line and is the constant term (i.e. Polynomial Interpolation [6])
- Compute another point from such that , becomes the second sub-share of .
- Erase both and from memory.
- Return the signing share and the sub-share .
3.2. Share reconstruction
Given a signing share and a sub-share as input (i.e. the outputs of the share splitting protocol in section 3.1) and access to the decentralized identity with secret key , the share reconstruction protocol proceeds as follows:
- Compute a signature .
- Compute a sub-share as the point .
- Generate the line by performing Polynomial Interpolation [6] using and as inputs.
- Compute as the constant term of .
- Erase both and from memory.
- Return as the secret share.
NOTE: The signature parameters and in are already computed modulo . We use the notation for the sub-share to make it clear (at a glance) that the sub-shares are computed using finite field arithmetic.
4. Threshold Signature Scheme Augmentations
The general approach for augmenting threshold signature protocols (i.e. key generation and signing - and optionally key refresh) is for each party to sign a non-interactive replay resistant challenge during the first round of communication to prove that it currently controls the associated decentralized identity. The other parties then verify the challenge signature at the beginning of the next round or identify the culprit and halt.
Key generation and key refresh protocols typically include a commitment to secret and random values in their first round while signing includes an arbitrary message, so either a commitment (e.g. for key generation and key refresh) or the message (e.g. for signing) is unambiguously concatenated with a protocol specific prefix and the current timestamp to generate a non-interactive replay resistant challenge.
NOTE: While most threshold signature schemes don't define a key refresh protocol (e.g. GG20 [2] and FROST20 [4]), it is relatively straightforward to derive such a protocol from a standard proactive secret sharing scheme like HJKY95 [7]. However, for applications that require support for access structure modification, it is preferable to derive a key refresh protocol from a share redistribution scheme like DJ97 [8] or WW01 [9], as the latter are more flexible and allow for both proactive security and access structure changes (see section 6 for details and additional considerations).
NOTE: While general sharing (and specifically the case where ) is not formally specified in CGGMP20 [1], it can be derived in a relatively straightforward manner based on GG18 [10] (and GG20 [2]) for the key generation and signing protocols (as described in section 1.2.8 of CGGMP20 [1]) and HJKY95 [7] (or WW01 [9]) for the key refresh protocol. In particular, this entails performing -out-of- Feldman's verifiable secret sharing [11] of the secret shares for key generation (as described in section 2.8 and phase 2 of section 3.1 in GG20 [2] and similarly in section 2.6 and phase 2 of section 4.1 in GG18 [10]) or refresh shares for key refresh (with some modifications as described in sections 3.3 and 3.4 of HJKY95 [7] or in section 4 of WW01 [9]), and transforming to shares (using the appropriate Lagrangian coefficients) for pre-signing and signing (as described in section 3.2 in GG20 [2] and similarly in section 4.2 in GG18 [10]).
4.1. Key Generation
Follow the key generation protocol described in section 3.1 and figure 5 of CGGMP20 [1] to generate ECDSA secret shares with the following modifications:
- At the end of Round 1, broadcast 2 additional parameters for each associated with the decentralized identity with verifying key and secret key as follows:
- The decentralized identity verifying key .
- The current UTC timestamp .
- The signature .
- At the beginning of Round 2, for each , verify from all where :
- Verify that or report the culprit and halt.
- Verify by checking that the output of is valid or report the culprit and halt.
- After the Output phase, follow the share splitting protocol in section 3.1 to split secret share into a signing share and a sub-share for each party .
- Modify Stored State for each as follows:
- Don't store .
- Add , and .
4.2. Signing
Follow the signing protocol described in sections 4.2 and 4.3 and figure 8 of CGGMP20 [1] to generate an ECDSA signature with the following modifications:
- Before Round 1, for each party , follow the share reconstruction protocol in section 3.2 to reconstruct secret share .
- At the end of Round 1, for each associated with the decentralized identity with verifying key and secret key , send 2 additional parameters to all where as follows:
- The decentralized identity verifying key .
- The current UTC timestamp .
- The signature .
- At the beginning of the Output phase, verify from all where as follows:
- Verify that or report the culprit and halt.
- Verify that is within the current epoch for identity authenticated requests or report the culprit and halt.
- Verify by checking that the output of is valid or report the culprit and halt.
4.3. Key Refresh
Follow the key refresh protocol described in section 3.2 and figure 6 of CGGMP20 [1] to generate new ECDSA secret shares with the following modifications:
- At the end of Round 1, broadcast 2 additional parameters for each associated with the decentralized identity with verifying key and secret key as follows:
- The decentralized identity verifying key .
- The current UTC timestamp .
- The signature .
- At the beginning of Round 2, for each , verify from all where as follows:
- Verify that or report the culprit and halt.
- Verify by checking that the output of is valid or report the culprit and halt.
- After the Output phase, follow the share splitting protocol in section 3.1 to split the new secret share into a new signing share and a new sub-share for each party .
- Modify Stored State for each as follows:
- Don't store .
- Replace with and with .
5. Identity Authentication and Quorum Approval
5.1. Identity Authenticated Request
Decentralized identity authenticated requests allow parties to perform or request actions based on their associated decentralized identity.
5.1.1. Identity Authenticated Request Initiation
To initiate an identity authenticated request with a command from a party associated with decentralized identity with verifying key and secret key :
- Read the current UTC timestamp .
- Compute the signature .
- Broadcast , , and .
5.1.2. Identity Authenticated Request Verification
To verify an identity authenticated request with a command from a party given its associated decentralized identity verifying key , a timestamp , a signature and a set of verified decentralized identities for all other parties as input:
- Verify that or report the culprit and halt.
- Verify that is within the current epoch for identity authenticated requests or report the culprit and halt.
- Verify by checking that the output of is valid or report the culprit and halt.
5.2. Identity Challenge
Identity challenges are used to verify that a party controls a decentralized identity.
5.2.1. Identity Challenge Initiation
To issue an identity challenge to a party from all verifying parties where for a verified request with command initiated at timestamp :
- Sample a random .
- Broadcast , and to all parties, such that all parties can compute .
5.2.2. Identity Challenge Response
For a party with associated decentralized identity secret key , to respond to an identity challenge for a command initiated at timestamp , given from all parties where :
- Compute .
- Compute the signature .
- Broadcast , , and to all verifying parties .
5.2.3. Identity Challenge Response Verification
To verify an identity challenge response from a party for a command initiated at timestamp , given its associated decentralized identity verifying key , a signature and from all verifying parties where as input:
- Compute .
- Verify by checking that the output of is valid or report the culprit and halt.
5.3. Identity Rotation
Identity rotation allows any party to change the decentralized identity associated with its secret share.
Identity rotation for a party from a decentralized identity with verifying key and secret key to a decentralized identity with verifying key and secret key proceeds as follows:
- For , initiate an "identity-rotation" request by following the protocol in section 5.1.1.
- For all where :
- Verify the "identity-rotation" request by following the protocol in section 5.1.2.
- Initiate an identity challenge for by following the protocol in section 5.2.1.
- For , respond to the identity challenge by following the protocol in section 5.2.2 with the following augmentations:
- Compute an additional signature .
- Add and to the broadcast parameters.
- For all where :
- Verify the identity challenge response from by following the protocol in section 5.2.3.
- Verify that controls the new decentralized identity verifying key as follows:
- Compute :
- Verify by checking that the output of is valid or report the culprit and halt.
- Modify Stored State as follows:
- Create by replacing with in .
- Replace with .
- Broadcast confirmation of successful rotation of the verifying key for .
- For , upon receiving confirmation of successful rotation from a quorum of :
- Compute the new signing share and sub-share based on the new decentralized identity as follows:
- Compute the secret share by following the share reconstruction protocol in section 3.2.
- Follow the share splitting protocol in section 3.1 to split into a new signing share and a new sub-share based on the new decentralized identity .
- Modify Stored State as follows:
- Replace with in .
- Replace with .
- Replace with .
- Compute the new signing share and sub-share based on the new decentralized identity as follows:
5.4. Quorum Approved Request
Quorum approved requests allow any verified party to initiate actions that require explicit approval from a quorum of verified parties before execution (e.g. share addition and removal, and threshold modification).
A quorum approved request with a command from a party associated with decentralized identity with verifying key and secret key proceeds as follows:
- For , initiate an identity authenticated request by following the protocol in section 5.1.1.
- For all where that approve the requested action:
- Verify the identity authenticated request by following the protocol in section 5.1.2.
- Initiate an identity challenge for by following the protocol in section 5.2.1 with the following augmentations:
- Compute a signature .
- Add and to the broadcast parameters.
- For , upon receiving an augmented identity challenge from a quorum such that , respond to the identity challenge by following the protocol in section 5.2.2 with the following modifications:
- At the beginning of the identity challenge response protocol, verify that approvals have been received from a valid quorum of signatories by checking that such that and where , the output of is valid or report the culprit and halt.
- Compute as where .
- Add to the broadcast parameters.
- For all where :
- Verify the augmented identity challenge response from by following the protocol in section 5.2.3 with the following modifications:
- Compute as where .
- Verify that a valid quorum of signatories has approved the request as follows:
- Verify that or report the culprit and halt.
- Verify that or report the culprit and halt.
- Verify that where , the output of is valid or report the culprit and halt.
- Verify the augmented identity challenge response from by following the protocol in section 5.2.3 with the following modifications:
6. Access Structure Modification
Access structure modification allows a quorum of verified parties to perform any of the following actions:
- share addition - issue a secret share to a new party and its associated decentralized identity
- share removal - revoke the secret share of any party.
- threshold modification - change the threshold (i.e. change the size of the quorum).
As noted in section 4, most threshold signature schemes don't define a key refresh protocol, and this is also the case for access structure modification protocols. However, it is similarly relatively straightforward to derive a suitable access structure modification protocol from a standard share redistribution scheme like DJ97 [8] or WW01 [9].
In fact, for applications that require support for access structure modification, it is preferable to replace a key refresh protocol based on (or similar to) a proactive secret sharing scheme like HJKY95 [7] (as is the case for CGGMP20 [1] key refresh) with a protocol based on (or similar to) a share redistribution scheme like DJ97 [8] or WW01 [9] as the latter are more flexible and allow for both proactive security and access structure changes.
NOTE: For threshold signature schemes with identifiable aborts (e.g. CGGMP20 [1], GG20 [2] and FROST20 [4]), key refresh protocols should be derived from verifiable share redistribution schemes like WW01 [9] to preserve the same security model.
Therefore, access structure modification can be achieved by following the augmented key refresh protocol described in section 4.3 of this document, with some modifications based on a verifiable share redistribution scheme like WW01 [9] (or similar) as described above. In particular, this entails each party (from a suitable subset of parties) performing a -out-of- (where and denote the new threshold and new number of parties respectively) Feldman's verifiable secret sharing [11] (with some modifications as described in section 4 of WW01 [9]) of its current secret share (i.e. the output from either key generation or the most recent key refresh) with other parties (in the suitable subset).
6.1. Share Addition
Share addition for a new party with associated decentralized identity proceeds as follows:
- Initiate a quorum approved "share-addition" request by following the protocol in section 5.4.
- Follow the augmented key refresh protocol described in section 4.3, with verifiable share redistribution modifications as described above and with included as a participant, if the quorum approved request above succeeds.
6.2. Share Removal
Share removal for a party with associated decentralized identity proceeds as follows:
- Initiate a quorum approved "share-removal" request by following the protocol in section 5.4.
- Follow the augmented key refresh protocol described in section 4.3, with verifiable share redistribution modifications as described above and without , if the quorum approved request above succeeds.
6.3. Threshold Modification
Threshold modification proceeds as follows:
- Initiate a quorum approved "threshold-modification" request by following the protocol in section 5.4.
- Follow the augmented key refresh protocol described in section 4.3, with verifiable share redistribution modifications as described above, if the quorum approved request succeeds.
7. Share Recovery
Share recovery is only possible if the user's decentralized identity either survived or can be recovered after the disastrous event. In either case, there are two options for share recovery depending on:
- A quorum of honest parties surviving the disastrous event.
- A backup (preferably encrypted) of a signing share and sub-share pair on user-controlled secondary or device-independent storage.
7.1. Share recovery with a surviving quorum of honest parties
If a quorum of honest parties survives the disastrous event, share recovery can be accomplished based on peer-to-peer decentralized identity authentication.
Share recovery for a party with associated decentralized identity with verifying key and secret key proceeds as follows:
- For , Initiate a "share-recovery" request by following the protocol in section 5.1.1.
- For all where :
- Verify the "share-recovery" request by following the protocol in section 5.1.2.
- Initiate an identity challenge for by following the protocol in section 5.2.1.
- For , respond to the identity challenge by following the protocol in section 5.2.2.
- For all where , verify the identity challenge response from by following the protocol in section 5.2.3.
- Follow the key refresh protocol described in section 4.3 if all verifications above pass.
7.2. Share recovery with a backup
7.2.1. Overview of share recovery with a backup
From the share splitting and reconstruction protocol in section 3, we note that for any party , the combination of a signing share and a sub-share alone is insufficient to reconstruct the secret share . This is because a signature of from the decentralized identity is required to compute the sub-share , so that and can then be used to reconstruct and compute the secret share as the constant term of .
Therefore, a signing share and sub-share pair can be safely backed up to user-controlled secondary (e.g. a secondary device or a flash drive) or device-independent storage (e.g. Apple iCloud 1, Google Drive 2, Microsoft OneDrive 3, Dropbox 4 e.t.c) without exposing the secret share .
7.2.2. Generating an encrypted backup for share recovery
For increased security, a signature of a standardized phrase can be used as entropy for generating an encryption secret which can then be used to encrypt the signing share and the sub-share using a symmetric encryption algorithm before saving them to back up storage.
Given a standardized phrase , a key derivation function , a symmetric encryption algorithm , this proceeds as follows:
- Compute the signature .
- Generate the encryption secret .
- Compute the ciphertext for the signing share as .
- Compute the ciphertext for the sub-share as .
- Erase both and from memory.
- Save and to backup storage.
7.2.3. Decrypting an encrypted backup
Share recovery would then start by signing this standardized phrase, using the signature to recreate the encryption secret and then decrypting the encrypted backup to retrieve the signing share and the sub-share .
Given a standardized phrase , a key derivation function , a symmetric encryption algorithm , the ciphertext for the signing share and the ciphertext for the sub-share , this proceeds as follows:
- Compute the signature .
- Generate the encryption secret .
- Compute the signing share .
- Compute the sub-share .
- Erase both and from memory.
- Return the signing share and the sub-share .
7.2.4. Further security and usability considerations for share recovery with a backup
For further improved security and usability, the signing share can be prefixed with a custom message that alerts the user to the purpose of the signature. This can help reduce the effectiveness of an adversary that gains access to the backup and tries to trick the user into signing .
Additionally, it's possible to rerun the share splitting protocol to generate a new pair of a signing share and a sub-share such that , and to be specifically used for backup and recovery. This gives us the option to have separate signing shares for backup and recovery with customized prefixes that make it clear to the user that they're signing a backup signing share.
Lastly, the "backup" signing share can be generated based on user input (e.g. a passphrase or security questions) removing the need for it to be backed up together with a sub-share but instead relying on the user to provide this input during recovery as a security-usability tradeoff.
Acknowledgements
This work is funded by a grant from the Ethereum Foundation 5.
References
- Apple iCloud. https://www.icloud.com.↩
- Google Drive. https://drive.google.com.↩
- Microsoft OneDrive. https://www.microsoft.com/en-us/microsoft-365/onedrive/online-cloud-storage.↩
- Dropbox. https://www.dropbox.com.↩
- Ethereum Foundation: Ecosystem Support Program. https://esp.ethereum.foundation.↩