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

[tevador]

Hi Mike,

My apologies. I thought this later email from 14th April had the
latest version of the proposal:
https://lists.torproject.org/pipermail/tor-dev/2020-April/014225.html

> In short, we let the queue grow at a faster rate than we serve, and we
> trim it occasionally.

What is the benefit of this approach rather than discarding low
priority requests right away in the top-half handler?

Note that a priority queue is typically implemented as a heap, which
does not support efficient trimming.

> However, it still has the following potential issues:
>  A) AES will bottleneck us at ~100Mbit-300Mbit at #2 in top-half above
>  B) Extra mainloop() iterations for INTRO2s may be expensive (or not?)

I don't think AES is the main concern here. Each introduction request
is 512 bytes (AFAIK), so with a PoW verification performance of 2000
requests per second, the top-half handler will bottleneck at ~1 MB/s.

> Are there other reasons to do stochastic sampling over a priority queue,
> given this top-half and bottom-half design?

After thinking about it more, I would recommend starting with a simple
priority queue as proposed. More complex solutions can be implemented
later if field testing finds issues.

T.