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

[David Hopwood <hopwood@zetnet.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----

Roger Dingledine wrote:
> 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).

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.

(If a node on the reply path fails, that can be proven using the same
protocol.)

> 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.

Yes.

> 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,

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.

>   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

No, Alice must be prepared to challenge j if necessary.

>   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.

Yes.

>        (Alternate: i sends the W-receipts to Alice too.
>        So Alice never has to challenge.)

i doesn't know who Alice is, and has no way to send anything to her. (It
would be possible to put reply blocks in each layer of the onion, but that
would require O(k^2) space overhead, so I wasn't intending that that should
be done.)

>      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.

>        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.

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.

> 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.

There would be no advantage to i in doing this. It might as well dump
the message instead.

>       This implies that A needs
>       to challenge j at some point in this process too, yes?

Yes, using the challenge protocol described in the paper under Goal 1.

>     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.

The challenge protocol will work in any of these cases.

>       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)?

The latter, see above.

- -- 
David Hopwood <hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBOq7ilDkCAxeYt5gVAQEGuQf/TyMLFZwp0ItqHJER/Be9OF6/zcJnZSi0
fr2DVPaoNGYp//3S0Y8xYF9F/EhFQ1/MgSCYFWOK3Z/GWWRg6G2cjwGRyJJ/cZcj
vbiYf+cla5myzE2vJ9p0qZwJDAyCKzuYrpoQem1BqxEIGtjq7sX1ZkORvO77+nnk
L3lMCoU+v0yk1pSb5WEehWj1pkKFmYXT0omRUUlcajx4nOvuqBklaCFCzfMwpPKN
rezz0541RUTlAXwM/YJaudnJsxVq7yt+2j44xzBqxM5s34M3FpoWqQiKFTrcXJ4M
hzvpyttsgNrRp0rpQjsaoSA3uClJrR41QUMHkKG/QZd/mDz78kpYqg==
=bcCJ
-----END PGP SIGNATURE-----