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.