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
BlockchainLeader ElectionVerifiable Random FunctionPost-QuantumAlgorand
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.