Paper 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.

Note: Reference implementation available at https://github.com/fetchai/research-dvrf