Randomized leader election using VRF

Author : Seonpyo Kim<spkim@kodebox.io>

Created: 2019-08-20

# 1. Introduction

Tendermint rotates through the validator set, i.e. block proposers, in a weighted round-robin fashion. Leaders can be subject to targeted denial-of-service attacks because attackers can predict exactly who will be the next proposer and direct all their bots to simultaneously attack that proposer.

Bitcoin is not susceptible to such attacks because it is impossible to predict the next block proposer before the block is propagated to the network. Only the node that solved the proof-of-work problem knows that it can propose a block and other nodes in the network can confirm that the proposed block is from a valid block proposer by verifying the nonce.

To mitigate the possible denial-service-attacks on Tendermint, we need to introduce randomness into its leader election mechanism. In this proposal, we sketch how to introduce a verifiable random function (VRF) to assign leaders to round numbers in a less predictable way.

# 2. Background

## 2.1. Verifiable random function (VRF)

In cryptography, a verifiable random function is a pseudo-random function that provides publicly verifiable proofs of its outputs’ correctness[2]. The operating principle of VRFs is as follows:

Figure1. VRF

VRFs guarantee collision resistance and pseudorandomness. Moreover, they give a unique output random hash for a given message, unlike DSAs(digital signature algorithm). Using VRFs, arbitrary values can be calculated privately by any user and can be verified publicly. Furthermore, users cannot brute force their way to get a more desirable random hash value because the output random hash is unique for the given message.

## 2.2. Algorand committee selection

Algorand’s cryptographic sortition aims to constitute a committee randomly, but the result of an election can be discovered privately[1]. Algorand implements cryptographic sortition as shown in the following figure:

Sortition requires a role parameter that allows distinction amongst different roles. In Algorand’s consensus, there exists the block proposer and the fork proposer. 𝜏 specifies the expected number of users selected for a certain rule. A calculated value j determines the number of elections of a user. Additionally, w refers to the weight of a user and W refers to the total weight of all users.

The sortition algorithm of Algorand is analogous to biased coin flipping with hitting probability p, namely “Bernoulli trial”. It treats each stake token as an independent coin. Thus, the total voting power is equal to the number of coins that hit success. The probability p is set by the expected number of committee over the number of candidates.

The number of hits is determined not by multiple independent trials but by one hash value calculated with the VRF function(sk, seed). To treat one VRF function result as an aggregated value of multiple independent trials, the VRF should guarantee that the output of the function is a uniform random value. More specifically, the region in which (output_hash) / 2^(hashlen) exists determines the voting power k, where the output_hash refers to the output of the VRF function and the hashlen refers to the length of VRF outputs.

Figure 2: The sketch of B(k; 2, ¼)

# 3. Design

## 3.1. Leader election

The leader election process follows Algorand’s sortition algorithm. Let’s assume each validator has equal weight. If one naively sets the expected committee number(𝜏) as 1, then p becomes 1/30. In this situation, the probability of how many block proposers are elected is as follows:

# proposer | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|

probability | 0.362 | 0.374 | 0.187 | 0.060 | 0.014 | 0.002 | 0.0003 | 0.00004 |

Though the expected number was set to 1, the chance of there being no proposers elected is as high as 36%. This is the most undesirable case since block finalization does not occur in that round. When 𝜏 is greater than 1, it is possible to secure at least one block proposer with high probability.

For 𝜏 = 6 when the total weight is 30, the chance of “no proposer” is reduced to 0.12%.

# proposer | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|

probability | 0.0012 | 0.0093 | 0.0337 | 0.0785 | 0.1325 | 0.1723 | 0.1795 | 0.1538 |

# proposer | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
---|---|---|---|---|---|---|---|---|

probability | 0.1106 | 0.0676 | 0.0355 | 0.0161 | 0.0064 | 0.0022 | 0.0007 |

If there are multiple proposers, they independently propose blocks and only the proposal with the highest priority is accepted. Proposal priority will be discussed in the next section.

Until now we have assumed that each node has equal weight, but it is improper because each has different voting powers. In this case, splitting stakes into multiple nodes and managing all of them are more advantageous than managing a single node that has a lot of stakes. To eliminate the chances of Sybil attacks, the weight of a node must be proportional to the amount of stake delegated to the node.

If the total weight is large enough, it is possible to recalculate the proper 𝜏 value by using the “Poisson distribution” approximation [A].

## 3.2. Proposal priority

One validator can be elected as a block proposer multiple times in one round with stake-proportional weight. However, even if elected multiple times, it is nonsensical to propose multiple blocks in a single round. Here’s where the priority comes into play.

The priority for a block proposal is the measure of the power of that proposal. Block proposals need to be prioritized, and proposals with more power end up gaining more priority. In a single Tendermint round, there should be only one valid proposal, which would be the proposal with the highest priority.

The priority for the block proposal is obtained by calculating Hash(VRF output_hash || sub-user index). To become higher in priority, a validator can try as many times as the number of elections. In this process, the validator iterates the sub-user index from zero to the number of election - 1. Other validators can verify the priority by using the published VRF output hash. The highest priority of all the block proposer’s selected sub-users is the priority of the height.

## 3.3. Gossip

Algorand gossips two different kinds of messages in the proposal step. One message only contains the priorities and proofs of the chosen block proposers, and the other message contains the entire block, the proposer’s sortition hash, and the proof. The purpose of this distinction is to quickly converge to the global highest priority proposer. These messages enable most users to learn who is the highest priority proposer, and thus quickly discard other proposed blocks.

We apply the same technique to Tendermint because fast convergence to the highest priority block will decrease the average block finalization time. Validators first propagate priorities and proofs through push gossip. Each validator discards priorities that have lower value than the proposal with the highest priority that it has seen. After a sufficient amount of time, most users will know who is the highest priority proposer. Then, these users can get the block proposal through a pull gossip to the highest priority proposer. This minimizes unnecessary message transfers in the network.

## 3.4. Verification

To introduce this sortition process to CodeChain, it needs two additional verification steps. One is a VRF output verification with a known public key of a certain validator. The other is proposal priority verification using the VRF output and the sub-user index validation (sub-user index < number of election).

For a single node, verifications take at least 5 times, when 𝜏 = 6. There is a trade-off between fast block finalization and correct block finalization. To vote in the global highest priority block, Tendermint module needs a looser timeout to wait and observe the actual highest priority block. However, this would make the ‘propose’ step take more time than before and force all nodes to wait full timeouts when there are no proposers. Therefore, the total confirmation latency would increase.

## 3.5. VRF seed

CodeChain blocks must contain the seed values. CodeChain’s leader election scheme needs the VRF seed to remain unpredictable until the current round. Hence, the seed should be dependent on parent_block_seed. Moreover, every Tendermint round requires a unique seed to determine block proposers, so the seed must be dependent on the Tendermint round value(i.e. height and view). Algorand’s idea is quite complicated because Algorand’s consensus algorithm “BA*” allows fork choices. However, Tendermint does not allow forks in its consensus, making the seed scheme simpler. The simplest form is:

current_block_seed = VRF_sk(parent_block_seed || height || view).

Attackers may want to control current_block_seed to have an advantage in the next sortition; however, one cannot be certain that they will have the highest priority in a round even though the hash value for the priority is large enough. Since nobody can predict other validators’ VRF results, priorities are also unpredictable. Malicious users may try their best to delay consensus until a certain “view” comes, which makes their VRF output in sortition bigger. However, controlling the “view” is more difficult than controlling current_block_seed because it requires a more complete control over the consensus process. The “view” value can get higher only when more than 2⁄3 of the validators in the committee fail to agree on a single block. Therefore, VRF_sk(parent_block_seed || height || view) is reasonable as a seed value of each round.

# 4. Safety and Liveness Analysis

Occasionally, there will be no block proposers elected in the sortition. Fortunately, it does not harm the liveness property of the Tendermint consensus since “no proposer” leads all honest nodes to wait until timeout and proceed to the next round. Malicious users could not pretend to be elected proposers because they can’t manipulate the VRF result, ultimately leading their proposal priority verification to fail.

References

Appendix

[A] Poisson distribution approximation. The probability of U coin hits out of total K coins, where the expected number of hits is set to 𝜏, is

and it’s equal to

For relatively very large U , and fixed K

And

So the probability of sampling exactly K sub-users is :

which is poisson distribution.