[freehaven-dev] Idea: building mix cascades via reputation

[Roger Dingledine <arma@mit.edu>]

I'm trying to get an idea of previous work and how feasible/interesting
this sounds.

The idea follows from our IHW2001 paper on tracking mix reliability. One
of the problems that we found from that paper was that an adversary could
perform a selective DoS attack, such that his nodes were the only ones
remaining with a good reputation. Then users would choose their mix path
from the adversary's nodes, thus losing their anonymity.

At IHW, Ross Anderson suggested building longer-term paths, much as
the phone company builds when routing large sets of phone calls around
England. I got another spark when I ran across a 1998 coderpunks post
from Jim McCoy about how to gather participants for a DC-net based on
comparable bandwidth and reputation.

The overall idea is to form mix cascades out of mixes which have
comparable bandwidth and comparable reputation.

In the simple version, there's a Reputation Server (RS) which is
responsible for tracking cascade reliability and also for declaring new
cascades (we can separate the roles later). Mixes inform the RS about
the bandwidth they intend to provide (perhaps they choose from various
classes -- 10k/s, 100k/s, 1M/s, etc), and the RS randomly combines mixes
with comparable bandwidth and comparable reputation into cascades.

Cascades continue until a timeout is reached (the cascade was
'successful'), or at some point the bandwidth being achieved is some
threshold less than the intended bandwidth (the cascade 'failed'). If a
cascade fails, the RS marks a -1 for each participating mix -- regardless
of which one caused it to fail. If a cascade succeeds, each mix gets a +1.

Since the RS chooses cascades, the adversary can't build a cascade
of his own and publish it. The scheme works if there are lots of
participating nodes -- each randomly constructed cascade will probably
not be entirely owned by the adversary. An adversary can only get his
mix into a high-reputation cascade if his mix has comparable reputation;
if he causes the cascade to fail, then he sacrifices his reputation
along with the rest of them.

If mixes publish their cascade success and failure statements (and
they are verifiable), then we can reduce the trust required for the
reputation-tracker role. By using some sort of multi-party computation (eg
each node commits a random number, and since the adversary cannot predict
the numbers from honest participants, he can't rig cascade formation),
we can remove the trust requirement for the cascade-chooser role.

It's not immune to shilling and other attacks, but it's really simple. :)
If honest participants can provide significantly more bandwidth than
the adversary, then high-reputation mixes (and thus cascades) ought to
be hard to take down.

I'm worried that it will be hard to verify failure or success of a
cascade, though. What incentive do participants in a failed cascade have
to tell anyone that it failed? If bandwidth is all that gets counted,
can bad nodes replace real traffic with (valid) garbage, and thus cause
a cascade to be successful even if it's not delivering any messages? Do
we need to leverage the more-complicated witness system from the mix-acc
paper in order to verify correct mix operation, or can we get by with
something simpler since we only need to verify correct cascade operation?

Since we're looking at cascades and bandwidth, it seems intuitive to
try to transition our ideas over to stream-based mixes rather than
packet-based mixes. Does that hurt or help things?

Thoughts?
--Roger