Re: Batching Strategy and Network Structure

[Roger Dingledine <arma@mit.edu>]

I want to make sure I have something straight, below.

On Tue, May 07, 2002 at 05:54:11AM +0000, David Hopwood wrote:
> OK. Here's a summary of the attacks from Section 4 of [disad-free-routes]:
> 
> =====
> # Section 4.2
> # Position in MIX route. Based on our attacker model, each user should be
> # anonymous, even if his messages only pass one trustworthy MIX. In a MIX
> # network a certain MIX may be on different positions on the individual
> # routes of the messages he receives. In comparison a MIX of a cascade
> # will always have the same position because the route is static as long
> # as the cascade exists. The question is: is a MIX of a MIX network able
> # to detect his position in a route of a certain message
> 
> Yes, but this is not a problem in itself.
> 
> # and if so, can he use this knowledge to partition the input batch?
> 
> No.
> The following statement is still true:
> 
> # Eventually, a message is only unobservable in that group of messages
> # which have this MIX on the same routing position.
> 
> but in the synchronous design, that's not a problem because this group
> is large (if only one MIX is trustworthy, 1/w of all messages in the
> batch, which is what it would be anyway).
[snip] 
> > >Define the {\em width}, $w$ of a MIX network using synchronous batching to
> > >be the number of nodes that simultaneously process messages in each
> > >hop period. (If this is not constant, we can still talk about the
> > >maximum, minimum and mean width.)
[snip]
> > >Let $T_{batch}$ be the expected throughput in a single batch period,
> > >i.e. the number of messages that go through the network in a batch.

So the anonymity set you're hiding in is based not just on the number of
messages that are processed during your batch, but also on the width of
the network? That is, a cascade provides more anonymity because its $w$
is 1, but at the same time it's more limited because each node has to
be able to handle all messages?

So what we're really looking at is a tradeoff between size of anonymity
set and amount of work we require from each node (and consequently,
amount of trust we place in each node)?

> > >Let $N$ be the number of nodes in the network. An interesting case
> > >is $w = n = N$; in that case we could use a set of $N$ cascades
> > >arranged as a Latin square.\footnote{[[define Latin square]]}
> > >This ensures that all nodes make full use of the available bandwidth;
> > >however it gives users no choice in the set of nodes used.

Can you elaborate on this point some more? At first glance it appears
that maximizing $w$ is a good way to minimize anonymity sets (and so we
are drawn to a cascade topology if we want best anonymity).

--Roger