Proof of Work -> atmospheric carbon

[Hal Finney]

John Gilmore writes:
> The last thing we need is to deploy a system designed to burn all
> available cycles, consuming electricity and generating carbon dioxide,
> all over the Internet, in order to produce small amounts of bitbux to
> get emails or spams through.

It's interesting to consider the ultimate technological resolution to this
issue. Will a global-scale proof-of-work based system inherently consume
substantial amounts of energy? Or are there ways of doing computing
which would allow such a system to use only moderate energy consumption?

This question relates to the thermodynamics of computation. It has
long been known that logically reversible transformations can be done
with arbitrarily low energy dissipation. Hence attention is focused on
irreversible transformations, particularly those that require bit erasure.
Erasing a bit dissipates approximately energy of approximately kT where
k is Boltzmann's constant and T is temperature.

The question is whether a POW system inherently involves a great deal
of irreversible logical transitions, causing bit erasure and dissipating
energy? Or could a POW token be created using solely reversible logic?

One note is that any algorithm can in principle be made reversible except
for the size of the output: compute it using reversible logic, possibly
creating many excess bits which will allow the reversal, until we get
the answer; then make a copy of the output; then reverse the calculation,
consuming all the excess bits until we get back to the original value. The
only irreversible step was saving the output. However this is impractical
for large calculations like we are talking about, because the number of
excess bits would dwarf the size of the calculation.

The hash collisions used in systems like Bitcoin or Hashcash (technically
not collisions, rather searches for pre-images of hash values with many
leading zero bits) seem inherently irreversible. The algorithm typically
sets up a pre-image that includes a counter value, computes the hash,
increments the counter and repeats until a hash is found with the desired
properties. The hash function itself typically uses many intrinsically
irreversible transitions, since logical irreversibility is a defining
requirement of a hash function. Even if we use the trick in the preceding
paragraph to eliminate the cost of the intermediate steps in computing
the hash, we would still need to erase the output result each iteration,
dissipating energy. Typical POW systems in use today require millions
to billions of iterations, and this would be likely to increase in the
future, so the dissipation could be substantial.

Replacing the hash with a logically invertible function might help to
reduce the number of intermediate bits, and eliminate the need to use
the run-backwards trick. One would require that both the pre-image and
the post-image contain a number of bits in fixed positions. However this
would still seem to require the same kind of search algorithm, causing
dissipation as each intermediate result is erased.

Perhaps a variation on this idea would work, if the logically invertible
function was itself very slow, perhaps paramaterized to have a huge number
of rounds. Then only a relatively small number of iterations would be
needed before a lucky result is found, for a given level of POW effort.
This would reduce dissipation. However it would slow down verification,
and since verification of the POW will be done far more often than
creation, we can't afford to tip things too far in that direction.

Another idea I had was to use a deterministic POW rather than a random
one like hash collision. Cryptographic work on "timed commitments" and
related topics has shown that repeated squarings modulo an unknown RSA
modulus allow for a relatively concise and quickly verifiable proofs that
some very large number of squarings had taken place, with no shortcuts
possible for the creation of the resulting certification. Broadly
speaking, modular squaring is logically reversible, in that one could
theoretically compute the square root. But in practice, as with the
hash computation, computing a modular square using logically reversible
operations will produce a large number of excess bits. Even if the excess
from a single squaring could be consumed using the trick mentioned
above, one would still be forced to erase the temporarily result of
each individual squaring operation, as the POW would require a very
large number of squarings.  So the overall dissipation would appear to
be similar to the hash computation.

(Also, it's not clear that a deterministic POW works well for an
application like Bitcoin; it might let the owner of the fastest computer
win every POW race, giving him too much power.)

So the question from John's challenge remains open: is there a POW
system which could be built solely on logically reversible computation?
The computation has to be intrinsically time consuming, but with a short
and quickly verifiable certificate of validity.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com