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 _______________________________________________ bitcoin-dev mailing list [email protected] https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
