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
https://www.metzdowd.com/pipermail/cryptography/2009-January.txt