📅 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
Tim Ruffing [ARCHIVE] /
npub1cm…dwkls
2023-06-07 20:00:30
in reply to nevent1q…629z
Author Public Key
npub1cmt6gqyfw3sdngkq0wadtpe3kmgyyeld6ad0g2h5tar3kpzcrmpqddwklsPublished at
2023-06-07 20:00:30Event JSON
{
"id": "108c3ab8132c3caa75b2d3df7170fab69bd968b4e05dc093a14183cc9d2e6eec",
"pubkey": "c6d7a400897460d9a2c07bbad58731b6d04267edd75af42af45f471b04581ec2",
"created_at": 1686160830,
"kind": 1,
"tags": [
[
"e",
"ea46271e9d88e0388863236306d6d46086b86332e1d16ae1de36104566b2ecfe",
"",
"root"
],
[
"e",
"2a83281e9b67cbae41ec0ededfe1e85b145765937c9c79aac3eeef2e22ee43d3",
"",
"reply"
],
[
"p",
"b8acca17a6f74c77cd8a4899846d99012d1b52082a01a2d2753fcb0c6669a60b"
]
],
"content": "📅 Original date posted:2017-04-19\n📝 Original message:On Tue, 2017-04-18 at 12:34 +0200, Natanael via bitcoin-dev wrote:\n\u003e To prove that an implementation is near optimal, you would show\n\u003e there's a minimum number of necessary transistor activations per\n\u003e computed hash, and that your implementation is within a reasonable\n\u003e range of that number. \n\nI'm not an expert on lower bounds of algorithms but I think proving\nsuch properties is basically out of reach for mankind currently.\n\n\u003e \n\u003e We also need to show that for a practical implementation you can't\n\u003e reuse much internal state (easiest way is \"whitening\" the block\n\u003e header, pre-hashing or having a slow hash with an initial whitening\n\u003e step of its own). This is to kill any ASICBOOST type optimization.\n\u003e Performance should be constant, not linear relative to input size. \n\nYes, a reasonable thing in practice seems to use a slower hash function\n(or just iterating the hash function many times), see also this thread:\n https://twitter.com/Ethan_Heilman/status/850015029189644288 .\n\nPoW verification will still be fast enough. That's not the bottleneck\nof block verification anyway.\n\nAlso, I don't agree that a PoW function should not rely on memory.\nMemory-hard functions are the best we have currently.\n\n\nTim",
"sig": "c310d6876f03b2b2815eca1080581f695da844d98c0c4861474e344a6d39c5a29fa54f18eb2a7442db7461d84bbc6f3b664a0db68c848a74f2f85741f03707f9"
}