Nakamoto Consensus with VDF and VRF

Hey guys, had some thoughts on combining the Nakamoto consensus with verifiable delay function (VDF) and verifiable random function (VRF).

The idea is to use VDF to simulate the PoW puzzle solving, and VRF to create puzzle difficulty variations for different validator nodes. Combining the VDF puzzle with the Nakamoto longest chain rule, validator nodes are effectively chosen at random as the block proposer for each block height. Compared to BFT based consensus which usually poses an upper limit on the number of validator nodes, this approach can achieve a high level of decentralization like Bitcoin, and yet does not burn nearly as much electricity for potentially the same level of security.

Here are the details. For block height i, the validator nodes compete to solve the following VDF puzzle. Whichever validator first solves the puzzle can extend the chain.

(r_i, \pi_i^r) \leftarrow VRF_{sk}(seed=d_{i-1} || r_{i-1})

(d_i, \pi_i^d) \leftarrow VDF(x=r_i, T=r_i / S)

Here sk is the secret key of the validator, and S is the stake (i.e., number of coins) of the validator. r_i and \pi_i^r are the random number and its corresponding proof generated by the VRF. Similarly, d_i and \pi_i^d are the output for the VDF function and its proof. These four strings, along with the public key of the block proposer, needs to be included in the block header for other validators to verify the correctness of the proposed block.

In the first formula, the VRF function uses the concatenation of d_{i-1} and r_{i-1} as the seed, where both of the two random numbers can be retrieved from the header of the parent block at height i - 1. The VRF returns r_i, which is used in the second formula to modulate the difficulty of the VDF puzzle. Thus, each validator node has to solve a puzzle with different difficulty (and hence takes different amount of time).

The second formula uses Pietrzak’s iterative squaring VDF construct, which takes two input parameters, x and the number of iterations T. We simply set x to r_i, and T to r_i/S. Note that T, and therefore the difficulty of the VDF puzzle is inversely proportional to the validator’s stake S. This can effectively prevent the sybil attack. A user can attempt to create multiple accounts, each with a fraction of his total stake, and solve the corresponding VDF puzzles in parallel. However, it can be proven using the expectation of the minimum of uniform random variables that by doing this, the expected amount of time to solve the VDF puzzle only increases. Thus, the best strategy is to put all the stake in a single account.

We also note that in the first formula, the concatenation d_{i-1} || r_{i-1} is used as the seed for the VRF. This is to prevent malicious users from quickly evaluating the difficulty for each branch if he wants to fork the chain.

Update:

Actually we can make the VDF puzzle even more similar to the PoW hashing puzzle. Still based on Pietrzak’s scheme, the VDF puzzle asks for integer T, such that

K(H(r_i)^{2^T}) < M

Here K() is a one-way hash function. Once T is found, the validator node also outputs d_i = H(r_i)^{2^T} , and the corresponding proof \pi_i^d. With the proof, other validators can very quickly verify that (1) d_i is indeed equal to H(r_i)^{2^T} , and (2) K(d_i )< M.

Such a VDF puzzle has the advantage that the validators don’t know how long it takes to obtain the solution until the solution is found. This is similar to the PoW hashing puzzle.

However, we note that this VDF puzzle is inherently sequential, so unlike the PoW hashing puzzle, throwing more hardware cannot shorten the solving time.

Also note that the random number r_i for different validator nodes are not the same. Hence, each validator is solving a different puzzle. And here is where the randomness/lottery comes from.

Thoughts? Any loophole in the proposal? Any feedback is appreciated!

1 Like

Actually we can make the VDF puzzle even more similar to the PoW hashing puzzle. Still based on Pietrzak’s scheme, the VDF puzzle asks for integer T, such that

H(r_i)^{2^T} < M

Once T is found, the validator node also outputs d_i = H(r_i)^{2^T} , and the corresponding proof \pi_i^d. With the proof, other validators can very quickly verify that (1) d_i is indeed equal to H(r_i)^{2^T} , and (2) d_i < M.

Such a VDF puzzle has the advantage that the validators don’t know how long it takes to obtain the solution until the solution is found. This is similar to the PoW hashing puzzle.

However, we note that this VDF puzzle is inherently sequential, so unlike the PoW hashing puzzle, throwing more hardware cannot shorten the solving time.

Also note that the random number r_i for different validator nodes are not the same. Hence, each validator is solving a different puzzle.

This post was flagged by the community and is temporarily hidden.

will the speed of generating a block too slow?

if everybody has the same VDF device, would this make those with more stakes deterministicly win over those with less?

Would this encourage mining pools?

I guess we can tweak the difficulty of the VDF puzzle to control the block interval

Yes good point! The expected return can be higher if people form staking pools. For example, other things being equal, a validator with 2s stake is more likely to solve the VDF puzzle than two validators each having s stake within the same amount of time (since 2p > 1 - (1-p)^2). Hence it is more profitable to pool the stake together with the design described in the original post.

To address this I think we can place a cap on the max stake per validator node to make it more fair to all participants.

um, it will end up with all people with the “max stake”, so why not fix the staking amount? :smiley:

Hey,

Can you explain what’s exactly the purpose of the VDF in your scheme?
Why not just use a VRF (kind of like Algorand proposes)?

Yes possibly :slight_smile: That also simplifies the design. In practice though, it might be beneficial to have a cap instead so people without sufficient amount of tokens can also stake and participate in the consensus process.

Good question. So my understanding is that Algorand uses VRF to select a subset of validators as the candidates for the next block proposer. However, since multiple validators might be selected by the VRF, Algorand needs to run a Byzantine Agreement protocol to determine the block proposer (only one validator can be elected). Instead, the VDF puzzle (seeded by VRF) in our proposal creates runtime randomness to “select” the next block proposer in a way similar to Bitcoin PoW.

One challenge though, is that different implementations could have vastly different speed solving the same VDF. For example, an ASIC solver could be 20 times faster than a software solver running on CPUs.

To address this at the protocol level, one idea is to increase the puzzle difficulty for the current block’s proposer for the next N blocks. This reduces the chance this validator is selected again as the block proposer in the near future, effectively reducing his speed advantage.

For example, suppose we have N validators, and a few of them is m times faster than others in solving VDF (in practice there is like a bound on m , e.g. m < 20). We can impose a rule that for the current block proposer, the puzzle difficulty is increased by 2^m times for the next N/2 blocks on the same chain:

K(H(r)^{2^T}) < M/2^m

This kind of rules can be enforced since in PoS chains, typically a validator needs to lock its stake for a long time. As the difficulty is increased tremendously, with high probability, any node can be elected as the proposer at most twice within N consecutive blocks. On the other hand, the expected number of times a slow node can be elected as the proposer is roughly 1. Hence this could reduce the advantage of the faster node from m down to 2.