# 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.

Progress freeness: The SLT could also be used to take a POW problem which is not progress free and make it into a problem which is progress free. For example, suppose that one wants to use a POW problem that incentivizes the development of computers that can perform tasks at higher and higher frequencies (I am currently as of January of 2018 not endorsing nor opposing this kind of POW problem as a useful POW problem). Then the POW problem should be a problem which can be easily verified but where the most efficient algorithm for solving the POW problem requires one to perform N steps in a sequence so that the person with the computer that runs at the highest frequency always wins the block reward. This POW problem without the SLT however is a very bad problem for cryptocurrencies since the entity with the fastest processor will always win; this problem is not progress free. However, the SLT can take this problem and turn it into a progress free problem which still incentivizes people to develop faster computers. Suppose that $N$-step version of this POW problem without the SLT is to find a pair $(k,x)$ such that $(k,x)\in D_{N}$. Then the goal of this POW problem with the SLT is to find a pair $(k,x)$ where $k$ is a hash and $x$ is data so that $(k,x)\in D_{N}$ and $H(k||x||\text{Data}(k,x)) Suppose that the problem of finding a suitable hash$k$along with data$x$so that$(k,x)\in D$has only 32 bits of security. Furthermore, suppose that any increase in the security level of the cryptocurrency POW problem will make the verification of the POW problem too inefficient to use in practice (useful POW problems tend to take a much longer time to validate than useless POW problems). Then while the problem of finding some$(k,x)\in D$will not be a viable POW problem since its difficulty cannot be increased beyond 32 bits of security, the problem of finding some$(k,x)\in D$where$H(k||x||\text{Data}(k,x)) < C$could be made arbitrarily difficult. The lost solution problem for the SLT In a useful POW problem that employs the SLT where the solutions to the problems themselves are of a practical use, someone needs to keep a record of the solutions$(k,x)$where$(k,x)\in D$but$H(k||x||\text{Data}(k,x)) \geq C$which are thrown out using the solution lottery technique; the fact that the SLT throws out useful solutions to a POW problem shall be called the lost solution problem (LSP) for this post. The solution thrown out by the SLT do not need to be posted on the blockchain nor should they be put on the blockchain, but they need to be publicly available. For useful POW problems where the process of obtaining a solution rather than the solution itself is what is important, the LSP is not an issue, but it is an issue to useful POW problems where the solution itself is of interest. The most basic solution to the LSP is for the miners to post their inputs$(k,x)$where$k$is an appropriate hash and where$(k,x)\in D$but$H(k||x||\text{Data}(k,x))\geq C$or where$(k,x)$is an otherwise good solution simply as a matter of courtesy. Miners would probably be willing to post these solutions as a matter of courtesy since it does not take very much work to post these solutions. If a miner is discourteous and does not post his solutions, then the POW will not be as useful as it could be, but the cryptocurrency will not suffer from any security weaknesses, so discourteous miners can only do a limited amount of harm against the reputation of the cryptocurrency. Courtesy may not be a strong enough incentive for miners to compel them to post their solutions since courtesy does not give miners any financial incentive. Furthermore, if the miners have an incentive to keep their solutions as a secret, they will not be willing to post their solutions simply out of courtesy. Therefore, in order to solve the SLT problem by incentivizing miners to post their solutions, the cryptocurrency protocol should require all miners to accept the blockchain fork backed up with the highest number of posted solutions$(k,x)$such that$(k,x)\in D$. Since the cryptocurrency miners do not want their blocks to become orphan blocks, they will post all of their solutions$(k,x)$such that$(k,x)\in D$and they will only mine on the fork with the most solutions$(k,x)$such that$(k,x)\in D\$. The miners may also be encouraged to boycott all chains if they suspect that the miner has not posted all of his solutions and such a boycott against suspected bad miners may be incorporated into the cryptocurrency protocol (for a simplistic example of such a protocol, the protocol could be to always accept a block from an established miner over a block from a new miner (or someone pretending to be a new miner) if the new miner does not post at least the average number of solutions per block and to outright reject all blocks from established miners if they are suspected of intentionally withholding more than 10 percent of solutions with a 3 sigma confidence).

Conclusion

It will probably be very difficult to make useful POW problems if one just used a single algorithm per cryptocurrency that does not employ the SLT. However, if one uses many kinds of POW problems in a cryptocurrency and if one employs the SLT in many of these problems, then constructing a new useful POW problem is no longer as difficult. With multiple POW problems and with the SLT a useful POW problem only needs to be useful, difficult to solve, easy to verify, automatically generated, and the solutions need to be tied to the solver and the blockchain. Since the problem of constructing useful POW problems is a tractible applied mathematics research problem with great economic benefit, it will be a good idea for mathematicians and other experts to work on developing such problems.