Mitigating The Impact Of The Quantum Freeze

Abstract: In this article, we examine various approaches to mitigating the impact of a quantum computer related coin freeze, by allowing the quasi frozen coins to potentially be recovered in a quantum secure way. This can be achieved using two transactions: i. A set-up transaction (which includes a hash commitment) and ii. A recovery transaction. Another option, with just one transaction, involves adding a ZKP to a transaction, proving the spender knows the wallet seed phrase. These systems illustrate that in theory, if we really wanted to, we could construct a quantum freeze such that almost every quasi frozen coin was potentially recoverable. However, the recovery process and softfork protocol upgrades to allow the recovery could be quite complicated and they may also have other downsides, for instance an increased burden on node operators. However, if we are going to do a freeze, in our view, these recovery options could be worth considering.

Overview

This is our third piece in a series on preparing Bitcoin for quantum computers. Our first piece looked at Lamport signatures, while our second piece looked at the advantages of Tapleaf quantum safe spends. In this piece, we look at how we could mitigate the impact of freezing people’s coins, in the event of a freeze of quantum vulnerable coins. In particular methods of mitigating the impact of potential coin loss through various quantum secure recovery schemes.

As the possible options and schemes below illustrate, there is actually a lot that could be done, such that potentially only a tiny number of people could have their coins completely frozen forever. However, there is a lot of complexity and downsides to many of the below freeze mitigation plans.

Commitment Recovery Method

Commitment transactions and OP_Return outputs, could be used to recover funds in a quantum secure way, post freeze. This could apply to a standard P2PKH output, which has avoided address re-use. This setup involves two transactions, with the second transaction directly putting the private key onchain in plain text.

P2PKH transactions that avoid address re-use are already quantum safe, except for the risk of a quantum attacker finding your private key before the spend transaction is confirmed. The below scheme uses a commitment transaction and a 100 block window, to prevent an attacker from being able to do this.

The structure of this recovery method is outlined in the below image:

A step by step guide describing this process is provided below:

1. Put a hash commitment in the OP_Return output of an initial set-up transaction

2. Wait for 100 confirmations

3. Create second transaction, a recovery transaction, that spends the quantum vulnerable coins, with the correct quantum vulnerable signature, such that the transaction is valid according to the old pre-quantum freeze rules

4. In the OP_Return output of the second transaction, include the following fields concatenated together:

• The private key

• The destination address

• The TXID of the set-up transaction

5. The OP_Return hash in the initial transaction, was set-up such that it was the hash output of two of the three fields in the recovery transaction OP_Return output. i.e. SHA256(The private key + The destination address). The TXID of the set-up transaction cannot be included in the commitment hash for obvious reasons, but this is not necessary anyway.

This recovery scheme would require quite a complex protocol upgrade. The protocol upgrade would need to specify that the recovery transaction is only valid, if a valid hash commitment exists in a block with at least 100 confirmations and all the details in the OP_Return output successfully match up and generate the signature to spend the coins. Without completing the recovery steps exactly right, the funds would remain frozen. Since the recovery transaction still contains a working quantum vulnerable signature, the recovery transaction is therefore still valid under the old pre-quantum rules. Therefore, perhaps this upgrade could be a softfork, rather than a hardfork. Using this method, the spender proved they knew the private key before the signature went on the blockchain. This is therefore quantum secure.

This scheme is not perfect and can only be used once. Once you put your private key onchain in plain text, it is obviously known to everyone and anyone can take any remaining funds after 100 blocks. In addition to this, if the recovery transaction is not confirmed within 100 blocks of being broadcast, the funds could be stolen by almost anyone. We are not advocating this exact scheme, we are just describing it as an illustration about how a quantum recovery scheme could be constructed with relatively simple primitives, essentially only using hash functions. On the other hand, upgrading the protocol, building wallets capable of this process and educating users on this recovery, are likely to be quite challenging tasks.

Seed Phrase Commitment Method

One thing worth appreciating is that many people who hold Bitcoin used 12 or 24 words to generate their wallets. For instance, according to BIP-39. To get from the list of ordered words to the wallet seed, a password-based key derivation function is used. This involves the SHA512 hash function and is therefore pretty much quantum safe, as far as we know. Therefore, while a quantum computer could in theory see your public key onchain and then work backwards using quantum magic to get your private key, it could never work all the way backwards to your ordered 12 words.

The idea is that since the step in getting from 12 words to the master private key is quantum safe, you could put those 12 words onchain to spend in a quantum safe way, this would involve two steps, a set-up transaction and a recovery transaction. This method can be used even if the public key is already available onchain, for instance because of address re-use or Taproot outputs.

The structure of this recovery method is outlined in the below image:

A step by step guide describing this process is provided below:

1. Put a hash commitment in the OP_Return output of an initial set-up transaction

2. Wait for 100 confirmations

3. Create second transaction, a recovery transaction, that spends the quantum vulnerable coins, with the correct quantum vulnerable signature, such that the transaction is valid according to the old pre-quantum rules

4. In the OP_Return output of that second transaction, include the following fields concatenated together:

• The ordered 12 word seed phrase

• The wallet derivation path

• The destination address

• The TXID of the set-up transaction

5. The OP_Return hash in the initial transaction, was set-up such that it was the hash output of the three of the four fields in the recovery transaction OP_Return output. i.e. SHA256(The ordered 12 word seed phrase + The derivation path + The destination address). As before the TXID of the set-up transaction cannot be included in the commitment hash.

This scheme has many of the downsides associated with the Commitment Recovery Method outlined above, however adding this recovery method alongside the first one, potentially allows the recovery of even more coins.

Pre QDay Commitment Method

This type of commitment based recovery system can even be used to recover funds from an extremely quantum vulnerable P2PK output, where the public key is on the blockchain as soon as the funds are received and the outputs were created before the seed phrase system was even invented. The methodology is outlined in the diagram below:

The trick here is that the set-up transaction goes onchain prior to QDay. Therefore, we can assume that only the legitimate owner of the funds had the private key at that date. This recovery scheme seems pretty pointless, since unlike the other recovery systems we have discussed above, it requires action to be taken before QDay and if action can be taken prior to QDay, the funds could alternatively have just been swept up to a quantum safe output anyway. Afterall, moving the funds to a quantum safe output is probably far easier than conducting a set-up transaction.

However, this recovery option may be useful to Satoshi Nakamoto (or the apparent dominant miner in 2009). Satoshi could conduct the set-up transaction before QDay. The public would have no idea Satoshi did this, because all we would see is a normal looking transaction, unrelated to Satoshi’s apparent coins, with a OP_Return output of 256 bits. This way Satoshi could maintain plausible deniability as to whether he/she had access to the old coins, while still being able to recover them in a quantum safe way post QDay, if he or she wanted to. Assuming of course Satoshi was interested in something like this.

We could even create a scheme where the 256 bit commitment in the set-up transaction is a Merkle root hash of a giant Merkle tree, with the recovery conditions of thousands of quantum vulnerable outputs. Therefore, just one 256 bit hash commitment in an OP_Return output could be used to recover thousands of outputs with hundreds of thousands of Bitcoin, at a later date. In this scenario the recovery transactions would need to have quite large OP_Return outputs, to produce a path from the Merkle root to a leaf. (Luckily large OP_Return outputs get relayed nowadays).

Zero Knowledge Proof Seed Phrase Method

The above schemes have a critical downside, which is that the recovery process can only be used once for each address. However, there is of course something called a Zero Knowledge Proof (ZKP). A ZKP is when you prove something, while still keeping certain information pertinent to the process secret. For example a ZKP can be used to prove you have a seed phrase used to generate a Bitcoin address and digital signature, while keeping the words secret. While many ZKP proof schemes are quantum vulnerable, some ZKP schemes, such as STARK, are quantum secure.

The ZKP methodology is outlined in the diagram below:

A key advantage here is that when a ZKP is used, the secret seed phrase is not revealed, therefore in this recovery scenario, a ZKP spend can be used multiple times for the same address. There is therefore no need for a set-up transaction and recovery transaction, just one transaction is required. The ZKP approach only works for the seed phrase, not a private key, because the quantum vulnerable signature still needs to go onchain for the transaction to be valid and therefore the private key could be calculated by a quantum computer.

The key advantage of this approach is that Bitcoiners would not need to prepare for QDay by moving coins in advance. The new spend type, with a ZKP added in the OP_Return output, that proves the spender has the seed phrase, can just be considered the new way of spending Bitcoin after QDay. People can continue using their wallet as normal until the freeze, then upgrade their wallets to add the new ZKP output and continue to spend their coins. After QDay, at their own leisure, people could gradually move their coins to new outputs that can be spent by schemes more efficient than ZKP, such as SPHINCS+. But the key here is that there is no need for a panic transition before QDay.

A significant downside here is that not everyone uses seed phrases to generate their wallets. However, seed phrases have been extremely popular for over 10 years now.

Conclusion

These systems illustrate that in theory, if we really wanted to, we could construct a quantum freeze such that almost every quasi frozen coin was potentially recoverable. The multiple recovery options increase the chance of catching more coins. For example the ZKP seed phrase recovery method could be used and when a seed phrase was not used to generate the wallet, the commitment recovery method could be used. This is likely to cover the overwhelming majority of coins. Only in scenarios when both a seed phrase wasn’t used and the public key was exposed when the coins were received, would the coins be potentially totally unrecoverable. The below table lists all the current coins outstanding by the type of Bitcoin output and provides the possible freeze mitigation options which may be applicable.

^{Source: https://dune.com/murchandamus/bitcoins-utxo-set}

These possible post-quantum freeze recovery systems are not without their downsides. For example they may be complicated, involve significant softfork protocol upgrades and be burdensome on node operators, including new possible DoS vulnerabilities. However, if we are going to do a freeze, they may at least be something worth considering. At least it is an interesting thought experiment.

​BitMEX Blog 

Weiterlesen