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:
𝑒≠1Computability: 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.
𝔾1/𝔾2 swap
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 reffered to as 𝔾1/𝔾2 swap.
Chained Randomness
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.
Unchained 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.