Bitcoin verwendet für das Signieren von Transaktionen ein Elliptisches-Kurven-Kryptographie-Verfahren (ECDSA, Elliptic Curve Digital Signature Algorithm), das in der Krypto-Community oft als nicht Quantum-sicher gilt. In diesem Post erfahrt ihr, warum es eine Entwarnung in dieser Hinsicht gibt und Bitcoin grundsätzlich höchst wahrscheinlich Quantum-sicher ist.
Bis jetzt gibt es nur eine sehr beschränkte Anzahl von Quanten-Algorithmen, die wirklich eine Verbesserung im Vergleich zu normalen (klassischen) Computern bringen würden, der bekannteste ist der Shor-Algorithmus, der bereits 1994 vom amerikanischen Mathematiker Peter Shor konzipiert wurde und der genialste Quanten-Algorithmus überhaupt ist.
Der Shor-Algorithmus würde es tatsächlich ermöglichen, gängige Kryptographie-Verfahren wie RSA oder die in Bitcoin-genutzten ECDSA-Keys in kurzer Zeit zu knacken. Konkret wäre die Laufzeit nur polynomiell O(n^3), wobei n hier die Schlüssellänge in Bits angibt, was bedeuten würde, dass man die in Bitcoin verwendeten 256-Bit-Keys extrem effizient kompromittieren könnte. Dazu wären einige zig Millionen Quanten-Schritte notwendig. Auf klassischen Computern würde die Laufzeit hingegen explodieren.
Es gibt nur einen kleinen Haken. Es gibt keinen Quanten-Computer, der diesen Algorithmus ausführen könnte.
Der Weltrekord, eine Zahl mit einem Quanten-Computer zu faktorisieren liegt bei der Zahl 21, was einer 5-Bit Zahl (5 qubits) entspricht, und ein Trivialfall ist. 21 = 3 x 7.
2019 ist ein Versuch eine größere Zahl (die Zahl 35) zu faktorisieren bereits am Quanten-Noise gescheitert.
Mittlerweile gibt es auch theoretische Erkenntnisse, dass Quanten-Noise den Shor-Algorithmus unbrauchbar macht (Jin-Yi Cai. Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise. 2023).
Das Problem ist ähnlich wie beim Grover-Algorithmus, die extrem heftigen mathematischen Annahmen über die Realität. Damit der Algorithmus funktionieren würde, bräuchte man etwa 6n logische qubits (1500 qubits) und zig Millionen Quanten-Gates (O(n^3)).
Die Superposition aller qubits müsste über zig Millionen-Schritte erhalten bleiben.
Dazu würde der interne State bei so vielen überlagerten und interagierenden qubits wieder ein gigantisches Ausmaß erreichen und größer sein als die Anzahl der Atome im Universum (10^80).
Der Algorithmus nimmt weiter an, dass das Universum mit einer unendlichen Genauigkeit (Auflösung der komplexen Wellenfunktion) rechnet und über Tausende qubits und Millionen Gates skaliert, was anscheinend nicht der Fall ist.
In der Natur dürfte es sehr viele Cutoffs geben, über Dekohärenz (das Kollabieren der Superposition) würde die Natur das Anwachsen der Komplexität in extrem absurde Ausmaße wahrscheinlich unterbinden, wobei dieser Vorgang in der Physik noch ziemlich unerklärt ist. Man weiß nicht, was Dekohärenz wirklich ist und wodurch sie genau ausgelöst wird. Früher dachte man, dass man dazu einen intelligenten Beobachter (mit einem Bewusstsein) bräuchte, mittlerweile gibt es Anzeichen, dass bereits die Interaktion mit anderen Teilchen zu Dekohärenz führen kann.
Kurz gesagt, der Algorithmus ist eine mathematische Meisterleistung, kann aber in der Realität nicht ausgeführt werden.
Meiner Meinung nach muss man sich wegen Quanten-Computern daher keine allzu großen Sorgen machen, allerdings wäre es möglich, dass auch ein viel schnellerer, klassischer Algorithmus gefunden wird, der Zahlen faktorisiert oder das Diskrete-Logarithmus-Problem von ECDSA-Keys löst. Der Speedup des Shor-Algorithmus kommt nämlich nicht nur vom Quanten-Computer selbst, sondern weil dieser auch die mathematische Struktur des Problems geschickt ausnutzt.
Es gibt aber noch ein weiteres cooles Security-Feature der Bitcoin-Blockchain, die Keys sind gehasht auf der Blockchain und werden erst, wenn eine Transaktion abgeschickt wird, preisgegeben, was einen möglichen Angriff auf nur gerade aktive Transaktionen beschränken würde.
Was sagt ihr dazu? Denkt ihr, dass Quanten-Computer eine Bedrohung für Bitcoin & Co. sind oder ist die Gefahr in Wirklichkeit übertrieben, da (sinnvolle) Quanten-Computer physikalisch höchst wahrscheinlich unrealistisch sind?
Shor's Algorithm
AI-generated illustration (Copilot)
https://en.wikipedia.org/wiki/Shor%27s_algorithm
https://x.com/vikisecretscom/status/1919344986522333357
Shor's discrete logarithm quantum algorithm for elliptic curves
https://arxiv.org/abs/quant-ph/0301141
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
https://arxiv.org/abs/2306.10072
Factoring using 2n+2 qubits with Toffoli based modular multiplication
https://arxiv.org/abs/1611.07995
Bitcoin: Elliptic Curve Secp256k1
https://en.bitcoin.it/wiki/Secp256k1
How many logical qubits are needed to run Shor's algorithm efficiently on large integers (n>2^1024)?
Why Bitcoin Mining (SHA-256) is post Quantum-safe (if Quantum Computer existed)
@vikisecrets/why-bitcoin-mining-sha256-is-post-quantumsafe-if-quantum-computer-existed-axu
Do (useful) Quantum Computers exist at all? Best mathematical explanation of Grover's algorithm so far by 3Blue1Brown.
English
Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) to sign transactions, which is often considered to be non-quantum secure in the crypto community. In this post, you will learn why there is most likely an all-clear in this regard and why Bitcoin is fundamentally quantum-safe.
So far, there are only a very limited number of quantum algorithms that would really bring an improvement compared to normal (classical) computers, the best known being Shor's algorithm, which was conceived by the American mathematician Peter Shor back in 1994 and is the most brilliant quantum algorithm so far.
The Shor algorithm would actually make it possible to crack common cryptographic methods such as RSA or the ECDSA keys used in Bitcoin in a short time. Specifically, the runtime would only be polynomial O(n^3), where n is the key length in bits, which would mean that the 256-bit keys used in Bitcoin could be compromised extremely efficiently. This would require "only" tens of millions of quantum steps. On conventional computers, on the other hand, the runtime would explode and be infeasible.
There is just one small catch. There is no quantum computer that could execute this algorithm.
The world record for factoring a number with a quantum computer is the number 21, which corresponds to a 5-bit number (5 qubits) and is a trivial case. 21 = 3 x 7.
In 2019, an attempt to factorize a larger number (the number 35) already failed due to quantum noise.
There are now also theoretical findings that quantum noise renders Shor's algorithm basically useless (Jin-Yi Cai. Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise. 2023).
The problem is similar to the Grover's algorithm, the extremely crazy mathematical assumptions about reality. For the algorithm to work, you would need about 6n logical qubits (1500 qubits) and tens of millions of quantum gates (O(n^3)).
The superposition of all qubits would have to be maintained over tens of millions of steps.
With so many superimposed and interacting qubits, the internal state would again reach a gigantic scale and be larger than the number of atoms in the universe (10^80).
The algorithm also assumes that the universe calculates with infinite precision (resolution of the complex wave function) and scales over thousands of qubits and millions of gates, which is apparently not the case.
In reality, there could be many cut-offs, nature would probably prevent the growth of complexity to extremely absurd proportions via decoherence (the collapse of the superposition), although this process is still quite unexplained in physics. It is not known what decoherence really is and what exactly triggers it. Originally it was thought that an intelligent observer (with a consciousness) was needed, but there are now signs that even interactions with other particles can lead to decoherence.
In short, the algorithm is a mathematical masterpiece, but cannot be executed in reality.
In my opinion, there is no need to worry too much about quantum computers, but it is possible that a much faster classical algorithm could be found that factorizes numbers or solves the discrete logarithm problem of ECDSA keys. The speedup of Shor's algorithm comes not only from the quantum computer itself, but also because it cleverly exploits the mathematical structure of the problem.
But there is another cool security feature of the Bitcoin blockchain: the keys are hashed on the blockchain and are only revealed when a transaction is sent, which would limit a possible attack to only currently active transactions.
What do you think? Do you think that quantum computers are a threat to Bitcoin & Co. or is the danger actually exaggerated, as (useful) quantum computers are most likely not real?