[tor-dev] [RFC] Proposal: A First Take at PoW Over Introduction Circuits

[tevador]

Hi teor,

On Sun, May 10, 2020 at 6:36 AM teor <teor at 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.