In the drand setup phase, you create a collective private and public key pair shared among 𝑛 participants. This is done through a
𝑡-of-𝑛 Distributed Key Generation (DKG) process and results in each participant recieving a copy of the collective public key plus a private key share of the collective private key — no individual node knows the 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. This is an overview of the different sub-components of the drand DKG implementation.
Secret sharing is an important technique many advanced threshold cryptography mechanisms rely on.
Secret sharing allows you to split a secret value
𝑠1,…,𝑠𝑛 so that
𝑠 can only be reconstructed if a threshold of
𝑡 shares is available.
Shamir’s Secret Sharing (SSS)
The SSS scheme is one of the most well-known and widely used secret sharing approaches, and a core component of drand. SSS works over an arbitrary finite field, but a simplistic approach uses the integers modulo
𝑝, denoted by
𝑠∈ℤ𝑝 denote the secret to share.
𝑠, a dealer first creates a polynomial,
𝑎0=𝑠 and (random)
𝑖=1,…,𝑡−1 and then creates one share 𝑠𝑖 for each participant 𝑖 by evaluating 𝑞(𝑥) at the integer 𝑖 and setting 𝑠𝑖=(𝑖,𝑞(𝑖)).
To recover the secret
𝑠, collect at least
𝑡 shares, then uniquely reconstruct
𝑞(𝑥) using Lagrange interpolation and obtain
Note that you can use any subset of
𝑡-of-𝑛 shares to perform Lagrange interpolation and uniquely determine
𝑠; however, having a subset of less than
𝑡 shares does not allow to learn anything about
Verifiable Secret Sharing
SSS scheme assumes that the dealer is honest, but this may 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.
drand uses 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,
𝑔, so that any element
𝑥∈𝔾 can be written as
𝑥=𝑔𝑎 for some
In addition to distributing shares of the secret to participants, the dealer also broadcasts commitments to the coefficients of the polynomial
𝑞(𝑥) of the form
(𝐴0,𝐴1,…,𝐴𝑡−1)=(𝑔𝑠,𝑔𝑎1,…,𝑔𝑎𝑡−1). These commitments enable individual participants,
𝑖, to verify that their share
𝑠𝑖=(𝑖,𝑞(𝑖)) is consistent with respect to the polynomial
𝑞(𝑥) by checking that
The recovery of secret
𝑠 works the same as regular SSS, except that verified to be valid shares are used.
Distributed Key Generation (DKG)
Although VSS schemes protect against a malicious dealer, the dealer still knows the secret. To create a collectively shared secret
𝑠 so no individual node gets any information about it, participants can use a DKG protocol. drand uses Pedersen’s DKG scheme, which runs
𝑛 instances of Feldman’s VSS in parallel and on top of additional verification steps.
𝑖, create a (random) secret,
𝑠𝑖∈ℤ𝑝, and share it all participants using VSS, sending a share,
𝑠𝑖,𝑗 to each
𝑗 and broadcasts the list of commitments
(𝐴𝑖,0,𝐴𝑖,1,…,𝐴𝑖,𝑡−1) to everyone.
𝑗 verifies the shares received as prescribed by Feldman’s VSS scheme. If
𝑗 receives an invalid share,
𝑗 broadcasts a complaint.
𝑖 must reveal the correct share
𝑠𝑖,𝑗 or they are considered an invalid dealer.
At the end of the protocol, the final share of
𝑠𝑖=∑𝑗𝑠𝑗,𝑖 for all valid participants
𝑗 , that is, for all
𝑗s not excluded during the verification phase.
The collective public key associated with the valid shares can be computed as
𝑆=∑𝑗𝐴𝑗,0 for all valid
Note: Even though the secret created using Pedersen’s DKG can be biased, it is safe to use for threshold signing as shown by Rabin et al.