Paper 2022/993
A New Look at Blockchain Leader Election: Simple, Efficient, Sustainable and Post-Quantum
, Monash University, CSIRO's Data61, Radboud University, Delft University of Technology, Florida Atlantic University, CISPA Helmholtz Center for Information Security, Monash University, Monash University, Monash University, CSIRO's Data61Abstract
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
-
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},
note = {\url{https://eprint.iacr.org/2022/993}},
url = {https://eprint.iacr.org/2022/993}
}
