A technique that could be used to construct and improve proof-of-work problems.

In this post, I am going to talk about a trick using hash functions that takes computational problems and makes them suited or better suited to use as cryptocurrency proof-of-work (POW) problems. Yes, this trick can be applied to any potential cryptocurrency POW problem.

Review and references

If you are already familiar with cryptocurrencies and cryptocurrency POW problems, then feel free to skip this section. If you are not familiar with cryptocurrencies and their POW problems, then please read Satoshi Nakamoto’s paper Bitcoin. For a more in-depth study of cryptocurrencies, I recommend the coursera course Bitcoin and Cryptocurrency Technologies (there is also a book Bitcoin and Cryptocurrency Technologies that I recommend).

If you have not read Satoshi Nakamoto’s paper and don’t plan to right now, then just take note that many cryptocurrencies are distributed by solving computational problems which are known as proof-of-work problems; the process of solving these problems is known as mining.

Requirements for cryptocurrency POW problems

Consider the following characteristics which are desirable or required in POW problems.

1. (Verifiable but intractible) The problem must be difficult to solve yet easy to verify.
2. (Fine tunability) The difficulty of the problem must be finely tunable so that coins are distributed at a constant rate.
3. (Automatic generation) Instances of the problem must be generated automatically and efficiently.
4. (Solution tied to block and solver) The solutions must depend on the block and the solver of the block so that a valid solution for Alice will no longer be a valid solution for Bob.
5. (Usefulness) The solution to the problem together with the process of obtaining the solution should have enough value outside the cryptocurrency to justify the resources used to solve the problem.

Let me now add a few more desired characteristics for proof-of-work problems.

1. (Endless problems) There should be an unlimited amount of problems to work on so that the POW will not quickly expire.
2. (Unbreakability) The problem should be cryptographically secure in the sense that it should be thought to be impossible for an entity to have a secret algorithm that solves the POW problem at a much faster rate than everyone else can. If an entity has a secret algorithm, then that entity could launch a 51 percent attack, and such a secret algorithm will produce an unfair wealth distribution.
3. (Progress-freeness and pre-computation resistance) Suppose that Alice and Bob are working on the POW problem and they both have an equal amount of computational power. If Alice has not solved the problem but Alice has started working on the problem five minutes ago, then Alice should have no advantage over Bob in solving the POW problem. Furthermore, Alice should have no way of computing the solutions in advance. The chance of someone solving the mining problem needs to be directly proportional to her computational power.

The multi-algorithm approach

So one way to alleviate the issues that arise with useful POW problems is to use multiple POW problems so that the cryptocurrency does not fall apart in the case that there is a bad POW problem or in the case that a POW problem becomes bad. Characteristics 1-4 and i-iii are required for all cryptocurrencies with a single POW problem, but characteristics i-iii though desired are not required for cryptocurrencies with many POW problems.

There may be some POW problems which are useful up to a point but where the practical value of these problems satisfies the law of diminishing returns, but with a multi-algorithm POW, certain problems may be retired from the problem schedule when their practical value is no longer worth the computational effort put into solving them. Multiple algorithm POW problems also help alleviate the initial distribution problem for cryptocurrencies since multiple algorithms will distribute a new cryptocurrency more evenly and fairly than a single algorithm could.

A POW scheme consisting of many algorithms is much more complex than a single algorithm scheme and it will take much more work to develop a multi-algorithm POW scheme than a single algorithm POW (in a multi-algorithm POW scheme, one also needs to develop techniques for removing broken or outdated problems; for example, in a multi-algorithm POW, one will need to have a system that automatically removes a broken problem once someone submits a formal proof that the POW problem can be solved in polynomial time).

The solution lottery technique

The solution lottery technique is a tool that one can use to make a POW problem obtain several of the advantages of hash based POW problems without any of their disadvantages. Stated informally, the solution lottery technique (SLT) is a technique where one increases the difficulty of a POW problem without changing any other characteristic of the POW problem simply by only accepting solutions with exceptionally low hashes. While the SLT uses hash functions, the SLT is designed so that a miner seldomly calls upon a hash function in order to solve the POW problems. Therefore, miners will focus their energy on solving the main problem rather than computing hashes.

Let me now state how the SLT is applied to a typical POW problem. Suppose that $D$ is a set of ordered pairs. Suppose that $H$ is a cryptographic hash function and $\text{Data}(k,x)$ is a piece of information that can be easily obtained when after one verifies that $(k,x)\in D$ but which cannot be obtained if one does not verify whether $(k,x)\in D$ or not.

Problem A without SLT: The objective of Problem A is to find an input $x$ and a suitable hash $k$ so that $(k,x)\in D$.

Problem A with SLT: The objective of Problem A with SLT is to find an input $x$ along with a suitable hash $k$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$.
For Problem A with or without the SLT, the data $k$ may be reused many times, so one does not have to compute very many hashes $k$ but one has to determine whether $(k,x)\in D$ many times. Similarly, one only has to compute the hash $H(k||x||\text{Data}(k,x))$ if $(k,x)\in D$. Since hash functions are computed seldomly with the SLT, miners will devote almost all of their resources into finding pairs $(k,x)\in D$ rather than in computing hashes, and hence the POW problems will retain their characteristics such as usefulness or ASIC resistance with or without the SLT. The input $\text{Data}(k,x)$ is necessary for the SLT to opeate correctly since otherwise a miner would solve Problem A with SLT simply by first computing $H(k||x)$ and if $H(k||x) < C$, then the miner would verify whether $(k,x)\in D$ (and hence the miner would most of the resources computing hashes rather than determinine whether $(k,x)\in D$).
Let us now look at a few ways that the SLT can improve cryptocurrency POW problems.

Fine-tunability: It may be difficult to fine tune the difficulty of a certain POW problem. However, with the SLT, it is much easier to fine tune the difficulty of the POW problem since the software simply has to adjust the parameter $C$ in order to make the problem easier or more difficult.

Smoothly tuning coarse parameters with SLT: In some POW problems, changing the set $D$ could change the difficulty of the POW problem in an unpredictable manner. The SLT could help smoothly change the set $D$ in these cases. Suppose that the POW problem at block $n$ is to find a hash $k$ and data $x$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$. Then the POW starting in block $n+1$ would be to find a hash $k$ and data $x$ so that ($(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$) or ($(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$) where $C'$ is chosen so that it is easier to find $k,x$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$ than it is to find $k,x$ so that $(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$. Then the constant $C'$ will gradually increase. At the same time, the constant $C$ will decrease so that the difficulty of the POW problem remains constant until $C=0$ and when $C=0$, the POW problem will simply be to find $k,x$ so that $(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$.
Security boost: The SLT can also take very low security POW problems and make these problems viable as cryptocurrency POW problems even though their security level without the SLT is very low.