Skip to main content

Threshold Network

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 nn participants. This is done through a tt-of-nn Distributed Key Generation (DKG) process at the end of which each of the nn 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 tt 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

Secret sharing is an important technique that many advanced threshold cryptography mechanisms rely on. Secret sharing allows one to split a secret value ss into nn shares s1,,sns_1,\ldots,s_n such that ss can only be reconstructed if a threshold of tt 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 pp denoted by Zp\mathbb{Z}_p. Let sZps \in \mathbb{Z}_p denote the secret to be shared.

Share Distribution: To share ss a dealer first creates a polynomial q(x)=a0+a1x+...+at1xt1q(x) = a_0 + a_1x + ... + a_{t-1}x^{t-1} with a0=sa_0 = s and (random) aZpa \in \mathbb{Z}p for i=1,,t1i = 1,\ldots,t-1

The dealer then creates one share sis_i for each participant ii by evaluating q(x)q(x) at the integer ii and setting si=(i,q(i))s_i = (i,q(i)).

Secret Reconstruction: To recover the secret ss, one first collects at least tt shares, then uniquely reconstructs q(x)q(x) via Lagrange interpolation, and finally obtains ss as s=a0=q(0)s = a_0 = q(0).

Note that any subset of tt-of-nn shares can be used to perform Lagrange interpolation and uniquely determine ss. Having any subset of fewer than tt shares does not allow one to learn anything about ss, 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 G\mathbb{G} denote a cyclic group of prime order pp in which computing discrete logarithms is intractable.

A cyclic group means there exists a generator gg such that any element xGx \in \mathbb{G} can be written as x=gax = g^a for some a0,,p1a \in {0,\ldots,p-1}.

Share Distribution: In addition to distributing shares of the secret to the participants, the dealer also broadcasts commitments to the coefficients of the polynomial q(x)q(x) of the form (A0,A1,,At1)=(gs,ga1,,gat1)(A_0,A_1,\ldots,A_{t−1}) = (g^s,g^{a_1},\ldots,g^{a_{t-1}}).

These commitments enable each participant ii to verify that their share si=(i,q(i))s_i = (i,q(i)) is consistent with respect to the polynomial q(x)q(x) by checking that gq(i)=j=0t1(Aj)ijg^{q(i)} = \prod_{j=0}^{t-1}(A_j)^{i^j} holds.

Secret Reconstruction: The recovery of secret ss 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 ss 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 nn 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 ii creates a (random) secret siZps_i \in \mathbb{Z}_p and shares it with all other participants using VSS by sending a share si,js_{i,j} to each participant jj and broadcasting the list of commitments (Ai,0,Ai,1,,Ai,t1)(A{i,0},A_{i,1},\ldots,A_{i,t-1}) to everyone.

Share Verification: Each participant verifies the shares it receives as prescribed by Feldman's VSS scheme. If participant jj receives an invalid share si,js_{i,j} from participant ii, then jj broadcasts a complaint. Afterward, participant ii must reveal the correct share si,js_{i,j} or is considered an invalid dealer.

Share Finalization: At the end of the protocol, the final share of participant ii is si=jsj,is_i = \sum_j s_{j,i} for all participants jj that are valid, i.e., for all those jj not excluded during the verification phase.

The collective public key associated with the valid shares can be computed as S=jAj,0S = \sum_j A_{j,0} for all valid participants jj.


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.

Neji DKG

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 Ki=kiG1G1K_i = k_i * G_1 \in \mathbb{G_1} 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 nn participants and we set the threshold T>n/2T > n/2 as being the number of parties necessary to perform an operation with the distributed secret key.

Deal Phase


Each participant does the following:

  1. Generate T random coefficients a1,,aTFa_1, … , a_T \in \mathbb{F} for a polynomial f(x)f(x) of degree T-1
  2. Compute nn shares f(1),f(2),,f(n)f(1), f(2), … , f(n)
    1. Note in the future we might replace the indices with roots of unity ω1,ω2\omega^1, \omega^2…
  3. Compute commitment to the polynomial: F(x)=f(x)G1F(x) = f(x) G_1 by multiplying all coefficients by the base generator G1G_1
  4. Generate a random scalar rFr \in \mathbb{F} and R=rG1R = rG_1
  5. Compute encryption of the share for each recipient:
    1. For recipient i, compute Ci=H(rKi)b(f(i))C_i = H(rK_i) \oplus b(f(i)) where b(.)b(.) transforms the scalar into bytes in little endian format.
  6. Output the deal consisting of:
    1. Coefficients of F(x)F(x)
    2. Randomizer RR
    3. Encryption vector: CiC_i


Each recipient i perform the following verification:

  1. Compute shared key Si=kiRS_i = k_iR
  2. Decrypts share f(i)=H(Si)Cif(i) = H(S_i) \oplus C_i (interprets results as a scalar)
  3. Verify consistency: F(i)==f(i)G1F(i) == f(i)G_1
  4. If consistency check is not passing, then go to complaint phase.

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.

  1. Generate a random tFt \in \mathbb{F}
  2. Compute w=tRw = tR and w=tG1w' = tG_1^{'}
  3. Compute u=kiG1u' = k_iG_1^{'}
  4. Compute e=H(Ci,Si,u,w,w)e = H(C_i, S_i, u', w, w')
  5. Compute f=tekif = t - e * k_i
  6. Output proof [Si,e,f,u][S_i, e, f, u']


The smart contract will use the information from the deals and from the proof:

  1. Compute w=fG1+eSi=(teki)R+(eki)R=tRw = fG_1 + eS_i = (t - e*k_i)R + (e*k_i)R = tR
  2. Compute w=fG1+eu=(teki)G1+(eki)G1=tG1w' = fG_1^{'} + eu' = (t - e*k_i)G_1^{'} + (e*k_i)G_1^{'} = tG_1^{'}
  3. Check if e==H(Ci,Si,u,w,w)e == H(C_i, S_i, u', w, w')
    1. If not, the complaint is not valid (the smart contract can decide to slash etc, out of scope of this document)
    2. 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.
  4. If check is valid, then decrypt the share shi=H(Si)Cish_i = H(S_i) \oplus C_i
  5. Verify the consistency: F(i)==shiG1F(i) == sh_i G_1
    1. If consistency is verified, complaint is not valid (the deal was correctly created)
    2. If consistency check fails, the complaint is valid and the dealer must be excluded from the list of valid participants.

Final Phase

This phase happens after the first two and is simply the phase where the distributed keypair can be computed.

Secret Share for participant i:

si=jfj(i)s_i = \sum_j f_j(i) for all dealers jj that were not excluded during the complaint phase.

Public Key

S=jFj(0)S = \sum_j F_j(0) for all dealers jj that were not excluded during the complaint phase.