Verifiable lag functions on Bitcoin
This post was first published on Medium.
A verifiable delay function (VDF) is a function that takes a significant amount of time sequentially calculation to evaluate, but can be quickly verified. We implemented it on Bitcoin for the first time. VDF, as a cryptographic primitive, can be used to build a plethora of new applications, such as public random beacons, computational timestamps, and proofs of data replication.
VDF
Motivations
Random beacon on chain
Achieving randomness is difficult in a blockchain because everything is deterministic and public. A classic example is a smart betting contract between two parties, where one party wins if the next block’s hash is even, and the other wins if it is odd. A miner can cheat this contract by playing it and at the same time ignoring each new block causing him to lose the bet.
A VDF solves this problem by requiring the randomness to come not from the block itself, but from a VDF of it. Tuning the VDF to take a long time to compute, say an hour, discourages a miner from cheating by forfeiting mining rewards in found blocks of the next hour, as it is greater than the bet amount.
Lottery
In a similar example, Alice, Bob, and Charlie want to play a lottery round, where they must generate a random number together to determine the winner. In a naive approach, each of them publishes a random number. Once all participants have done this, they compute a hash of the sum of the published numbers.
The problem is that the last person to submit their number can determine the outcome. For example, if Alice and Bob have already submitted their values, Charlie can just try to calculate the result using different numbers until he finds a number that gives the desired result.
To solve this problem, we introduce a delay using VDF. Let’s say participants have to hand in their numbers between 12:00 and 12:10. After all numbers have been submitted (or the deadline has passed), they are hashed again and a VDF is evaluated against the resulting hash that takes longer than 10 minutes, say an hour. Now Charlie couldn’t cheat as the result evaluation time is longer than the submission window.
Formal definitions
A valid VDF F must have the following properties:
- Consecutive: everyone can count f(x) in successive steps. Note that it is imperative that the computation cannot be parallelized. This ensures that an attacker cannot significantly speed up computation by using more resources alone. Computation time is limited only by the speed of a single execution thread.
- Efficiently verifiable: given the output jany observer can verify that y = f(x) in a short time, specifically log