Pauli Group is using NFTs on proof-of-quantum.com to measure and protect the future of blockchains from quantum attacks.

Why?

Because along with factoring, discrete logarithms (on elliptic curves) are one of the very few applications for which we are most confident to find an exponential advantage of quantum computers over their classical counterpart as early as 2029-2033. From there the rate of key breaking will increase exponentially in time which will create an existential risk for current blockchains. However the exact timeline is unknown as it depends on future advances in algorithms, error correction methods and improved fabrication and control methods. Given the potential scale of the future cryptocurrency market and the magnitude of the risk, we decided on deploying a platform to measure the progress of quantum computers are breaking the cryptography of blockchains with on-chain challenges with a gradation of difficulties. Measuring the risk is the first step toward transitioning blockchains to quantum-proof cryptography this decade.

Let’s now dive deeper and explain more about the very technical subject of quantum cryptanalysis of blockchains.

What are quantum computers and how do they pose a risk for blockchains and cryptocurrencies?

Quantum computers are physical devices that harness the laws of quantum mechanics to efficiently solve some types of problems that would otherwise take ages on machines designed to operate only from classical physics principles.

In classical physics, the state of a computer can be described with probabilities over the possible configurations of 0’s and 1’s bits that represent the states of the individual logical components. In a computation, if the actions that transform the bits are commensurate in energy and timescale with the natural processes of the fundamental constituents of matter, then it becomes possible to observe constructive and destructive interference patterns in the probabilities of the different configurations of 0’s and 1’s. When the operations that build up such a calculation are done reversibly in a way that does not destroy information, then those interference effects between the waves that determine the probability of different results can be steered to solve otherwise very difficult problems. This is the art of quantum computing. Those interference patterns are especially useful for computations that involve measuring astronomically long cycles in the space of configurations. Discrete logarithms, factoring and quantum simulations are examples of such problems that quantum computers are good at solving.

Quantum computers will have the ability to recover the private keys from the public keys stored on blockchains. Almost all blockchains use elliptic curve cryptography for signing transactions on a ledger. While elliptic curve cryptography cannot be hacked with a classical computer, it is one of the easiest methods to break with a large enough quantum computer using Shor’s discrete logarithm algorithm. Most major blockchain use the same 256-bit elliptic curve, secp256k1, since the signatures can be efficiently verified and the keys are relatively small at 32 bytes. This also means that there is a single point of failure for most infrastructures built on those blockchains. The precise timeline of the power of quantum computers at solving increasingly difficult cryptography problem is not known. It depends on many factors and trends, notably the execution of the roadmap of the quantum computing hardware providers.

However, quantum computers are extremely susceptible to noise and environmental fluctuations which wash out the interference patterns. Overcoming decoherence is the main challenge to using quantum processors for cryptanalysis. Methods and design principles exist to mitigate and suppress the various errors induced by decoherence processes, but they require important engineering overhead which are expected to be overcome by the end of the decade.

There are credible roadmaps for all major quantum computing hardware companies such as IBM and Google. The fundamental physics has been de-risked as several groups are reporting success in early fault-tolerant experiments. This means we are now entering the regime where making processors with more and better physical qubits will yield an exponential advantage at breaking the cryptographic keys and signatures that are used on the internet today and in blockchains.

A large enough quantum computer can recover the private key from the public key.

An important figure of merit when evaluating the difficulty of running quantum algorithm is the number of so-called “T” gates. Those are operations that are required for universal quantum computation but cannot be executed in a fault-tolerant fashion. Hence their implementation requires special care which induces most of the overhead in the successful execution of quantum algorithms. The current best estimates for breaking the cryptography of blockchains requires approximately 10 billion T gates on about 2,500 error corrected qubits. The leading approach to implement error corrected qubits from noisy physical qubits is the surface code, a two-dimensional array of qubits which encodes quantum information in a way that protects it from noise and decoherence. For example, Gidney and Ekerå estimated that solving the RSA 2048 factoring problem using the surface code would be doable in 8 hours using 20 million noisy qubits. However, the general rule of thumb in the literature of the last decades is that breaking elliptic curves typically requires less quantum gates than RSA 2048. This indicates a strong probability that cryptocurrencies will be broken by quantum computers a few years before RSA (which could realistically be broken by 2035). A recent coarse estimate requires 1 day with 13 million qubits to break the elliptic curve of Bitcoin. This can be considered an upper bond on resources as algorithms, error correction methods and qubit fabrication techniques are continuously improved.

 

The rate at which the risks will increase can be difficult to evaluate as it depends on several parameters with complex interactions. General benchmarks such as quantum volume can help model risks, but they are not as indicative as benchmarks tailored for applications. There are many sources of uncertainty and trends to compound to assess the quantum vulnerability of blockchains: progress in achieving hardware milestones and reducing noise, rate of deployment of future hardware, reduction in production costs of hardware, improvement in quantum and classical algorithms, improvement in error correcting codes and compilation methods, rate of deployment and adoption of quantum resistant cryptographic solutions in blockchain technologies, etc.

How can we measure the progress of the technology in a transparent and verifiable way?

The Pauli Group solution: assess the risk empirically with application benchmark challenges that can be used to measure the progress of the large-scale integration of quantum computing systems. Specifically, these benchmarks will take the form of challenge for near- and mid-term fault-tolerant devices meant to quantitatively assess the risks of cryptographic assets. We chose to release those challenges on the Polygon blockchain as it is compatible with the Ethereum virtual machine (EVM) smart contracts, it has low transaction fees and it is available on the NFT platform OpenSea. The challenges can included a sponsored reward and are presented as NFTs that can be traded once solved.

Our NFTs contain both their public key and a hint of the private key.  The public key ‘P’ is given by it’s x (blue) and y (green) component, it is computed from the private key ‘k’ and the base point ‘G’ as P = [k]G. Bits of the private key ‘k’ (red) are given except the last ‘n’ bits which define the difficulty of the puzzle. For example, for a difficulty of 4 bits, all but the last four digits are given (and the puzzle can simply be solved by trying all 16 possible combinations). The difficulty of the challenges increases in increments of 4 bits up to the maximal difficulty of 256 bits, where no information is given about the private key (this corresponds to the difficulty of breaking Bitcoin and other blockchains). Using the best classical method, namely the Pollard rho kangaroo algorithm, the time to solve a puzzle is exponential as it doubles for every increment of 4 bits of difficulty. This is the solver we included in our platform which can solve 40 bits challenges in the browser on most computers in a few minutes. Quantum computers will be able to break those challenges in a time which scales as the cube of the difficulty, which is an exponential improvement over the best classical method. For elliptic curves, we estimate that the quantum advantage transition will happen in the range of 120 bits to 160 bits difficulty in our challenges. The resolution of those challenges will be a clear signal that P2PK addresses on Bitcoin (for which the public key is recorded on the blockchain) are at imminent risk.

We believe that basic discrete logarithms toy problem could be solved on quantum computers from 2025 onward. Given our approach of finely grained difficulty for our cryptographic challenges, it may be possible to observe a quantum-classical crossover on intermediate difficulty challenges on our platform. This could happen in the transition era of 2025-2029 between noisy intermediate scale machines and large scale fault-tolerant quantum computers. By tracking the progress of quantum computers at solving challenges easier than the full difficulty of breaking Bitcoin, we aim at shepherding the orderly post-quantum transition for blockchains before the end of the decade.