Unbiasable Randomness Generation with VRF and VDF

[rongjian]

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] 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
[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

[andy]

Even more important than the performance of generating a random number (when discussing the possibility that an adversary is attempting to bias a salt or nonce) is its entropy.

Randhound doesn’t really deal with the entropy problem. It assumes that an initial source of the random number is sufficiently entropic, and instead focusing on the possibility that an adversary may submit a biased random number [1]. While this is important, just as important/more important is that the PRNG generates a sufficiently entropic random number in the first place.

Entropy is a serious topic in the cryptologic community. There are already a number of different sources and tests for entropy, with NIST SP800-90B arguably governing the best set of testing criteria and resulting sources for entropy [2].

If you’re trying to stop someone from hacking your nonces or salts, focusing on consensus seems far less important than focusing on whether or not someone has submitted a bogus, but validated, pseudorandom number in the first place. I would encourage you to consider enforcing that a number is sufficiently entropic first - either by formally requiring some type of PRNG/TRNG - then moving onto mathematically establishing that the entropy of that number/set of numbers is within a specific range rather than trying to think of this as a consensus problem.

[1] https://eprint.iacr.org/2016/1067.pdf
[2] https://csrc.nist.gov/publications/detail/sp/800-90b/final

[nb1]

Totally agree on the entropy @andy

This is why we are using both VRF and VDF.

VRF provide our weak entropy, which could be be biased with a withholding attack (a node can choose not to commit his randomness).

But as the VDF output is not predictable before the attacker eventually choose to withhold his VRF output, and assuming the VDF is a random oracle, both VDF output would be random.

Does that make sense to you?

[andy]

I’m a bit confused. So to clarify, you’re using VRF to generate your random number and “double checking” that with VDF?

This doesn’t seem to address the root problem of “what if the PRNG I use has insufficient or biased entropy.” To quote the RFC for VRF 1:

“Pseudorandomness, as defined in Section 3.3, does not hold if the VRF keys were generated adversarially. For instance, if an adversary outputs VRF keys that are deterministically generated (or hard-coded and publicly known), then the outputs are easily derived by anyone.”

So VRF completely passes the buck on entropy to whatever was the keygen system. I’m not sure a VDF really deals with the heart of the entropy problem though, as most VDFs pass the buck themselves on entropy (and thus the whole “cryptographic” definition of a hash) onto the PRNG 2:

“By itself, σ-sequentiality does not imply Ω(λ) min-entropy. Stronger min-entropy preservation can be demonstrated in other ways given additional properties of the VDF, e.g. if it is a permutation or collision-resistant. Under suitable complexity theoretic assumptions (namely the existence of subexponential 2o(n)
circuit lower bounds) a combination of 1A randomness extractor can then be applied to the output to map it to a uniform distribution. Nisan-Wigderson type PRGs and extractors can also be used to generate poly(λ) pseudorandom bits from a string with min-entropy log λ.”

So again we come to the same problem: the root source of entropy isn’t necessarily entropic. And that’s a real problem because there is the possibility of someone potentially exploiting that - and this existing scheme - to employ some kind of side channel attack.

As an alternative, why not just do this: enforce random number generation using a popularly verified library implementing one of the NIST SP800-90A certified DBRGs 3.

Worst case there is you get into a quibble about whether something like /dev/urandom is sufficiently entropic - which is something we all have to deal with and typically handwave unless you’re making nuclear codes. You can still employ whatever cryptographic routing mechanisms you want to muddle the waters on some kind of collusive pre-image attack. But having a sufficiently entropic RNG will also help guard against birthday attacks and collision attacks.

Also you minimize the possibility of a side channel attack being exploited here. That’s important because in addition to the obvious technical complexity of implementing the above, there’s this:

“Although neither formal definitions nor proofs of (cryptographic randomness) have appeared in cryptographic literature, the VRF schemes presented in this specification are believed to satisfy this property if the public key was generated in a trustworthy manner. Additionally, the ECVRF also satisifies this property even if the public key was not generated in a trustworthy manner, as long as the public key satisfies the key validation procedure in Section 5.6.”

That is low key terrifying and reminds of IOTA’s original issues with cryptographic security around a not too dissimilar topic.

[rongjian]

Hi, Andy:

Thanks for all the feedback. I see your concern about VRF being potentially exploited by malicious key generation. But our design actually prevented that because the participants’ VRF key are predetermined and can not be changed. Sorry for the confusion as the details about how the participants and their private key are determined were not posted in this thread.

In short, the participants and their private key are fixed when they are generating the VRF randomness for the DRG. Participants who are eligible to join the DRG were registered in the ledger beforehand, and they can not change their private key during the DRG. So the only thing a malicious party can do is to withhold his input, which is not effective.

Regarding the NIST SP800-90A certified DBRGs, I haven’t looked into it. Is the randomness publicly verified on the generator’s identity?

[nickw]

Hey Andy,

Really glad to have someone with your expertise adding to the conversation. I hope RJ’s response above adds some clarity to our approach.

Let me add my two cents:
Our approach is similar to the “Unicorn” protocol mentioned in “Verifiable delay functions” section 2, described below [1]. The hash of the last block is used as an init message from which to generate a VRF. We gather enough VRF inputs to guarantee that there is at least 1 honest party who contributes. This VRF is committed to the next block and serves as a preimage for a VDF which we compute to gather the final random number. Because the time required to compute the VDF is longer than the time between blocks, the leader cannot know how to manipulate the preimage to his advantage.

In the paper that proposes Unicorn, they address the problem of a lack of entropy in the sample collected from the group by concatenating it with another high entropy input [2]. I’m not sure this is necessary in our case but it could be something to consider.

Otherwise, I would think that the private keys used to generate the VRF inputs would have high entropy since they would be staking wallets holding quite a bit of tokens. They would be incentivized to use a high entropy private key to keep their funds safe.