Bitcoin and Cryptocurrency Technologies

This course contains scientific errors, and the cryptocurrency sector is suffering very much from such sloppy research and a poor understanding of certain aspects of computation which will become increasingly relevant in the future.

In the section, "Energy consumption and ecology", the authors claim that since SHA-256 is a non-reversible computation, Bitcoin mining must consume a minimum amount of energy due to Landauer's limit. This is false.

To give you some background, Landauer's principle states that in order to delete information by replacing that information with a whole bunch of 0's, one must spend at least k*T*ln(2) energy per bit deleted and replaced with a 0; here k=1.38*10^(-23) Joules/Kelvin is Boltzmann's constant, T is the temperature, and ln denotes the natural logarithm (ln(2)=0.69...). Landauer's principle should be thought of as a consequence of the second law of thermodynamics since any violation of Landauer's principle would cause a decrease in entropy. Reversible computing is the type of computing where one does not delete any information or where one deletes as little information as possible. Since reversible computing does not delete any information, reversible computation is not subject to Landauer's limit. While reversible computing is potentially many times more energy efficient than conventional computation, today there are no reversible computers out on the free market.

Today, there is much hype about quantum computation, but people do not seem to understand that reversible computation is much more feasible than quantum computation and that we should expect to see reversible computers outperform irreversible computers long before we get our money's worth from all the quantum computation research (by some estimates, we are quite close to the day when reversible computers start to outperform conventional computers). There are a few reasons we have not seen reversible computation get much attention by much of anyone. In the past the efficiency of conventional computation was so far away from Landauer's limit that Landauer's limit was not relevant. The performance gains in computation were achieved simply by shrinking the size of the components in an integrated circuit. Today, these reasons are no longer relevant since research indicates that reversible computers with energy efficiencies below Landauer's limit are possible http://www.imm.org/Reports/rep046.pdf.

Now, reversible computers (as soon as people start building them) will be capable of doing any computation that can be done by conventional computers. As you might expect, it typically takes more steps to perform a computation reversibly than it does to perform the same computation using a conventional computer. However, through computing and uncomputing using an optimal strategy to Bennett's pebble game, any computation that can be performed with space S and time T can also be performed reversibly using space O(S*log(T/S)) and time O(T*(T/S)^epsilon). This means that the computational overhead incurred from reversibility is quite reasonable. This computational overhead can be further reduced by incorporating a small amount of irreversibility into the computation. Landauer's limit is irrelevant for producing any theoretical limits to the energy consumption for performing any computation.

For Bitcoin mining, one however does not need to use Bennett's pebble game in order to conclude that Bitcoin mining can be done on a reversible computer at an efficiency rate well below Landauer's limit per hash. Two of the main security requirements of cryptographic hash functions are collision resistance and second pre-image resistance, and both of these security requirements are weak versions of reversibility, so cryptographic hash functions by their very nature should be at least partially reversible. If you look at the inner workings of SHA-256, you will find that SHA-256 uses much modular addition (which is a quite reversible operation since there are reversible ripple carry adders that can perform this operation) along with other components which can be constructed with very few reversible gates and which leave behind none of the garbage information that often comes from reversible computation.

Even without regarding anything that I had just said about Bennett's pebble game and SHA-256, one should still conclude that all cryptocurrencies can be effectively mined using a reversible computer simply by uncomputing all of the garbage data after every hash attempt. In case I have not convinced you, here is a general template for a computer program for mining a cryptocurrency in the completely reversible programming language Janus.

The goal of the following POW problem is to find an input i where w=12321 after we perform the assignments

w=i; x=((i+214)^(i+142211))+(w&1231); w-=(x&13321).

procedure proofofwork(int i,int w,int x)

w+=i

x^=((i+214)^(i+142211))+(w&1231)

w-=(x&13321)

procedure main()

int i

int w

int x

call proofofwork(i,w,x)

from i=0 do

uncall proofofwork(i,w,x)

i+=1

call proofofwork(i,w,x)

until (w=12321)

uncall proofofwork(i,w,x)

The output of this program for solving a POW problem (and this output includes all possible garbage information) is

i = 20513

w = 0

x = 0

and i=20513 is a solution to this POW problem.

While this scientific error may seem as a minor issue, for heat production and energy use issues, we should all expect for nearly reversible computers to replace the conventional computers that we have today. Furthermore, cryptocurrency mining problems can be used to stimulate the initial development of the energy efficient reversible computer. Unfortunately, the cryptocurrency community does not seem to care that their mining efforts have only wasted resources and polluted our planet without producing any technology or scientific advancement to show for it.

-Joseph Van Name Ph.D.