I have some amazing news. The total market cap for all cryptocurrencies has for the first time has reached 100 billion dollars. On April 24,2017 the total market map for all cryptocurrencies has hit 30 billion for the first time and it has been growing ever since. At the same time, while Bitcoin has in the past been the only major cryptocurrency, Bitcoin no longer is the only major cryptocurrency since Bitcoin currently amounts for about 45 percent of the total market cap for all cryptocurrencies (on March 1,2017 Bitcoin amounted to about 85 percent of the total market cap for all cryptocurrencies).
I believe that unless most of the world’s governments wage a cyber war against cryptocurrencies, in the somewhat near future cryptocurrencies will for the most part replace fiat currencies or at least compete with government fiat currencies. Governments today have an incentive to produce more fiat currencies since governments are able to fund their programs by printing more of their own money (producing more money is a bit more subtle than simply taxing people). However, there is no motivation for anyone to exponentially inflate any particular cryptocurrency (I would never own any cryptocurrency which will continue to exponentially inflates its value). For example, there will never be any more than 21 million bitcoins. Since cryptocurrencies will not lose their value through an exponential inflation, people will gain more confidence in cryptocurrencies than they would with their fiat currencies. Furthermore, cryptocurrencies also have the advantage that they are not connected to any one government and are supposed to be decentralized.
Hopefully the world will transition from fiat currencies to digital currencies smoothly though. Cryptocurrencies are still very new and quite experimental, but cryptocurrencies have the potential to disrupt the global economy. There are currently many problems and questions about cryptocurrencies which people need to solve. One of the main issues with cryptocurrencies is that the proofofwork problem for cryptocurrencies costs a lot of energy and resources and these proofofwork problems produce nothing of value other than securing the cryptocurrency. If instead the proofofwork problems for cryptocurrencies produce something of value other than security, the public image of cryptocurrencies will be improved, and as a consequence, governments and other organizations will be less willing to attack or hinder cryptocurrencies. In this post, I will give another attempt of producing useful proofofwork problems for cryptocurrencies.
In my previous post on cryptocurrencies, I suggested that one could achieve both security and also obtain useful proofsofwork by employing many different kinds of problems into the proofofwork scheme instead of a single kind of problem into such a scheme. However, while I think such a proposal is possible, it will be difficult for the cryptocurrency community to accept and implement such a proposal for a couple of reasons. First of all, in order for my proposal to work, one needs to find many different kinds of proofofwork problems which are suitable for securing cryptocurrency blockchains (this is not an easy task). Second of all, even if all the proofofwork problems are selected, the implementation of the proposal will be quite complex since one will have to produce protocols to remove broken problems along with a system that can work together with all the different kinds of problems. Let me therefore propose a type of proofofwork problem which satisfies all of the nice properties that hashbased proofofwork problems satisfy but which will spur the development of reversible computers.
I am seriously considering creating a cryptocurrency whose proofofwork problem will spur the development of reversible computers, and this post should be considered a preliminary outline of how such a proofofwork currency would work. The next time I post about reversible computers spurred by cryptocurrencies, I will likely announce my new cryptocurrency, a whitepaper, and other pertinent information.
What are reversible computers?
Reversible computers are theoretical superefficient classical computers which use very little energy because they can in some sense recycle the energy used in the computation. As analogies, an electric motor can recover the kinetic energy used to power a vehicle using regenerative braking by running the electric motor in reverse, and when people recycle aluminum cans the aluminum is used to make new cans. In a similar manner, a reversible computer can theoretically in a sense regenerate the energy used in a computation by running the computation in reverse.
A reversible computer is a computer whose logic gates are all bijective and hence have the same number of input bits as output bits. For example, the AND and OR gates are irreversible gates since the Boolean operations AND and OR are not bijective. The NOT gate is a reversible gate since the NOT function is bijective. The Toffoli gate and Fredkin gates are the functions $T$ and $F$ respectively defined by
$$T:\{0,1\}^{3}\rightarrow\{0,1\}^{3},T(x,y,z)=(x,y,(x\wedge y)\oplus z)$$
and
$$F:\{0,1\}^{3}\rightarrow\{0,1\}^{3},F(0,y,z)=(0,y,z),F(1,y,z)=(1,z,y).$$
The Toffoli gate and the Fredkin gate are both universal reversible gates in the sense that Toffoli gates alone can simulate any circuit and Fredkin gates can also simulate any circuit.
While reversible computation is a special case of irreversible computation, all forms of classical computation can be somewhat efficiently simulated by reversible circuits. Furthermore, when reversible computers are finally constructed, one should be able to employ a mix of reversibility and irreversibility to optimize efficiency in a partially reversible circuit.
Reversible computation is an improvement over classical computation since reversible computation is potentially many times more efficient than classical computation. Landauer’s principle states that erasing a bit always costs $k\cdot T\cdot\ln(2)$ energy where $T$ is the temperature and $k$ is the Boltzmann constant. Here the Boltzmann constant is $1.38064852\cdot 10^{−23}$ joules per Kelvin. At the room temperature of 300 K, Landauer’s principle requires $2.8\cdot 10^{−21}$ joules for every bit erased. The efficiency of irreversible computation is limited by Landauer’s principle since irreversible computation requires one to erase many bits. On the other hand, there is no limit to the efficiency of reversible computation since reversible computation does not require anyone to erase any bit of information. Since reversible computers are potentially more efficient than classical computers, reversible computers do not generate as much heat and hence reversible computers can potentially run at much faster speeds than ordinary classical computers.
While the hardware for reversible computation has not been developed, we currently have software that could run on these reversible computers. For example, the programming language Janus is a reversible programming language. One can therefore produce, test, and run much reversible software even though the superefficient reversible computers currently do not exist.
The proofofwork problem
Let me now give a description of the proofofwork problem. Suppose that
 $a_{i,j},b_{i,j},c_{i,j}\in\{0,1\}$ are randomly generated whenever $1\leq i\leq 128,1\leq j\leq 85$,

$T_{i,j}:\{0,1\}^{3}\rightarrow\{0,1\}$ is the mapping defined by
$$T_{i,j}(x,y,z)=((a_{i,j}\oplus x)\wedge(b_{i,j}\oplus y))\oplus c_{i,j}\oplus z,$$  $a_{i}\in\{1,\ldots,256\}$ for $i\in\{1,\ldots,128\},$
 $((a_{i,1,1},a_{i,1,2},a_{i,1,3}),…,(a_{i,85,1},a_{i,85,2},a_{i,85,3}))$ is a randomly generated partition of $\{1,\ldots,256\}\setminus\{a_{i}\}$ for $1\leq i\leq 128$,

For $i\in\{1,…,128\},j\in\{1,…,85\}$, $f_{i,j}:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where
$f_{i,j}((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ if and only if $x_{n}=y_{n}$ whenever $n\neq a_{i,j,3}$ and
$$y_{a_{i,j,3}}=T_{i,j}(x_{a_{i,j,1}},x_{a_{i,j,2}},x_{a_{i,j,3}}),$$  $$f_{i}=f_{i,1}\circ…\circ f_{i,85},$$
 $\sigma:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where $\sigma((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ precisely when $x_{n}=y_{n}$ for $n>128$ and $y_{n}=x_{n}+x_{n+128}$ whenever $n\leq 128$,
 $\mu:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where $\mu((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ precisely when $x_{n}=y_{n}$ for $n>128$ and $y_{n}=x_{n}+x_{257n}$ whenever $n\leq 128$,

$\tau:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where $\tau((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ precisely when
$x_{n}=y_{n}$ for $n>64$ and $y_{n}=x_{n}+x_{n+64}$ whenever $n\leq 64$,  $$f=\tau\circ\sigma\circ f_{128}\circ…\circ f_{1}\circ \sigma\circ\mu.$$
The function $f$ can be computed by a reversible circuit which we shall denote by $C$ with 132 different layers. The 128 layers in the circuit $C$ which are used to compute the functions $f_{1},…,f_{128}$ shall be called rounds. The circuit $C$ consists of 10880 Toffolilike gates along with 576 CNOT gates (The circuit $C$ has a total of 11456 gates).
Since the randomizing function $f$ is randomly generated, one will be able to replace the function $f$ with a new randomly generated function $f$ periodically if one wants to.
Let $\alpha$ be an adjustable 256 bit number. Let $k$ be a 128 bit hash of the current block in the blockchain. Then the proofofwork problem is to find a 128 bit nonce $\mathbf{x}$ such that $f(k\#\mathbf{x})\leq\alpha$. The number $\alpha$ will be periodically adjusted so that the expected value of the amount of time it takes to obtain a new block in the blockchain remains constant.
Efficiency considerations
It is very easy to check whether a solution to our proofofwork problem is correct or not but it is difficult to obtain a correct solution to our proofofwork problem. Furthermore, the randomizing function $f$ in our proofofwork problem can be just as easily computed on a reversible computer as it can on an irreversible computer. If reversible gates are only slightly more efficient than irreversible gates, then using a reversible computer to solve a proofofwork problem will only be profitable if the randomizing function is specifically designed to be computed by a reversible circuit with no ancilla, no garbage bits, and which cannot be computed any faster by using an irreversible circuit instead. Standard cryptographic hash functions are not built to be run on reversible computers since they require one to either uncompute or to stockpile garbage bits that you will have to erase anyways.
Security considerations
The security of the randomizing permutation $f$ described above has not yet been thoroughly analyzed. I do not know of any established cryptographic randomizing permutation $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ that is written simply as a composition of reversible gates. I therefore had to construct a cryptographic randomizing permutation specifically as a proofofwork problem for cryptocurrencies.
There are several reasons why I have chosen to use mostly randomness to construct the function $f$ instead of intentionally designing each gate of the function $f$. The circuit $C$ has depth 132 which is quite low. Perhaps I can slightly increase the security or the efficiency of the proofofwork problem by designing each particular gate without any randomness but I do not believe that I can increase the security or efficiency by much. If the function $f$ is constructed once using random or pseudorandom information, then one can set up a system to automatically replace the function $f$ with a new function generated in the same manner (periodically changing the function). A randomly constructed function $f$ may even provide better security than a function $f$ constructed without randomness because it seems like since the function $f$ is constructed randomly, the function $f$ would be difficult to analyze. Another reason why I chose a randomly constructed circuit is that a randomly constructed circuit $f$ has a much simpler design than a function such as the SHA256 hash.
In the worst case that the randomizing function is suspected to be insecure, one would have to increase the number of rounds in the randomizing function $f$ from 128 to a larger number such as 192 or 256 so that the randomizing function $f$ would become secure (it is better if 128 rounds is suspected to be insecure before the cryptocurrency is launched since if we need to increase the number of rounds from 128 to 192, then that would require a hard fork which will annoy users and miners and devalue such a currency).
The security requirement for the randomizing permutation $f$ as a proofofwork problem is weaker than the security problem for a randomizing permutation when used to construct a cryptographic hash function or a symmetric encryptiondecryption system. For a cryptographic hash function or a symmetric encryption or decryption to remain secure when used for cryptographic purposes, such a function must remain secure until the end of time, so an adversary may potentially use an unlimited amount of resources in order to attack an individual instance of a cryptographic hash function or symmetric encryption/decryption system. Furthermore, in the case of symmetric cryptography, an adversary will have access to a large quantity of data encrypted with a particular key. However, the current blockchain data $k$ changes every few seconds, so it will be quite difficult to break the proofofwork problem.
Reversible computers are halfway inbetween classical computers and quantum computers
I believe that the large scale quantum computer will by far be the greatest technological advancement that has ever or will ever happen. When people invent the large scale quantum computer, I will have to say “we have made it.” Perhaps the greatest motivation for constructing reversible computers is that reversible computers will facilitate the construction of large scale quantum computers. There are many similarities between quantum computers and reversible computers. The unitary operations that make up the quantum logic gates are reversible operations, and a large portion of all quantum algorithms consists of just reversible computation. Both quantum computation and reversible computation must be adiabatic (no heat goes in or out) and isentropic (entropy remains constant). However, quantum computers are more complex and more difficult to construct than reversible computers since the quantum gates are unitary operators and the quantum states inside quantum computers must remain in a globally coherent superposition. Since quantum computers are more difficult to construct than reversible computers, a more modest goal would be to construct reversible computers instead of quantum computers. Therefore, since reversible computers will be easier to construct than large scale quantum computers, we should now focus on constructing reversible computers rather than large scale quantum computers. The technology and knowledge used to construct super efficient reversible computers will then likely be used to construct quantum computers.
An antiscientific attitude among the mathematics community
I have seen much unwarranted skepticism against Landauer’s principle and the possibility that reversible computation can be more efficient than classical irreversible computation could ever be. The only thing I have to say to you is that you are wrong, you are a science denier, you are a troll, and you are just like the old Catholic church who has persecuted Galileo.
Now, as of 6/10/2017, the total market cap for all cryptocurrencies is 110 billion USD.
If you look at the news, recently all graphics cards have been sold out everywhere because people are buying these graphics cards to mine Ethereum. Imagine if this sort of effort were concentrated into producing reversible computers which are more efficient than conventional computers. Cryptocurrencies need to switch to reversible circuit friendly POW problems so that someone will finally make the reversible computer.