(FWD) Re: [freehaven-dev] Resource management for Chord

[Roger Dingledine <arma@mit.edu>]

----- Forwarded message from owner-freehaven-dev@seul.org -----

From: Raph Levien <raph@levien.com>
Date: Tue, 24 Jul 2001 22:11:30 -0700
To: Roger Dingledine <arma@mit.edu>
Cc: freehaven-dev@freehaven.net, zooko@zooko.com
Subject: Re: [freehaven-dev] Resource management for Chord

Thanks, Roger, for the thoughtful feedback to my wacky ideas.

I've been thinking about reputation in stamp-trading networks a bit
more, and have come up with the outline of a new proposal.

First, what are the attacks we're trying to prevent? An attacker node
can do anything it likes, but it takes some thought to figure out
which attacks are actually interesting. Here is my list:

1. An attacker can simply forge stamps. This is trivial because, in
my scheme, there is no cryptographic protection.

2. An attacker can attempt to flood the network with his own stamps.
To the extent that these displace the good stamps, the network is
harmed.

3. An attacker can attempt to game the exchange rates of individual
nodes who are trading stamps. There are lots of ways to do this, but
one of the more interesting is to cause ones own worthless stamps
to be accepted for high exchange value.

I am not at all sure that this characterizes the space of interesting
attacks. It should be a good start, though.

Let's look at (1) first. An obvious approach is to use digicash-like
coins instead of purely random stamps. However, I'm not convinced that
this will help much. It's still possible to double-spend, and I'm not
convinced that techniques for detecting double-spending are any easier
than techniques for detecting more straightforward forgeries.

Probably a more effective approach is to modify the stamp trading
protocol so that nodes can accept their own stamps, and issue new
stamps of value nearly equal to the value of the valid stamps
submitted. A node who wishes to purchase stamps buys them from the
seller, then verifies them with the issuer. This is analogous to the
"deposit and withdraw" protocol that Mojo Nation uses to avoid double
spending.

For (2), one approach I've considered is to limit the _inflow_ of
stamps on each edge. Note that, if the exchange rate is fixed at 1:1,
this limitation takes care of itself, as the inflow is exactly equal
to the outflow, and the outflow is bounded (it is manually
configured).

However, there's reason to believe that more flexible exchange rates
are desirable. In this case, as the value of the stamps goes down, the
ability to flood the network with them goes up. This isn't good.

In order to analyze attacks based on exchange rates, one needs a
concrete proposal for how the exchange rates are determined. I've left
this open before, but am now ready to suggest one.

Recall that each node keeps a set of "stamps on hand". I propose that
each stamp in this set has an accompanying history trail. Thus, for
stamps that A gives to B along the A->B trust link, the history trail
reads simply "received stamps from A."

Now, if B wants to purchase C stamps, and if A has them on hand, B
buys them from A using A stamps. The history trail on the returned C
stamps now reads, "received stamps from A, used them to purchase C
stamps from A". Another iteration of this might append "used them to
purchase D stamps from C".

Now, when a stamp comes to the end of its life, its history trail is
used as feedback to the "reputations" of the nodes listed in the
trail. End of life for a stamp may arise from:

1. Expiration. This would indicate that the stamp is not in
particularly high demand. Perhaps the exchange rate should be lowered.

2. It buys something (other than stamps) successfully. Cool beans!
Perhaps the exchange rate should be raised. Also, we might want to
keep track of the quality of the purchase when that's appropriate
(latency is one such criterion, and is common to nearly all
transactions).

3. It is purchased. This indicates that the stamp is in demand by
other nodes. Perhaps the exchange rate should be raised.

4. It is rejected - ie, an attempt was made to purchase something
(other stamp or otherwise), and the issuer claimed it wasn't
valid. Bad juju. We don't want to buy any more of these, so lower the
exchange rate.

Now for a tricky question: how to divvy up the blame or praise? I'm
not sure yet. At this point, I don't see anything wrong with just
dividing it equally among the nodes listed in the trail, but a
different heuristic might of course be better.

The exchange rate determines two parameters in the protocol. First how
many of our own stamps should we charge a node who wants to buy stamps
from us? Second, how eager are we to purchase X stamps from trading
partner Y? In particular, compare the ratio of our valuations of X and
Y stamps with Y's exchange rate for X stamps. If it's favorable,
buy. If it's unfavorable, pass. I believe this should set up a decent
equilibrium.

Analysis is going to be a bit tricky. One thing to keep in mind is
that we expect a wide variation in the number of transactions with
each trading partner. Nodes close in either hash space or close in the
trust graph will probably be common trading partners, while others
will be contacted very rarely. In the latter case, not enough
transactions will be performed on the node to evaluate its reputation
with any confidence. Thus, we're trusting the nodes who sold us the
stamp.

The reputation of stamps is implicit in the exchange rate. It may make
sense to report some of the reputation data explicitly. For example,
it might be valuable to distinguish whether X stamps have low value
because X charges a lot for its services, (but delivers reliably), or
whether there's a high rejection rate. But I see this as a refinement.
I'm sure that the analysis is going to be hard enough just looking at
scalar-valued exchange rates.

My intuition tells me that this should work. High valuations derive
from successful transactions. Attempts to flood or forge should drive
valuations down to zero. Local errors probably won't propagate widely
and do much damage, because everything flows along trust links. But
it's certainly complex enough that I'm not sure. Doing the analysis
is going to be real work. I would _love_ it if there were anyone out
there smart enough, and interested enough, to help with that. Let's
do a paper together!

Raph

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