Topic: Lost coins vulnerable to theft in the future? (Read 579 times)

That is the purpose of ZKP, isn't it? You provide a proof that you know some information without actually revealing it (and so nobody can duplicate it if you are the only one who knows the hash).

Correct.

The public key with the largest amounts of coins stored in a P2PK output that I am aware of is:

This corresponds to the following uncompressed address: https://blockchair.com/bitcoin/address/1PTYXwamXXgQoAhDbmUf98rY2Pg1pYXhin

Note that all the dust outputs which follow are P2PKH outputs paying to the address, not the public key. Only the very first output is P2PK, meaning 3,233.17 BTC are locked behind that public key.

So the default was that the mining reward of 50 BTC was sent to a different public key each time?
It would favor the scenario of "gradual breaking" the keys rather than "grab all at once".

I wonder how something like this could work considering the fact that any information provided based on hashes that could reproduce the keys could be duplicated by the other parties that are trying to steal the same coins.

The same as any other output script but instead of using hash of public key you use the same public key. It could be reused or the wallet could produce a new pubkey for every new payment (which was the default).

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

---

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?

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.

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.

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.

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.

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.

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.

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

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".

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. 

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.

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.

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.

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.)


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.

---

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.

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.

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:


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.

I see that you like my idea.


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!

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.

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").

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.

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?