Verifiable A verifiable delay functions function (VDFsVDF) are is a new cryptographic primitive that is capable of introducing computational delays and creating cryptographic randomness. They were first described yielding cryptographically verifiable time delays through sequential computation. One of the use cases of VDFs is public unbiasable randomness without a trusted third party. VDFs were first defined in a June 2018 paper by Stanford professor of cryptography , Dan Boneh and others. Verifiable delay functions are a function which requires functions which require lots of sequential computation to evaluate, but once a solution is found is very easy to verify. The first construction of a problem similar to VDFs is a ‘timelock puzzle’ from Rivest, Shamier and Wagner. Timelock puzzles introduced the concept of encrypting data ‘into the future’ by requiring a specified amount of computation before a piece of specified data could be decrypted. However, unlike VDFs, timelock puzzles could not be efficiently verified.A few weeks after their introduction, two constructions of VDFs were created by academics and for which the function output can be quickly verified via a short proof. An older ‘timelock puzzle’ construction similarly uses sequential computation to create a time delay. Timelock puzzles were introduced by Rivest, Shamir and Wagner to encrypt data ‘into the future’.
In the same month VDFs were defined, two independent constructions were published by Pietrzak and Wesolowski. These two constructions allowed have evaluation proofs that are exponentially faster verification of the timelock puzzle construction previously introduced. This new cryptographic primitive can be used in distributed ledgers protocols to verify than the direct inherently-sequential evaluation. VDFs can be used by blockchains to create more scalable consensus protocols, introduce un-biasable unbiasable randomness, and enable proof-of-replication. Their use is already being incorporated into blockchain protocols such as Ethereum, the second largest blockchain platform in the world, and Filecoin, an upcoming platform offering decentralized storage. However, to retain the security properties provided by their computational delay, VDFs must be accelerated as much as possible to ensure that they provide a minimum elapsed real timeVDF evaluations must run fast enough to avoid attacks that jeopardise their connect to real-world time. Specifically, an attacker should not be able to evaluate VDFs more than, say, 10 times faster than the general public.
In order to better reason about the potential performance of a hardware accelerated VDF, the Ethereum Foundation, Protocol Labs, the Interchain Foundation, and Supranational have collaborated to develop novel algorithms and semiconductor designs for VDFs. In the first phase of the engagement these collaborators partnered This VDF alliance has focused on RSA VDFs based on repeated modular squaring. A partnership with Erdinc Ozturk of Sabanci University led to develop the development a low latency VDF modular squaring algorithm targeted at an ASIC architecture. The team This algorithm was able used to leverage this design to develop an FPGA implementation that solved a twenty-year-outstanding timelock puzzle at MIT that was developed by famed cryptographer Ron Rivest. While this design was focused on the evaluation component of VDFs, that is computing the sequential work required of a VDF, there is still a considerable amount of research to be completed to develop an efficient hardware accelerator to verify these functions. For example, the Rivest time lock puzzle took almost two months of computation to solve, and a similar amount of computational time to verify.
The goal of this proposal is to develop an ASIC hardware accelerator that can both evaluate the VDF function and quickly generate ‘proofs’. These proofs provide the ‘verifiable’ component of verifiable delay functions. Without an efficient means to generate proofs for VDFs, a large amount of parallel computing would be required after the evaluation of the VDF. By developing an accelerator that can both evaluate VDFs and generate proofs of their completion, VDFs can be leveraged to add randomness to decentralized consensus protocols in a trustless manner. By reducing the computational complexity of verifying VDFs, commodity hardware can be used by participants to maintain the state of a blockchain network.
While a relatively new cryptographic primitive, VDFs have been reviewed and investigated by top cryptographers such as Dan Boneh of Stanford and Ron Rivest of MIT. Since their introduction almost a year ago, there has been an increasing amount of academic research including investigations into continuous VDFs and VDFs from isogenies. In addition to their use in distributed ledger protocols, VDFs can be used to improve commit and reveal schemes, to improve the security of lotteries, and their acceleration may improve the practicality of other cryptographic techniques such as RSA accumulators.
Though VDFs are currently being developed to introduce randomness or enable proof-of-replication in distributed ledger protocols, they have the capability to drastically reduce the electricity consumed in traditional proof-of-work blockchain networks. VDFs provide many of the same properties of proof-of-work algorithms (sybil resistance, simple verification, etc.) without being parallelizable. This means that there is no incentive to develop ‘mining farms’ as they exist today. For example, the computational delay enforced by VDFs can be utilized to deploy ‘proof-of-elapsed time’ consensus as used in Hyperledger Sawtooth. A similar concept is employed by the blockchain protocol Chia, created by former inventor of BitTorrent Bram CohenDespite their recent introduction in mid-2018, VDFs has been an active field of research. Academic resources, video content, and explainers are available at vdfresearch.org. An FPGA competition to accelerate repeated modular squaring launched August 1, 2019.