Efficient Verifiable Delay Functions
- PDF / 471,783 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 214 Views
Efficient Verifiable Delay Functions Benjamin Wesolowski Univ. Bordeaux, CNRS, Bordeaux INP, IMB, UMR 5251, 33400 Talence, France INRIA, IMB, UMR 5251, 33400 Talence, France Cryptology Group, CWI, Amsterdam, The Netherlands [email protected] Communicated by Masayuki Abe Received 21 October 2019 / Revised 27 July 2020
Abstract. We construct a verifiable delay function (VDF). A VDF is a function whose evaluation requires running a given number of sequential steps, yet the result can be efficiently verified. They have applications in decentralised systems, such as the generation of trustworthy public randomness in a trustless environment, or resource-efficient blockchains. To construct our VDF, we actually build a trapdoor VDF. A trapdoor VDF is essentially a VDF which can be evaluated efficiently by parties who know a secret (the trapdoor). By setting up this scheme in a way that the trapdoor is unknown (not even by the party running the setup, so that there is no need for a trusted setup environment), we obtain a simple VDF. Our construction is based on groups of unknown order such as an RSA group or the class group of an imaginary quadratic field. The output of our construction is very short (the result and the proof of correctness are each a single element of the group), and the verification of correctness is very efficient. Keywords. Time-lock puzzle, VDF, Randomness beacon, RSA, Class group.
1. Introduction We describe a function that is slow to compute and easy to verify: a verifiable delay function (henceforth, VDF) in the sense of [4].1 These functions should be computable in a prescribed amount of time Δ, but not faster (the time measures an amount of sequential work, that is work that cannot be performed faster by running on a large number of parallel cores), and the result should be easy to verify (i.e. for a cost polylog(Δ)). These special functions are used in [25] (under the name of slow-timed hash functions) to construct a trustworthy randomness beacon: a service producing publicly verifiable random numbers, which are guaranteed to be unbiased and unpredictable. These randomness beacons, introduced by Rabin [30], are a valuable tool in a public, decentralised setting, 1 The paper [4] was developed independently of the present work, yet we adopt their terminology for verifiable delay functions, for the sake of uniformity.
© International Association for Cryptologic Research 2020
B. Wesolowski
as it is not trivial for someone to flip a coin and convince their peers that the outcome was not rigged. A number of interesting applications of VDFs have recently emerged— see [4] for an overview. Most notably, they can be used to design resource-efficient blockchains [12], eliminating the need for massively power-consuming mining farms. VDFs play a key role in the Chia blockchain design (chia.net), and the Ethereum Foundation (ethereum.org) and Protocol Labs (protocol.ai) are teaming up to investigate the technology of VDFs which promise to play a key role in their respective platforms
Data Loading...
