## 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. ## A warning against proof-of-stake cryptocurrencies and against altcoins I am making this post since recently several altcoins which are not mined by proof-of-work problems have gained a very high market cap and because I see a major downside to these non-minable coins. Furthermore, the newer cryptocurrencies are non-minable, and people should be very wary of non-minable coins. To make things short, there are two ways in which transactions are verified in a cryptocurrency without the use of a central authority, namely proof-of-work (POW) and proof-of-stake (POS). With POW, people gain the right to validate cryptocurrency transactions by solving a computationally difficult problem (the process of solving this problem is known as “mining”), and the people are rewarded for solving these POW problems and validating the transactions with newly minted coins and with transaction fees. The difficulty of this problem is automatically adjusted so that the average time it takes to solve the problem remains constant. POS does away with the need to solve such a computationally difficult problem. With POS, the cryptocurrency rewards an entity the right to validate transactions according to how much of the cryptocurrency the entity possesses. POS should be thought of as a cheap alternative to POW, and by cheap I mean that POS is of low quality rather than inexpensive as a result of a community unwilling to put the effort into making a good POW problem and solving these problems. In this post, I am not going to discuss whether POS is suitable as a mechanism for validating transactions in the long run since I am currently far from the best person to write about such an issue (this post will therefore not be very technical). However, I am going to make the case that one needs POW in order to fairly initially distribute a cryptocurrency and that POS is insufficient for initially distributing the cryptocurrency. Most of the ideas in this post are not original ideas and they have been broadcasted elsewhere by other people. We observe that recently POS coins have been gaining a high market cap while the POW coins have not received such great gains. Furthermore, the newer cryptocurrencies with a high market cap are all POS coins as opposed to POW coins. I also want to make it clear that my criticism of POS is only limited to the initial distribution of the coin. So there is about 800 billion dollars in cryptocurrencies floating around as of 1/06/2017. With such a high market cap, we must now ask the question as to whether the people who own these cryptocurrencies have truly earned the coins that they have. A related question one should also ask is whether the coins have been distributed evenly and fairly. If these cryptocurrencies have not been distributed fairly, we must then find and employ the best strategy for fairly distributing these new coins. One possible solution to the initial distribution problem without resorting to POW is to give every single person in a certain region of the world. For example, in the cryptocurrency Auroracoin, an equal number of coins were given to each citizen of Iceland. This solution however has its problems. Cryptocurrencies distributed like Auroracoin have a major competitive disadvantage since such cryptocurrencies are limited to certain regions of the world, and as a result any coin similar to Auroracoin will probably have a low market cap. By limiting a cryptocurrency to a certain part of the world, such a cryptocurrency is not that much different from fiat currencies since cryptocurrencies should not be limited to certain groups of people. Fairly distributing a cryptocurrency to every citizen of a nation also has some logistic disadvantages since during the initial distribution, not every citizen would accept such a cryptocurrency and there is no guarantee that the citizens of that nation would accept such a cryptocurrency in the future. It is difficult to distribute a currency if the people do not want that new currency. Auroracoin’s solution to the initial distribution problem is the best possible solution to this problem without resorting to POW. Other solutions to the initial distribution problem in a POS system are very unfair and/or logistical nightmares. For example, if the coin has been initially distributed through an ICO (initial coin offering), then one’s wealth is determined solely by how much one gives to a central non-government organization. While this method of initial distribution works well for distributing stocks, it is not a fair way to distribute new cryptocurrencies because it is necessary for cryptocurrencies to be distributed as evenly as possible. There is no way to evenly and fairly distribute a new cryptocurrency solely through a high risk ICO since ICOs distribute coins based on how much people are willing to risk their money at cryptocurrency projects which have not been launched yet and which have not stood the test of time. ICOs are unnecessary to develop a new cryptocurrency since new cryptocurrencies could be launched simply by cutting and pasting, and the development of the cryptocurrency could be funded by a sort of treasury system similar to that of the cryptocurrency Dash. Let us also observe that many ICOs are complete scams. If a cryptocurrency must use an ICO, then only a small portion of the total number of coins should be distributed through that ICO and the rest of the coins should be distributed by using POW (Ethereum has combined ICO with POW for its initial distribution and that is fine). Would you like your national currency to be initially distributed based on how much money one gives to someone who may or may not be a scam artist? Or would you instead like your national currency to be distributed to people according to how much they work for it? Many people say that POS is cheaper than POW. But the damage to an economy caused by POS because all of the wealth has been distributed to the wrong people will be much more expensive than POW could ever be. Even though I consider POW to be a fair way to initial distribute a new cryptocurrency, one still has to be careful with POW coins since POW still could have major initial distribution problems if it is not done correctly. The initial distribution mining period needs to be long enough for the cryptocurrency to be fairly distributed among the users. If most of the coins are given to the early adopters and the cryptocurrency gains a high market cap only after most of the coins have been distributed, then a few people will have an excessive amount of wealth that they have not worked for and which they have not earned. In my opinion, the initial distribution period should last at least a decade for a fair distribution, and Bitcoin’s halving period of four years is too short for newer cryptocurrencies (of course even a one year initial distribution period using POW is much better than any ICO since at least with a POW people are investing in a cryptocurrency that has been launched). With what I had said, you may be tempted to cry foul at the initial distribution of Bitcoin, but I would not consider the initial distribution of Bitcoin to be unfair in any way. The early investors into Bitcoin became rich, but they also provided a great deal of value to the cryptocurrency community. The early investors into Bitcoin were the people who made the notion of a cryptocurrency what it is today, and the early investors of Bitcoin were necessary in order for the market caps of cryptocurrencies to grow to where they are today. However, one cannot make the argument that if someone becomes rich from being an early adopter of an altcoin, then that person has truly earned his money. An early adopter of an altcoin has not helped make cryptocurrencies become mainstream so it is unfair for such an entity to have an enormous amount of wealth. The early adopters of Bitcoin also deserve their wealth because they decided to get Bitcoin early because they truly understood either how Bitcoin works or how Bitcoin is important; the same cannot be said of the early adopters of altcoins. Since Bitcoin early adopters truly deserve their wealth because they believed in the system and because they helped bring cryptocurrencies into the mainstream, one could argue that Bitcoin is the most fairly distributed cryptocurrency. The cryptocurrency must also choose a useful POW problem that has real-world applications outside of the cryptocurrency community. For example, the POW problem for Bitcoin is to find a SHA256 hash$k$so that$k < C$where$C$is a number that changes every 2016 blocks; the hashes$k$with$k < C\$ have no purpose outside of the cryptocurrency itself, nor is the process of mining bitcoins of much value. Bitcoin mining therefore becomes a nearly useless job whose only purpose outside the cryptocurrency is to keep people employed doing a nearly useless job.
A useful POW problem cannot be seen as wasteful in any way since the work needed to solve that problem will be used to advance science, technology, or mathematics.

If a person gets rich from solving useless POW problems from cryptocurrencies, then that person has not done work to improve anyone’s lives. It is not fair for someone to get rich off a cryptocurrency by performing a nearly useless job. It is definitely not fair for all coins in a cryptocurrency to arise from performing a nearly useless job.

We need a useful POW problem also because people should get paid for performing useful jobs rather than useless jobs. Unfortunately, the cryptocurrencies launched so far have not successfully employed useful POW problems, so mathematicians still have a lot of work to do.

Now, it is not solely up to the cryptocurrency authorities to solve the initial distribution problem, but the people can also help solve the initial distribution problem by investing in a diversified set of cryptocurrencies. One will incur a much lower risk by investing in a diverse set of cryptocurrencies at least until stable cryptocurrencies emerge. While useful POWs whose mining period elapses over several years will help fairly distribute cryptocurrencies, the people need to also do their part by investing in a diverse set of cryptocurrencies and creating systems that will allow others to more easily invest in a diverse set of cryptocurrencies.

I should mention that POW and POS are not the only ways of initially distributing new cryptocurrencies since one could use proof-of-burn in order to transfer coins from an existing cryptocurrency to a new cryptocurrency. However, proof-of-burn is a rarely used consensus and initial distribution mechanism, so proof-of-burn currently should not be considered to be a substitute for proof-of-work or proof-of-stake.