Paper 2023/1103

Practical Large-Scale Proof-of-Stake Asynchronous Total-Order Broadcast

Orestis Alpos, University of Bern
Christian Cachin, University of Bern
Simon Holmgaard Kamp, Aarhus University
Jesper Buus Nielsen, Aarhus University

We present simple and practical protocols for generating randomness as used by asynchronous total-order broadcast. The protocols are secure in a proof-of-stake setting with dynamically changing stake. They can be plugged into existing protocols for asynchronous total-order broadcast and will turn these into asynchronous total-order broadcast with dynamic stake. Our contribution relies on two important techniques. The paper ``Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography'' [Cachin, Kursawe, and Shoup, PODC 2000] has influenced the design of practical total-order broadcast through its use of threshold cryptography. However, it needs a setup protocol to be efficient. In a proof-of-stake setting with dynamic stake this setup would have to be continually recomputed, making the protocol impractical. The work ``Asynchronous Byzantine Agreement with Subquadratic Communication'' [Blum, Katz, Liu-Zhang, and Loss, TCC 2020] showed how to use an initial setup for broadcast to asymptotically efficiently generate sub-sequent setups. The protocol, however, resorted to fully homomorphic encryption and was therefore not practically efficient. We adopt their approach to the proof-of-stake setting with dynamic stake, apply it to the Constantinople paper, and remove the need for fully homomorphic encryption. This results in simple and practical proof-of-stake protocols. We discuss how to use the new coin-flip protocols together with DAG rider [Keidar et al., PODC 2021] and create a variant which works for dynamic proof of stake. Our method can be employed together with many further asynchronous total-order broadcast protocols.

Available format(s)
Cryptographic protocols
Publication info
Total-Order BroadcastAtomic BroadcastProof of StakeRandom Beacon
Contact author(s)
orestis alpos @ unibe ch
christian cachin @ unibe ch
kamp @ cs au dk
jbn @ cs au dk
2023-07-17: approved
2023-07-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Orestis Alpos and Christian Cachin and Simon Holmgaard Kamp and Jesper Buus Nielsen},
      title = {Practical Large-Scale Proof-of-Stake Asynchronous Total-Order Broadcast},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1103},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.