Paper 2022/1642

Proofs of Proof-of-Stake with Sublinear Complexity

Shresth Agrawal, Jacobs University Bremen, Technische Universität München
Joachim Neu, Stanford University
Ertem Nusret Tas, Stanford University
Dionysis Zindros, Stanford University
Abstract

Popular Ethereum wallets (like 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 by faking payments and balances, or censoring transactions. On the other hand, light clients, which are not in popular use today, allow decentralization, but are concretely inefficient, often with asymptotically \emph{linear} bootstrapping complexity. This poses a dilemma between decentralization and performance. We design, implement, and evaluate a new proof-of-stake (PoS) \emph{superlight} client with concretely efficient and asymptotically \emph{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 honest provers are destined to win once an adversarial Merkle tree is challenged at sufficient depth. We provide an implementation for mainnet Ethereum: compared to the state-of-the-art light client construction of Ethereum, our client improves time-to-completion by $9\times$, communication by $180\times$, and energy usage by $30\times$ (when bootstrapping after $10$ years of consensus execution). As an important additional application, our construction can be used to realize trustless cross-chain bridges, in which the superlight client runs within a smart contract and takes the role of an on-chain verifier. We prove our construction is secure and show how to employ it for other PoS systems such as Cardano (with fully adaptive adversary), Algorand, and Snow White.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. Advances in Financial Technologies - AFT 2023
Keywords
blockchainproof of stakeethereumsuperlight clientlight clientoptimistic
Contact author(s)
s agrawal @ jacobs-university de
jneu @ stanford edu
nusret @ stanford edu
dionyziz @ stanford edu
History
2023-10-05: last of 3 revisions
2022-11-25: received
See all versions
Short URL
https://ia.cr/2022/1642
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1642,
      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{https://eprint.iacr.org/2022/1642}},
      url = {https://eprint.iacr.org/2022/1642}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.