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 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 :12 with these properties:

• Bilinearity: ,,1,2, we have (,)=(,)

• Non-degeneracy: 1

• Computability: There exists an efficient algorithm to compute . drand currently uses the Barreto-Lynn-Scott curve BLS12-381.

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

To generate a key pair, a signer first chooses a private key, , at random, and then computes the corresponding public key as =22.

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 computes =()1.

To verify that a BLS signature on a message is valid, the verifier checks if ((),)=(,2) holds using the signers public key .

Note that this equation holds for valid signatures since ((),)=((),2)=((),2)=((),2)=(,2).

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.

The participants run a -of- DKG to setup a collective public key, 2, and private key shares of the unknown collective private key, , as described above.

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

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.

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

To verify a collective BLS signature, , a verifier 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.

In the above, 1 and 2 could be swapped. The implication is on the relative size of public key and signatures. The first drand chains are constructed as described above, with signatures on 2 and public keys on 1. Signature size is 96 bytes, and public key size is 48 bytes.

Certain applications prefer smaller signatures at the cost of a larger public key. This is why certain drand beacons have signatures on 1 and public key on 2. Such a change is referred to as 1/2 swap.

The drand randomness beacon operates in discrete rounds, . In every round, drand beacons configured to use chained randomness produce 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.

drand beacons can also be configured to use unchained randomness. To extend this chain of randomness, each drand participant, , creates in round the partial BLS signature, on the message =() where a cryptographic hash function.

This process allows for a direct precomputation of message for round =i.