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.
| P2PKH || No (trusted miner) || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
| P2PKH (reused) || No || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
I think I'd like to structure that information differently, similar to how I did so on this slide:
I'll also need to add a 5th case: Unhardened BIP-32 HD wallet keys
This should be resolved now. Let me know if it's not.
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.
What about public keys that are derived via BIP-32 non-hardened child keys? While the public key is not reused, one might be able to guess and check child keys from revealed public keys and learn the public key for a p2pkh address prior to seeing a signature for that public key. Is there a reason this is not a concern?
That is a concern I haven't considered. I'll be sure to add that.
It's also been added to the new table for scenarios for revealed public keys on bitcoin.
Looks good to me
Derivation of child keys (whether hardened or not) requires the chain code, so this is only a concern if the attacker has access to the extended public key (in which case they can just directly convert it to an extended private key).
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.
Reading "Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes" it is unclear to me how the number 10^40 for applying Grover to Bitcoin's POW was arrived at in this BIP. It might be worth creating a footnote that details the derivation of this result from that paper.
Those figures were provided by Pierre-Luc, along with the relevant paper. I've included a footnote with his comments.
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.
Very interesting. I'll be sure to include that nuance.
I've reworked the paragraph. Let me know if that works. The 95 zeros figure came from the 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.
All very good points. I'll make sure those are reflected in the BIP.
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.
Thank you for that. I've made some edits and replaced the other sections with that. Here's the diff: https://github.com/bitcoin/bips/compare/7f4456de30db2528bcfc1dddbbc3c7533169646a..d83c29d59b78443e20a040395ca23777bfc332f1
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)
Sounds good. Let me know if my latest changes have resolved this.
Looks good for now, thank you.
Interesting (the question of resistance to quantum computing may have resurged lately with the publication of https://scottaaronson.blog/?p=8329, see also https://x.com/n1ckler/status/1839215426091249778).
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
Thank you for that, I've added that link as a reference.
@cryptoquick Can you begin to write up the sections currently marked as TBD, along with a backwards compatibility section (to describe incompatibilities, severity, and suggest mitigations, where applicable/relevant)? We've begun to reserve a range of BIP numbers for this topic, pending continued progress here.
typo fix
@cryptoquick ping for an update here. Have you seen https://groups.google.com/g/bitcoindev/c/p8xz08YTvkw / https://github.com/chucrut/bips/blob/master/bip-xxxx.md? It may be interesting to review each other and possibly collaborate.
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:
This 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].
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].
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 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.
Is this not just a question of time? If the security of the DLP is broken, eventually it could be broken in the time between submission of a transaction and its confirmation. Anyway, an attacker could simply outspend the victim’s transaction to buy more time.
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.
Relying on mining pools to keep transactions private does not feel like a viable security assumption.
Agreed, which is why P2QRH is preferable. It's still worth mentioning, but I'll be sure to explain this is the entire purpose of P2QRH, to essentially keep the mempool trustless.
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.
Rather, this new output type would be expected not be vulnerable at all?
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.
The 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
What is "bc1r"? It has not been introduced at this point.
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.
As of earlier this month, ₿1,723,848 were held in P2PK outputs.
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.
Some of this Motivation section could appear in "Related Work" or "backward compatibility".
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.
Does it then even make sense to base the new output type on Taproot rather than e.g. P2WPKH?
There's already things that use taptrees where this kind of cryptographic commitment scheme would be adequate, such as for RGB. It would be nice to also be able to rely on Schnorr signature aggregation even in cases where its security has to be augmented by PQC. Do you know of anything that could be broken if the public key isn't known in advance? Like MuSig2 or FROST?
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.
* Add details on attestation structure and parsing.
* bip-p2qrh.mediawiki: Separating discussion about Grovers algorithm into
its own section.
* Update phrasing and formatting.
* Kyle fixes
* Add Jeff Bride to acknowledgments
* Apply suggestions from code review
Co-authored-by: Kyle Crews <92337423+CrewsControlSolutions@users.noreply.github.com>
* Updates to clarity.
---------
Co-authored-by: jbride <jbride2001@yahoo.com>
Co-authored-by: Kyle Crews <92337423+CrewsControlSolutions@users.noreply.github.com>
Just a note: The content of the BIP should be nearing its final state. Feel free to leave feedback while I work on the test vectors, it'll take me a while since I'm also making changes to rust-bitcoin in order to support P2QRH and transaction attestation, but I don't expect any major changes from my side at this point.
* MediaWiki fixes, remove redundant sections.
* Fix link format check
Hey @cryptoquick, just wanted to mention a few quick things:
@murchandamus Done!
0 | @@ -0,0 +1,592 @@ 1 | +<pre> 2 | + BIP: TBD
Nit:
BIP: ?
0 | @@ -0,0 +1,592 @@ 1 | +<pre> 2 | + BIP: TBD 3 | + Title: QuBit: SegWit version 3 spending rules (P2QRH)
Should mention that it’s a soft fork:
Layer: <Consensus (soft fork)
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
The preamble is order sensitive:
Created: 2024-06-08
License: BSD-3-Clause
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
This feels like a partial repetition of lines 29–31. Perhaps the prior lines should be folded into this introduction of the issue.
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
Most output types require the public key is explicitly stated in the input script and it doesn’t even have to be recovered from the signature.
8 | + Type: Standards Track 9 | + License: BSD-3-Clause 10 | + Created: 2024-06-08 11 | +</pre> 12 | + 13 | +__TOC__
The TOC is generated automatically in the richtext view:
I started taking a look, but two additional commits have been made since. I’ll try to take a look next week.
The line break suggestion was meant mostly as a way to make diffs more readable and make it easier to make suggestions in the review. It’s not a fixed rule, so if it breaks stuff, feel free to e.g. leave table rows or links in a single line even if it’s longer than other stuff.
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
0 | @@ -0,0 +1,587 @@ 1 | +<pre> 2 | + BIP: ? 3 | + Title: QuBit: SegWit version 3 spending rules (P2QRH) 4 | + Layer: <Consensus (soft fork)
Sorry, my suggestion had an errant "<" here.
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.
not to reveal the transaction public key to attackers.
Suggest removing unnecessary sentence. If you disagree, resolve this comment.
Actually, I think it provides important context and insight as to what P2QRH specifically addresses given the alternative (private miner mempools), but that's just my opinion.
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
Did you mean fee market rather than free market?
Not really, but maybe that might make more sense? The fee market is supposed to be a free market.
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.
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
I'd suggest that readability would be improved by having a subsection titled something like "Long Range and Short Range Quantum Attacks" that defines this terminology and consequences are introduced upfront.
Something like:
If you disagree with this suggestion, just mark this comment as resolved.
Done!
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.
The specific quantum-resistant signature algorithm used is inferred from the length of the public key.
If we infer the signature algorithm from the public key alone, then we will reject a signature which has the wrong length for that algorithm. This makes error handling easier and the output commits to the signature algorithm.
Whereas if we infer the signature algorithm from the public key and the signature then if one of them is wrong, we don't know the intended signature algorithm.
That's a good point.
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:
Below you discuss supporting secp256k1 as an algorithm for this output. It should probably be included in this list.
I think I'll just clarify this section is for PQC algorithms.
I want to propose an alternative design. Instead of supporting multiple different signature algorithms in the same output and then inferring algorithm based on public key length. Flag signature algorithm based on address prefix, e.g. addresses that start with bc1f only accept FALCON-1024 public keys and signatures.
Is the reason you are doing multisig outside of script, because of the stack element limitations of some these bigger signatures? Are there any issues with the values on the attestation stack being larger than 520?
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
What about just using a merklized structure for tapscript so we don't need to depend on signature specifies? The output could be HASH256(HASH256(pubkey),scriptroot) where scriptroot = HASH256(merkletree of scripts). You'd get the taproot privacy benefits of not revealing that a script spend path exists when doing a key spend. If no script spend path exists simply choosing scriptroot to be a random number, if a script spend path exists, include a random number as one of the branches of your merkle tree.
The main downside of this merklized approach is that each spend has to push an additional 32 bytes. However given the size of post-quantum signatures and public keys, this additional 32 bytes shouldn't matter much.
https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki
That's a great point. You're right, we should use a merkle tree to allow branch exclusions. We can distinguish between hashes and x-only public keys because x-only public keys will be accompanied by a signature, whereas a hash would not, and so it would be considered and excluded branch.
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
What about using a STARK over all the post-quantum signatures included in a block by the miner to accelerate verification? Is there anything about this design that would prevent adding such a feature?
As we discussed privately, a STARKS-based approach would be out of scope for this BIP, but alternative approaches specified in separate BIPs are certainly welcome.
Sorry for coming late with this important PR, we have just shared 3 proposed pqc algorithms that guarantee elimination of quantum computer risk.
Sorry for coming late with this important PR, we have just shared 3 proposed pqc algorithms that guarantee elimination of quantum computer risk.
That's a great start! I see from your documentation here you're intending to use the same PQC signature algorithms we've selected, which is validating of the approach recommended for this BIP.
Co-authored-by: Ethan Heilman <ethan.r.heilman@gmail.com>
I want to propose an alternative design. Instead of supporting multiple different signature algorithms in the same output and then inferring algorithm based on public key length. Flag signature algorithm based on address prefix, e.g. addresses that start with
bc1fonly accept FALCON-1024 public keys and signatures.
The problem with that approach is that there's only so many OP_NUMs to prefix the address type with for each signature type. If new signature algorithms were added, I would imagine they would be added in batches, so that bc1f would indicate a superset of multiple algorithms.
- This makes it straightforward to add new post-quantum signature algorithms and lets you streamline this design by only needing to support one post-quantum signature algorithm.
- This avoids using length as a signaling mechanism. Currently length works, but what if two algorithms have the same length public key? Do we lengthen one?
Yes, we would lengthen one.
- Supporting multiple signature algorithms in the same output is likely to increase complexity for other protocols. Say a payment channel where the two parties are using different signature algorithms. I don't see this as a strong reason not to do this, but I think the BIP needs a justification for this additional complexity.
In the case of a payment channel, it's a 2-of-2 multisig agreed to by both parties. If either party finds the signature algorithms proposed unacceptable, the channel simply won't be funded.
Is the reason you are doing multisig outside of script, because of the stack element limitations of some these bigger signatures? Are there any issues with the values on the attestation stack being larger than 520?
Partly for that reason, and also, because I want this to use stricter validation rules than all that script expresses.
Hi, Sorry for the ping, This is too complicated for me. Is there no way to simplify or generalize this?
Yesterday, we pushed it with a simplified and holistic version.
Hi, Sorry for the ping, This is too complicated for me. Is there no way to simplify or generalize this?
Perhaps a good summary is this:
In this BIP we suggest a new address format beginning with bc1r that introduces the capability for users to generate addresses that can receive payments signed using quantum-resistant keys and signatures.
It really is that simple, but there are the details for why this needs to happen and how it should happen and this tries to cover those in a comprehensive enough manner, or at least, as comprehensive as we can be without test vectors.
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
I assume that the doubling from the example here is meant to be relevant for the duplication of the effort:
keys from public keys—a process referred to as quantum key decryption. Importantly, simply doubling the public key
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]
"Additionally" could be read as being related:
closer to 20%. Independently, 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
Sorry for being imprecise when I suggested line breaks. I meant that it would be preferable for lines of flowing text to be limited in length as it can be hard to see what exactly changed for extremely long lines
It is fine for tables and code samples to be longer, as line breaks can add confusion or introduce errors in those cases.
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].
Some schemes already assume that higher native segwit versions follow lower segwit versions. It seems that skipping a version should have a stronger motivation as a similar mnemonic could be crafted as easily for version 2: bc1(z), corresponds to "(z)ecure addresses" or to addresses that "let the user rest e(z)".
I've removed this as per @vostrnad's suggestion.
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).
I’m not sure that is a pressing concern.
Removed. Nobody cares about CISA anymore :joy_cat:
Oh, I don’t mean that people don’t care about CISA anymore. I just don’t think we would need to skip a version to keep space for it, when there isn’t even a concrete proposal yet.
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.
While maybe a sensible recommendation, this feels a bit digressive.
Maybe, but BIPs are read by many kinds of people with different backgrounds and motivations, and I think it's important to provide background on Satoshi's Shield in order to not be fearmongering. It's important that readers have a proper perspective of the threat this addresses, you know?
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
Nit:
* [https://bitcoinops.org/en/newsletters/2024/06/14/ Bitcoin Optech newsletter]
* [https://bitcoinops.org/en/podcast/2024/06/18/#draft-bip-for-quantum-safe-address-format Bitcoin Optech discussion
@jonatack Why did you re-add the draft designation? From what I understand, @murchandamus recommended that be changed: #1670 (comment)
@jonatack Why did you re-add the draft designation? From what I understand, @murchandamus recommended that be changed: #1670 (comment)
I see. The PR title doesn't refer to the GitHub status of "draft, not ready for review", only that it is a BIP draft as yet without a number -- once there is a number, then the title becomes "BIP <number>: ..." instead. I unified a few titles yesterday to make it easier for me to follow the various PRs.
Are there any remaining obstacles keeping this from getting a BIP number?
I have a range of numbers in mind for QC resistance BIPs to run by the other editors and am re-reviewing here.
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
Please update the BIP number (on line 2), filename, and the created date to 2024-12-18 (date of BIP number assignment) and add a corresponding BIP draft entry to the repo root README file.
Done!
Assigned BIP number 360.
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:'''
This proposal uses SQIsign signatures, an isogeny-based quantum-resistant signature scheme, to enhance the protocol's quantum security. While SQIsign has shown promising performance and compact signature sizes, it is worth noting that SQIsign is not part of the NIST PQC standardization process. This choice reflects a consideration of alternatives beyond NIST's selected algorithms, aiming to balance quantum resistance with efficiency and practical implementation constraints. Future analysis and community feedback will determine its suitability for adoption. All other pq alogrithms of Group 1 & 2 highlighted in pqcBitcoin repo are confirmed NIST standard and tested.
Somehow you've reviewed an older version of this BIP. SQIsign has been removed.
Sorry for being late, but was any thought been given to the feasibility of cryptographic multisig for the algorithms named?
Raccoon has a few threshold signature protocols which can drop in with the originally defined Raccoon (so long as parameters are mutual).
https://eprint.iacr.org/2024/1291 https://eprint.iacr.org/2024/184 https://eprint.iacr.org/2024/496
This would avoid the on-chain cost of several signatures and provide indistinguishability.
@kayabaNerve This BIP supports multisig. Maybe threshold signatures can be added once they're more mature.
I'm aware of the on-chain multisig possible with this proposal, which would have non-trivial scalability limits.
Raccoon was one of the PQ signature algorithms submitted to the NIST competition for additional schemes, alongside SQIsign. It isn't explicitly/inherently a threshold signature and just has threshold signature schemes available. I'd question if it is too immature given the (currently rather) unique benefits provided.
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
This proposal defines a new output type, not address type. An address is merely an encoding of an output script, and in this case an existing address type (Bech32m) is used.
This proposal aims to mitigate these risks by introducing a Pay to Quantum Resistant Hash (P2QRH) output 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
It seems intuitive that a short range attack would require a more powerful QC than a long range attack, but is this just intuition or is it rooted in actual science? In the former case this text needs more "may"s and "it is believed"s, and in the latter case a link to relevant research.
Yes, I will add this section:
<ref name="short-range">
In the paper
[https://arxiv.org/pdf/2306.08585 How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates]
the authors estimate that CRQC with 28 million superconducting physical qubits would take 8.3 seconds to calculate a
256-bit key, while a CRQC with 6.9 million physical qubits would take 58 seconds. This implies that a CRQC with 4x as
many qubits would be roughly 7 times faster.
</ref>
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
Since there are only 7 standard output types relevant to this discussion, does the table really need to be non-exhaustive?
(P2PK, P2PKH, P2MS, P2SH, P2WPKH, P2WSH, P2TR)
72 | +vulnerable to a long-range quantum attack: 73 | + 74 | +{| class="wikitable" 75 | +|+ Vulnerable address types 76 | +|- 77 | +! Address type !! Vulnerable !! Prefix !! Example
|+ Vulnerable output types
|-
! Type !! Vulnerable !! Prefix !! Example
75 | +|+ Vulnerable address types 76 | +|- 77 | +! Address type !! Vulnerable !! Prefix !! Example 78 | +|- 79 | +| P2PK || Yes || 04 || 80 | +0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf
To prevent formatting breaks, I'd recommend using a 33-byte (compressed) key instead.
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
It should be noted that Taproot outputs 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.
Can you elaborate? Child keys depend not only on the parent key but also on the chain code.
This is in reference to this comment: #1670 (review)
I think @vostrnad’s point stands
I think I'll just leave that point out, then.
Yes, I believe so, too: #1670 (review)
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)
* P2PK outputs (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
Shouldn't this say "BIP-32 extended public keys" instead?
I don't think so, if I understand @EthanHeilman 's feedback, but I could be wrong.
I’m not sure, but I could see that you would need the entire xpub, not just the parent public key.
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
Link doesn't work, please fix.
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.
This still leaves in the possibility that Satoshi comes back and spends the coins. Why don't we choose coins that we know nobody knows the private key for, i.e. coins locked to a NUMS point?
Is there an example of that? If so, a link would be very helpful.
I only managed to find two non-empty addresses that use an obvious NUMS point containing around 0.02 BTC in total:
Given this lack of funds locked in NUMS addresses and Murch's other criticisms (which I agree with) I'd recommend completely removing the concept of canary coins from the BIP.
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
There's no such thing as a "P2PK address"; P2PK scripts don't have a standardized address format. (What mempool.space shows is just the raw public key, not an address, not least because you can't send to it using any commonly used wallet software.)
block reward of 50 coins each, and there are roughly 34,000 distinct P2PK scripts 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
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
In the case of SegWit and Taproot these are just coincidences. I would leave this out.
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
BIP16 doesn't use double SHA-256 though?
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
What's an "output spend script"?
Also known as the scriptpubkey. Is that the preferred terminology?
I prefer either "input script" and "output script" or "scriptSig" and "scriptPubKey". I don’t think I’ve seen "output spend script" before.
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
To address the risk of arbitrary data being stored using P2QRH (QuBit) outputs, 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
In the distant future, following the implementation of the P2QRH output type 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:
This is a bit inaccurate: you can't just modify the existing serialization format because existing nodes still need to receive transactions in that format. Instead you're creating a new format and keeping both (actually 3 now).
By the way, will you not also need to introduce e.g. a qtxid, similar to wtxid?
Following BIP-141, a new transaction serialization format is introduced to include an 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).
You probably mean compact size, not VarInt. See https://learnmeabitcoin.com/technical/general/compact-size
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
outputs. 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.
the design of the P2TR (Taproot) output type using Schnorr signatures.
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
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
I assume that "twice" specifically corresponds to doubling the length rather than "increasing it".
keys from public keys—a process referred to as quantum key decryption. Importantly, simply doubling the public key
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]
It sounds like the two are related, but rather you are citing two independent resources. Also, Pieter has previously espoused the opinion that he is not a cryptographer.
closer to 20%. Independently, cryptographer Pieter Wuille [https://x.com/pwuille/status/1108085284862713856 reasons]
Also I think Pieter has previously mentioned that he wouldn’t consider himself a cryptographer, so maybe just go with "Bitcoin developer"
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
It is proposed to implement a Pay to Quantum Resistant Hash (P2QRH) output 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
algorithm. This new output 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 | +|}
It should perhaps be reiterated in the context of this table that their funds are only safe in P2PKH, P2SH, P2WPKH, and P2WSH outputs if they haven’t used the address before.
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
Same point as raised above by @vostrnad
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.
This whole part about the Canary and Satoshi’s Shield feels a bit like an excursion from the main topic. Anyway, if I were to attack anything, I wouldn’t go after Satoshi’s coins. First because it would raise suspicion immediately, and secondly, because e.g., the Binance Cold Wallet 34xp4vRoCGJym3xR7yCVPFHoCNxv4Twseo currently holds ₿248,597.53479136 and is a reused address.
I understand that perspective, but as the first BIP related to quantum computing, I wanted to appropriately set the stage even for skeptics. The Canary address is meant to be a flag in the sand that people can hopefully agree that if Satoshi is expected never to return, then this is a logical place to check to agree that Bitcoin is unequivocally compromised.
I don’t get it. If you could compromise an output script worth 50 ₿ or an output script worth 250 k₿, how does the former serve as a canary, i.e., an early warning?!
I agree, attempting to create a convention for canary coins seems inherently flawed and out of scope for this BIP.
Okay, I'll remove it.
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].
I’m not convinced by this rationale for skipping ahead in the versions. A similar mnemonic could be made up for bc1z e.g., "(z)ecure against quantum".
I think a better use for bc1z would be P2TRH, which is a follow-up BIP I want to introduce as an alternative should this BIP fail to gather consensus.
As for bc1r, I think to some degree aesthetics matter. "Resistant" should be the word that comes to mind.
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).
I would prefer using native segwit versions as proposals come up rather than leaving space for things with an uncertain timeline.
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.
Would this perhaps better be described as a Witness Program?
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.
It might generally make sense to separate the description of the output type mechanics from the serialization format into different sections.
Good suggestion. I've moved this section and the next to a section after the ScriptPubKey section called Output Mechanics.
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.
I have no clue about the trade-offs here, but wouldn’t it make the proposal much more viable if it picked only one and added hooks to introduce another later in case we change our mind as we learn more?
It's in the interest of supporting hybrid cryptography, especially for high value outputs, such as cold wallets used by exchanges. I'll be sure to add that explanation, if it helps.
As for viability, I can explain that a separate libbitcoinpqc library could be developed as a drop-in analogue to libsecp256k1.
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.
This begs the question how Quantum Resistant and Quantum Secure are distinguished.
Good question. I've added more details on that.
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:
It’s not clear to me why we are suddenly talking about multiple public keys here.
I've added some more details, let me know if that helps.
I've added some more details, let me know if that helps.
Link to the change commit, please?
This is where I clarified, while not a hard requirement, it makes sense for there to always be at least two public keys for a P2QRH address: https://github.com/bitcoin/bips/pull/1670/commits/0fdd8c3edc9e563bcf5a7cb0cc93e6f428b948d8#diff-e296d32a8f60ef9f846683e801718d16c41fa7d8f1065e0afa6405a0764a91e3R250-R253
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.
I’m fairly lost here. The multiple public keys and tree construction seems to be mentioned for the first time here. If there was rationale for this tree construction, I missed it. It’s not clear to me what this tree construction achieves. How many of the public keys can be provided directly in the form of their hashes? When you mention MAST, I assume you mean "Merklized Alternative Script Trees", so one would spend by revealing only a single key from the tree and satisfy its spending conditions? Altogether, this section is hard to follow for me.
I've tried to add more supporting information. Let me know if that's better.
I think I’m slowly getting the gist of it, but it might help to cover the abstract idea briefly at a higher level before getting into all the details.
BIP114 is also named "MAST" (Merkelized Abstract Syntax Trees), so perhaps write out the MAST you are referring to here.
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)
Should the flag not be considered a boolean array? 0x01 for witness, 0x02 for attestation, 0x03 for witness and attestation? Is it possible for an attestation to appear without a witness section?
I've considered this, and yes, it might make sense if we've completely transitioned away from classical cryptography. I'll be sure to factor that in.