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

[Michael J Freedman <mfreed@MIT.EDU>]

The very short answer before I really thought about this problem:  I always
considered querying the judges as a majority function.   

We don't want to get uber-fancy with judge-reputation in some cyclical
fashion.  When somebody wants to tattle on another node, contact some k
judges (where k is small) chosen at random.  Then, we can ask judges about
reputation in some sort of majority function.  

This does ignore some potential problems with adversaries colluding with
evil judges and only "randomly choosing" these evil judges.  This might be
true to some extent, Roger, I guess it's an area to consider further.

--mike


At 02:08 AM 3/3/2001 -0500, you wrote:
>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
> 

-----
"Not all those who wander are lost."                  mfreed@mit.edu