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

[tevador]

On Sun, Jun 7, 2020 at 8:42 AM <yoehoduv at protonmail.com> wrote:
>
> One way is to include the target effort in requests, and include both
> the server-provided nonce and the target effort as the x in Hx.  Then
> only check that the real effort comes out no less than the target
> effort, but use the target effort for everything else.
>

That's a very good idea. It would also prevent "lucky" high-effort
solutions (unless the client wants to play the lottery).

With the Equi-X puzzle, it would work like this:

C   ... server challenge (32 bytes)
N   ... client nonce (16 bytes)
E   ... client target effort (4 bytes, little endian)
S   ... Equi-X solution (16 bytes)
R   ... hash result (4 bytes, little endian)
||  ... concatenation operator

The client's algorithm:
Input: C
1) Select N, E
2) Calculate S = equix_solve(C || N || E)
3) Calculate R = blake2b(C || N || E || S)
4) if R * E > UINT32_MAX, go back to step 1)
5) Submit C, N, E, S (68 bytes total)

The server's algorithm:
Input: C, N, E, S
1) Check that C is a valid challenge (there may be multiple challenges
active at a time).
2) Check that E is above the minimum effort
3) Check that N hasn't been used before with C
4) Check equix_verify(C || N || E, S) == EQUIX_OK
5) Calculate R = blake2b(C || N || E || S)
6) Check R * E <= UINT32_MAX
7) Put the request in the queue with weight E

Optionally, C could be omitted from the extension field if there is
only one global challenge. That would reduce the payload size to 36
bytes.

Note: 32-bit effort should be enough for more than a week of solving
with an 8-core CPU.

T.