Hi teor,
On Sun, May 10, 2020 at 6:36 AM teor teor@riseup.net wrote:
There are two possible issues with this design:
Division is expensive on some platforms, including ARM-based devices. But there might be a way to calculate an approximate value without division. (For example, bit shifts, or multiplying by an inverse.) Or we could calculate the maximum value once, and then re-use it.
Is it still possible to express the full range of difficulties? Is that expression reasonably compact?
Some advantages of this exponential distribution are:
- spurious results can be filtered using a single instruction (a bit mask),
- the expected effort is quick and easy to calculate,
- the effort can be expressed in a compact way.
Maybe we don't need some of these properties, and a linear design would be fine.
But if we do, we could change the exponent to the square or cube root of two. There would be a smoother distribution, but a wider range, and the checks would still be reasonably fast.
T
You only need 1 or 2 divisions per introduction request, so it doesn't matter even if division is expensive, because it will take a minuscule amount of time compared to the actual hashing effort.
There are 2 scenarios:
1) User wants to wait for X seconds and then submit the best result they could find.
2) User wants to wait as long as it takes to submit a result with an effort of at least E.
In case 1), the client will simply take the smallest result R found during the X seconds and calculate ACTUAL_EFFORT = MAX_RESULT / R at the end.
In case 2), the client will calculate TARGET = MAX_RESULT / E at the beginning and keep hashing until they find a result R <= TARGET. Then they can calculate ACTUAL_EFFORT = MAX_RESULT / R at the end, which implies ACTUAL_EFFORT >= E.
Case 1) takes 1 division instruction, case 2) takes 2 division instructions. When hashing, the client can filter results with a single instruction (comparison).
Examples:
1) After X seconds, the client finds results 660445, 6317, 599102 ... 111847. The smallest result is 6317, so:
ACTUAL_EFFORT = 1048575 / 6317 = 165
2) The client wants to find a result with an effort of at least E = 165, so they calculate TARGET = 1048575 / 165 = 6355. Then they can keep hashing until they find R <= 6355, e.g. 6317. The actual effort is calculated as above.
So the only advantage of the exponential notation is:
- the effort can be expressed in a compact way.
This can save a few characters in the HS descriptor, at the cost of a coarse effort classification, e.g. clients who spent 60 seconds hashing will be, on average, classified the same as those who spent 100 seconds.