Non-interactive proofs of proof-of-work

Aggelos Kiayias, Andrew Miller, Dionysis Zindros*

*Corresponding author for this work

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

Abstract / Description of output

Decentralized consensus protocols based on proof-of-work (PoW) mining require nodes to download data linear in the size of the blockchain even if they make use of Simplified Payment Verification (SPV). In this work, we put forth a new formalization of proof-of-work verification by introducing a primitive called Non-Interactive Proofs of Proof-of-Work (NIPoPoWs). We improve upon the previously known SPV NIPoPoW by proposing a novel NIPoPoW construction using superblocks, blocks that are much heavier than usual blocks, which capture the fact that proof-of-work took place without sending all of it. Unlike a traditional blockchain client which must verify the entire linearly-growing chain of PoWs, clients based on superblock NIPoPoWs require resources only logarithmic in the length of the chain, instead downloading a compressed form of the chain. Superblock NIPoPoWs are thus succinct proofs and, due to their non-interactivity, require only a single message between the prover and the verifier of the transaction. Our construction allows the creation of superlight clients which can synchronize with the network quickly even if they remain offline for large periods of time. Our scheme is provably secure in the Bitcoin Backbone model. From a theoretical point of view, we are the first to propose a cryptographic prover–verifier definition for decentralized consensus protocols and the first to give a construction which can synchronize non-interactively using only a logarithmically-sized message.
Original languageEnglish
Title of host publicationFinancial Cryptography and Data Security
Subtitle of host publication24th International Conference
EditorsJoseph Bonneau, Nadia Heninger
Number of pages18
ISBN (Print)9783030512798
Publication statusPublished - 18 Jul 2020
Event24th International Conference on Financial Cryptography and Data Security - Kota Kinabalu, Malaysia
Duration: 10 Feb 202014 Feb 2020

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Financial Cryptography and Data Security
Abbreviated titleFC 2020
CityKota Kinabalu

Keywords / Materials (for Non-textual outputs)

  • bloackchain
  • proof-of-work
  • sidechains
  • bitcoin


Dive into the research topics of 'Non-interactive proofs of proof-of-work'. Together they form a unique fingerprint.

Cite this