TY - GEN
T1 - Non-interactive Proofs of Proof-of-Work
AU - Kiayias, Aggelos
AU - Miller, Andrew
AU - Zindros, Dionysis
N1 - Publisher Copyright:
© 2020, International Financial Cryptography Association.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85089240146&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089240146&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-51280-4_27
DO - 10.1007/978-3-030-51280-4_27
M3 - Conference contribution
AN - SCOPUS:85089240146
SN - 9783030512798
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 505
EP - 522
BT - Financial Cryptography and Data Security - 24th International Conference, FC 2020, Revised Selected Papers
A2 - Bonneau, Joseph
A2 - Heninger, Nadia
PB - Springer
T2 - 24th International Conference on Financial Cryptography and Data Security, FC 2020
Y2 - 10 February 2020 through 14 February 2020
ER -