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, University of Queensland
Julian Loss, CISPA Helmholtz Center for Information Security
Amin Sakzad, Monash University
Ron Steinfeld, Monash University
Wayne Yang, Monash University
Raymond K. Zhao, Monash University

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 our proposal 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.

Available format(s)
Publication info
Blockchain Leader Election Verifiable Random Function Post-Quantum Algorand
Contact author(s)
muhammed esgin @ monash edu
oguzhan ersoy @ ru nl
v kuchta @ uq edu au
lossjulian @ gmail com
Amin Sakzad @ monash edu
Ron Steinfeld @ monash edu
Wayne Yang @ monash edu
Raymond Zhao @ monash edu
2022-08-03: approved
2022-08-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Muhammed F. Esgin and Oguzhan Ersoy and Veronika Kuchta and Julian Loss and Amin Sakzad and Ron Steinfeld and Wayne 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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.