Why Bitcoin Mining (SHA-256) is post Quantum-safe (if Quantum Computer existed)

Bitcoin Mining verwendet einen Proof-Of-Work Mining Algorithmus, der auf der SHA-256 Hashfunktion basiert. Miner müssen zu jedem Block einen bestimmten SHA-256 Hash finden, indem sie eine große Anzahl von Zahlen (Nonces) per Brute-Force probieren, bis sie einen passenden Hash finden, der die Difficulty-Vorgabe (Target) entspricht. Konkret bedeutet das, einen Hash zu finden, der eine bestimmte vorgegebene Anzahl von führenden 0-Bits entspricht.

Die Befürchtung ist, dass Quanten-Computer die Sicherheit von Bitcoin gefährden könnten.

Die gute Nachricht, mit großer Wahrscheinlichkeit wäre SHA-256 Post-Quantum-Computer-sicher.

Selbst wenn Quanten-Computer mit 256 logischen qubits existieren würden, man die SHA-256 Funktion in Quantum-Gates nachbauen und den Grover-Algorithmus anwenden könnte, wären Quanten-Computer immer noch zu langsam.

Der Speedup wäre eher im Bereich O(sqrt(N)), das würde bedeuten, dass der Grover-Algorithmus O(2^128) Schritte benötigen würde, was immer noch eine unglaublich große Zahl ist. Größenordnung 10^38.

Dazu kommen alle anderen heftigen Annahmen, die notwendig wären, damit das überhaupt funktionieren würde. Zum Beispiel müsste die Superposition über alle 2^128 Schritte erhalten bleiben, was extrem unwahrscheinlich ist. Weiters müsste die Auflösung der Wavefunction enorm hoch sein und würde vermutlich bereits unter der Planck-Länge liegen. Weiters dürfte es keinen Noise geben, der Quanten-Computer müsste 100% genau mit einer enormen Auflösung rechnen. Intern würde der State-Vektor ein gigantisches Ausmaß erreichen (2^256) und bereits etwa so groß sein, wie die Anzahl an Atomen im Universum (10^80). Und dann kommt noch der Faktor Zeit. Selbst bei extrem optimistischen Annahmen würde der Quanten-Computer dafür länger brauchen als das Universum existiert hat.

In der Realität würde es wahrscheinlich schon an der Umsetzung des SHA-256 Algorithmus in Quanten-Gates scheitern.

Alles in allem dürfte SHA-256 Quanten-Computer sicher sein. Anders sieht es bei den Keys aus, die Bitcoin verwendet, aber auch da gibt es eine Entwarnung, die ich euch in einem Folge-Post erläutern werde.

Was sagt ihr dazu? Denkt ihr, dass Quanten-Comptuer eine Gefahr für Bitcoin sind? Sind (sinnvolle) Quanten-Computer überhaupt möglich oder wegen physikalischen Limits nicht realisierbar?

Is Bitcoin Mining (SHA-256) post Quantum Computer-safe?

Source: 3Blue1Brown

English

Bitcoin mining uses a proof-of-work mining algorithm based on the SHA-256 hash function. Miners must find a specific SHA-256 hash for each block by trying a large number of numbers (nonces) using brute force until they find a matching hash that corresponds to the difficulty specification (target). In concrete terms, this means finding a hash that corresponds to a certain specified number of leading 0 bits.

The fear is that quantum computers could jeopardize the security of Bitcoin.

The good news is, most probably, SHA-256 would be post-quantum-computer safe.

Even if quantum computers with 256 logical qubits existed, the SHA-256 function could be replicated in quantum gates and the Grover algorithm could be applied, quantum computers would still be too slow.

The speedup would be more in the range of O(sqrt(N)), which would mean that the Grover algorithm would require O(2^128) steps, which is still an incredibly large number. Order of magnitude 10^38.

Add to that all the other hefty assumptions that would be necessary for quantum computers to work at all. For example, the superposition would have to be maintained over all 2^128 steps, which is extremely unlikely. Furthermore, the resolution of the wavefunction would have to be enormously high and would probably already be below the Planck length. Furthermore, there should be no noise, the quantum computer would have to calculate 100% accurately with an enormous resolution. Internally, the state vector would reach a gigantic size (2^256) and would already be about as large as the number of atoms in the universe (10^80). And then there is the time factor. Even under extremely optimistic assumptions, the quantum computer would need longer than the universe has existed.

In reality, the implementation of the SHA-256 algorithm in quantum gates would already fail.

All in all, SHA-256 should be quantum computers safe. The situation is different for the keys used in Bitcoin, but there is an all-clear here too, which I will explain in a follow-up post.

What do you think? Do you think that quantum comptuers are a threat to Bitcoin? Are (useful) quantum computers even possible or not feasible due to physical limitations?

Posted Using INLEO