<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by John Smith on Medium]]></title>
        <description><![CDATA[Stories by John Smith on Medium]]></description>
        <link>https://medium.com/@jsmith.anonymous113?source=rss-58943ad05c46------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*CDlX9imKdi6ZKSRL7pXJVg.png</url>
            <title>Stories by John Smith on Medium</title>
            <link>https://medium.com/@jsmith.anonymous113?source=rss-58943ad05c46------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 13:16:04 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@jsmith.anonymous113/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Bitcoin and Quantum Computing — An Unpleasant Collision Course]]></title>
            <link>https://medium.com/@jsmith.anonymous113/bitcoin-and-quantum-computing-an-unpleasant-collision-course-c69ed2a7c455?source=rss-58943ad05c46------2</link>
            <guid isPermaLink="false">https://medium.com/p/c69ed2a7c455</guid>
            <category><![CDATA[quantum-computing]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[security]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[bitcoin]]></category>
            <dc:creator><![CDATA[John Smith]]></dc:creator>
            <pubDate>Sat, 22 Dec 2018 03:08:50 GMT</pubDate>
            <atom:updated>2018-12-23T03:51:12.877Z</atom:updated>
            <content:encoded><![CDATA[<h3>Bitcoin and Quantum Computing — An Unpleasant Collision Course</h3><p><strong><em>“First movers very rarely win with new technology…because tech becomes obsolete. Tech innovates or it dies.”</em></strong></p><p>– <em>Ari Paul, co-founder/CIO of Blocktower Capital, on Anthony Pompliano’s Off the Chain Podcast, 12/17/18</em></p><p><strong>Quantum computing will profoundly disrupt Bitcoin and the entire cryptocurrency ecosystem. Bitcoin’s developers have a plan for transitioning to quantum-resistant cryptography, but their best efforts may not be enough to avert existential risk to the network.</strong></p><p><strong>THE GENIUS OF BITCOIN: DISTRIBUTED CRYPTOGRAPHIC CONSENSUS</strong></p><p>The first blockchain blinked into existence on January 3, 2009, when Satoshi Nakamoto’s computer mined the genesis block of bitcoins. Starting with that entry, the entire history of Bitcoin transactions is stored in an ever-growing ledger that can now be found on millions of hard drives worldwide. Other blockchains have sprung up around it, giving rise to a young, thriving technological ecosystem. What began as a revolution in digital money has expanded to distributed computation more generally and is now positioned to be one of the fastest-growing sectors in the global economy over the coming decade.</p><p>Bitcoin was the first implementation of digital money that solved the problem of preventing users from spending the same funds more than once without using a centralized database. This is the fundamental innovation of blockchain technology: <em>distributed consensus.</em> By recording every transaction on a ledger that is kept by every node on the network, it becomes trivial to achieve agreement among all parties on which funds belong to whom. Each user’s funds are secured by what is known as <em>public-key cryptography</em>, which allows the use of public addresses on the ledger that can be viewed by anyone but only allow their respective owners to make transactions. The creator of an address receives a corresponding ‘private key’ that is used to digitally sign transactions from that address.</p><p>The security of these digital signatures relies on the existence of mathematical problems that are much harder to solve than their solutions are to check. To crack the so-called Elliptic Curve Digital Signature Algorithm (ECDSA) used by Bitcoin would take today’s fastest supercomputer far over a trillion years. However, in 1999, Peter Shor published an algorithm could do it in ‘polynomial time’, easily on the timescale of hours or minutes [1]. The catch is, this algorithm requires a different kind of computer altogether — a <em>quantum computer</em>.</p><p><strong>QUANTUM COMPUTING WILL DISRUPT CRYPTOCURRENCIES’ DIGITAL SIGNATURE ALGORITHMS</strong></p><p>Quantum Computing may end up being the most significant technology development of the 21st century. Following several decades of slow but steady progress, a bona fide technological arms race has now begun. With QC on the verge of reaching utility at a large scale, superpowers like the USA, China, and the EU have invested billions of dollars into research and development [2, 3]. The world’s largest technology corporations have also sprung into competition on this frontier, including Google, IBM, Microsoft, Intel, and Alibaba. What used to be a niche area of physics is becoming replete with entrepreneurs and scientists determined to carve out of a slice of this emerging sector for themselves. Massive value will accrue to the winners in the race to build the world’s largest and most effective quantum computer.</p><p>The alarm has begun to be raised about the approaching downfall of modern cryptographic standards. Digital signature algorithms such as ECDSA and the closely related RSA secure not only Bitcoin and cryptocurrencies but the entire internet, banking system, and more. The issue has been covered by <a href="https://www.economist.com/science-and-technology/2018/10/20/quantum-computers-will-break-the-encryption-that-protects-the-internet">the Economist</a> [4], <a href="http://fortune.com/2018/12/15/quantum-computer-security-encryption/">Fortune</a> [5], and <a href="https://www.nytimes.com/2018/12/03/technology/quantum-encryption.html">the New York Times</a> [6]. While large-scale quantum computers appear to still be at least five years out, major governmental institutions such as the NSA are already beginning their transition to post-quantum standards [7]. The United States’ National Institute of Standards and Technology, or NIST, has stated that “regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing”. Several scientific articles have gone further into detail on the nature of the threat specifically to Bitcoin and blockchains [8, 9], including a recent <a href="https://www.nature.com/articles/d41586-018-07449-z">Nature commentary</a> [11].</p><p>The response in the cryptocurrency community, however, has so far been muted. While several luminaries in the field, including Vitalik Buterin and Andreas Antonopoulos, have briefly addressed the issue [12, 13], we will see below how their statements fail to account for the full scope of the problem at hand. In the remainder of this article, we will critically examine the current state of thinking around Bitcoin’s eventual migration to post-quantum cryptography.</p><p><strong><em>KR: “Andreas, I want to ask you one last question, and it’s one that really scares the shit out of me, and that is quantum computing. It seems like every other week I’m hearing some press about quantum computing, and how they’re making giant leaps forward. Doesn’t quantum computing and this idea of being able to potentially crack the encryption that underpins all of these cryptocurrencies … is that going to be a reality in the next ten to twenty years?”</em></strong></p><p><strong><em>AA: “Absolutely. It is going to be a reality.”</em></strong></p><p><strong><em>— Kevin Rose &amp; Andreas Antonopoulos, on the Kevin Rose Podcast, 11/13/17</em></strong></p><p><strong>THE NATURE OF THE PROBLEM</strong></p><p>The most obvious explanation for the lack of clamor around this topic in the world of cryptocurrencies is an understandable ignorance that it is even worth discussing in the first place. However, for those investors, developers, and enthusiasts who have stumbled across mentions of quantum computing’s role in the future of cryptocurrency, the line of thinking may instead be something like, <em>“Bitcoin’s developers have already thought about this and have a plan to take care of it when the time comes.” </em>Is that really the case? Let’s see how the core developers themselves think about the subject.</p><p>A discussion on the Bitcoin dev forum titled ‘<a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015761.html">Transition to post-quantum</a>’ began on February 15, 2017, with core developers Tristan Hoy and Tim Ruffing laying out the plans for what is known as a <em>commit-delay-reveal</em> transaction scheme [14]. Adam Back, renowned cryptographer and Blockstream CEO, has proposed a similar mechanism [15].</p><h3>Adam Back on Twitter</h3><p>@real_or_random @secparam @matthew_d_green @zkproofs @johnsonlau01 There&#39;s a similar design challenge in committed tx (aka encrypted tx). One commit mechanism I suggested H2(pubkey),k=H3(pubkey),AE(k,PQkey,PQsig). Where AE is authenticated symmetric key encryption. Then first valid commitment wins. You could build it using committed tx.</p><p>To understand what this entails, we must first appreciate the specific threat this method is meant to combat.</p><p>The essential problem is this. If Bitcoin changes nothing, then eventually, addresses with known public keys will have their private keys derived from those public keys by a quantum computer running Shor’s algorithm. This includes very old addresses (including Satoshi’s) as well as addresses that have sent a transaction, publishing their public keys to the blockchain. The owner of that quantum computer could then simply use the found private keys to send bitcoin from those addresses to themselves. A transition to a post-quantum digital signature algorithm does not solve this problem; an attacker could simply use the vulnerability to claim balances on the new chain using the old-format private keys. An alternative method of attack would be to short bitcoin and then make this vulnerability public, crashing the value of bitcoin and enriching themselves in the process.</p><p>The commit-delay-reveal scheme is meant to help Bitcoin address these challenges. It works as follows: a user can create a wallet secured by a post-quantum signature algorithm, then publish a transaction to the blockchain using a combination of their old private key, the new private key from that post-quantum address, and a predefined delay period (which the authors in [10] suggest should be approximately 6 months). The transaction would then go through after that period of time.</p><p>That is the most rigorous solution available. Unfortunately, it has several crucial flaws: first, not only do those become funds unusable for a long period of time, but the process significantly bloats the blockchain [14] and may be too technically challenging to be performed by less savvy holders of bitcoin. Second, whether a commit-delay-reveal scheme is implemented or not, bitcoin residing in vulnerable addresses with lost private keys will be stolen anyways. Ultimately, those funds can still be dumped on the market by an attacker who simultaneously shorts bitcoin, as enumerated above.</p><p>Bitcoin’s developers have also considered stopgap measures. A bitcoin-dev <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-December/016556.html">discussion </a>from December 14th, 2018 [16] suggests including the capability of generating addresses based on higher-bit (e.g., 381-bit instead of 256-bit) elliptic curves, which would require about 150% as many qubits as the present curves to efficiently crack via Shor’s algorithm. Of course, these measures fail to solve the fundamental problem of relying on elliptic-curve digital signatures. Like the commit-delay-reveal scheme, these mechanisms also rely on individual users opting in to using the more secure signatures, leaving millions of bitcoins behind in vulnerable addresses.</p><p>This threat may end up being existential. It is also not limited to Bitcoin — indeed, it imperils the future of nearly every single cryptocurrency in existence today. In order to be immune to quantum computing attacks, a cryptocurrency must have utilized a post-quantum signature algorithm from its inception. Several examples already exist, and more will inevitably follow in the years to come. Heavily centralized altcoin projects may also have a fighting chance to make it over this hump.</p><p><strong>HOW LONG DO WE HAVE?</strong></p><p>The number of <em>logical qubits</em> required to crack secp256k1, the specific elliptic curve on which Bitcoin’s public-key cryptography is based, is approximately 2330 [17]. The noisiness associated with qubits, however, means that the number of qubits in a quantum computer is larger than the number of logical qubits that it functionally possesses. A scientific paper by Aggarwal et al. (2017) modeled the development of quantum computing given optimistic and conservative assumptions, respectively; this model estimates that 2330 logical qubits will be available between approximately 2024 and 2030. If higher-bit elliptic curves are used as a stopgap, it will shift Bitcoin’s security window by a year or two. Eventually, though, the blockchain’s ability to support more complex curves will be outstripped by the exponentially-growing computational abilities of quantum computers.</p><p><strong>Further Reading</strong>: <a href="https://medium.com/coinmonks/quantum-computers-pose-a-credible-threat-to-the-security-of-bitcoin-4b1dd65944ca">https://medium.com/coinmonks/quantum-computers-pose-a-credible-threat-to-the-security-of-bitcoin-4b1dd65944ca</a></p><p><strong>APPENDIX A — CRITICAL EVALUATION OF ANDREAS’ AND VITALIK’S ATTEMPTS TO ADDRESS THIS ISSUE</strong></p><p>Andreas Antonopoulos has addressed the threat of quantum computers to cryptocurrencies several times <a href="https://www.kevinrose.com/single-post/andreas-antonopolous">(KR podcast</a>), (<a href="https://www.youtube.com/watch?v=wlzJyp3Qm7s">YouTube Video</a>). In the rest of the interview quoted above, Andreas goes on to say that cryptocurrencies may be “the least of our worries” when it comes to quantum computing. Specifically, he delineates <em>unequal</em> <em>availability</em> of quantum computing as the major threat. His ultimate proposed solution to the problem, however, is just that the algorithm can be changed whenever it becomes necessary. This article has made it clear why it will be anything but straightforward to do so.</p><p>Vitalik Buterin has also addressed the threat of quantum computers in an incredibly prescient <a href="https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150/">article </a>entitled “Bitcoin is not quantum-safe, and how we can fix it when needed”. To quote from his article, he states:</p><p><em>“The solution is this: as soon as a quantum pre-emergency is declared, everyone should move their wealth into a 1-of-2 multisignature transaction between an unused, old-style, Bitcoin address, and an address generated with the new Lamport scheme. Then, developers should quickly create the Lamport patch for as many Bitcoin clients as possible and push for everyone to upgrade. If the whole process is done within weeks, then by the time quantum computers become a threat the bulk of people’s bitcoins will be in new-style Lamport addresses and will be safe.”</em></p><p>This assumes that everyone both can and will move their bitcoin to new wallets. As mentioned above, this will not be possible for wallets whose private keys have been lost, or for users who are unable or unwilling at the time to respond in such a manner. The commit-delay-reveal scheme being considered by Bitcoin’s developers is a more evolved (and less centralized) solution than what Vitalik articulates, and it still has the problems that are discussed above.</p><p><strong>WORKS CITED</strong></p><p>1. Shor, P.W., <em>Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.</em> SIAM review, 1999. <strong>41</strong>(2): p. 303–332.</p><p>2. Castelvecchi, D., <em>Europe Shows First Cards in €1-billion Quantum Bet.</em> 2018.</p><p>3. McFarland, M. <em>China bet big on quantum computing. Now the US races to keep up.</em> 2018 12/20/2018].</p><p>4. <em>Quantum computers will break the encryption that protects the internet</em>, in <em>The Economist</em>. 2018.</p><p>5. Hackett, R., <em>Quantum Computers Threaten the Web’s Security. We Must Take Action Now</em>, in <em>Fortune</em>. 2018.</p><p>6. Cade Metz, R.Z., <em>The Race Is On to Protect Data From the Next Leap in Computers. And China Has the Lead.</em>, in <em>The New York Times</em>. 2018.</p><p>7. Schneier, B. <em>NSA Plans for a Post-Quantum World</em>. 2015; Available from: <a href="https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html">https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html</a></p><p>8. <em>Post-Quantum Cryptography</em>. December 17, 2018; Available from: <a href="https://csrc.nist.gov/projects/post-quantum-cryptography.">https://csrc.nist.gov/projects/post-quantum-cryptography.</a></p><p>9. Aggarwal, D., et al., <em>Quantum attacks on Bitcoin, and how to protect against them.</em> arXiv preprint arXiv:1710.10377, 2017.</p><p>10. Stewart, I., et al., <em>Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack.</em> Royal Society open science, 2018. <strong>5</strong>(6): p. 180410.</p><p>11. Fedorov, A.K., E.O. Kiktenko, and A.I. Lvovsky, <em>Quantum computers put blockchain security at risk</em>. 2018, Nature Publishing Group.</p><p>12. Antonopoulos, A., <em>Bitcoin Q&amp;A: Is quantum computing a threat?</em> 2018, YouTube.</p><p>13. Buterin, V. <em>Bitcoin Is Not Quantum-Safe, And How We Can Fix It When Needed</em>. 2013; Available from: <a href="https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150/">https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150/.</a></p><p>14. Hoy, T. and T. Ruffing. <em>[bitcoin-dev] Transition to post-quantum</em>. 2018 12/20/18]; Available from: <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015715.html.">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015715.html.</a></p><p>15. Back, A. 12/20/18]; Available from: <a href="https://twitter.com/adam3us/status/948219461345075201">https://twitter.com/adam3us/status/948219461345075201</a>.</p><p>16. Towns, A. <em>[bitcoin-dev] Schnorr and taproot (etc) upgrade</em>. 2018; Available from: <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-December/016556.html.">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-December/016556.html.</a></p><p>17. Roetteler, M., et al. <em>Quantum resource estimates for computing elliptic curve discrete logarithms</em>. in <em>International Conference on the Theory and Application of Cryptology and Information Security</em>. 2017. Springer.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c69ed2a7c455" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>