How One Quantum Algorithm Could Destroy 90% of Blockchains

Quantum Computing

While every computing platform has advantages and disadvantages, in principle, almost anything can be used as a computing platform. Everything from the mechanical abacus to water-based circuits to the modern computer with electricity and semiconductors have been used to store and transform information. 

In that vein, quantum computing is a new type of computing platform that uses the quantum physics phenomena of entanglement and superposition to achieve dramatically increased efficiencies for solving specific algorithmic problems. 

While no publicly available hardware can exploit these efficiencies as of yet, the mathematical models for quantum computing have been around since the 1980s. This has enabled us to develop quantum algorithms before we have the hardware that can run them. 

One of these, Shor's algorithm, will be able to break cryptographic keys, such as those used in Bitcoin. Current estimates figure that we need quantum computers with  approximately 2500 logical qubits. For reference, publicly available quantum computing hardware has hundreds of physical qubits, but essentially only 1 logical qubit due to the need for a significant degree of error correction across the physical qubits to reach 1 reliable logical qubit. 

To reiterate, we already have the software to crack keys, we just don't have the hardware yet -- but we will eventually. We will look more closely at how this can occur, but first, we need to discuss one of the most widely used algorithms, the Fourier Transform.

The Fourier Transform

The Fourier transform is a way of extracting component frequencies from a signal. Let's unpack that quickly.

When you speak into a microphone, a specific sequence of events happens: 

1. Your vocal cords physically push on the surrounding air, creating pressure waves. 

2. Those waves propagate through space and then hit the microphone diaphragm, making it oscillate at the same frequencies as the waves your vocal cords created. 

3. The diaphragm’s motion is converted into a time-varying electrical signal, which the microphone samples. 

Applying a Fourier transform to that sampled signal yields a list of amplitudes and phases, with one for each frequency present in your original sound. Here’s an example of how this looks in python, with a visual output:

Code <Python>

import numpy as np

import matplotlib.pyplot as plt

# Generate a simple signal: mix of 5 Hz and 10 Hz sine waves

sample_rate = 1000  # Samples per second

duration = 1  # Second

t = np.linspace(0, duration, sample_rate * duration, endpoint=False)

audio_data = (0.5 np.sin(2 np.pi 5 t)) + np.sin(2 np.pi 10 * t)


# Plot the original sine wave (time-domain signal)

plt.figure(figsize=(10, 6))

plt.plot(t, audio_data)

plt.title('Original Sine Wave Signal')

plt.xlabel('Time (s)')

plt.ylabel('Amplitude')

plt.grid(True)

plt.show()


# Compute DFT

dft = np.fft.fft(audio_data)

frequencies = np.fft.fftfreq(len(audio_data), 1 / sample_rate)

magnitude = np.abs(dft)

# Positive frequencies only

positive_freq_mask = frequencies >= 0

frequencies = frequencies[positive_freq_mask]

magnitude = magnitude[positive_freq_mask]


# Plot spectral

plt.figure(figsize=(10, 6))

plt.plot(frequencies, magnitude)

plt.title('Magnitude Spectrum of Generated Signal')

plt.xlabel('Frequency (Hz)')

plt.ylabel('Magnitude')

plt.grid(True)

plt.show()

And here are the results, as represented on a sine wave: 

Original Sine Wave Signal

Magnitude Spectrum of Generated Signal

So you can see we took a mixture of 5 and 10hz sine waves, applied the transform and got spikes at 5 and 10, proportional to the original amplitudes.  This is apparent both in the waveform as well as in the table axis, which shift following the Fourier transform.

It's like writing down a speech using an alphabet of frequencies. One can also view this process as resonance. The Fourier Transform is good at finding patterns that repeat. It works by testing many possible rhythms (or frequencies) and seeing which ones match the signal. If a part of the signal matches the test frequency, it lines up and adds together, creating a strong result. But if it doesn’t match -- if it’s off-beat -- those parts cancel each other out because they point in different directions.

This ability to spot repeating patterns, or periods, is exactly what makes the Fourier Transform so powerful in Shor’s algorithm. That algorithm looks for a hidden repetition in a number pattern, and the Fourier Transform helps reveal it.

Quantum Algorithms: Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum algorithm equivalent of the Fourier Transform that can operate on a superposition of inputs, enabling it to process exponentially many inputs simultaneously. 

Unlike the classical Fourier Transform, which requires computing each function value separately, the QFT can use quantum parallelism to evaluate the function at a superposition of many inputs at once, thereby achieving exponential speedups for problems like factoring and discrete logarithms. QFT is the cornerstone of Shor's algorithm, which enables quantum computers to crack Bitcoin keys.

Now let's quickly review how Bitcoin keys work:

Discovered in 1985 by Victor Miller and Neil Koblitz, Elliptic Curve Cryptography (ECC) is widely used today for its compact keys and fast signature algorithms. 

Elliptic curves are described by the form y^2 = x^3 + ax + b mod p where p is a large prime number. 

Points on the curve can be added together to get another point, as illustrated above. You can add one point to another by drawing a line through both and finding its third intersection with the curve, then reflecting that across the x axis to get the sum. 

For instance, in the picture P + Q = -R.

You can also add a point to itself. In this case, you make the line tangent to the curve at P and again see where it intersects the curve elsewhere. If the line never intersects the curve, we say their sum is 0. This gives us a way to multiply points by numbers, for example 3P = P + P + P.

It turns out that adding a point to itself over and over is easy to do but difficult to reverse, so if someone gives you P and Q and asks you to find k such that kP = Q, it is not easy to do. This “trapdoor” behavior is due to information about the structure of Q being lost when k is omitted. Reverse engineering that structure necessarily takes work. 

It’s like how, in school, you may recall that factoring or division was significantly harder than multiplication. The most general version of this problem is known as P vs NP and there is a $1m prize for proving the answer either way.

Retrieving k given P and Q is an example of the discrete logarithm problem and its hardness is the basis for ECC. In ECC, k is the private key and Q is the public key and all x and y values are taken modulo p for some large prime p. 

In Bitcoin, the private key is used to make signatures proving ownership of funds and the public key is used to verify these signatures.

With these concepts in hand, we now have all the pieces to describe Shor's algorithm.

Shor's Algorithm

Shor's algorithm uses the quantum fourier transform to efficiently solve the discrete log problem at the heart of elliptic curve cryptography. 

To crack an elliptic curve key, it evaluates f(a, b) = (a + bk)P = aP + bQ over a superposition of all possible values of both a and b, where P is the base point, Q is the public key, and k is the private key. 

The function is periodic with period n, so nP = 0. 

The QFT  finds all a and b such that bk = -a mod n, which, after a few runs, yields the private key k via modular arithmetic. Solving this last equation is very fast, O(log n).

If Q is a Bitcoin public key, then extracting k from it would allow an attacker to steal the Bitcoin from the key. Having even one outgoing transaction from a Bitcoin address reveals the public key on-chain, so most addresses would be vulnerable.

And it's not just Bitcoin that's vulnerable. Almost every blockchain relies on ECC for signing transactions. This is why quantum computing is such a threat to blockchain security, and given its relevance to cryptography and national security, it is likely that governments will try to keep quantum algorithm progress a secret as long as possible.

What To Do Next

You don’t have to be a quantum physicist to protect yourself against the quantum threat. New methods like lattice or hash cryptography protect against Shor’s algorithm and all other known quantum algorithms. 

• Never reuse blockchain addresses to send cryptocurrency

• Don’t interact with any smart contracts with the wallet where you store the majority of your funds

• Ensure that the public key of any valuable address is kept entirely private

• Monitor updates from watchdog organizations like Quantum Canary and regulatory institutions like NIST

• Consult cryptographic libraries to swap out the cryptography in your systems without coming up with a new algorithm

One of the most effective ways to protect yourself is to consult an expert. I’m available for an initial consultation to discuss quantum securing the systems that protect you and your business. Reach out to me using the links below or the contact page of this site. 

Sources:

• https://www.youtube.com/watch?v=rVOhYROKeu4

• https://arxiv.org/abs/1706.06752?ref=btq-publication.ghost.io

• https://www.allaboutcircuits.com/technical-articles/what-is-the-fourier-transform/

• https://www.classiq.io/insights/shors-algorithm-explained

• https://scienceexchange.caltech.edu/topics/quantum-science-explained/entanglement

• https://scienceexchange.caltech.edu/topics/quantum-science-explained/quantum-superposition

• https://arxiv.org/pdf/2405.07222

• https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

• https://bitinfocharts.com/top-100-richest-bitcoin-addresses.html

• https://math.mit.edu/classes/18.03/sup/sup12.pdf