Hi teor, On Sun, May 10, 2020 at 6:36 AM teor <t...@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. _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev