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

[Roger Dingledine <arma@mit.edu>]

On Wed, Mar 14, 2001 at 03:17:03AM +0000, David Hopwood wrote:
> The receipts don't need to be sent back to Alice, only to the previous
> node. There is also an end-to-end receipt that is sent from Bob to Alice,
> using a (one-time, limited duration) reply block, so that Alice knows
> whether the whole transmission succeeded.

Ah, ok. So there can be an end-to-end receipt, as you describe. Alternatives
include:

* Alice uses a test messages so she knows if it arrives.
* Alice posts to a public forum (eg usenet) so she knows if it arrives.
* Alice probabilistically asks for receipts -- often enough that she
  busts people who are frequently cheating.
* Alice simply freeloads and trusts that other people will do the
  test messages or other actions needed to verify/publicize node behavior.

Any of these sound at all relevant, or should we simply say "she puts
a reply block in there and Bob should answer it" and be done with it?
 
> No, to h. Alice can later request the receipt from h (using the mix-net
> with another one-time reply block, to preserve her anonymity). Since she
> doesn't initially know which node failed, she uses a binary search to
> determine the last node on the path that has a receipt.

<quibble>Note the "hold-receipt-til-queried" behavior I described in an
earlier post; it just might be able to foil this binary search.</quibble>
 
> >      But: what is the technique whereby A knows that the list of W's i
> >        provides is "right"?
> 
> i has to include a core group of (partially) trusted witnesses.

So there is a static publically known set of witnesses which Alice
expects to see receipts from. If there are 9 core witnesses, then 5 or
more failure receipts *from core witnesses* is enough to convince Alice
that i isn't lying. Alice ignores non-core witnesses.

This means that even if i picks a subset of witnesses to query (or,
equivalently, picks a subset of receipts to give to Alice), then he
still can't convince a majority of core witnesses to collude with him.
 
> Exactly. These witnesses would probably also be scorers, in which case
> they can score based on any failures that they witness directly, without
> having to trust anyone else.

Sounds good.

In the earlier protocol anybody could become a scorer, because the
contents of the ledger were public. Yet here, any witnesses who aren't
core witnesses are effectively freeloaders and can be ignored (and should
be ignored, for the sake of efficiency) by all sides. That means that
non-core witnesses won't get reports of bad nodes. Is there any way to
salvage the anybody-a-scorer approach? (I'm ok if there isn't.)
 
Thanks for the clarifications,
--Roger