Quote from: o_e_l_e_o on June 13, 2022, 02:16:31 PM

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.

Quote from: death_wish on June 08, 2022, 05:46:55 PM

Quote from: o_e_l_e_o on June 08, 2022, 11:58:14 AM

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. [...]

Quote from: death_wish on June 10, 2022, 03:30:49 PM

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!