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 majord...@metzdowd.com