Preguntas y respuestas

Brassard-Høyer-Tapp (BHT) Algorithm and Bitcoin (BIP360)

Tamaño del texto

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 i.e. pre-existing P2SH addresses can't be retroactively collision-attacked even once the attack becomes feasible, because the attack requires a setup phase where both addresses are "rolled" by the attacker at the same time and before handing out one of them for some multi-party use. Shor and Grover are a bigger threat as those could be used to perform non-interactive attacks on old 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.

Seguir explorandoCatálogo de datosBuscar