Satoshi should have designed Bitcoin mining for reversible computation

[jvanname]

In an ideal world, Bitcoin should have used a mining algorithm that is designed to accelerate the development of reversible computing technologies from the day it was originally launched.

Landauer's principle states that every irreversible erasure of a bit of information costs more than k*T*ln(2) energy where k=1.38*10^(-23) Joules/Kelvin, T is the temperature, and ln(2)=0.69314... For example, it takes more than 2^33*k*T*ln(2) energy to replace a gigabyte of random bits with zeros. k*T*ln(2) is not a lot of energy, but we run into problems with irreversible computation well above k*T*ln(2) energy. Regardless of one's computing technology, one should expect to spend at least 100*k*T energy per irreversible operation even if we use ideal irreversible hardware. In the real world, our hardware is not ideal, so one will have problems with irreversible computation when the energy efficiency is many thousands of times k*T. It is therefore time for people to start looking into reversible computation since the efficiency gains of irreversible computation will stagnate unless we start using reversible computing.

I do not see any evidence that suggests that it is impossible or infeasible to make energy efficient reversible computers, but it will probably be difficult. One reason why reversible computing will be difficult is that reversible computation has a computational complexity theoretic overhead. Fortunately, the computational complexity overhead for reversible computation is surprisingly small. The 1989 paper Time/Space tradeoffs for reversible computation by Charles Bennett indicates that any irreversible computation taking time T and space S will take time O(T*(T/S)^epsilon) and space O(S*(1+ln(T/S))) (well, actually these formulas are from a 1990 note by Robert Y. Levine and Alan T. Sherman on the paper). One can get better time/space bounds by trading time and space with partial reversibility and parallel computation. Since the time/space overheads are quite reasonable, one should expect for reversible computation to eventually replace all irreversible computation, but since the computational complexity overheads are something, it will be difficult for anyone to manufacture profitable physically reversible computers.

Bitcoin uses SHA-256 mining. SHA-256 is an example of a cryptographic hash function, and cryptographic hash functions are well-suited as cryptocurrency mining algorithms except for how computing the cryptographic hash function is not mean to solve any scientific problem. Since cryptocurrency mining algorithms must satisfy quite stringent conditions, it is very difficult to make a cryptocurrency mining algorithm that both works well at establishing decentralized consensus but which also solves an important scientific problem. Fortunately, the problem of developing reversible computing hardware is an important scientific problem that is can be made to satisfy all the cryptographic properties that cryptographic hash functions satisfy. To do this, one should use a reversible mining algorithm that is designed to run on reversible hardware.

I am talking about how things should have been, but even in a parallel universe, I doubt that this would have been feasible for Satoshi to do for several reasons. First of all, in order to use cryptocurrency mining to accelerate the development of reversible computing technologies, Satoshi would have needed the foresight to predict how big Bitcoin would be, and Satoshi would have also needed the understanding of the importance of reversible computation in future computing hardware. Satoshi would have also needed access to the expertise to design a mining algorithm to optimally accelerate the development of reversible computing technologies, and it would have taken a significant amount of time to design a mining algorithm for reversible computation.

To design a mining algorithm for reversible computation, one must balance cryptographic security with the efficiency at which the mining algorithm helps solve the problem of reversible computation. This means that Satoshi should have had experts both in the cryptography and in reversible hardware. Furthermore, since reversible mining algorithms satisfy different security properties than your traditional block ciphers, hash functions, and cryptographically secure pseudorandom number generators, mathematicians should have ideally done the mathematical research on these block ciphers and other cryptosystems before Satoshi came along. Then Satoshi needed to apply this mathematical and cryptographic research to developing a secure mining algorithm for cryptocurrency technologies. This mathematical research includes much AI, so before 2008, it would have been harder do to this research, but maybe Satoshi could have taken a different route towards this research that does not involve AI.

Now that Bitcoin has been out for so long, it is not feasible for Bitcoin to have a mining algorithm that is designed to advance science by solving the problem of reversible computation.