This spent several months gathering feedback from the mailing list and from other advisors. This is hopefully polished enough to submit upstream.
Let me know if you have any questions or feedback, and of course feel free to submit suggestions.
Thank you for your time.
41+|-
42+! Address type !! Vulnerable !! Prefix !! Example
43+|-
44+| P2PK || Yes || 04 || 0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf2342c858ee
45+|-
46+| P2PKH || No || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
It might be worth discussing the conditions under which P2PKH is vulnerable in more detail. While the Deloitte report covers this, this table leaves the impression that P2PKH is safe.
0| P2PKH || No (trusted miner) || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
1| P2PKH (reused) || No || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
28+
29+Mining may one day be vulnerable to disruption by very advanced quantum computers making use of Grover's algorithm. However, Grover's [https://arxiv.org/pdf/1902.02332 scales very poorly] compared to Shor's, requiring 10^40 quantum operations in comparison to 10^8 for running Shor's over ECC. It's for this reason that the primary threat to Bitcoin by quantum computers is to its signature algorithm and not Proof of Work, hence the focus on a new address format.
30+
31+The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack.
32+
33+Ordinarily, when a transaction is signed, the public key can be recovered from the signature. This makes a transaction submitted to the mempool vulnerable to quantum attack until it's mined. One way to mitigate this is to submit the transaction directly to a mining pool, which bypasses the mempool. This process is known as an out-of-band transaction. The mining pool must be trusted not to reveal the key to attackers.
It’s also been added to the new table for scenarios for revealed public keys on bitcoin.
24+
25+=== Motivation ===
26+
27+This proposal aims to improve the quantum resistance of bitcoin's signature security should the Discrete Logarithm Problem (DLP) which secures Elliptic Curve Cryptography (ECC) no longer prove to be computationally hard, likely through quantum advantage by Cryptographically-Relevant Quantum Computers (CRQCs). [https://arxiv.org/pdf/quant-ph/0301141 A variant of Shor's algorithm] is believed to be capable of deriving the private key from a public key exponentially faster than classical means. The application of this variant of Shor's algorithm is herein referred to as quantum key decryption. Note that doubling the public key length, such as with a hypothetical secp512k1 curve, would only make deriving the private key twice as hard. The computational complexity of this is investigated further in the paper, [https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specifications-on-reaching ''The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime''].
28+
29+Mining may one day be vulnerable to disruption by very advanced quantum computers making use of Grover's algorithm. However, Grover's [https://arxiv.org/pdf/1902.02332 scales very poorly] compared to Shor's, requiring 10^40 quantum operations in comparison to 10^8 for running Shor's over ECC. It's for this reason that the primary threat to Bitcoin by quantum computers is to its signature algorithm and not Proof of Work, hence the focus on a new address format.
I completely agree with your claim that:
It’s for this reason that the primary threat to Bitcoin by quantum computers is to its signature algorithm and not Proof of Work, hence the focus on a new address format.
The math in the footnote is for finding SHA256 preimages, but the text and cited article discusses Bitcoin mining/POW which is only a partial preimage, e.g. find SHA256 output with 75 zeros in front. These partial preimages should be not as hard as finding a full SHA256 preimage.
The quantum safety of Bitcoin POW is a an open question. Is a quantum computer than can do the POW significantly faster than a classic miner an attack or simply better mining technology? Are there other quantum attacks on Bitcoin mining?
I would frame this as symmetric cryptography in Bitcoin, such as preimages in the transactions Merkle tree, rather than mining.
log2_work message from Bitcoin Core in the latest block… Let me know if that’s not right.
Log2 work is the total work from the genesis block all the way to that current block not a measure of work of that block alone.
Bitcoin PoW per hash is ~700 Exahash/second. That roughly $log2(700 * 10^{18} )=2^{68.2}$ per second and $2^{74.5}$ per block. 75 zero bits would more the accurate current number.
There is a big difference between the cost of preimages on SHA256 and HASH160 with a quadratic reduction: SHA256 as you point out is $2^{128} \approx 10^{40}$ but HASH160 used in P2PKH is $2^{80} \approx 10^{24}$. Still much larger than ECC, but I wanted to call this out because it is unlikely we will ever build a computer classical or quantum that can do $2^{128}$ within the next 100 years whereas Bitcoin currently does $2^{80}$ every 30 minutes.
If I didn’t misunderstand “Applying Grover’s Algorithm to Hash Functions” the cost of a groover preimage attack on a n-bit hash function where you are trying to want to find 1 preimage out of a set of k preimages is $\sqrt{2^{n-\log2{(k)}}}$. Let’s say we are looking for any preimage of a P2PKH output. As of Sept 29 2024 there are 53,102,992 P2PKH in Bitcoin’s UTXO set. This gets us an attack cost of $\sqrt{2^{160-25.66}}=2^{67.17} \approx 10^{20}$.
All of this still supports your argument that the current pressing need in Bitcoin is ECC. It worth having tighter bounds, so we know when we are in danger for the symmetric side of Bitcoin.
I’ve published some more updates you can see here:
Also, is P2WPKH not also as vulnerable as P2PKH? I think they both use HASH160, do they not?
Yes P2WPKH, P2PKH, P2SH all use HASH160 (20 Byte) whereas P2WSH uses SHA256 (32 Byte).
Thanks for the updates and making the changes. My main concern is that if precise numbers are going to be used for Bitcoin and Groovers I want to avoid a situation where the numbers are not representative of the threat. I suspect many people in Bitcoin will use this BIP to educate themselves on quantum attacks. I’ll write up a longer comment during my lunch break today.
I realize by pointing out the nuances I’ve accidentally caused this section to grow into two large paragraphs, when really all you are trying to do make is the reasonable point that quantum attacks on ECC signatures should be the most immediate concern.
Here is my attempt to get the same point across but without having to get into the details:
The primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its uses of ECC (Ecliptic Curve Cryptography) used in Bitcoin’s signatures and Taproot commitments]. This is because Shor’s algorithm enables a CRQC to break the cryptographic assumptions of ECC in roughly 10^8 ≈ 2^26) quantum operations. While a QRQC could use Grover’s algorithm to gain a quadratic speed up on brute force attacks on the hash functions used in Bitcoin, a significantly more power quantum computer is needed for these attacks to meaningfully impact Bitcoin. For instance a preimage attack on HASH160 using Grover’s algorithm would require at least 10^24 ≈ 2^80 quantum operations.
It does make sense to discuss Grover’s algorithm w.r.t. multi-target preimage attacks against P2SH and P2PKH when discussing the security of address types against a QRQC.
230+To help implementors understand updates to this BIP, we keep a list of substantial changes.
231+
232+* 2024-06: High level rough draft
233+* 2024-07: Additional algorithms in PQC table
234+* 2024-08: Add FALCON signatures, update to use NIST standard terminology, add public key sizes.
235+* 2024-09: Additional detail on P2QS. Deprecate P2QR. Postpone SQIsign. Add details on quitness.
A few non-urgent nits regarding the changelog:
(See https://keepachangelog.com and https://www.gnu.org/prep/standards/html_node/Style-of-Change-Logs)
29+Mining may one day be vulnerable to disruption by very advanced quantum computers making use of [https://en.wikipedia.org/wiki/Grover's_algorithm Grover's algorithm]. However, Grover's [https://arxiv.org/pdf/1902.02332 scales very poorly] compared to Shor's. Grover's potentially requires roughly 10^40 quantum operations in comparison to 10^8 for running Shor's over ECC, should no optimization for partial preimages be needed. Partial preimage optimization may lower the difficulty to find a block than the full 256-bit preimage (say, for a number with 75 zero bits in front).<ref>See [https://quantumcomputing.stackexchange.com/a/12847 Sam Jaques on Bitcoin mining].</ref> Regardless of such optimizations, the primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its signature algorithm] and not necessarily Proof of Work, hence the focus on a new address format. Additionally, should quantum mining demonstrate quantum advantage over ASIC miners, miners will transition to operating CRQCs instead.<ref>Grover's algorithm is a quadratic speedup, so instead of 2^256 tries it takes about 2^128 calls to the oracle (which is about 10^38 operations) to get a 256 bit preimage. The number of gates would be some multiple of that number. That's roughly how we get the correct order of magnitude, Mosca did a more finegrained calculation and land ballpark in similar large numbers. The number is so large, it's unclear the exact calculation with all the prefactors so far, contrary to ECC, which is roughly 10^8 operations, including the constant factors. A talk by [https://sam-jaques.appspot.com/papers Sam Jaques] gave some estimate of the size of the machine that would be necessary for Grover to attack hashes and it was a small astronomical body.</ref>
30+
31+It is worth mentioning that any addresses using RIPEMD160 / HASH160 could also be vulnerable to Grover's algorithm.<ref>There is a big difference between the cost of preimages on SHA256 and HASH160 with a quadratic reduction:
32+SHA256 is 2^128 ≈ 10^40 but HASH160 used in P2PKH and P2WPKH is 2^80 ≈ 10^24 quantum operations. This is much larger than ECC, and while it is unlikely a classical or quantum computer that can perform 2^128 within the next 100 years, Bitcoin currently does 2^80 classical operations every 30 minutes. Additionally, with Grover's, [https://bitcoin.stackexchange.com/a/115849/139611 a black box function could sidestep Shor's entirely, and SHA-256, providing the private key itself to a P2PKH or P2SH address.]</ref>
33+
34+The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now closer to 20%.
Another vulnerability estimation in early 2019: 5M-10M bitcoin
typo fix
12+
13+== Introduction ==
14+
15+=== Abstract ===
16+
17+This document proposes a new SegWit output type, with spending rules based initially-- but not solely-- upon FALCON signatures. (For more on why, see the Rationale and Security sections.) A constraint is that no hard fork or increase in block size is necessary. This document is inspired by [https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki BIP-341], which introduced the design of the P2TR (Taproot) address type using Schnorr signatures.
Some of this might fit better in later parts of this document.
How about something like this:
0This document proposes the introduction of a new output type based on FALCON signatures. This approach for adding a post-quantum secure output type does not require a hard fork or block size increase.
The inspiration by BIP 341 could be mentioned in the acknowledgments, and Rationale and Security being the relevant sections to understand the “Why” seem natural.
24+
25+=== Motivation ===
26+
27+This proposal aims to improve the quantum resistance of bitcoin's signature security should the Discrete Logarithm Problem (DLP) which secures Elliptic Curve Cryptography (ECC) no longer prove to be computationally hard, likely through quantum advantage by Cryptographically-Relevant Quantum Computers (CRQCs). [https://arxiv.org/pdf/quant-ph/0301141 A variant of Shor's algorithm] is believed to be capable of deriving the private key from a public key exponentially faster than classical means. The application of this variant of Shor's algorithm is herein referred to as quantum key decryption. Note that doubling the public key length, such as with a hypothetical secp512k1 curve, would only make deriving the private key twice as hard. The computational complexity of this is investigated further in the paper, [https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specifications-on-reaching ''The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime''].
28+
29+The primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its breaking of ECC used in signatures and Taproot commitments], hence the focus on a new address format. This is because Shor's algorithm enables a CRQC to break the cryptographic assumptions of ECC in roughly 10^8 quantum operations. While a CRQC could use [https://en.wikipedia.org/wiki/Grover's_algorithm Grover's algorithm] to gain a quadratic speed up on brute force attacks on the hash functions used in Bitcoin, a significantly more powerful CRQC is needed for these attacks to meaningfully impact Bitcoin. For instance, a preimage attack on HASH160<ref>used by P2PKH, P2SH, and P2WPKH addresses, though not P2WSH because it uses 256-bit hashes</ref> using Grover's algorithm would require at least 10^24 quantum operations. As for Grover's application to mining, see [https://quantumcomputing.stackexchange.com/a/12847 Sam Jaques post on this].
0The primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its breaking of ECC used in signatures and Taproot commitments], hence the focus on a new address format. This is because Shor's algorithm enables a CRQC to break the cryptographic assumptions of ECC in roughly 10^8 quantum operations. While a CRQC could use [https://en.wikipedia.org/wiki/Grover's_algorithm Grover's algorithm] to gain a quadratic speed up on brute force attacks on the hash functions used in Bitcoin, a significantly more powerful CRQC is needed for these attacks to meaningfully impact Bitcoin. For instance, a preimage attack on HASH160<ref>used by P2PKH, P2SH, and P2WPKH addresses, though not P2WSH because it uses 256-bit hashes</ref> using Grover's algorithm would require at least 10^24 quantum operations. As for Grover's application to mining, see [https://quantumcomputing.stackexchange.com/a/12847 Sam Jaques’ post on this].
26+
27+This proposal aims to improve the quantum resistance of bitcoin's signature security should the Discrete Logarithm Problem (DLP) which secures Elliptic Curve Cryptography (ECC) no longer prove to be computationally hard, likely through quantum advantage by Cryptographically-Relevant Quantum Computers (CRQCs). [https://arxiv.org/pdf/quant-ph/0301141 A variant of Shor's algorithm] is believed to be capable of deriving the private key from a public key exponentially faster than classical means. The application of this variant of Shor's algorithm is herein referred to as quantum key decryption. Note that doubling the public key length, such as with a hypothetical secp512k1 curve, would only make deriving the private key twice as hard. The computational complexity of this is investigated further in the paper, [https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specifications-on-reaching ''The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime''].
28+
29+The primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its breaking of ECC used in signatures and Taproot commitments], hence the focus on a new address format. This is because Shor's algorithm enables a CRQC to break the cryptographic assumptions of ECC in roughly 10^8 quantum operations. While a CRQC could use [https://en.wikipedia.org/wiki/Grover's_algorithm Grover's algorithm] to gain a quadratic speed up on brute force attacks on the hash functions used in Bitcoin, a significantly more powerful CRQC is needed for these attacks to meaningfully impact Bitcoin. For instance, a preimage attack on HASH160<ref>used by P2PKH, P2SH, and P2WPKH addresses, though not P2WSH because it uses 256-bit hashes</ref> using Grover's algorithm would require at least 10^24 quantum operations. As for Grover's application to mining, see [https://quantumcomputing.stackexchange.com/a/12847 Sam Jaques post on this].
30+
31+The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now closer to 20%. Additionally, cryptographer Peter Wuille estimates even more might be vulnerable, for the reasons provided [https://x.com/pwuille/status/1108085284862713856 here].
0The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now closer to 20%. Additionally, cryptographer Pieter Wuille [https://x.com/pwuille/status/1108085284862713856 reasons] even more might be vulnerable.
30+
31+The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now closer to 20%. Additionally, cryptographer Peter Wuille estimates even more might be vulnerable, for the reasons provided [https://x.com/pwuille/status/1108085284862713856 here].
32+
33+Ordinarily, when a transaction is signed, the public key can be recovered from the signature. This makes a transaction submitted to the mempool vulnerable to quantum attack until it's mined. One way to mitigate this is to submit the transaction directly to a mining pool, which bypasses the mempool. This process is known as an out-of-band transaction. The mining pool must be trusted not to reveal the transaction public key to attackers.
34+
35+Not having public keys exposed on-chain is an important step for quantum security. Otherwise funds would need to be spent to new addresses on a regular basis in order to prevent the possibility of a "long-range CRQC attack" recovering the key behind high value addresses. A long-range quantum attack can be considered one performed with chain data, such as that from a used address or one encoded in a spend script. A "short-range quantum attack" would be one performed on keys in the mempool, which is seen as impractical given transaction throughput and block time. As the value being sent increases, so too should the fee in order to commit the transaction to the chain as soon as possible. This makes useless the public key revealed by spending a UTXO, so long as it is never reused.
28+
29+The primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its breaking of ECC used in signatures and Taproot commitments], hence the focus on a new address format. This is because Shor's algorithm enables a CRQC to break the cryptographic assumptions of ECC in roughly 10^8 quantum operations. While a CRQC could use [https://en.wikipedia.org/wiki/Grover's_algorithm Grover's algorithm] to gain a quadratic speed up on brute force attacks on the hash functions used in Bitcoin, a significantly more powerful CRQC is needed for these attacks to meaningfully impact Bitcoin. For instance, a preimage attack on HASH160<ref>used by P2PKH, P2SH, and P2WPKH addresses, though not P2WSH because it uses 256-bit hashes</ref> using Grover's algorithm would require at least 10^24 quantum operations. As for Grover's application to mining, see [https://quantumcomputing.stackexchange.com/a/12847 Sam Jaques post on this].
30+
31+The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now closer to 20%. Additionally, cryptographer Peter Wuille estimates even more might be vulnerable, for the reasons provided [https://x.com/pwuille/status/1108085284862713856 here].
32+
33+Ordinarily, when a transaction is signed, the public key can be recovered from the signature. This makes a transaction submitted to the mempool vulnerable to quantum attack until it's mined. One way to mitigate this is to submit the transaction directly to a mining pool, which bypasses the mempool. This process is known as an out-of-band transaction. The mining pool must be trusted not to reveal the transaction public key to attackers.
32+
33+Ordinarily, when a transaction is signed, the public key can be recovered from the signature. This makes a transaction submitted to the mempool vulnerable to quantum attack until it's mined. One way to mitigate this is to submit the transaction directly to a mining pool, which bypasses the mempool. This process is known as an out-of-band transaction. The mining pool must be trusted not to reveal the transaction public key to attackers.
34+
35+Not having public keys exposed on-chain is an important step for quantum security. Otherwise funds would need to be spent to new addresses on a regular basis in order to prevent the possibility of a "long-range CRQC attack" recovering the key behind high value addresses. A long-range quantum attack can be considered one performed with chain data, such as that from a used address or one encoded in a spend script. A "short-range quantum attack" would be one performed on keys in the mempool, which is seen as impractical given transaction throughput and block time. As the value being sent increases, so too should the fee in order to commit the transaction to the chain as soon as possible. This makes useless the public key revealed by spending a UTXO, so long as it is never reused.
36+
37+It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) address type that relies on a Post-Quantum Cryptographic (PQC) signature algorithm. This new address type protects transactions submitted to the mempool and helps preserve the free market by reducing the need for private, out-of-band mempool transactions.
34+
35+Not having public keys exposed on-chain is an important step for quantum security. Otherwise funds would need to be spent to new addresses on a regular basis in order to prevent the possibility of a "long-range CRQC attack" recovering the key behind high value addresses. A long-range quantum attack can be considered one performed with chain data, such as that from a used address or one encoded in a spend script. A "short-range quantum attack" would be one performed on keys in the mempool, which is seen as impractical given transaction throughput and block time. As the value being sent increases, so too should the fee in order to commit the transaction to the chain as soon as possible. This makes useless the public key revealed by spending a UTXO, so long as it is never reused.
36+
37+It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) address type that relies on a Post-Quantum Cryptographic (PQC) signature algorithm. This new address type protects transactions submitted to the mempool and helps preserve the free market by reducing the need for private, out-of-band mempool transactions.
38+
39+The following table is non-exhaustive but intended to inform the average bitcoin user whether their bitcoin is vulnerable to quantum attack.
This feels like it is oversimplifying a bit. This seems to show output types that are generally vulnerable to long-range attacks. Additionally, any reused hash-based addresses are also vulnerable to long-range attacks, and all of the output types below are vulnerable to short-range attacks.
Edit: I see, it is clarified briefly later. Perhaps it would make sense to reorder a bit here.
0The following table is non-exhaustive but intended to inform the average bitcoin user whether their bitcoin is vulnerable to a long-range quantum attack.
63+|-
64+! Scenario !! Type of attack
65+|-
66+| Early addresses (Satoshi's coins, CPU miners, starts with 04) || Long-range
67+|-
68+| Reused addresses (any type, except bc1r) || Long-range
76+
77+The only time a short-range attack can occur is when the transaction is in the mempool, whereas a long-range attack occurs when the public key is known well in advance. Short-range attacks require much larger, more expensive CRQCs.
78+
79+Should quantum advantage manifest, a convention is proposed in spending the full 65-byte P2PK key used by the coinbase output in Block 1 back to itself. It is proposed to call the address in Block 1 the [https://mempool.space/address/0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf2342c858ee Canary address] since it can only be spent from by others (assuming Satoshi's continued absence) if secp256k1 is broken. Should the Canary coins move, that will signal that reliance on secp256k1 is presently vulnerable. Without the Canary, or an address like it, there may be some doubt as to whether the coins were moved with keys belonging to the original owner.
80+
81+As an interesting aside, coinbase outputs to P2PK keys go as far as block 200,000, so it's possible there are between 1-2 million coins that are vulnerable from the first epoch. These coins can be considered "Satoshi's Shield." Any addresses with a balance of less than the original block subsidy of 50 coins can be considered incentive incompatible to capture until all of these are mined.
82+
83+It's for the above reason that, for those who wish to be prepared for quantum emergency, it is recommended that no more than 50 bitcoin are kept under a single distinct, unused Native SegWit (P2WPKH, "bc1q") address at a time. This is assuming that the attacker is financially-motivated instead of, for example, a nation state looking to break confidence in Bitcoin. Additionally, this assumes that other vulnerable targets such as central banks have upgraded their cryptography already.
84+
85+The Commercial National Security Algorithm Suite (CNSA) 2.0 has a timeline for software and networking equipment to be upgraded by 2030, with browsers and operating systems fully upgraded by 2033.
86+
87+Lastly, it is worth noting by way of comparison that [https://ethresear.ch/t/how-to-hard-fork-to-save-most-users-funds-in-a-quantum-emergency/18901 Vitalik Buterin's proposed solution] in an Ethereum quantum emergency is quite different from the approach in this BIP. His plan involves a hard fork of the chain, reverting all blocks after a sufficient amount of theft, and using STARKs based on BIP-32 seeds to act as the authoritative secret when signing. These measures are deemed far too heavy-handed for bitcoin.
93+
94+It is proposed to use SegWit version 3. This results in addresses that start with bc1r, which could be a useful way to remember that these are quantum [r]esistant addresses (similar to how bc1q corresponds to Se[q]Wit and bc1p corresponds to Ta[p]root). This is referencing the lookup table under [https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#bech32 BIP-173].
95+
96+The proposal above also leaves a gap in case it makes sense to use version 2, or bc1z, for implementation of other address formats such as those that employ Cross Input Signature Aggregation (CISA).
97+
98+P2QRH is meant to be implemented on top of P2TR, combining the security of classical Schnorr signatures along with post-quantum cryptography. This is a form of "hybrid cryptography" such that no regression in security is presented should a vulnerability exist in one of the signature algorithms used. One key distinction between P2QRH and P2TR however is that P2QRH will encode a hash of the public key. This is a significant deviation from how Taproot works by itself, but it is necessary to avoid exposing public keys on-chain where they are vulnerable to attack.
This is a quick first skim. Seems fine so far, I left some comments. The Motivation and Rationale seem a bit long, perhaps some of that could be split out into other sections like Related Work, Backward Compatibility, or just tightened a bit.
I’m wondering whether introducing four different signature schemes at once may be a bit too ambitious.
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
I’m wondering whether introducing four different signature schemes at once may be a bit too ambitious.
SPHINCS and Crystals-DILITHIUM are approved by NIST. Antoine Riard specifically requested the inclusion of SPHINCS on the mailing list, and the alternative proposal implements Crystals-DILITHIUM. FALCON is likely to be approved as as a FIPS standard as well, but it’s not yet official. SQIsign is very attractive for its small public key and signature sizes, but it is only just recently under review.
