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


From hal at finney.org Tue Jan 27 14:35:43 2009
From: hal at finney.org (Hal Finney)
Date: Tue, 27 Jan 2009 11:35:43 -0800 (PST)
Subject: Proof of Work -> atmospheric carbon
Message-ID: <20090127193543.67F9314F6E1@finney.org>

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.