Paper 2020/096

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

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

Abstract

We provide the first systematic analysis of two multiparty protocols, namely (Non-Interactive) Fully Distributed Verifiable Random Functions (DVRFs) and Decentralised Random Beacons (DRBs), including their syntax and definition of robustness and privacy properties. We refine current pseudorandomness definitions for distributed functions and show that the privacy provided by strong pseudorandomness, where an adversary is allowed to make partial function evaluation queries on the challenge value, is strictly better than that provided by standard pseudorandomness, where such adversarial queries are disallowed. We provide two new DVRF instantiations, named DDH-DVRF and GLOW-DVRF, that meet strong pseudorandomness under widely accepted cryptographic assumptions. Additionally we show that a previously sketched DVRF construction that we name Dfinity-DVRF meets the weaker property of standard pseudorandomness. We show the usefulness of our DRB formalism in two different ways. Firstly, we give a rigorous treatment of a folklore generic construction that builds a Decentralized Random Beacon from any DVRF instance and prove that it satisfies robustness and pseudorandomness provided that the original DVRF protocol is secure. Secondly, we capture several existing DRB protocols from academy and industry using our framework, which serves as an evidence of its wider applicability. DRBs have recently gained a lot traction as a key component for leader(s) election in decentralized ledger technologies, and we provide a classification of some of the most prominent. By building on an an obvious connection between Dfinity-DVRF and Threshold BLS signatures we discuss how to transform GLOW-DVRF into a modified Threshold BLS signature scheme with stronger security as an additional contribution of independent value. Finally, we report on experimental evaluations of the three concrete DVRFs studied under several cryptographic libraries, and we also report preliminary benchmark results on two of the DRBs obtained from the generic DVRF-to-DRB transformation. Our findings are that our two new DRB instantiations are strongly pseudorandom and strongly unbiasable, while exhibiting high performance and linear communication complexity (as the random beacon values are computed in a non-interactive fashion). We conclude that our new DRB instantiations are to our knowledge the most efficient instantiations currently available while enjoying strong and formally proven security properties. Some of our benchmarks can be independently verified as we provide an open source C++ reference implementation of the DVRFs discussed in this work.

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