Lost coins vulnerable to theft in the future?

[Adam_xx]

Let's say there are even 2-3 mil. coins that are lost (nobody has private keys anymore).

Note that there are addresses with revealed public keys that do have a balance and aren't P2PK outputs, such as 1P5ZEDWTKTFGxQjZphgWPQUpe554WKDfHQ. Those are in the same danger as well if their owners don't move them to a quantum-safe address.

Yeah, I know, as stated in my post.
Also P2TR outputs are in the same danger.
So maybe altogether 2-3 mil. is accurate.

The damage (of course if that happens at all) depends on the speed of breaking the keys.

[pooya87]

My logic is that if something is considered vulnerable then it must be removed from the Bitcoin protocol. For example if OP_CAT has a weakness then it is removed from the code entirely even if someone had used it in a script. Which is exactly what happened, this OP code and a handful of others were completely removed.
Similarly if OP_CHECKSIG becomes vulnerable then it must be removed from the code not still remain there and let people choose to use it or not!

[Adam_xx]

It can only be seen from this thread that opinions on this are very different (relevant points on both sides).
For this reason, I think that forming a new consensus would not be reached and the default situation (letting the coins be stolen) is the most likely outcome.
Or the situation is resolved by two separate forks and market valuation.

[o_e_l_e_o]

So maybe altogether 2-3 mil. is accurate.

It's closer to 4 million vulnerable coins, according to this study: https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html

It was done around 2 years ago, but you can see from the graph halfway down the page that the number has fluctuated around the 4 million mark for ~8 years, so I suspect it is still around the same. P2PK outputs are essentially constant and unchanging, while reused P2PKH addresses have slowly fallen as reused P2WPKH addresses have slowly increased. And of course we can now add in P2TR outputs as well.

My logic is that if something is considered vulnerable then it must be removed from the Bitcoin protocol. For example if OP_CAT has a weakness then it is removed from the code entirely even if someone had used it in a script. Which is exactly what happened, this OP code and a handful of others were completely removed.
Similarly if OP_CHECKSIG becomes vulnerable then it must be removed from the code not still remain there and let people choose to use it or not!

This is the most convincing argument for the opposite position to mine, I think. But it is worth pointing out that nobody's coins were made unspendable when OP_CAT was removed, compared to the millions of coins which would be made unspendable if OP_CHECKSIG is removed.

[Adam_xx]

So maybe altogether 2-3 mil. is accurate.

It's closer to 4 million vulnerable coins, according to this study: https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html

It was done around 2 years ago, but you can see from the graph halfway down the page that the number has fluctuated around the 4 million mark for ~8 years, so I suspect it is still around the same. P2PK outputs are essentially constant and unchanging, while reused P2PKH addresses have slowly fallen as reused P2WPKH addresses have slowly increased. And of course we can now add in P2TR outputs as well.

4 million currently vulnerable but people would migrate.
Not all 4 million from the study are coins with lost private keys.
If it is e.g. 2 million coins being stolen in small chunks for 10 years, the effect on price would not be so significant.
What do you think?

[NotATether]

If it is e.g. 2 million coins being stolen in small chunks for 10 years, the effect on price would not be so significant.

Coins are not going to be stolen in small chunks like that, they're either going to be stolen in quick succession because commercial quantum computers can in fact break SHA256, or they are not going to be stolen at all, because as it turns out, quantum computers cannot break SHA256 yet.

There are only two possible outcomes.

[Adam_xx]

If it is e.g. 2 million coins being stolen in small chunks for 10 years, the effect on price would not be so significant.

Coins are not going to be stolen in small chunks like that, they're either going to be stolen in quick succession because commercial quantum computers can in fact break SHA256, or they are not going to be stolen at all, because as it turns out, quantum computers cannot break SHA256 yet.

There are only two possible outcomes.

SHA-256 is not quantum endangered as far as I understand the topic (just a little speedup with Grover's algorithm).
We are talking here about ECC vulnerabilities (Shor's algorithm/lattice attacks).
And breaking each key can be quite a long process (= it is not the winner takes it all in "quick succession").

[o_e_l_e_o]

Coins are not going to be stolen in small chunks like that, they're either going to be stolen in quick succession because commercial quantum computers can in fact break SHA256

ECDLP rather than SHA256 as Adam_xx has pointed out, but regardless, I don't think they would be stolen in quick succession.

It will not be the case that ECDLP goes from "unsolvable" to "trivial to break" in a single step. If ECDLP does become broken, then the first time someone breaks it it will be because they ran a quantum computer for days or even weeks to break it, meaning they can at most empty a single address. Then they will have to start again for another address, and then another, and then another, and there are tens of thousands of vulnerable addresses to be attacked.

Quantum computers will get faster and more efficient as time goes on, so eventually it may well be possible to crack an address in a few seconds or minutes, but that certainly won't be the case to begin with.

[death_wish]

As I mentioned in another thread, I would only support locking coins if there was some way for the real owner to prove ownership and unlock them again, such as by providing a zero knowledge proof that they own the seed phrase which generated the relevant private keys. But this does not solve the problem of truly lost coins or early coins in P2PK addresses.

I see that you like my idea.

The only option is to introduce a new quantum resistant address type and  give everybody plenty of time to move across to it (in the order of several years). What happens with coins that don't move becomes the real issue here - do we either decide as a community to permanently lock them* so they can never be moved again, or do we just ignore them and let them be stolen by whoever manages to first and then re-enter the general circulation. I am in favor of the latter option.

*Perhaps the best option, but one which would need a lot more work to be viable, would be to lock all these coins but provide a mechanism to unlock them if the real owner can provide some quantum-resistant proof that they are indeed the real owner. An example would be if I could prove that I owned the seed phrase which generated a given wallet or address. Such a mechanism (if developed) would only solve this issue for seed phrase generated addresses though, and there are a lot of vulnerable coins in P2PK address and other non HD wallets that this does not address.

In theory, this could be done without revealing the seed, using a zero-knowledge proof:  In theory, any operation that can be performed by a computer can have its correct performance proved in zero knowledge. [...]

To illustrate:  For publicly known Hash160 image H of secret preimage secp256k1_pubkey, you can prove in zero knowledge that you ran a program that outputs true for the following:

Code: (Pseudocode)

RIPEMD160(SHA256(secp256k1_pubkey)) == H

Verifying the proof does not require any knowledge of secp256k1_pubkey.

Neat trick, eh?  That’s the toy version; it simply proves that you know the unrevealed public key.  Building this into a system that permits secure spending of funds would necessarily be more complicated; [...]

Mulling this, I am quite confident that a practical post-quantum ZK proof emergency salvage system could be designed not based on seed derivations, but for all UTXOs that require unrevealed public keys.  This includes P2SH/P2WSH.  The only coins that could not be safely salvaged are those in addresses with known public keys:  Reused P2PKH/P2WPKH, all P2TR, reused P2SH/P2WSH multisig, etc.  (About those, I absolutely agree with you that coins vulnerable to theft cannot be locked or seized; the idea flies in the face of all that Bitcoin means!)

Following the above-quoted posts, I was working on refining this idea, thinking towards writing this up—for the forum and/or bitcoin-dev, and also for proper documentation of prior art.  (I am afraid that my idea, or some aspects of it may potentially constitute patentable methods; as a precaution, I want to create solid public documentation of prior art, with strong evidence of invention date.)  I have been interrupted and distracted for the past week or so, but I should get back to this soon.

Meanwhile, I wish to reassure Adam_xx and any others worried about quantum computers.  With a nod to Clarke:  Any sufficiently advanced cryptography is indistinguishable from magic.  My zero-knowledge proof coin-salvaging system can be done.  The question is if it will be done in Bitcoin; and given that this is open-source software, I really oughtn’t just sit around idly dreaming about it.


A few little scratch-notes:

AFAIK, zk-STARKS (not SNARKs) are post-quantum for soundness.  (zk-SNARKs may arguably (?) be sound for zero-knowledgeness in a post-quantum world; but IIUC, they will lack soundness against forgery by a quantum computer.)

zk-STARKs are rarely used in practice, because their proof sizes are three orders of magnitude larger than zk-SNARK proofs—far too big for ordinary “send some money” types of blockchain transactions!  Ethereum already tolerates that cost for one of their major L2 systems, which amortizes the cost of an on-chain zk-STARK verification across large numbers of L2 transactions.  For onetime emergency salvage in Bitcoin, the transaction size cost would be worthwhile—perhaps even with a fee rebate supported by miners, who have the long-term incentive to mine emergency transactions for free or cheap to help keep Bitcoin alive through a hypothetical Quantum Apocalypse.

I have significant concerns about how computationally expensive this would be.  Although anything that can be computed theoretically can have its computation proved in zero knowledge, in practice, protocols based on zero-knowledge proofs need to choose carefully what they will run inside the ZK proving arithmetic circuit.  Some even design their own cryptographic primitives such as hashes, etc.; designing primitives that run efficiently inside a ZK arithmetic circuit seems to be a very narrow subspeciality in the field of cryptography.  Some of the primitives that Bitcoin uses are notoriously bad for this.  Again, however, I anticipate that a onetime emergency salvage system could probably consider that cost less painful than letting Bitcoin be destroyed by a hypothetical Quantum Apocalypse.

I also remind any readers that quantum computers capable of cracking Bitcoin do not currently exist, and there is no proof that they are possible in practice.  It is good to think about these things now, but I do not want to feed FUD.  IMO, the threat of a potential Quantum Apocalypse is much, much worse for PGP, Tor, the HTTPS in your browser, and anything else that could be retrospectively decrypted.  That could be catastrophic—and there is no way to fix it with some sort of a salvage system!

[o_e_l_e_o]

I see that you like my idea.

Well, it's a good idea if implemented safely, but I won't let you take all the credit, since I've discussed such a thing in the past:

I could provide a zero knowledge proof that I am in possession of the extended private key or the seed phrase which was used to derive that private key.

On a wider scale, although it would be great to have such a thing implemented, and it would be a prerequisite to me being comfortable with some coins being "locked" by consensus, it would only serve to make a small difference in the event that quantum computers can break the ECDLP. Assuming that the majority of addresses which are being actively reused would migrate to quantum-proof addresses, and that the 1.73 million BTC in P2PK addresses will be stolen regardless, then this system would only serve to protect coins in non-reused non-P2PK addresses which are inaccessible to the owner. We cannot place an accurate figure on this group, but I believe it to be significantly smaller than all the estimates bandied about by people who simply assume that any coin which hasn't moved in >5 years (for example) has been lost, since (for example) such a category includes the majority of my coins, which are absolutely not lost.

It's certainly worth doing for the individuals it would protect, but it will make little difference I think to the overall impact on bitcoin.

[Adam_xx]

Mulling this, I am quite confident that a practical post-quantum ZK proof emergency salvage system could be designed not based on seed derivations, but for all UTXOs that require unrevealed public keys.  This includes P2SH/P2WSH.  The only coins that could not be safely salvaged are those in addresses with known public keys:  Reused P2PKH/P2WPKH, all P2TR, reused P2SH/P2WSH multisig, etc.  (About those, I absolutely agree with you that coins vulnerable to theft cannot be locked or seized; the idea flies in the face of all that Bitcoin means!)

But what about all those other UTXOs (lost reused P2PKH/P2WPKH, lost P2TR, lost reused P2SH/P2WSH multisig)? I think that is the main dilemma here. I would quote Pieter Wuille here: "If a QC can ever spend lost ECC-locked coins, I believe it's game over for Bitcoin. How can an asset maintain value if an attacker has the ability to flood the market with the significant portion of the entire supply?".

I don't like the idea of some coins being locked by consensus, however, Pieter has a point that the economical impact of flooding the market with all these coins could be unsurvivable.

[death_wish]

I see that you like my idea.

Well, it's a good idea if implemented safely, but I won't let you take all the credit, since I've discussed such a thing in the past:

I could provide a zero knowledge proof that I am in possession of the extended private key or the seed phrase which was used to derive that private key.

Thanks for the link.  I hadn’t seen that.

Why do you focus on the extended private key or seed phrase?  If a ZK system were implemented that ran Bitcoin consensus rules (including Bitcoin script, and everything else) inside a proving circuit, then people could simply publish proofs that they had validated their own transactions spending the coins.  The transaction inputs and outputs would not be hidden, so there is no need to worry about double-spends (the reason for Zcash’s nullifier system).  IMO, it would be a terrific engineering effort to get this working right; and computational costs may be not insignificant.  But in theory, it can surely be done; and in practice, an emergency would probably justify the costs.

(Bonus, another thing I have been wanting to investigate and post about:  Perhaps the engineering effort could also be repurposed to make a succinct version of Bitcoin, for light clients to attain full-node security simply by validating a proof that someone else had validated the entire blockchain up to the current tip.  I do not know if this is feasible in practice.  Mina had to invent their own cryptographic primitives, for efficiency reasons.)

On a wider scale, although it would be great to have such a thing implemented, and it would be a prerequisite to me being comfortable with some coins being "locked" by consensus, it would only serve to make a small difference in the event that quantum computers can break the ECDLP. Assuming that the majority of addresses which are being actively reused would migrate to quantum-proof addresses, and that the 1.73 million BTC in P2PK addresses will be stolen regardless, then this system would only serve to protect coins in non-reused non-P2PK addresses which are inaccessible to the owner. We cannot place an accurate figure on this group, but I believe it to be significantly smaller than all the estimates bandied about by people who simply assume that any coin which hasn't moved in >5 years (for example) has been lost, since (for example) such a category includes the majority of my coins, which are absolutely not lost.

It's certainly worth doing for the individuals it would protect, but it will make little difference I think to the overall impact on bitcoin.

One of the great things about Bitcoin is that people are never under time pressure to move their coins.  You can go into a coma or get shipwrecked on an island, and reclaim your bitcoins when you are available to claim them.

Anyone who deals with altcoins eventually has the experience, “You must upgrade/do this claim procedure/exchange old tokens for new tokens” with a deadline to avoid losing your money.  Not so much in the more credible altcoins, but it is disturbingly common in others.  It is horrible, and it is all the more reason to appreciate Bitcoin.

With the type of system that I describe, most people who follow best practices for avoiding address reuse could upgrade and move coins at their leisure.  If you so choose, you could leave your >5-year-old coins untouched for another 30 years—then publish a proof to spend them.

But what about all those other UTXOs (lost reused P2PKH/P2WPKH, lost P2TR, lost reused P2SH/P2WSH multisig)? I think that is the main dilemma here. I would quote Pieter Wuille here: "If a QC can ever spend lost ECC-locked coins, I believe it's game over for Bitcoin. How can an asset maintain value if an attacker has the ability to flood the market with the significant portion of the entire supply?".

I don't like the idea of some coins being locked by consensus, however, Pieter has a point that the economical impact of flooding the market with all these coins could be unsurvivable.

That could surely cause an extreme bear market.  How much worse of a bear market could be caused by calling into question Bitcoin’s fundamental trustworthiness?

A major part of Bitcoin’s fundamental value is that you can trust that nobody will ever change the rules to seize your coins or divert their value.  (This sometimes happens in alts—e.g., Juno, or Terra.)  And as o_e_l_e_o has noted, there is no way to know if a coin has been lost.  “Lost coins” statistics are guesses, and probably bad ones.

[Adam_xx]

It is difficult for me to imagine that a consensus on this would be somehow reached. I have been asking this theoretical question for a couple of months now and the community is divided almost like 50/50. Even the developers have different opinions (Pieter Wuille/Adam Back would probably prefer locking the coins, Jimmy Song favors letting them be stolen, etc.). So if the situation occurs anytime in the future there will be a huge controversy. If attacking the keys is slow the result would be probably "just" a bear market. If it is fast and huge amount of coins will flood the market I am afraid it would really endanger the existence of Bitcoin.

[o_e_l_e_o]

Why do you focus on the extended private key or seed phrase?  If a ZK system were implemented that ran Bitcoin consensus rules (including Bitcoin script, and everything else) inside a proving circuit, then people could simply publish proofs that they had validated their own transactions spending the coins.

Perhaps I misunderstand, but in the scenario in which two people both have access to the relevant private key (the true owner and an attacker who has reversed ECDLP and obtained the private key), how does providing a ZK validation of a transaction solve the problem, given that either party could produce such a proof? Surely the true owner needs to provide a ZK proof that they can derive the private key from some parent key/seed/number/etc., which the attacker would be unable to do. Please correct me if I'm wrong.

It is difficult for me to imagine that a consensus on this would be somehow reached. I have been asking this theoretical question for a couple of months now and the community is divided almost like 50/50.

I'm sure a consensus will be reached when it becomes worth reaching. Such a scenario is decades away, while bitcoin itself is only 13 years old. There are far more pressing things to discuss and develop than to work on some quantum computing solutions which will almost certainly be hugely outdated by the time they are relevant.

[Kakmakr]

I think when an exploit happens in a centralized system.... a centralized "authority" will make decisions on behalf of the affected users or customers... but in a decentralized monetary system.... consensus is required for changes to happen. So I reckon different solutions (forks) will be offered and the owners of those coins, will have to abide by what the consensus would be.

This will obviously have to happen very quickly, because an exploit like this will affect a lot of other people ...that have control over their tokens. (The previous Bitcoin forks was very hostile ......so I reckon a decision to do this, will cause a lot of troubles in the community)  

I will suggest that a redundancy plan goes into a vote before this happens.... and then when it happens, it can quickly be implemented before the breach can be exploited too much. 

[pooya87]

Another factor that would affect the decision whether to lock the coins or not would be the total amount that would be affected by the vulnerability. It is not just P2PK outputs, it is all the reused addresses that have revealed their public key and still have a balance and all the new outputs that start using public keys again like P2TR outputs or any other output type that contains public key like P2MS. For example if it affects a quarter of bitcoin total supply (5-6 million BTC) then it is a serious issue to let them be "stolen".

[o_e_l_e_o]

So I reckon different solutions (forks) will be offered and the owners of those coins, will have to abide by what the consensus would be.

I think that would be one of the worst possible outcomes, similar to what happened with ETH and ETC. Some people decide that the principles of bitcoin should be protected and therefore we do nothing to these coins, while some people decide that these coins should be locked to protect the markets. Not only would there be no consensus on which path to take, there would also be no consensus as to which fork gets to keep the BTC ticker and which becomes an altcoin. Not that I actually care about Ethereum, but as far as I am concerned ETC is the true Ethereum and ETH is the fork in which a small group of developers decided to unilaterally reverse someone's transactions.

This will obviously have to happen very quickly

I really don't think so. It will be decades before (if?) a quantum computer is capable of realistically threatening the ECDLP. It will be years more before it can actually steal coins from a single address. It will be years more before they are capable of breaking an address in matter of hours instead of matter of days. We have plenty of time to reach a consensus when it becomes apparent that we should, but there are plenty of other more pressing things to work on first.

It is not just P2PK outputs, it is all the reused addresses that have revealed their public key and still have a balance and all the new outputs that start using public keys again like P2TR outputs or any other output type that contains public key like P2MS.

I think in general people are far less careless with their wallets and their private keys than they were 10-12 years ago. Addresses which are actively being reused just now as well as anyone starting to use P2TR are highly likely to still have access to these addresses when the time comes and be able to migrate their coins to whatever new quantum proof address type we end up with.

a quarter of bitcoin total supply (5-6 billion BTC)

Ooft. That fiat hyperinflation has finally come for bitcoin too!

[Adam_xx]

Another factor that would affect the decision whether to lock the coins or not would be the total amount that would be affected by the vulnerability. It is not just P2PK outputs, it is all the reused addresses that have revealed their public key and still have a balance and all the new outputs that start using public keys again like P2TR outputs or any other output type that contains public key like P2MS. For example if it affects a quarter of bitcoin total supply (5-6 billion BTC) then it is a serious issue to let them be "stolen".

There is probably a solution for reused addresses if they are a part of HD wallets so the problem might be "just" with very old P2PK and reused addresses from non-HD wallets. That is currently at least 2 mil. coins but not all of them are lost. The breaking process will probably not be so fast as o_e_l_e_o pointed out, at least in the beginning (and if ever, of course). The economical effect could really be similar to mining. If we look at exchange inflows for the last couple of days the amount of coins changing hands is huge (and still survivable). If BTC can survive such scenario without need to lock the coins (or lock but introduce a way to claim them by ZKP) it would be good.

There is a quote from Adam Back's tweet:

also I think (fairly new thought) that HD keys that were reused could be soft-forked to require a Zero Knowledge proof of knowledge of the chain code and master even if the coin private key was public information. (and soft-fork made not be spendable with direct ECDSA.).

-----

Of course there is a problem that chain code / master is sometimes known by the wallet providers, etc. and also who will distinguish which coin is a part of HD wallets/which not (and thus which coins can be locked for ECC signing). And the issue with P2PK and non-HD coins still persists. But at the same time I suppose this claiming process will not be used so much because every rational person would move their coins way long before they become vulnerable. But the option to move coins even when ECDSA is no longer supported would be nice.

Or ECDSA/Schnorr will be phased-out much sooner before it is dangerous to use (e.g. a couple of decades) and when we get to the situation of a quantum computer attacking the old coins the consensus for locking the old outputs will be much easier to reach.

Or we just let all the coins like they are. And the market will absorb the multi-year lasting inflow of stolen coins.

[o_e_l_e_o]

Of course there is a problem that chain code / master is sometimes known by the wallet providers, etc.

If your master private key is already known by your wallet provider, then your coins are already unsafe and could be stolen at any time. Quantum computing doesn't change this.

and also who will distinguish which coin is a part of HD wallets/which not (and thus which coins can be locked for ECC signing).

This is impossible to do. You either lock them all and accept that some of them will remain locked forever even if the true owner returns, or you lock none of them.

[Adam_xx]

That is why i think only these two scenarios are realistically possible:

Or ECDSA/Schnorr will be phased-out much sooner before it is dangerous to use (e.g. a couple of decades) and when we get to the situation of a quantum computer attacking the old coins the consensus for locking the old outputs will be much easier to reach.

Or we just let all the coins like they are. And the market will absorb the multi-year lasting inflow of stolen coins.

Also what comes into my mind at the moment - it is true that a huge amount of coins are sitting in P2PK outputs in chunks of 50 BTC coins, however, it an attacker manages to get a private key from one of the early public keys (on which there are these chunks of 50 BTC coins) he would be able to steal a big portion of coins at once.

But I am not sure how P2PK worked. Has the public key changed every time for early wallets?