Proof of Necessary Work: Succinct State Verification with Fairness Guarantees

Assimakis Kattis, Joseph Bonneau

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Blockchain-based payment systems utilize an append-only log of transactions whose correctness can be verified by any observer. Classically, verification costs grow linearly in either the number of transactions or blocks in the blockchain (often both). Incrementally Verifiable Computation (IVC) can be used to enable constant-time verification, but generating the necessary proofs is 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, producing proofs using energy that would otherwise be wasted. We implement and benchmark a prototype of our system, enabling stateless clients to verify the entire blockchain history in about 40 milliseconds.

Original languageEnglish (US)
Title of host publicationFinancial Cryptography and Data Security - 27th International Conference, FC 2023, Revised Selected Papers
EditorsFoteini Baldimtsi, Christian Cachin
PublisherSpringer Science and Business Media Deutschland GmbH
Pages18-35
Number of pages18
ISBN (Print)9783031477508
DOIs
StatePublished - 2024
Event27th International Conference on Financial Cryptography and Data Security, FC 2023 - Bol, Croatia
Duration: May 1 2023May 5 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13951
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Financial Cryptography and Data Security, FC 2023
Country/TerritoryCroatia
CityBol
Period5/1/235/5/23

Keywords

  • consensus algorithms
  • proof-of-work
  • zero-knowledge proofs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Proof of Necessary Work: Succinct State Verification with Fairness Guarantees'. Together they form a unique fingerprint.

Cite this