Cryptology ePrint Archive: Report 2020/096

Fully Distributed Verifiable Random Functions and their Application to Decentralised Random Beacons

David Galindo and Jia Liu and Mihai Ordean and Jin-Mann Wong

Abstract: We provide the first systematic analysis of (Non-Interactive) Fully Distributed Verifiable Random Functions (DVRFs), including their syntax, definition of integrity and privacy properties, and describe and analyse three concrete constructions, two of which are original. Building on recent work (Agrawal, Mohassel, Mukherjee, Rindal: CCS 2018), we strengthen the standard pseudorandomness property by allowing an adversary to make partial queries on the challenge value, and call the resulting property strong pseudorandomness. We show how a prominent DVRF construction in the blockchain space meets standard pseudorandomness, and provide two other instantiations that meet strong pseudorandomness, under widely accepted cryptographic assumptions. We review how to generically build a Decentralized Random Beacon (DRB) from any DVRF instance. DRBs have recently gained a lot traction as a key component for leader(s) election in decentralized ledger technologies. We provide implementations and experimental evaluations of three concrete DVRFs, using different cryptographic libraries. Our two new DRB instantiations are strongly pseudorandom and strongly unbiasable, while exhibiting high performance and linear communication complexity (as they are in essence non-interactive). We provide a C++ reference implementation that is available in open source form.

Category / Keywords: cryptographic protocols / Blockchain, Random Beacon, Distributed Computation, Leader Election, Implementation

Date: received 30 Jan 2020, last revised 3 Feb 2020

Contact author: david galindo at fetch ai

Available format(s): PDF | BibTeX Citation

Note: Reference implementation available at

Version: 20200204:124806 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]