[freehaven-dev] more musings on the judge/receipt notion

[Roger Dingledine <arma@mit.edu>]

Algorithm for a 100% reliable node:

Accept all incoming messages. Store them. Don't ever forward anything.
Listen for people asking you for a receipt. Whenever anybody does,
deliver that message, and send back the receipt you just got.

Assumptions:
1) you can store a whole lot of packets.
2) when you try to send to the next hop, it works.

Let's examine this second assumption more.

My first suggestion for Alice (the unhappy sender) to identify the
faulty node is to binary search over her path. That way with a mere log
n queries, she can locate the evil node. Yet with the above algorithm,
she'll get confused and might either rule out nodes that actually are
the bad ones, or do a bad-node-haunt which 'causes' her message to
get delivered.  The solution? I guess if Alice suspects her message
hasn't been delivered, then she needs to do an O(n) search starting at
the beginning.
Does that work?
(How does she suspect her message didn't get delivered, anyway? In
the ledger system, she could know for sure. Are we going to restrict
claim-able messages to test messages sent for the purpose of claiming?)

This also raises another point of confusion I've got, pertaining to
how Alice notices/queries. As I understand from your description of
the protocol: if a node B fails to deliver to a node C, then it goes to
a bunch of judges and says "C isn't listening to me". The judges then
ascertain that themselves, and if it's true "they publish that fact",
else they give B a valid receipt from C.

Yet how does Alice know that a given judge published that fact? She's
going to query B, and B is going to say "well, yeah, that's because C
sucks." Can B provide anything more substantive back to Alice? (Say,
a statement from a judge J_1 that J_1 also thinks C sucks.)

So what if node B has bad taste in judges, but otherwise performs the
protocol correctly? So when Alice asks B about her message, and B says
"well, J_1 says it's not my fault", and Alice says "well yeah, but J_1
can't tie his own shoes, much less deliver messages" -- what can Alice
do at this point? Do we need a secondary reputation-for-picking-judges
value for nodes? Do we have to offload that knowledge onto users, who
have to keep track of it and remember it themselves, or can we somehow
get judges to track that information too?

This can be helped a bit because if B asks enough J's, one of them will
be 'good' and will return a receipt to C. So does this come down to
"How do we get B to pick a non-evil judge?"?

Sorry for posting only questions so far. :) I was trying to go to sleep,
and it popped into my head.

(O, and a way to make the algorithm I proposed at the top of this mail
even more robust: if the next hop has a good reputation, keep the message
until somebody asks for a receipt, else forward it. That way you maximally
disrupt traffic while still being pretty certain you can get a receipt
if Alice calls you on it. Isn't it great what you can do if reputations
are public?)

--Roger