Re: Batching Strategy and Network Structure

[Roger Dingledine <arma@mit.edu>]

On Tue, May 07, 2002 at 05:54:11AM +0000, David Hopwood wrote:
> Roger Dingledine wrote:
> > It would be a nice thing to investigate once we've
> > got Mixminion going -- so then we can start trying out new things like
> > reputation systems and alternate network topologies.
> 
> If that's what we're going to do, then we should try to make the protocol
> quite general, e.g. by implementing source-timing and several possible
> ways of doing replies, decided by the hop header (which is always
> non-malleable). Then we can experiment with different batching techniques
> just by changing clients, not nodes or the protocol itself. As long as
> the options that are actually used are constrained, the only difference
> this makes is that the attacker can introduce messages that don't follow
> the preferred batching technique. This probably doesn't make much
> difference: at least for interval batching, adding messages should never
> reduce the anonymity sets of the other messages.
> 
> Later we could simplify the protocol depending on the batching approach
> we decide to use, in case the extra generality could enable any attacks.

This is an important decision we need to look at.

I feel confident that a synchronous mix-net is going to provide better
anonymity than its asynchronous counterpart, *if we do it right*. But
it also seems that it's harder to do it right.

David: can you point us at papers in The Literature that use synchronous
mix-net designs? The mix-acc paper assumes it. What about others? I want
to get a feel for how well-peer-reviewed the concept itself is.

As an example, it seems hard to get time synchronization right. If the
batch time is several minutes, then the hop time is less than a minute.
How plausible is it to get every node in the network synchronized to
several-second precision? An adversary could convince a server that
it's a different time, causing it to reject valid messages; are more
insidious attacks possible?

We could choose a larger batch time, eg an hour, so hop times are
5-10 minutes. Synchronizing all the nodes in the network to within a
minute may be more practical. We would be losing those users who need
faster delivery --- but perhaps we don't want them anyway? We can't
be everything for everybody; those people should go find a low-latency
connection-oriented service.

But more generally, do we want to try to fold this stuff into what we
plan to build, or leave it out until later? We've got a couple of options:

a) Put off spec and coding until we have a design we're happy with. I
think this is a bad idea, because it'll be another year until we're
happy with a radical change like this.

b) Ignore all of this new-fangled stuff and just build the asynchronous
network we started with. This may also be a poor choice, because we'll
be unhappy with the anonymity it provides, so we'll always be looking
toward the 'second system'.

c) Open up the protocol as described above. Have the protocol be quite
flexible, and have "suggested user behavior" be a subset of the protocol.
We can then revise suggested behavior as we gain more intuition and
solve more problems.

d) Others?

I intend to continue discussion of the synchronous approach, because I
feel it's the better answer long-term. But I'm not the only one in on
this, and I'm not currently one of those who'll be building it short-term.

Nick: How much more likely are we to stagnate if we choose c) rather
than b)?

George: What's your impression of the anonymity differences?

Len/Nick: is most of the actual hard-to-get-done work going to be in
the client and not the server, so having a more flexible protocol really
doesn't affect the difficulty of changing user behavior?

Others: What's your take on this? How do you want to procede? (Your
answer gets more weight if you do some of the work :)

Thanks,
--Roger