Randomness Generation

In this section, we describe how to use this collective key pair to generate publicly-verifiable, unbiasable, and unpredictable randomness in a distributed manner.

First, we explain pairing-based cryptography (PBC), which has become quite popular, and is used in many modern consensus protocols or zero-knowledge proofs, such as zk-SNARKs. We will then show how drand uses PBC for the randomness beacon generation phase for threshold Boneh-Lynn-Shacham (BLS) signatures. Finally, we will discuss how drand links the generated threshold BLS signatures into a randomness chain.

​​ Pairing-based Cryptography

Pairing-based cryptography is based on bilinear groups (𝔾1,𝔾2,𝔾𝑡), where 𝔾1, 𝔾2, and 𝔾𝑡 are cyclic groups of prime order 𝑝 with generators 𝑔1, 𝑔2, and 𝑔𝑡, respectively, and a pairing operation 𝑒:𝔾1×𝔾2→𝔾𝑡 with these properties:

• Bilinearity: ∀𝑎,𝑏∈ℤ∗𝑝,∀𝑃∈𝔾1,∀𝑄∈𝔾2, we have 𝑒(𝑎𝑃,𝑏𝑄)=𝑒(𝑃,𝑄)𝑎𝑏

• Non-degeneracy: 𝑒≠1

• Computability: There exists an efficient algorithm to compute 𝑒. Drand currently uses the Barreto-Naehrig curve BN256.

​​ BLS Signatures

To generate publicly-verifiable, unbiasable, distributed randomness, drand utilizes threshold Boneh-Lynn-Shacham (BLS) signatures. First we will describe regular BLS signatures and then the threshold variant.

BLS signatures are short signatures that rely on bilinear pairings and consist only of a single element in 𝔾1. They are deterministic in the sense they depend only on the message and the signer’s key, unlike other signature schemes, such as ECDSA, that require a fresh random value for each signed message to be secure. Put differently, any two BLS signatures on a given message produced with the same key are identical. In drand, we utilize this property to achieve unbiasability for randomness generation.

The BLS signature scheme consists of the these sub-procedures.

​​ Key Generation

To generate a key pair, a signer first chooses a private key, 𝑥∈ℤ∗𝑝, at random, and then computes the corresponding public key as 𝑋=𝑔𝑥2∈𝔾2.

​​ Signature Generation

Let 𝐻:{0,1}∗→𝔾1 denote a cryptographic hash function that maps arbitrary bit strings to elements of 𝔾1. To compute a BLS signature 𝜎 on a message 𝑚, the signer simply computes 𝜎=𝑥𝐻(𝑚)∈𝔾1.

​​ Signature Verification

To verify that a BLS signature 𝜎 on a message 𝑚 is valid, the verifier checks if 𝑒(𝐻(𝑚),𝑋)=𝑒(𝜎,𝑔2) holds using the signer’s public key 𝑋.

It is easy to see that this equation holds for valid signatures since 𝑒(𝐻(𝑚),𝑋)=𝑒(𝐻(𝑚),𝑔𝑥2)=𝑒(𝐻(𝑚),𝑔2)𝑥=𝑒(𝑥𝐻(𝑚),𝑔2)=𝑒(𝜎,𝑔2).

​​ Threshold BLS Signature

The goal of a threshold signature scheme is to collectively compute a signature by combining individual partial signatures independently generated by the participants. A threshold BLS signature scheme has the following sub-procedures.

​​ Key Generation

The 𝑛 participants execute a 𝑡-of-𝑛 DKG to setup a collective public key, 𝑆∈𝔾2, and private key shares 𝑠𝑖∈ℤ∗𝑝 of the unknown collective private key, 𝑠, as described above.

​​ Partial Signature Generation

To sign a message, 𝑚, each 𝑖 uses their private key share, 𝑠𝑖, to create a partial BLS signature, 𝜎𝑖=𝑠𝑖𝐻(𝑚).

​​ Partial Signature Verification

To verify the correctness of a partial signature, 𝜎𝑖, on 𝑚, a verifier uses the public key share, 𝑆𝑖, generated during the DKG, and verifies that 𝑒(𝐻(𝑚),𝑆𝑖)=𝑒(𝜎𝑖,𝑔2) holds.

​​ Signature Reconstruction

To reconstruct the collective BLS signature, 𝜎 on 𝑚, a verifier first gathers 𝑡 different and valid partial BLS signatures, 𝜎𝑖, on 𝑚 followed by a Lagrange interpolation.

​​ Signature Verification

To verify a collective BLS signature, 𝜎, a verifier simply checks that 𝑒(𝐻(𝑚),𝑆)=𝑒(𝜎,𝑔2) holds, where 𝑆 is the collective public key.

Thanks to the properties of Lagrange interpolation, the value of 𝜎 is independent of the subset of 𝑡 valid partial signatures, 𝜎𝑖, chosen during signature reconstruction. Additionally, Lagrange interpolation also guarantees that no set of less than 𝑡 signers can predict or bias 𝜎.

In summary, a threshold BLS signature, 𝜎, exhibits all properties required for publicly-verifiable, unbiasable, unpredictable, and distributed randomness.

​​ Chained Randomness

The drand randomness beacon operates in discrete rounds, 𝑟. In every round, drand produces a new random value using threshold BLS signatures linked together into a chain of randomness. To extend this chain of randomness, each drand participant, 𝑖, creates in round 𝑟 the partial BLS signature, 𝜎𝑟𝑖 on the message 𝑚=𝐻(𝑟∥𝜎𝑟−1) where, 𝜎𝑟−1 denotes the (full) BLS threshold signature from round 𝑟−1 and 𝐻, a cryptographic hash function.

Once at least 𝑡 participants have broadcasted their partial signatures, 𝜎𝑟𝑖, on 𝑚, anyone can recover the full BLS threshold signature, 𝜎𝑟 that corresponds to the random value of round 𝑟. After this, drand nodes move to round 𝑟+1 and reiterate the process.

For round 𝑟=0, drand participants sign a seed fixed during drand setup. This process ensures that every new random value depends on all previously generated signatures. Since the signature is deterministic, there is also no possibility for an adversary forking the chain and presenting two distinct signatures 𝜎𝑟 and 𝜎′𝑟 in a given round 𝑟 to generate inconsistencies in the systems relying on public randomness.