VDFs are not Proof of Work
Verifiable Delay Functions (VDFs) are popping up in a lot of blockchain research as of late (Ethereum, Chia, etc). They are proving to be very useful tools in cryptoeconomic mechanism design. A recent paper digs into a host of VDF applications while fleshing out the properties and theory behind them. These functions aim to provide a minimum amount of time delay on players either knowing some piece of information or participating in the protocol in some way. VDFs do this by requiring significant computation to calculate but relatively little computation to verify.
This asymmetrical relationship between calculation and verification looks a little bit like Proof of Work (PoW) at first glance. This is actually what I tend to hear from researchers when they first learn about VDFs being potentially used in Proof of Stake (PoS) systems. Something of the tune — “sounds like we are just reverting back to Proof of Work” or “can we not do this without burning CPU cycles again”. Although VDFs and traditional PoW algorithms share the relationship of “hard to compute” while being “easy to verify”, the core difference is that blockchain PoW consensus algorithms are proof of parallelizable work and are probabilistic in success, not functions. VDFs, on the other hand, are proof of sequential work and are deterministic functions.
Parallelizable vs Sequential Work
VDFs by design are non-parallelizable. To make a VDF hard or take longer to compute, we just increase the amount of cycles that must be calculated. Each cycle depends on the previous cycle’s output for its input, so to begin cycle N, we must already have the output of cycle N-1. A player can gain little to no speed up in computation time by adding additional processors.
This is in stark contrast to blockchain PoW algorithms that are purposefully designed to be parallelizable. The more processors a player has working on a PoW algorithm, the faster (probabilistically) they will find a solution. This incentivizes players to increase the amount of hardware they have dedicated to searching for a solution. On the other hand, if a player wants to find the solution to a VDF, there is no advantage in having additional hardware to the attack the problem in parallel. The only way to gain an advantage is by buying or designing faster hardware.
Function vs Probabilistic Game
VDFs are functions, as stated in its name. For a given input, there is only one verifiably correct output. To find this output, a player simply executes the VDF the prescribed number of cycles. All players that play the game will eventually calculate the same solution, and only one solution will verify as correct for a given VDF input.
With PoW algorithms, there are many solutions that would verify as a correct output for a given input. To find one of these outputs, the player executes a small function on a guessed input and checks that the output satisfies the verifier. The player can run any number of these small functions on any amount of hardware with different guesses in parallel with the hope that one hits an output that satisfies the verifier. Depending on the incentives driving actors to play this game, a player might feel inclined to dedicate more and more hardware to the problem to gain an edge on other actors — thus the PoW arms race that is consuming an ever increasing and insane amount of computational power and energy.
A Purposeful Monopoly
Probabilistic and parallelizable are the two properties that create the PoW arms race. Not only can someone parallelize the solver, but the player with the most parallelized computational power still only wins probabilistically proportional to the amount of computational power they control. This leads to players being incentivized to the play the game at whatever capacity they have. For the purposes of PoW, this creates a somewhat equitable game. This equitability draws players both small and large.
Because VDFs are not probabilistic, they do not have this equitable property. Depending on the game in which they are deployed, VDFs actually end up with the opposite property and tend towards being monopolistic. The player with the fastest piece of hardware will almost always be able to calculate the VDF first (unless the player goes offline, is censored, or another player manages to buy/build a better piece of hardware). If the first player to solve a VDF reveals the solution for public verification (likely to claim a reward), then all but the fastest players simply will not play the game. Even if a player’s hardware is 95% as fast as the fastest player, they will almost never win and should probably just never play. The monopolistic property prevents the computational arms race, but at the same time opens up a whole host of other attacks and design considerations. For example, what happens if the monopolist suddenly goes offline!
I’ll leave this and other considerations to ethresear.ch and future articles. In the meantime, I hope you’ve been convinced that using a VDF in a PoS system will not result in a protocol that burns as much energy as the entire country of Ireland 😜