What computational mathematics problems that could be used as proof-of-work problems for cryptocurrencies? To make this question easier to answer, I want proof-of-work systems that work in cryptocurrencies that contain many different kinds of proof-of-work problems (the use of many different kinds of proof-of-work problems is more secure than the use of only one type of proof-of-work problem) instead of proof-of-work systems that work in cryptocurrencies with only one kind of proof-of-work problem.


Background
----------


To make things simple, cryptocurrency mining requires one to solve computational problems as a proof-of-work. For example, in Bitcoin, the miners must find data whose SHA-256 hash begins with many zeroes. Unfortunately, solutions to the proof-of-work problem for most cryptocurrencies have no intrinsic value in themselves, and these problems use up great amounts of resources and people have even made malware to solve these proof-of-work problems.


Mathematicians have a limited amount of computational resources and cryptocurrency mining could potentially supply mathematicians with a nearly unlimited amount of computational power. For example, cryptocurrency miners receive an equivalent of [millions of dollars](https://blockchain.info/charts/miners-revenue) in revenue per day and they spend much computational power solving the problems required to mine these cryptocurrencies.


Requirements
------------


Most computational mathematics problems are unsuitable as proof-of-work problems for cryptocurrencies. Here are some requirements and things we would like in such a problem.


1. $\textbf{Verifiable but intractible:}$ The problem must be difficult to solve but easy to verify. Many NP-complete problems will satisfy this requirement.
2. $\textbf{Tunability:}$ The difficulty of the problems must be fine-tunable. There should be a system in place that, given a positive real number $t$, automatically and efficiently selects a problem that can be solved on average in $t$ seconds without actually solving the problem. Optimization problems can easily be made to satisfy this requirement since with an optimization problem one can simply choose the best solution every 5 minutes or so (optimization problems may not be the best for cryptocurrencies though).
3. $\textbf{Intrinsic value:}$ The solution to the problems must have some intrinsic value. These solutions and not just the process of obtaining the solutions should be of a scientific, mathematical or practical interest.
4. $\textbf{Efficient automatic generation:}$ The problems must be automatically generated since cryptocurrencies in-general have no central authorities.
5. $\textbf{Solution tied to block and solver:}$ For example, in Bitcoin the information being hashed includes the person solving the problem along with other information. This way someone cannot steal someone else's solution.


The following traits are necessary only if there is one or a couple kinds of proof-of-work problem per cryptocurrency or there is no process to automatically remove broken proof-of-work problems.


i. $\textbf{Endless problems:}$ There must be a limitless amount of problems to solve so that a new problem could generated every few minutes.


ii. $\textbf{Unbreakability:}$ The class of problems should be “unbreakable”. The security of cryptocurrencies depends on the fact that no party should have a secret algorithm that quickly solves the problems and that no body is likely to develop such a secret algorithm in the future.


iii. $\textbf{Progress freeness:}$ Each individual problem must be “progress-free” in the following sense. If Alice works on the problem from noon and Alice has not found a solution by 12:30, then at 12:30 Alice will have no advantage over another participant who begins working on the problem at 12:30. In other words, the amount of time it takes to solve the given problem follows an exponential distribution.


iv. $\textbf{Pre-computation resistance:}$(observed by Loreno Heer in the comments) The proof-of-work problem should be “pre-computation resistant”. One way to obtain this desired property is to make the proof-of-work problem dependent on random data such as current transactions. One could also make future problems depend on previous solutions.


Other comments
--------------


I am slightly more interested in mathematical problems which have or may have future practical applications instead of problems which are only of a purely mathematical interest. In a best case scenario, I would like to see problems which may have cryptographic applications.


This question differs from [this previous question](https://mathoverflow.net/questions/188249/what-problem-would-you-base-your-mathcoin-on) since the previous question did not ask for problems which are specifically suitable as proof-of-work problems for cryptocurrency mining (and the answers given are not suitable as proof-of-work problems for cryptocurrency mining either).



What computational problems would be good proof-of-work problems for cryptocurrency mining?
[Here is a recent paper](https://boolesrings.org/jvanname/2017/07/22/nebula-the-cryptocurrency-that-will-produce-the-reversible-computer/), which has been received positively in the cryptocurrency community. I will expand on this paper here. 


While conventional hash functions do not allow one to construct very useful proof-of-work problems, if one replaces the hash function for the proof-of-work with a randomizing function specifically designed to be computed by reversible circuits, then the proof-of-work problem has practical use besides simply securing the blockchain. This proof-of-work problem will prompt the development of super-efficient reversible computers. Furthermore, these new proof-of-work problems will satisfy all of the requirements that one will want in a proof-of-work problem for cryptocurrencies that I have listed in the question.


**What is reversible computing?**


A bijective gate (such as the NOT, Toffoli, and Fredkin gates) is also called a reversible gate (and by definition every bijective gate must have the same number of input bits as output bits). A circuit is said to be reversible if all of its logic gates are reversible. As combinatorial circuits model ordinary computation, the reversible circuits model reversible computation. Any computation that can be efficiently carried out by an ordinary computer can also be reasonably efficiently computed using a reversible computer. For example, PSPACE=REVSPACE where REVSPACE refers to the problems which can be solved on a reversible computer with a polynomial amount of space.


**Why reversible computing?**


Landauer's principle states that erasing a bit always costs $k\cdot T\cdot\ln(2)$ energy where $k$ is the Boltzmann constant and $T$ is the temperature. Since $k=1.38064852\cdot 10^{-23}\cdot m^{2}\cdot kg\cdot s^{-2}\cdot K^{-1}$, we conclude that at $300 K$, erasing a bit costs $2.8 × 10^{−21}$ joules.


While conventional computing always costs energy since with conventional computing, one always has to erase information, there is most likely no lower limit to the efficiency of reversible computation since reversible computing does not erase any information. Since reversible computers will be more efficient than ordinary computers, reversible computers will not generate as much heat as ordinary computers, so reversible computers will be able to operate at much higher speeds than ordinary computers.


While a reversible computer should in theory be much more efficient than an irreversible computer, there are currently no reversible computers out in the market today which are more efficient than their irreversible counterparts.


If the proof-of-work problems for cryptocurrencies require one to solve problems designed for super efficient reversible computers, then corporations will have a great incentive to produce reversible integrated circuits which can quickly solve these problems without using so much energy.


**A preliminary description of the proof-of-work problem**


We shall now select a proof-of-work problem which should be carried out by a reversible computer just as easily as it is carried out by a classical computer. I therefore want the randomizing function to be computable on a reversible circuit without any ancilla.


For this proof-of-work problem, suppose that $f:\{0,1\}^{324}\rightarrow\{0,1\}^{324}$ is a function computed by a circuit which consists solely of reversible gates and where the circuit does not contain any garbage or ancilla bits.


Suppose that $\mathbf{k}$ is the hash of the block header and $\alpha$ is an adjustable 324 bit number. Then the proof-of-work problem for the current block shall be to find some 68 bit string $\mathbf{x}$ such that $f(\mathbf{k}\#\mathbf{x})\leq\alpha$ where $\#$ denotes the concatenation operation.


