Unbiasable Randomness

Generation with VRF and VDF

Sharding in blockchain involves the methodology of assigning nodes into different shards. Nodes within the same shards forms a committee and run consensus in parallel. Various approaches have been proposed to assign nodes into shards such as randomness-based sharding in Omniledger and RapidChain [1,2], location-based sharding, and centrally-controlled sharding. Out of all the approaches, randomness-based sharding has been recognized as the most secure solution. In randomness-based sharding, a mutually agreed random number is used to determine the sharding assignment for each node. The random number must have the following properties:

  1. Unpredictable: No one should be able to predict the random number before it’s generated.

  2. Unbiasable: The process of generating the random number should not be bias-able by the participants.

  3. Verifiable: The validity of the generated random number should be verifiable.

  4. Scalable: The algorithm of randomness generation should scale to large number of participants.

Omniledger uses the RandHound [3] protocol, which is a leader-driven distributed randomness generation (DRG) process that involves PVSS (Publicly Verifiable Secret Sharing) and Byzantine Agreement. RandHound is a O(n*c2) complex protocol that divides participant nodes into multiple groups of size c. It achieves the first three properties above but is impractically slow to qualify as scalable.

RapidChain [2] takes an easier and faster approach by letting each participant do VSS (Verifiable Secret Sharing) and using the combined secret shares as the resulting randomness. Unfortunately, this protocol is not secure because the malicious nodes can send inconsistent shares to different nodes [3]. Besides, RapidChain [2] does not describe how the nodes reach consensus on the multiple versions of reconstructed randomness.

In addition, Algorand relies on the VRF-based (Verifiable Random Function) cryptographic sortition to select the group of consensus validators. The Ethereum 2.0 design proposed the use of VDF (Verifiable Delay Function) [4] to delay the revelation of the actual random number so as to prevent last-revealer attack. VDF [4] is a recently studied cryptographic primitive which takes an adjustable minimum amount of time to compute and the result can be verified immediately.

Harmony’s approach borrows elements from the above works, but differs from them in the following ways. First, Harmony’s DRG protocol is O(n) complex, which is at least an order of magnitude faster than RandHound. Second, unlike RapidChain’s simple VSS-based approach, ours is unbiasable and verifiable. Third, compared to Ethereum 2.0’s solution, our approach uses BFT consensus to provide finality to the random number. Besides, the DRG protocol runs naturally with the shard committee of a leader and many validators. Specifically, the protocol contains the following steps:

  1. A leader sends an init message with the hash of the last block H(Bn-1) to all the validators to start the DRG protocol.

  2. For each validator i, after receiving the init message, a VRF is computed to create a random number ri and a proof pi: (ri, pi)=VRF(ski, H(Bn-1), v) , where ski is the secret key of validator i and v is the current view number of consensus. Then, each validator sends back (ri, pi) to the leader.

  3. The leader waits until it receives f+1 valid random numbers and combine them with XOR operation to get the random number preimage pRnd.

  4. The leader runs BFT (discussed in §2) among all the validators to reach consensus on the pRnd and commit it in block Bn.

  5. After pRnd is committed, the leader starts computing the actual randomness Rnd=VDF(pRnd, T), where T is the VDF difficulty and is set algorithmically such that the randomness can only be computed after k blocks.

  6. Once Rnd is computed, the leader initiates a BFT among all validators to agree on the validity of Rnd and finally commit the randomness into the blockchain.

The use of VDF here is to provably delay the revelation of Rnd and avoid malicious leader biasing the randomness by specifically selecting a subset of the VRF random numbers. With VDF, the leader won’t be able to know what’s the actual randomness before the pRnd is committed into the blockchain. Therefore, the best a malicious leader can do is either blindly commiting the randomness pRnd, or stalling the protocol by not committing the pRnd. The former is the same as the honest behavior. The latter won’t cause much damage as the same timeout mechanism in PBFT will be used to switch the leader and restart the protocol.

[1] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger via sharding,” in 2018 IEEE Symposium on Security and Privacy (SP), pp. 19–34, 2018. https://eprint.iacr.org/2017/406.pdf 2 [2] M. Zamani, M. Movahedi, and M. Raykova, “RapidChain: A Fast Blockchain Protocol via Full Sharding.” Cryptology ePrint Archive, Report 2018/460, 2018. https://eprint.iacr.org/2018/460. [3] E. Syta, P. Jovanovic, E. Kokoris-Kogias, N. Gailly, L. Gasser, I. Khoffi, M. J. Fischer, and B. Ford. Scalable Bias-Resistant Distributed Randomness. In 38th IEEE Symposium on Security and Privacy, May 2017. https://eprint.iacr.org/2016/1067.pdf 1 [4] Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable delay functions. In CRYPTO 2018, 2018. https://eprint.iacr.org/2018/601.pdf 3