Reducing Participation Costs via Incremental Verification for Ledger Systems

Weikeng Chen; Alessandro Chiesa; Emma Dauterman; Nicholas P.  Ward

Paper 2020/1522

Reducing Participation Costs via Incremental Verification for Ledger Systems

Weikeng Chen

Alessandro Chiesa

Emma Dauterman

Nicholas P. Ward

Abstract

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: incrementally verifiable computation succinct arguments ledger systems
Contact author(s): weikengchen @ berkeley edu
alexch @ berkeley edu
edauterman @ berkeley edu
npward @ berkeley edu
History: 2023-04-28: last of 2 revisions; 2020-12-08: received; See all versions
Short URL: https://ia.cr/2020/1522
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1522,
      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{https://eprint.iacr.org/2020/1522}},
      url = {https://eprint.iacr.org/2020/1522}
}