Abstract
In the setting of blockchain based transaction ledgers we study the problem of “simplified payment verification” (SPV) which refers to the setting of a transaction verifier that wishes to examine the last k blocks of the blockchain (e.g., for the purpose of verification of a certain transaction) using as only advice the genesis block (or some “checkpoint” block that is known to it).
The straightforward solution to this task requires the delivery of the blockchain, the verification of the proof of work it contains, and subsequently the examination of the last k blocks. It follows that the communication required to complete this task is linear in the length of the chain.
At first thought the above seems the best one can hope: a sublinear in the length of the chain solution to the problem will be susceptible to an attacker that, using precomputation, can fool the verifier.
Contrary to this intuition, we show that with a suitable modification to the current Bitcoin blockchain protocol (that incurs a single hash expansion in each block and gives rise to the notion of an interconnected blockchain) we can produce proofs of proof of work with sublinear complexity in the length of the chain hence enabling SPV to be performed much more efficiently.
This research was supported by ERC project CODAMODA, # 259152.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Or a checkpoint block, if the verifier is in possession of such a block.
- 2.
We thank the anonymous reviewers of the 3rd Workshop on Bitcoin and Blockchain Research for providing pointers to the relevant forum posts.
- 3.
We note that there is no provision for authenticated channels in the Bitcoin setting; hence when we refer to a request for information from a certain player this is not performed in an authenticated fashion.
- 4.
Here we use the following variant: \(\mathrm {Pr}(X \le k ) \le \exp (- (np-k)^2/ 2np) \), where \(k\le np\).
- 5.
Roughly because \(\gamma = \alpha - \alpha ^2\) and thus this condition approximates the “honest majority” condition only if \(\alpha ^2\) is close to 0. See [6] for more details.
References
Back, A.: Hashcash (1997). http://www.cypherspace.org/hashcash
Back, A., Corallo, M., Dashjr, L., Friedenbach, M., Maxwell, G., Miller, A., Poelstra, A., Timn, J., Wuille, P.: Enabling Blockchain Innovations with Pegged Sidechains (2014). https://blockstream.com/sidechains.pdf
Bahack, L.: Theoretical bitcoin attacks with less than half of the computational power (draft). Cryptology ePrint Archive, Report 2013/868 (2013). http://eprint.iacr.org/
Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993)
Friedenbach, M.: Compact SPV proofs via block header commitments, Bitcoin-development mailing list post (2014). https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-March/004727.html
Garay, J., Kiayias, A., Leonardos, N.: The Bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015)
Juels, A., Brainard, J.G.: Client puzzles: a cryptographic countermeasure against connection depletion attacks. In: NDSS. The Internet Society (1999)
Lewenberg, Y., Sompolinsky, Y., Zohar, A.: Inclusive block chain protocols. In: Böhme, R., Okamoto, T. (eds.) FC 2015. LNCS, vol. 8975, pp. 528–547. Springer, Heidelberg (2015)
Miller, A.: The high-value-hash highway, Bitcoin forum post (2012). https://bitcointalk.org/index.php?topic=98986.0
Nakamoto, S.: Bitcoin: a peer to peer electronic cash system (2008). http://bitcoin.org/bitcoin.pdf
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report, Cambridge, MA, USA (1996)
Sompolinsky, Y., Zohar, A.: Secure high-rate transaction processing in bitcoin. In: Böhme, R., Okamoto, T. (eds.) FC 2015. LNCS, vol. 8975, pp. 507–527. Springer, Heidelberg (2015)
Acknowledgement
The authors wish to thank Giorgos Panagiotakos for helpful discussions as well as the anonymous referees of the 3rd Workshop on Bitcoin and Blockchain Research for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 International Financial Cryptography Association
About this paper
Cite this paper
Kiayias, A., Lamprou, N., Stouka, AP. (2016). Proofs of Proofs of Work with Sublinear Complexity. In: Clark, J., Meiklejohn, S., Ryan, P., Wallach, D., Brenner, M., Rohloff, K. (eds) Financial Cryptography and Data Security. FC 2016. Lecture Notes in Computer Science(), vol 9604. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53357-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-662-53357-4_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53356-7
Online ISBN: 978-3-662-53357-4
eBook Packages: Computer ScienceComputer Science (R0)