A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the probability of success of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the probability of success of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.

Dec 1, 20210 citations

Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search.

Alexandru Cojocaru, Juan A. Garay, Aggelos Kiayias +2 more

Bitcoin and its underlying blockchain protocol have recently received significant attention in the context of building distributed systems and foundations of the consensus problem. At the same time, the rapid development in quantum computing makes the threats to cryptography more and more concerning. In this work, we revisit the formal security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), in the presence of quantum adversaries -- i.e. adversaries equipped with quantum computers. We show that the security of the Bitcoin backbone holds under a quantum analogue of the ``honest majority'' assumption that we develop. The critical ingredient of proving security of the blockchain is to analyzing the quantum query complexity of a Chain-of-Proofs-of-Work search problem. This problem in turn reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. This can be viewed as an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the powerful recording technique due to Zhandry (Crypto 2019). Our analysis indicates that the security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the probability of success of a single classical query to the protocol's underlying hash function. Perhaps surprisingly, the wait time for safe settlement of transactions in the case of quantum adversaries matches (up to a constant) the safe settlement time in the classical case and thus does not result in any further overhead.Bitcoin and its underlying blockchain protocol have recently received significant attention in the context of building distributed systems and foundations of the consensus problem. At the same time, the rapid development in quantum computing makes the threats to cryptography more and more concerning. In this work, we revisit the formal security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), in the presence of quantum adversaries -- i.e. adversaries equipped with quantum computers. We show that the security of the Bitcoin backbone holds under a quantum analogue of the ``honest majority'' assumption that we develop. The critical ingredient of proving security of the blockchain is to analyzing the quantum query complexity of a Chain-of-Proofs-of-Work search problem. This problem in turn reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. This can be viewed as an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the powerful recording technique due to Zhandry (Crypto 2019). Our analysis indicates that the security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the probability of success of a single classical query to the protocol's underlying hash function. Perhaps surprisingly, the wait time for safe settlement of transactions in the case of quantum adversaries matches (up to a constant) the safe settlement time in the classical case and thus does not result in any further overhead.

Dec 30, 20203 citations

Generalized Hybrid Search and Applications to Blockchain and Hash Function Security

Alexandru Cojocaru, Juan A. Garay, Fang Song

In this work we first examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. We then construct a hybrid quantum-classical search algorithm and analyze its success probability. Regarding the former, for search problems that are allowed to have multiple solutions and in which the input is sampled according to arbitrary distributions we establish their hybrid quantum-classical query complexities -- i.e., given a fixed number of classical and quantum queries, determine what is the probability of solving the search task. At a technical level, our results generalize the framework for hybrid quantum-classical search algorithms proposed by Rosmanis. Namely, for an arbitrary distribution $D$ on Boolean functions, the probability an algorithm equipped with $τ_c$ classical and $τ_q$ quantum queries succeeds in finding a preimage of $1$ for a function sampled from $D$ is at most $ν_D \cdot(2\sqrt{τ_c} + 2τ_q + 1)^2$ , where $ν_D$ captures the average (over $D$ ) fraction of preimages of $1$ . As applications of our hardness results, we first revisit and generalize the security of the Bitcoin protocol called the Bitcoin backbone, to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we examine the generic security of hash functions against hybrid adversaries. Regarding our second contribution, we design a hybrid algorithm which first spends all of its classical queries and in the second stage runs a ``modified Grover'' where the initial state depends on the distribution $D$ . We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.In this work we first examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. We then construct a hybrid quantum-classical search algorithm and analyze its success probability. Regarding the former, for search problems that are allowed to have multiple solutions and in which the input is sampled according to arbitrary distributions we establish their hybrid quantum-classical query complexities -- i.e., given a fixed number of classical and quantum queries, determine what is the probability of solving the search task. At a technical level, our results generalize the framework for hybrid quantum-classical search algorithms proposed by Rosmanis. Namely, for an arbitrary distribution $D$ on Boolean functions, the probability an algorithm equipped with $τ_c$ classical and $τ_q$ quantum queries succeeds in finding a preimage of $1$ for a function sampled from $D$ is at most $ν_D \cdot(2\sqrt{τ_c} + 2τ_q + 1)^2$, where $ν_D$ captures the average (over $D$) fraction of preimages of $1$. As applications of our hardness results, we first revisit and generalize the security of the Bitcoin protocol called the Bitcoin backbone, to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we examine the generic security of hash functions against hybrid adversaries. Regarding our second contribution, we design a hybrid algorithm which first spends all of its classical queries and in the second stage runs a ``modified Grover'' where the initial state depends on the distribution $D$. We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.

arXiv:2311.03723Nov 7, 20230 citations

Quantum Advantage on Proof of Work

Dan A. Bard, Joseph J. Kearney, Carlos A. Pérez-Delgado

Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.

arXiv:2105.01821May 5, 20212 citations

Quantum advantage on proof of work

Dan A. Bard, Joseph J. Kearney, Carlos A. Pérez-Delgado

ArrayJul 6, 202225 citations

On the Security of Proofs of Sequential Work in a Post-Quantum World

Jeremiah Blocki, Seunghoon Lee, Samson Zhou

A Proof of Sequential Work (PoSW) allows a prover to convince a resource-bounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depth-robust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depth-robust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long $\mathcal{H}$ -sequence and that any malicious party running in sequential time $T-1$ will fail to produce an $\mathcal{H}$ -sequence of length $T$ except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time $T-1$ will fail to produce an $\mathcal{H}$ -sequence except with negligible probability -- even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry's recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak's efficient construction (EUROCRYPT 2018).A Proof of Sequential Work (PoSW) allows a prover to convince a resource-bounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depth-robust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depth-robust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long $\mathcal{H}$-sequence and that any malicious party running in sequential time $T-1$ will fail to produce an $\mathcal{H}$-sequence of length $T$ except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time $T-1$ will fail to produce an $\mathcal{H}$-sequence except with negligible probability -- even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry's recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak's efficient construction (EUROCRYPT 2018).

arXiv:2006.10972Leibniz international proceedings in informaticsJun 19, 202012 citations

O(p^{-1/2})

classical ones, where

p

is the probability of success of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.

O(p^{-1/2})

classical ones, where

p

is the probability of success of a single classical query to the protocol's underlying hash function. Perhaps surprisingly, the wait time for safe settlement of transactions in the case of quantum adversaries matches (up to a constant) the safe settlement time in the classical case and thus does not result in any further overhead.

D

on Boolean functions, the probability an algorithm equipped with

τ_c

classical and

τ_q

quantum queries succeeds in finding a preimage of

1

for a function sampled from

D

is at most

ν_D \cdot(2\sqrt{τ_c} + 2τ_q + 1)^2

, where

ν_D

captures the average (over

D

) fraction of preimages of

1

. As applications of our hardness results, we first revisit and generalize the security of the Bitcoin protocol called the Bitcoin backbone, to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we examine the generic security of hash functions against hybrid adversaries. Regarding our second contribution, we design a hybrid algorithm which first spends all of its classical queries and in the second stage runs a ``modified Grover'' where the initial state depends on the distribution

D

. We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.

\mathcal{H}

-sequence and that any malicious party running in sequential time

T-1

will fail to produce an

\mathcal{H}

-sequence of length

T

except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time

T-1

will fail to produce an

\mathcal{H}

-sequence except with negligible probability -- even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry's recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak's efficient construction (EUROCRYPT 2018).