# A variety of mathematical proof-of-work problems will provide better security for cryptocurrencies than hash-based proof-of-work problems

I have some great news. For the first time, the total market cap as of 5/23/2017 for all cryptocurrencies is at \$80,000,000,000 (a month ago it was at \$30,000,000,000 but who knows what it will be in a month or two). Furthermore, as of 5/17/2017, for the first time cryptocurrencies other than Bitcoin consist of more than 50 percent of the total market cap for all cryptocurrencies. These historic events should not be taken lightly. I predict that in the future, cryptocurrencies will for the most part replace fiat currencies. The rise of cryptocurrencies will undoubtably change the world in many important ways. For example, some have predicted that cryptocurrencies will end all war (it will be hard to fund wars with cryptocurrencies)! To learn more about cryptocurrencies, you can read the original paper on the first cryptocurrency Bitcoin.

A proof-of-work problem is a computational problem that one must do to in order to produce new coins in the cryptocurrency and to maintain the security of the cryptocurrency. For example, in Bitcoin, the proof-of-work problem consists of finding suitable strings which produce exceptionally low SHA-256 hashes (the hashes must be low enough so that only one person produces a such hash every 10 minutes or so). In this post, I am going to outline how employing many different kinds of more mathematical proof-of-work problems will provide much better security for cryptocurrencies than if one were to employ only one type of proof-of-work problem and how some of the issues that arise with useful proof-of-work problems are resolvable.

I believe that hash problems are popular proof-of-work problems for cryptocurrencies not because they are the best but simply because they are simple and these hash-based proof of work problems have been the best proof of work problems in instances where a proof-of-work was needed before cryptocurrencies came into being. For example, hash-based proof-of-work problems are used to thwart denial-of-service attacks and spam since for a normal user the proof-of-work problems are not too difficult to solve but the problems will be too difficult for an attacker to compute. While the hash-based proof-of-work problems are ideal to thwarting denial-of-service attacks and spammers, they are not ideal as proof-of-work schemes for cryptocurrencies.

Cryptocurrencies with a many kinds of proof-of-work problems can satisfy very lax requirements compared to cryptocurrencies with only one type of proof-of-work problem.

The security of cryptocurrencies depends on the fact that no single entity can solve more than 50 percent of the proof-of-work problems. If a malicious entity solves more than 50 percent of the proof-of-work problems, then such an entity can undermine the security of the entire cryptocurrency (such an attack is called a 51 percent attack). If a cryptocurrency has only one kind of proof-of-work problem, then that proof-of-work problem must satisfy very strict requirements. But if the same cryptocurrency has many different kinds of proof-of-work problems, then those proof-of-work problems are only required to satisfy relatively mild conditions, and it is therefore feasible for many useful proof-of-work problems to satisfy those conditions (here temporarily assume that there is a good protocol for removing broken proof-of-work problems). Let me list those conditions right here.

The conditions colored orange are always absolutely essential for any proof-of-work problem on a cryptocurrency. The conditions colored green are essential when there is only one kind of proof-of-work problem, but these conditions in green are not necessary when there are many different kinds of proof-of-work problems for the cryptocurrency.

1. Verifiable but intractible

-These problems need to be difficult to solve but it must be easy to verify the solution to these problems.

2. Utility

The solution to the problem should have other uses than simply securing the cryptocurrency. The solution should have practical applications as well, or at the very least, the solutions to the problem should advance mathematics or science. Right now, the proof-of-work problem for Bitcoin is amounts to simply finding data whose SHA-256 hash is exceptionally low.

3. Scalability.

For Bitcoin, the proof-of-work problems need to be solved approximately every 10 minutes (with an exponential distribution), and in any cryptocurrency, the proof-of-work problem must consistently be solved in about the same amount of time. As time goes on, the proof-of-work problems need to get more difficult to accomodate for faster computers, quicker algorithms, more people working on the problem, and more specialized computer chips solving the problem. If $X$ is the distribution of the amount of time it takes to compute the proof-of-work problem, then $X$ should have a consistent mean and the distributions $X,1/X$ should have low variance (we do not want to solve the problem for one block in one second and solve the problem for the next block in one hour).

4. Efficient automatic generation

-The proof-of-work problems need to be generated automatically based on the previous blocks in the blockchain. Cryptocurrencies are decentralized so there cannot be a central agency which assigns each individual proof-of-work problem.

5. Progress-freeness

Progress freeness for search problems means that the probability that the first solution is found at time $t$ follows an exponential distribution. Progress freeness for problems whose objective is to optimize $f(x)$ means that for all $\alpha$ the probability of finding a solution where $f(x)\geq\alpha$ at time $t$ follows an exponential distribution. In other words, solutions are found randomly without regard of how long one has been working on obtaining a solution. Said differently, if Alice spends 30 minutes attempting to find a solution without finding a solution, then Alice will not have any advantage if she has not spent any of the 30 minutes searching for a solution. If there is only one kind of proof-of-work problem for a cryptocurrency, and that proof-of-work problem is far from progress free, then the entity who has the fastest computer will always win, and such an entity could launch a 51 percent attack. As an extreme example of why progress-freeness is needed, suppose that a problem always takes 1000 steps to solve. If Alice has a computer that can do 500 steps a second and Bob has a computer that can do 1000 steps a second, then Bob will solve the problem in 1 second and Alice will solve the problem in 2 seconds. Therefore Bob will always win. However, a lack of progress freeness is no longer a problem if in the cryptocurrency, there are many proof-of-work problems running simultaneously. For example, in the above scenario, even if Bob is able to solve a particular problem better than everyone else, Bob will have to spend much of his computational power solving that particular problem, and Bob will not have enough resources to solve the other proof-of-work problems, and therefore Bob will be unable to launch a 51 percent attack.

6. Optimization-freeness

By optimization-freeness, I mean that people need to be confident that in the future an entity will not be able to obtain a faster algorithm than we have today. The motivation behind optimization freeness is that if an entity has a secret algorithm which is much faster or better than all the other algorithms, then such an entity will be able to launch a 51 percent attack. However, a cryptocurrency employs many different kinds of proof-of-work problems, then such an entity will be able to solve a particular problem better than all others but that entity will not be able to launch a 51 percent attack. In fact, if a cryptocurrency employs many different kinds of proof-of-work problems, then optimization freeness will make the cryptocurrency less secure instead of more secure.

7. Pre-computation resistance

Pre-computation refers to when an entity solves a proof-of-work problem before the proof-of-work problem for a particular block is determined.

8. Unlimited problems

There needs to be an unlimited supply of proof-of-work problems to solve. This is only an issue if there is only one kind of proof-of-work problem for the cryptocurrency. If there are many kinds of proof-of-work problems in a cryptocurrency, then a particular type of proof-of-work problem can simply be removed by an automatic procedure or when all of the particular instances of the problem have been solved.

The problem-removal-protocol

So for a cryptocurrency which employs many different kinds of proof-of-work problems, the list of all problems which are currently being used in the cryptocurrency shall be called the problem schedule. If there are many different types of proof-of-work problems in the problem schedule, there is a good chance that a few of these proof-of-work problems should eventually be broken and should therefore be removed from the problem schedule. Since cryptocurrencies are meant to be as decentralized as possible, the process of removing broken proof-of-work problems from he problem schedule needs to be done automatically without a change to the programming of the cryptocurrency. Let me therefore list three different ways that a proof-of-work problem could be automatically removed from the problem schedule.

1. Formal proof of break

The proof-of-work problem will be considered to be broken and removed from the problem schedule if an entity submits a formal proof that the proof-of-work problem can be solved in polynomial time. The entity who submits the formal proof will win a pre-determined number of blocks in the blockchain and hence new coins.

2. Heuristic algorithm for break

The proof-of-work problem will be considered to be broken and removed form the problem schedule if an entity named Alice submits an algorithm that breaks the proof-of-work problem. For search problems, the algorithm is simply expected to consistently find a fast and accurate solution even if the difficulty of the proof-of-work problem is increased to very high levels. For optimization problems, the breaking algorithm must quickly and consistently give solutions which are at least as good as solutions obtained using other algorithms. In the case of optimization problems broken by a heuristic algorithm, the protocol for removing a problem from the problem schedule is more involved. Alice will first need to openly submit her algorithm for solving the proof-of-work problem. Alice is then required to follow her own algorithm and obtain a solution which is at least as optimized as the solutions produced by all other entities (keep in mind that other entities may use Alice’s algorithm or attempt to improve upon Alice’s algorithm. Furthermore, the optimization process will last long enough for other entities to attempt to improve upon Alice’s algorithm). If Alice satisfies these requirements, then the problem is removed from the problem schedule, Alice is given a pre-determined number of blocks in the blockchain, and Alice will be awarded plenty of coins.

3. Automatic removal of broken proof-of-work problems

For search problems, if the proof-of-work problem is repeatedly quickly solved (possibly with multiple solutions) even when the difficulty of the problem increases without bounds, then the proof-of-work problem will be automatically removed from the problem schedule. For optimization problems, if the best solution or best solutions are consistently obtained early within the timespan for solving the problem, then the proof-of-work problem will automatically be removed from the problem schedule and after the problem is removed, no entity will be awarded any blocks in the blockchain as a prize.

The automatic removal system should preferrably be implemented in a way so that an entity with a secret algorithm can always provide the best solutions to this proof-of-work problem simply by producing solutions which always win but which fall below the threshold-of-removal. However, the automatic removal system should also be implemented so that if the secret algorithm that breaks the system becomes publicly available, then the problem will easily be removed. In other words, an entity can cross the threshold-of-removal if he wants to but such an entity can just as easily remain just below the threshold-of-removal in order to obtain many coins.

The benefits of having many kinds of proof-of-work problems

The most obvious benefit to our composite proof-of-work system with many kinds of proof-of-work problems is that our proof-of-work system allows for a wide flexibility of problems and hence it allows for proof-of-work problems which have useful benefits besides securing the cryptocurrency.

Useful proof-of-work problems will greatly benefit cryptocurrencies

Useful proof-of-work problems will obviously provide benefits since the solution to those proof-of-work problems will have practical applications or at least advance mathematics. Useful proof-of-work problems will also provide a benefit to the cryptocurrencies themselves since useful proof-of-work problems will greatly help the public image of cryptocurrencies.

The public image of cryptocurrencies is one of the most important battles that advocates of cryptocurrencies must face. After all, cryptocurrencies directly threaten many of the powers that governments possess, and governments have the power to ban cryptocurrencies. Not only can governments ban cryptocurrencies, but powerful governments also have the power to undermine the security of cryptocurrencies by launching 51 percent attacks against them since governments have nearly unlimited resources. Cryptocurrencies therefore need to obtain and maintain a strong public image in order to avoid governmental backlash as much as possible.

Another reason for cryptocurrencies need to obtain a strong public image is that cryptocurrencies are still new and many people do not consider cryptocurrencies as legitimate currencies (those dinosaurs are wrong). People therefore need to accept cryptocurrencies as legitimate currency.

Today, many people view the process of mining cryptocurrencies and maintaining the blockchain for a cryptocurrency as being incredibly wasteful and bad for the environment, and these criticisms against cryptocurrencies are justified. Cryptocurrency advocates would respond by saying that cryptocurrency mining is useful for securing and decentralizing the blockchain and hence not wasteful, but in any case, it is much better and much more efficient for these proof-of-work problems to have applications besides securing the blockchain (many cryptocurrencies have attempted to do away with proof-of-work problems since proof-of-work problems are seen as wasteful). I personally will not give cryptocurrencies my full endorsement until they are used to solve useful problems with mathematical, scientific, or practical merit.

Today people receive about 4 million dollars worth of bitcoins every day from mining these bitcoins. Unfortunately, in order to mine these bitcoins, people need to use much energy to power the computers that make these calculations. Imagine how much cryptocurrencies can be used to advance mathematics and science if the proof-of-work problems are selected with scientific advancements in mind. Imagine how much these advancements to science could boost the public image of cryptocurrencies.

A multitude of proof-of-work problems will increase the security of cryptocurrencies

It is less obvious that our composite proof-of-work system also strengthens the security of the cryptocurrency against 51 percent attacks. It is much more straightforward for an entity to launch a 51 percent attack against a cryptocurrency with only one type of proof-of-work problem than it is to launch an attack against a cryptocurrency with many types of proof-of-work problems. After all, to launch a 51 percent attack against a single proof-of-work hash-based problem, one must simply spend a lot of money to produce a lot of ASICs for solving that problem and at any time the attacker can completely break the problem. On the other hand, to launch a 51 percent attack against many proof-of-work problems, one must obtain many different types of ASICs in order to solve many different kinds of problems. Furthermore, in some cases, an attacker may not be able to solve some of these problems since the attacker may not have access to a secret algorithm for solving this problem, and an attacker will not have access to some specialized knowledge which will allow one to quickly solve the problem.

How our system could be implemented on established cryptocurrencies

Cryptocurrencies are supposed to be decentralized currencies. Since cryptocurrencies are supposed to be decentralized, there should be as few changes to cryptocurrencies as possible. This poses a problem for cryptocurrencies which are attempting to switch from useless proof-of-work problems to useful proof-of-work problems. My solution is to only make a change to the cryptocurrency protocol once. In order to minimize backlash and other chaos, the changes stated in the cryptocurrency protocol will be implemented gradually. Let me now give an example of how the change from useless proof-of-work problems to useful proof-of-work problems could take place. Let $t$ be the number of years before the change of the proof-of-work protocol were to take place. When $t=-4$, the cryptocurrency will begin selecting 144 different proof-of-work problems to be used in the cryptocurrency. At time $t=-1$, all 144 of the proof-of-work problems will be selected and the changes to the cryptocurrency protocol will be finalized. At time $t=0$, the cryptocurrency protocol will be modified but these modifications will take effect over a process of 6 years. Every day an average of 144 blocks will be generated. Every month from time $t=0$ to time $t=6$, two out of these 144 proof-of-work problems will be selected at random to be implemented into the problem schedule. At the $m$-th month from $t=0$, every day approximately $144-2m$ of the blocks on the blockchain will have a hash-based proof-of-work problem while the $2m$ other blocks will be from the 144 proof-of-work problems which have already been implemented into the problem schedule. At time $t=10$, a collection of new proof-of-work problems will be selected to replace the problems which have already been broken or which will be broken in the future.