Introduction to Decentralized Random Number Generation
A crash course on Proof-of-Stake (Part III)
Table of contents
- Prerequisites and Motivation
- A Proof-of-Concept for Proof-of-Stake
- Introduction to Decentralized Random Number Generation (this post)
- Verifiable Delay Functions and Verifiable Secret Sharing (coming soon)
- Nothing at Stake and Long Range Attacks (coming soon)
In the last part, I introduced a naive practical Proof-of-Stake scheme, that had serious flaws in term of security. One of drawbacks was bias-ability of our source of randomness, the hash of the last block; in each round, the selected miner was allowed and incentivized to bias the result of random number to increase probability of the event that he becomes selected as the miner of the next block again.
To address that issue, we dig into Decentralized Random Number Generation (DRNG) mechanisms. First, we see a framework to evaluate different DRNGs and then we review major types of DRNGs. Let’s start!
This part is going to be a bit technical, if you felt something is unclear or tough to understand, please let me know.
Decentralized Random Number Generation
A DRNG mechanism is a process in which a group of people collaboratively generate a random number while they do not rely on any third-parties. Let me introduce a simple DRNG before we proceed with details.
Naive Xor (Part I)
Assume we have deployed a smart-contract that executes our scheme. First of all, it lets anyone to register as a participant of the DRNG mechanism; assume N participants have registered so far. In each round, the mechanism executes following steps to generate the random number:
- Each participant must draw a random number locally. Let’s call the local random number of i-th participant as R_i.
- All participants must submit their local random numbers to the smart-contract.
- The output, our collaboratively generated random number, is computed as follows:
If a participant did not send his share, we simply ignore that share. Moreover, we can ask people to stake some coins in the smart-contract at the registration time so we can burn that stake if they happen to be unresponsive.
A careful reader may wonder, how we are going to use R as the determinator of next block miner while R requires a number of new blocks before it gets generated (Because we are generating R using a smart-contract). Well, we can generate R as large as we want and split it in chunks, say m chunks, then we can use those chunks to select miner of all following m blocks.
Desired characteristics of DRNG for Proof-of-Stake
So far we have learned about two different DRNG mechanisms, Last Block Hash and Naive Xor, but still we do not have a framework to compare DRNGs against each other. Here is a list of desired characteristics for a DRNG in Proof-of-Stake protocols from [1].
- Availability (Liveness): Successful completion despite participation of malicious nodes.
- Unpredictability: No one learn anything about the output before completion.
- Unbiased: Output distributed uniformly at random despite participation of malicious nodes.
- Verifiable: Output correctness can be checked by third parties. It means, there must exist an unforgeable witness (or attestation) that verify the output is the only valid output of the process.
- Scalable: Executable by many participants; low enough computation and communication complexity.
A good DRNG must satisfy above properties with high probability.
Last Block Hash
Now that we have appropriate measures, let’s weigh merits and demerits of last block hash mechanism.
- Available ✓
As long as the blockchain stay available, the last block hash mechanism stay available. - Unpredictability ✘
The last block miner is actually aware of the result before anyone else. - Unbiased ✘
The last block producer is able to test multiple valid blocks and only broadcast the one that is in her favor. - Verifiable ✘
There is no witness or attestation that proves the resulting block is the only block that was producible. (In fact, multiple blocks where possible.) - Scalable ✓: The DRNG is only limited as blockchain’s scalability. It requires no extra on-chain or off-chain messages.
Naive Xor (Part II)
Let’s analyze Naive Xor scheme. First, notice that everyone is able to watch transactions and get aware of R_i s before completion of process. Hence, the last participant that submits his share to the smart-contract can submit R_N in a way to make R equal to any arbitrary number he wants! This is called the last actor problem. So, the output of this scheme is not unbiased, unpredictable nor verifiable.
As long as at least one participant submit her share, the scheme keeps on producing new random numbers; in addition, unresponsive participants get punished. So it is fair to consider Naive Xor as an available scheme.
The number of required on-chain transactions per block is N/m, if we assume m a constant, we can not execute this scheme with huge number of participants. Thus, I consider Naive Xor as not salable.
Commit-Reveal Xor
The major short coming of Naive Xor is that the last participant is able to change his share adaptively before submitting it. It is a natural idea to limit participants in a way that they can not change their shares after seeing other participants’ shares. To implement this idea we add a step 0 to Naive Xor as follows:
0. Each participant must first submit hash of its random number. So, the i-th participant submit Hash(R_i).
Then we follow steps of Naive Xor. It is obviously required that R_i and Hash(R_i) conform otherwise the i-th participant gets punished.
This way the last actor is not able to adaptively change his share to make R equal to any arbitrary value. However, he can still decide between publishing or not publishing his share. Hence, he is able to bias the result to some extend.
To make this scheme verifiable we must terminate process each time even one person do not submit his share and repeat the whole process again. This way everyone can watch the blockchain and verify that resulting random number R is the only random number that was producible. (It causes some other problems but I won’t elaborate on it.)
Hash Onions Xor
Last two schemes, Naive Xor and Commit-Reveal Xor, were not scalable because they required large number of on-chain transactions as number of participants grows. The idea is to change Commit-Reveal step in a way that reduces number of required messages. In other words, the idea is to enable participants to commit to more than one value with each message.
Hash onion is a tool to commit a series of values using only one small message. For an arbitrary value x, we define C(x, i) as follows:
For example, C(x, 2) is hash of C(x, 1) and C(x, 1) is pre-image of C(x, 2). If one commits to C(x, 2), he commits to a series of values as: x, hash(x), hash(hash(x)).
Here is the Hash Onion Xor scheme: Each block must include a field named R and a field named pre-image. We set field R and field pre-image equal to arbitrary values in genesis block. Anyone can register as a prospective miner by staking some coins and submitting C(R_i, m) for a random value R_i. Note that m is a pre-defined constant in the protocol. In each round, the protocol select the next block miner from set of registered miners according to R. The selected miner must peel off one layer of his committed hash onion! To do so, the miner set the field pre-image equal to pre-image of last C(x, i) he has committed (by registering as a miner or by producing a block). Then he must set field R as follows:
(new block’s R) = (last block’s R) xor (new block’s pre-image)
For example, if V got selected as the miner of next block and if the pre-image of last block he has mined is equal to C(R_V, 5), he has to fill the pre-image field of new block with C(R_V, 4).
After a miner mines m+1 blocks, her hash onion gets completely peeled off and he has to register once again and commit a new hash onion. Note that, in this scheme we only communicate 2 extra messages per block. So, it is executable even with large number of participants.
Now we have availability, verifiability, and scalability. But our scheme, still lacks unpredictability and unbiassed-ness. The selected next miner can decide between peeling off his commit or not broadcasting a new block. So he is aware of the final result before everyone else and he can bias it in his favor.
What is next?
Is there any known DRNG mechanism that satisfy all those desired properties?! Fortunately yes! We will investigate Verifiable Delay Functions and Verifiable Secret Sharing as key tools that enable us to build such DRNG mechanisms. See you in next parts! :)
References
[1] https://eprint.iacr.org/2016/1067.pdf
