Quote from: Peter R on April 20, 2015, 04:33:26 PM

Quote from: Meni Rosenfeld on April 19, 2015, 11:27:52 AM

You should read up on https://en.wikipedia.org/wiki/Reversible_computing. You can in theory construct your logic gates in a way that will not erase information, and make arbitrarily long computations with a bounded energy expenditure. The notion that the Landauer's principle places a lower limit on the energy cost of computation is a myth.

Interesting. Let's imagine that we made a circuit to test nonces for bitcoin mining using reversible gates.

Code:

______________
   -| |-
   -| |-
i -| |- o
n -| |- u
p -| circuit |- t
u -| |- p
t -| |- u
   -| |- t
   -| |-
   --------------

Assume that the input to the circuit is the blockheader which consists of 608 bits + the 32-bit nonce. So we need 640 wires (bits) coming into our circuit at the input side.

At the output, all we really care about is a yea or nay on whether the nonce satisfies the difficulty target, which could be represented by a single bit. But that's not reversible because from one bit we can't go backwards and reproduce the 640-bit input. To make the computation reversible, our circuit must also have at least 640 bits coming out of it.

To use the circuit in practice, we apply our first nonce to the input, wait for the output to settle, and determine if the difficulty target was satisfied. The answer is probably NO...

So, now comes the irreversible part. We need test another nonce, which means we must flip at least one bit in our input (the input includes the nonce). So, as per Landauer's principle, this costs us energy¹

E > kT ln 2.

We have to do this many, many times until we find a nonce that satisfies the difficult target, expending energy at each step.

Another interesting property of our reversible circuit above is that it only performs the computation for infinitesimal energy input if we're willing to wait an infinitely long time to observe the output. In general, even for reversible gates, there is an energy-time tradeoff² for performing a specific computation:

(energy consumed)*(computation time) > some constant

A successful Bitcoin miner is concerned with more than finding the correct nonce with the least energy expenditure. He also wants to find it quickly! And this will always cost him energy, regardless of whether he use reversible or irreversible gates.

¹If this causes M bits to get flipped at the output, does this then mean the circuit required an energy input E > M kT ln 2 to test the next nonce? I'm not sure...

²Discovered by Charles Bennet (working at IBM with Rolf Landauer), refer to Feynman Lectures on Computation, Chapter 5.

There is no need to output lots of nonce values for unsuccessful searches. For example, one could build a reversible engine that would fully search a defined range and output a single bit that indicates whether the range contains a solution. This information could be used in a binary search to zero in on an exact solution. Alternatively, the identity of promising ranges could be passed on to a conventional hash engine which would search only guaranteed successful ranges.

Engineering details await detailed cost/performance specs for the "unobtanium" reversible devices.