This spent several months gathering feedback from the mailing list and from other advisors. This is hopefully polished enough to submit upstream.
Let me know if you have any questions or feedback, and of course feel free to submit suggestions.
Thank you for your time.
41+|-
42+! Address type !! Vulnerable !! Prefix !! Example
43+|-
44+| P2PK || Yes || 04 || 0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d4e0a604f8141781e62294721166bf621e73a82cbf2342c858ee
45+|-
46+| P2PKH || No || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
It might be worth discussing the conditions under which P2PKH is vulnerable in more detail. While the Deloitte report covers this, this table leaves the impression that P2PKH is safe.
0| P2PKH || No (trusted miner) || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
1| P2PKH (reused) || No || 1 || 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
28+
29+Mining may one day be vulnerable to disruption by very advanced quantum computers making use of Grover's algorithm. However, Grover's [https://arxiv.org/pdf/1902.02332 scales very poorly] compared to Shor's, requiring 10^40 quantum operations in comparison to 10^8 for running Shor's over ECC. It's for this reason that the primary threat to Bitcoin by quantum computers is to its signature algorithm and not Proof of Work, hence the focus on a new address format.
30+
31+The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack.
32+
33+Ordinarily, when a transaction is signed, the public key can be recovered from the signature. This makes a transaction submitted to the mempool vulnerable to quantum attack until it's mined. One way to mitigate this is to submit the transaction directly to a mining pool, which bypasses the mempool. This process is known as an out-of-band transaction. The mining pool must be trusted not to reveal the key to attackers.
It’s also been added to the new table for scenarios for revealed public keys on bitcoin.
24+
25+=== Motivation ===
26+
27+This proposal aims to improve the quantum resistance of bitcoin's signature security should the Discrete Logarithm Problem (DLP) which secures Elliptic Curve Cryptography (ECC) no longer prove to be computationally hard, likely through quantum advantage by Cryptographically-Relevant Quantum Computers (CRQCs). [https://arxiv.org/pdf/quant-ph/0301141 A variant of Shor's algorithm] is believed to be capable of deriving the private key from a public key exponentially faster than classical means. The application of this variant of Shor's algorithm is herein referred to as quantum key decryption. Note that doubling the public key length, such as with a hypothetical secp512k1 curve, would only make deriving the private key twice as hard. The computational complexity of this is investigated further in the paper, [https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specifications-on-reaching ''The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime''].
28+
29+Mining may one day be vulnerable to disruption by very advanced quantum computers making use of Grover's algorithm. However, Grover's [https://arxiv.org/pdf/1902.02332 scales very poorly] compared to Shor's, requiring 10^40 quantum operations in comparison to 10^8 for running Shor's over ECC. It's for this reason that the primary threat to Bitcoin by quantum computers is to its signature algorithm and not Proof of Work, hence the focus on a new address format.
I completely agree with your claim that:
It’s for this reason that the primary threat to Bitcoin by quantum computers is to its signature algorithm and not Proof of Work, hence the focus on a new address format.
The math in the footnote is for finding SHA256 preimages, but the text and cited article discusses Bitcoin mining/POW which is only a partial preimage, e.g. find SHA256 output with 75 zeros in front. These partial preimages should be not as hard as finding a full SHA256 preimage.
The quantum safety of Bitcoin POW is a an open question. Is a quantum computer than can do the POW significantly faster than a classic miner an attack or simply better mining technology? Are there other quantum attacks on Bitcoin mining?
I would frame this as symmetric cryptography in Bitcoin, such as preimages in the transactions Merkle tree, rather than mining.
log2_work message from Bitcoin Core in the latest block… Let me know if that’s not right.
Log2 work is the total work from the genesis block all the way to that current block not a measure of work of that block alone.
Bitcoin PoW per hash is ~700 Exahash/second. That roughly $log2(700 * 10^{18} )=2^{68.2}$ per second and $2^{74.5}$ per block. 75 zero bits would more the accurate current number.
There is a big difference between the cost of preimages on SHA256 and HASH160 with a quadratic reduction: SHA256 as you point out is $2^{128} \approx 10^{40}$ but HASH160 used in P2PKH is $2^{80} \approx 10^{24}$. Still much larger than ECC, but I wanted to call this out because it is unlikely we will ever build a computer classical or quantum that can do $2^{128}$ within the next 100 years whereas Bitcoin currently does $2^{80}$ every 30 minutes.
If I didn’t misunderstand “Applying Grover’s Algorithm to Hash Functions” the cost of a groover preimage attack on a n-bit hash function where you are trying to want to find 1 preimage out of a set of k preimages is $\sqrt{2^{n-\log2{(k)}}}$. Let’s say we are looking for any preimage of a P2PKH output. As of Sept 29 2024 there are 53,102,992 P2PKH in Bitcoin’s UTXO set. This gets us an attack cost of $\sqrt{2^{160-25.66}}=2^{67.17} \approx 10^{20}$.
All of this still supports your argument that the current pressing need in Bitcoin is ECC. It worth having tighter bounds, so we know when we are in danger for the symmetric side of Bitcoin.
I’ve published some more updates you can see here:
Also, is P2WPKH not also as vulnerable as P2PKH? I think they both use HASH160, do they not?
Yes P2WPKH, P2PKH, P2SH all use HASH160 (20 Byte) whereas P2WSH uses SHA256 (32 Byte).
Thanks for the updates and making the changes. My main concern is that if precise numbers are going to be used for Bitcoin and Groovers I want to avoid a situation where the numbers are not representative of the threat. I suspect many people in Bitcoin will use this BIP to educate themselves on quantum attacks. I’ll write up a longer comment during my lunch break today.
I realize by pointing out the nuances I’ve accidentally caused this section to grow into two large paragraphs, when really all you are trying to do make is the reasonable point that quantum attacks on ECC signatures should be the most immediate concern.
Here is my attempt to get the same point across but without having to get into the details:
The primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its uses of ECC (Ecliptic Curve Cryptography) used in Bitcoin’s signatures and Taproot commitments]. This is because Shor’s algorithm enables a CRQC to break the cryptographic assumptions of ECC in roughly 10^8 ≈ 2^26) quantum operations. While a QRQC could use Grover’s algorithm to gain a quadratic speed up on brute force attacks on the hash functions used in Bitcoin, a significantly more power quantum computer is needed for these attacks to meaningfully impact Bitcoin. For instance a preimage attack on HASH160 using Grover’s algorithm would require at least 10^24 ≈ 2^80 quantum operations.
It does make sense to discuss Grover’s algorithm w.r.t. multi-target preimage attacks against P2SH and P2PKH when discussing the security of address types against a QRQC.
230+To help implementors understand updates to this BIP, we keep a list of substantial changes.
231+
232+* 2024-06: High level rough draft
233+* 2024-07: Additional algorithms in PQC table
234+* 2024-08: Add FALCON signatures, update to use NIST standard terminology, add public key sizes.
235+* 2024-09: Additional detail on P2QS. Deprecate P2QR. Postpone SQIsign. Add details on quitness.
A few non-urgent nits regarding the changelog:
(See https://keepachangelog.com and https://www.gnu.org/prep/standards/html_node/Style-of-Change-Logs)
29+Mining may one day be vulnerable to disruption by very advanced quantum computers making use of [https://en.wikipedia.org/wiki/Grover's_algorithm Grover's algorithm]. However, Grover's [https://arxiv.org/pdf/1902.02332 scales very poorly] compared to Shor's. Grover's potentially requires roughly 10^40 quantum operations in comparison to 10^8 for running Shor's over ECC, should no optimization for partial preimages be needed. Partial preimage optimization may lower the difficulty to find a block than the full 256-bit preimage (say, for a number with 75 zero bits in front).<ref>See [https://quantumcomputing.stackexchange.com/a/12847 Sam Jaques on Bitcoin mining].</ref> Regardless of such optimizations, the primary threat to Bitcoin by CRQCs is [https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin#QC_attacks generally considered to be to its signature algorithm] and not necessarily Proof of Work, hence the focus on a new address format. Additionally, should quantum mining demonstrate quantum advantage over ASIC miners, miners will transition to operating CRQCs instead.<ref>Grover's algorithm is a quadratic speedup, so instead of 2^256 tries it takes about 2^128 calls to the oracle (which is about 10^38 operations) to get a 256 bit preimage. The number of gates would be some multiple of that number. That's roughly how we get the correct order of magnitude, Mosca did a more finegrained calculation and land ballpark in similar large numbers. The number is so large, it's unclear the exact calculation with all the prefactors so far, contrary to ECC, which is roughly 10^8 operations, including the constant factors. A talk by [https://sam-jaques.appspot.com/papers Sam Jaques] gave some estimate of the size of the machine that would be necessary for Grover to attack hashes and it was a small astronomical body.</ref>
30+
31+It is worth mentioning that any addresses using RIPEMD160 / HASH160 could also be vulnerable to Grover's algorithm.<ref>There is a big difference between the cost of preimages on SHA256 and HASH160 with a quadratic reduction:
32+SHA256 is 2^128 ≈ 10^40 but HASH160 used in P2PKH and P2WPKH is 2^80 ≈ 10^24 quantum operations. This is much larger than ECC, and while it is unlikely a classical or quantum computer that can perform 2^128 within the next 100 years, Bitcoin currently does 2^80 classical operations every 30 minutes. Additionally, with Grover's, [https://bitcoin.stackexchange.com/a/115849/139611 a black box function could sidestep Shor's entirely, and SHA-256, providing the private key itself to a P2PKH or P2SH address.]</ref>
33+
34+The vulnerability of existing bitcoin addresses is investigated in [https://web.archive.org/web/20240715101040/https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html this Deloitte report]. The report estimates that in 2020 approximately 25% of the bitcoin supply is held within addresses vulnerable to quantum attack. As of the time of writing, that number is now closer to 20%.
Another vulnerability estimation in early 2019: 5M-10M bitcoin
typo fix
