[freehaven-dev] (mix-acc) more ponderings about witnesses and receipts

[Roger Dingledine <arma@mit.edu>]

Comments and criticisms welcome. Please correct my misunderstandings.
I'm quite certain that I'm missing some pieces to the logic here, too.

Say Alice chooses a path to Bob:

A -> ... -> h -> i -> j -> ... -> B

In this case, i produced a receipt for h, and i never got a receipt from
j. Let's assume for now (because I think David Hopwood is) that as soon
as you get a receipt, you send it back to Alice (somehow).

So now either i failed (it didn't try to get the message to j) or j
failed (it wasn't around, or didn't provide a valid receipt). We're
not sure which.

Let's say i is a 'good node'.

  So it picks a set of W's and asks them to try to deliver the message
  to j. Either some W succeeds, in which case i gets a valid receipt
  and forwards it back to Alice, or no W succeeds. At this point, we
  can choose how we want the protocol to work:

  1) the protocol stops there, the W's will reflect j's reputation down
  the road, and Alice doesn't take a part in proving/claiming anything

  2) Alice is going to challenge i down the road.
     Then: when Alice challenges i, i should send A the list of W's, and
       Alice can query those W's to learn that they all failed to deliver
       to j.
     Or: each W, upon failing, should send i a receipt saying it failed.
       Then when Alice challenges, i returns the "no, it's not my fault,
       see?" receipts. (Alternate: i sends the W-receipts to Alice too.
       So Alice never has to challenge.)
     But: what is the technique whereby A knows that the list of W's i
       provides is "right"? What if i picks its own subset of W which
       it owns, thus allowing it to blame j when it was really i that
       was bad? What if i only reports a subset of the responses?
     One possibility: the list of W's is relatively small and relatively
       static. They are partially trusted, but the trust isn't complete,
       in that they all have differing goals (say, China gets to run a W,
       the NSA gets to run a W, microsoft gets to run a W, etc.) Then a
       majority of failures means that it's j's fault, not i's.

Then if i is a 'bad node':
  
  Then it doesn't try to send it to j. It either:

    sends the message to all W's, in which case one of them succeeds,
      but i dumps the receipt on the floor. This implies that A needs
      to challenge j at some point in this process too, yes?
    sends the message to a subset of W's. Either one of them succeeds
      or none of them do; this is just like sending it to all of them
      and then selectively ignoring responses.
    sends the message to no W's. Then if A challenges any of the W's
      he will find that i never tried to send it.

      This last point argues that point 1 above ("the protocol stops
      there") allows a bad i an easy attack: simply drop the message.

So how do we want to do the challenges? Is it really wise/efficient to
make the receipts always return to A, or can we manage this with only
a challenge-for-receipt-if-you-want-it protocol (which would eliminate
the need for non-transient reply blocks)?

--Roger