[bitcoin-dev] Properties of an ideal PoW algorithm & implementation

[Tim Ruffing]

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:
 https://twitter.com/Ethan_Heilman/status/850015029189644288 .

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.


Tim