A Quantum Money Solution to the Blockchain Scalability Problem

Andrea Coladangelo1 and Or Sattath2

1Computing and Mathematical Sciences, Caltech
2Computer Science Department, Ben-Gurion University

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We put forward the idea that classical blockchains and smart contracts are potentially useful primitives not only for classical cryptography, but for quantum cryptography as well. Abstractly, a smart contract is a functionality that allows parties to deposit funds, and release them upon fulfillment of algorithmically checkable conditions, and can thus be employed as a formal tool to enforce monetary incentives.
In this work, we give the first example of the use of smart contracts in a quantum setting. We describe a simple hybrid classical-quantum payment system whose main ingredients are a classical blockchain capable of handling stateful smart contracts, and quantum lightning, a strengthening of public-key quantum money introduced by Zhandry [55]. Our hybrid payment system employs quantum states as banknotes and a classical blockchain to settle disputes and to keep track of the valid serial numbers. It has several desirable properties: it is decentralized, requiring no trust in any single entity; payments are as quick as quantum communication, regardless of the total number of users; when a quantum banknote is damaged or lost, the rightful owner can recover the lost value.

Circa 1969, Wiesner proposed the idea of using the principles of quantum mechanics to construct “money that is physically impossible to counterfeit”.

40 years later, Nakamoto invented Bitcoin — a decentralized and censorship resistant form of money. Unlike other modern forms of money, here, no central party has control over the minting process (the issuance, or the printing of the money), users can make payments without permission from a central party, and the system is designed so that it is extremely hard to censor some transactions (for example, of a specific user), or the system as a whole.

Traditionally, quantum money and cryptocurrencies offer different trade-offs. One of the most serious limitations of Bitcoin and other crypto currencies is in terms of throughput: all the transactions need to be recorded in a shared ledger, and reaching consensus on that ledger is a slow process. Bitcoin supports less than 10 transactions per second, which is several orders of magnitude less than needed for a global currency.
Quantum money, on the other hand, is similar to cash, in which the throughput is essentially unbounded, as transactions only involve a payer and a payee; on the other hand, the minting is done by a central party, such as a central bank.

Is there a way to enjoy the benefits of both worlds – the decentralization and censorship resistance of a system such as Bitcoin, as well as the unlimited throughput that quantum money provides? In this work, we show that the answer is affirmative. We achieve this using a recent construction of a certain form of quantum money, called quantum lighting (Zhandry, Eurocrypt’19). Users can transform their “digital” cryptocurrency to quantum money, and use it much like cash. Users can also transform their quantum money back to its digital form, using a new cryptographic primitive which we introduce in this work, called bolt to signature capability.

For our design to be practical, the coherence time of quantum memory needs to increase from milliseconds to years. We expect that this increase would take decades to fruition. Additionally, the security of existing quantum lightning schemes is not satisfying: none of the existing schemes is provably secure based on standard assumptions.

► BibTeX data

► References

[1] S. Aaronson. Quantum copy-protection and quantum money. In Computational Complexity, 2009. CCC'09. 24th Annual IEEE Conference on, pages 229–242. IEEE, 2009.
https:/​/​doi.org/​10.1109/​CCC.2009.42

[2] G. Andresen and M. Hearn. Payment Protocol. Bitcoin Improvement Proposal (BIP) 70 https:/​/​github.com/​bitcoin/​bips/​blob/​master/​bip-0070.mediawiki, 2013.
https:/​/​github.com/​bitcoin/​bips/​blob/​master/​bip-0070.mediawiki

[3] E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin. In 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18-21, 2014, pages 459–474. IEEE Computer Society, 2014.
https:/​/​doi.org/​10.1109/​SP.2014.36

[4] J. Bonneau, J. Clark, and S. Goldfeder. On Bitcoin as a public randomness source. IACR Cryptology ePrint Archive, 2015:1015, 2015.
http:/​/​eprint.iacr.org/​2015/​1015

[5] C. Burchert, C. Decker, and R. Wattenhofer. Scalable funding of Bitcoin micropayment channel networks. Royal Society Open Science, 5(8):180089, August 2018.
https:/​/​doi.org/​10.1098/​rsos.180089

[6] I. Bentov and R. Kumaresan. How to use bitcoin to design fair protocols. In International Cryptology Conference, pages 421–439. Springer, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_24

[7] I. Bentov, R. Kumaresan, and A. Miller. Instantaneous decentralized poker. In International Conference on the Theory and Application of Cryptology and Information Security, pages 410–440. Springer, 2017. https:/​/​arxiv.org/​abs/​1701.06726.
arXiv:1701.06726

[8] C. Badertscher, U. Maurer, D. Tschudi, and V. Zikas. Bitcoin as a transaction ledger: A composable treatment. In Annual International Cryptology Conference, pages 324–356. Springer, 2017.
https:/​/​doi.org/​10.1007/​978-3-319-63688-7_11

[9] M. Ben-Or and D. Mayers. General security definition and composability for quantum & classical protocols. arXiv preprint quant-ph/​0409062, 2004.
arXiv:quant-ph/0409062

[10] S. Ben-David and O. Sattath. Quantum Tokens for Digital Signatures, 2016, arXiv: 1609.09047.
arXiv:1609.09047

[11] V. Buterin. Bitcoin Is Not Quantum-Safe, And How We Can Fix It When Needed. https:/​/​bitcoinmagazine.com/​articles/​bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150,http:/​/​www.webcitation.org/​6wDiIPU3l, 2013.
https:/​/​bitcoinmagazine.com/​articles/​bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150

[12] V. Buterin. A next-generation smart contract and decentralized application platform. https:/​/​github.com/​ethereum/​wiki/​wiki/​White-Paper, 2014.
https:/​/​github.com/​ethereum/​wiki/​wiki/​White-Paper

[13] R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 136–145. IEEE, 2001.
https:/​/​doi.org/​10.1109/​SFCS.2001.959888

[14] R. Canetti. Security and Composition of Cryptographic Protocols: A Tutorial. Technical report, Cryptology ePrint Archive, Report 2006/​465, 2006. http:/​/​eprint.iacr.org/​2006/​465,2006.
http:/​/​eprint.iacr.org/​2006/​465

[15] R. Canetti, Y. Dodis, R. Pass, and S. Walfish. Universally composable security with global setup. In Theory of Cryptography Conference, pages 61–85. Springer, 2007.
https:/​/​doi.org/​10.1007/​978-3-540-70936-7_4

[16] A. Coladangelo. Smart contracts meet quantum cryptography, 2019, arXiv: 1902.05214.
arXiv:1902.05214

[17] R. Canetti, D. Shahaf, and M. Vald. Universally composable authentication and key-exchange with global PKI. In IACR International Workshop on Public Key Cryptography, pages 265–296. Springer, 2016.
https:/​/​doi.org/​10.1007/​978-3-662-49387-8_11

[18] S. Dziembowski, L. Eckey, and S. Faust. Fairswap: How to fairly exchange digital goods. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 967–984. ACM, 2018.
https:/​/​doi.org/​10.1145/​3243734.3243857

[19] B. David, P. Gazi, A. Kiayias, and A. Russell. Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain. In J. B. Nielsen and V. Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume 10821 of Lecture Notes in Computer Science, pages 66–98. Springer, 2018.
https:/​/​doi.org/​10.1007/​978-3-319-78375-8_3

[20] C. Dwork and M. Naor. Pricing via Processing or Combatting Junk Mail. In Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, pages 139–147, 1992.
https:/​/​doi.org/​10.1007/​3-540-48071-4_10

[21] I. Eyal and E. G. Sirer. Majority Is Not Enough: Bitcoin Mining Is Vulnerable. In Financial Cryptography and Data Security - 18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers, pages 436–454, 2014, arXiv: 1311.0243.
https:/​/​doi.org/​10.1007/​978-3-662-45472-5_28
arXiv:1311.0243

[22] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, and P. Shor. Quantum money from knots. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 276–289, 2012.
https:/​/​doi.org/​10.1145/​2090236.2090260

[23] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, and P. Shor. Quantum money from knots. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 276–289. ACM, ACM, 2012, arXiv: 1004.5127.
https:/​/​doi.org/​10.1145/​2090236.2090260
arXiv:1004.5127

[24] O. Goldreich. The Foundations of Cryptography - Vol. 2, Basic Applications. Cambridge University Press, 2004.

[25] Z. Ji, Y. Liu, and F. Song. Pseudorandom Quantum States. In H. Shacham and A. Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III, volume 10993 of Lecture Notes in Computer Science, pages 126–152. Springer, 2018, arXiv: 1711.00385.
https:/​/​doi.org/​10.1007/​978-3-319-96878-0_5
arXiv:1711.00385

[26] J. Katz and Y. Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014.

[27] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: The blockchain model of cryptography and privacy-preserving smart contracts. In 2016 IEEE symposium on security and privacy (SP), pages 839–858. IEEE, 2016.
https:/​/​doi.org/​10.1109/​SP.2016.55

[28] A. Kiayias, A. Russell, B. David, and R. Oliynykov. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In J. Katz and H. Shacham, editors, Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, volume 10401 of Lecture Notes in Computer Science, pages 357–388. Springer, 2017.
https:/​/​doi.org/​10.1007/​978-3-319-63688-7_12

[29] A. Kiayias, H.-S. Zhou, and V. Zikas. Fair and robust multi-party computation using a global transaction ledger. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 705–734. Springer, 2016.
https:/​/​doi.org/​10.1007/​978-3-662-49896-5_25

[30] A. Lutomirski, S. Aaronson, E. Farhi, D. Gosset, A. Hassidim, J. Kelner, and P. Shor. Breaking and making quantum money: toward a new quantum cryptographic protocol. arXiv preprint arXiv:0912.3825, 2009.
arXiv:0912.3825

[31] L. Lamport. Constructing digital signatures from a one-way function, 1979.

[32] T. Lee, M. Ray, and M. Santha. On a quantum Bitcoin mining contest. private communication, 2018.

[33] A. Lutomirski. Component mixers and a hardness result for counterfeiting quantum money, 2011, arXiv: 1107.0321.
arXiv:1107.0321

[34] R. C. Merkle. Protocols for Public Key Cryptosystems. In Proceedings of the 1980 IEEE Symposium on Security and Privacy, Oakland, California, USA, April 14-16, 1980, pages 122–134. IEEE Computer Society, 1980.
https:/​/​doi.org/​10.1109/​SP.1980.10006

[35] I. Miers, C. Garman, M. Green, and A. D. Rubin. Zerocoin: Anonymous Distributed E-Cash from Bitcoin. In 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, May 19-22, 2013, pages 397–411. IEEE Computer Society, 2013.
https:/​/​doi.org/​10.1109/​SP.2013.34

[36] G. Malavolta, P. Moreno-Sanchez, A. Kate, M. Maffei, and S. Ravi. Concurrency and Privacy with Payment-Channel Networks. In B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 455–471. ACM, 2017.
https:/​/​doi.org/​10.1145/​3133956.3134096

[37] S. Meiklejohn, M. Pomarole, G. Jordan, K. Levchenko, D. McCoy, G. M. Voelker, and S. Savage. A fistful of Bitcoins: characterizing payments among men with no names. Commun. ACM, 59(4):86–93, 2016.
https:/​/​doi.org/​10.1145/​2896384

[38] M. Mosca and D. Stebila. Quantum coins, volume 523 of Contemp. Math., pages 35–47. Amer. Math. Soc., 2010, arXiv: 0911.1295.
arXiv:0911.1295

[39] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.
http:/​/​www.bitcoin.org/​bitcoin.pdf

[40] A. Narayanan. Hearing on Energy Efficiency of Blockchain and Similar Technologies, Committee on Energy and Natural Resources, United States Senate, August 2018.
https:/​/​www.energy.senate.gov/​public/​index.cfm/​files/​serve?File_id=8A1CECD1-157C-45D4-A1AB-B894E913737D

[41] A. Narayanan, J. Bonneau, E. W. Felten, A. Miller, and S. Goldfeder. Bitcoin and Cryptocurrency Technologies - A Comprehensive Introduction. Princeton University Press, 2016.

[42] J. Poon and T. Dryja. The bitcoin lightning network: Scalable off-chain instant payments, 2016.
https:/​/​www.bitcoinlightning.com/​wp-content/​uploads/​2018/​03/​lightning-network-paper.pdf

[43] A. Poelstra. Mimblewimble, 2016.
https:/​/​download.wpsoftware.net/​bitcoin/​wizardry/​mimblewimble.pdf

[44] D. Ron and A. Shamir. Quantitative Analysis of the Full Bitcoin Transaction Graph. In Financial Cryptography and Data Security - 17th International Conference, Japan, pages 6–24, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-39884-1_2

[45] D. Ron and A. Shamir. How Did Dread Pirate Roberts Acquire and Protect his Bitcoin Wealth? In Financial Cryptography and Data Security - FC 2014 Workshops, BITCOIN and WAHC 2014, Barbados, pages 3–15, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44774-1_1

[46] O. Sattath. Transforming Bitcoin to Quantum Money, and Back. Unplished Manuscript, 2019.

[47] Y. Tokunaga, T. Okamoto, and N. Imoto. Anonymous quantum cash, 2003.
http:/​/​qci.is.s.u-tokyo.ac.jp/​qci/​eqis03/​program/​papers/​O09-Tokunaga.ps.gz

[48] D. Unruh. Simulatable security for quantum protocols. arXiv preprint quant-ph/​0409125, 2004.
arXiv:quant-ph/0409125

[49] D. Unruh. Universally composable quantum multi-party computation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486–505. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-13190-5_25

[50] N. van Saberhagen. CryptoNote v 2.0, 2013.
https:/​/​cryptonote.org/​whitepaper.pdf

[51] S. Wehner, D. Elkouss, and R. Hanson. Quantum internet: A vision for the road ahead. Science, 362(6412):eaam9288, 2018.
https:/​/​doi.org/​10.1126/​science.aam9288

[52] S. Wiesner. Conjugate coding. ACM Sigact News, 15(1):78–88, 1983.
https:/​/​doi.org/​10.1145/​1008908.1008920

[53] G. Wood. Ethereum: a secure decentralised generalised transaction ledger. http:/​/​gavwood.com/​paper.pdf, 2014.
http:/​/​gavwood.com/​paper.pdf

[54] P. Wuille. Hierarchical deterministic wallets. Bitcoin Improvement Proposal (BIP) 32 https:/​/​github.com/​bitcoin/​bips/​blob/​master/​bip-0032.mediawiki, 2013.
https:/​/​github.com/​bitcoin/​bips/​blob/​master/​bip-0032.mediawiki

[55] M. Zhandry. Quantum Lightning Never Strikes the Same State Twice. In Y. Ishai and V. Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III, volume 11478 of Lecture Notes in Computer Science, pages 408–438. Springer, 2019, arXiv: 1711.02276.
https:/​/​doi.org/​10.1007/​978-3-030-17659-4_14
arXiv:1711.02276

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2020-08-10 16:17:50). On SAO/NASA ADS no data on citing works was found (last attempt 2020-08-10 16:17:51).