Non-Interactive Proofs of Proof-of-Work. presented at FinancialCryptographyandDataSecurity 2020

by Aggelos Kiayias, Andrew Miller, Dionysis Zindros,

Summary : Decentralized consensus protocols based on proof-of-work(PoW) mining require nodes to download data linear in the size ofthe blockchain even if they make use of Simplified Payment Verification (SPV). In this work, we put forth a new formalization of proofof-work verification by introducing a primitive called Non-InteractiveProofs of Proof-of-Work (NIPoPoWs). We improve upon the previouslyknown SPV NIPoPoW by proposing a novel NIPoPoW construction using superblocks, blocks that are much heavier than usual blocks, whichcapture the fact that proof-of-work took place without sending all ofit. Unlike a traditional blockchain client which must verify the entirelinearly-growing chain of PoWs, clients based on superblock NIPoPoWsrequire resources only logarithmic in the length of the chain, insteaddownloading a compressed form of the chain. Superblock NIPoPoWs arethus succinct proofs and, due to their non-interactivity, require only asingle 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 largeperiods of time. Our scheme is provably secure in the Bitcoin Backbonemodel. From a theoretical point of view, we are the first to propose acryptographic prover–verifier definition for decentralized consensus protocols and the first to give a construction which can synchronize noninteractively using only a logarithmically-sized message.