As a core component of blockchain, consensus algorithm faces an important tradeoff problem, namely the tradeoff between the number of consensus nodes and consensus performance. Although the larger the number of consensus nodes means a higher degree of decentralization, at the same time, the performance of consensus will be reduced. There are many blockchain projects that use Verifiable Random functions (VRF) to solve this problem. PlatONE, an alliance platform built by Universal Blockchain and its partners, uses VRF to improve consensus performance.

In PlatONE, the consensus algorithm is IBFT consensus. As the number of consensus nodes increases, the number of consensus messages also increases, leading to the decrease of TPS of blockchain. In order to achieve a good compromise between the number of consensus nodes and consensus performance, PlatONE adopts the mechanism of randomly selecting consensus node set, that is, a certain number of nodes are randomly selected from a large number of candidate consensus nodes to become specific nodes participating in consensus in a certain cycle. This allows for a good degree of decentralization and security while providing good consensus performance.

This article will use PlatONE as an example to illustrate how VRF can be combined with blockchain consensus.

1. Introduction to verifiable random Functions (VRF)

VRF was first proposed by Micali, Rabin and Vadhan. It is a pseudo-random function and provides a publicly verifiable proof of its output. The algorithm has the following characteristics:

• Pseudo-randomness: The output value is random

• Verifiability: The output can be verified (essentially a zero-knowledge proof)

• Uniqueness: The output random value is unique

Given an input valueXHas a private keyskPeople can calculate a function valueAnd to prove that. Use proof PI and public keyEveryone can verify thatWhether it is calculated using this algorithm and does not reveal anything about the private keyskThe information. At present, the construction scheme of VRF is based on the stochastic prediction model, which mainly falls into two categories: one of which adopts RSA to construct VRF, namely RSA VRF. The other uses elliptic curve cryptography to construct VRF, or EC VRF. The VRF solution described in this article uses THE EC VRF.

2. Consensus and VRF algorithm interaction design

2.1. Interaction diagrams

VRF mechanism involves the following two algorithms:

  • VRF

Generate a random number and proof for the block after the block generating node packs the block, and store it in the block. When other nodes receive the block, verify whether the proof and random number are correct.

  • The binomial distribution

In the election of consensus nodes, the binomial distribution is used to calculate the probability of each candidate node according to the weight of each consensus candidate node. In this way, the election is conducted according to the probability of each node. The higher the probability, the higher the probability of being selected. In order to increase the randomness of the election, random numbers generated by VRF are used to calculate the probability.

According to the color of the numbers in the figure above, two interactive processes can be divided to trigger the above two algorithms:

** Red numbers: ** belongs to the block node trigger, including the following process (represented by numbers in the figure)

  • **2: ** After the Worker completes the block generation, VRF is called to generate proofs and random numbers and store them in the block
  • **4: VrfPlugin is invoked after the transaction is executed by the Worker. If consensus nodes need to be elected, the binomial distribution algorithm is called

** Blue numbers: ** belong to non-block-producing node trigger (numbers in the figure)

  • **1: ** When a consensus node receives a block in Consensus Engine, verify whether the VRF output value of the block is correct
  • **3: ** After a block is synchronized by a non-consensus node, verify that the VRF output value of the block is correct
  • **5: ** After a block is synchronized by a non-consensus node, VrfPlugin is called. If consensus nodes need to be elected, the binomial distribution algorithm is called

2.2. The class diagram

The election of consensus nodes is performed by a combination of VRF and binomial distribution. The two algorithms are independently triggered and executed, but the probability calculation of binomial distribution depends on the randomness generated by VRF, and the probability of weight can be realized through randomness, which is explained as follows:

  • After the block is generated, VRF proof and random number are generated for the block and stored in the block. The random number is used as the election consensus node, and the proof is used to prove that the random number is generated by the block generating node based on the random number of the previous block
  • In the election of consensus nodes, it is necessary to use the random numbers of the first N blocks to be assigned to N nodes for xOR calculation with the random numbers of the current block, and the calculated values are used as the input values of the binomial distribution to calculate the probability
  • Each node is assigned different random numbers, so the input value of the binomial distribution of each node is different after calculation, and the points on the cumulative distribution curve of the binomial distribution obtained are different, thus generating probability

2.3. The storage

1. The original field Nonce in Header, whose type is []byte, is used as the proof of VRF storage. (For details about the proof fields, see interface description.)

2. As the election consensus node requires random numbers of N blocks (that is, the number of candidate nodes), these random numbers need to be stored in an appropriate way for easy reading.

Since N represents the number of nodes to be elected and is an indefinite number, it is possible to cache random numbers of the first several predetermined blocks. The preset number is temporarily set to 100 and can be set as required by the corresponding flag (tentative –nonceCache) on the node startup command line.

2.4. Specific business logic of the algorithm

Against 2.4.1. Type VRF (variable refrigerant flowrate) related

  1. Generate prove: Indicates the output block nodeworkerthecommitNewWorkCall before executing a transaction inVRFtheProveFunction generates proofs and random numbers for the block and stores them inHeaderIn theNoncefield
  2. The consensus node receives blocks: called by the consensus node after receiving the proposal blockVRFtheVerifyFunction checks whether the block’s proof is correct
  3. Non-consensus nodes synchronize blocks: Non-consensus nodes include consensus candidate nodes and observer nodes before the election in this cycle. Synchronization is divided into two parts, respectivelydownloaderandfetcherModules, which are eventually called after synchronizing blocksblockChaintheInsertChainFunction to process blocks inInsertChainCall from a functionVRFtheVerifyFunction checks whether the block’s proof is correct

2.4.2. Binomial distribution correlation

  1. A piece of the node: When triggered by the election process,workerTo call VrfPlugin after executing the transactionElectionFunction, which callsbinomial_distributionElection consensus node
  2. Non-generating block node: When triggered by the election process,blockChainTo call VrfPlugin after executing the transactionElectionFunction, which callsbinomial_distributionCompute the consensus node.
  3. Election trigger condition: In the parameter management contract, when the VRF election flag is triggered, the EVENT notification of the Config module is sent to the VRF module to trigger the election process of VRF consensus nodes.

2.4.3 binomial_distribution Election process

  1. Gets a list of consensus candidate nodes for election
  2. Gets a random number for the current block (fromBlockIn the callNonceFunction returns the proof and calls againVRFtheProofToHashFunction returns a random number.
  3. The random numbers of the first N blocks are obtained according to the random numbers stored in the cache. If the number of random numbers in the cache is less than N, the random numbers of the remaining blocks are read from the chain
  4. Calculate the probability of a single weight being selected, p=(total weight of the list to be elected/number of the list to be elected)* Number of voters/total weight of the list to be elected
  5. Each consensus candidate node is calledNewBinomialDistributionFunction and pass the respective n(weight) and p(probability) of the previous step into the function to instantiate an object
  6. Assign a random number to each candidate node, and do xor with the random number of the current block. Then divide the value by (2 ^ 256-1) to get the probability value between 0 and 1targetP
  7. Each candidate callsInverseCumulativeProbabilityFunction and take the probability value obtained in the previous steptargetPPassed in as an argument to the function, which yieldstargetPOf the cumulative distribution curvexvalue
  8. Finally, the x value calculated by each verifier is sorted in reverse order, and the first V verifiers are taken as the consensus nodes of the next cycle. Where V is the number of consensus nodes. The value of V is obtained from the Config module, that is, from the parameter management contract every time the VRF election is triggered, and passed by the Config module as a parameter in the event notification.

The following figure shows the xor rule for random numbers in the first N blocks :(example of N is 101)

Random numbers of the first N=101 blocks are assigned to each consensus candidate node according to the ranking of consensus candidate nodes (default is the order of nodes in the array). For example, the random number from the first block is assigned to the last candidate node, the random number from the second block is assigned to the last candidate node, and so on, and each candidate node also has the random number of the current block.

2.5. About node types

Corresponding to VRF design, node types in node management contract are as follows:

  • Observer node

Does not participate in the election of consensus nodes and only synchronizes blocks

  • Consensus candidate node

Participate in the election of consensus nodes; If it is not selected as a consensus node in this consensus cycle, block synchronization is also performed

  • Common node

In this consensus cycle, the candidate nodes are elected as consensus nodes to participate in the operation of consensus. In the next consensus cycle, all types of consensus nodes and consensus candidate nodes will participate in the election process of VRF consensus nodes. That is, only nodes of the observer node type do not participate in the election of consensus nodes.

2.6. About node attributes

The attributes of a node, in addition to the existing ones, include:

  • Weight of nodes (currently, the default weight of nodes is the same)

2.7. Algorithmic interface

2.7.1. Vrf_secp 256 k1

Using THE VRF algorithm of SECP256K1 curve

ECVRF_prove function

This function is used to generate random numbers and proofs based on input data. The random numbers and proofs are concatenated in the same byte array. The first 1 to 33 bits are random numbers

The arguments:

Reference:

ECVRF_verify function:

This function is used to verify random numbers and prove whether they are generated by the public key and based on the original data

The arguments:

Reference:

ECVRF_proof2hash function

This function is used to parse out random numbers from proofs

The arguments:

Reference:

2.7.2. Type VRF (variable refrigerant flowrate)

This class is the encapsulation of the concrete implementation algorithm. It does not expose the concrete curve, but only provides the general interface and parameters. Then it calls the concrete implementation algorithm class to construct the required parameters and pass them

Prove function

Generate proofs and random numbers

The arguments:

Reference:

Verify the function:

Verify that proofs and random numbers are correct

The arguments:

Reference:

ProofToHash function

Parse out random numbers by proof

The arguments:

Reference:

2.7.3. binomial_distribution

Implementation of binomial distribution algorithm

NewBinomialDistribution function

Instantiate a binomial distribution object used to compute a probability curve, consisting of two parameters: frequency and probability

The arguments:

Reference:

CumulativeProbability function

The cumulative distribution function computes the probability values of the range up to a point (time) on the curve

The arguments:

Reference:

InverseCumulativeProbability function

The cumulative distribution function, which uses the probability value to calculate the value x of the point where the probability belongs

The arguments:

Reference: