# Setup Phase

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 receiving 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

Secret sharing is an important technique many advanced threshold cryptography mechanisms rely on.

Secret sharing allows you to split a secret value `π `

into `π`

shares `π 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 `β€π`

. Let `π ββ€π`

denote the secret to share.

### β Share Distribution

To share `π `

, a dealer first creates a polynomial, `π(π₯)=π0+π1π₯+β―+ππ‘β1π₯π‘β1`

with `π0=π `

and (random) `ππββ€π`

for `π=1,β¦,π‘β1`

and then creates one share π π for each participant π by evaluating π(π₯) at the integer π and setting π π=(π,π(π)).

### β Secret Reconstruction

To recover the secret `π `

, collect at least `π‘`

shares, then uniquely reconstruct `π(π₯)`

using Lagrange interpolation and obtain `π `

as `π =π0=π(0)`

.

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 `πβ{0,β¦,πβ1}`

.

### β Share Distribution

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 `ππ(π)=βπ‘β1π=0(π΄π)ππ`

holds.

### β Secret Reconstruction

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.

### β Share Distribution

Individual participants, `π`

, 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.

### β Share Verification

`π`

verifies the shares received as prescribed by Feldmanβs VSS scheme. If `π`

receives an invalid share, `π π,π`

, from `π`

, then `π`

broadcasts a complaint. `π`

must reveal the correct share `π π,π`

or they are considered an invalid dealer.

### β Share Finalization

At the end of the protocol, the final share of `π`

is `π π=βππ π,π`

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 `π`

s.

**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.