Paper 2020/1522

Reducing Participation Costs via Incremental Verification for Ledger Systems

Weikeng Chen
Alessandro Chiesa
Emma Dauterman
Nicholas P. Ward

Ledger systems are applications run on peer-to-peer networks that provide strong integrity guarantees. However, these systems often have high participation costs. For a server to join this network, the bandwidth and computation costs grow linearly with the number of state transitions processed; for a client to interact with a ledger system, it must either maintain the entire ledger system state like a server or trust a server to correctly provide such information. In practice, these substantial costs centralize trust in the hands of the relatively few parties with the resources to maintain the entire ledger system state. The notion of *incrementally verifiable computation*, introduced by Valiant (TCC '08), has the potential to significantly reduce such participation costs. While prior works have studied incremental verification for basic payment systems, the study of incremental verification for a general class of ledger systems remains in its infancy. In this paper we initiate a systematic study of incremental verification for ledger systems, including its foundations, implementation, and empirical evaluation. We formulate a cryptographic primitive providing the functionality and security for this setting, and then demonstrate how it captures applications with privacy and user-defined computations. We build a system that enables incremental verification, for applications such as privacy-preserving payments, with universal (application-independent) setup. Finally, we show that incremental verification can reduce participation costs by orders of magnitude, for a bare-bones version of Bitcoin.

Note: Plumo citation update. Fix table layout.

Available format(s)
Cryptographic protocols
Publication info
incrementally verifiable computationsuccinct argumentsledger systems
Contact author(s)
weikengchen @ berkeley edu
alexch @ berkeley edu
edauterman @ berkeley edu
npward @ berkeley edu
2023-04-28: last of 2 revisions
2020-12-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Weikeng Chen and Alessandro Chiesa and Emma Dauterman and Nicholas P.  Ward},
      title = {Reducing Participation Costs via Incremental Verification for Ledger Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1522},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.