Re: [freehaven-dev] meeting sunday 2pm

[Roger Dingledine <arma@mit.edu>]

On Thu, Feb 03, 2000 at 12:57:48PM -0500, Todd Kamin wrote:
> I've got a question about how the whole buddy share idea relates to the idea of
> splitting files into shares.  I might be missing something here, but it seems to
> me we have added excess redundancy and complexity by including both these ideas.
> 
> Why do we even need buddy shares?  If some k shares of N total shares of a file
> are needed to reconstruct it, then N-k shares can be lost over the lifetime of a
> file without affecting the system's ability to reconstruct the file.  If the
> servnet is sufficiently evil so that more than N-k shares get lost over the
> lifetime of a file, then the servnet itself shouldn't be probably trusted with
> data at all.  In this case where many of the servers are evil, having a buddy
> might provide a little more robustness, but it won't ensure that files are not
> lost or that parts of files are not lost.  We don't want to burden the
> good servers with endlessly spawning copies of shares.  And, best of all, we
> won't have to deal with designing a good buddy share system.
 
The trick is that these two ideas address different issues. I think my
terminology was that the IDA (the share system) provides redundancy,
whereas the buddy system provides accountability. What this means is that
the "k of N" is what keeps evil systems from actually affecting the
documents in the servnet. The buddy system doesn't do this -- indeed, we
concluded at the meeting that we really can't afford to have buddies
spawn, because it introduces too many timing issues and timing attacks.
Buddies are there solely to be able to notice nodes that are dropping
shares. Otherwise nobody will ever know where a given share got dropped,
and that node will be able to continue playing the protocol and being evil
until he 'slips up'.

Now, you might ask "but we already have some measure of accountability --
people are checking on their shares, and if they go away then they lose
trust in the nodes they gave them to. Isn't this system sufficient to
eventually locate evil nodes, and isn't eventually Good Enough?"
It might well be good enough. I'm worried that it makes the system
very brittle, because it's open to a lot of timing and other devious
attacks from nodes that want to be evil just infrequently enough that
people don't think it's them. (In particular, timing attacks from people
teaming up to make somebody else look bad, or to do a DoS on a few nodes
of the mixnet at the same time as doing something slightly nasty, etc.)
I feel safer with a mechanism that is able to more closely localize
where and when the share was lost. There are still some holes in the
buddy system, but I don't think any of them are large enough that it
will break down. I hope. :)

> Curious,
> Todd

Thanks. Keep asking questions. :)
--Roger