A New Look at Blockchain Leader Election: Simple, Efficient, Sustainable and Post-Quantum

Muhammed F. Esgin; Oguzhan Ersoy; Veronika Kuchta; Julian Loss; Amin Sakzad; Ron Steinfeld; Xiangwen Yang; Raymond K. Zhao

Paper 2022/993

A New Look at Blockchain Leader Election: Simple, Efficient, Sustainable and Post-Quantum

Muhammed F. Esgin

, Monash University, CSIRO's Data61

Oguzhan Ersoy

, Radboud University, Delft University of Technology

Veronika Kuchta

, Florida Atlantic University

Julian Loss

, CISPA Helmholtz Center for Information Security

Amin Sakzad

, Monash University

Ron Steinfeld

, Monash University

Xiangwen Yang

, Monash University

Raymond K. Zhao

, CSIRO's Data61

Abstract

In this work, we study the blockchain leader election problem. The purpose of such protocols is to elect a leader who decides on the next block to be appended to the blockchain, for each block proposal round. Solutions to this problem are vital for the security of blockchain systems. We introduce an efficient blockchain leader election method with security based solely on standard assumptions for cryptographic hash functions (rather than public-key cryptographic assumptions) and that does not involve a racing condition as in Proof-of-Work based approaches. Thanks to the former feature, our solution provides the highest confidence in security, even in the post-quantum era. A particularly scalable application of our solution is in the Proof-of-Stake setting, and we investigate our solution in the Algorand blockchain system. We believe our leader election approach can be easily adapted to a range of other blockchain settings. At the core of Algorand's leader election is a verifiable random function (VRF). Our approach is based on introducing a simpler primitive which still suffices for the blockchain leader election problem. In particular, we analyze the concrete requirements in an Algorand-like blockchain setting to accomplish leader election, which leads to the introduction of indexed VRF (iVRF). An iVRF satisfies modified uniqueness and pseudorandomness properties (versus a full-fledged VRF) that enable an efficient instantiation based on a hash function without requiring any complicated zero-knowledge proofs of correct PRF evaluation. We further extend iVRF to an authenticated iVRF with forward-security, which meets all the requirements to establish an Algorand-like consensus. Our solution is simple, flexible and incurs only a 32-byte additional overhead when combined with the current best solution to constructing a forward-secure signature (in the post-quantum setting). We implemented our (authenticated) iVRF proposal in C language on a standard computer and show that it significantly outperforms other quantum-safe VRF proposals in almost all metrics. Particularly, iVRF evaluation and verification can be executed in 0.02 ms, which is even faster than ECVRF used in Algorand.

Note: Added DOI and updated performance results of another VRF proposal, LaV

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Minor revision. AsiaCCS 2023
DOI: 10.1145/3579856.3595792
Keywords: Blockchain Leader Election Verifiable Random Function Post-Quantum Algorand
Contact author(s): muhammed esgin @ monash edu
oguzhan ersoy @ ru nl
vkuchta @ fau edu
lossjulian @ gmail com
Amin Sakzad @ monash edu
Ron Steinfeld @ monash edu
Wayne Yang @ monash edu
raymond zhao @ data61 csiro au
History: 2023-07-12: last of 2 revisions; 2022-08-03: received; See all versions
Short URL: https://ia.cr/2022/993
License: CC BY

BibTeX

@misc{cryptoeprint:2022/993,
      author = {Muhammed F. Esgin and Oguzhan Ersoy and Veronika Kuchta and Julian Loss and Amin Sakzad and Ron Steinfeld and Xiangwen Yang and Raymond K. Zhao},
      title = {A New Look at Blockchain Leader Election: Simple, Efficient, Sustainable and Post-Quantum},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/993},
      year = {2022},
      doi = {10.1145/3579856.3595792},
      url = {https://eprint.iacr.org/2022/993}
}