Four Separate Threats Quantum Computing Poses to Bitcoin – Blockchain News, Opinion, TV and Jobs

by Kelce S. Wilson, PhD, MBA, J.D.

In this article, there are four separate threats to Bitcoin by quantum computing identified, their effects are described, and a solution to delay the two most severe threats is proposed.

The threats, in descending order of severity, are:

1. 1. A second preimage attack (forging a hash value) against the SHA-256 becomes computationally feasible, enabling the forgery of entire blocks.
   2. A simplified variation of the first threat uses a second preimage attack to delete transactions.
   3. Determining Bitcoin wallet private keys, which identify the wallet owners, becomes computationally feasible, enabling spending from others’ wallets.
   4. Mining by quantum computing hijacks the growth of the chain, enabling a small number of nodes to hoard new Bitcoin, at the expense of miners using traditional mining hardware, and also to control which blocks and transactions are added or blocked. 

Bitcoin leverages three computationally-intensive operations.  Two are used for security and one is used for controlling the growth of the blockchain in the absence of a permissioning entity (i.e., a central coordinator who decides which blocks to add and when to add them).  The two operations related to security are forging a hash value (i.e., via a second preimage attack) and cracking a digital signature to find the private key (of a key pair) that permits spending by a wallet.

Security is provided by the assumption that, although these two operations are not impossible, they are each so time-consuming that no one should be able to complete them within any relevant time. 

For example, either of these computations should require millions or billions of years or more.  The third operation is used in mining and is designed to be time-consuming, but only up to a point:  The average time for the entire mining community (presumably with each miner starting with a different initial guess) should be measurable in a matter of minutes. 

The four threats described herein result from quantum computing violating traditional assumptions regarding the speed of computing operations and thus the time required for completing certain calculations. 

For example, an experimental computer built by Google was reported to have completed a calculation in only 200 seconds that otherwise “a state-of-the-art classical supercomputer would take approximately 10,000 years.”  This is not an incremental speed-up, but rather requires a fundamental reassessment of security-related assumptions. 

Fortunately, even if (when?) the threats become feasible, the value in implementing them is far below the cost.  Thus, it is unlikely that rational attackers will implement them on a large scale for their obvious purpose.

Rather, if actually manifest, the threats may be implemented with a motivation to either remove Bitcoin as a viable currency option or as a form of economic warfare due to the wealth that may be destroyed.  Unfortunately, none of the threats needs to be actually feasible to undermine Bitcoin.  Mere widespread belief, even if incorrect, may produce a panicked exodus, resulting in a situation similar to how a “run on the bank” may damage an otherwise sufficiently-capitalized bank. 

Timeframe predictions are not provided for the materialization of the first three threats because the computational burdens required may vary by factors of thousands or even millions. 

For example, the time necessary to accomplish a second preimage attack (i.e., forge a hash value) may have a linear dependence on the size of the data item or file for which the hash is being forged.  Data items and files that may be attractive subjects of attempted forgery can vary from about a hundred bits to millions of bits. 

The result may be that even if a second preimage attack becomes feasible for small files or data items, large files may still present computationally infeasible burdens.  Similarly, key pairs may range in security-based upon how they are chosen, drastically varying the computational burden necessary to find the private key from the public key.  Thus, even if easy challenges, such as hashing small files and using weak key pairs, may become vulnerable, harder challenges, such as hashing large files and using only strong key pairs, may still be safe for a period of years. 

Overview

The first two threats are similar, the second being a minor simplification of the first, and so both are related to the same time-consuming computation: forging a hash value via a second preimage attack. 

The four threats, in descending order of severity, are:

1. 1. A second preimage attack against the SHA-256 becomes computationally feasible, enabling the forgery of entire blocks.
   2. A simplified variation of the first threat uses a second preimage attack to delete Bitcoin transactions.
   3. Determining Bitcoin wallet private keys, which identify the wallet owners, becomes computationally feasible, enabling spending from others’ wallets.
   4. Mining by quantum computing hijacks the growth of the chain, enables a small number of nodes to hoard new Bitcoin, at the expense of miners using traditional mining hardware, and additionally to control which blocks and transactions are added or blocked. 

Any of these threats, once becoming feasible, may be implemented in a manner intended to avoid detection, in order to enable long-term surreptitious exploitation, or may instead be openly practised or advertised in a manner that causes catastrophic, rapid abandonment of Bitcoin. 

The loss of trust in the Bitcoin blockchain (the first two threats) will not only destroy Bitcoin value, but will also negatively impact everyone who had been relying on the Bitcoin blockchain, and other similarly-designed blockchains, for establishing the trustworthiness of documents. 

This is because a forged block (an entire block or a block with a single altered transaction) may be promulgated, permitting double-spending of value that had been the subject of an earlier transaction.  The corresponding value will disappear from the earlier recipient’s holdings within the copies of the forged block, and although the majority of the blocks dispersed among the community may have the correct set of transactions. 

The forgery may remain undetected because the forged block will produce the proper hash value until a double-spending attempt is made.  When that occurs and the rift is detected by different nodes treating the transaction differently, even if it is possible to quickly sort out which block is correct, the resolution may be disruptive and a significant number of Bitcoin wallet owners may exit Bitcoin out of fear. 

Additionally, newly-generated or altered documents may be inserted into the blockchain via forged blocks that purport to prove the documents are much older than they truly are (or had different contents).  Once it becomes known that such falsified proof is possible, legitimate document proof, using the Bitcoin blockchain, may no longer be trusted.  A solution is proposed below that, if implemented in a timely manner, may delay the first two threats, thereby prolonging the trustworthiness of the Bitcoin and similar blockchains. 

The ability of one person to surreptitiously spend value from another’s wallet may also undercut confidence in Bitcoin’s security.  One possible result may be that some people will move value out of Bitcoin, causing a potential loss in total Bitcoin value, when this threat materializes – or when enough people believe it to be the case (even if untrue). 

Similarly, the belief that mining advantages provided by quantum computing are being exploited may rapidly shrink the mining community, as miners with traditional hardware may view the continued operation as unprofitable.  Fortunately, however, the cost of quantum computing capability may be so high that use for Bitcoin mining, stealing from Bitcoin wallets, and erasing transactions are such unprofitable uses that these attacks will fail to materialize. 

The threats are compared according to six factors:

1. Whether trust in the underlying blockchain is damaged.
2. Whether already-received cryptocurrency may be lost when actual transactions are replaced, in at least some distributed copies of the ledger, with other transactions (such as by someone merely transferring value back and forth among two of their own wallets).
3. The blockchain purports to prove an untrue condition (i.e., that a document existed at an earlier time than is true).
4.  Whether one person may spend value from another’s wallet.
5. Whether mining is impacted to provide one or more nodes with the ability to solve the mining challenge considerably faster than the majority of other mining nodes; and 
6. Growth of the blockchain is controlled by a small number of nodes.  The proposed solution, however, only addresses the first factor, which corresponds to the first two threats. 

1. Second Preimage Attacks Enable Forged Blocks 

A second preimage attack occurs when someone (such as an attacker), who is given a first digital file, creates a different digital file that has the same hash value.  A hash value is also known as a message digest.  A collision occurs when two digital files, having different content, have the same hash value. 

If someone is given a hash value as a target and then creates a new file that produces the hash value, this is called a preimage attack.  One scenario for a second preimage attack occurs when someone starts with a block of the blockchain, makes the first alteration to that block (which results in the block’s hash value being different), and then makes a second alteration so that the altered block will again produce the original hash value.  This is basically forcing a collision between the original block and the forged block. 

All hash values are theoretically vulnerable to collisions whenever the digital files being hashed are longer than the message digest (i.e., the files have more bits than does the hash value). 

Consider an exercise in which someone hashes every possible different file that has 256 bits.  Setting aside the extraordinary length of time this would take, we would hope that the SHA-256 hash function (which is what is used by Bitcoin and some other blockchains) would not have a collision.  That is, we would hope that as every possible combination of 256 bits is hashed, none of the hash values is repeated.  This is unlikely to occur, but if it did, it would be the best case of the SHA-256 having a minimum likelihood of a collision.  However, at the end of this exercise, if there had not been a collision, every possible different hash value will have been produced. 

When the next file is hashed, maybe one that is 255 or 257 bits, at least one hash value would necessarily have been repeated (either with this next file or with two files from the earlier exercise).  This result is simply unavoidable because there aren’t any more different hash values to use.  If the exercise is repeated with all possible files that are 260 bits long, each file will have an average of 15 collisions – each with a different file.  Many files that are large enough to be of significance and worth protecting by a blockchain will have a large number of possible collisions. 

Although the SHA-256 hash function does have collisions, it is currently trusted because the amount of time that would be required to intentionally create a collision (via a second preimage attack) is so long that it is exceptionally unlikely to occur.  The security is therefore provided by assuming that even the fastest computer will be too slow – an assumption that appears increasingly uncertain with the large speed advances that may be occurring with quantum computing in the near future. 

The threat scenario is that an attacker has spent some Bitcoin with another person at some point in the past, but wants that value back.  The attacker has two wallets and contrives a transaction in which value is transferred from one wallet to the other, essentially costing the attacker no Bitcoin value. 

The attacker then takes a copy of the block in which the Bitcoin was spent with the other person, and substitutes the new transaction in the ledger in place of (and therefore deleting) the prior transaction.  However, this first threat scenario is more complex than merely trying to cram the new transaction into a second preimage attack.  That approach is unlikely to be successful, as the Bitcoin transaction records are too terse and so do not provide a set of sacrificial bits to manipulate when attempting to go back to the original hash value. 

Bitcoin uses a cryptographic structure known as a Merkle tree that combines hash values of the transactions.  The hash values of the transactions are called Merkle tree leaves.  Leaves are combined and the combination is hashed to produce a Merkle tree branch.  Obviously, there are fewer first-tier branches than leaves.  Branches are combined and hashed, reducing the number of branches in each tier.  This process repeats until there is only a single hash value remaining, which is called the Merkle tree root.  This root is placed into the block header. 

For mining, a special nonce value is found by hashing only the header, which is relatively small compared with the entire block.  The nonce is found by a trial-and-error process of hashing the header and changing the nonce until a hash value is found that starts with a specified number of zeroes. 

In this threat scenario, the Merkel root will be different after changing one of the leaves (i.e., the leaf corresponding to the substitute transaction).  So a new nonce will need to be found.  There are some other minor complicating factors necessary to forge a new header, but addressing these will be manageable for anyone who has the computational capacity to successfully perform a second preimage attack against the SHA-256. 

With this type of attack, forging a new header, it is possible to also affect other data within the block.  Any generic data can also be altered.  This means that a forged block can contain data that did not exist at the time the original block was created and yet still fit within the blockchain at the proper place – being trusted just as if it were legitimate, until the forged data or the other compensating changes are identified. 

However, if the forger (attacker) is able to put the forged block into distribution where it is copied by other nodes, the Bitcoin community will then have conflicting ledgers.  One ledger will have the original transaction and the other will have the contrived replacement transaction. 

The ledger with the contrived transaction will result in the Bitcoin value reverting to the attacker and being taken (stolen) from the other person who had received it, earlier.  Although such an attack is highly unlikely to be profitable, because the cost of building and operating a quantum computer is far beyond the amount of value exchanged in Bitcoin transactions, there are nevertheless still reasons for forging blocks when it becomes feasible. 

Some people have been putting small documents (data sets) or hashes of larger documents into the Bitcoin blockchain in order to establish proof of some potentially important information indicated by that document. 

There may be a scenario in which the value of obtaining purported proof for an untrue condition may provide motivation.  However, the most likely motivation may be disruption: eliminating Bitcoin as a viable currency option, destroying wealth that had been built up within Bitcoin, or destroying the value of having document integrity provable as a result of having been entered into the Bitcoin blockchain.  The disruption motivation may easily arise within the context of economic warfare. 

The comparison factors for this threat are as follows: 

1. trust in the underlying blockchain is damaged, possibly catastrophically.
2. already-received cryptocurrency may be lost by the recipient when a transaction is replaced. 
3. the blockchain purports to prove an untrue condition.
4. this attack alone does not enable one person to spend value directly from another’s wallet.
5. mining is not directly impacted (although it would be an easier attack).
6. growth of the blockchain is not controlled by a small number of parties, with this attack alone. 

2. Second Preimage Attacks Permit Transaction Deletion (Merkle Tree Leaf) 

This second threat is a simpler, easier version of the block forgery described above because only a single Merkle tree branch is affected.  Upon substituting the contrived transaction for the original one, the bits of the other Merkle tree leaf are manipulated in an attempted second preimage attack against the first-tier (outermost) branch.

If this is successful, then the Merkle tree root will not change.  This, however, leaves a clue to the forgery: the manipulated transaction, which might be relied upon by someone else.  The manipulated bits are unlikely to correspond to a hash value and so will provide clear evidence of the forgery – when it is detected. 

Note that it is not guaranteed that a collision will exist when only the number of bits with which the original transaction’s leaf is paired is used for manipulation.  In some situations, the neighbouring branch’s hash value (which is combined at the next tier of the Merkle tree) will also need to be manipulated, further growing the evidence of forgery and likelihood of detection.  This type of attack is less stealthy but slightly easier than the first one described above. 

The comparison factors for this threat are as follows: 

1. 1. Trust in the underlying blockchain is damaged, possibly catastrophically; 
   2. Already-received cryptocurrency may be lost by the recipient when a transaction is replaced; 
   3. The blockchain purports to prove an untrue condition; 
   4. This attack alone does not enable one person to spend value directly from another’s wallet; 
   5. Mining is not directly impacted (although it would be an easier attack); and 
   6. Growth of the blockchain is not controlled by a small number of parties, with this attack alone.

Second Preimage Attacks Enable Forged Blocks

3. DETERMINING WALLET PRIVATE KEYS ENABLES THEFT OF BITCOIN VALUE 

Cracking digital wallet security can be accomplished by finding a wallet owner’s private key from their public key.  This computational burden is considerably less than the computational burden of performing a second preimage attack against the SHA-256.  If a mathematical solution, which is being investigated by world-class mathematicians, is not found, the fallback is a trial-and-error attempt.  The trial-and-error attempt is theoretically possible, but security is provided by assuming that it will simply take too long.  It is likely that quantum computing will break this assumption prior to making a second preimage attack against the SHA-256 feasible. 

The secrecy of a wallet’s private key is the only thing that enables one person to exclusively spend the Bitcoin value associated with the wallet.  Anyone who knows the key can spend from the wallet.  So the ability for an attacker to determine anyone else’s private key is likely to be catastrophic to the value of Bitcoin, as wallet owners attempt to cash out before their wallets; values are also stolen. 

Additionally, miners may begin abandoning Bitcoin in large numbers, if they perceive their mining efforts will be in jeopardy.  It is worth mentioning again that this threat does not actually need to materialize if a sufficient number of people believe (even incorrectly) that it has and then act on that belief. 

The comparion factors for this threat are as follows: 

1. Trust in the underlying blockchain is not yet damaged.
2. Already-received cryptocurrency is not necessarily lost by the recipient with this attack alone. 
3. The blockchain does not purport to prove an untrue condition.
4. This attack enables one person to spend value directly from another’s wallet.
5. Mining is not directly impacted (although it would be an easier attack).
6. Growth of the blockchain is not controlled by a small number of parties, with this attack alone.

4. MINING ADVANTAGES ARE EXPLOITED BY QUANTUM COMPUTING 

This final threat is likely to be the first one that is feasible because there is no computational speed threshold that must be attained.  Rather, the computational speed advantage of some experimental computing systems over traditional hardware computing solutions, such as those used for Bitcoin mining, already exists. 

Fortunately, the value of Bitcoin mining is so low, in view of the cost of producing a quantum computer, that economic realities, rather than technology, will likely be the primary neutralization of this threat.  However, given the growth of some government-funded large mining farms, smaller-scale and independent miners are likely to win a decreasing share of new Bitcoin value and exit the mining community.

As this continues, mining power will be concentrated in a smaller and smaller set of miners – the very people who are the enforcers of blockchain integrity.  This concentration of mining power may be a greater threat than mining advantages being exploited by quantum computing.  However, the quantum computing threat, even if impractical, is nevertheless possible.

The comparison factors for this threat are as follows: 

1. Trust in the underlying blockchain is not yet damaged; 
2. Already-received cryptocurrency is not necessarily lost by the recipient with this attack alone; 
3. The blockchain does not purport to prove an untrue condition; 
4. The attack alone does not enable one person to spend value directly from another’s wallet; 
5. Mining is directly impacted, becoming unfair for the vast majority of miners; and 
6. Growth of the blockchain is controlled by a small number of parties. 

5. PROPOSED SOLUTION TO THE FIRST TWO THREATS 

A simple solution can harden Bitcoin and other similarly-designed blockchains:  A parallel blockchain is generated, in which the original Bitcoin blocks form the cores of the new blocks, and the new blocks are chained using a pair of hash values (from two different hash functions) that each represents the entire prior block, rather than just the header.

The use of two different hash functions means that a successful preimage attack against only just one of the hash functions at a time will not work.  Both hash functions must simultaneously produce the prior hash values. 

This effectively turns a linear search into a two-dimensional search, significantly driving up the computational burden.  Additionally, by hashing the entire block (which may be greater than a Megabyte) rather than just a header that is a fraction of that size, will require each trial to take much longer, providing a multiplicative effect on the computational burden.