A freeze-and-restore proposal for dealing with quantum computers

Author: Bitmax Research

Source: https://www.bitmex.com/blog/Mitigating-The-Impact-Of-The-Quantum-Freeze

Abstract : In this paper, we examine several proposed coin freeze schemes to address the challenges of quantum computing. These schemes mitigate the impact of freezing by allowing near-frozen coins to be recovered in a quantum-safe manner. This can be achieved using two transactions: (1) a preparation transaction (containing a hash commitment); and (2) a recovery transaction. Another approach requires only one transaction, requiring the addition of a "zero-knowledge proof (ZKP)" to the transaction to demonstrate that the spender knows the wallet's seed word. These systems suggest that, theoretically, it is possible to construct a freeze scheme that allows recovery of almost all near-frozen wallets. However, the recovery process and the soft fork protocol upgrades that enable recovery could be highly complex and potentially have other drawbacks, such as increasing the burden on node operators. Nevertheless, these recovery options are worth considering if we were to actually freeze coins.

Overview

This is the third article in our series on Bitcoin's resilience against quantum computers. Our first article explored Lamport signatures ( Chinese translation ), and our second explored the benefits of the Tapleaf quantum-safe spending path ( Chinese translation ). In this article, we'll explore how to mitigate the impact of freezing people's quantum-fragile coins in response to quantum computers, specifically by reducing potential coin loss through various quantum-safe recovery schemes.

(Translator's note: In discussions about the impact of quantum computers, it is often proposed to freeze these coins to mitigate the impact on circulation caused by quantum computers stealing or recovering lost coins. Here, "freezing" means disabling spending methods that can be broken by quantum computers, namely simple elliptic curve signatures; "restoration" refers to regaining control of these coins—transferring them to a place with secure spending methods that only their owners can control.)

Commitment - Restoration Method

Commitment transactions and the OP_Return output can be used to recover funds in a quantum-safe manner after freezing them. This can be applied to standard P2PKH outputs (provided that address reuse has been avoided beforehand). This design requires sending two transactions, with the second transaction exposing the private key in plaintext on the blockchain.

P2PKH funds that do not reuse addresses are already immune to quantum long-range attacks. The only risk is that a quantum attacker could reverse engineer your private key before your spending transaction is confirmed in a block. The diagram below uses a commitment transaction and a window of 100 blocks to prevent such an attack.

The structure of the restoration method is also shown in the figure:

We will explain this process step by step:

1. Place an OP_Return output in an initial "preparation transaction".
2. Waiting for confirmation of 100 blocks.
3. Creating a second transaction, also known as a "restoration transaction," costs quantum-fragile coins; it itself requires a correct quantum-fragile signature so that, according to the old rules prior to the quantum freeze, the transaction is valid.
4. The OP_Return output of the second transaction contains the following fields concatenated from the beginning and end:
   • Private key
   • Transfer destination address
   • TXID for preparing the transaction
5. The OP_Return output for preparing a transaction should be the hash value of the two fields in the restored transaction's OP_Return output, namely SHA256(私钥+ 转账目标地址) . The TXID for preparing the transaction cannot be included in this commitment hash value, which is obvious, but unnecessary.

This recovery scheme would require a very complex protocol upgrade. This upgrade would specify that a subsequent recovery transaction is valid only if all details in its OP_Return output completely match the hash commitment of a transaction that has received at least 100 block confirmations; and if the recovery transaction also carries a valid signature. If the recovery process is not completed correctly, the funds remain frozen. Because the recovery transaction still carries a valid quantum fragile signature, it is valid under the rules prior to the quantum freeze. Therefore, this upgrade might be a soft fork (rather than a hard fork). Using this method, the spender proves that they knew the private key before the signature was sent to the blockchain, thus ensuring quantum security.

This approach is imperfect and can only be used once. Once you publish your private key in plaintext on the blockchain, everyone knows it, and anyone can take any remaining funds after waiting 100 blocks. Furthermore, if the recovery transaction fails to be confirmed within 100 blocks after broadcast, the funds can be stolen by almost anyone. In other words, if miners can censor the transaction for 100 blocks, they can steal the funds. We are not advocating for this approach, but rather using it as a demonstration: how to construct a quantum-resistant recovery scheme using relatively simple primitives (essentially, only hash functions are used here). On the other hand, upgrading the protocol, developing wallets capable of handling this process, and informing users about this recovery method can be extremely difficult.

Another issue is address reuse. The public keys of P2PKH outputs might already be exposed on the blockchain, as long as the address hasn't been used for the first time. If this recovery scheme is allowed, a quantum attacker could still steal users' coins as long as address reuse exists, rendering the freeze ineffective. One way to circumvent this is to only allow this recovery method to be applied to addresses that haven't been reused. However, this could place a significant burden on nodes, as they would need to traverse the entire Bitcoin history to check the validity of a recovery transaction. In this case, pruned nodes would be unable to check the validity of recovery transactions.

Seed word commitment method

It's worth noting that many people use 12- or 24-word seed terms to generate wallets and store Bitcoin. For example, they might use the BIP-39 seed term standard. To derive the wallet seed from this ordered term, a password-based key derivation function is needed. This involves the SHA512 hash function, which is therefore quantum-secure (at least as far as we know). Therefore, while a quantum computer could theoretically see your public key on the blockchain and then use quantum magic to reverse-engineer your private key, it simply cannot deduce your ordered 12-word term indefinitely.

Therefore, one idea is that if the process of deriving the master private key from the 12-word phrase is quantum secure, then spending it by publishing the seed word phrase should also be quantum secure. This involves two steps: a "preparation transaction" and a "restoration transaction." This method can even be used in situations where the public key is already exposed on-chain (such as address reuse and Taproot output).

The structure of this restoration method is shown in the following figure:

The steps are as follows:

1. Place an OP_Return output in an initial "preparation transaction".
2. Waiting for confirmation of 100 blocks.
3. Creating a second transaction, also known as a "restoration transaction," costs quantum-fragile coins; it itself requires a correct quantum-fragile signature so that, according to the old rules prior to the quantum freeze, the transaction is valid.
4. The OP_Return output of the second transaction contains the following fields concatenated from the beginning and end:
   • Ordered 12-word seed words
   • Wallet Derivation Path
   • Transfer destination address
   • TXID for preparing the transaction
5. The OP_Return output for preparing a transaction should be the hash values of the three fields in the restored transaction's OP_Return output, namely SHA256(种子词+ 派生路径+ 转账目标地址) . As mentioned earlier, the TXID of the prepared transaction cannot be included.

This approach shares many of the same drawbacks as the aforementioned "commitment-restoration approach," except that allowing this approach outside of the aforementioned options offers the potential to restore more coins.

QDay Pre-Commitment Method

This commitment-based recovery system can even be used to recover P2PK outputs, which are most vulnerable to quantum computers—the script's public key is exposed the moment it receives funding (when the output is created), before even a seed term standard exists. The following diagram illustrates this method:

The peculiarity of this approach lies in the fact that the transaction preparation must be published on the blockchain before QDay (the day quantum computers mature). Therefore, we can assume that only the then-right owner of the funds knows its private key. This recovery scheme sounds somewhat comical because, unlike the recovery systems mentioned earlier, it requires the owner of the funds to take action before QDay; however, if the owner can take action before QDay, the funds can be transferred to a quantum-safe output. After all, transferring funds to a quantum-safe output should be much easier than constructing the transaction preparation.

However, this recovery scheme could be particularly useful to Satoshi Nakamoto (or rather, the one who received the vast majority of the mining rewards in 2009). Nakamoto could construct a preparatory transaction before QDay. People wouldn't know what Nakamoto was doing because we would only see an ordinary transaction, seemingly unrelated to Nakamoto's coins, with only an OP_Return output (carrying 256 bits of data). This would allow Nakamoto to maintain a plausible excuse regarding whether these ancient coins were used, but after QDay, he could retrieve them in a quantum-safe manner, if he so desired. Of course, this assumes Nakamoto was interested in this.

We could even create a scenario where the 256-bit commitment carried in a commitment transaction is the Merkle root hash of a massive Merkle tree, with restoration conditions for thousands of quantum-fragile outputs. Therefore, a single 256-bit hash commitment in an OP_Return output could be used to restore thousands of outputs (potentially worth hundreds or thousands of BTC) later. In this case, the restoration transaction would have a very large OP_Return output because a path from the leaf to the Merkle root needs to be provided. (Fortunately, large OP_Return outputs can now be forwarded across the network). This Merkle root approach could also alleviate blockchain congestion caused by rushing to create commitment transactions before QDay.

Zero-knowledge evidence seed word method

All the above schemes have a fatal flaw: each address can only initiate a restoration operation once. However, there is something called "zero-knowledge proof (ZKP)." Zero-knowledge proofs allow you to prove something while keeping some information about the process confidential. For example, a zero-knowledge proof can be used to prove that you possess a seed word (which generates an address and can generate a corresponding digital signature), but this seed word remains secret. While many ZKP schemes are quantum fragile, some, such as STARK , are quantum safe.

The ZKP method is shown in the following figure:

A key advantage of this approach is that the seed term itself is not exposed when using a zero-knowledge proof. Therefore, the same address can be used multiple times for ZKP expenditure (recovery). This eliminates the need for two transactions (preparation transaction + recovery transaction) and suffices with just one transaction. This ZKP method is only useful for the seed term and cannot be used in the "commitment-recovery scheme" because the quantum-fragile signature still needs to be published on-chain for the transaction to be valid. Therefore, the private key will inevitably be deduced by a quantum computer.

This approach has another advantage: Bitcoiners don't need to move funds before QDay. This new spending method—carrying a zero-knowledge proof in the OP_Return output to demonstrate that the spender owns the seed word—can be used as a new spending method after QDay. People can continue using their wallets normally until they are frozen; then they can upgrade their wallet software, add ZKP outputs, and continue spending their coins. After QDay, people can gradually transfer their funds to outputs that are more efficient at spending than ZKP (such as outputs using SPHINCS+ hash function signatures) as needed. But the key point is: before QDay, you don't need to worry about migration.

Another potential benefit of this ZKP method is improved privacy—publishing a seed term reveals all of a wallet's past transaction history. With ZKP, however, spent outputs may not be associated with recovery funds.

A major drawback of this method is that not everyone uses seed words to generate their own wallet. However, seed word wallets have been extremely popular for over 10 years.

in conclusion

These recovery schemes demonstrate that, theoretically, we could construct a quantum freeze scheme if we truly wanted to, making it possible to recover almost every coin nearing a frozen state. Supporting multiple recovery options increases the probability of coin recovery. For example, the ZKP seed term recovery method works for wallets with a seed term; while if a wallet doesn't have a seed term, the commitment-recovery method can be used. This likely covers the vast majority of coins. Only coins that haven't used a seed term and whose public keys have been exposed are completely unrecoverable. The table below lists the coin denominations currently held by various script types, along with applicable recovery schemes.

Data source: https://dune.com/murchandamus/bitcoins-utxo-set

These potential post-quantum freeze-recovery systems each have their drawbacks. For example, they could be complex, require massive soft fork protocol upgrades, and potentially cause problems for node operators (potentially introducing new DoS vulnerabilities). However, if we were to actually freeze the system, at least these recovery options are genuinely being considered. At the very least, they represent an interesting thought experiment.

(over)