Paper 2020/190

Proof of Necessary Work: Succinct State Verification with Fairness Guarantees

Assimakis Kattis and Joseph Bonneau

Abstract

Blockchain-based payment systems utilize an append-only log of transactions whose correctness can be verified by any observer. In almost all of today’s implementations, verification costs grow linearly in either the number of transactions or blocks in the blockchain (often both). We propose a new distributed payment system which uses Incrementally Verifiable Computation (IVC) to enable constant-time verification. Since generating the succinct proofs needed to verify correctness is more expensive, we introduce the notion of Proof of Necessary Work (PoNW), in which proof generation is an integral part of the proof-of-work used in Nakamoto consensus, effectively producing proofs using energy that would otherwise be wasted. We implement and benchmark a prototype of our system using recent recursive SNARK-based constructions, enabling stateless “light” clients to efficiently verify the entire blockchain history in about 40 milliseconds.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
proof-of-workconsensusIVCzk-snarks
Contact author(s)
kattis @ cs nyu edu
History
2020-02-18: received
Short URL
https://ia.cr/2020/190
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/190,
      author = {Assimakis Kattis and Joseph Bonneau},
      title = {Proof of Necessary Work: Succinct State Verification with Fairness Guarantees},
      howpublished = {Cryptology ePrint Archive, Paper 2020/190},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/190}},
      url = {https://eprint.iacr.org/2020/190}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.