[freehaven-dev] (FWD) Re: paper comments - 1st impressions

[Roger Dingledine <arma@mit.edu>]

----- Forwarded message from David Hopwood <hopwood@zetnet.co.uk> -----

Date: Sun, 25 Feb 2001 23:36:40 +0000
From: David Hopwood <hopwood@zetnet.co.uk>
To: freehaven@freehaven.net
Subject: Re: paper comments - 1st impressions

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

Michael J Freedman wrote:
> David Hopwood wrote:
> >If N_i tries to send a message to N_{i+1} but cannot obtain a receipt,
> >then instead of publishing the message, it sends it to all of the
> >judges (if N_i cannot manage to contact any judges, then it should be
> >considered unreliable, so it is OK that it does not obtain a receipt).
> >
> >Each judge then independently tries to send the message to N_{i+1}
> >(who must provide a separate receipt for each connection). If a judge
> >obtains a receipt, it sends it back to N_i. If N_i receives at least
> >one valid receipt from a judge, it will store one of them as if it had
> >obtained it directly from N_{i+1}. If a judge cannot obtain a receipt,
> >it concludes that N_{i+1} was unreliable, and publishes that fact
> >(here we are communicating the fact that N_{i+1} is unreliable to
> >human listeners, rather than to programs, which allows use of various
> >channels that are unlikely to all be attacked). If someone hears enough
> >judges that they trust say that N_{i+1} is unreliable, they will
> >believe that it is.
> 
> I'm a bit unconvinced that this is providing any real security.  (But I'm
> really tired when reading this, so bear with me).
> 
> N_i sends to N_{i+1}
> N_{i+1} sends a receipt back to N_i saying "I got it."
> N_i is happy
> N_{i+1} does nothing more

Now, suppose the original sender, Alice, suspects that her message has not
been delivered. She determines (by communicating with each node over the
mix-net) the first node that does not have a receipt from the next node on
the route, which in this case will be N_{i+1}.

Because N_i is honest, Alice can obtain from N_i the receipt signed by
N_{i+1}. Then she tells the judges that N_{i+1} failed (also giving the
receipt, message, random seed, and the next node N_{i+2}, which are checked
as in the original protocol). They try to obtain from N_{i+1} its receipt
signed by N_{i+2}, but fail because N_{i+1} doesn't have it. Therefore,
all the judges conclude that N_{i+1} failed, and the honest judges publish
that.

> But it's not quite that simple, 'cause honest nodes can also have a
> failure mode whereby they send the "got it" receipt, then just crash,
> and (I think?) we lose.

If a node crashes, and does not recover in sufficient time to try again,
then it is by definition unreliable.

If you mean that a node might send a receipt then forget that it had to
process the message, that should be prevented by writing the message to
stable storage using a two-phase commit protocol (which is well-understood
stuff from database design), before sending the receipt. If this is
implemented properly, there is no window where an honest node will fail
to satisfy the protocol if it crashes, provided that crashes do not last
too long and are reasonably infrequent.

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

iQEVAwUBOpmM/jkCAxeYt5gVAQGfgAgAp63N8Y7XXp+DMrHx8k6UHuKCyMSENaE5
MgLk8ByoLW/vgXEiZ7H8f4m3xgNYZpKO02xJAjYi5rVUvE+WmWWzP0QqtpsKwvM/
xw/HFvjF5Y1cVzltVmU0F7s1/h9fnSCZD90bXO8Xl/hW2T1xLiK2PmYdZT/WS2sk
8BxexEPCuFXiKCfAfJkJu1KezSO8aSVEFYUJPwSAsk165t7mjeivtRVI0NhOJW4B
8Rxq0FLR2ThqtfgRyq24x38q++qOKrw+VNzPei9kv8VOiXA1OfKgTgEMjhI4zVLo
eLiC/yjn71ImNYCUbz7IsZxKQcFLnCxhucYQ/JYhEPmbVK/ao2VjjQ==
=jwib
-----END PGP SIGNATURE-----

----- End forwarded message -----