Huang Qi
Co-Founder & CTO of Tarax Network
Senior full-stack engineer with a master's degree in computer science. His main research directions are distributed systems and P2P self-organizing networks.
image description
He has successively engaged in technical research on distributed data sharing in the Intelligent Science Group of the Institute of Computing Technology, Chinese Academy of Sciences, Sony China Research Institute, Baidu, and Toutiao.
The sharing I bring to you today is called "Application and Principle Analysis of VRF in Blockchain", which originated from a public chain called Tarax Network that our team is working on. For the sake of scene positioning, we want to find a way to achieve consensus with low power consumption. Then POW must not be considered, and it is easy to think of POS. Then consider that whether it is POW or POS, they want to randomly find a node that cannot be predicted to package the block, and make this block recognized by the entire network.
Then in the matter of random selection, VRF is the most direct way to draw lots based on verifiable random selection.
Of course, POW does not only have the function of randomly selecting points for packaging, but also has some considerations of game and human nature. In the current POS scheme, it is not OK after randomly selecting points. Instead of the random point selection scheme, naturally It will also redesign the game and human nature issues from other aspects.
But let's solve the problems one by one first, leaving aside the content of the game, let's study VRF first.
We look at this with two questions:
1. What is a verifiable random function?
2. How do some current chain schemes use verifiable random functions?
What is a Verifiable Random FunctionA verifiable random function can be viewed as arandom oracle
, which means that I can get a random number output through any input:
1. For different Inputs, the Output values are random and evenly distributed within the value range.
2. For the same Input, the Output it gets must be the same.
However, the verifiable random function has one more non-interactive zero-knowledge proof than the random oracle, which can be used to verify the correctness of the random number output, indicating that the random number was indeed generated by someone.
Verifiable Random Functions It contains four functions.
1. Generate a key and generate a public key-private key pair, which will not be discussed in detail later
2. Generate random number output
3. Computational zero-knowledge proof
4. Verify random number output
The process of generating a random number and its proof is performed locally, and the input is a private key and a value. The output is the random number and its zero-knowledge proof.
So through these four functions and their outputs, how do we randomly select points?
text
Verifiable Random Function Draw
The simplest method, after we generate the random number value through VRF above, we can set a threshold recognized by the entire network to determine whether it is selected. For example, we all agree that a value of 100 is the threshold. Suppose I randomly get 101 in a certain round Then, I was allowed to proceed to the next step.
However, this simplest solution has no way to prevent Sybil attacks. Therefore, most of the current VRF lottery schemes will allocate votes based on rights and interests, and then design the lottery algorithm.
Let's take a look at the most common solution now, which is to calculate the result of the lottery through the binomial distribution.First of all, we have generated a value through the private key. This value can actually be regarded as a large positive integer. Assuming it is 256bit, its value range should be between 0 and 2 to the 256th power. corresponding to it
Divide by 2 to the power of 256 to get a value between 0 and 1.
Put this value into the cumulative distribution of the binomial distribution for comparison, and you can get the corresponding value (see PPT for details).
If this value is greater than zero, it is equivalent to drawing a lottery that can proceed to the next step.
Broadcast this value together with the sum generated by the previous VRF to others, and any other received user can verify whether the following two conditions are true:
1. Whether the verification is correct
1. Is it necessary to use VRF for lottery?
How does it compare to random oracles?
2. Are there other application scenarios?
thank you all.
Verifiable Random Functions [1999]
Ouroboros: A provably secure proof-of-stake blockchain protocol [2017] Algorand:
Scaling Byzantine Agreements for Cryptocurrencies [2017]
Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain [2018]
https://github.com/iost-official/Documents/blob/master/ Technical_White_Paper/EN/Tech_white_paper_EN.md
https://tools.ietf.org/html/draft-irtf-cfrg-vrf-02
https://github.com/Realiserad/fts-tree
https://www.cs.bu.edu/~goldbe/projects/vrf
2. Use the binomial distribution function to get whether j' is equal to j
Assuming that both conditions are true, it proves that the lottery result is correct and credible.
So far, the process from lottery generation to verification is complete.
Through the description of the above process, it is not difficult to see that the VRF-based lottery mechanism has several advantages:
1. First of all, its lottery process does not need to communicate with others, and the lottery result can be obtained directly on the machine, and the x input is recognized by everyone, and the output value for the same x is fixed, so it cannot be passed multiple times try to change the lottery result
2. After a node receives the lottery information from other nodes, it can use the attached certificate to prove the correctness of the random number to ensure that it is indeed calculated by the owner of the private key. Therefore, the lottery result cannot be forged.
3. VRF is mainly used to obtain a pseudo-random number. The lottery part is mainly responsible for a binomial distribution function. By constructing the parameters of the binomial distribution, we can easily control the winning rights that need to be obtained. The number is adapted to different scenarios that require lottery.
After talking about the lottery algorithm based on VRF, let's take a look at what this lottery algorithm brings to the blockchain consensus.
Changes brought by VRF lottery to consensus
Let's start with a specific example.
Ouroboros is Cardano's consensus algorithm. It is very interesting. At the beginning, it proposed a consensus process scheme, but this scheme is provably safe, and does not involve the implementation of every part. Then it will gradually add implementation details in the update of the paper version and in the specific implementation plan.
So far, his theoretical version has iterated three versions, namely Ouroboros, Praos and Genesis. In the second version of Praos, the part of VRF is introduced as the extraction of block proposal nodes.
First, let’s briefly talk about the consensus process of Ouroboros:
Before the start of each epoch, in the last round of epoch, a random seed and a number of Stake Holders will be determined as the participating nodes of this round of epoch. According to the random seed, the slot leader of all slots in this round will be obtained , and they are packaged sequentially.
In the previous round, Random Seed submissions were generated by an interactive PVSS scheme. To give a simple example to illustrate, it is similar to two people who cannot guess punches through real-time communication. If one person receives the punch result of the other, he can issue a sure-win punch to win, so that It's not fair, so now, we first use a card to replace our punch, and then cover it, everyone doesn't know what the punch is, but we can guarantee that everyone has chosen the punch up. The results will be announced later.
After the Random Seed is generated, the Follow the Satoshi algorithm is used to obtain the slot leader of each slot. Follow the Satoshi can be regarded as a random oracle machine, which can use the Random Seed and the equity value of each StakeHolder to give each The slot randomly assigns a stake holder as the slot leader, and this result is known to each node before the start of this epoch, and they can calculate it by themselves.Then there will be a problem:
I can know the packaging node of a certain block in advance, so the attacker can attack the packaging node in advance to achieve its purpose of attack.
Later, in Praos, that is, the second version of Ouroboros, it introduced VRF to replace the Follow the Satoshi scheme. After we have just learned about the process and characteristics of VRF lottery, we can know that after the introduction of VRF, every The slot leader of a round of slots is only known to the node itself. After he publishes, other nodes can verify whether he really has this role, so that the above-mentioned attacks can be avoided.
But this also brings new problems. As mentioned above, Follow the Satoshi can randomly assign a slot leader to each slot, but VRF, a probability-based lottery method, cannot be sure about this point. It may also happen that a certain round of slots does not draw a slot leader or draws out multiple slot leaders. Therefore, in Praos, an additional solution has been added to deal with this situation.
Comparing the two solutions, VRF introduces two abnormal situations in addition to the unpredictable security upgrade of the slot leader. But are these two anomalies new problems introduced by VRF? Let's think about it.
In fact, whether it is the Follow the Satoshi or VRF solution, this problem must be solved, because even if I can guarantee that each slot has a slot leader, I cannot guarantee whether the slot leader can print packets in this slot. The solution to verify the fork is a problem that must be considered as long as it is a chain. Suppose a slot leader is attacked, and a large number of repeated packaging in its own slot will also cause fork problems.
Therefore, in the absence of new problems, increasing the anonymity of packaging nodes is actually a security upgrade for the system.
Then let's take a look at some other consensus algorithms that use or heavily rely on VRF.
The idea is generally to use a verifiable random function to draw lots to reduce the number of participating consensus nodes or certain roles.
1. Algorand selects the packer first, and after the packer is selected, the committee is selected, and the committee uses BA* to select blocks.
2. In Dfinity, the threshold is increased by deposit, and the number of participating nodes is reduced, and then the packager is selected. After the packager is selected, the notary is selected, and the block weights are sorted to select the block.
text
text
Some Problems
After sharing VRF and some of its current applications, there are several questions that we need to think about together:
How does it compare to an asymmetric encryption scheme whose process is similar?
thank you all.
image description
https://github.com/pinqy520/vrf.js
Currently used in the implementation of the Tarax consensus algorithm
references—————————————————————————————————————————————————————
image description
https://v.qq.com/x/page/e0735yg5l7t.html
Blockchain Funds-Technology Federation
BFTF co-organizers:
image description
