Grover vs Shor: why hashes are not the problem for bitcoin
Every conversation about quantum computers and bitcoin ends up naming two algorithms. One of them, Shor's, is the reason the topic exists at all. The other, Grover's, is often listed next to it as if it were a second threat of the same size. It is not. Shor turns a hard problem into an easy one. Grover makes a brute-force search somewhat shorter. That difference is why a public key on the chain matters and a hash on the chain does not, and it is the rule our scanner is built on. This article goes through what each algorithm does, what the published numbers say, and where the honest caveats are.
The short version. Shor's algorithm solves the discrete logarithm problem efficiently, so a large error-corrected quantum computer could turn a visible public key into its private key. Grover's algorithm only speeds up unstructured search, by a square root: a search over 2160 possibilities becomes roughly 280 steps, and those steps have to run one after another. That is not a practical attack on a bitcoin address hash, on SHA-256, or on mining. It has also been proven that no quantum algorithm does fundamentally better on this kind of search. So the question for your coins is whether the public key is visible, not whether the hash could be reversed.
Two algorithms, two kinds of problem
Bitcoin relies on two different kinds of cryptography, and each has its own quantum algorithm aimed at it.
- Signatures use elliptic curve cryptography on the secp256k1 curve. Your private key is a number; your public key is a point on the curve derived from it. Going forward is cheap. Going backwards, from the point to the number, is the discrete logarithm problem, and classical computers have no efficient way to solve it.
- Hashes are one-way functions with no structure to exploit. Addresses commit to a hash of a key or a script, SegWit and Taproot commit to hashes of scripts, and mining is a search for a block header whose double SHA-256 hash falls under a target.
Peter Shor's 1994 paper, later posted to arXiv, attacks the first kind. Lov Grover's 1996 paper, “A fast quantum mechanical algorithm for database search”, is the general tool people point at the second kind. They are not two versions of the same attack. They differ in kind, and the gap between them is enormous.
What Shor does to a public key
Shor's paper gives quantum algorithms for factoring and for discrete logarithms that run in a number of steps polynomial in the size of the input. In plain terms, doubling the key size makes the problem a few times harder, not astronomically harder. That is what “breaks” means here. Classically, recovering a 256-bit elliptic curve key is out of reach; with Shor on a large enough machine it becomes a computation of fixed, finite size.
How large is large enough? The most cited gate-level estimate is Roetteler, Naehrig, Svore and Lauter (2017). They bound the cost for an elliptic curve over an n-bit prime field at 9n + 2⌈log2n⌉ + 10 qubits and a circuit of at most 448n3log2n + 4090n3 Toffoli gates. For a 256-bit field, the size Bitcoin uses, that works out to at most 2,330 qubits and about 1.3 × 1011 Toffoli gates. Those are logical qubits, each of which would have to be built from many physical qubits with error correction. No machine today runs this circuit, and we do not put a date on when one could. Later work has revised these figures. What matters here is the shape: the cost is finite and grows slowly as keys get longer.
The input Shor needs is the public key. If the key is on the chain, the attack has everything it needs. If only a hash of the key is on the chain, Shor has nothing to start from. BIP-360 frames the threat the same way: its motivation section describes Shor's algorithm deriving private keys from public keys, and splits attacks into long exposure (keys that sit visible on the chain) and short exposure (keys visible only while a spend waits in the mempool).
What Grover does to a hash
Grover's algorithm solves a much more general problem: find the one input, among N possibilities, that makes some check succeed, when there is no structure to guide you. Classically you try candidates one by one and need about N/2 tries on average. Grover's abstract puts the quantum cost at O(√N) steps.
A square root sounds dramatic until you write it in bits. It halves the exponent:
| Target | Where Bitcoin uses it | Classical brute force | With Grover |
|---|---|---|---|
| 160-bit hash (HASH160) | P2PKH 1…, P2SH 3…, P2WPKH bc1q… | about 2160 | about 280 sequential iterations |
| 256-bit hash (SHA-256) | P2WSH, the proposed P2MR | about 2256 | about 2128 sequential iterations |
And it cannot be improved much further. In 1997 Bennett, Bernstein, Brassard and Vazirani proved that, for this kind of unstructured search, no quantum algorithm can do fundamentally better than the square root, and they note that Grover's result makes the bound tight. NIST's report on post-quantum cryptography (NISTIR 8105) draws the practical conclusion for symmetric ciphers and hashes: if Grover ever matters, “doubling the key size will be sufficient to preserve security.” Its summary table lists SHA-2 and SHA-3 as needing larger output, not replacement. Elliptic curve signatures, in the same table, are listed as no longer secure.
Why the square root is not enough
The table already looks reassuring, but it flatters the attacker in three ways.
The steps are sequential. Grover's iterations have to run one after the other on the same quantum state. NIST's call for post-quantum proposals makes the point directly: Grover requires a long-running serial computation, and in a realistic attack one has to run many smaller instances in parallel, which makes the speedup less dramatic. The same document suggests that envisioned quantum architectures might perform around 240 logical gates in sequence per year. Even if each Grover iteration cost a single gate, which it does not, 280 iterations at that rate is 240 years, more than a trillion. That is our arithmetic on NIST's figure, and it is a floor, not an estimate.
Parallel machines help only a little. Splitting a Grover search across many quantum computers does not divide the time by the number of machines, as it would for classical brute force. The search space shrinks for each machine, but each still pays the square root of its share. A million machines buy roughly a thousandfold speedup, not a millionfold one. NIST cites Zalka's 1999 proof that Grover's algorithm is optimal for this.
Each step is expensive. To steal coins from a hashed address, an attacker does not need any input that hashes to the target. They need a private key whose public key hashes to the target, because the spend must carry a valid signature. So every Grover iteration would have to run an elliptic curve multiplication, a SHA-256 and a RIPEMD-160 inside the quantum circuit, then undo them. The elliptic curve part alone is the same kind of arithmetic that dominates the cost of Shor's circuit, repeated at every one of the 280 steps.
Put together, a Grover attack on an address hash is not a smaller version of a Shor attack on a public key. It is a different order of problem, and on every published estimate it is not a practical one.
Collisions, and why P2WSH is 32 bytes
There is one place where hash length has already been an issue, and it is worth getting right because it is often mixed up with the quantum question. A preimage attack looks for an input that matches a given hash; that is what stealing from someone else's address would need. A collision attack looks for any two inputs with the same hash, which is far cheaper: about 280 work for a 160-bit hash, even classically.
Collisions matter only when someone else helps write your script, for example a multi-party contract where a dishonest participant could search for two scripts with the same address, one of which they alone can spend. BIP-141 gives this as the reason P2WSH uses a 32-byte hash instead of P2SH's 20 bytes: 280 work is no longer infeasible, and by the end of 2015 Bitcoin mining had already computed about 284 hashes. BIP-360 states that its P2MR output, like P2WSH, gives 128 bits of collision resistance and 256 bits of preimage resistance.
Quantum algorithms for collisions exist. Brassard, Høyer and Tapp (1997) find collisions with fewer function evaluations than classical methods, but they need a large memory to do it. Bernstein (2009) analysed the cost and concluded the algorithm has a fundamentally worse price-performance ratio than classical parallel collision search, even under optimistic assumptions about quantum hardware. So the collision concern is real but classical, it applies to shared scripts, and it was addressed by the 32-byte formats. It is not a reason to worry about a single-signature address.
What about mining?
Mining is a search for a nonce that brings a hash under a target, which looks like a textbook Grover problem. Aggarwal, Brennen, Lee, Santha and Tomamichel (2017) studied it and found Bitcoin's proof-of-work relatively resistant to substantial quantum speedup, mainly because specialised mining chips are extremely fast compared with the estimated clock speed of near-term quantum computers. A square-root advantage in the number of steps does not help if each step is millions of times slower. The same paper found the elliptic curve signatures much more at risk, which is the Shor side again.
Mining also adjusts. If any miner, quantum or not, became faster, difficulty would rise to match. That changes who earns the rewards; it does not let anyone take coins from an address.
What this means for your coins
The practical rule follows directly. A coin is exposed to a long exposure quantum attack when its public key is visible on the chain, and not when only a hash is. That is why the line runs where it does:
- Hashed address, never spent from: only a hash is on the chain. Grover does not change that in practice.
- Hashed address that has spent: the spend published the key, so any coins still there sit on a visible key. This is how address reuse turns safe coins into exposed ones.
- Taproot: the output is a tweaked public key, visible from the moment it receives. We explain why in are Taproot addresses quantum vulnerable.
- Pay-to-public-key: the oldest coins were paid straight to a key, with no hash at all. See P2PK: Satoshi's coins and quantum computers.
Two caveats keep this honest. First, a hash protects the key only while the key stays off the chain and out of other people's hands: an extended public key you shared, or the same key used behind another address format, can reveal it. Second, every spend reveals the key for the minutes it waits to confirm. That short exposure window is not something a hash can fix; it needs post-quantum signatures, which BIP-360 says it intends to leave to a separate proposal. Our first article covers both kinds of exposure, and what a quantum attack on bitcoin would actually look like walks through each one step by step.
For scale, BIP-361, a draft proposal, states that over 34% of all bitcoin had a revealed public key as of 1 March 2026. All of that is on the Shor side of the line. None of it is there because of Grover.
See which side of the line your coins are on
Paste an address, or an extended public key for a whole wallet, and ShorWatch checks whether each address shows only a hash or has its public key on the chain, and shows the balance on each side. It runs in your browser against public chain data from mempool.space. Nothing is sent to us and nothing is stored.
Scan an addressRead-only · Non-custodial · Nothing stored · No account needed
Limits. The scanner reports exposure at rest from public chain data: whether a public key is already visible on the chain. It treats a hash as protecting the key, for the reasons above; it does not, and cannot, assess whether a key leaked off the chain or through another address format. It does not cover pre-2011 pay-to-public-key outputs; it treats any multisig script address as opaque until it spends; and it cannot see coins held on an exchange or a custodial wallet in someone else's addresses. It is an informed first pass, not an audit, and not financial or security advice. Alerts, where offered, detect activity; they cannot block it. The qubit and gate figures are upper bounds from Roetteler et al. (2017) and have been revised by later work; the 240 gates per year figure is NIST's preliminary guidance from 2016, and the year count derived from it is our arithmetic. The 34% figure is from BIP-361, a draft, as published at the time of writing.