[messaging] Recognizing senders of metadata-hidden messages

[Brian Warner]

On 7/28/15 12:11 PM, Trevor Perrin wrote:

> For comparison, the Pond delivery-token scheme was sketched here:

Ah, thanks, I'd forgotten about that thread. Good analysis there.

> In your scheme the client gives the server a whitelist of tokens. The
> Pond scheme has less recipient<->mailbox communication, but at the
> cost of a growing blacklist.

Right, I like the blacklist, but we must either 1: accept an
unboundedly-growing server storage requirement (to remember the used
tokens), or 2: impose a hard limit on the number of messages that can be
sent through the mailbox (with a storage requirement proportional to
that limit, via jbonneau's numbered-keys bitmap scheme). I guess I
prefer the latter.. I suppose the key numbers should be allocated by
feeding a counter into a PRP? So the mailbox server can't glean
information from their values (consequtive numbers were probably given
to the same sender), but the recipient can remember which have yet to be
allocated with a single counter value.

It's a shame we can't use the common "timestamp+nonce" trick to reject
replays with bounded storage space, since the tokens may be quite old by
the time they're used (issuance-time and use-time should be unlinkable).

One thing that might help.. in Petmail, I'm trying to make it very easy
to transition to new a mailbox, to encourage a competitive ecosystem of
service providers (costs too much? too slow? switch to a better one!).
Agents notify each other about additions/removals to their current set
of mailboxes, and messages can be sent to any server in that set. To
switch from mailbox provider A to B, you first tell all your
correspondents you're using A+B, wait for acks, then publish just B.

We could use this mechanism to switch between queues within a single
mailbox server, which would effectively establish an epoch for the
delivery tokens. Then we could use jbonneau's numbered tokens, with
perhaps a million message-per-epoch limit (so something like 128kB for
the bitmap). When we're down to 10% of the space left, allocate a new
mailbox on the same server, update the senders, then retire the old one
(along with all tokens that were tied to it).

Really this is an option 3: bounded space, unlimited messages, but
intolerant of long silences. I suppose there will always be senders who
stay offline long enough that they don't get the updates. Maybe we
retain the old mailbox for as long as there are contacts using it: if
they're offline, they won't be sending messages anyways, so the
remaining space in the bitmap won't be consumed very quickly.

I imagine we have a design-space split here: "mostly online" systems
(which depend upon frequent interaction), vs "mostly offline" systems
that can tolerate arbitrary periods of inactivity.

cheers,
 -Brian