Vulnerability of Blockchain Technologies to Quantum Attacks

Quantum computers work by exploiting quantum physical effects to decrease the time required to solve (certain) computational problems by creating and utilizing quantum superpositions.

There are two main families of quantum algorithms that are relevant to the current discussion: subgroup-finding algorithms, and amplitude amplification.

The first class of algorithms is best represented by Shor’s algorithm[5]. This algorithm can both factor large integers and solve the discrete logarithm in polynomial time. In particular, it can factor an integer $N$ in time $O\left(\log^{2}N\log\log N\log\log\log N\right)$ (or more succinctly $O\left(\log^{3}N\right)$) and space $O\left(\log N\right)$. Or, as a function of the input size (in bits) $n=\log N$, Shor’s algorithm runs in time $O\left(n^{2}\log n\log\log n\right)$ (or more succinctly $O\left(n^{3}\right)$), using space $O\left(n\right)$.

This is particularly relevant because most public-key cryptosystems deployed today—including RSA, EC, ElGamal and Diffie–Hellman—rely on the computational hardness of either one of these two problems. In order to understand the magnitude of the issue, one can take RSA 2048 as an example. This is considered the ‘gold standard’ for security at the time of writing. A simple calculation shows that it would take a classical computer with a 5Ghz CPU roughly 13.7 billion years to break an RSA 2048 cipher using current best techniques. A quantum computer operating at 10Mhz would be able to do it in roughly 42 minutes¹¹1We calculate this by taking the number of quantum gates—counting error-correction—needed to factor an RSA 2048 public-key.. In order to do so, however, a device needs to be able to hold in quantum memory a state large enough to represent (at least) both the input to the problem, and the output. As discussed earlier, it can be estimated that a quantum computer large enough to break RSA-2048 will likely be ready by the year 2035 (see e.g.[2, 3]).

The second class of algorithm—amplitude amplification[6, 7]—consists of generalizations of Grover’s search algorithm[8]. These algorithms allow for a solution to be found in any search space of cardinality $N$ in time $O\left(\sqrt{N}\right)$. In short, this allows for any NP-Complete problem to be solved quadratically faster than any known classical algorithm. While the speed-up is a lot less dramatic than in the previous case, the importance of these algorithms rests in their general applicability. In short, any problem whose solution can be verified efficiently (i.e. any problem in NP) admits a quadratic quantum speed-up. Amplitude amplification algorithms are particularly relevant here because many, if not all, consensus algorithms for blockchain technologies rely on solving NP-Complete problems (more details below).

Blockchain and Distributed Ledger Technology (DLT) markets are predicted to be valued at $7.59 billion by 2024 [9]. Industries that have strong use cases include finance[10], logistics[11], and legal fields [12], with many large global corporations getting on board and integrating the technology: for example IBM [13], JP Morgan[14] and Amazon [15], with Facebook also announcing their own cryptocurrency Libra[16]. This technology removes the need for a trusted third-party to enable the transfer of data and assets.

Blockchains work on group consensus; the validity of a transaction is determined by a group of nodes that need not trust one another. The blockchain is managed by independent nodes that must reach consensus before updating the ledger with newly validated transactions. There are many mechanisms that enable a network to gain consensus, the most popular being Proof-of-Work (PoW)[17]. This consensus mechanism and underlying cryptographical techniques give blockchains their trustless ability. In general, blockchains work through the linkage of blocks in chronological order. These blocks are groups of transactions of information or cryptocurrency that nodes have broadcast to the network. This forms an immutable series of information, or a chain. Each block in the chain will contain a group of transactions and their information that has been declared to the network. This is generally through the transfer of tokens (cryptocurrency). These tokens hold intrinsic value like traditional fiat currencies—rather than simply hold information about that value like, say, a bank account balance. However, unlike tradition currencies, they are not minted by a central bank. Tokens are distributed to miners, who are nodes that form the group consensus and as such perform work on the network, as a reward for good work. This work primarily consists of creating the blocks in the chain as well as validating that the transactions are well formed and are mathematically fair on the network, i.e. not creating or destroying tokens and not spending more than the user transferring tokens can afford. It is through this group consensus that the network and underlying economy of the network can function fairly and independently of any central authority.

Blockchain technologies can be simplified down to two constituent parts, the consensus protocol and the transaction mechanism. The transaction mechanism is how actors transfer tokens and information; this requires them to provide a digital signature in order to authenticate that they possess the public and private key used to create the digital signature. The consensus mechanism dictates how the verifiers or mining nodes on the network agree on the next blockchain update, which transactions are added, and whether the transactions and the block are cryptographically and structurally valid.

PoW is the most commonly used consensus mechanism within a blockchain. PoW requires a miner to prove that they have committed a certain amount of effort through the expenditure of computing resources to generate the new block. This mechanism was adopted by Bitcoin forcing the miner, while compiling transactions into a block, to perform some work, i.e. spend computational and financial resources to solve a problem. This incentivizes the miner to generate a valid block containing only valid transactions. This work is also easily verified by a any node connected to the network. This expended energy guarantees that a cost is associated with creating a block. Careless or malicious miners that expend the energy to complete a PoW algorithm but have created a bad block (a block that includes at least one transaction that if included into the chain would create a wrong state, e.g. spending over a user’s balance) will be discovered by other nodes in the network. The block will be invalid and this would not be considered by other miners as part of the main chain, leaving the miner financially worse off, as they would receive no mining reward. This ensures the validity of the information contained within the block that is considered by the network as the head of the current longest chain (the block to which miners will attempt to append the next block in the chain). The hardness of this PoW determines how quickly each block is added to the chain: if the hardness of the problem increases then it will take miners longer to solve the problem as it will require more work to be performed by the mining nodes [18].

Determination of the ownership of assets within a blockchain network is comparatively more complex when compared to centrally-controlled networks and financial exchanges. A holder of some tokens must be able to demonstrate that they have the ability and authority to spend the tokens. In a centralized system this is kept in check by a central authority. In decentralized systems, cryptographic techniques, such as signature schemes, must be used to demonstrate ownership.

Signature schemes allow a holder of tokens to cryptographically sign a transaction, and this signature directly relates to the user’s public/private key pair from which their account is created. There are many different signature schemes, for example ElGamal[19], RSA[20], and Schnorr [21]. Elliptic Curve Digital Signature Algorithm (ECDSA) is a signature scheme that relies on the difficulty of solving the discrete logarithm problem over elliptic curves. Compared to other schemes, ECDSA allows for the same level security using smaller keys—for instance, 256 bits compared to 2048 bits in the case of RSA [22]. Signing and verification speed as well as compact signature size are all essential for blockchain technologies. This makes ECDSA particularly well-suited for use in blockchains. However, given its reliance on the discrete logarithm problem for its security, coupled with its smaller key-sizes, ECDSA is particularly vulnerable to quantum attacks[23].

Bitcoin, first described in a paper by a person or a group under the pseudonym Satoshi Nakamoto [55], is the most popular and first true blockchain technology. The 2008 paper paved the way for the development of the distributed ledger technological space. Designed as a peer to peer payment method, it removed the need for a central authority. It is underpinned by cryptographic schemes that allow peers in the network to validate transactions in a trustless environment, and store these in a ledger that is cryptographically secure and immutable. These cryptographic techniques are secure from attack on a classical computer, however, they can be exploited by a sufficiently powerful quantum computer.

Bitcoin uses Hashcash as its PoW mechanism. Hashcash[56] was originally designed as a denial of service countermeasure for email systems. This was done by requiring the potential sender to expend time solving a computationally hard problem, before being able to send an email. As implemented in Bitcoin, Hashcash requires the prospective miner to calculate a SHA-256 hash value for the header—plus some random number— so that the hash value is smaller than a predetermined number. This number is an adjustable parameter in the Bitcoin network. The smaller the number, the higher the computational difficulty of the problem.

The use of the Hashcash PoW mechanism has two net effects. One, with the current high difficulty parameter, miners are incentivized to use specialist hardware, such as ASIC miners, and/or join mining pools where the work and reward are divided among various users. More importantly, PoW de-incentivizes attempts to add bad blocks to the networks. These blocks have a very high chance of being rejected by the network due to error correction, and therefore ensuring very high wasted costs on the potential miner.

The transaction mechanism within Bitcoin uses ECDSA signature scheme in order to prove authority and ownership of tokens, as well as irrefutable evidence that the tokens have been spent and that the transaction has not been meddled with after the transaction has been signed. The elliptic-curve Bitcoin employs for its ECDSA is secp256-k1. The signature in Bitcoin is made up of two values $S$ and $R$ [57]. $R$ is the $x$ coordinate of a point of an elliptic curve²²2A further description of elliptic-curve cryptography can be found here[58].. This point is the public key of an ephemeral public / private key pair, created by a user during the process of signing the transaction. $S$, the other half of the signature can then be created as follows: $S=k^{-1}(SHA256(m)+dA\cdot R)~{}mod~{}p$. Where $k$ is the temporary private key, $SHA256(m)$ is the hash of the transaction message, $dA$ is the signing private key, and $p$ is the prime order of the elliptic field. Given $S$ and $R$ of a signature, the signature can be validated by any user as $K$, the ephemeral public key, can be found from the two parts of the signature. During this process a user must also declare the public key associated with their account in order for validation to occur. This process signature is required for every input of a transaction, otherwise the transaction will be invalid and will not be added in a block in the blockchain.

Bitcoin and its underlying cryptographic schemes are vulnerable to possible quantum attacks. One such attack uses Grover’s search algorithm to perform PoW at a much faster rate than classical miners. An attacker would aim to generate just over as much PoW as the rest of the network combined—effectively forcing consensus on any block the attacker so desires (this is known as a 51% attack).

Current ASIC miners are capable of performing roughly 18TH/s. This, combined with the current sizes of Bitcoin networks, makes a quantum based 51% attack infeasible for the time being. Our own calculations based on current ASIC technology, as well as that of other authors[3, 2], put the earliest likely date that this type of attack will be possible at 2028. However, advances in ASIC technology are likely to push back this date much farther.

However, the most damaging attack on the Bitcoin blockchain is on its ECDSA scheme; more specifically upon transactions that had been declared to the network and not yet added to the blockchain. The hardness of ECDSA relies on the hardness of the Elliptic Curve Discrete Logarithm Problem. As noted in the previous section, this problem can be solved in polynomial time $O(n^{3})$ on a quantum computer of sufficient size where on a classical computer it can be solved in exponential time at approximately $O(2^{n})$. While on the bitcoin network it could be possible to not only hijack individual transaction it must also be considered that a quantum attack could also aim to take control of a users entire bitcoin wallet. If the same public / private key pair is used to hold the users bitcoin after the public key becomes public knowledge, then all funds secured by the key pair will be vulnerable. However, it must also be considered that bitcoin wallets tend to not repeatedly use the same key pairs. Bitcoin transactions send an entire UTXO (potentially multiple depending on whether the user is in possession of one UTXO that is greater than the amount to be transacted). In the most simple form of bitcoin transaction, one UTXO will be spent as the input, there will then be two outputs. One creates a new UTXO of the amount being transferred to the relevant account. If the UTXO in the input is greater than the UTXO in the output a second UTXO is created as the change, which will be returned to the original user. This account where the change is sent to typically will be controlled by a newly generated public / private key pair. This means that an attack designed to get access to the entirety of the users wallet while possible on the bitcoin network is less likely by the common security mechanism of changing the public / private key pair after every transaction.

An effective quantum attack would consist of finding the private key when the public key is revealed following the broadcast of a signed transaction to the network. This would allow an attacker to sign a new transaction using the private key, thus impersonating the key owner. As long as the quantum attacker can ensure that their transaction is placed on the blockchain before the genuine transaction, they can essentially ‘steal’ the transaction and direct the newly created Unspent Transaction Output (UTXO) into whichever account they choose. It is easy to calculate that a quantum computer with 485550 qubits and running at a clock-speed of 10GHz could solve the problem using Shor’s algorithm in 30 minutes[2]. At the same time, the average waiting time for transactions in the pool of transactions currently waiting to be integrated into a block in the Bitcoin blockchain frequently exceeds 30 minutes [59]. This makes this type of attack quite feasible.

Early in the implementation of Bitcoin it was possible for Bitcoin users to be paid directly to their public key (P2PK), rather than to the hash of the public key, which is commonly known as the user’s payment address. This has potential repercussions for older Bitcoin accounts. An example of this is the first ever Bitcoin transaction between Hal Finey and Satoshi Nakamoto at block 170 of the Bitcoin blockchain. This form of transaction is common in early coinbase transactions used to reward Bitcoin miners. This means that some of the original (often quite affluent) accounts may have revealed their public key in the early stages of the Bitcoin blockchain.

Thus, these accounts are extremely vulnerable to quantum attacks using Shor’s algorithm. Unlike the attack on the ECDSA signature scheme described earlier, there is no time limit to perform this type of attack. Once a sufficiently large quantum computer exists (estimated by the year 2035), a quantum attacker can easily calculate these accounts’ private keys, sign new transactions as these users, and empty these accounts of all their funds.

The threat of quantum attack has given rise to a project called Bitcoin Post-Quantum. [38] This project hard forked from the bitcoin network at block height 555,000 (mined on 22/12/2018). This project utilizes a quantum secure digital signature scheme [60] as well as implementing a Proof-of-Work mechanism utilizing the birthday paradox as in Z-Cash discussed in section Zcash. Because this project is a fork, however, it provides no actual security benefits to the original Bitcoin chain. Hence, the discussion in this section is still very much relevant.

In summary, Bitcoin will be very vulnerable to quantum attacks using Shor’s algorithm. The most wide-spread vulnerability open to attack will be transactions that have been declared to the network and not yet added to a block. The most vulnerable accounts are those that divulged their public-key in the earlier days of the Bitcoin network. Finally, Bitcoin’s consensus mechanism exhibits a vulnerability to Grover algorithm-based attacks. However, since Grover’s algorithm only provides a quadratic advantage, advances in classical computer technology are likely to keep Bitcoin secure against this type of attack for much longer than for Shor’s algorithm-based attacks.

Ethereum is considered the second generation of blockchain technologies. It has an associated cryptocurrency, Ether, and introduced the use of smart contracts and distributed Applications(dApps). Ethereum uses an account-based system where each transaction will deduct or add Ether to a user’s account. Smart contracts allow users of the blockchain to create a computationally-binding contract, meaning that it allows the creation of transactions dependent on certain trackable objectives.

Ethereum is currently transitioning from a Proof-of-Work (PoW) consensus mechanism, to a Proof-of-Stake (PoS) one. EthHash is a PoW mechanism that is used in the current implementation of Ethereum at the time of writing this paper. A single round of SHA-3 (Keccak-265) hashing is used to create the PoW problem, in a similar manner to Bitcoin. Mining nodes then compete to generate a hash that solves the PoW problem. The second is the currently not implemented PoS mechanism known as Casper [61]. As mentioned earlier, PoW is used to provide a computationally tasking problem to ensure that a block produced by a miner is valid. PoS however dissuades bad miners from attempting to subvert the system as they risk losing their Ether if they perform a poor job. The security in the system relies on the fact that the larger the stake the more voting power a miner will receive, by staking more coins a user is more likely to behave honestly as they have more to lose if discovered. Further security is gained from the disincentive that a user would have to own a large amount of Ether in order to perform an attack, a successful attack would inevitably cause price drops for the cryptocurrency thereby negatively impacting a user that is wealthy in ether.

Ethereum, like Bitcoin, uses a variant of the ECDSA scheme based on the secp256-k1 elliptic curve[62, 63]. In an Ethereum transaction there is no ‘from’ field, which means that the primary public key $K$ associated with account is not explicitly revealed. It can however be retrieved through a process called public key recovery where a user can reconstruct the public key from another user’s transaction signature.

Similar to Bitcoin’s consensus mechanism, a quantum attacker can make use of Grover’s algorithm to attack EthHash. We can calculate the hash rate possible on a quantum computer against the Ethereum as follows. First, we calculate the difficulty $D$ of the PoW for Ethereum: $D=\frac{H_{r}\times B}{2^{32}}$ where $H_{r}$ is the network hash rate and $B$ is the block time of the blockchain. In Ethereum $B$ is currently 16 seconds, while $H_{r}$ is currently $18\times 10^{13}$ H/s [64]. Therefore, the difficulty value is currently 670552. The equivalent hash rate for a quantum computer is $h_{q}=0.04\times s\sqrt{D}$, where $s$ is the clock speed of the computer. Even without any advances in ASIC technology, a quantum attacker would require a clock speed of about 5THz before being able to attempt a 51% attack Ethereum’s consensus mechanism.

The Ethereum signature scheme is highly insecure against attacks using Shor’s algorithm, since Ethereum’s signature scheme relies on the hardness of the discrete logarithm problem. This can be solver in polynomial time ($O(n^{3})$) using Shor’s algorithm compared to exponential time ($O(2^{n})$) on classical infrastructures. Ethereum does have one minor advantage in that it has a significantly shorter transaction processing time when compared to Bitcoin. This is countered, however, with one major disadvantage: Ethereum’s use of account-based transactions. Every single outgoing transaction needs to be signed using the account’s private key, and can be verified using the public key. Once a user has an outgoing transaction, the account’s public key is available to anyone that reconstructs it using the key recovery process mentioned earlier. A quantum assailant can thus request the public key, calculate the private key using Shor’s algorithm, and thus takeover the entire account. This vulnerability is exacerbated by the existence of tools such as Etherscan [65] that allow an assailant to search for, and target, accounts holding a large amount of Ether. This attack would be severely damaging as the potential reward (for the attacker) and loss (for the victim) would be significantly higher when compared to targeting individual transactions since the quantum attacker would be targeting an entire accounts balance of tokens.

In summary, while Ethereum has a considerably shorter block-time when compared to Bitcoin it is significantly more vulnerable to quantum attack due to its account-based transaction system. While some other blockchains allow a user to reuse the same public key for multiple transactions, it is far less common and users are dissuaded from this practice. In Ethereum, all outgoing transactions are signed using a single private/public key pair associated with the account. This makes the entire account balance vulnerable after a single outgoing transaction.

Litecoin is a source-code fork of the Bitcoin blockchain. This means that it shares many similarities with Bitcoin. However, Litecoin also has marked differences: these include the block time as well as the PoW mechanism[66]. It has very similar use-case to Bitcoin as an electronic payment method. However, due to a shorter block time, its goal is to process transactions faster than Bitcoin.

Litecoin uses a different PoW scheme than Bitcoin, called Scrypt. It has the same goal of expending computing resources in order to solve a problem to give a user authority to create the next block on the chain. Scrypt is designed to use significantly less hashing power; this can be seen in comparison with Bitcoin where the hashing rate is approximately 46,000,000TH/s [67] against 298TH/s [68] for Litecoin.

Scrypt is a simplified version of the password derivation function created by C. Percival [69], originally for the Tarsnap online backup system. Scrypt differs from other PoW schemes in that rather than being highly intensive on the processing power, it is highly intensive on the use of RAM on the mining node. This originally was chosen in order to reduce the advantage of using—and hence prevalence of—ASIC miners when compared with blockchain technologies. However it was proven relatively quickly that Scrypt was not ASIC-resistant [70].

Litecoin uses an ECDSA scheme in order to sign transactions. Similarly to Bitcoin, it implements its signature scheme using the secp-256k1 elliptic curve.

Like other PoW systems, Scrypt is potentially vulnerable to a quantum 51% attack using Grover’s algorithm. Litecoin’s current hash rate is 320TH/s[71]. Litecoin’s difficulty can be calculated as: $D=\frac{32\times 10^{13}\times 150}{2^{32}}=11175870$. Thus a quantum computer would have to run at a clock speed of 2.4 Thz to even attempt such an attack at current hash rates. This, plus future improvements in ASIC technology make this type of attacks unlikely in the foreseeable future.

Because of its use of ECDSA, Litecoin is vulnerable to quantum attacks in polynomial time of $O(n^{3})$ while using Shor’s algorithm performed against transactions that are awaiting to be incorporated into a block. This is likely to be the most profitable attack for a quantum attacker. Litecoin has the advantage of a shorter block time and a slightly quicker throughput when compared to Bitcoin. Therefore, Litecoin has some minor improved resistance against quantum attacks when compared to Bitcoin. This advantage is however minimal: given a quantum computer capable of attacking Bitcoin, a slight increase in its clock speed would suffice to make it capable of attacking Litecoin.

While this section focused on Litecoin, a similar analysis applies to many more ‘altcoins’ that are based on the Bitcoin blockchain or the original Bitcoin code. These range from direct hard forks of the Bitcoin blockchain of which there are 45 current active projects, through Bitcoin cashcitebcash, Bitcoin gold[72] and Bitcoin core[73], to source code forks like Litecoin. While a detailed discussion of each of every single ‘altcoin’ is necessarily beyond the scope of this paper, this section serves to highlight the vulnerability of all ECDSA based blockchains—which includes almost all Bitcoin forks—to quantum attacks that use Shor’s algorithm.

In summary, due to its similarities to Bitcoin, Litecoin displays the same vulnerabilities to quantum attacks. Moreover, Litecoin can be used to demonstrate the severe vulnerabilities faced by blockchain technologies based on Bitcoin.

Many of these altcoins have significantly lower transaction processing times than Bitcoin. This gives these blockchains slightly higher resilience to Shor algorithm-based attacks—though they are all ultimately quite vulnerable to such attacks.

On the other hand, given current hash rates, and likely improvements in ASIC technology, Litecoin is likely to be safe from Grover’s algorithm-based attacks on its consensus mechanisms for the foreseeable future. However, a drop in this hash rate—for example, due to a reduction of the block reward for completing the PoW as has happened before[74]—could leave the network more vulnerable.

Monero is a blockchain that focuses on the privacy of its users. A majority of blockchains advocate anonymity through the use of pseudonyms. Pseudonym identities however do not provide a user with anonymity as their pseudonym is known to other users. Through the use of chain analysis techniques it is possible to discover who has sent and received transactions, furthermore the number of tokens sent or received, or account balances. Monero provides obfuscation of both a user’s identity and value of transactions through the use of further cryptographical techniques. It offers true anonymity to its users through the use of Pedersen Commitments [75] and Range Proofs [76].

Monero uses the ASIC-resistant CryptoNight v8 PoW scheme which is derived from the Egalitarian Proof of Work from CryptoNote [77]. The scheme relies on access to slow memory at random intervals. CryptoNight is particularly memory intensive, requiring 2Mb per instance.

EdDSA is used as the signing algorithm in Monero. EdDSA is implemented using the twisted Edwards curve Ed25519. This signature scheme is a variant of ECDSA and is still reliant on the hardness of the discrete logarithm problem. A keccak-256 (SHA-3) hashing function $\mathbb{H}$ is used. The signature for signing a transaction using EdDSA is made up of two parts $R$ and $s$ [78]. First, a user must compute the hash of their private key $k$ so that $\mathbb{H}(k)$ to create $h_{k}$. They then compute $r=\mathbb{H}(h_{k},m)$ where $m$ is the message of the transaction. $r$ is then associated with a generator of the elliptic curve $G$ to form $R=rG$. The second signature component $s$ is then computed as $s=(r+\mathbb{H}(R,K,m))\cdot k$, where $K$ is the user’s public key. This signature scheme is extended in Monero, through the use of ring signatures.

A further area of interest in Monero is how it gains transaction anonymity. It does so through the use of three technologies working together: stealth addresses, ring signatures and ring confidential transactions.

In simple terms, stealth addresses and ring signatures work in the following way. For every transaction, Monero also broadcasts several ‘fake’ inputs to the transaction. Only the senders and receivers of the transaction will know which is the correct commitment for the transaction, as the senders and receivers of tokens share a secret key. Moreover, if there are multiple recipients within the transaction, only the sender will have knowledge of the whole transaction. The process consists of the user including one input using UTXO (balance) from their wallet, and padding with extra randomly selected spent outputs to the transaction up to the ring size. For instance, if the ring size is five then a further four randomly selected spent outputs are added as inputs into the transaction. Which input is the correct one (signed by the user) will not be deducible to other users[79].

The Monero network needs a way to ensure that the above transactions balance correctly, in other words that the incoming currency into the transaction equals the outgoing currency. Monero’s current mechanism for doing so is called Bulletproof,[80]. Bulletproof is a zero knowledge proof protocol that can ensure the balance of transactions. It is much more efficient than previous zero knowledge range proofs, both in computational terms and the amount of space required on the blockchain to record these proofs.

Monero very recently moved it’s PoW scheme from CryptoNight to RandomX [81]. RandomX is PoW system based on the execution of random programs in a special instruction-set that consists of integer math, floating point math and branches. This PoW system was developed with the intent of minimizing GPU advantage in PoW. However, it is possible that this may also, indirectly, lead to more quantum resiliency. As of this writing, no method for gaining quantum advantage for RandomX is known.

Monero’s signing algorithm EdDSA, like ECDSA, relies on the hardness of the discrete logarithm problem for its security, making it highly susceptible to quantum attacks using Shor’s algorithm in $O(n^{3})$ computations. However, Monero’s privacy system gives it some added level of security. An attacker would not know the amount being transferred in a target transaction. Hence, transactions of value are unobservable without prior attacks. Further, the use of RingCT means that the quantum assailant would need to solve multiple Pedersen commitments in order to find the correct public key used in the transaction. This makes Monero slightly more secure against—or at least a slightly less attractive target for—quantum assailants than other blockchain networks.

Bulletproofs are particularly susceptible to quantum attack. They rely on the discrete logarithm problem for their hardness and so similarly can be solved in polynomial time of $O(n^{3})$. The security relies on the fact that no-one knows any $xG=H$ and no $xH=G$ for the Pedersen commitment. A quantum attacker could breach the commitment revealing the values contained within. This would allow the attacker to reveal all previous transactions that have been obfuscated, since one of the key features of a blockchain is that it is immutable. While this does not have any financial benefit, the information gained could be valuable, as the hidden information may be confidential, and could potentially be used to extort users of the network.

In summary, Monero transactions are highly vulnerable to quantum attacks—though the network’s transaction anonymization makes these less attractive targets for attack than transactions in other blockchain networks. However, it should also be noted, Monero’s PoW system—RandomX—is the only such system with no known quantum vulnerabilities.

Zcash is another privacy-based blockchain. Unlike Monero, however, Zcash allows for transactions to go from private accounts to public ones, and vice versa. Anonymity is integral to the Zcash blockchain. Rather than pseudonymising the identity of users through the use of account address, input and outputs can be obfuscated. It allows private transactions as well as public transactions. Zcash transactions implement zero-knowledge proofs in the form of zk-snarks (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge); these use a trusted set up. Trusted setup uses some form of publicly-available element as part of the proving mechanism for a transaction. These publicly-available elements are either generated by a central entity, or alternatively in collaboration with the entire network in the form of a public ceremony [85]. Zk-snarks are a zero-knowledge proof system that allows a user to demonstrate that a transaction they are sending is fair while not revealing the amount being transacted. Within Zcash there are four transaction types [86]: private, deshielding, shielding and public. Private transactions obfuscate the amount being transacted at input and output. Shielding transactions obfuscate previously publicly-visible transactions, while de-shielding does the opposite. Public transactions can be considered “traditional transactions”, similar to those in other blockchains, in that they employ only pseudonym identities to protect users, and in that the value being transacted is publicly visible.

Zcash uses the Equihash PoW to gain consensus. Equihash [87] is a memory-hard PoW based on the generalized birthday problem. Equihash has the parameters $n$ and $k$. $k$ is the target value while the miner is given a sequence of $X_{1...N}$ $n$ bit strings. The miner must find $2^{k}$ distinct $X_{ij}$ such that $\oplus^{2^{k}}_{j=1}X_{ij}=0$. The solution to this problem is found using Wagner’s algorithm, which is the most efficient known algorithm for finding the solution to this problem on a classical computer.

ZCash implements EdDSA, instantiated on the Ed25519 curve. A signature consists of two parts S and R. This is defined by the scheme described in [88] and is also described in the ZCash white paper [86]. This signature scheme is reliant on the hardness of the discrete logarithm problem. The signature consists of:

• 1.

  An elliptic curve generator $B$ of mod $\mathcal{L}$

• 2.

  A cryptographic hash function $H$ which in the case of ZCash is BLAKE-2b-256.

• 3.

  $M$ which the message being signed

• 4.

  The private key $a$

• 5.

  The public key $A$ which is generated from the private key in the form $A=aB$ where $B$ is a generator on the Ed25519 elliptic curve.

First $r$ is created where $r=H(a,M)$, then $r$ is multiplied by $B$ so that it is $R=rB$. $S$ can then be computed as $S=(r+H(R,A,M)a)\text{ mod }\mathcal{L}$, giving the signature $Sig=(S,R)$.

Zk-Snarks, as previously stated, rely on a trusted set-up. This set-up requires the pre-generation of a greater public-key. This global public-key must have no private-key, otherwise the holder of such a key could create ZCash tokens at will. This greater public-key is created by many users collaboratively creating shards, or small portions, of a greater public-key from individual user private-keys. After the public ceremony, if at least one user destroys their individual private key, then attempting to find the greater public-key’s corresponding private-key becomes computationally infeasible on a classical computer. This is because this private-key can only be computed by either solving the discrete logarithm problem, or by having access to all the ephemeral private keys used to create the greater public-key.

Zcash is open to quantum attacks in three distinct ways. The first one is quantum attacks against its consensus mechanism. Grassi [89] et. al. developed a quantum algorithm for the $k-xor$ problem (generalized birthday problem), that improves on Wagner’s classical algorithm. This quantum algorithm has an improved time and memory complexity of $O\left(2^{n/(2+\lfloor log_{2}(k)\rfloor)}\right)$ compared to Wagner’s $O\left(2^{n/(1+\lfloor log_{2}(k)\rfloor)}\right)$. This opens the avenue for a quantum attack against the consensus mechanism, potentially leading to a quantum 51% attack against the network.

Since the signature scheme for ZCash is reliant on the hardness of the discrete logarithm problem, it is susceptible to quantum attacks using Shor’s Algorithm. Transactions broadcast to the network could be stolen by a quantum attacker, before they are added to the blockchain.

The global public parameter that is used in the production of zk-SNARKs, is a public-key that has no corresponding private-key and is reliant on the hardness of the discrete logarithm problem. Quantum attackers through the use of Shor’s algorithm could solve to find the global private key. This would not be reliant on the need for any further information as to how the global public parameter was created during the ceremony. With the possession of the global private key, a quantum attacker could create an infinite amount of ZCash tokens. With the private key they would not be able to access other users’ transactions being broadcast on the network. However, being able to create tokens at will, especially in a network that has obfuscated transactions this would be extremely dangerous to the network and its associated economy.

ZCash has a high vulnerability to quantum attacks. Previous examples that we have discussed are at threat to transactions being stolen once broadcast to the network. However, on ZCash the vulnerability allows a quantum assailant to create tokens. Further to this, the work shown by Grassi et al., means the consensus mechanism used by ZCash is also more vulnerable than other blockchain technologies discussed. Transactions that have been broadcast to the network are equally vulnerable, since the signing mechanism relies on the hardness of the discrete logarithm problem.