Can any computational challenge be transformed to proof-of-work?

Question

The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO. I wonder whether there exists an algorithm that can convert practically any computational challenge $\mathcal C$ (whose solution can be verified efficiently) into another such challenge $\Psi(\mathcal C)$ (which is used for proof-of-work) such that

1. The function $\Psi$ is randomized, using some (public) random sequence $r$.
2. Solving $\Psi(\mathcal C)$ is typically as hard as solving $\mathcal C$.
3. If a solution $x$ is found for $\Psi(\mathcal C)$, then a solution $\Psi^{-1}(x)$ can be efficiently computed for the original challenge $\mathcal C$.
4. Knowing a solution for $\mathcal C$ does not help in finding a solution for $\Psi(\mathcal C)$.

$\;\:\:$4' (Update). As pointed out by Noah in a comment, the previous condition should be strengthened to requiring that preprocessing $\mathcal C$ should also not give any advantage in solving $\Psi(\mathcal C)$.

This last condition is required so that no one can be put into an advantageous position just because they know a solution of $\mathcal C$. Using this method, people could submit computational problems that they want solved and a central authority could pick some worthy of solving (like finding aliens vs. breaking passwords). Note that it doesn't seem to be an issue if the problem takes even a week to solve (I guess those aliens can't be that good in hiding ;), as this could result in a bigger reward for a solution. Anyways, these topics are not related to the solution of my theoretical problem, but of course I'm happy to discuss them in the comments/on the forum.

A possible solution would be the following: $\Psi$ maps $\mathcal C$ into $(\mathcal C,HASH_r)$, that is, to solving $\mathcal C$ and some other, computationally hard challenge. One problem with this is that knowing a solution to $\mathcal C$ does make solving $\Psi(\mathcal C)$ somewhat easier (how much easier depends on the difficulty of $HASH_r$). Another issue is that $\Psi(\mathcal C)$ became more difficult than $\mathcal C$.

Answer 1

(Note: Andreas Björklund suggested a solution in the comments that I believe is better than the one described below. See http://eprint.iacr.org/2017/203, by Ball, Rosen, Sabin, and Vasudevan. In short, they give proofs of work based on problems like Orthogonal Vectors whose hardness is well understood and to which many problems (e.g., k-SAT) can be reduced relatively efficiently. Their PoW instance $\Psi(\mathcal{C})$ is as hard as a worst-case Orthogonal Vectors, even if the input instance $\mathcal{C}$ is easy, so that they avoid a major drawback of the solution described below.

The solution described below might benefit from its simplicity---it can be described to a non-expert---but it seems to me to be much less interesting theoretically.)

A solution is possible if one makes the strong assumption that "the fastest algorithm for $\mathcal{C}$ is fundamentally randomized" (and if we model a cryptographic hash function as a random oracle). One way to formalize this is to say that

1. $\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$ (otherwise, I guess it's not really a valid challenge);
2. the fastest randomized algorithm for $\mathcal{C}$ runs in expected time $T$ on a typical instance; and
3. there exists an efficiently computable function $f$ from $\{0,1\}^k$ to the domain of solutions to $\mathcal{C}$ for $k \approx \log_2 T$ such that there always exists an $s \in \{0,1\}^k$ with $f(s)$ a solution to $\mathcal{C}$.

Notice that the assumption that $k \approx \log_2 T$ implies that brute-force search of $\{0,1\}^k$ is essentially the optimal algorithm for $\mathcal{C}$. So, this is quite a strong assumption. On the other hand, if $\mathcal{C}$ does not satisfy these properties, then it's hard for me to imagine satisfying both your conditions (2) and (4).

Then, given a hash function $H : \{0,1\}^* \to \{0,1\}^k$, which we model as a random oracle, we define $\Psi_H(\mathcal{C}; r)$ as follows, where $r \in \{0,1\}^\ell$ for some $\ell \gg k$ is the random input to $\Psi_H$. The goal is to output $x \in \{0,1\}^*$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. In other words, $(r,x)$ should hash to "good random coins" for the above algorithm.

Let's see that this satisfies all of your conditions.

1. "The function $\Psi$ is randomized, using some (public) random sequence $r$." Check!
2. "Solving $\Psi(\mathcal{C})$ is typically as hard as solving $\mathcal{C}$." Notice that the simple randomized algorithm for $\Psi_H(\mathcal{C},r)$ runs in expected time at most $2^k$ plus polynomial overhead, and by assumption $2^k \approx T$ is essentially the running time of the optimal algorithm for $\mathcal{C}$.
3. "If a solution $x$ is found for $\Psi(\mathcal{C})$, then a solution $\Psi^{-1}(x)$ can be efficiently computed for the original challenge $\mathcal{C}$." This can be done by computing $f(H(r,x))$, which is a solution to $\mathcal{C}$ by assumption.
4. "Knowing a solution for $\mathcal{C}$ does not help in finding a solution for $\Psi(\mathcal{C})$." By definition, solving $\Psi_H(\mathcal{C}; r)$ requires finding $x$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. Since we modeled $H$ as a random oracle, we can lower bound the expected running time of any algorithm that solves this problem by the optimal expected query complexity of the query problem in which $H$ is given by a black box and we are asked to find a solution to the same problem. And, again because $H$ is a random oracle, the expected query complexity is just the inverse of the fraction of elements $x \in \{0,1\}^k$ that are solutions (up to a constant factor). By assumption, the optimal expected running time of any algorithm for $\mathcal{C}$ is $T \approx 2^{k}$, which implies that this fraction cannot be much larger than $2^{-k}$. Since $\ell \gg k$ and $r \in \{0,1\}^\ell$ is chosen uniformly at random, this is even true with preprocessing that is allowed to depend on $H$ and $\mathcal{C}$ (but not $r$), and in particular it is true even if we know a solution to $\mathcal{C}$ in advance.

Answer 2

The following simple technique which I call the solution lottery technique (SLT) can be used in conjunction with other techniques (such as having multiple POW problems, the technique mentioned in Noah Stephens-Davidowitz's answer, etc) to help transform computational challenges into viable proof of work problems. The SLT helps ameliorate issues with cryptocurrency mining problems other than conditions 1-4.

Suppose that $\mathcal{C}$ is a computational challenge of the form “find a suitable hash $k$ along with a string $x$ such that $(k,x)\in D$.”

Problem $\Psi(\mathcal{C})$ setup: Suppose that $D$ is a set, $H$ is a cryptographic hash function, and $C$ is some constant. Suppose furthermore that $\textrm{Data}(k,x)$ is a piece of information that is easy to obtain after one determines that $(k,x)\in D$ but which cannot be obtained otherwise.

Problem $\Psi(\mathcal{C})$ objective: Find a pair $(k,x)$ such that $k$ is a suitable hash and where $(k,x)\in D$, and where $H(k||x||\textrm{Data}(k,x))<C$.

Let us now investigate how problem $\Psi(\mathcal{C})$ satisfies requirements 1-4.

1. We have to assume $\mathcal{C}$ is already randomized for the SLT to satisfy this property.

2-3. $\Psi(\mathcal{C})$ will typically become more difficult than $\mathcal{C}$ and this is a good thing. The difficulty of a proof-of-work problem needs to be finely tunable, but the original problem $\mathcal{C}$ may or may not have a finely tunable level of difficulty (remember that the difficulty in mining Bitcoin is adjusted every two weeks). The difficulty of problem $\Psi(\mathcal{C})$ is equal to the difficulty of finding some suitable $(k,x)\in D$ multiplied by $\frac{2^{n}}{C}$. Therefore, since the constant $C$ is finely tunable, the difficulty of $\Psi(\mathcal{C})$ is also finely tunable.

Even though the problem $\Psi(\mathcal{C})$ is more difficult than the original problem $\mathcal{C}$, almost all of the work for solving the problem $\Psi(\mathcal{C})$ will be spent on simply finding a pair $(k,x)$ with $(k,x)\in D$ rather than computing hashes (one cannot compute whether $H(k||x||\textrm{Data}(k,x))<C$ or not until one has computed $\textrm{Data}(k,x)$ and one cannot compute $\textrm{Data}(k,x)$ unless one verifies that $\textrm{Data}(k,x)\in D$).

Of course, the fact that $\Psi(\mathcal{C})$ is more difficult than $\mathcal{C}$ presents some new concerns. For a useful problem, it is most likely the case that one would want to store the pairs $(k,x)$ where $(k,x)\in D$ in some database. However, in order to receive the block reward, the miner must only reveal a pair $(k,x)$ where $(k,x)\in D$ and $H(k||x||\textrm{Data}(k,x))<C$ instead of all the pairs $(k,x)\in D$ regardless of whether $H(k||x||\textrm{Data}(k,x))<C$ or not. One possible solution to this problem is for the miners to simply reveal all pairs $(k,x)$ where $(k,x)\in D$ out of courtesy. Miners will also have the ability to reject chains if the miners have not posted their fair share of pairs $(k,x)\in D$. Perhaps, one should count the number of pairs $(k,x)\in D$ for the calculation as to who has the longest valid chain as well. If most of the miners post their solutions, then the process of solving $\Psi(\mathcal{C})$ will produce just as many solutions as the process of solving $\mathcal{C}$.

In the scenario where the miners post all of the pairs $(k,x)\in D$, $\Psi(\mathcal{C})$ would satisfy the spirit of conditions 2-3.

4. $\Psi(\mathcal{C})$ may or may not satisfy condition $4$ depending on the specific problem.

$\textbf{Other Advantages of this technique:}$

The SLT offers other advantages than conditions 1-4 which are desirable or necessary for a proof-of-work problem.

1. Improving the security/efficiency balance: The SLT will help in the case that $\mathcal{C}$ may be too easy to solve or too difficult to verify. In general, $\Psi(\mathcal{C})$ is much more difficult to solve than $\mathcal{C}$, but $\Psi(\mathcal{C})$ is about as easy to verify as $\mathcal{C}$.

2. Removal of a broken/insecure problem: The SLT could be used to algorithmically remove bad POW problems in a cryptocurrency with a backup POW-problem and multiple POW problems. Suppose that an entity finds a very quick algorithm for solving problem $\mathcal{C}$. Then such a problem is no longer a suitable proof-of-work problem and it should be removed from the cryptocurrency. The cryptocurrency must therefore have an algorithm that removes $\mathcal{C}$ from the cryptocurrency whenever someone has posted an algorithm that solves problem $\mathcal{C}$ too quickly but which never removes problem $\mathcal{C}$ otherwise. Here is an outline of such a problem removal algorithm being used to remove a problem which we shall call Problem $A$.

a. Alice pays a large fee (the fee will cover the costs that the miners incur for verifying the algorithm) and then posts the algorithm which we shall call Algorithm K that breaks Problem $A$ to the blockchain. If Algorithm K relies upon a large quantity of pre-computed data $PC$, then Alice posts the Merkle root of this pre-computed data $PC$.

b. Random instances of Problem A are produced by the Blockchain. Alice then posts the portions of the pre-computed data which are needed for Algorithm K to work correctly along with their Merkle branch in order to prove that the data actually came from $PC$. If Alice's algorithm fed with the pre-computed data $PC$ quickly, then the problem is removed and Alice receives a reward for posting the algorithm that removes the problem from the blockchain.

This problem removal procedure is computationally expensive on the miners and validators. However, the SLT removes most of the computational difficulty of this technique so that it can be used if needed in a cryptocurrency (instances which this technique is used will probably be quite rare).

3. Mining pools are more feasible: In cryptocurrencies, it is often very difficult to win the block reward. Since the block rewards are very difficult to win, miners often mine in things called mining pools in which the miners combine their resources in solving a problem and in which they share the block reward in proportion to the amount of “near misses” they have found. A possible issue for $\mathcal{C}$ is that it may be difficult to produce a qualitative notion of what constitutes as a “near miss” for the problem $\mathcal{C}$ and the algorithm for finding a near miss may be different from the algorithm for solving $\mathcal{C}$. Since the pool miners will be looking for near misses, they may not be very efficient at solving $\mathcal{C}$ (and hence, few people will join mining pools). However, for $\Psi(\mathcal{C})$, there is a clear cut notion of a near miss, namely, a near miss is a pair $(k,x)$ where $(k,x)\in D$ but where $H(k||x||\textrm{Data}(k,x))\geq C$, and the algorithm for finding near misses for $\Psi(\mathcal{C})$ will be the same as the algorithm for finding solutions to $\Psi(\mathcal{C})$.

4. Progress freeness: A proof-of-work problem $P$ is said to be progress free if the amount of time it takes for an entity or group of entities to find next block on the blockchain follows the exponential distribution $e^{-\lambda x}$ where the constant $\lambda$ is directly proportional to the amount of computational power that entity is using to solve Problem $P$. Progress freeness is required for cryptocurrency mining problems in order for the miners to receive a block reward in proportion to their mining power to achieve decentralization. The SLT certainly helps mining problems achieve progress freeness.