Verifiable Delay Functions

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

Paper 2018/601

Verifiable Delay Functions

Dan Boneh, Joseph Bonneau, 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.

Note: Added a tight VDF construction from just verifiable computation

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in Crypto 2018
Keywords: VDF proof of sequential work time-lock puzzle RSA
Contact author(s): benafisch @ gmail com
benedikt @ cs stanford edu
History: 2019-06-26: last of 6 revisions; 2018-06-18: received; See all versions
Short URL: https://ia.cr/2018/601
License: CC BY

BibTeX

@misc{cryptoeprint:2018/601,
      author = {Dan Boneh and Joseph Bonneau and Benedikt Bünz and Ben Fisch},
      title = {Verifiable Delay Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/601},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/601}},
      url = {https://eprint.iacr.org/2018/601}
}