[freehaven-dev] Trading / Buddies

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

Let me give a summary of how this is going to work, before I start
assessing options for buddy spawning and number of buddies.

For each share, when it is created a certain number of copies are
created; each copy is called a 'buddy', and each share is labelled
by which number buddy it is. Just to say that again: each buddy is
*different*. The buddy number on the inside will be different, so
the pile of bits that are signed by the PK for that document will
be different. On the other hand, every share is also marked with a
share number, so people doing the document reconstruction can ignore
the buddy number.

Each of these buddy shares needs to be traded away separately; this means
that implementing an n-buddy system means a factor of n increase in overhead
per document.

Each buddy has some dynamic data associated with it, for each other buddy.
Specifically, each buddy stores one of sets A, B, or C:
A. "My buddy is dead."
B. "I am a secondary copy. Don't do anything related to buddies with me."
C. Each of the following.
  * Timestamped "I know my buddy is alive"
  * Timestamped certificate from PK_b saying "I, node b, am in charge of this
    data."
  * Number of successive queries that have failed for this buddy
  * Number of primaries we believe to be in existence for this buddy
  * Number of secondaries we believe to be in existence for this buddy
  * Flag for whether this buddy has a query in progress (so he doesn't move)

A trade between C and D can be abstracted as the following:
C has a document doc1 and D has a document doc2, and they want to trade.
They negotiate a trade, and afterwards:
* C has doc2 and a receipt from D saying "I have received doc1 from you and
  will keep it."
* D has doc1 and a receipt from C saying "I have received doc2 from you and
  will keep it."
* All buddies of doc1 have been notified by C that C is relinquishing the
  file to D, and by D that it is now in charge of the file.
* All buddies of doc2 have been notified by D that D is relinquishing the
  file to C, and by C that it is now in charge of the file.

The key to remember is that we use these receipts as guides. You cannot
"prove" anything with them. You can only use them to make your claim sound
more plausible. Whether somebody believes your claim will come down to
whether they 'trust' you, in the sense of the trust network.
With this in mind, here's one implementation of the trading protocol:

1) C sends a message to D with "doc1" and "description of desired doc2"
2) D sends a message to C with "doc2" and "receipt for doc1"
3) C sends a message to D with "receipt for doc2"
   C sends a message to buddies of doc1 saying "I relinquish doc1 to D"
   C sends a message to buddies of doc2 saying "I am in charge of doc2"
4) D sends a message to buddies of doc2 saying "I relinquish doc2 to C"
   D sends a message to buddies of doc1 saying "I am in charge of doc1"

The buddies only get notified after the trade is agreed to from both
sides. Notice that C ends up with a receipt from D before he decides whether
to make the trade. There isn't a real solution to this though, without
either a whole bunch of messages or a third party (plus secure reliable
connection between TP and others) that everybody trusts...

Periodically (configurable by each given node), a share decides to check
on its buddies. It does this by doing a request, either for the whole
document or only for its share number (the frequency of which it chooses
is configurable by the node too). After a while, it figures it's given
people enough time to respond, and it counts up the number of primary
and secondary shares it's received for each buddy number, and decides
if anything's missing. If it is, it increments the "# successive failed
queries", and if that has passed a threshold (also configurable on that
node), it decides to 'squawk'.

The process of squawking consists of broadcasting a signed opinion that
a specified node lost a share that it was responsible for.

Optionally, a node can negotiate with another node for that node to
be a 'proxy squawker' for that squawk. The motivation for this will be
explained further in the discussion of the 'cut the internet backbone'
attack. (Don't you love these names? :)

If a node wants to refute an accusation against it, it does so as a
separate broadcast. It broadcasts a message containing the claim it's
referring to, plus a receipt indicating that it gave responsibility
of the share to somebody else. Whether the refutation is convincing will
be left entirely up to each listening node.

Ok, that's enough for one mail.
I'll cover tradeoffs for buddy spawning or how many buddies to choose in
the next mail.

--Roger