Paper 2022/1642

Proofs of Proof-of-Stake with Sublinear Complexity

Shresth Agrawal, Jacobs University Bremen
Joachim Neu, Stanford University
Ertem Nusret Tas, Stanford University
Dionysis Zindros, Stanford University

Popular Ethereum wallets (e.g., MetaMask) entrust centralized infrastructure providers (e.g., Infura) to run the consensus client logic on their behalf. As a result, these wallets are light-weight and high-performant, but come with security risks. A malicious provider can mislead the wallet, e.g., fake payments and balances, or censor transactions. On the other hand, light clients, which are not in popular use today, allow decentralization, but at concretely inefficient and asymptotically linear bootstrapping complexity. This poses a dilemma between decentralization and performance. In this paper, we design, implement, and evaluate a new proof-of-stake (PoS) superlight client with concretely efficient and asymptotically logarithmic bootstrapping complexity. Our proofs of proof-of-stake (PoPoS) take the form of a Merkle tree of PoS epochs. The verifier enrolls the provers in a bisection game, in which the honest prover is destined to win once an adversarial Merkle tree is challenged at sufficient depth. To evaluate our superlight protocol, we provide a client implementation that is compatible with mainnet PoS Ethereum: compared to the state-of-the-art light client construction of PoS Ethereum, our client improves time-to-completion by 9x, communication by 180x, and energy usage by 30x (when bootstrapping after 10 years of consensus execution). We prove that our construction is secure and show how to employ it for other PoS systems such as Cardano (with full adaptivity), Algorand, and Snow White.

Available format(s)
Publication info
blockchain proof of stake ethereum superlight client light client optimistic
Contact author(s)
s agrawal @ jacobs-university de
jneu @ stanford edu
nusret @ stanford edu
dionyziz @ stanford edu
2022-12-15: last of 2 revisions
2022-11-25: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Shresth Agrawal and Joachim Neu and Ertem Nusret Tas and Dionysis Zindros},
      title = {Proofs of Proof-of-Stake with Sublinear Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1642},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.