BIP-360: QuBit - Pay to Quantum Resistant Hash #1670

41+|-
42+! Address type !! Vulnerable !! Prefix !! Example
43+|-
44+| P2PK || Yes || 04 || 0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf2342c858ee
45+|-
46+| P2PKH || 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.

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.

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.

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

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.

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

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

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.

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.

0@@ -0,0 +1,592 @@
1+<pre>
2+  BIP: TBD

0@@ -0,0 +1,592 @@
1+<pre>
2+  BIP: TBD
3+  Title: QuBit: SegWit version 3 spending rules (P2QRH)

 5+  Comments-Summary: No comments yet.
 6+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-TBD
 7+  Status: Draft
 8+  Type: Standards Track
 9+  License: BSD-3-Clause
10+  Created: 2024-06-08

33+this is investigated further in the paper,
34+[https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specifications-on-reaching ''The impact
35+of hardware specifications on reaching quantum advantage in the fault tolerant regime''].
36+
37+The primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks
38+generally considered to be their potential to break ECC, which is used in signatures and Taproot commitments], hence

44+and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the
45+Bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now
46+closer to 20%. Additionally, cryptographer Pieter Wuille [https://x.com/pwuille/status/1108085284862713856 reasons]
47+even more might be vulnerable.
48+
49+Ordinarily, when a transaction is signed, the public key can be recovered from the signature. This makes a transaction

 8+  Type: Standards Track
 9+  License: BSD-3-Clause
10+  Created: 2024-06-08
11+</pre>
12+
13+__TOC__

0@@ -0,0 +1,587 @@
1+<pre>
2+  BIP: ?
3+  Title: QuBit: SegWit version 3 spending rules (P2QRH)
4+  Layer: <Consensus (soft fork)

50+Ordinarily, when a transaction is signed, the public key is explicitly stated in the input script. This means that the
51+public key is exposed on the blockchain when the transaction is spent, making it vulnerable to quantum attack until
52+it's mined. One way to mitigate this is to submit the transaction directly to a mining pool, bypassing the mempool.
53+This process is known as an out-of-band transaction or a private mempool. In this case, the mining pool must be trusted
54+not to reveal the transaction public key to attackers. The problem with this approach is that it requires a trusted
55+third party, which the P2QRH proposal aims to avoid.

63+requires more sophisticated CRQCs. As the value being sent increases, so too should the fee in order to commit the
64+transaction to the chain as soon as possible. Once the transaction is mined, it makes useless the public key revealed
65+by spending a UTXO, so long as it is never reused.
66+
67+It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) address type that relies on a PQC signature
68+algorithm. This new address type protects transactions submitted to the mempool and helps preserve the free market by

67+It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) address type that relies on a PQC signature
68+algorithm. This new address type protects transactions submitted to the mempool and helps preserve the free market by
69+preventing the need for private, out-of-band mempool transactions.
70+
71+The following table is non-exhaustive but intended to inform the average Bitcoin user whether their bitcoin is
72+vulnerable to a long-range quantum attack.

110+| Any transaction in the mempool (except for P2QRH) || Short-range
111+|-
112+| Unhardened BIP-32 HD wallet keys || Both Long-range or Short-range
113+|}
114+
115+The only time a short-range attack can occur is when the transaction is in the mempool, whereas a long-range attack

314+For each input, a separate attestation field is used. To know how many attestation fields are present, implementations
315+must count the number of inputs present in the transaction.
316+
317+=== Signature Algorithm Identification ===
318+
319+The specific quantum-resistant signature algorithm used is inferred from the length of the public key and signature.

317+=== Signature Algorithm Identification ===
318+
319+The specific quantum-resistant signature algorithm used is inferred from the length of the public key and signature.
320+Implementations must recognize the supported algorithms and validate accordingly.
321+
322+Supported algorithms and their NIST Level V parameters:

519+One consideration for choosing an algorithm is its maturity. secp256k1 was already 8 years old by the time it was
520+chosen as Bitcoin's curve. Isogeny cryptography when it was first introduced was broken over a weekend.
521+
522+Ideally SQIsign also proves to be flexible enough to support
523+[https://www.pierrickdartois.fr/homepage/wp-content/uploads/2022/04/Report_OSIDH_DARTOIS.pdf Isogeny Diffie-Hellman] to
524+replace ECDH applications, and also provide methods for the key tweaking necessary to support TapScript for P2QR

442+For example, for CRYSTALS-Dilithium Level V, a single signature is 4,595 bytes, a substantial increase over current
443+ECDSA or Schnorr signatures.
444+
445+==== Performance Impact ====
446+
447+Verification of quantum-resistant signatures will be computationally more intensive, and any attestation discount will

29+the cryptographic assumptions of Elliptic Curve Cryptography (ECC), which secures Bitcoin's signatures and Taproot
30+commitments. Specifically, [https://arxiv.org/pdf/quant-ph/0301141 Shor's algorithm] enables a CRQC to solve the
31+Discrete Logarithm Problem (DLP) exponentially faster than classical methods<ref name="shor">Shor's algorithm is
32+believed to need 10^8 operations to break a 256-bit elliptic curve public key.</ref>, allowing the derivation of private
33+keys from public keys—a process referred to as quantum key decryption. Importantly, simply increasing the public key
34+length (e.g., using a hypothetical secp512k1 curve) would only make deriving the private key twice as hard, offering

42+
43+The vulnerability of existing Bitcoin addresses is investigated in
44+[https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-
45+and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the
46+Bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now
47+closer to 20%. Additionally, cryptographer Pieter Wuille [https://x.com/pwuille/status/1108085284862713856 reasons]

76+|-
77+! Address type !! Vulnerable !! Prefix !! Example
78+|-
79+| P2PK || Yes || 04 ||
80+0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf
81+2342c858ee

156+the capital B refers to Bitcoin. The name QuBit also rhymes to some extent with SegWit.
157+
158+It is proposed to use SegWit version 3. This results in addresses that start with bc1r, which could be a useful way to
159+remember that these are quantum (r)esistant addresses (similar to how bc1q corresponds to Se(q)Wit and bc1p corresponds
160+to Ta(p)root). This is referencing the lookup table under
161+[https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#bech32 BIP-173].

159+remember that these are quantum (r)esistant addresses (similar to how bc1q corresponds to Se(q)Wit and bc1p corresponds
160+to Ta(p)root). This is referencing the lookup table under
161+[https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#bech32 BIP-173].
162+
163+The proposal above also leaves a gap in case it makes sense to use version 2, or bc1z, for implementation of other
164+address formats such as those that employ Cross Input Signature Aggregation (CISA).

133+
134+It's for the above reason that, for those who wish to be prepared for quantum emergency, it is recommended that no more
135+than 50 bitcoin are kept under a single, distinct, unused Native SegWit (P2WPKH, "bc1q") address at a time. This is
136+assuming that the attacker is financially motivated instead of, for example, a nation state looking to break confidence
137+in Bitcoin. Additionally, this assumes that other vulnerable targets such as central banks have upgraded their
138+cryptography by this time.

562+
563+* [https://groups.google.com/g/bitcoindev/c/Aee8xKuIC2s/m/cu6xej1mBQAJ Mailing list discussion]
564+* [https://delvingbitcoin.org/t/proposing-a-p2qrh-bip-towards-a-quantum-resistant-soft-fork/956?u=cryptoquick Delving
565+Bitcoin discussion]
566+* [https://bitcoinops.org/en/newsletters/2024/06/14/ Bitcoin OpTech newsletter]
567+* [https://bitcoinops.org/en/podcast/2024/06/18/#draft-bip-for-quantum-safe-address-format Bitcoin OpTech discussion

 5+  Author: Hunter Beast <hunter@surmount.systems>
 6+  Comments-Summary: No comments yet.
 7+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-TBD
 8+  Status: Draft
 9+  Type: Standards Track
10+  Created: 2024-06-08

352+  * Public Key Length: 2,592 bytes
353+  * Signature Length: 4,595 bytes
354+* '''FALCON-1024:'''
355+  * Public Key Length: 1,793 bytes
356+  * Signature Length: 1,280 bytes
357+* '''SQIsign NIST-V:'''

34+length (e.g., using a hypothetical secp512k1 curve) would only make deriving the private key twice as hard, offering
35+insufficient protection. The computational complexity of this attack is further explored in
36+[https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specifications-on-reaching ''The impact
37+of hardware specifications on reaching quantum advantage in the fault-tolerant regime''].
38+
39+This proposal aims to mitigate these risks by introducing a Pay to Quantum Resistant Hash (P2QRH) address type that

58+spent to new addresses on a regular basis in order to prevent the possibility of a "long-range CRQC attack" recovering
59+the key behind high-value addresses. A long-range quantum attack can be considered one performed with chain data, such
60+as that from a used address or one encoded in a spend script. This is likely to be more common early on, as early
61+quantum computers must be run for longer in order to overcome errors caused by noise. A "short-range quantum attack"
62+would be one performed on keys in the mempool, which is seen as much more difficult given the block time, and so it
63+requires more sophisticated CRQCs. As the value being sent increases, so too should the fee in order to commit the

66+
67+It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) address type that relies on a PQC signature
68+algorithm. This new address type protects transactions submitted to the mempool and helps preserve the free market by
69+preventing the need for private, out-of-band mempool transactions.
70+
71+The following table is non-exhaustive but intended to inform the average Bitcoin user whether their bitcoin is

72+vulnerable to a long-range quantum attack:
73+
74+{| class="wikitable"
75+|+ Vulnerable address types
76+|-
77+! Address type !! Vulnerable !! Prefix !! Example

75+|+ Vulnerable address types
76+|-
77+! Address type !! Vulnerable !! Prefix !! Example
78+|-
79+| P2PK || Yes || 04 ||
80+0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf

85+| P2WPKH || No || bc1q || bc1qsnh5ktku9ztqeqfr89yrqjd05eh58nah884mku
86+|-
87+| P2TR || Yes || bc1p || bc1p92aslsnseq786wxfk3ekra90ds9ku47qttupfjsqmmj4z82xdq4q3rr58u
88+|}
89+
90+It should be noted that Taproot addresses are vulnerable in that they encode a 32-byte x-only public key, from which a

89+
90+It should be noted that Taproot addresses are vulnerable in that they encode a 32-byte x-only public key, from which a
91+full public key can be reconstructed.
92+
93+If a key is recovered by a CRQC it can also be trivially checked to see if any child keys were produced using an
94+unhardened [https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki BIP-32] derivation path.

 96+==== Long Range and Short Range Quantum Attacks ====
 97+
 98+Long Range Quantum Attack is an attack in which the public key has been exposed on the blockchain for an extended
 99+period of time, giving an attacker ample opportunity to break the cryptography. This affects:
100+
101+* Early addresses (Satoshi's coins, CPU miners, starts with 04)

 99+period of time, giving an attacker ample opportunity to break the cryptography. This affects:
100+
101+* Early addresses (Satoshi's coins, CPU miners, starts with 04)
102+* Reused addresses (any type, except P2QRH)
103+* Taproot addresses (starts with bc1p)
104+* Unhardened BIP-32 HD wallet keys

112+Short-range attacks require much larger, more expensive CRQCs since they must be executed within the short window
113+before a transaction is mined. Long-range attacks can be executed over a longer timeframe since the public key remains
114+exposed on the blockchain indefinitely.
115+
116+Should quantum advantage manifest, a convention is proposed in spending the full 65-byte P2PK key used by the coinbase
117+output in Block 1 back to itself. It is proposed to call the address in Block 1 the

113+before a transaction is mined. Long-range attacks can be executed over a longer timeframe since the public key remains
114+exposed on the blockchain indefinitely.
115+
116+Should quantum advantage manifest, a convention is proposed in spending the full 65-byte P2PK key used by the coinbase
117+output in Block 1 back to itself. It is proposed to call the address in Block 1 the
118+[https://mempool.space/address/0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f81

118+[https://mempool.space/address/0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f81
119+41781e62294721166bf621e73a82cbf2342c858ee
120+Canary address] since it can only be spent from by others (assuming Satoshi's continued absence) if secp256k1 is
121+broken. Should the Canary coins move, that will signal that reliance on secp256k1 is presently vulnerable. Without the
122+Canary, or an address like it, there may be some doubt as to whether the coins were moved with keys belonging to the
123+original owner.

122+Canary, or an address like it, there may be some doubt as to whether the coins were moved with keys belonging to the
123+original owner.
124+
125+Coinbase outputs to P2PK keys go as far as block 200,000, so there are, at the time of writing, 1,723,848 coins that
126+are vulnerable from the first epoch at the time of writing in P2PK outputs alone. The majority of these have a
127+block reward of 50 coins each, and there are roughly 34,000 distinct P2PK addresses that are vulnerable. These coins

137+in Bitcoin. Additionally, this assumes that other vulnerable targets such as central banks have upgraded their
138+cryptography by this time.
139+
140+The Commercial National Security Algorithm Suite (CNSA) 2.0 has a timeline for software and networking equipment to be
141+upgraded by 2030, with browsers and operating systems fully upgraded by 2033. According to NIST IR 8547, Elliptic Curve
142+Cryptography is planned to be disallowed within the US Federal government after 2035. An exception is made for hybrid

155+This is the first in a series of BIPs under a QuBit soft fork. A qubit is a fundamental unit of quantum computing, and
156+the capital B refers to Bitcoin. The name QuBit also rhymes to some extent with SegWit.
157+
158+It is proposed to use SegWit version 3. This results in addresses that start with bc1r, which could be a useful way to
159+remember that these are quantum (r)esistant addresses (similar to how bc1q corresponds to Se(q)Wit and bc1p corresponds
160+to Ta(p)root). This is referencing the lookup table under

168+should a vulnerability exist in one of the signature algorithms used. One key distinction between P2QRH and P2TR
169+however is that P2QRH will encode a hash of the public key. This is a significant deviation from how Taproot works by
170+itself, but it is necessary to avoid exposing public keys on-chain where they are vulnerable to attack.
171+
172+P2QRH uses a 32-byte HASH256 (specifically SHA-256 twice-over, which is similar to that used in
173+[https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki#specification BIP-16]) of the public key to reduce the

170+itself, but it is necessary to avoid exposing public keys on-chain where they are vulnerable to attack.
171+
172+P2QRH uses a 32-byte HASH256 (specifically SHA-256 twice-over, which is similar to that used in
173+[https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki#specification BIP-16]) of the public key to reduce the
174+size of new outputs and also to increase security by not having the public key available on-chain. This hash serves as
175+a minimal cryptographic commitment to a public key. It goes into the output spend script, which does not receive the

192+increase in economic activity. An increase in the witness discount would not only impact node runners but those with
193+inscriptions would also have the scarcity of their non-monetary assets affected. The only way to prevent these effects
194+while also increasing the discount is to have a completely separate witness—a "quantum witness." Because it is meant
195+only for public keys and signatures, we call this section of the transaction the attestation.
196+
197+To address the risk of arbitrary data being stored using P2QRH (QuBit) addresses, very specific rules will be applied

222+time-tested, and well-reviewed. Lattice cryptography is relatively new and introduces novel security assumptions to
223+Bitcoin, but their signatures are smaller and might be considered by some to be an adequate alternative to hash-based
224+signatures. SQIsign is much smaller; however, it is based on a very novel form of cryptography known as supersingular
225+elliptic curve quaternion isogeny, and at the time of writing, is not yet approved by NIST or the broader PQC community.
226+
227+In the distant future, following the implementation of the P2QRH address format in a QuBit soft fork, there will likely

300+This allows for inclusion of a Taproot MAST merkle root in the attestation, which makes P2QRH a quantum-resistant
301+version of Taproot.
302+
303+=== Transaction Serialization ===
304+
305+Following BIP-141, the transaction serialization is modified to include a new attestation field after the witness field:

314+
315+=== Attestation Structure ===
316+
317+The attestation field consists of:
318+
319+* <code>num_pubkeys</code>: The number of public keys (VarInt encoded).

530+chosen as Bitcoin's curve. Isogeny cryptography when it was first introduced was broken over a weekend.
531+
532+Ideally SQIsign also proves to be flexible enough to support
533+[https://www.pierrickdartois.fr/homepage/wp-content/uploads/2022/04/Report_OSIDH_DARTOIS.pdf Isogeny Diffie-Hellman] to
534+replace ECDH applications, and also provide methods for the key tweaking necessary to support TapScript for P2QR
535+addresses. Additionally, isogeny-based post-quantum cryptography is based on higher-order elliptic curves, and so it

586+* 2024-09-27 - Initial draft proposal
587+
588+== Acknowledgements ==
589+
590+This document is inspired by [https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki BIP-341], which introduced
591+the design of the P2TR (Taproot) address type using Schnorr signatures.

29+the cryptographic assumptions of Elliptic Curve Cryptography (ECC), which secures Bitcoin's signatures and Taproot
30+commitments. Specifically, [https://arxiv.org/pdf/quant-ph/0301141 Shor's algorithm] enables a CRQC to solve the
31+Discrete Logarithm Problem (DLP) exponentially faster than classical methods<ref name="shor">Shor's algorithm is
32+believed to need 10^8 operations to break a 256-bit elliptic curve public key.</ref>, allowing the derivation of private
33+keys from public keys—a process referred to as quantum key decryption. Importantly, simply increasing the public key
34+length (e.g., using a hypothetical secp512k1 curve) would only make deriving the private key twice as hard, offering

42+
43+The vulnerability of existing Bitcoin addresses is investigated in
44+[https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-
45+and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the
46+Bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now
47+closer to 20%. Additionally, cryptographer Pieter Wuille [https://x.com/pwuille/status/1108085284862713856 reasons]

70+
71+As the value being sent increases, so too should the fee in order to commit the transaction to the chain as soon as
72+possible. Once the transaction is mined, it makes useless the public key revealed by spending a UTXO, so long as it is
73+never reused.
74+
75+It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) address type that relies on a PQC signature

71+As the value being sent increases, so too should the fee in order to commit the transaction to the chain as soon as
72+possible. Once the transaction is mined, it makes useless the public key revealed by spending a UTXO, so long as it is
73+never reused.
74+
75+It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) address type that relies on a PQC signature
76+algorithm. This new address type protects transactions submitted to the mempool and helps preserve the free market by

 97+| P2WSH || No || bc1q || bc1qvhu3557twysq2ldn6dut6rmaj3qk04p60h9l79wk4lzgy0ca8mfsnffz65
 98+|-
 99+| P2TR || Yes || bc1p || bc1p92aslsnseq786wxfk3ekra90ds9ku47qttupfjsqmmj4z82xdq4q3rr58u
100+|-
101+| P2QRH || No || bc1r || bc1r8rt68aze8tek87cnz4ndnvfzk6tk93jv39n4lmpu5a4yw453rcpszsft3z
102+|}

119+
120+Short Range Quantum Attack is an attack that must be executed quickly while a transaction is still in the mempool,
121+before it gets mined into a block. This affects:
122+
123+* Any transaction in the mempool (except for P2QRH)
124+* Unhardened BIP-32 HD wallet keys

146+
147+It's for the above reason that, for those who wish to be prepared for quantum emergency, it is recommended that no more
148+than 50 bitcoin are kept under a single, distinct, unused Native SegWit (P2WPKH, "bc1q") address at a time. This is
149+assuming that the attacker is financially motivated instead of, for example, a nation state looking to break confidence
150+in Bitcoin. Additionally, this assumes that other vulnerable targets such as central banks have upgraded their
151+cryptography by this time.

168+This is the first in a series of BIPs under a QuBit soft fork. A qubit is a fundamental unit of quantum computing, and
169+the capital B refers to Bitcoin. The name QuBit also rhymes to some extent with SegWit.
170+
171+It is proposed to use SegWit version 3. This results in addresses that start with bc1r, which could be a useful way to
172+remember that these are quantum (r)esistant addresses. This is referencing the lookup table under
173+[https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#bech32 BIP-173].

171+It is proposed to use SegWit version 3. This results in addresses that start with bc1r, which could be a useful way to
172+remember that these are quantum (r)esistant addresses. This is referencing the lookup table under
173+[https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#bech32 BIP-173].
174+
175+The proposal above also leaves a gap in case it makes sense to use version 2, or bc1z, for implementation of other
176+address formats such as those that employ Cross Input Signature Aggregation (CISA).

181+however is that P2QRH will encode a hash of the public key. This is a significant deviation from how Taproot works by
182+itself, but it is necessary to avoid exposing public keys on-chain where they are vulnerable to attack.
183+
184+P2QRH uses a 32-byte HASH256 (specifically SHA-256 twice-over) of the public key to reduce the size of new outputs and
185+also to increase security by not having the public key available on-chain. This hash serves as a minimal cryptographic
186+commitment to a public key. It goes into the scriptPubKey, which does not receive the witness discount.

208+to spending from the witness stack in SegWit v3 outputs. A fixed signature size will be necessary for spending the
209+output, and the output must be spendable to be considered valid within node consensus. A fixed signature size will also
210+be helpful to disambiguate between signature types without an additional version byte, as SQIsign signatures are
211+substantially smaller than FALCON signatures. Consequently, the correct signature algorithm can be inferred through
212+byte length. The public key and signature will be pushed separately to the attestation stack. Multiple signatures can
213+be included in order to support multisig applications, and also for spending multiple inputs.

230+The inclusion of these four cryptosystems: SPHINCS+, CRYSTALS-Dilithium, FALCON, and SQIsign have various advocates
231+within the community due to their varying security assumptions. Hash-based cryptosystems are more conservative,
232+time-tested, and well-reviewed. Lattice cryptography is relatively new and introduces novel security assumptions to
233+Bitcoin, but their signatures are smaller and might be considered by some to be an adequate alternative to hash-based
234+signatures. SQIsign is much smaller; however, it is based on a very novel form of cryptography known as supersingular
235+elliptic curve quaternion isogeny, and at the time of writing, is not yet approved by NIST or the broader PQC community.

236+
237+In the distant future, following the implementation of the P2QRH output type in a QuBit soft fork, there will likely
238+be a need for Pay to Quantum Secure (P2QS) addresses. These will require specialized quantum hardware for signing,
239+while still [https://quantum-journal.org/papers/q-2023-01-19-901/ using public keys that are verifiable via classical
240+means]. Additional follow-on BIPs will be needed to implement P2QS. However, until specialized quantum cryptography
241+hardware is widespread, quantum resistant addresses should be an adequate intermediate solution.

249+To integrate P2QRH into existing wallet software and scripts, we introduce a new output descriptor function
250+<code>qrh()</code>. This function represents a P2QRH output, similar to how <code>wpkh()</code> and <code>tr()</code>
251+are used for P2WPKH and P2TR outputs, respectively.
252+
253+The <code>qrh()</code> function takes the HASH256 of the concatenated HASH256 of the quantum-resistant public keys as
254+its argument. For example:

306+
307+This merkle tree construction creates an efficient cryptographic commitment to multiple public keys while enabling
308+selective disclosure.
309+
310+This allows for inclusion of a Taproot MAST merkle root in the attestation, which makes P2QRH a quantum-resistant
311+version of Taproot.

316+
317+  [nVersion][marker][flag][txins][txouts][witness][attestation][nLockTime]
318+
319+* <code>marker</code>: <code>0x00</code> (same as SegWit)
320+
321+* <code>flag</code>: <code>0x02</code> (indicates the presence of both witness and attestation data)

342+
343+* <code>signature_length</code>: compact size length of the signature.
344+* <code>signature</code>: The signature bytes.
345+
346+This structure repeats for each input, in order, for flexibility in supporting multisig schemes and various
347+quantum-resistant algorithms.

386+
387+* Valid signatures corresponding to the public key(s) and the transaction data.
388+
389+3. For multi-signature schemes, all required public keys and signatures must be provided for that input within the
390+attestation. Public keys that are not needed can be excluded by including their hash in the attestation accompanied
391+with an empty signature. This includes classical Schnorr signatures.

572+== References ==
573+
574+* [https://groups.google.com/g/bitcoindev/c/Aee8xKuIC2s/m/cu6xej1mBQAJ Mailing list discussion]
575+* [https://delvingbitcoin.org/t/proposing-a-p2qrh-bip-towards-a-quantum-resistant-soft-fork/956?u=cryptoquick Delving Bitcoin discussion]
576+* [https://bitcoinops.org/en/newsletters/2024/06/14/ Bitcoin OpTech newsletter]
577+* [https://bitcoinops.org/en/podcast/2024/06/18/#draft-bip-for-quantum-safe-address-format Bitcoin OpTech discussion transcript]