Re: [freehaven-dev] (FWD) Re: paper comments - 1st impressions

[Roger Dingledine <arma@mit.edu>]

> Date: Sun, 25 Feb 2001 07:11:38 +0000
> From: David Hopwood <hopwood@zetnet.co.uk>
> To: freehaven@freehaven.net
> Subject: Re: paper comments - 1st impressions
> 
> Yes. This does cause very severe practical problems. Fortunately, I
> think it's possible to eliminate the ledger entirely.

The benefit of the ledger is that it allows anybody to verify a claim.
Ideally, we'd like to allow anybody to claim ("verify (in)correct
operation of MIXes") as well.

The intuition is to broadcast so everybody knows the truth. But yes,
there are practical implications for this which make it not work very
well in practice.

Specifically, the ledger idea requires every MIX node to query the ledger
every T (perhaps 12 hours). This is kind of bad. What gets really bad
is that Alice (the sender), in order to check if her mail got through,
has to query the ledger. Either she queries the ledger for every entry
(prohibitively expensive) or she queries just for the nodes in her path,
thus giving away her path. Oops.
 
> The purpose of the ledger in the original protocol was to split
> sending a message from receiving it, in such a way that anyone can
> determine later whether a message was sent. The problem it solves
> is that if A fails to send a message to B, we want an observer
> to be able to determine whether that is A's fault or B's fault.

More than just 'an observer'. '*any* observer'.

> I suggested before a method of reducing reliance on the ledger by
> using receipts. Suppose we use that idea, and also replace the remaining
> use of the ledger with a set of "judges" (who are fairly well respected,
> but none of which need be trusted absolutely). The judges should have
> reasonably reliable, high-bandwidth Internet connections.

This idea seems reasonable. I don't like the idea of needing Alice to
query every node in her path, but that had to be done on the ledger anyway
(oops), and this is more feasible.
 
> This also simplifies the failure proofs, because all messages should
> have receipts (rather than having to consider the two cases of messages
> that are sent directly, and those that are published to the ledger, as
> in my previous suggestion).
 
We should also walk through some cases where Alice chooses a consecutive
sequence of bad mixes in her path (where if those bad mixes are controlled
by one person, that person can choose which mix gets "blamed" if he
chooses to drop a message). But I think we're ok there; it would just
be good to have it explicit.

> To accuse N_j of being unreliable, send an accusation (that it received
> a message M and did not pass it on in time) to all of the judges.
> N_j can refute it by sending back its receipt for M to each judge.
> The judges who do not get back a receipt that refutes the accusation
> will conclude that N_j is unreliable, and publish that as before.

My first thought is that evil judges will wrongly accuse mixes, meaning
mixes need to query the judges every so often to make sure they aren't
publishing false data.

But we're ok. Judges will be of two forms:
"Good": plays the protocol. Checks with the mix first. So the mix doesn't
have to worry.
"Evil": doesn't play the protocol. Eg, doesn't check with the mix first.
But this judge would also ignore the mix if he said "no, wait, I've got
a receipt for that!". So the mix doesn't have to worry (there's nothing
he can do).

> > >We should talk about recompense or payment more generally, without
> > >discussing digital cash unless we really need to do so. The point still
> > >stands that there's no good way to pay MIXes in place.
> 
> Yes there is. I will post a protocol for this (that can also pay for
> storage and other things).

I'd be very curious to see this. We've been fighting with the storage
payment problem ever since we started Free Haven.
 
> Fixed by sending accusations via the mix-net (in the protocol using judges,
> the accuser would probably send to each judge by a different route - this
> works as long as the mix-net is not so unreliable that none of the
> messages get through, or not enough get through that people will trust
> that many judges).
 
Good. I also get the feeling that this environment is more amenable to
handling replays without fear of reputation loss. Have you given any
thought to this?

> To prevent this, the final recipient should look like another mix
> node, and should send a receipt back to the sender using a one-time
> reply block. Obviously this doesn't apply for recipients who don't have
> any compatible software, but nothing can be done about that.

Agreed.
 
> > >> Sections 5-9 are somewhat new, but offer no surprises.  There is no
> > >> discussion on active attacks. For instance, usually a mix network
> > >
> > >Yes, this is a good point. We should explicitly say what we can do about
> > >these attacks.
> 
> I can do that.

Is there a canonical list somewhere of active attack categories?
 

One of the reviewers suggestions that we compress sections 1-4
dramatically, and focus on the rest of it. I agree with this idea.

I think we could spend a bit of time describing the receipt/judge notion,
then some more time describing how to approach a reputation system here,
then some time with a model and analysis (including Mike's musings on
economic theory implication), plus a good bit of time describing attacks
and how we handle them, and also reasonable extensions that make the
system more foo (for foo \in {anonymous, reliable, robust, efficient, ...)

I think we can do this, and it will turn out well. Anybody want to
volunteer to shred the first half of the paper?

Thanks,
--Roger