[bitcoin-dev] Properties of an ideal PoW algorithm & implementation
tim.ruffing at mmci.uni-saarland.de
Wed Apr 19 11:08:15 UTC 2017
On Tue, 2017-04-18 at 12:34 +0200, Natanael via bitcoin-dev wrote:
> To prove that an implementation is near optimal, you would show
> there's a minimum number of necessary transistor activations per
> computed hash, and that your implementation is within a reasonable
> range of that number.
I'm not an expert on lower bounds of algorithms but I think proving
such properties is basically out of reach for mankind currently.
> We also need to show that for a practical implementation you can't
> reuse much internal state (easiest way is "whitening" the block
> header, pre-hashing or having a slow hash with an initial whitening
> step of its own). This is to kill any ASICBOOST type optimization.
> Performance should be constant, not linear relative to input size.
Yes, a reasonable thing in practice seems to use a slower hash function
(or just iterating the hash function many times), see also this thread:
PoW verification will still be fast enough. That's not the bottleneck
of block verification anyway.
Also, I don't agree that a PoW function should not rely on memory.
Memory-hard functions are the best we have currently.
More information about the bitcoin-dev