Distributed Randomness Beacon
The research in this article is provided by Enya Labs as part of their contributions to Boba Network.
Written by Jia Liu
Summary
We present an implementation of distributed randomness beacons (DRBs) using threshold cryptography, zk-SNARKs, and BLS signatures. This process generates unique, publicly verifiable, unpredictable and unbiased pseudorandom values in a decentralized network, such as a blockchain network. Technically, our DRB is built from a distributed verifiable random function (DVRF), a cryptographic primitive that enables a group to collectively compute a pseudorandom value. The instantiation of our DVRF has two main components:
- Non-interactive distributed key generation (NI-DKG): This is the key setup process for a group of n participants to distribute their secret keys via t-out-of-n threshold secret sharings in a non-interactive way. Non-interactive means that the participants don’t need to exchange messages multiple times, making the protocol easier to implement in practice. We use zk-SNARKs to guarantee the validity of the data generated by each participant and we implement this protocol in Halo2 — a plonk based zero knowledge proving system.
- Randomness generation: After the keys are set up, participants can collaborate to compute pseudorandom values over many rounds. Each round is uniquely identified by a public input, such as a timestamp or counter. Each participant provides a partial evaluation for the input, and a threshold number of these partial evaluations can be combined to produce the final pseudorandom value. This pseudorandom output is deterministic for each input, but unpredictable until the value is created.
The significance of this work is:
- Decentralization and Trustlessness: DRBs are central to many decentralized systems and cryptographic applications, such as blockchain and smart contracts. They ensure fairness, security, and trustworthiness by generating random numbers in a way that no participant or coalition of participants can predict or bias the outcome. This work can help design more secure, efficient, and fair decentralized systems.
- Improved Efficiency and Practicality: The existing solutions for DKG either require a lot of communication between participants, which is difficult to implement, or they require each participant to publish a large amount of data, which is slow and inefficient. By proposing a more efficient protocol, we contribute to making these cryptographic systems more practical for real-world use.
- Secure Pseudorandomness: DRBs ensure the pseudorandom numbers are not only secure and unpredictable but also publicly verifiable. This adds an extra layer of security and trust, as anyone can verify that the pseudorandom numbers have been correctly computed, without needing to trust any party in the system.
- Applicability to Ethereum and other Blockchains: Our DRB is designed to be as compatible as possible with Ethereum, one of the most widely used blockchain platforms, to facilitate the adoption of the protocol in the blockchain and crypto industry. However, some of the necessary operations in DRB are not natively supported by Ethereum. Therefore, we also discuss how the protocol could be integrated on Ethereum using some workarounds.
Introduction
Distributed randomness beacons (DRBs) aim to enable a group of n participants to jointly compute a random output in a way that prevents a participant or coalition of participants from predicting or biasing the outcome. DRBs have many applications, including verifiable lotteries and leader election in distributed consensus protocols. Here are a few potential use cases:
- Random Sampling in Decentralized Networks: In decentralized systems, there may be a need to select a random sample of nodes for certain tasks. Blockchain systems often require a source of randomness for various purposes, such as electing proposers for the next block, forming a consensus group, shuffling validators, or assigning tasks in a decentralized network. DRBs can be used to generate random numbers that no participant can predict or manipulate.
- Decentralized Lotteries and Gaming: In decentralized lotteries, the fairness of the draw is paramount. A distributed randomness beacon that can be verified by anyone, and which no participant can manipulate, would be an ideal solution. This also applies to other forms of gaming where randomness is required.
- Decentralized Decision Making: In any decentralized decision-making process, from voting systems to collective governance protocols, it might be necessary to randomly select participants for certain roles, responsibilities, or rights. A public, verifiable source of randomness would be critical in these systems.
Remember that the success of all these use cases relies not only on the randomness being unpredictable and unbiased, but also on it being publicly verifiable, which our protocol achieves. This guarantees a high level of trust and fairness in all of these applications.
DRBs can be constructed from distributed verifiable random function (DVRFs) [1,2,3,4]. A DVRF is a t-out-of-n threshold cryptographic scheme that achieves the following security properties:
- Uniqueness: given an input x, the output pseudorandom value v is deterministic. Uniqueness is crucial for certain decentralized applications, such as selecting the next block proposer or the next set of validators in a consensus protocol. Uniqueness guarantees a deterministic choice for the next block, and without it, the blockchain will fork and fail to reach consensus.
- Public verifiability: anyone can verify a cryptographic proof that the pseudorandom value v is correctly computed. There is no need to trust any party to honestly create the random value.
- Pseudo-randomness: the distribution of v is indistinguishable from random. No one can predict the value of v before it’s created, and no one is able to bias the value of v to their advantage.
Related work. The DVRF constructions proposed in [2] rely on an interactive distributed key generation (DKG) protocol to initiate the global public parameters and members’ secret keys. This interactive setup involves several rounds of communications among members, making it difficult to implement in practice. Dfinity proposes a non-interactive distributed key generation (NI-DKG) protocol in [3] but each participant publishes a huge amount of data (i.e., chunk encryptions for shares and proofs) and its verification time is very slow. A snark-based NI-DKG was implemented in [5] using BLS12–377/BW6 curves which are 2-chain pairing curves. However, these two curves are not natively supported on Ethereum, as there are no precompiles for curve operations on BLS12–377/BW6.
Protocol description
Performance
Our DVRF proof-of-concept implementation can be found at: https://github.com/bobanetwork/
zkdvrf. We have evaluated its performance on an AWS instance r6i.8xlarge, which has 32 CPUs and 256GB of memory.
The proof size remains constant and the verification time can be further reduced by hashing the public inputs which is not yet implemented. The peak memory usage of 19GB for 43 participants is moderate. In practice, 43 nodes should be sufficient for most applications. For example, Drand began with a threshold of 6-out-10 in 2019 and currently operates 23 nodes with a threshold of 12 to create verifiable randomness. In the future, we will explore recursive SNARKs to further reduce memory usage and on-chain verification costs.
- Randomness generation:
The performance of a single partial evaluation, its verification, and the verification of the final pseudorandom value are independent of the values of (t,n).
Ethereum integration considerations
Ethereum has precompiles for bn256 curve but it doesn’t support some of the necessary operations required by our DVRF. Below we suggest some workarounds:
- Ethereum does not have precompiles for hash_to_curve, we can implement the function in Solidity (for example, https://github.com/thehubbleproject/hubble-contracts/blob/master/
contracts/libs/BLS.sol). Alternatively, as a Layer 2 rollup network, we can deploy this precompile (https://eips.ethereum.org/EIPS/eip-3068) to save on gas costs.
References:
[1] Timo Hanke, Mahnush Movahedi, and Dominic Williams. DFINITY technology overview series, consensus system. CoRR, abs/1805.04548, 2018.
[2] David Galindo, Jia Liu, Mihai Ordean, Jin-Mann Wong: Fully Distributed Verifiable Random Functions and their Application to Decentralised Random Beacons. EuroS&P 2021: 88–102. https://eprint.iacr.org/2020/096.pdf
[3] Jens Groth: Non-interactive distributed key generation and key resharing. IACR Cryptol. ePrint Arch. 2021: 339 (2021). https://eprint.iacr.org/2021/339.pdf
[4] Drand: https://drand.love/docs/overview/#how-drand-works
