Cryptology ePrint Archive: Report 2018/601

Verifiable Delay Functions

Dan Boneh and Joseph Bonneau and Benedikt Bünz and Ben Fisch

Abstract: We study the problem of building a verifiable delay function (VDF). A VDF requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. VDFs have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for VDFs and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.

Category / Keywords: cryptographic protocols / VDF, proof of sequential work, time-lock puzzle, RSA,

Original Publication (with minor differences): IACR-CRYPTO-2018

Date: received 12 Jun 2018, last revised 26 Jun 2019

Contact author: benafisch at gmail com, benedikt at cs stanford edu

Available format(s): PDF | BibTeX Citation

Note: Added a tight VDF construction from just verifiable computation

Version: 20190626:143251 (All versions of this report)

Short URL: ia.cr/2018/601