Paper 2017/963

Non-Interactive Proofs of Proof-of-Work

Aggelos Kiayias, Andrew Miller, and Dionysis Zindros

Abstract

Open consensus protocols based on proof-of-work (PoW) mining are at the core of cryptocurrencies such Bitcoin and Ethereum, as well as many others. In this work, we construct a new primitive called Non-Interactive Proofs of Proof-of-Work (NIPoPoWs) that can be adapted into existing PoW-based cryptocurrencies to improve their performance and extend their functionality. Unlike a traditional blockchain client which must verify the entire linearly-growing chain of PoWs, clients based on NIPoPoWs require resources only logarithmic in the length of the blockchain. NIPoPoWs are thus succinct proofs and require only a single message between the prover and the verifier of the transaction. With our construction we are able to prove a broad array of useful predicates in the context of cross PoW-based blockchain transfers of assets, including predicates about facts buried deep within a blockchain which is necessary for the basic application of accepting payments. We provide empirical validation for NIPoPoWs through an implementation and benchmark study, in the context of two new applications: First, we consider a multi-client blockchain that supports all proof-of-work currencies rather than just one, with up to 90% reduction in bandwidth. Second, we discuss a “cross-chain ICO” application that spans multiple independent blockchains. Using our experimental data, we provide concrete parameters for our scheme.

Note: Rewriting of the narrative of the paper; various bug fixes and improvements; definitional revisions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
blockchainproof-of-worksidechainsbitcoin
Contact author(s)
dionyziz @ gmail com
History
2018-05-31: last of 2 revisions
2017-09-30: received
See all versions
Short URL
https://ia.cr/2017/963
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/963,
      author = {Aggelos Kiayias and Andrew Miller and Dionysis Zindros},
      title = {Non-Interactive Proofs of Proof-of-Work},
      howpublished = {Cryptology ePrint Archive, Paper 2017/963},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/963}},
      url = {https://eprint.iacr.org/2017/963}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.