Note: The first sections are meant to be an introduction to how threshold networks work. If you want to read the DKG specs Medusa implements, skip to the last section of this page.
The purpose of the setup phase is to create a collective private, and public key pair shared among participants. This is done through a -of- Distributed Key Generation (DKG) process at the end of which each of the participants obtains a copy of the collective public key, together with a private key share of the collective private key. The key shares are computed such that no individual node knows the entire collective private key.
Each private key share can then be used to perform cryptographic threshold computations, such as generating threshold signatures, where at least contributions produced using the individual private key shares are required to successfully finish the collective operation.
A DKG is performed in a fully distributed manner, avoiding any single points of failure. We give an overview of the different sub-components of the DKG implementation in the following subsections.
Secret sharing is an important technique that many advanced threshold cryptography mechanisms rely on. Secret sharing allows one to split a secret value into shares such that can only be reconstructed if a threshold of shares is available.
Shamir's Secret Sharing (SSS) scheme is one of the most well-known and widely used secret sharing approaches, and it is a core component of Medusa. SSS works over an arbitrary finite field, but for simplicity, we use the integers modulo denoted by . Let denote the secret to be shared.
Share Distribution: To share a dealer first creates a polynomial with and (random) for
The dealer then creates one share for each participant by evaluating at the integer and setting .
Secret Reconstruction: To recover the secret , one first collects at least shares, then uniquely reconstructs via Lagrange interpolation, and finally obtains as .
Note that any subset of -of- shares can be used to perform Lagrange interpolation and uniquely determine . Having any subset of fewer than shares does not allow one to learn anything about , though.
Verifiable secret sharing
Shamir's Secret Sharing scheme assumes that the dealer is honest but this assumption might not always hold in practice.
A Verifiable Secret Sharing (VSS) scheme protects against malicious dealers by enabling participants to verify that their shares are consistent with those dealt to other nodes ensuring that the shared secret can be correctly reconstructed later on.
Medusa relies on a variation of Feldman's VSS scheme, an extension of SSS. Let denote a cyclic group of prime order in which computing discrete logarithms is intractable.
A cyclic group means there exists a generator such that any element can be written as for some .
Share Distribution: In addition to distributing shares of the secret to the participants, the dealer also broadcasts commitments to the coefficients of the polynomial of the form .
These commitments enable each participant to verify that their share is consistent with respect to the polynomial by checking that holds.
Secret Reconstruction: The recovery of secret works as in regular SSS with the difference that verified to be valid shares are used.
Pedersen's distributed key generation (DKG)
Although VSS schemes protect against a malicious dealer, the dealer still knows the secret itself. To create a collectively shared secret such that no individual node gets any information about it, participants can utilize a Distributed Key Generation (DKG) protocol.
Medusa relies on a variation Pedersen's DKG scheme, which essentially runs instances of Feldman's VSS in parallel on top of some additional verification steps. The final scheme is explained in the next section.
Share Distribution: Every participant creates a (random) secret and shares it with all other participants using VSS by sending a share to each participant and broadcasting the list of commitments to everyone.
Share Verification: Each participant verifies the shares it receives as prescribed by Feldman's VSS scheme. If participant receives an invalid share from participant , then broadcasts a complaint. Afterward, participant must reveal the correct share or is considered an invalid dealer.
Share Finalization: At the end of the protocol, the final share of participant is for all participants that are valid, i.e., for all those not excluded during the verification phase.
The collective public key associated with the valid shares can be computed as for all valid participants .
Even though this DKG allows for some biasability in the final private key, because participants don't commit to the polynomial beforehand as in the Gennaro et al. one, it has been proven that the resulting key can be used for any re-keyable scheme such as BLS signature or El Gamal encryption, in this Mary et al. paper. This is sufficient for our purposes.
In Medusa, we rely on a smart contract to do the communication and we also use it for doing some verifications. Specifically, we employ Neji's DKG version that makes use of the computation capabilities of the smart contract.
Specfically, it enables us to skip the justification phase by having the contract directly verify onchain if a complaint is valid or not. If the complaint is valid, then the dealer is disqualified. If not valid, then the complainer is disqualified.
Each participant registered with a temporary private/public keypair at the beginning of the protocol. How and where is out of scope for this crypto spec but you can think of it as if every participant save their public keys on a common smart contract.
We assume there is participants and we set the threshold as being the number of parties necessary to perform an operation with the distributed secret key.
Each participant does the following:
- Generate T random coefficients for a polynomial of degree T-1
- Compute shares
- Note in the future we might replace the indices with roots of unity
- Compute commitment to the polynomial: by multiplying all coefficients by the base generator
- Generate a random scalar and
- Compute encryption of the share for each recipient:
- For recipient i, compute where transforms the scalar into bytes in little endian format.
- Output the deal consisting of:
- Coefficients of
- Encryption vector:
Each recipient i perform the following verification:
- Compute shared key
- Decrypts share (interprets results as a scalar)
- Verify consistency:
- If consistency check is not passing, then go to complaint phase.
The recipient whose share is invalid will prove it to the smart contract by giving the shared key to the smart contract and proving it is the correct one without revealing its private key.
- Generate a random
- Compute and
- Output proof
The smart contract will use the information from the deals and from the proof:
- Check if
- If not, the complaint is not valid (the smart contract can decide to slash etc, out of scope of this document)
- Note the verifier must have the ciphertext not from the complainer but from the first phase. Using smart contract it is either registered onchain or the hash of it.
- If check is valid, then decrypt the share
- Verify the consistency:
- If consistency is verified, complaint is not valid (the deal was correctly created)
- If consistency check fails, the complaint is valid and the dealer must be excluded from the list of valid participants.
This phase happens after the first two and is simply the phase where the distributed keypair can be computed.
Secret Share for participant i:
for all dealers that were not excluded during the complaint phase.
for all dealers that were not excluded during the complaint phase.