Re: [freehaven-dev] sketching accountability requirements/solutions in FH

[Michael J Freedman <mfreed@MIT.EDU>]

Just checked in the following at the end of my micropayments section.
It focuses on a number of the problem Roger described.  Some of these we
might want to futher flush out in a Free Haven resource management
design case study.

--mike


Subsubsection: The difficulty of distributed systems:
               How to exchange micropayments among peers
--------------------------------------------------------

Alice wants resources operated by Bob.  Alice pays Bob with
some micropayments. Bob provides Alice with the purchased access 
to his resources.

This sounds like a great model for economically-based distribution
that provides both accountability and effective congestion management
of resources.  However, the problem is rarely so simple in the case
of peer-to-peer distributed systems on the Internet.

Consider the Mixmaster mix-net remailer.  Alice sends an email to Bob
through a number of intermediate proxy remailers, which strip all
identifying information from the message before transmitting it.  This
design is used to distributed trust across operational and often
jurisdictional lines.  Only a very powerful adversary -- able to observe
large sections of the network and use advanced traffic analysis
techniques -- should be able to link the sender and recipient of any
given message.  Hence, we achieve an "anonymous" communications path for
email.  Zero Knowledge System's Freedom Network is virtually similar in
basic design.

Consider Gnutella or Freenet with their corresponding routing protocols.
Alice seeks some piece of information contained in the network.  She
sends out a query to all peers that she knows about (her "friends"),
these peers in turn propogate the request along, branching it through
the network.  Hopefully, before the time-to-live (TTL) of the query
expires, the request traverses enough intermediate hops and finds Bob,
who responds with the desired information.

These examples highlight a design quite common in P2P systems,
especially for systems focusing on anonymity (by distributing trust) or
searching (by distributing content).  That is, endpoint peers are not
the sole ones involved in an operation; Alice and Bob are joined by any
number of intermediate peers.  So how should we handle micropayments?
What are the entities involved in a transaction?  Let's examine some
possible strategies.

    [Sketch of 4 modes:
     end to end:
     Alice paying Bob through a long link of intermediate nodes]
     pairwise:
     each paying each other
     amortized:
     each paying each other of lessening amount
     all points:
     Alice paying each, make sure we show possibly necessary anonymity]    

   * <b>End-to-end model:</b>  

     Naively, we only consider the end-to-end transaction: Alice only
     sends Bob some form of payment.  This model works fine for
     operations which do not make use of intermediate nodes.  But if
     intermediate peers are involved, they lack any protection from
     attack.  Bob might even be fictitious; Alice can attack any number
     of intermediate peers by routing her queries through them, using up
     their bandwidth or wiping their Freenet-type data caches.  This
     problem is precisely our motivation for using micropayments!

   * <b>Pairwise model:</b>  

     Recognizing the problem of the end-to-end model, we decide to
     blindly throw micropayments in between all peers.  One long route
     can be modeled as a number of pairwise transactions.  This might
     appear to protect each recipient of payments, but is also
     fundamentally flawed.
     
     Using fungible micropayments, each peer earns one unit when from
     its predecessor, then spends one unit with its successor.  Assuming
     equal costs throughout the network, Alice is the only net debtor
     and Bob the only net creditor.  If Alice and Bob have the same
     operators, she's managed to extract work from the intermediate
     nodes without paying, a more-subtle DoS or flooding attack!

     Using non-fungible micropayments, Alice remains a net debtor, but
     so are all intermediate peers.  Alice makes use of greater
     computational resources (distributed or otherwise) to flood
     intermediate peers with POWs.  Being properly-behaving nodes, these
     peers attempt to make good on the micropayment exchange, and start
     churning out POWs for the next hop in the protocol...and
     churning...and churning.

   * <b>Amortized pairwise model:</b>

     From what we learned from the equivalent-cost pairwise model, we
     amortize Alice's cost throughout the network route by iteratively
     descreasing cost.  Say, Alice pays X with 4 units of micropayment,
     X pays Y with 3 units, Y pays Z with 2 units, who in turn pays Bob
     only 1 unit.
      
     We still lose in the case of non-fungible POWs.  First of all,
     Alice can still make use of greater wealth, economies of scale,
     distributed computing, etc. in order to attack intermediate nodes.
     Peers X, Y, and Z still need to churn along, possibly unable to
     afford such load.

     For fungible payments, this model appears more promising.
     Intermediate nodes end up as net creditors: their resources are
     paid for accordingly by Alice's initial lump-sum payment that
     propogates through the route, each hop taking a slice of the
     remaining micropayment pie.

     This model has another weakness from a security point-of-view: we
     leak information regarding the route-length.  We mentioned the
     Mixmaster mix-net at the beginning of this section; the system
     allows a sender to specify the number and identity of intermediate
     remailers, this number of hops and their corresponding identities
     are unknown to all other parties.  [XXX Footnote: We ignore the
     possibility of traffic analysis here, and assume that the user
     chooses more than one hop, such that no intermediate node can
     completely reconstruct the message route.]  Alice needs to specify
     a lump-sum micropayment pie to the first peer in her route; given a
     monotomically (or even linearly) decreasing cost function,
     intermediate peers can extrapolate how many hops are in the route,
     as well as their relative position.
     
     Furthermore, Alice may not know the route length.  Using Gnutella-
     or Freenet-type searching, Alice has no idea how many hops are
     necessary before the query reaches Bob.  Also, as her query
     branches out throughout the network, this could become
     prohibitively expensive.  (A well-ordered binary search tree
     requires visiting O(lg n) nodes, where n is the number of nodes;
     realistically, P2P systems will be nowhere as ordered.)

   * <b>All points model:</b>

     These previous problems lead us to suggest an all-points model.
     Alice pays each peer engaged in the protocol, intermediate and
     endpoint alike.  (We recognize and henceforth ignore the issue that
     Alice may not know which peers are involved, a la the searching
     problem.)

     This solution is ideal for fully-identified systems.  The cost of
     resource falls solely upon its instigating requestor.

     Anonymous systems add a few difficulties to using this model.
     First of all, we lose some ability to do interactive payment
     models.  For the forward-only Mixmaster mix-net, intermediate nodes
     can not tell Alice what client puzzle she should solve for them --
     only the first hop knows Alice's identity!  Therefore, payments
     must be of a non-iteractive variety.  To stop double-spending, the
     scheme must use either a centralized bank server model (e.g.,
     Chaumian ecash) or have recipient-specific information encoded in
     the payment (e.g., hash cash).  This recipient-specific information
     should further be hidden from view, so as to protect an
     eavesdropper from being able to piece together the route by looking
     at the micropayments.  Recipient-hiding cryptosystems [cite] help
     ensure that encryption of some data, the micropayment in this case,
     does not itself leak information as to whom the data is encrypted.

     In short, the all-points payment model -- while offering advantages
     over the prior three models -- presents its own difficulties.


So Alice has paid for some resource.  But did she get what she paid for?
This question deals with the problem of trust, discussed more fully in
chapter XXXXXXXX.  But given our discussion so far, there are a few
things to note.

In the case of data storage, Alice can query Bob at a later date for her
document, verify its checksum for accuracy, and be assured that Bob has
properly stored her document.  She is not assured that Bob has answered
all requests for that document, but she may be more convinced if Bob
can't determine the identity of the requestor, namely her.

Distributed computation can be checked for accuracy.  A problem may be
verified much easier than it may be computed (e.g., finding hash
collisions for bread pudding protocols.)  In other situations, we can
use special algorithms to check the validity of aggregate data much
faster than performing each calculation individually [cite 6.875
problem.].  [But as SETI@Home showed, verification can be a problem.
David, expand a line or two?  What is a "good" SETI algorithm....]

Verifying bandwidth allocation can be a trickier issue.  Bandwidth often
goes hand-in-hand with data storage: Bob hosts a web page for Alice, but
is he handling all the requesting traffic?  We can always sample
anonymously at random and gain some statistical assurance.  Still, the
Mixmaster problem returns to haunt us.  David Chaum, who proposed
mix-nets in 198XXXXX [cite], suggested that mix nodes publish the
outgoing batch of messages.  Alternatively, they could publish some
number per message, selected at random by Alice and known only to her.
This suggestion works well for the theoretical mix-net concept with a
public bulletin board; in Internet systems, it is difficult to ensure
that the mix node actually sends out these messages.

Micropayment schemes can help ensure accountability and resource
allocation in P2P systems.  But the solution requires careful design and
a consideration of all security problems: it's not a simple cut-n-paste
problem.  This section hopefully outlined many of the issues surrounding
micropayments in P2P systems, as well as the strengths and weaknesses of
alternate design decisions.

While payment schemes can be used in a variety of P2P situations --
systems in which peers are fully identified, to systems in which peers
are fully anonymous -- they do involve some risk.  Whenever Alice makes
an electronic payment, she accepts some risk that Bob will fulfill his
bargain.  When identities are known, we can rely on existing legal or
social mechanisms.  In fully anonymous systems, no such guarantee is
made, so Alice attempts to minimize her risk at any given time by making
small, incremental micropayments.  However, there is another possibility
for pseudonymous systems, or identified systems for which legal
mechanisms should only be used as a last resort: reputation schemes.  In
this next section, we consider the problem of reputation in greater
depth...