nonoise₿itcoin

Background

When thinking about quantum computing, the focus is on Shor's algorithm impacting ECC, and to a lesser extent Grover's algorithm impacting hash functions.

If I understand correctly, Grover's algorithm can theoretically find a preimage with the square root of the operations of a classical computer, in other words the bits of security is cut in half (e.g. HASH160 addresses are reduced to 80 bits of security, and P2WSH addresses are reduced to 128 bits of security).

Since 128 bits is secure, SHA256 still appears secure in a world with Grover's algorithm.

Question

However I learned about the Brassard-Høyer-Tapp (BHT) algorithm as well, which is relevant to finding collisions. It seems that it could reduce the collision security of SHA256 from half the bits (birthday paradox) to one third of the bits, about 85 bits, which is below typical standards.

There is at least one context where a collision attack is relevant: in a collaborative multisignature scenario. In fact this scenario is what prompted P2WSH avoiding HASH160 (80 bits of collision security) and instead just use SHA256 (reference).

It's a bit of a niche issue (it seems to have been overlooked when designing P2SH) and I haven't seen mention of it in the post-quantum discussions. In fact, I wonder if the current version of proposed BIP 360 overlooks this, because the proposed P2TSH address follows BIP 173, using only 32 bytes (256 bits). But could this abstract issue warrant a larger address, like was done with P2WSH?

Grover's is related and some considerations were discussed here on Stackexchange, too.

We could design a black box function 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). 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.

If 2^80 is infeasible for a QC then 2^85 will be infeasible, too, assuming BHT is limited by the same square root scaling law.

The other implementation of Bitcoin produced some work on this, too. In Technical Bulletin - Bitcoin Cash Pay-to-Script-Hash (P2SH): Past, Present, and Future some of this was discussed. In 2023 BCH introduced P2SH32 for the same reason BTC introduced P2WSH (collision resistance). It suggested P2SH48 as the solution, but did not propose introducing it any time soon since network can't be surprised by 2^85 QC capability suddenly becoming available, and it's questionable whether it will ever be feasible.

The important thing here is that capability for a collision attack CAN NOT affect addresses created before the capability became available. P2SH wasn't at risk until ASICs became advanced enough that they could find a collision in less than a day and for less than $4M/collision (2022 estimate from the CHIP).

Shor and Grover are a bigger threat as those could be used to perform non-interactive attacks on addresses at rest. Successful attacks would reveal existence of capable enough QCs, and then maybe networks would need to consider 384-bit addresses.

The above bulletin suggests that practical Grover's implementation would have a cost greater than the bare number of cycles implies, and references a passage from Amy M. et. al. "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" (2016):

We showed that attacking SHA-256 requires approximately 2^153.8 surface code cycles and that attacking SHA3-256 requires approximately 2^146.5 surface code cycles. For both SHA-256 and SHA3-256 we found that the total cost when including the classical processing increases to approximately 2^166 basic operations. Our estimates are by no means a lower bound, as they are based on a series of assumptions.