<p>We <a href="https://crypto.stackexchange.com/questions/102574/could-grovers-algorithm-perform-a-search-in-n-2-for-a-match-in-a-particular-sub">could design a black box function</a> to break both P2PKH and P2SH (and P2WSH, etc.) addresses in 2^80 single-threaded quantum computer cycles.
Assuming a clock speed on scale of GHz, this would take about 10 million years.
Important to note is that splitting the work and doing it in parallel is not as beneficial as with classic computers because it would offer only a quadratic speedup (<a href="https://eprint.iacr.org/2017/811.pdf" rel="nofollow noreferrer">Fluhrer, S., Reassessing Grover's Algorithm</a>).
In other words, doing the work in 1 year would require building 100 trillion quantum computers because <code>sqrt(100T) == 10M</code>.
Therefore, we can say that breaking a 160-bit hash preimage is physically possible because 10M years is a finite amount of time and less than age of the universe.
However, it is still infeasible.</p>
<h3>Breaking P2PKH</h3>
<p>Output locking script template is:</p>
<p><code>OP_DUP OP_HASH160 OP_DATA_20 pubkey-hash-20 OP_EQUALVERIFY OP_CHECKSIG</code></p>
<p>so cracking it with a hypothetical quantum computer would require running <a href="https://en.wikipedia.org/wiki/Grover%27s_algorithm" rel="nofollow noreferrer">Grover's algorithm</a> to find some <code>x</code> such that <code>hash160(x) == pubkey-hash-20</code>.
Once we'd find <code>x</code>, we'd then apply a much easier <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow noreferrer">Shor's algorithm</a> to find the secret key.
The revealed keypair would most likely not be the original keypair, however it wouldn't really matter since the key authentication part of the Script would evaluate to true for any key that would satisfy <code>hash160(x)=pubkey-hash-20</code>.</p>
<h3>Breaking P2SH</h3>
<p>Output locking script template is:</p>
<p><code>OP_HASH160 OP_DATA_20 redeem-script-hash-20 OP_EQUAL</code></p>
<p>however the actual redeem script will be evaluated after authentication against the hash, and it must also pass validation.
Therefore, finding any random <code>x</code> such that <code>hash160(x) == redeem-script-hash-20</code> won't do, because it will most likely be an invalid redeem script.
To address this, we could perform a Grover's search for a particular template.
We'd do that by designing a function like <code>f(x) = 0x21 || x || 0xac</code> and then crack the composite function <code>hash160(f(x))</code> as our black box function.
The raw bytes appended with <code>x</code> in <code>f(x)</code> definition will make our redeem script match the pay-to-public-key (P2PK) template:</p>
<p><code>OP_DATA_33 x OP_CHECKSIG</code>.</p>
<p>With Grover's algorithm we'd find <code>x</code> that satisfies <code>hash160(f(x)) = redeem-script-hash-20</code>, and then we'd apply Shor's algorithm to crack the secret key of <code>x</code>.
Finally, we could then spend the funds with the public key, signature, and the P2PK redeem script (<code>redeem-script=f(x)</code>).</p>
<p>The discovered redeem script would most likely not be the original redeem script, however it wouldn't really matter since the redeem script authentication part would evaluate to true for any redeem script that would satisfy <code>hash160(redeem-script)=redeem-script-hash-20</code>.</p>
<h2>Afterthoughts / potential optimization</h2>
<p>I think we could optimize it by embedding public key generation as another function in the composite so we won't need Shor's algorithm at all, because we'd find the secret key directly:</p>
<ol>
<li>Define a function <code>g(x)=p</code> that maps a secret key to a public key.</li>
<li>Run Grover's on <code>hash160(f(g(x))) = redeem-script-hash-20</code></li>
</ol>
<p>some matching <code>x</code> will be a secret key that satisfies all the requirements, then we compute <code>g(x)</code> to get the public key, then <code>f(g(x))</code> to get the redeem script, which will be acceptable way to spend because the hash will match that of the address.</p>

CC BY-SA 4.0
2022-11-04T08:44:42.560Z
2022-11-04T11:13:40.140Z
2022-11-04T11:13:40.140Z
bca-0353f40e
<p>It is well understood that quantum computers could make finding 256-bit hash-collisions feasible, and that they could break elliptic-curve public key encryption currently used in Bitcoin. It is also well understood that 160-bit addresses are not collision-resistant, however that is not really a problem for common applications (P2PKH).</p>
<p>What about addresses where the public key was never revealed, would they be safe at rest? Currently HASH160 addresses have 160-bits of security against preimage attacks, but QCs could theoretically bring it down to 80 bits which would be in the &quot;danger zone&quot;.</p>
<p>A successful preimage attack would not necessarily yield the original public key, but in the scenario where QCs would be capable of cracking 160-bit hash preimages then they could also trivially find a private key of whatever public key the preimage attack would yield, so some sort of constrained-size quantum preimage search would do?</p>
<p>The only literature I found discussing this is <a href="https://link.springer.com/chapter/10.1007/978-3-319-45741-3_11#Sec19" rel="nofollow noreferrer">this multi-breakage</a> section in <a href="https://link.springer.com/chapter/10.1007/978-3-319-45741-3_11" rel="nofollow noreferrer">Giechaskiel, I., Cremers, C., Rasmussen, K.B. (2016). On Bitcoin Security in the Presence of Broken Cryptographic Primitives</a>.</p>

CC BY-SA 4.0
2023-04-02T00:13:44.773Z
It is worth noting that modern cutting edge quantum computers that would be able to handle such computations efficiently have not even acquired up to 100 qbits (source: https://www.youtube.com/watch?v=d_5u2qdKoUU) and at this barrier they cannot even break low bitlength RSA ciphers. There is probably a REALLY long time before this becomes a relevant threat, nevertheless I love the idea to protect against it. So go on with that please.
Poseidon
<address><quantum-computing>
Post-quantum preimage resistance of HASH160 addresses
bca-0353f40e
# Post-quantum preimage resistance of HASH160 addresses

(Asked by: username_0 on 2022-10-31)

It is well understood that quantum computers could make finding 256-bit hash-collisions feasible, and that they could break elliptic-curve public key encryption currently used in Bitcoin. It is also well understood that 160-bit addresses are not collision-resistant, however that is not really a problem for common applications (P2PKH).

What about addresses where the public key was never revealed, would they be safe at rest? Currently HASH160 addresses have 160-bits of security against preimage attacks, but QCs could theoretically bring it down to 80 bits which would be in the "danger zone".

A successful preimage attack would not necessarily yield the original public key, but in the scenario where QCs would be capable of cracking 160-bit hash preimages then they could also trivially find a private key of whatever public key the preimage attack would yield, so some sort of constrained-size quantum preimage search would do?

The only literature I found discussing this is [this multi-breakage](https://link.springer.com/chapter/10.1007/978-3-319-45741-3_11#Sec19) section in [Giechaskiel, I., Cremers, C., Rasmussen, K.B. (2016). On Bitcoin Security in the Presence of Broken Cryptographic Primitives](https://link.springer.com/chapter/10.1007/978-3-319-45741-3_11).

**Tags:** address, quantum-computing

> **Comments:**
> **username_1**: It is worth noting that modern cutting edge quantum computers that would be able to handle such computations efficiently have not even acquired up to 100 qbits (source: https://www.youtube.com/watch?v=d_5u2qdKoUU) and at this barrier they cannot even break low bitlength RSA ciphers. There is probably a REALLY long time before this becomes a relevant threat, nevertheless I love the idea to protect against it. So go on with that please.  

---

## 1 answers

### Answer by username_0 on 2022-11-04. Score: 0 | Accepted answer

We [could design a black box function](https://crypto.stackexchange.com/questions/102574/could-grovers-algorithm-perform-a-search-in-n-2-for-a-match-in-a-particular-sub) to break both P2PKH and P2SH (and P2WSH, etc.) addresses in 2^80 single-threaded quantum computer cycles.
Assuming a clock speed on scale of GHz, this would take about 10 million years.
Important to note is that splitting the work and doing it in parallel is not as beneficial as with classic computers because it would offer only a quadratic speedup ([Fluhrer, S., Reassessing Grover's Algorithm](https://eprint.iacr.org/2017/811.pdf)).
In other words, doing the work in 1 year would require building 100 trillion quantum computers because `sqrt(100T) == 10M`.
Therefore, we can say that breaking a 160-bit hash preimage is physically possible because 10M years is a finite amount of time and less than age of the universe.
However, it is still infeasible.

### Breaking P2PKH

Output locking script template is:

`OP_DUP OP_HASH160 OP_DATA_20 pubkey-hash-20 OP_EQUALVERIFY OP_CHECKSIG`

so cracking it with a hypothetical quantum computer would require running [Grover's algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm) to find some `x` such that `hash160(x) == pubkey-hash-20`.
Once we'd find `x`, we'd then apply a much easier [Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm) to find the secret key.
The revealed keypair would most likely not be the original keypair, however it wouldn't really matter since the key authentication part of the Script would evaluate to true for any key that would satisfy `hash160(x)=pubkey-hash-20`.

### Breaking P2SH

Output locking script template is:

`OP_HASH160 OP_DATA_20 redeem-script-hash-20 OP_EQUAL`

however the actual redeem script will be evaluated after authentication against the hash, and it must also pass validation.
Therefore, finding any random `x` such that `hash160(x) == redeem-script-hash-20` won't do, because it will most likely be an invalid redeem script.
To address this, we could perform a Grover's search for a particular template.
We'd do that by designing a function like `f(x) = 0x21 || x || 0xac` and then crack the composite function `hash160(f(x))` as our black box function.
The raw bytes appended with `x` in `f(x)` definition will make our redeem script match the pay-to-public-key (P2PK) template:

`OP_DATA_33 x OP_CHECKSIG`.

With Grover's algorithm we'd find `x` that satisfies `hash160(f(x)) = redeem-script-hash-20`, and then we'd apply Shor's algorithm to crack the secret key of `x`.
Finally, we could then spend the funds with the public key, signature, and the P2PK redeem script (`redeem-script=f(x)`).

The discovered redeem script would most likely not be the original redeem script, however it wouldn't really matter since the redeem script authentication part would evaluate to true for any redeem script that would satisfy `hash160(redeem-script)=redeem-script-hash-20`.

## Afterthoughts / potential optimization

I think we could optimize it by embedding public key generation as another function in the composite so we won't need Shor's algorithm at all, because we'd find the secret key directly:

1. Define a function `g(x)=p` that maps a secret key to a public key.
2. Run Grover's on `hash160(f(g(x))) = redeem-script-hash-20`

some matching `x` will be a secret key that satisfies all the requirements, then we compute `g(x)` to get the public key, then `f(g(x))` to get the redeem script, which will be acceptable way to spend because the hash will match that of the address.


---

