Subscribe to Blockchain at Berkeley
>100 subscribers
Subscribe to Blockchain at Berkeley
>100 subscribers
Share Dialog
Share Dialog
By: Riteka Murugesh
Blockchain: an unalterable record of transactions that is public and distributed across a peer-to-peer network. Facilitates decentralization, transparency, and traceability of transactions.
Cryptocurrency: digital currency that IS NOT issued by a central entity
Bitcoin: a popular cryptocurrency to allow transactions directly between peers, cutting out the middlemen such as banks.
ECDSA (Elliptic Curve Digital Signature Algorithm): a cryptographic algorithm used in Bitcoin to sign transactions. It is a one-way formula, where a user’s public key can be generated from their private key. But, with an individual’s public key, a fraudulent person can’t compute that individual’s private key.
P2PKH (Pay to PubKey Hash): when transactions are made, the cryptocurrency is directed to the hash of the receiver’s public key rather than just their public key as it is in P2PK (Pay to PubKey). This adds more security and privacy to transactions
Runtime in Big O Notation: runtime refers to how long a function takes to execute especially as we scale the input size. E.g. O(n^2) < O(2^n)
NP (Nondeterministic Polynomial Runtime): NP problems are problems that can be solved in polynomial runtime. In Big O notation, that refers to n to any power.
NP Hard: refers to problems that are “at least as hard as the hardest problems in NP”
NP Complete: refers to problems whose solutions can be quickly verified in polynomial runtime
Quantum computing: development of a computer that utilizes properties studied in quantum theory, such as atomic and subatomic behavior of material and energy.
Qubits (Quantum Bits) enable subatomic particles such as electrons to exist in more than one state at a time. This duality enables a ‘wavelike’ state. When qubits link with each other, their wavelike states will interfere with each other, facilitating an extremely, extremely efficient performance of calculations—can cut down runtime by a million years even!
As we herald in the web3 era and the quantum era, there’s a lot to cheer on. Blockchain promises disruption of the status quo with decentralized systems in healthcare, supply chain logistics, and even insurance. At the same time, quantum computing will furnish a heightened supply of computing power to propel fields such as machine learning and computational chemistry.
Just as qubits can coexist in a state of 1 and 0, can we successfully coexist in the quantum era and the web3 era while propelling innovations in both realms? This question boils down to cryptography—blockchain’s best friend but quantum computing’s target of attack. Cryptographic primitives provide the basis for blockchain privacy and security as seen in hash functions and asymmetric encryption schemes such as ECDSA—they rely on the “impossibility” of classical computers in respectively performing prime factorization on large numbers and solving the discrete logarithm problem over an ellipse. Unfortunately, despite the boons that quantum computing will bring, it will be able to solve these “impossible” problems that classical computers can’t solve, threatening these cryptographic primitives and thereby the entire blockchain ecosystem. Though current quantum computers haven’t attained this yet, by 2035, it is predicted that quantum-cyber attacks will be able to break state-of-the-art blockchain cryptography techniques.
Though some cryptographers believe that this isn’t an immediate threat, it truly is a race against time. With merely a decade, we need to analyze effective post-quantum blockchain cryptography methods, as there are some concerning vulnerabilities in current blockchain implementations.
Looking deeper into the classic blockchain architecture, Bitcoin, we can identify some of these vulnerabilities, and discuss some potential solutions.
The Bitcoin network relies on a Proof of Work mechanism where miners expend computational power to compute a SHA-256 block hash after determining a valid nonce to a preimage cryptographic hash puzzle—an NP-complete problem. What’s great about PoW is that dishonest nodes are disincentivized from mining since the costs of mining a fraudulent block outweigh the extremely minute probability of the block being accepted by the honest nodes into the honest blockchain. However, quantum computing’s Grover’s search algorithm threatens this disincentive by guaranteeing a solution to any NP-complete problem—in this case the cryptographic hash puzzle—with a quadratically faster runtime in comparison to classical techniques. Using this algorithm, dishonest nodes can perform PoW much faster than the rest of the network combined and conduct a 51% attack, thereby leaving the honest nodes no choice but to accept these fraudulent blocks into the honest chain. By 2028, with advances in quantum computing, such a 51% attack may be possible. The functionality of blockchain and thereby Bitcoin is contingent on the honest nodes being able to build a long and honest chain, but such quantum computing advances will destroy this consensus functionality of blockchain.
Even more seriously, quantum computing’s Shor’s algorithm threatens the public key cryptography mechanism fueled by ECDSA (Elliptic Curve Digital Signature Algorithm). ECDSA is a trap-door function on classical computers, meaning, though the public key can be computed from the private key (by multiplying the private key by a base point on the curve), the reverse isn’t true. The computational hardness of determining the private key from the public key is what Bitcoin relies on, but Shor’s algorithm enables this reversal. With proper advances, a quantum computer will be able to find this private key in merely O(n3) time in comparison to the O(2n) time of classical computers.
But doesn’t Bitcoin now employ P2PKH addresses instead of P2PK due to concerns of quantum computing? Since public keys are hashed now, aren’t private keys safe from computation? In order to be deemed quantum-resistant, the public key should never be revealed publicly even for a moment. However, even with P2PKH addresses, as soon as BTC is transferred from a P2PKH address, it is public knowledge that can be exploited by quantum computers until the transaction is ingrained in a mined block. During that period before it is mined, a quantum computer can compute the private key from the public key and forge a transaction addressed to itself from the private key it computed in order to steal BTC. It takes ~10 minutes to mine a block, and if a quantum computer is developed to take less than 10 minutes to break ECDSA, the fraudulent transaction can be mined in place of the original one, placing the BTC at risk for theft. In just over a decade, this might be possible.
So now we see single transactions are vulnerable. But, even entire wallets themselves are vulnerable to quantum attack. If users use their P2PKH addresses again after their public key was publicly revealed for a transaction, all the coins in their wallets can be stolen, which is why users are encouraged to avoid reusing P2PKH addresses. Since users have fortunately adopted this practice to a large extent, the amount of BTC in reused P2PKH addresses has dwindled to ~2.5M BTC. Unfortunately, all users who joined at the inception of Bitcoin set up P2PK addresses which means that their public keys are out in the open for quantum computers to compute the private keys and steal the 2M BTC that all these P2PK addresses together hold. Over 4M BTC, valued at 40B USD and comprising a whopping 25% of the total BTC in the network, from both reused P2PKH addresses and P2PK addresses is sitting clearly in the line of attack for quantum computers. If all of this trapped BTC is stolen, Bitcoin’s value will tremendously decline and so will belief in the technology.
Fixing These Vulnerabilities. Wait... Can we even?
How can these trapped BTC be saved from quantum computing? The issue with many of these addresses is that the owners have lost their private keys which means they have no access to the BTC held within. A possible solution is to gain approval from users in the network via consensus to transfer these BTC to new addresses assigned to the owners who should both store their private key and stop reusing P2PKH addresses from then on.
To fix the root problem of quantum computers being able to compute private keys from public keys in the first place, can we replace ECDSA with quantum-resistant alternatives? Lattice-based cryptography is one alternative. It relies on solving problems such as the Short Vector Problem—finding the shortest non-zero vector between 2 points in the lattice—which is NP-hard and inefficient to solve even on a quantum computer. Another alternative, multivariate polynomial-based cryptography, relies on solving systems of multivariate polynomial equations which is also computationally hard even on quantum computers.
But, we still haven’t addressed a possible solution to prevent 51% attacks by quantum computers that can perform PoW much faster. In fact, these attacks seem inescapable unless a majority of the Bitcoin network also use quantum computers to keep pace with any fraudulent quantum computers or unless we shift to a different proof of work mechanism.
As we race against time to fix these vulnerabilities in blockchain through post-quantum algorithms so that we can coexist in the web3 era and the quantum era, an even more fascinating and out-of-the-world next thought arises—quantum blockchain, or in other words, combatting quantum with quantum. Can we design the blockchain to be quantum itself?
[1] https://www.sciencedirect.com/science/article/pii/S2590005621000138
[2]https://cloudsecurityalliance.org/artifacts/blockchains-in-the-quantum-era/
[3]https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410
[4]https://www.sciencedirect.com/science/article/pii/S2590005622000650
[6]https://spectrum.ieee.org/quantum-blockchains-could-act-like-time-machines
[7]https://medium.com/coinmonks/public-and-private-keys-in-cryptocurrency-c0910d6a1c20
[8]https://analyticsindiamag.com/top-applications-of-quantum-computing-everyone-should-know-about/
[9]https://www.ibm.com/topics/quantum-computing
By: Riteka Murugesh
Blockchain: an unalterable record of transactions that is public and distributed across a peer-to-peer network. Facilitates decentralization, transparency, and traceability of transactions.
Cryptocurrency: digital currency that IS NOT issued by a central entity
Bitcoin: a popular cryptocurrency to allow transactions directly between peers, cutting out the middlemen such as banks.
ECDSA (Elliptic Curve Digital Signature Algorithm): a cryptographic algorithm used in Bitcoin to sign transactions. It is a one-way formula, where a user’s public key can be generated from their private key. But, with an individual’s public key, a fraudulent person can’t compute that individual’s private key.
P2PKH (Pay to PubKey Hash): when transactions are made, the cryptocurrency is directed to the hash of the receiver’s public key rather than just their public key as it is in P2PK (Pay to PubKey). This adds more security and privacy to transactions
Runtime in Big O Notation: runtime refers to how long a function takes to execute especially as we scale the input size. E.g. O(n^2) < O(2^n)
NP (Nondeterministic Polynomial Runtime): NP problems are problems that can be solved in polynomial runtime. In Big O notation, that refers to n to any power.
NP Hard: refers to problems that are “at least as hard as the hardest problems in NP”
NP Complete: refers to problems whose solutions can be quickly verified in polynomial runtime
Quantum computing: development of a computer that utilizes properties studied in quantum theory, such as atomic and subatomic behavior of material and energy.
Qubits (Quantum Bits) enable subatomic particles such as electrons to exist in more than one state at a time. This duality enables a ‘wavelike’ state. When qubits link with each other, their wavelike states will interfere with each other, facilitating an extremely, extremely efficient performance of calculations—can cut down runtime by a million years even!
As we herald in the web3 era and the quantum era, there’s a lot to cheer on. Blockchain promises disruption of the status quo with decentralized systems in healthcare, supply chain logistics, and even insurance. At the same time, quantum computing will furnish a heightened supply of computing power to propel fields such as machine learning and computational chemistry.
Just as qubits can coexist in a state of 1 and 0, can we successfully coexist in the quantum era and the web3 era while propelling innovations in both realms? This question boils down to cryptography—blockchain’s best friend but quantum computing’s target of attack. Cryptographic primitives provide the basis for blockchain privacy and security as seen in hash functions and asymmetric encryption schemes such as ECDSA—they rely on the “impossibility” of classical computers in respectively performing prime factorization on large numbers and solving the discrete logarithm problem over an ellipse. Unfortunately, despite the boons that quantum computing will bring, it will be able to solve these “impossible” problems that classical computers can’t solve, threatening these cryptographic primitives and thereby the entire blockchain ecosystem. Though current quantum computers haven’t attained this yet, by 2035, it is predicted that quantum-cyber attacks will be able to break state-of-the-art blockchain cryptography techniques.
Though some cryptographers believe that this isn’t an immediate threat, it truly is a race against time. With merely a decade, we need to analyze effective post-quantum blockchain cryptography methods, as there are some concerning vulnerabilities in current blockchain implementations.
Looking deeper into the classic blockchain architecture, Bitcoin, we can identify some of these vulnerabilities, and discuss some potential solutions.
The Bitcoin network relies on a Proof of Work mechanism where miners expend computational power to compute a SHA-256 block hash after determining a valid nonce to a preimage cryptographic hash puzzle—an NP-complete problem. What’s great about PoW is that dishonest nodes are disincentivized from mining since the costs of mining a fraudulent block outweigh the extremely minute probability of the block being accepted by the honest nodes into the honest blockchain. However, quantum computing’s Grover’s search algorithm threatens this disincentive by guaranteeing a solution to any NP-complete problem—in this case the cryptographic hash puzzle—with a quadratically faster runtime in comparison to classical techniques. Using this algorithm, dishonest nodes can perform PoW much faster than the rest of the network combined and conduct a 51% attack, thereby leaving the honest nodes no choice but to accept these fraudulent blocks into the honest chain. By 2028, with advances in quantum computing, such a 51% attack may be possible. The functionality of blockchain and thereby Bitcoin is contingent on the honest nodes being able to build a long and honest chain, but such quantum computing advances will destroy this consensus functionality of blockchain.
Even more seriously, quantum computing’s Shor’s algorithm threatens the public key cryptography mechanism fueled by ECDSA (Elliptic Curve Digital Signature Algorithm). ECDSA is a trap-door function on classical computers, meaning, though the public key can be computed from the private key (by multiplying the private key by a base point on the curve), the reverse isn’t true. The computational hardness of determining the private key from the public key is what Bitcoin relies on, but Shor’s algorithm enables this reversal. With proper advances, a quantum computer will be able to find this private key in merely O(n3) time in comparison to the O(2n) time of classical computers.
But doesn’t Bitcoin now employ P2PKH addresses instead of P2PK due to concerns of quantum computing? Since public keys are hashed now, aren’t private keys safe from computation? In order to be deemed quantum-resistant, the public key should never be revealed publicly even for a moment. However, even with P2PKH addresses, as soon as BTC is transferred from a P2PKH address, it is public knowledge that can be exploited by quantum computers until the transaction is ingrained in a mined block. During that period before it is mined, a quantum computer can compute the private key from the public key and forge a transaction addressed to itself from the private key it computed in order to steal BTC. It takes ~10 minutes to mine a block, and if a quantum computer is developed to take less than 10 minutes to break ECDSA, the fraudulent transaction can be mined in place of the original one, placing the BTC at risk for theft. In just over a decade, this might be possible.
So now we see single transactions are vulnerable. But, even entire wallets themselves are vulnerable to quantum attack. If users use their P2PKH addresses again after their public key was publicly revealed for a transaction, all the coins in their wallets can be stolen, which is why users are encouraged to avoid reusing P2PKH addresses. Since users have fortunately adopted this practice to a large extent, the amount of BTC in reused P2PKH addresses has dwindled to ~2.5M BTC. Unfortunately, all users who joined at the inception of Bitcoin set up P2PK addresses which means that their public keys are out in the open for quantum computers to compute the private keys and steal the 2M BTC that all these P2PK addresses together hold. Over 4M BTC, valued at 40B USD and comprising a whopping 25% of the total BTC in the network, from both reused P2PKH addresses and P2PK addresses is sitting clearly in the line of attack for quantum computers. If all of this trapped BTC is stolen, Bitcoin’s value will tremendously decline and so will belief in the technology.
Fixing These Vulnerabilities. Wait... Can we even?
How can these trapped BTC be saved from quantum computing? The issue with many of these addresses is that the owners have lost their private keys which means they have no access to the BTC held within. A possible solution is to gain approval from users in the network via consensus to transfer these BTC to new addresses assigned to the owners who should both store their private key and stop reusing P2PKH addresses from then on.
To fix the root problem of quantum computers being able to compute private keys from public keys in the first place, can we replace ECDSA with quantum-resistant alternatives? Lattice-based cryptography is one alternative. It relies on solving problems such as the Short Vector Problem—finding the shortest non-zero vector between 2 points in the lattice—which is NP-hard and inefficient to solve even on a quantum computer. Another alternative, multivariate polynomial-based cryptography, relies on solving systems of multivariate polynomial equations which is also computationally hard even on quantum computers.
But, we still haven’t addressed a possible solution to prevent 51% attacks by quantum computers that can perform PoW much faster. In fact, these attacks seem inescapable unless a majority of the Bitcoin network also use quantum computers to keep pace with any fraudulent quantum computers or unless we shift to a different proof of work mechanism.
As we race against time to fix these vulnerabilities in blockchain through post-quantum algorithms so that we can coexist in the web3 era and the quantum era, an even more fascinating and out-of-the-world next thought arises—quantum blockchain, or in other words, combatting quantum with quantum. Can we design the blockchain to be quantum itself?
[1] https://www.sciencedirect.com/science/article/pii/S2590005621000138
[2]https://cloudsecurityalliance.org/artifacts/blockchains-in-the-quantum-era/
[3]https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410
[4]https://www.sciencedirect.com/science/article/pii/S2590005622000650
[6]https://spectrum.ieee.org/quantum-blockchains-could-act-like-time-machines
[7]https://medium.com/coinmonks/public-and-private-keys-in-cryptocurrency-c0910d6a1c20
[8]https://analyticsindiamag.com/top-applications-of-quantum-computing-everyone-should-know-about/
[9]https://www.ibm.com/topics/quantum-computing
Blockchain at Berkeley
Blockchain at Berkeley
No comments yet