[freehaven-dev] Resource management for Chord

[Roger Dingledine <arma@mit.edu>]

This is the latest brainstorm on the idea that Raph Levien originally
proposed to a few of us, on how to manage resources in Chord (the goal
is to reduce the damage that Bad People can do). I've published it here
for greater exposure and hopefully more comments. I'm sorry that some
of the statements seem kind of terse; I'm trying to make this not take
10 pages. Please do ask me if you want an idea clarified.

The overall idea is a Chord network where each node issues its own
currency (coins), and you need to present one of its coins to a node
in order for it to process your request (read, write, etc). Overlaid on
the Chord network is a trust network, specifying who "trusts" who.

In the original formulation, nodes mint coins and give those coins to
nodes they 'like' (trust). Nodes trade coins so they always have "enough"
to do transactions -- eg, they might try to have a comparable-sized
bucket of coins for each finger in the Chord finger table.

Thus it is easy to get coins if:
* You're pointed at in the trust graph
* You have coins somebody wants (and they can learn this)

First concern: "What about double-spending?"
The ecash we're using is *transferable* ecash, so the standard fraud
detection techniques from Brands and Chaum don't work -- they rely on the
"bank->user->merchant->bank" model of money flow. But if we throw out
the anonymity requirement, we can make this work by simply including an
audit trail with each coin. When you give a coin to somebody, sign it
saying you did. Coins are only valid with a complete audit trail.
Double-spent coins have an audit trail which forks at the faulty node.

Second concern: "Chord is vulnerable to false finger table updates."
Indeed, Chord gains its efficiency because nodes only remember a small
bit of information about the network participants, and they assume
you're being nice when you tell them that things have changed. Thus even
one false finger table update can really break things. We don't address
this, but rather leave it to the Chord team. But note that this means we
shouldn't charge coins for finger table updates, because that wouldn't
do any good.

Third concern: "Honest nodes don't know how many coins to print. Bad
nodes can mint an arbitrary number of coins."
Honest nodes should moderate the number of coins they mint based on how
hosed they have been or want to be. They can also tune the lifetime of
coins, to gain greater control over how hosed they might be. They can also
moderate which downstream nodes they give coins to, if certain downstream
nodes tend to cause pain for them (eg sudden spending sprees). As for
bad nodes and inflation, see the discussion of "coin credibility" below.

"Why give coins away?"
* People are more likely to like you (== trust you) if you
  demonstrate that you trust some people.
* Giving a coin to C is a contract that you are willing to do work
  for C. Nodes are participating in the system not to maximize their
  profit but to contribute resources to the system. The goal is not to
  collect as many coins as possible, but rather to get into a position
  where they have enough coins to do what they were intending to do.
  So in theory they don't mind giving coins away, since that's what
  they're there for.

Perhaps you should give away excess coins of any type (not just your own)
downstream in the trust graph. This makes it much more likely that the
system will work in a way characterized by the max flow algorithms.

Fourth concern: "How do you punish misbehavior?"
Meta-reputation -- "coin credibility"
* Option 1: Each person learns coin credibility separately
  * Easy to do and set up, decentralized so nothing to attack.
  * New nodes are scary (since they might screw you), so nobody finds
    new honest nodes.
  * System is very static, since you don't learn from others' fortunes
    or misfortunes.
* Option 2: Reputation System -- third party references arrive at
  a reputation server, who collates them and answers reputation queries.
  * The system adapts quickly to node performance changes or changes in
    how valuable a currency "ought to be".
  * Less work for each node, since the reputation server does the work
  * Reputation servers have pooled information, so they learn more than
    one server can learn individually.
  * Reputation servers are particularly valuable for new people joining
    the system.
  * Reputation servers can also act as bulletin boards or match-makers,
    making it much easier to know who is offering which coins.
  * Reputation servers, even if redundant, are a vulnerable centralized
    point.

Note that pinpointing a double-spender is tricky. Imagine a pair of
audit trails
 A -> B -> C -> D -> E -> F
 A -> B -> C -> D -> E -> G
Clearly E was the double-spender, but E could just be a scapegoat created
by D. But D could have been created by C. So A's real recourse when
its coin was double-spent is to blame B a little bit (perhaps it shifts
the proportions of coins that it gives out a little bit away from B),
and possibly tell B about it -- then B might decrement its chances of
trading with C in the future, and/or choose to tell C about it. And so
on down the line.

New people joining the system have unknown coins. Nobody would want to
trade known-credible coins for unknown coins. Since nodes give coins
away for free, people will learn the credibility of these coins, allowing
their value to increase over time.

"What are coins for?"
They're clearly not for updating finger tables, as shown above. Since
storage resources and service resources (bandwidth, cpu, etc) have very
different properties, it makes sense to separate write coins and read
coins -- or more generally, to have write coins and service coins. The
service coins can be used for reading, querying about available coins,
checking coin validity ("has this been double-spent yet?"), etc. Indeed,
services can be free except during times of congestion, meaning service
coins are mostly unnecessary except if you want to get preferential
service treatment. Write coins can include the details of the offered
contract, such as starting and ending times for storage of a share.

Nodes can limit even more the distance that coins can travel by
including policies with each coin. For example, a policy on A's coin
to B might encourage the advogato capacity limits by declaring "You
can give at most 15 coins from this batch to C" -- A will honor the
first 15 coins that come in with an audit trail starting "A -> B -> C",
and then get increasingly unhappy at B as more such coins come in. More
general policies might be "You can give away at most 15 coins from this
batch", or "Audit trails from this batch can be at most 5 hops." Policies
included in coins will increase their size and complicate the trading
and reputation tracking algorithms, but could prove extremely useful.

"Since coins expire, they depreciate as their expiration date nears."
We can get as deep as we like into economic modelling and discussions,
based eg around trafficking in coin futures, etc. More power to you,
if you figure out how to do this and other people agree to it.

"Why use Chord at all, if we have this reputation system?"
Chord provides an efficient lookup system which is crucial for finding
the location of data. A trading system, or even a good reputation system,
is no good without a way of efficiently doing things.

"Can we throw away the trust web and just use reputation servers?"
We could, since reputation servers are as powerful as we make them. In
the new system, you go directly to the guy you want to do a transaction
with and bribe him with your coins to do the transaction. Perhaps
you go early and bribe him with your coins to give you a coin of his,
which you can use later. Or maybe you ask other people for his coin,
if they're willing to trade it to you. You can get opinions from the
reputation servers, or keep track of things yourself if you prefer.
It's a very appealing model, since it seems to solve the same problems,
without needing the trust web. But the trust web is very compelling,
since it's decentralized -- the reputation servers can be attacked and
taken out. The more we rely on the reputation server to run the network,
the more damage if we lose it.

"Can we throw away the reputation server and just use the trust web?"
In this idea, each node records what it observes, and when necessary
it adjusts its local trust decisions (to whom it gives its coins (and
maybe how the policies work), and with whom it attempts to trade coins)
so things are better for it. It's conceivable that this could work,
and if it did then we'd remove the major headache of the reputation
server. New people would get introduced to the system by meeting other
server operators out-of-band and getting trusted, or by doing some service
for established nodes and getting those nodes to introduce them to other
established nodes to gain credibility. Coins are a mechanism to quantify
the idea of "offered storage", and to make it more convenient to trade
around the ability to cash in on that offer.

"In reality, a combination of these approaches is the best way to do it."
Get nodes to remember things locally, but also allow them to pool
statements together so periodically nodes can download a snapshot of the
overall system to get hints at trends and new honest nodes. The system
continues to function smoothly if the reputation servers disappear for
a while, but it functions even more smoothly if the reputation server
is there and providing more information.

Getting rid of the requirement for anonymity allows much easier
verification, in turn making the development of a comparable reputation
system much simpler.

--Roger