Discussion Post on PQC - Quantum Vulnerabilities of Blockchains

TL;DR

  • Cryptocurrencies are digital money systems powered by blockchain technology. While not all the same, all cryptocurrencies share a vulnerability to quantum attacks.
  • This post discusses the potential threat quantum computers pose while determining the risk exposure and security of some of today’s cryptocurrencies.
  • The post also presents some post-quantum digital signature schemes for building blockchains that can survive the Quantum Era.

Citation

  • [1] Vulnerability of Blockchain Technologies to Quantum Attacks by Joseph J. Kearneya, Carlos A. Perez-Delgado. https://arxiv.org/pdf/2105.01815.pdf
  • [2] The Future of Cryptocurrency Blockchains in the Quantum Era by Sarah Alghamdi and Sultan Almuhammadi. 2021 IEEE International Conference on Blockchain (Blockchain). IEEE, 2021.
  • [3] Assessment of Quantum Threat To Bitcoin and Derived Cryptocurrencies by Stephen Holmes, Liqun Chen. https://eprint.iacr.org/2021/967.pdf

Background

Introduction

In 1994, Peter Shor, creator of Shor’s Algorithm, demonstrated how quantum computers could crack cryptosystems in exponentially faster time than classical computers. The faster computation is because Shor’s algorithm runs on polynomial time. As quantum capabilities advance and blockchains scale to secure billions of dollars of assets, the threat of quantum attacks increases exponentially.

Understanding blockchain’s current level of vulnerability is critical to helping mitigate the risk of losing assets on the blockchain through quantum hacking. It will also help identify what blockchains need to survive the quantum era.

Terminology
Shor’s algorithm:
A quantum computer algorithm for finding the prime factors of an integer. It was developed by American mathematician Peter Shor in 1994 and is the most famous quantum algorithm. Its popularity is due to the fact that it leverages quantum computers’ ability to calculate huge values in exponentially less time.

Discrete Logarithm Problem: Discrete logarithms are mathematical problems defined by multiplicative cyclic groups. They are the basis of public key cryptography security because of the assumption that no efficient method can compute them in general.

ECDSA (Elliptic Curve Digital SIgnature Algorithm): A Digital Signature Algorithm (DSA) which uses public/private keys derived from elliptic curve cryptography (ECC). In the ECDSA algorithm, n is the size of the private signature key and they are based on the algebraic structure of elliptic curves over finite fields.

ECDLP (Elliptic Curve Discrete Logarithm Problems): A unique form of the discrete logarithm problem in which elliptic curves are used for cryptography. ECDLP is the basis of elliptic curve cryptography and rests on the assumption that the problem is hard to compute.

Research Question

When will quantum computing be powerful enough to execute Shor’s algorithm? What can be done to protect blockchains from the Quantum Era?

Summary

Potential Threats and Risk Exposure
Quantum computers drastically reduce the time needed to solve some computational issues. There are two main quantum algorithms relevant to our discussion:

  • Shor’s algorithm
  • Grover Search algorithm

Shor’s algorithm factors large integers and computes logarithms in polynomial time. The Grover Search algorithm is based on generalizations, searching for the transaction hash codes and solving NP-complete problems. Between the two, Shor’s algorithm is the more significant threat as its computational speed is exponential.

Any blockchain solely relying on integer factorization or discrete log problem (DLP) is completely vulnerable to quantum attacks running on Shor’s algorithm. On the other hand, Grover’s algorithm computes hash functions quadratically, implying that the blockchain can resist attacks by doubling the size of the key.

Blockchains use signature schemes like Elliptic Curve Digital Signature Algorithm (ECDSA) to sign each transaction. This signature is linked to the user’s public/private key pair from which they created their account. ECDSA uses Elliptic Curve Cryptography - a cryptography system based on the algebraic structure of elliptic curves over finite fields. The signature scheme also relies on how difficult it is to solve discrete logarithm problems.

It is worth noting that ECDSA provides the same level of security compared to other schemes, even though it uses smaller keys. For instance, 256 bits when compared to 2048 bits of RSA. These two features make ECDSA ideal for blockchains. Unfortunately, the same features - reliance on discrete logarithm problems and smaller keys - also expose blockchains to quantum attacks.

Quantum computers drastically reduce the time needed to solve some computational issues. There are two main quantum algorithms relevant to our discussion:

The first is Shor’s algorithm that factors large integers and computes logarithms in polynomial time. The second is the Grover Search algorithm based on generalizations, searching for the transaction hash codes and solving NP-complete problems. Between the two, Shor’s algorithm is the more significant threat. As mentioned in the “Terminology” section, the algorithm’s computational speed is exponential.

Any blockchain solely relying on integer factorization or discrete log problem (DLP) is completely vulnerable to quantum attacks running on Shor’s algorithm. On the other hand, Grover’s algorithm computes hash functions quadratically, implying that the blockchain can resist attacks by doubling the size of the key.

Cryptocurrencies Vulnerable to Quantum Attacks
This discourse’s primary purpose is for us to understand the vulnerability level of existing blockchains to quantum attacks. For example, many blockchains like Bitcoin, Ethereum, Litecoin use digital signatures based on Elliptic Curve Discrete Logarithm Problems (ECDLP). Note that a cryptocurrency may use other signature schemes with ECDLP. However, they’ll still be vulnerable to the same quantum attacks due to ECDLP.

Below we look at Bitcoin, Ethereum, and Litecoin and their vulnerability levels. And how long it would take a quantum computer to break the system.

Bitcoin
Bitcoin and all its related cryptocurrencies are at risk of quantum attacks. As mentioned above, Bitcoin uses ECDSA. It has been speculated that a quantum computer of appropriate scale running Shor’s algorithm could break ECDSA in polynomial time. The attack would involve monitoring the public key to find its private key after the transaction is made. With the private key, the attacker can sign new transactions.

Bitcoin uses UTXOs - unspent transaction outputs - for transactions. Once the user initiates the transaction, the network records and deletes each input, and new outputs are created for the next transaction. In the case of quantum attacks, the attacker can “steal” transactions and direct the newly created UTXO to any account they choose.

A quantum computer with a computing power of 485550 qubits, using Shor’s algorithm and running at a clock speed of 10GHz, could complete this attack in 30 minutes. The attack’s success depends on how long the network takes to add new transactions to the block. If each attack falls within 30 minutes (typical for Bitcoin), the attacker could successfully move money before the network notices.

Another thing worthy of note is that early Bitcoin users and miners were paid directly to their public key (P2PK) instead of to the hash of the public key. As a result, these accounts are highly vulnerable to the attacks discussed earlier. The extreme vulnerability is because there is no time limit for the attack. Once a sufficiently large quantum computer is developed, an attacker can easily calculate each account’s private keys, sign new keys (to impersonate the owners) and empty all the funds.

Ethereum
The Ethereum network will soon transition from its current Proof-of-Work consensus mechanism to Proof-of-Stake. PoS’ security relies on users staking Ethereum to gain voting and consensus power. That said, EthHash is currently the PoW mechanism used to secure Ethereum. In Ethereum transactions, there is no “from” field. That makes each public key K associated with the account unknown. You can, however, recover it by reconstructing the key from another user’s transaction signature.

Like Bitcoin, a quantum attacker with a large enough memory can use Grover’s algorithm to attack EthHash. While calculating Ethereum’s risk exposure, the authors discovered the network has a minor advantage with its shorter transaction processing time [1, p.8].

However, Ethereum’s use of account-based transactions eclipses this advantage. For context, every outgoing transaction must be signed using the account’s private key. Once an attacker finds the private key responsible for the transactions, they can access the user’s entire account balance.

That said, even without any advances in ASIC technology, a quantum attacker would need a clock speed of about 5THz before they can attempt a 51% attack on Ethereum (which would still not be successful)[1, p.8].

Litecoin

Litecoin is a fork and lighter version of Bitcoin with some differences. The network has a shorter block time - 2 minutes - and less power consumption for mining due to its different PoW method known as Scrypt. Because Litecoin uses ECDSA, the cryptocurrency is vulnerable to all the quantum attacks mentioned above, especially on unprocessed transactions. But, Litecoin possesses the advantage of a shorter block time and throughput compared to Bitcoin.

This advantage gives Litecoin some resistance against such quantum attacks. But just like Ethereum, the advantage is minor given that with an increase in clock speed, a quantum computer would be capable of attacking Litecoin. It is worth noting that this analysis applies to all altcoins based on the Bitcoin blockchain source code - hard forks and source code forks. In summary, Litecoin has the same quantum vulnerabilities due to its similarities to Bitcoin.

Monero
Monero is a privacy-focused blockchain where transactions are untraceable. The blockchain uses Ring Confidential Transaction (RingCT) to hide the transaction details and the sender’s public key. Monero also uses Edwards Curve Digital Signature Algorithm (EdDSA), based on the discrete logarithm problem. Like ECDSA, EdDSA is vulnerable to quantum attacks. But according to an update (RandomX)[1, p.10], in Monero’s consensus protocol, the blockchain is more resistant to 51% attacks using Grover’s algorithm.

Grin
Grin is another privacy-focused blockchain similar to Monero as it uses Pedersen commitments - a form of discrete logarithm - to hide/obfuscate transaction details. Grin is also in danger of quantum attacks because of its privacy mechanism and use of signature schemes. However, while the attacker can remove the obfuscation, they won’t know if the transactions are important enough for attacks.

Other cryptosystems and blockchains vulnerable to quantum attacks are Beam and Zcash. Both are also privacy-focused blockchains that keep network transaction details private and untraceable. And their vulnerability is also linked to their use of elliptic curves and discrete logarithm problems.

How Long Will It Take?
Now we know why these cryptocurrencies are vulnerable to quantum attacks. How long will it take for a quantum computer to launch a (successful) quantum 51% attack?

Let’s first consider Moore’s Law for an estimate of resources. Bitcoin’s network hash rate is currently about 1.96 x 108 hashes (H/s) per second, while quantum computers start at 40 Mhz. With both increasing over time as dictated by Moore’s law, we have an estimated 27 years until a single quantum computer can successfully launch a 51% attack. This estimate, however, is conservative because quantum computers are still in their infancy, and we can expect them to grow faster in the coming years.

Following the law, running a quantum search algorithm (assuming no error correction) on SHA-256 hashes would require about 512 qubits. Major quantum computer manufacturer IBM predicts such quantum computers will be in the market by 2023. We also consider today’s reported quantum computer clock speeds. With this data, we can expect a quantum attacker using Grover’s algorithm to compute about 1.6 x 1015 H/s.

Earlier, we considered the vulnerability and risk exposure of existing cryptocurrencies like Bitcoin & Ethereum to quantum computer attacks. The two cryptocurrencies represent 59% of the industry, with a current total market cap of 567 billion.

Therefore, the focus is on protecting their vulnerabilities while designing post-quantum digital signatures that will replace ECDSA.

It is worthy to note that we already have cryptosystems that can withstand quantum attacks. Their resistance is due to the digital signatures used in building them, which known quantum algorithms cannot compute. They are in the table below:

Digital Signature Blockchain Market Cap
CURL-P IOTA $799,630,249
WOTS+ Mochimo $420,821
XMSS (eXtended Merkle Signature Scheme) Quantum Resistant Ledger $13,634,974
Signature Chains Nexus $11,247,965
Ring LWE HyperCash $6,026,602
Multi-Signature Cellframe $7,509,372

The third category includes recently designed quantum-safe cryptocurrency blockchains but not implemented yet. They are included in the table below:

Signature Cryptocurrencies
SPHINCS-256 Corda
XMSS, WOTS+ Bitcoin PostQuantum

Estimations
Although quantum computing is in its early stage must overcome many issues, companies are working hard to increase quantum computing capacity.

This nearness to the Quantum Era has made researchers calculate and estimate when a quantum computer could completely break ECDSA. According to Divesh Aggrawal, “Quantum attacks on Bitcoin, and how to protect against them” could be as early as 2027. Michel Mosca, author of “Cybersecurity in an era with quantum computers: Will we be ready?” estimates that a quantum computer capable of breaking RSA with 2048 bits in the year 2031 with a 50% chance. Joseph Kearney, on the other hand, estimates this will be possible by 2035.

Actionables: Avoiding Quantum Attacks
Not all cryptocurrencies are equal to quantum attackers. Different timing attack vulnerabilities and user behavior increase the cost of an attack.

  • Users can migrate to a one-time address, which protects the public key from a quantum computer with low clock speed.

  • A multi-signature address will also raise the bar for attackers. Recall n as the number of signatures required to unlock the address/key, and it takes up to 20 n of signatures to unlock an address in Bitcoin. The user can increase the resources required for the attack as it will take longer to compute in the same unprocessed transaction window.

  • Paying a higher gas fee for a transaction incentivizes miners to process it faster, which reduces the risk of a denial of processing transactions attack.

The industry should also implement a few practices:

  • To reduce the ever-present risk of the 51% attack, new blockchains should be built on post-quantum cryptography. These new blockchains should also avoid using PoW for consensus and should instead use PoS or any other consensus that is not based on hash searching.
  • There is a need for a quantum-safe blockchain that supports smart contracts. This blockchain will ensure easy startup of other quantum-safe cryptocurrencies in the future.
  • IOTA and other post-quantum blockchains using hash-based digital signatures should increase the key sizes to resist attacks running on Grover Search algorithm.
  • Classical blockchains should upgrade to post-quantum signature algorithms like NIST’s lattice-based algorithms. This upgrade is possible because the blockchain’s signature scheme is modularized, meaning developers can replace them upon core update.

Further Reading

  • P. W. Shor, “Algorithms for quantum computation:
    Discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science, pp. 124–134, Ieee, 1994.
  • F. Ma, M. Ren, Y. Fu, M. Wang, H. Li, H. Song, and Y. Jiang, “Security reinforcement for ethereum virtual machine,” Information Processing & Management, vol. 58, no. 4, p. 102565, 2021.
  • X. Li, P. Jiang, T. Chen, X. Luo, and Q. Wen, “A survey on the security of blockchain systems,” Future Generation Computer Systems, vol. 107, pp. 841–853, 2020.
  • J. Fernando, “Bitcoin vs. litecoin: What’s the difference?.” https://www.investopedia.com/ articles/investing/042015/ bitcoin-vs-litecoin-whats-difference.asp,
  • S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,”: https://bitcoin.org/bitcoin.pdf, 2008.
  • Coinmarketcap: https://coinmarketcap.com/
  • P. Zhang, L. Wang, W. Wang, K. Fu, and J. Wang, “A blockchain system based on quantum-resistant digital signature,” Security and Communication Networks, vol. 2021, 2021.
  • Joseph Kearney, Dan Bard, Carlos Perez-Delgado, “Quantum advantage on proof of work”
  • Evaluating cryptocurrency security and privacy in a post-quantum world
    Adam Corbo, Mitchell “Isthmus” Krawiec-Thayer, Brandon G Goodell
10 Likes

Thank you for posting this! Great job synthesizing several papers. As I dig through this, I also wanted to connect this thread to a summary from last year that also analyzed quantum vulnerabilities that @Larry_Bates posted. That paper was focused exclusively on Bitcoin, but I did think it was interesting that one of the findings was:

In the present discussion post, @Harvesto suggests Bitcoin’s vulnerability might be greater based on time as opposed to number of queries.

Are these potential discrepancies due to developments that have occurred in the last year, or are these analyses simply looking at different types of attacks; some that Bitcoin might be resistant to and others that it might be vulnerable to?

5 Likes

Thanks for this connection Paul! If anything, I believe these findings reinforce each other. The number of rounds it took for the estimated vulnerability gap to be closed was about three rounds. Current Bitcoin block times are about 10 minutes. Three rounds would be roughly 30 minutes. The math legitimately works perfectly here.

The very last line from the original summary post was in reference to time: “It will also make it more difficult for quantum adversaries to determine the current state of the chain to make the gap between the search time and the settlement time-weighted towards settlement.”

This “gap between search time and settlement time” is the gap the attacker would have to close to have their chain have the proper hashed sequence to overtake the “honest” chain. That would take roughly three search rounds, or currently 30ish minutes. This assumes the attacker can sustain the attack for that long, which is the limitation on the attacker; their capacity to have enough energy to sustain the attack over time.

7 Likes

@Harvesto This is concise and explicit, good one.

I’m interested in the effect of switching from one Digital Signature Algorithm (DSA) to another on classical blockchains.

Most classical blockchains have a low throughput which is already a lot of pain for users. So, in switching from ECDSA to say NIST’s lattice-based algorithms, is the scalability of such a blockchain a tradeoff thus reinforcing the idea of blockchain trilemma? That is, scalability being traded for security?

2 Likes

Thanks for the feedback Paul!

And the connection too. I believe it is a combination of both. The section you quoted from the discussion post refers to a quantum attack on a block/one transaction/UTXO.

Bitcoin’s blockchain is not completely vulnerable to quantum computing, but an attacker with the specified resources could successfully attack and steal the UTXOs , i.e. alter the honest chain however they choose.

That said, the attack’s success depends on a condition - it must fall within the 30 minutes settlement time.

2 Likes

Aptly put Larry! :clap:

That is what determines whether the attacker succeeds or not.

2 Likes

Apart from post-quantum cryptography, I don’t know of another usecase for Lattice-based algorithms. Based on that, I don’t believe there will be a trade-off or (negative/positive) effect on the blockchain’s scalability.

There will be increased security against quantum attacks, but the scalability won’t slow down drastically.

I also think a blockchain’s scalability has to do with other factors like it’s consensus mechanism, core software which determines algorithm, block and response time.

5 Likes

A very reasonable response. Thank you!

2 Likes

Glad to have the convo :smiley:

1 Like

@Harvesto, that was a nice piece there.

My own little contribution is that, if quantum computing develops more quickly than efforts to future-proof digital money, the blockchain accounting system that underpins cryptocurrencies may be subject to more complex attacks and faked transactions.

But, the good news is that In an effort to stay ahead of the Blockchain vulnerability issues, the National Institute of Standards and Technology (NIST) of the US government has been carefully searching for quantum-proof cryptographic algorithms for several years, enlisting the help of researchers from all over the world.In fact, some blockchain and cryptocurrency projects are actively developing quantum resistant software to address these blockchain vulnerabilities.

4 Likes

Nice work @Harvesto I see you really went deep into this, well I’d like to contribute my little knowledge on this.

I feel this Moore’s rule is outdated stating that “it will likely be 27 years before a single quantum computer can effectively launch a 51% attack”.
However, as of late, the encryption protecting Bitcoin might be broken in under 10 minutes. 13 million qubits alone could complete the task in about a day. Well given that quantum computing is still in its infancy and that we can anticipate it to accelerate in the future years, this estimate is modest. Quantum attacks will be more secure, but scalability won’t be significantly slowed down. The consensus process, the core software that controls the algorithm, block size, and reaction time are some key elements that affect how scalable a blockchain is. I’m not aware of any additional applications for lattice-based algorithms than post-quantum cryptography. On the basis of it, I don’t think there will be a trade-off or positive/negative impact on the scalability of the blockchain.

Well @Larry_Bates what do you think is the best remedy to this situation. An extension to the time frame causing a delay or what?

3 Likes

One of the most viable proposed solutions to this existential threat is to establish a “leaderless” system in which the round is never started from the same validator or set of nodes:
Scalable and Probabilistic Leaderless BFT Consensus through Metastability - Oracles and Data - Smart Contract Research Forum

In effect, instead of “expanding the gap,” or “occluding the gap,” this method would effectively constantly “move the gap” so that an attacker’s target would never be the same validating block or set of nodes.

4 Likes

How many quantum attacks have been recorded ever since. And can the same attack method be used on DAO’s and platforms like SCRF ?

6 Likes

The issue is not just breaking the encryption, but also getting the spot in the chain correct. If the block proposed has the proper private key, but is not the proper block; it will not be validated. This is why it not only becomes a problem of cracking the encryption, but a “Chain of PoWs” problem in which the attacker has to simultaneously crack the encryption while proposing a dishonest chain takeover at the properly timed block. It is an issue of breaking encryption, but also timing the accumulating chain output to match. This is why it is not likely to get it on the first round, and would take roughly 3 rounds for an attacker to both crack the encryption and also be able to propose the properly aligned chain of proofs.

Early on when the attacks were theoretical; it was seemingly an issue of raw computing power being able to overcome effectively any algorithm that it needed to. This often presumed a sedentary target, and a moving target represents a new set of variables that makes quantum attacks much more complex to pull off than was initially anticipated.

It was estimated that it would take 1.9 billion qubits to crack bitcoin’s chain in 10 minutes. Currently, IBM’s superconductor quantum machine is 127 qubits. I don’t think it needs to be mathematically articulated how far apart the current state of machines is from the proposed theoretical machine that would be necessary to begin to get close to execute the proposed line of attack. As we have real-world examples of quantum machines, the theoretical attack has more tangible examples from which to draw. In that context, the attack just does not look like a threat that will be a serious problem for many years to come.

5 Likes

There have been 0 successful recorded attacks. It is near impossible to know an attack is happening if it’s unsuccessful, so an immeasurable number of unsuccessful attacks may have taken place (or not). The attack method would not be useful unless there was a significant use of encryption. It’s also an extremely expensive form of attack and the current state of quantum machines would make it an inappropriate tool to use to attack most DAOs. It’s not just a tool that anyone can use or get access to, so the motivation and target would have to be viable for the attacker to need to utilize that much power to wage an attack. It just wouldn’t make logistical sense for someone to use a quantum attack on SCRF. There just isn’t anything that is encrypted and also a target valuable enough to use that many resources.

6 Likes

Much appreciated @Cashkid18

Yes, we all in the cryptography and cryptocurrency community should be grateful to NIST for researching and developing quantum-proof cryptographic algorithms.

Glad to know the solutions to the quantum threat exists.

1 Like

Glad to know there have been 0 successful recorded attacks.

About the potential attacks on DAOs and SCRF, I also believe it will be expensive and unfruitful to launch such an attack based on the available reward.

1 Like

Thanks, @Freakytainment, for contributing your little knowledge :smiley:

I see @Larry_Bates has done justice to your question and observation. However, I want to add something.

Based on the available quantum computing power and the resources required to crack Bitcoin’s chain, we can conclude that the quantum threat is not on the radar of the cryptography/cryptocurrency community.

That doesn’t mean we rest easy; our focus should be on creating awareness and transitioning to post-quantum algorithms ASAP.

4 Likes

Thanks for sharing, Larry

Further reading shows that blockchains may have trouble reaching consensus when they migrate to quantum-proof algorithms.

Can you shed light on how the migration could affect the blockchain’s decentralized nature and possible complications in governance structures?

Or share any resource that expands on the topic.

3 Likes

Can you explain what you mean here? I am not sure I understand the framing, or if I am reading it correctly I am not sure the framing is accurate. What are you referencing when coming to this conclusion?

2 Likes