The multiverse theory. Quantum entanglement. Instant communication across infinite space.
The field of quantum physics swirls with dazzling and confounding possibilities.
Just as sparks and thunder dazzled the ancients, quantum physics dazzles us.
And like our mastery of electricity, our mastery of quantum computing will drive one of our great technological jumps forward.
How Powerful Are Quantum Computers?
Only small quantum computers have been built so far. Larger computers are theoretical — or still kept secret. As the technology develops, we may soon be operating a computer wielding more raw mathematical power than all of our modern-day laptops, desktops, and supercomputers combined.
The advantages of such a mighty machine are impressive, but so are the challenges it brings to society.
For one, the encryption methods we use every day to safely communicate, browse the web, and send financial transactions will be at risk. Quantum computers are particularly good at solving the intense mathematical problems used to drive encryption and cryptocurrency.
Why Are Quantum Computers So Powerful?
The phone, tablet, or computer you’re reading this on — unless you’re a N(A)SA employee testing the latest quantum powerhouse — is a classical computer. It uses transistors to do everything. Each transistor is either on (1) or off (0) at any given time, and so classical computers “understand” things in strings of 1s and 0s.
Digital data is nothing but a long series of on’s and off’s.
In simplistic terms, this means the amount of possibilities a computer can process is multiplied by two with each transistor you add — since that transistor can be either on or off.
Quantum computers utilize quantum bits — called “qubits” for short. Each quantum bit is a particle placed into a state called superposition, which allows the qubit to assume a value of 1 or 0 simultaneously.
This basis of quantum computing defies common sense. Yet the results are demonstrable.
Superposition allows a quantum computer to process many, many, many more data possibilities than a classical computer.
A properly constructed quantum computer with just 300 qubits can process as much information as a classical computer containing more transistors (2³⁰⁰) than there are particles in the known universe.
How quantum computers work is hard for a finite being to conceptualize, but let me put it this way: the ideal quantum computer attack on a Bitcoin key evaluates all possible private keys simultaneously. This superposition is then carefully collapsed (using the quantum Fourier transform) into another state that has a high probability of returning the correct answer.
Thankfully, such an attack requires a sufficient number of qubits and level of error-correction which have not yet been achieved in a stable quantum computer system.
Except for the one operated by the shadow government, of course.
Defining Quantum Entanglement
Quantum computers have a trick hidden up their Schrodingerian sleeves that gives us hope for creating a stable quantum computer sooner rather than later: entanglement.
Qubits can become “entangled” with one another. Measuring one qubit collapses it into a single state (1 or 0) — and if it is entangled with another qubit, the measurement instantly causes the other qubit to reflect the same state, no matter the distance between them.
This relationship has been verified at distances of over 700 miles. In that particular experiment, the science team’s “transmission of entangled photon pairs [was] ‘a trillion times more efficient than using the best telecommunication fibers.’”
Spooky stuff, indeed.
Due in part to their need for correct quantum entanglement, we believe that quantum computers will only be good at calculating specific mathematical problems. But they can do so at extreme speeds.
In fact, they are able to calculate billions of times more quickly than traditional computers can.
One such problem is the Discrete Logarithm Problem. Elliptic curve cryptography (referred to as ECC or ECDSA) relies on this problem for its security, but quantum computers can use Shor’s algorithm to break ECDSA and find a private key extremely quickly. ECDSA is commonly used by cryptocurrencies, so with Shor’s algorithm, public cryptocurrency keys become vulnerable to quantum attack, jeopardizing the private keys paired with them.
If a private key is discovered, all the funds it controls are up for grabs.
Meaning that crypto will die, unless it adapts. There are three general ways to create a quantum-resistant cryptocurrency.
How to Make a Quantum-Resistant Cryptocurrency
1) Stronger Keys.
One way to increase quantum resistance against Shor’s algorithm in particular is to use larger keys. This increases the amount of time and the number of qubits required to break a cryptocurrency key — and stable quantum computers are much harder to create as the number of qubits increases.
Definition: Key, a string that a computer algorithm uses to encrypt or decrypt data. Symmetric keys, such as keys for file encryption, work both ways with only one key. Asymmetric keys, like those used in cryptocurrency, work only one way, so they come in keypairs. One key (the “private key”) is used by one person to create signatures and sign transactions. The other key (the “public key”) is used by the whole network to verify the signatures are genuine. Due to its mathematical limitations, a public key absolutely cannot create signatures — only verify that they are authentic.
If you need more help understanding keys and signatures, try this article.
2) Stronger Hashes.
In addition to crypto signing algorithms, crypto hashing algorithms can be attacked, as well.
Definition: Hash, a process that turns data of any size — like a letter, a sentence, or a whole movie — into data of a fixed size, such as 256 bits. Cryptographic hashes will always give you the same result if you input the same data, but this result will appear random. Changing the data you inputted even slightly gives a completely different result. Hashing is an essential component of blockchain technologies.
Try the SHA-256 hash out for yourself with the awesome hash widget created by Jack Preston for his blockchain explainer articles.
(Note: trying this hash is actually legal in all jurisdictions and for all ages.)
Grover’s algorithm is a more general attack that can calculate a number that matches a certain mathematical property. This broad-purpose algorithm can be adapted to go after all kinds of targets — including the SHA256 and RIPEMD-160 hashes used by Bitcoin and many other cryptocurrencies.
This vulnerability is most often addressed by using a more complicated hashing algorithm, since Grover’s algorithm does not destroy the security of hashes, just reduces it.
Stronger keys and hashes are good, but we do not know the limit our quantum computers will reach. So while these measures do postpone the quantum threat and/or make quantum attacks more difficult, they may not be a long-term solution. Thankfully, there is another way.
3) Changing Private/Public Keys.
It is a common mistake to call a Bitcoin address a “public key,” but that’s not correct. Bitcoin addresses are actually a hash of a public key. This means that an attacker cannot decrypt even your public key from your Bitcoin address.
However, once you send funds from a Bitcoin address, your public key is published on the blockchain, rendering your address vulnerable to quantum attack. This vulnerability applies to most other cryptocurrencies, as well — after all, most cryptocurrencies have been developed from Bitcoin.
There is a way out of this vulnerability: you could send all of your coins to a new address each time. Consider each and every address dead as soon as you use it to send. Any attacker successfully breaking your public key would be wasting a large amount of resources only to seize power over an empty address.
But manually shuffling your coins to new addresses all the time is awkward, so quantum-resistant coins can automate this behavior, preventing the public key from being exposed to attack. They usually do this by generating a new private/public keypair with each transaction. Once you send some coins and expose your public key, you get a new keypair to control your coins, rendering attacks on your old keypair useless.
These are the major quantum security measures currently implemented or in development. Keep an eye out for the terms keys, hashes, and signatures to track the use of the above security methods by the currencies we discuss.
For a super-technical discussion of the above measures as they relate to Bitcoin specifically, see the October 2017 research paper “Quantum attacks on Bitcoin, and how to protect against them.”
Five [update: now Six!] Quantum Resistant Cryptocurrencies
Quantum resistance is still in development for most coins pursuing it. Thankfully, the community does have some time to perfect and implement solutions — though perhaps not as much time as we think.
The five [original] coins below are sorted in descending order by market cap.
Note: NEO and Cardano (ADA) also plan to allow for quantum-resistant signatures. I may add them here as more details about these plans emerge over the next year. Particl (PART) also includes quantum resistance, and a number of other projects may add it to their development roadmap soon.
1) IOTA (MIOTA): Directed Acyclic Graph
Quick points: No blockchain. Transacting nodes verify other randomly selected transactions. Private keys are protected with Winternitz one-time signatures. For maximum security, addresses should be discarded after they send IOTA for the first time.
IOTA’s Tangle is not a blockchain in the traditional sense, though it does run on a blockless distributed ledger.
In summary, each player on IOTA’s network — be it a smart IoT device or not — must approve two previous transactions in order to broadcast its own transaction. Note that there are other DAG-based currencies, such as Byteball, which use a system that is similar to IOTA’s.
IOTA uses one-time Winternitz signatures rather than elliptic curve signatures (the quantum-vulnerable cryptographic method mentioned above). An IOTA node’s seed generates new public/private keypairs when needed. So while an address can be used to receive IOTA multiple times, as soon as it sends IOTA, it becomes insecure. (Technically, it becomes half as secure with each use.)
As long as no more funds are received to an IOTA address after the address sends a transaction somewhere, anyone successfully attacking the address will be unable to access any funds.
In other words, when used correctly, an IOTA address is empty mere moments after it becomes a possible target. As long as this rule is followed, quantum attacks on IOTA do not even have a reasonably exposed target to attack, since new private keys (and signatures and addresses) are generated for each send transaction.
There is some concern that IOTA’s Tangle may be vulnerable to a variant of a 51% attack, in its case a 33% attack.
Definition: 51% attack, a commonly discussed attack on a cryptocurrency where a malicious actor or pool of actors controls enough of the mining power on the cryptocurrency’s network to control the network to some degree. Despite the attack’s name, the power required can be lower than 51%.
A quantum computer’s power could possibly be used to dominate proof of work power on a network and execute a 51% attack. However, for several reasons, I see this as an improbable quantum attack on a cryptocurrency, at least in the near future. IOTA is attempting protections against the attack (as they can be executed by lots of classical computing power), but whether these protections are effective is debated.
Note: IOTA is popular and ambitious, but it is also controversial, in particular due to some of the cryptography it uses and other alleged security issues. I have not researched the debate enough to have an opinion on the matter.
2) Nexus (NXS): Signature Chains, Stronger Keys and Hashing
Quick points: Launched years ago. Stronger keys and hashes already implemented. Private key protection via signature chains will eliminate the need to change addresses with every transaction, but signature chains are not quite finished. Ledger Nano S does not yet support the stronger keys and hashes.
Nexus claims to be the first quantum-resistant blockchain, and as far as I can tell, they are indeed the first to have implemented quantum-resistant keys and hashes — but while it has been in progress for months, public key protection is not quite finished.
Nexus evolved from a traditional Bitcoin-style blockchain called Coinshield. However, it is now significantly different from Bitcoin, with significant progress made towards a “multi-dimensional chain” (MDC or 3DC) which offers a solution to blockchain scalability and security issues. Apparently, Nexus’s 3DC will allow for many more transactions per second than most other solutions in the space.
Nexus uses 571-bit private keys — larger than Bitcoin’s 256-bit key, and also more secure against Shor’s algorithm since 571 is a prime number.
This makes Nexus exponentially more difficult to crack than Bitcoin with traditional computing — a comparison between the size of a grain of sand and the size of the Sun is not even close to large enough to serve as an adequate analogy — but for quantum computers, these stronger keys increase the difficulty of breaking Nexus by a small multiple (3x-4x) of the number of qubits.
Nexus also uses more secure hashes: 1024-bit Skein and Keccak quantum-resistant hashing algorithms. This is much larger than Bitcoin’s 256-bit hash.
One temporary downside of this increased security is that all hardware wallets are currently unable to accommodate Nexus at the hardware level due to these increased key and hash sizes. I believe this will change as more cryptocurrencies adopt larger key and hash sizes.
As far as signatures go, Nexus is implementing signature chains, a decentralized system accessed with a username, password, and PIN. These chains “update the private and public keys that secure your address and obscure them after each and every transaction, maintaining the integrity and security of your account even on mobile wallets.” According to Nexus, signature chains are extremely compact and lightweight, an advantage over other quantum-resistant schemes. Since the address is divorced from the public key, a Nexus user does not need to change addresses in order to change keypairs.
Nexus currently has three consensus channels: prime (proof-of-work finding clusters of large prime numbers, potentially helpful for number theorists), hashing (Bitcoin-esque proof-of-work mining), and proof-of-stake. In order to execute a 51% attack on the network, an attacker needs to attack multiple channels. As I said above, I find it unlikely that future quantum attacks will take the form of quantum computers dominating a network’s mining power, but if they do, this multi-channel feature is relevant.
Nexus’s most flashy selling points are actually unrelated to quantum resistance: it has partnered with Singularity.ai to explore the AI space and with Vector Space Systems to launch satellites to provide global censorship-resistant coverage and possibly global free Internet.
3) Quantum Resistant Ledger (QRL): Signature Protection, Hash-based Proof of Stake
Quick points: Not launched yet (still planned for Q1 2018), but available as an ERC20 token that can be converted later. Private key protection and hash-based proof of stake. QRL claims it will be storable on Ledger Nano S when launched.
While other coins have strong focuses in other departments — IOTA on the Internet of Things and Nexus on satellites and speed/scalability — QRL’s central pitch is quantum security. QRL claims to be a “first of its kind, future-proof post-quantum value store.” So what makes it unique?
Based on my research, I believe that QRL was indeed the first cryptocurrency concept, though not the first actual implementation, with private key protection. (The currency’s mainnet Genesis block was mined in September 2017.) It is, however, the first to implement efficient signature protection and hash-based proof of stake.
QRL initially allowed for:
- Lamport-Diffie one time signatures below a many-time Merkle tree signature scheme (MSS) and
- Winternitz one-time signatures, also with a many-time MSS.
In case you want to know a bit more: Lamport and Winternitz signatures can usually safely sign only one transaction per signature, but combining these with many-time Merkle tree signature schemes allows for the scheme to be used more efficiently (more than just once per each signature). The MSS is believed to be resilient against quantum computer algorithms despite this efficiency.
QRL now also implements:
- XMSS (eXtended Merkle Signature Scheme), a “peer-reviewed post-quantum algorithm.” XMSS is an OTS (One Time Signature Scheme). Keypairs are generated as needed, making XMSS unforgeable.
QRL’s key protection scheme, then, shows similarities to Nexus’s signature chain plans, but with several quantum-resistant options available for use.
QRL has still not launched its mainnet as of this writing, and so is only available as an ERC20 token for the time being. The token will be convertible when the mainnet launches.
One advantage QRL has over Nexus — and IOTA, for that matter — is that the Ledger Nano S will support holding QRL upon launch.
Quantum Resistant Ledger is currently proof-of-work (CryptoNight) and plans to hard fork to proof-of-stake in Q3 2018. Their proposed proof-of-stake algorithm was also created with quantum resistance in mind: it plans to use “hash-chains and hash-based pseudo random number functions and does not rely on conventional signatures.”
Our final two coins aiming for quantum resistance share some similarities. They are notably smaller, have anonymous development teams, and have so far shown a knack for reaching development milestones ahead of schedule.
4) Shield (XSH)
Shield is a multi-algorithm proof-of-work privacy coin with a set of common privacy features, as well as TOR integration. Proof of stake and masternodes are scheduled to come in 2018, in addition to an unknown new privacy feature. Shield had no premine, unlike a number of privacy coins.
As a privacy coin, XSH does include some features which make quantum attacks more challenging than against, say, Bitcoin, but it does not yet feature significant quantum resistance. The developers plan to introduce a post-quantum signing algorithm (likely BLISS or Winternitz) in Q4 2018. If implemented, this will significantly increase the coin’s quantum security.
Shield’s development team has consistently delivered ahead of schedule and is very responsive in Shield’s Discord community, so I expect quantum resistance to be implemented on time.
5) Mochimo (CHI, which is also the name of the actual currency)
Mochimo plans to launch on April 30th, 2018.
According to the Mochimo website, “The announcement of Google’s 49-qubit quantum computer in July of 2017 precipitated the Mochimo project.” Google claims to have advanced beyond that number of qubits with Bristlecone, a 72-qubit computer which Google is working to bring down to reasonable error rates.
The Mochimo community is driven to create a solid solution before Google advances too far. Their project is still young, and further concrete information is difficult to find on the Internet, but the developers can be contacted on their Slack. Mochimo does plan for a premine.
6) Hcash (HSR)
Bonus addition! A reader rightly pointed out that Hshare’s Hcash is implementing BLISS signatures for quantum resistance. In fact, it is a version of BLISS that Hshare claims is “faster, hardened against side-channel attacks, power analysis and 51% attacks.” I look forward to learning more about the project.
Please let me know if you are aware of another cryptocurrency that is specifically targeting quantum security and has made significant or unique progress.
What about Bitcoin? What about Ethereum? What about <my favorite digital currency>?
Bitcoin already has a sort of quantum resistance since your public key is only known when the address is spent from. This allows only a short time to break the address before the coins are gone, assuming all of the coins “in” the address are sent away.
But as I mentioned above, manually creating new addresses every time you spend is clunky. Besides, Bitcoin may be vulnerable to other attacks.
Popular Bitcoin evangelist Andreas Antonopoulos has rightly asserted that Bitcoin can change to meet the need for quantum security. “Both the signing algorithm and the hashing algorithm can be switched out.”
Antonopoulos is one of the cryptocurrency community’s key teachers and promoters, but I have three main concerns about his position of non-urgency, given that quantum computer development may occur more rapidly than we think.
First, whenever the need for quantum resistance becomes pressing, we may not even be aware of it.
The first quantum computer developed which can break Bitcoin may in fact be developed and used in secret. In the video, Antonopoulos is correct that a government with a clandestine quantum computer would probably not tip its hand by cracking Bitcoin. However, the computer’s controllers could potentially steal from large wallets, for example — perhaps including wallets known to belong to other governments. Without knowing about the quantum computer’s existence, the public and even the victim would likely assume the private keys to the wallet had been phished or stolen.
Second, Antonopoulos is also correct that once quantum computers are generally available, their existence will not present a threat since they will be adopted on the Bitcoin network. But he seems to overlook the inevitable prolonged middle phase between a single powerful quantum computer and general availability.
Third, Bitcoin, like many cryptocurrencies, has difficulty with governance. A major change — for instance, moving on to more difficult hashing algorithms which invalidate the expensive ASICs used by large mining companies — may take a long time to successfully be adopted by enough of the network.
I am assuming Antonopoulos was not expecting the question in this particular session and might be amenable to this viewpoint.
It is better to make Bitcoin quantum resilient too soon than too late.
Ethereum, NEO, etc., etc.
In the long term, Ethereum and especially NEO should be able to support any level of encryption that users want. Many other cryptocurrencies should, too.
For example, Ethereum’s EIP 86 proposed that users be able to choose any digital signature algorithm — meaning able to choose quantum-computer-safe addresses and avoid the ECDSA scheme vulnerable to Shor’s algorithm. (Mixing addresses may present security concerns that render this solution only an interim one, but I need to do more research on that point.)
On the whole, it remains to be seen exactly how major platforms like Ethereum, NEO, EOS, NEM, etc. will address quantum security, but they are far from doomed. Change may be difficult, and significant updates may be required, but it is possible. Increased public awareness may provide the incentive needed.
When Will Quantum Computers Arrive?
Yet even when quantum computers are strong enough to crush most modern cryptocurrencies, it may not be cost-effective to do so. Since any outside interference can have unpredictable effects on particles, quantum computers need to be kept protected at a few thousandths of a degree above absolute zero. That is really, really cold.
Furthermore, the more qubits you add, the greater the chances of your house of qubits collapsing, an event known as decoherence. Even if you have the temperature under wraps.
Yet despite these challenges, Google and IBM — and presumably other groups — say they are advancing quickly, though some doubt their claims. If their projects can be taken at face value, though, it is highly likely that a quantum computer will be created that can break Bitcoin within our lifetimes.
We may have less time than we think. Heck, in some universes other than ours, Bill Gates said 640 KB of RAM would be enough for anyone. Had he said that in our universe, he could not have been more wrong, and yet he would have been right at home. People here underestimate the progress and overestimate the limitations of technology all the time.
Quantum computing may be here even sooner than we estimate. Much sooner.
I hope the best cryptocurrency projects have implemented quantum protection by then.