[freehaven-dev] On Buddies and Spawning

[Roger R Dingledine <arma@mit.edu>]

Each share has a buddy share, whose job it is to watch over that share
and decide when it has been lost. Once it has been lost, the buddy does
a broadcast announcement declaring its opinion that the share has been
lost. For added robustness, perhaps the buddy should spawn a new copy
of itself after its share dies. Indeed, after this death the buddy
no longer has a buddy, so it's defenseless if an evil node wishes to
silently delete it.
However, the idea of allowing buddies to spawn introduces many more
problems than it solves. First of all is the problem of exponential
growth of share population. If two shares get separated by network
outages (or if they're intentionally kept from communicating by an evil
server), they will declare each other lost and double in population.
This frequent population doubling is bad, because each new buddy that's
spawned must be kept as a new share until its expiration date is reached
-- this means introducing new shares into the system, and also means
forcing servnet nodes that are following the protocol (the 'good' nodes)
to provide space from their own machine for the new buddies. A possible
solution to this is come up with some sort of protocol for shares to
notice that there are more than two of them, and somehow agree on which
should die out (having support for premature death of shares is very
dangerous) or merge (having the ability to make directed trades so a
share and some of its buddies arrive in the same place leaves us open to
attacks where an evil node suckers every share to arrive at the same time,
and then kills them all). In any case, such a solution adds increased
complexity to the protocols, and most likely reduces the anonymity of
the system, since it requires frequent conversations between shares and
their buddies, possibly on such touchy subjects as declaring locations.

Another possibility is to start out with 3 or more copies of each
share. This could simply have the advantage that a given share doesn't
die out as quickly, or it could introduce some more flexibility (and thus
complexity) such as voting on trust issues: if only one buddy broadcasts an
opinion about a lost share, chances are good that it's lying.

However, the reason why a buddy might squawk is based entirely on
its own decision that something is amiss. As such, it has no real
cryptographic proof that the share in question has been lost. This means
that the assessment of its broadcast (how much weight to put in it,
whether to react) is necessarily a fuzzy and qualitative calculation.

Because of this qualitative nature, the response to a squawk will be
based in large part on the configuration of each individual listener --
whether it is amenable to believing a node's squawk or whether it prefers
to ignore squawks.

------

We want to categorize and distinguish between the benefits that we get:
breaking the document into shares provides us with reliability, whereas
adding buddies provides us with accountability. If we want more
reliability, we should simply use more shares. This implies that the
only reason to use more than 2 buddies would be if it gains us increased
accountability. Since the accountability we get from buddies is already
pretty vague (and based more on the behavior of the listener than of the
buddy), and also because more than two buddies implies a significant
increase in the complexity of the trust network and its protocols, I
believe that two buddies is a very reasonable choice.



Of course, this begs the next question: why are buddies for the 'same'
share? Can we remove the factor of two overhead from having an extra
copy for each share, by pointing share 1 at share 2 as its 'buddy', and
share 2 at share 3 as its buddy, etc? I'm really tired right now, so I
don't know if this is a really stupid question or a really insightful
one. Let me know. :)

Thanks,
--Roger