Non-interactive Proofs of Proof-of-Work

Aggelos Kiayias, Andrew Miller, Dionysis Zindros

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

Abstract

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 (US)
Title of host publicationFinancial Cryptography and Data Security - 24th International Conference, FC 2020, Revised Selected Papers
EditorsJoseph Bonneau, Nadia Heninger
PublisherSpringer
Pages505-522
Number of pages18
ISBN (Print)9783030512798
DOIs
StatePublished - 2020
Event24th International Conference on Financial Cryptography and Data Security, FC 2020 - Kota Kinabalu, Malaysia
Duration: Feb 10 2020Feb 14 2020

Publication series

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

Conference

Conference24th International Conference on Financial Cryptography and Data Security, FC 2020
Country/TerritoryMalaysia
CityKota Kinabalu
Period2/10/202/14/20

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Non-interactive Proofs of Proof-of-Work'. Together they form a unique fingerprint.

Cite this