An Addition To The Bitcoin Wiki Page On Quantum Computing
And Mosca’s Theorem Of Risk Determination Applied To Blockchain.
If you have read part 3 of the series “Quantum resistant blockchain and cryptocurrency, the full analysis in seven parts.”, you could decide to skip the first part of this article and go straight to the header:
“To make a complete and realistic estimate of the expected timeline for upgrading and migration we use Mosca’s theorem of risk determination.”
Because I feel the Bitcoin Wiki page on quantum computing is missing some crucial information, I decided to add some balance.
QC attacks.
Timeline/ Plausibility.
If you want some information about the advancement and expectations in quantum computing development, it’s not a bad idea to take a look at some statements of the companies that do the actual development. Reading those, we see a huge speedup in development is expected.
- “It should be about 5 years to 1000 qubit chips with superconducting technology. It should be about 10 years to million qubit chips.” (Jim Clarke, Intels Quantum hardware director. (Full interview here)
- “And a million-physical-qubit system, whose general computing applications are still difficult to even fathom? It’s conceivable, says Neven, “on the inside of 10 years.” (That is Harmut Neven of Google’s quantum computing effort)
- IBM believes quantum computers will be mainstream in 5 years. (Meaning outside of research labs, but not necessarily in living rooms of the average Joe. And no amount of qubits mentioned though)
- “Five years from now, we will have a commercial quantum computer,” Says Microsoft’s Holmdahl.
- And those are just the commercial companies. [The Pentagon sees quantum computing as the next arms race. China is about to pump $10 Billion in a research center. They won’t be open about their developments as Google etc. It’s not a bad idea to start looking for solutions and new opportunities in blockchain.
- This paper estimates ECDSA could be at risk as soon as 2027.
Besides the development of quantum computers themselves, we shouldn’t forget about other advancements that will bring the breaking of current signature schemes closer. There are algorithms developed that are less sensitive to error rates. And existing algorithms are reinvented and/ or improved and new ways of deployment are discovered. For example this optimized version of Shor’s algorithm for prime factoring. That factors 2048 bit RSA integers in 8 hours using 20 million noisy qubits. The previous method was about 100 times slower. This shows the importance of these kinds of developments since these also advances a critical timeline.
Reviewing the above doesn’t mean that ECDSA will be broken in a few years, but reading the statement on the BitcoinWikipage that ECDSA keys will quite likely be safe until at least 2030–2040, kind of hints at a certain degree of bias in the writing of that Wiki article. As it is written now, it implies that any action or discussion on the subject is unnecessary at this point in time.
But if we look at the statements on the heaviest weight entities on security, we see that all of them are stating that the critical date is impossible to be predicted. It is impossible to exclude and dismiss a sudden advancement in development and neither is it possible to guarantee decades slow development. At the same time is acknowledged by all that the realization of this critical level in quantum computing would have catastrophic implications and the time in which the realization of a quantum resistant upgrade is fulfilled is of such uncertain length, that action should not be postponed.
The National Academy of Sciences (NAS) 2018:
The NAS, also in their report on quantum computing:
National Security Agency (NSA) 2015:
- NSA announced that it is planning to transition “in the not too distant future” (statement of 2015) to a new cipher suite that is resistant to quantum attacks.
- “Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy.”
NSA advised:
Federal Register (The daily journal of the United States Government) 2016:
And as you know, ECDSA is used by BTC as a signature scheme. ECDSA is a FIPS 186–4 standard: NIST; ECDSA FIPS 186–4.
2016: The National Institute of Standards and Technology (NIST)
The reason they advise starting to seriously prioritize the development, standardization, and deployment of post-quantum cryptography is threefold:
1. The hazard and the security disaster it would create is of such significance that one can’t afford to take any gambles.
2. Public and universal analysis of a possible critical date can only be done while reviewing public information. And because there are huge interests at stake (commercially and strategically), not all developments will be shared publicly. So, assessing the risk, you should assume the possibility of a blind spot. This means that in assessing the risk, you must seriously consider the idea that an estimate should be adjusted to an earlier timeline if you would have had all the information at your disposal in your analysis of the development curve. Adding to that blindspot, there are developments in other fields that can bring a critical date closer. To give an example: a new algorithm called Variational Quantum Factoring is being developed and looks quite promising. “ The advantage of this new approach is that it is much less sensitive to error, does not require massive error correction, and consumes far fewer resources than would be needed with Shor’s algorithm. As such, it may be more amenable for use with the current NISQ (Noisy Intermediate Scale Quantum) computers that will be available in the near and medium term.” See for more information here.
3. An implementation period of new cryptography takes time. While the needed timeframe depends on the system, an analysis of this timeframe should be made. If this isn’t carefully done, there is no way to make a total risk analysis where you reflect the expected timeframe against the expected time the risk will materialize.
If We Apply This To Blockchain And Cryptocurrency:
1. A passive attitude could, if the timing is wrong, similarly result in a disaster where coins lose close to 100% of value due to security risks and possible hacks.
Bitcoin Wiki acknowledges this.
2. The same uncertainty on developments applies, which means a suitable margin should be taken in timeline estimation.
Considering the information above, where companies predict huge speed up in development and the named organizations mention the uncertainty of ay timeline, the point of view from BitcoinWiki that ECDSA keys are safe until at least 2030–2040 could be argued.
3. A serious estimation of the implementation period should be made.
Aside from any discussion within what period the threat might materialize, if you want to be able to make any sort of risk assessment, then we absolutely need an estimation on the implementation period. This is missing in the bitcoin wiki page.
To even begin to look at estimating this period, we should have more clarity on the method of upgrading BTC (or any other existing blockchain). BitcoinWiki mentions a soft fork and that everyone should send their BTC to the new available address type. This is presented as an easy fix, but leaves out the hard parts:
Even though they do acknowledge there is no plug and play replacement for current signature schemes, the emphasis on the undertaking of implementation of any of the existing quantum resistant algorithms is missing. This is an important time factor.
Besides the preparation period, which will take time (the process of researching the options, redesigning, proposal of different options), three important issues are not mentioned:
1. The need for consensus. Even though consensus will be easily reached on the result: a quantum resistant Bitcoin, the choice in method (the type of signature and method of implementation) will result in several options and might still be cause for the difficulty to reach consensus. Even though Lamport signatures are mentioned now as a favorite, this doesn’t mean there is a guarantee on consensus, since there is no information on how this will affect the performance and how mining(rigs) will need to adjust. Another important factor to reach consensus is the moment of implementation. Many might feel an early implementation will be premature. This means the risk grows that time might be short once the risk is imminent. The following two factors will show that an additional period after implementation might be crucial.
2. As acknowledged in the bitcoin wiki page, the human factor plays a part in the upgrade of the blockchain: after the blockchain upgraded, all coins must be migrated to new quantum resistant addresses by users personally. The emphasize that the failure of a part of the users to migrate their coins, will result in a risk in value decline due to possible hacks is missing though. The bigger the percentage of coins on an old vulnerable address, the bigger the security risk. The MtGox hack of 2011 caused an immediate drop of 49% and a 5 months drop of 93%. That was 2k stolen BTC (0.04% circ suppl back then) hacked from an exchange. Not BTC itself. In this case, it will be the blockchain that is hacked. The migrated coins will be safe in number, but not in value, since a hack of other coins will result in a negative market reaction as any blockchain hack will. It’s an important point because this means that for you as a user, to secure your valuables, you depend on the action of all other users. Which is at this point of time estimated to be around 7 million users. Which includes about 700.000 addresses that hold more than 1 Bitcoin. This means that, as a user, security-wise, you depend on the need for an enormous group of other people to pay attention to developments, understand the necessity, understand the need for personal action after BTC itself has already upgraded to quantum resistance, behave responsibly, proactive and fast.
3. What's totally missing is the issue with lost addresses. (Users who lost keys can’t access the coins anymore, which means that those coins can never be moved to quantum resistant addresses and can therefore never be protected and will stay vulnerable to quantum hacks forever). Combining the human factor and the issue with lost addresses means we can conclude that it is impossible for existing blockchains to upgrade and successfully protect 100% of their current circulating supply due to the fact that not all coins will be migrated to safe quantum resistant addresses. Technically you could burn those coins, but since it is impossible to determine with certainty that stagnant coins are lost coins and not long term holders, burning would be a risk since it could mean that peoples actual funds would be burnt with it. This either means that a huge % will be vulnerable forever, or that risk needs to be taken to burn those coins. If the decision would be taken to burn any leftover coins, legally a fixed period would need to be set as a deadline, which would add time to the possibly already tight timeline. This period should be long enough to be sustainable in court if any coins might be burned that should not have been burned and the owners sue the devs responsible.
If we take into account that 36% of the circulating supply is on addresses with exposed public keys, and that about 20% of BTC is on lost addresses (Second source here), another research came to the same conclusion: Chainalysis concluded that between 17% (low estimate) and 23% (high estimate) of BTC was lost at the time of publishing.
Those lost addresses include the Satoshi addresses (with P2PK UTXOs: these are the older addresses from the period that public keys were not hashed, but published in full.
We can only conclude that this is a huge % of BTC that is vulnerable to a hack and that that is a huge elephant in the room that BitcoinWiki chooses to ignore.
So those are the factors we need to take into account to make any form of a serious estimate on the timeframe we should think about when we want BTC to go from vulnerable to quantum hacks, to fully quantum secure.
To make a complete and realistic estimate of the expected timeline for upgrading and migration we use Mosca’s theorem of risk determination. Now for blockchain, the theorem can be adjusted as follows:
v = selection of signature scheme, proposal for implementation. (Different signature schemes are available. There is no plug and play scheme to replace current schemes. And there are several solutions imaginable to handle the bigger signatures.)
w = reaching consensus and upgrading the nodes. (Since phase “v” quite likely results in multiple options, the consensus is not a given and might be a trajectory like we seen with the SegWit fork. Besides the need to chose between different options, there should be decided when the upgrade will be effective. This is a second subject that will cause debate.)
x = migration period. (After an upgrade of the signature scheme, all the coins are still stored on the old, vulnerable public-private key addresses. The upgrade simply gives the users the tools to create a new, quantum resistant address and migrate their coins to the safety of that address. Without migration, there is no quantum resistance. Due to the decentralized nature of blockchain, this can only be done by the users themselves, since only they have the private key and thus only they have access to the coins.)
y = stagnant phase to minimize the risk of burning live funds. (This last phase is advised since for most existing blockchains a considerable amount of their circulating supply is lost and can never be migrated to quantum resistant addresses. A solution should be found for these so-called lost addresses. The only solution to this problem would be to burn them. Otherwise, they will be hanging like Damocles’ sword of uncertainty over the value of the blockchain forever. Due to the fact that none of the users are registered and thus cannot be contacted, you can not determine which addresses are really lost and which are simply longtime holders. If we take another look at the results of the research by Chainalysis, who concluded that between 17% (low estimate) and 23% (high estimate) of BTC was lost at the time of publishing, we see a difference of about 1 million BTC in the high and low estimate range. The big discrepancy between the high and low estimate (about 1 million BTC), shows the issues there will be to determine with certainty what stagnant addresses are lost and what are long term holders. This is important to notice for anyone who proposes to just burn the lost addresses in any neglect able period of time after upgrading to a quantum resistant signature scheme. Their phase should be a serious period of time. And then still, if at a certain point in time the decision is made to burn any leftover coins, you will risk burning peoples live funds. This makes the last phase controversial if not impossible to fulfill without trading one risk for the other.
z = The time we have until a quantum computer of a critical level has materialized
q = is the margin we should deduct from z as a safe margin to compensate the blind spot caused by the fact that any assessment of the development curve of quantum computers is based on incomplete information. Additionally, q accounts for the fact that developments on other levels like algorithms improvements can contribute to a quicker reach of the moment a quantum computer can break the cryptography in question.
V, w, x, y, z, and q are all undetermined. V, w, x, y will need to be done for every single blockchain that is serious about risk determination personally. Since for none of these periods there is a substantiated period of time known, no serious risk determination can be done.
If you have read part six of “Quantum resistant blockchain and cryptocurrency, the full analysis in seven parts.”, you could decide to skip the rest of this article.
The bitcoin wiki page makes the following statement: “Bitcoin already has some built-in quantum resistance.”
This is not correct. Hashed public keys are no protection: It is often said that not reusing addresses would make BTC quantum resistant, which is not true, fully explained in part six of this series.
Tl;dr:
As soon as a transaction is made, its public key is revealed. Once a transaction is made, it isn’t instantly confirmed and added to the blockchain. This means that in the timeframe and route between the transaction is sent from your device and the confirmation on the blockchain, the transaction can be hijacked. BitcoinWiki acknowledges this, but at the same time claims it still is some sort of quantum resistance due to the fact it would take a very fast quantum computer to hijack the transaction in the ten minutes block time timeframe.
That’s fine but obviously doesn’t give you any form of protection if that speed happens to be reached.
But more importantly, the window of opportunity is bigger than the mentioned ten minutes. Some attacks vectors are not mentioned:
When a transaction is sent to the nodes it can be MITM-ed. Close enough to the source transactions can be prevented to reach any node altogether and work with the obtained public key from there. Also when it waits in the pool the pubkey can be obtained before the tx is confirmed and a forged tx can be prioritized using high fees. At rush hours, this means that this can be an extensive prolongation of the window of opportunity. And the third window of opportunity: as also mentioned in the BitcoinWiki page, transactions can be hijacked during block time as explained in this paper see page 7, point 3.
But one of the things that are most overlooked, is that even if it was any form of protection, there is a huge percentage of BTC that is on published public keys. Which means those can be hacked anyway, which means, as Andrew Poelstra mentions “you have retained all these tokens that are worthless.” So no, it’s an absolute smokescreen to say that bitcoin has any form of built-in quantum resistance.
Lately, Pieter Wuille, BTC dev, acknowledged this on twitter, here and here.
This is also acknowledged by Andrew Poelstra in this interview. (40:00 and further) He even goes as far as explaining how public keys are exposed in several other ways besides sending transactions to such an extent that “basically all the public keys are exposed.” “If everybody else bitcoins are lost, then […] you have retained all these tokens that are worthless.” Which is an acknowledgment of the risk of value decline due to hacks of the percentage of BTC that is not on addresses with hashed public keys?
44:00 “It was never intended as quantum protection. It doesn’t function as quantum protection. There’s sort of this idea out there that it does, but it doesn’t. And even if it did, by the way, it’s very unclear how you would spend your coins again, because you have to reveal the public key to spend the coins.”
“Revealing your public key inside a zero-knowledge proof, we know how to do that but these are over a 100Kb, so then you would need to attach a 100Kb to each tx. Try to fit that in the blockchain. It’s not realistic.”
So that should be the end of that misconception.
