Tim Ruffing [ARCHIVE] on Nostr: 📅 Original date posted:2017-04-19 📝 Original message:On Tue, 2017-04-18 at ...
📅 Original date posted:2017-04-19
📝 Original message: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
📝 Original message: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