Proof of Necessary Work: Succinct State Verification with Fairness Guarantees

Assimakis Kattis, Joseph Bonneau

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


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
Number of pages18
ISBN (Print)9783031477508
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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Financial Cryptography and Data Security, FC 2023


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this