Section: Micropayment Schemes
-----------------------------
Accountability measures based on micropayments require that each party
offer something of value in an exchange. Consider Alice and Bob, both
servers in a peer-to-peer system. This system may deal with publishing
or file sharing; Alice may be inserting a document into the system and
want Bob to store it for her. Alternatively, the system may serve to
provide anonymous communication; Alice may wish Bob to anonymously forward
some email or real-time Internet protocol message for her. In either
case, Alice seeks some resource commodity -- storage and bandwidth
respectively -- from Bob. In exchange, Bob asks for a micropayment
from Alice to protect his resources from overuse. Throughout this
section, we're going to refer to both Alice (the payer, sender, or
customer in our system) and Bob (the payee, recipient, or vender).
There are two main flavors of micropayments schemes. First,
non-fungible schemes do not offer Bob any real redeemable value; the
goal is simply to slow Alice down when she requests resources from Bob.
She pays with a POW (proof of work), showing that she performed some
computationally difficult problem. With the second type of scheme --
fungible micropayments -- Bob receives a payment that holds some
intrinsic or redeemable value, commonly known as digital cash.
Both of these schemes may be used to protect against resource allocation
attacks. In a nutshell, communication denial of service attacks can be
prevented by charging for bandwidth: Bob may require payment for any use
of his bandwidth, or only charge if he detects a possible DoS attack.
Likewise, as Bob charges to store data, an attacker needs to pay some
(prohibitively) large amount to flood Bob's disk space. Obviously, if an
attacker is able to flood Bob with enough data to simply fill his pipe,
these techniques offer no protection.
The difference between micropayments and digital cash is a semantic one.
The label "micropayment" has generally been used to describe schemes
using small-value individuals payments. Usually, Alice will send a
micropayment for some small incremental use of a resource, rather than
single large digital cash "macropayment" for, say, a month's worth of
service. (We do describe some common designs for both.) We'll continue
to just use the commonly-accepted phrase "micropayment," without
formally differentiating between the two.
Digital cash may be either anonymous or identified. Anonymous schemes
do not reveal Alice's identity to Bob or the bank, while
identified spending schemes expose her information.
Other approaches can be taken: Alice remains anonymous to Bob but not
the bank; or anonymous to everybody yet traceable, i.e., a sequence of
purchases can be related, but not linked to an identity. But no matter
the flavour of payment -- non-fungible, fungible, anonymous, identified,
large, or small -- we want to ensure that a malicious user can't commit
forgery or spend the same coin more than once without getting
caught. [XXXX footnote: For small micropayments, we only need to stop
large-scale forgery. .] [this is a *critical point*. Don't leave it to the
footnote. Maybe it should be an entire subsection, describing systems
that realize this (eg recent discussion on mojonation-users). -rd]
Identified schemes are the digital analog of debit or credit cards.
Alice sends a "promise of payment" that will be honored by her bank or
financial institution. Forgery is not so much a problem here, as,
similar to a real debit card, the bank ensures that Alice has enough
funds in her account and transfers the specified amount to Bob.
Unfortunately, though, the bank has all knowledge of all of Alice's
transactions.
Anonymous schemes take a different approach, and are the digital analog
of real cash. The electronic coin itself is "worth" some dollar-amount.
If Alice loses the coin, she's lost the money. If Alice manages to pay
both Bob and Charlie with the same coin and not get caught, she's
successfully double-spent the coin. In the real world, government mints
use special paper, microprinting, holograms, and other technologies to
prevent forgery. On the other hand, duplication is easy in a digital
medium: just copy the bits! We need to find alternative methods
to prevent this type of fraud. Often, this involves looking up the coin in
a database of spent coins. Bob might have a currency unique to him, such
that the same coin couldn't be used to pay Charlie. Or, coins might be
payee-independent, and Bob would need to verify with the coin's issuing
"mint" that it has not already been spent with Charlie.
With this description of micropayments and digital cash in mind, let's
consider some various schemes.
Subsection: Non-Fungible Micropayments
--------------------------------------
Proofs of work were first advocated by Cynthia Dwork and Moni Naor in
1992 as ``pricing via processing'' to handle resource allocation
requests.
[Cynthia Dwork and Moni Naor. Pricing via processing or
combatting junk mail. In Ernest F. Brickell, editor, Advances in
Cryptology--CRYPTO '92, volume 740 of Lecture Notes in Computer
Science, pages 139-147. Springer-Verlag, 1993, 16-20 August 1992.]
They premise to require a user to compute a moderately hard, but not
intractable, computation problem to gain access to some resource.
Informally, the problem takes a long time to solve, but only a short
time to verify. Therefore, the prover Alice must perform a significantly
greater amount of computational work than the verifier Bob.
Dwork and Naor describe these pricing functions specifically to combat
electronic junk mail. Email senders must attach some non-interactive
proofs of work (POWs) which specify the recipient. These POWs serve as
a form of electronic poststamp. The destination is encoded with the
POW, so that the recipient can trivially determine if the POW is malformed.
Also, a simple lookup in a local database can be used to check whether
it has been spent before.
The postage may appear ``free'' to a private user, i.e., solving the
computational problem may take some time proportional to the time
needed to write the email. Individual users or mail distribution lists may
further specify access control lists (``frequest correspondent list'') such
that some messages do not require a POW. These techniques are useful
for social efficiency: if private correspondence instead cost some actual
usage free, users may be less likely to send email otherwise beneficial,
and the high bandwidth of the electronic medium may be underutilized.
On the other hand, unsolicited bulk mailings would need to spend a
large amount of computation cycles to generate the necessary POWs.
Dwork and Naor additionally introduced the idea of a POW with a trap door.
That is, a function that is moderately hard to compute without knowledge
of some secret, but easy to compute given this secret (the trap door).
Therefore, ``authorities'' could easily generate postage to sell for
pre-specified destinations.
Subsubsection: Junk Mail Prevention
-------------------------------------------------------------
The goal of "pricing via processing" -- combatting electronic junk mail
that has grown out-of-hand -- represents a mechanism for achieving
accountability within a distributed system. Junk mail, or spam, abuses
the un-metered nature of email and Internet bandwidth in general. The
most common form is commercial junk mail, in which the sender is
advertising or selling some product or service. Even if the email only
achieves an extremely small success rate, the sender is still
successful. Because of the un-metered nature of email, the marginal
cost of sending email is realistically zero (i.e., the cost per
transaction), and the sender can turn a profit.
Spam wastes both global and individual resources. On a broad scale,
it congests the Internet, wasting bandwidth and server CPU cycles. On
a more personal level, filtering and deleting spam can waste an
individual's time (which, collectively, can represent significant
person-hours). Users also may be faced with metered connection charges,
although recent years has seen a trend towards un-metered service and
"always-on" access.
Even though the motivations for junk mail might be economic, not
malicious, senders who engage in such behavoir play an adversarial role
in "hogging" the resources. As junk mail proves beneficial, users
remain motivated to misuse shared Internet resources. This is a clear
example of the tragedy of the commons.
Proper parameterization can balance this cost of sending email against
the email's expected value (the monetary benefit of success
multiplied by the probability of success.) Requiring micropayments can
decrease the cost-benefit ratio of unsolicited email, reducing spam and
providing economic incentive for more targeted marketing.
Internet-wide changes are not required to see a benefit from
micropayments via proofs-of-work. Indeed, individuals can adopt
personal requirements as receipients. More realistically, however,
individual, non-standard practices will merely reduce usability.
Although these individuals may no longer be targeted, junk mailers
would continue to fight over the commons.
While email misuse is an annoyance familiar to everybody, we will
consider several other resource attacks which may be prevented by
micropayment schemes. But first, a description of some other
micropayment schemes, so that we can later compare which ones are
better for certain scenarios.
Subsubsection: Other Types of Non-Fungible Micropayments
---------------------------------------------------------
Hash cash is an alternative micropayment scheme also based on proofs-
of-work. Designed by Adam Back in late 1997, hash cash is payment in
burnt computation by calculating k-bit partial hash collisions on
chosen texts.
[http://www.cypherspace.org/~adam/hashcash/]
Hash functions are familiar in two different areas of computing:
indexing for database storage and message digests for security
applications. We consider hash functions used for security, such as
SHA-1 (160-bit message digest), RIPEMD-160 (160-bit digest), and MD5
(128-bit digest). More formally, a hash function is a transformation
that takes a variable-size input x (the pre-image) and returns a
fixed-size output string h (the message digest). A cryptographically
strong hash function also is required to be one-way and collision-free,
i.e., it is computationally infeasible to find a single input which
produces a known output, or to find two inputs which produce the same
output. [XXX Note: can we remove a few lines here, as repeated in
Trust chapter?]
The work required to mint hash cash is based on the complexity of
finding these hash collisions: inputs which map to the same digest.
While finding full 160- or 128-bit collisions is hard, more easily we
can find k-bit partial collisions for small k. That is, we are looking
for two inputs which hash to digests that share k identical low-order
bits, the higher bits can differ. This becomes possible as the search
space for brute-forcing the problem becomes sufficiently small. (For
example, the probability of guessing a 17-bit collision is 2^{-17}; this
problem takes approximately 65,000 tries on average.)
Hash cash protects against double-spending by using individual
currencies. The hash cash pre-image found must collide with an ID or
name specified by the recipient. So, hash cash coins are specific to
recipients, who can immediately verify their validity against a local
spent-coin database.
Another micropayment scheme based on partial hash collisions was
suggested by researchers at RSA Labs. Proposed by Ari Juels and
John Brainard, client puzzles were introduced to provide a cryptographic
countermeasure against "connection depletion" attacks, whereby
connections requests are initiated with a server and left unresolved to
exhaust server resources. Legitimate requests therefore go unanswered,
and the resource appears to be "down."
[A. Juels and J. Brainard. Client Puzzles: A Cryptographic Defense
Against Connection Depletion Attacks. NDSS '99.]
When client puzzles are used, a server usually accepts connection
requests as normal. However, when it suspects that it is under
attack, marked by a significant rise in connection requests, it
responds to requests by issuing unique "client puzzles." This puzzle
is a hard cryptographic problem, based on the time and information
specific to the server and client request.
[http://www.rsasecurity.com/news/pr/000211.html]
Similar to the approach taken by hash cash, client puzzles require that
the client needs to find some k-bit partial hash collisions. Client
puzzles add a concept of sub-puzzles, which decrease the chance of
correct guessing an entire solution at random without actually
performing any calculations. The puzzle is made up of some number of
sub-puzzles, each comprised of a given message digest and (n-k) bits of
an n-bit input. To solve the puzzle, the client finds the missing
k-bits of each sub-puzzle. The use of these sub-puzzles greatly
decreases the probability that a client can correctly guess
puzzle solutions.
[XXX Footnote:
For example, the average work factor of a (k+3)-bit puzzle with
one sub-puzzle is the same as that of a puzzle with eight k-bit
sub-puzzles. However, the chance of correctly guessing the
former is 2^{-(k+3)}, while the latter is only 2^{-8k}.
XXX]
Subsubsection: Non-Parallelizable Work Functions
------------------------------------------------
Both of these hash-collision proofs-of-work are trivially
parallelizable. The size of the search-space of these problems
specifies their "hardness." With N machines, the problem can be solved
in 1/Nth the amount of time. Still, the accountability mechanisms and
goals we have already described might accept parallelizable problems.
After all, users still pay with the same expected amount of burnt CPU
cycles, whether a single machine burns M cycles, or N machines burn M
cycles collectively.
If the goal of non-fungible micropayments is to slow Alice down from
overusing Bob's resources, parallelizable schemes do not fit our
purposes. The server loses if we are using client puzzles to stop
connection depletion attacks and requesters can leverage parallel
computing to solve these "hard" puzzles in very short periods of time.
Let's actually try to make Alice wait for a fixed period between two
transactions, in order to better protect our resources. Consider a
"proof-of-time": we desire a client to spend some amount of time, as
opposed to work, to solve a given problem. An example is MIT's LCS35
Time Capsule Crypto-Puzzle. The time capsule, sealed in 1999, will be
opened after either 35 years or a supplied cryptographic problem is
solved, whichever comes first. The problem is designed to foil any
benefit of parallel or distributed computing, solvable only as quickly
as the fastest single processor available.
Time-lock puzzles, such as the LCS35 time capsule, were presented by Ron
Rivest, Adi Shamir, and David Wagner. These types of puzzles are
designed to be "intrinsically" or "inherently" sequential in nature.
The LCS35 problem used is to compute 2^{2^t} (mod n), where n is the
product of two large primes p*q, and t sets the difficulty of the
puzzle. This puzzle can be solved only by performing t successive
squares modulo n. There is no known way to speed-up this calculation
without knowing the factorization of n.
[Ronald L. Rivest, Adi Shamir, and David A. Wagner. Time-lock puzzles
and timed-release Crypto. Feb 1996.].
It's worth noting in passing that the previous construction is not
*proven* to be non-parallelizable. Its security rests on the fact that we
see no way to make perform the repeated modular squaring in parallel. This
problem is tied up with the "P vs. NC" problem in
computational complexity theory and is outside the scope of this chapter.
Similar to the better known "P vs. NP" problems, which concerns the
question "which problems are easy?" the P vs. NC problem asks "which
problems are parallelizable?"
[XXX Footnote:
Historical note: NC stands for Nick's Class, named after Nicholas
Pippenger, one of the first researchers to investigate such problems.]
We refer the reader to
[ Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo.
Limits to Parallel Computation: P-Completeness Theory.
Oxford University Press 1995 ]
for more detail.
Subsection: Fungible Micropayments
----------------------------------
All of the micropayment schemes we have previously described are
non-fungible: while Alice pays Bob for resource use with some coin that
represents a proof-of-work, he cannot redeem this token for something of
value to him. While this micropayment helps prevent DoS and flooding
attacks, there's no measure of "wealth" in the system. Bob has no
economic incentive to engage in this exchange.
The question also becomes one of economy of scale: how much the variable
cost of the scheme (generating POWs) is a function of its size. If the
cost per transaction actually declines with the size of the scheme, the
effect is dramatic. The cost charged for resource allocation may be
sufficiently large for individuals, yet virtually zero for large
organizations. One possible side effect is that larger and larger
computers may be used to solve larger and larger pointless problems,
in a hyper-inflationary race to generate POWs.
What this means for peer-to-peer systems, if an economy of scale exists,
is that rich groups would be better able to control the system. If they
wish to restrict access or content, these groups could utilize superior
resources to attack the system, burning "cheaper" CPU cycles in parallel
to generate the POWs necessary to gain access to the system's resources.
If a fixed cost is associated with all resources, however, organizations
cannot take advantage of economies of scale.
Secondly, non-fungible micropayments are less-suited for congestion
management of long-term resources. We have largely motivated POWs --
hashcash, client puzzles, or other computational problems -- in terms of
"slowing down" the rate at which an adversary can use up a peer's
bandwidth, usually in the form of a query flooding attack. Without vast
computational power, an attacker cannot eat up all resources. Data
flooding presents a different problem, however, in which an attacker
seeks to take up all available storage space. If the system is built
for long-term storage, the effects of data flooding can be cumulative.
(Without loss of generality, we can consider this problem the same for
any resources allocated for long-term periods.) If micropayments only
cost CPU cycles and cannot be redeemed for something of value, an
attacker can slowly nibble at resources, requesting a Meg now and then,
until she controls a large percentage of the total. Without payments
having an intrinsic value, the attacker is better able to afford the
cost (e.g., in the form of idle CPU cycles). Furthermore, the attacked
peer is unable to use these payments in exchange for other peers'
resources, or alternatively to purchase more resources.
Enter redeemable payments. This compensation motivates users to donate
resources, fixes the cost for resources more stably, and provides a
slightly different flavor of protection from resource attack.
Subsubsection: Freeloading
--------------------------
The history of the Internet records a number of users who have freely
donated resources. The hacker ethos and free software movement can be
relied on to provide resources to an extent. Johan Helsingius ran the
initial "anonymous" remailer -- anon.penet.fi -- for its own sake. The
cypherpunk (type I) and Mixmaster (type II) remailers for anonymous
email are run and maintained for free from around the globe. Processing
for SETI@Home and distributed.net is also performed without
compensation, other than the possibility of fame for finding an alien
signature or cracking a key.
Unfortunately, not everybody donates equally. Although a P2P system may
yield some overall benefit to an individual, it is also tempting for a
user to "let somebody else pay for it" and just reap the rewards.
Peer-to-peer systems may combat this effect by incorporating coercive
measures into their design or deployment, ensuring that users actually
donate resources. This is not a trivial problem. Napster provides a
good example: users only need to "connect" to Napster when actually
searching for mp3 files, otherwise they can remain offline.
Furthermore, users are not forced to publicly share files, although
downloaded files are placed in a public directory by default. A fairly
recent analysis of Gnutella traffic shows a similar amount of free
riding in the system.
[http://www.parc.xerox.com/istl/groups/iea/papers/gnutella/FreeRidingA.html]
Upwards of 70% of Gnutella users shared no files, and 90% of the users
answered no queries. Free Haven tackles this problem by attempting to
ensure that users donate proportional amounts of resources as they use.
The system relies on accountability via reputation, which we discuss
later. Mojo Nation, on the other hand, pays users "Mojo" -- the
system's private digital currency -- for donated resources.
Subsubsection: Fungible payments for accountability
----------------------------------------------------
Wealth gained through private currency exchange -- such as "Mojo" -- can
be leveraged for other system resources. Fungible micropayments are not
used solely, or arguably largely, for economic incentives. Instead,
they act as an accountability measure. Peers can't freeload in the
system, as they can only earn wealth by making their own resources
available (or by purchasing resource token via some other means).
This equivalency measure even better protects a system from attack:
an adversary needs to donate a proportional amount of resources that
she seeks to tie up.
Even payments redeemable for real-world currencies are useful to protect
against resource misuse. Given a cost associated to resource
allocation, attacking a system costs real dollars. The average
script-kiddie downloading DoS scripts from RootShell.com or trying to
flood the system is unlikely to be able to afford a successful attack,
"renting" sufficient resources to restrict others' access or the
system's content. Distributed attacks still cost the same number of
micropayments, using many computers or only one. It is arguable that
real currency favor richer organizations, who may be the only ones
willing and able to fund a successful attack against the system.
However, they still need to spend some fixed dollar amount, and the
nature of real currencies provides a partial defense against continued
attack. A user can purchase additional physical disk space (or
bandwidth) from this money earned, for which the price drops weekly.
Therefore, the cost of successfully attacking the system increases with
time.
Business arrangements, not technology, link digital cash to real-world
currencies: transactions can be visualized as foreign-currency exchange,
as we need to convert an amount of money to digital cash before we spend
it. The Mark Twain Bank "issued" DigiCash eCash in the U.S. in the
mid-1990s, joined by other banks in Switzerland, Germany, Austria,
Finland, Norway, Australia, and Japan.
[http://www.canada.cnet.com/news/0-1003-200-332852.html] ECash can as
easily be used for private currencies lacking real-world counterparts;
indeed, "Mojo" is based on eCash technology (although without, in
default form, the blinding operations which provide anonymity.) The
digital cash schemes we describe, therefore, can be used for both
private and real-world currencies.
Subsubsection: Micropayment Digital Cash Schemes
------------------------------------------------
Ronald Rivest and Adi Shamir introduced two simple micropayment schemes,
PayWord and Micromint, in 1996. PayWord is a credit-based scheme, based
on chains of paywords (hash values), while MicroMint represents coins by
k-way hash-function collisions. Both of these schemes follow the
light-weight philosophy of micropayments: nickles and dimes don't
matter. If a user loses a payment, or is able to forge a few payments,
we can ignore such trivialities. Security mechanisms are not as strong,
nor as expensive, as full macropayment digital cash schemes, which we
shall discuss later. At a rough estimate, hashing is about 100 times
faster than RSA signature verification, and about 10,000 times faster
than RSA signature generation.
[R. Rivest and A. Shamir. PayWord and MicroMint: Two simple
micropayment schemes. Lecture Notes in Computer Science 1189,
Proc. Security Protocols Workshop, Cambridge, Springer Verlag (1997). 69-87.]
PayWord is designed for applications in which users engage in many
repetitive micropayment transactions. Some examples are non-free web sites
maintained by some vender or pay-per-minute online games or movies. It
seeks to minimize communication -- mainly online verification -- with
brokers (better known as the "banks" in many digital cash schemes).
Alice establishes an account with a broker and is issued a digital
certificate. When she communicates with vender Bob for the first time
each day, she computes and commits to a new payword chain w_1, w_2, ...,
w_n. This chain is created by choosing some random w_n, and calculating
w_i = hash(w_{i+1}) from 0..n-1. The commitment is the root w_0 of the
chain; a micropayment is (w_i, i), where w_i is the next payword in the
chain in ascending order. Just knowing w_0, vender Bob can't compute
any paywords, but can easily verify the i-th payment knowing only
w_{i-1}. Bob reports to the broker only once at the end of the day,
with the last (highest-indexed) micropayment and the corresponding
commitment received that day. The broker adjusts accounts accordingly.
As payword chains are both user- and vender-specific, the vender can
immediately determine if the user attempts to double-spend a payword.
Unfortunately, however, PayWord does not provide any transaction
anonymity. As this is a credit-based system, the broker knows that
Alice paid Bob.
[describe the use of payword in any (even hypothetical) p2p systems?
i want this tied into my interests sooner -rd]
MicroMint takes the different approach of providing less security, but
doing so at a very low cost for unrelated low-value payments. Earlier,
we described k-bit collisions, in which we found two inputs which mapped
to the same lowest k-bits in the digest. MicroMint coins are
represented instead by full collisions: all the bits of the digests have to
be identical. A k-way collision is a set of distinct inputs (x_1, x_2,
..., x_k) which all map to the same digests, hash(x_1) = hash(x_2) =
... = hash(x_k). These collisions are obviously hard to find, as hash
functions are specifically designed to be collision-free!
[XXX Footnote: We need to examine approximately 2^{(n(k-1)/k)} inputs to
find a k-way collision, essentially the "birthday paradox", see [Rivest,
Shamir paper]]
The security in MicroMint rests in an economy of scale: minting individual
coins is difficult, yet once some threshold of calculations have been
performed, coins can be minted with accelerated ease. Therefore, the
broker can therefore cost-effectively mint coins, while small-scale
forgers can only produce coins at a cost exceeding their value.
Consider a balls and bins metaphor. A broker throws a ball blindly; it
lands in some bin. When an individual bin is full, these balls are
removed and form a Micromint coin. The "ball" is the input x, the bin
it lands in is indexed by hash(x). The broker will continue this
process ad nauseam. K balls in a bin represent a k-way hash collision.
The number of bins is large, though: 2^n, where n is the digest length.
Rivest and Shamir further describe methods to decrease the amount of
storage required to mint coins, as well as techniques to increase the
difficulty of large-scale forgery.
[can you list some p2p situations where this might be useful? -rd]
[
* micromint works well with bread pudding. also the cost of
verification is extremely low. this makes it ideal for embedded p2p
applications. also embedded apps are the only place where we care about
speed and verification cost any more. "heavyweight" signature schemes
aren't so heavy in the face of 800Mhz P3s!
* imagine your Rio as a mobile gnutella unit.
* mobile mix-nets which dynamically form ad hoc networks
based on who can pay.
* heck. add "mobile", "embedded" and "ad hoc" to any p2p
application. imagine Mojo-enabled tie clips which make you
money at cocktail parties by routing instructions to the
guy with the hors d'oeurves.
-dm]
Similar to Payword, the MicroMint broker knows both Alice, to whom the
coins are issued, and vender Bob. This system is therefore not
anonymous, allowing the broker to catch Alice if she attempts to
double-spend a coin.
Subsubsection: Making money off of others' work
------------------------------------------------
So how to make money off of donated resources, without requiring a
system-wide digital cash scheme to be in place? Make some bread pudding
and sell it at the local bakery.
Markus Jackobsson and Ari Juels introduced the idea of a bread
pudding protocol in 1999. Bread pudding is a dish that originated
with the purpose of reusing stale bread. In a similar spirit, this
protocol defines a POW such that the computational effort may be reused
for a separate, useful, and verifiably correct computation. This
computation is not restricted to any specific problem, although the
authors further specify a simple bread pudding protocol for minting
MicroMint coins.
[Markus Jackobsson, Ari Juels. Proofs and Work and Bread Pudding
Protocols. In B. Preneel, ed., Communications and Multimedia Security,
pages 258-272, Kluwer Academic Publishers, 1999.]
They provide a variant on the original minting scheme, although the
computational cost of the two remains the same. This variant, however,
allows the problem of finding a single, valid coin to be distributed as
a POW. The fundamental idea is to make clients solve partial hash
collisions, similar to the concept of hash cash, yet this computation is
useful only to the mint, who holds some necessary secret. With enough
of these POWs, the minter can offload the majority of computations
necessary to minting a coin.
Effectively, Bob is asking Alice to compute part of a micromint coin,
but this partial coin is only useful when combined with thousands or
millions of other similar computations. Bob collects all of these
computations and combines them into Micromint coins.
Without requiring system-wide fungible
digital cash, Bob can reuse others' computation work for computations
"valuable" only to him. This provides both extensibility and
payment-scheme-independence for peers in the same P2P system.
Subsubsection: Anonymous Macropayment Digital Cash Schemes
----------------------------------------------------------
Up until now, we have only described micropayment digital cash schemes,
where the value of each coin or token is fairly small. Forgery only
makes sense if it can be performed in large-scale; we aren't concerned
with "nickles and dimes." The protocols also have not offered
multi-party security and privacy of payments.
The "macropayment" digital cash schemes we about to discuss offer
stronger security and anonymity. However, these protections come at a
cost. The computational and size requirements of such digital cash is
much greater. In cryptographic literature, micropayment are usually
considered extremely small (such as $0.01), and only use hash functions
and other very efficient primitives. These macropayment digital cash
schemes use public-key operations, such as exponentiation, which are
much more expensive (i.e., slow). While generally, they are not
efficient enough for very small transactions, we describe such schemes
for completeness. When we later develop the concept of reputation
systems, we can make larger and larger transactions without assuming
incommensurate risk.
Pioneering work on the theoretical foundations of anonymous digital cash
was carried out by David Chaum in the early 1980s.
[D. Chaum, Blind signatures for untraceable payments. Advances in
Cryptology - Crypto '82, Springer-Verlag (1983), 199-203)]
[D. Chaum, Security without identification: transaction systems to make
big brother obsolete, Communications of the ACM 28 (10) (1985),
1030-1044.]
[D. Chaum, A. Fiat, M. Naor. "Untraceable Electronic Cash,"
Advances in Cryptology -- Proceedings of Crypto '88, Lecture Notes
in Computer Science, no. 403, Springer-Verlag, pp. 319-327.]
The electronic cash system developed is based on an extension of digital
signatures, called blind signatures. A digital signature is a way to
authenticate a message as belonging to a person, built upon existing
Public Key Infrastructure (PKI). See the chapter on Trust for a greater
description of signatures and PKI. A blind signature scheme
allows a person to get a message signed by another party, while not
revealing the message's contents to that party.
Alice creates some number (the proto-coin) and multiplies it by a secret
random number. She sends this resulting proto-coin -- blinded by the
random number -- to the bank. The bank checks that she has a positive
balance, and signs the proto-coin "this is a valid coin" with a
denomination-specific private key. The bank returns this to Alice, and
subtracts the corresponding amount from Alice's bank account. Alice
then divides out the random number multiplier and finds herself with a
properly minted coin, carrying a valid signature from the bank. As an
analogy, Alice slips a piece of paper into a carbon-lined envelope,
representing the blinded proto-coin. The banks only writes its
signature across the envelope, which imprints a carbon signature onto
the inside paper. Alice removes the paper and is left with a valid
coin.
Alice can then spend this coin with Bob. Before accepting it, Bob needs
to check with the issuing bank that the coin hasn't already been spent,
a process of online verification. Afterwards, Bob can deposit the coin
with the bank, which has no record to whom that coin was issued. It
only saw the blinded proto-coin, not the underlying "serial" number.
[XXX Footnote: cut this?
A bit of math. Chaum demonstrated a blind signature scheme implementation
using RSA signatures:
Alice has some message m she wishes signed. Bob has a public key (e,n)
and private key (d,n). Alice generates some random r and sends x =
(r^e m) mod n to Bob. The value x is "blinded" by r. Bob computes and
returns t = x^d mod n. Alice can obtain the true signature s on m by
computing:
s = r^{-1} t mod n = r^{-1} (r^e m)^d mod n
= r^{-1} r^{ed} m^d mod n r^{-1} r m^d mod n
= m^d mod n
End FOOTNOTE]
This digital cash system is both anonymous and untraceable. Its
disadvantage, however, is that coins need to be verified online for
double-spending. This has obvious performance effects. Chaum holds patents
on his system, and founded DigiCash in 1990 to implement these
technologies.
Stefan Brands proposed an alternative digital cash scheme in 1993, which
forms the core of a system implemented and tested by CAFE, a European
project of both academic and commercial members. His patents are
currently held by the Montreal-based privacy company Zero-Knowledge
Systems, Inc. His digital cash scheme allows offline checking of
double-spending for fraud-tracing, with obvious performance benefits
compared to online verification. It is also well-suited for
incorporation into smartcards, and the underlying technology provides an
entire framework for privacy-protecting credential systems.
[Stefan Brands. An efficient off-line electronic cash system based on
the representation problem. Centrum voor Wiskunde en Informatica (CWI),
Technical report CS-R9323, March 1993. http://www.xs4all.nl/~brands/]
[Stefan Brands. Rethinking Public Key Infrastructures and Digital
Certificates; Building in Privacy. Cambridge: MIT Press, 2000.]
Brands' scheme makes use of a blind issuing protocol to generate a
"secret key certificate" for Alice. In the digital cash context, this
certificate is a valid coin, represented by a (secret key, public key,
digital signature) triple certified by the bank. A key aspect of this
protocol is that the bank knows -- and encodes attributes into --
part of Alice's secret key, but has no idea what the
corresponding public key and certificate look like (aside that they are
consistent with the known part of the secret key.) At the end of the
issuing protocol, somewhat similar to the techniques described above,
Alice performs some mathematical operations to generate a valid coin.
The fraud-tracing capability arises from a different payment protocol.
Instead of actually giving her coin to the vender Bob -- indeed, the
coin contains Alice's secret key -- she proves interactively to Bob that
she is the proper holder of that coin (i.e., knows the secret key
associated with the public key), without actually disclosing its
contents. This type of payment, a signed proof of knowledge transcript,
is a fundamental shift from the Chaumian ecash model, in which the coin
is "immutable," being merely a bit string.
If Alice only spends the coin once, the bank can gain no information as
to her identity (i.e., the coin is blinded for one "show"). After all,
during the issuing protocol, the bank only saw part of Alice's secret
key, not the public key used to verify Alice's payment transcript
signature. Yet, if Alice double-spends the coin, the bank can use it to
extract her identity!
Imagine the analogy of a Cartesian plane. The first random number
challenge used during payment provides one point (x0,y0) on this plane.
An infinite number of lines can pass through this one point. If Alice
uses the same coin to pay Charlie, a different random number is used.
Now we know a second (x1,y1) point, and two points uniquely define a
line. Alice's identity is now exposed, represented by this line.
This scheme -- useful for both digital cash and credentials -- can be
used to encode other useful information, such as negotiable attributes
which may be exposed during payment, or high-value secrets to prevent
lending. This technology is much more complicated than Chaum's blinding
and electronic cash systems, and a more in-depth discussion lies outside
the scope of this chapter. Brands' new book
[ Brands, S. _Rethinking Public Key Infrastructures and Digital
Certificates: Building in Privacy_ MIT Press Cambridge, MA 2000]
describes his technologies in depth.
[p2p applications where this could be used? -rd
talk about negotiable attributes. talk about high-value secrets]
[ talk about revealing credentials without identity. I can create a nym
and build up a reputation using it. then have the key certified by
someone using Brand's technologies. This allows me to transfer some
of the trust I built up by way of that credential to a _new_ nym.
So in essence I can pick and choose what I want to present at any
given point. this is very powerful and it's also hard to reconcile
with a reputation system. Here's why:
One of the major ways we make pseudospoofing ineffective is to make
new identities worth zilch. This is what happens in mailing lists
and is codified in the advogato trust metric. There's a long time
between creating a new identity and being able to use the identity
for anything useful. But if you can use some of the trust built
up by the old identity for the new one, and leave behind the negative
karma built up by the old identity -- why not pseudospoof? why not
create two or three different people? or cheat someone and then
reinvent yourself? -dm]
Subsection: The use and effectiveness of micropayments
in peer-to-peer systems
-------------------------------------------------------
So far, we have spent quite a bit of time describing various
micropayment and digital cash schemes. Our discussion is not meant as
exhaustive, yet it provides some examples of various cryptographic
primitives and technologies used for electronic cash: public-key
encryption, hash functions, digital signatures, certificates, blinding
functions, proofs-of-knowledge, and different one-way and trap-door
problems based on complexity theory. The list reads like a
cryptographic cookbook. Indeed, the theoretical foundations of digital
cash -- and the design of systems -- have been actively researched and
developed over the past two decades.
Only in the past few years, however, have we begun to see the real-world
application of micropayments and digital cash, spurred by the growth of
the Internet into a ubiquitous platform for connectivity, collaboration,
and even commerce. Electronic cash surely has a place in future
society. But, its place is not yet secured. We are not going to try to
predict either its ease of adoption or market capture: there are widely
varying economic, social, and institutional arguments about its eventual
role.
Instead, we will motivate the use of micropayments for peer-to-peer
systems: when micropayments are useful, with what issues P2P systems should
concern themselves, when certain digital cash technologies are better
than others, how to tell whether the micropayments are working, and how
to achieve stronger or weaker protections.
Subsubsection: Motivation
-------------------------
The need for resource protection in P2P systems is an important one.
Even if an administrator can partition his hard drive, or restrict access
to his bandwidth or CPU cycles to hours during which it is not locally in
use, an adversary can destroy the utility of his resources to the P2P system
at large if they are not locally protected. After all, the
capabilities of a P2P system are the aggregate of all its peers.
In this section, we have described the design of micropayment schemes,
as well as some possible application. There is no cookie-cutter
approach to matching resource protection requirements with micropayment
policies. Various schemes are useful to attract different user
behaviors and security levels.
The basic premise of micropayments is to make small, incremental
payments, so that peers can make exchanges without prior knowledge of
each other. At any time, a peer only floats a small amount of risk for
a single exchange. If both peers are satisfied with the result, they
can continue with successive exchanges.
To complete the picture, we have also presented some designs of digital cash
macropayments, where coin values may be greater, resulting in high
risks. In the next section, we describe how reputation systems can
reduce this risk and empower pseudonymous peer-to-peer commerce on the
Internet.
Subsubsection: Application-layer effectiveness to
distributed attack
--------------------------------------------------
Micropayments provide an application-layer security mechanism for
resource management. To gain access, a remote peer needs to offer some
payment specified by the administrator's security policy. As such,
micropayments are not as susceptible to attacks which attempt to surpass
network-layer mechanisms by distributed denial-of-service (DDoS)
attacks.
A network-layer defense against a common form of DoS attack is what is
known as SYN cookies, which are used to prevent SYN flooding. SYN flooding
is a connection depletion attack whereby half-open connections are
established easily via IP-spoofing. We alluded to this problem in our
discussion of client puzzles. An adversary sends SYN messages -- the
first message of the three-part TCP connection "handshake" -- to a
victim system. These messages appear legitimate, but in fact refer to
a spoofed system unable to respond with the expected SYN-ACK message.
This means that the final ACK message will never be sent back to the
victim.
[XXX 3-stage TCP handshake picture?]
Normally, a machine will only keep track of pending SYN connections
and drop other incoming requests, effective denying service to other,
legitimate users. Machines with SYN cookies remove this queue and only
keep track of complete SYN-ACK handshakes. This prevents adversaries
from IP-spoofing connection requests, as the spoofed machine would not
respond to SYN-ACK that the IP-source cannot be spoofed as easily, else
that spoofed machine would not complete the handshake.
In a DDoS attack, an adversary gains control over a the large number of
unprotected machines world-wide and launches a simultaneous attack on a
victim. Even if SYN cookies are preventing SYN flooding, if 100
machines each establish 1000 connections with the victim, all of its
possible 65536 ports are tied up.
The vulnerability of systems to DDoS attacks was made patently obvious
in February, 2000, when many large web servers were brought down.
Attacked servers included Yahoo, Buy.com, ZDNet, eBay, CNN.com, and
E-Trade.com. MIT network-security recently found evidence of adversaries
testing the new Trinity-3 DDoS attack on its network.
P2P systems have similar weaknesses. Adversaries can flood storage
space or congest network bandwidth. Publius attempts to control damage
from flooding by limiting file submission size to 100K (an implementation
detail of their system trial), but N submissions of 100K each eats up
as much space as one N*100K submission. Furthermore, as many P2P systems
are designed to be pseudonymous or anonymous, they might not even
provide protection from spoofing-type attacks.
Micropayments can prevent distributed attacks. No matter the
number or identity of servers engaged in an attack, the adversaries still
need to provide micropayments to cover resource usage. We've already
discussed some tradeoffs between parallelizable POWs and proofs-of-time
to handle distributed computation.
Important to note is that payment verification itself can be a DoS
target: an attacker can flood a system with cheaply-minted counterfeit
coins, eating up computational resources through verification checking
alone. This problem largely depends on the computational complexity of
coin verification. Many of the systems we describe -- hashcash, client
puzzles, MicroMint, Payword -- can very quickly verify coins, with only
a single or a few hash operations. [XXX Footnote: Our Pentium-III 800 Mhz
machine tested as performing approximately 312,000 hashes per second.]
Public-key operations, such as modular exponentiation, can be significantly
more expensive.
Subsubsection: Identity-based payment policies
----------------------------------------------
When designing a policy for accepting micropayments, peers might wish to
charge a varying amount to peers based on identity, e.g., for local
users, for specified "friends", for users from academic or
non-commercial subnets, for users within specified jurisdictional areas.
Peer-to-peer naming schemes can be wildly different from traditional,
heirarchical DNS namespaces. ICQ uses a unique "ICQ number" which is
independent of IP-address (although this number is merely mapped to
IP-address in a centralized name server; this design is not
anonymous.) Pseudonymous mail systems, like Zero-Knowledge System's
Freedom mail system, use reply-blocks to traverse the mix-net to the actual
destination: only the pseudonym alias is known. Real-time communication
systems like the Freedom network, Crowds, and JANUS/rewebber also
protect the privacy of reply paths. Forward-only anonymous remailers
have no concept of the sender's identity. On the other hand, the Jabber
protocol uses a DNS-type naming schemes, in which messages are sent to
username@servername. [XXX true???] This comes at the cost of
anonymity, though, if servers wish to limit subscription to their Jabber
services based on real-world information.
There are two main issues of note with identity-driven micropayments.
First, systems which expose user identities still need to protect
against spoofing and other practical security weaknesses. We can look
to SSL and other cryptographic authentication mechanisms based on
public-key cryptography, given a PKI or suitable certificate authority
(CA) hierarchy.
Second, however, these same techniques are not as applicable for
privacy-protecting systems. Real-world information is not linked to
the naming scheme which pseudonymously identifies peers in the system.
This issue of identity management and decision-making will be considered
at length in our next section on reputation brokering.
Subsubsection: Economic analysis of micropayment design
-------------------------------------------------------
There are a number of design differences between the various
micropayment schemes. Some charge a non-fungible fee -- CPU cycles --
some charge a fungible fee, while still others charge variable fees
based on time or congestion -- client puzzles during possible resource
attacks.
The overall design of a P2P system with micropayments should not
consider merely the technical and implentation issues of different
micropayment schemes, but also the overall economic impact of the entire
system. Different micropayment schemes have different economic
implications. To analyze the economic impact of an micropayment scheme
in any system, we have to consider the well-being of all economic agents
participating in and affected by the system. Three general groups come
to mind in the case of a P2P system: the owner of the system, the
participants, and the rest of society.
How does an micropayment scheme impact these three agents? Participants
face direct benefits and costs, the owner can collect fees or
commissions to cover the fixed cost of design and/or the variable costs
of operation, and the rest of society can benefit indirectly by
synergies made possible by the system, knowledge spillovers, freed-up
alternative common resources, etc. To simplify our discussion, we
assume that whatever benefits participants also benefits society.
Furthermore, we can realistically assume a competitive market, such that
the owner is probably best off serving the participants as well as
possible. Therefore, we focus on the participant cost-benefit analysis.
A classic case of economic analysis of bridge tolls serves as a good
analogy for a P2P system. In 1844, the French engineer Jules Dupuit
reached a major breakthrough in economic theory by arguing the following
way: the economically efficient toll on an uncongested bridge is zero,
because the extra cost from one more person crossing the bridge is zero.
Although bridge building and maintenance is not free -- it costs some
money to the owner -- it is socially inefficient to extract this money
through some positive toll. Society as a whole is worse off because
some people choose not to cross due to this toll, even though their
crossing would cost the owner nothing, and they would not interfere with
anyone else's crossing (the uncongested assumption). Therefore,
everyone should be allowed to cross the bridge for free, and the society
should compensate the bridge-builder through a lump-sum payment.
[Arsene Jules Etienne Dupuit, (1804-66), "On Tolls and Transport
Charges", 1842, Annales des Ponts et Chaussees (trans. 1962, IEP).]
This bridge example serves as a good analogy to a P2P system with
micropayments. Congestion or a similar interference makes the extra
cost of one more person participating non-zero. Tolls should only be
extracted in order to limit congestion and regulate access to people who
value crossing the most. Similarly, resource allocation to limit
congestion is the only justifiable reason for micropayments in a P2P
system, given the above economic argument. Indeed, excessive
micropayments can dissuade users from using the system. Users might not
access certain content, engage in e-commerce, or anonymously publish
information that exposes nefarious corporate behavior, all of which lead
to societal inefficiencies.
This analysis highlights the ability of micropayments to prevent attacks
and adds the implied ability to manage congestion. Congestion
management is a large research area in networking. Many gateways use
random early detection (RED) to proactively drop some arriving data
packets at random before the queue fills up (helping limit congestion in
light of the TCP best-effort design, as an attempt to communicate the
congestion to the cause merely adds to the congestion.) Micropayments
can play a useful complementary role in such systems by helping peers
prioritize packets, whether we consider network packets through system
pipes, or access to storage space. Users who really want access will
pay accordingly, although this clearly leads to wealth-favored access
patterns. (For true fairness, this issue should be balanced against
overall social efficiency-gains.) We can further imagine a hybrid of
these two models, in which reputation further plays a role in
prioritizing resource allocation.
Most economic research relevant for micropayments has focused owner-side
strategies for maximizing profit. AT&T researchers compared flat-fee
vs. pay-per-use fee methods which assumed the owner is a monopolist, and
concluded that more revenues are generated with a flat-fee model.
Similar research at MIT and NYU independently concluded that content
bundling and fixed-fees can generate greater profits per good.
[Competitive pricing of information goods: Subscription pricing versus
pay-per-use, P. C. Fishburn and A. M. Odlyzko, Economic Theory 13 (1999),
447-470. http://www.research.att.com/~amo/doc/competitive.pricing.ps]
[Y. Bakos and E. Brynjolfsson. Bundling Information Goods: Pricing,
Profits, and Efficiency. Management Science, (December 1999).
www.stern.nyu.edu/~bakos/big.pdf]
We believe that our focus on costs and benefits to participants is more
suited to the reality of the P2P market, for several reasons. First,
owners do not enjoy the luxury of dictacting exchange terms, thanks to
competition. Second, non-fungible micropayments do not generate revenues
for the owner; it is not always worthwhile to even consider
owner-benefit. Third, we expect that a large amount of resources in P2P
systems will be donated by users: people will donate otherwise unused
CPU cycles to SETI@Home calculations, unused bandwidth to forward
Mixmaster anonymous email, unused storage for Free Haven data shares.
For these situations, the sole role of micropayments is to achieve
optimal resource allocation among participants. In order words,
micropayments in a P2P system should only be used to prevent congestion,
referring to both bandwidth and storage limitations.
Subsubsection: Moderating security levels: an accountability slider
---------------------------------------------------------------------
Both prohibitive cost and ill-equipped protection measures can hinder
the growth of a highly-used, highly-available, stable P2P system. As we
have described, prohibitive cost decreases usage and limits the
aggregate resources available from peers. Too-weak protectionary
mechanisms may not prevent denial-of-service attacks or resource
flooding. In addition, weak accountability measures encourage
freeloading.
If a P2P system only wishes to prevent query-flooding (bandwidth)
attacks, the congestion management approach taken by client puzzles
-- and useable with any form of micropayment -- answers the problem.
Query-flooding attacks are transient; once the adversary stops
actively attacking the system, the bandwidth is readably available
to others.
As we have suggested, other forms of congestion are cumulative, such
as those related to storage space. Free Haven seeks "document permanence,"
whereby peers promise to store data for a given time period (although the
Free Haven trading protocol seeks to keep this system dynamic, see its
related chapter.) If we wait until the system is already full before
charging micropayments, we've already lost our chance to adequately
protect against congestion.
This is the freeloading problem: we wish to prevent users from
parasitically congesting the system, without offering something of value
in return, which leads to social inefficiencies as discussed.
Furthermore, an adversary can attempt to flood the system early to fill
up all available space. Therefore, for systems in which resource
pressures accue cumulatively, micropayments should always be required.
Free Haven's answer is to require that peers offer storage space
proportional to that which they take up. (Even though micropayments are
not used, the idea of payment by equivalent resources is similar.)
The alternative to this design is the caching approach taken by systems
such as Freenet. Old data is dropped as newer, more "popular" data
arrives. This approach does not remove the resource allocation problem,
however, it only changes the issue. First, flooding the system can
flush nearby caches of undesirable data, yet hopefully should not
congest the resources of more "distant" peers. Second, freeloading is
not as much a concern, for peers are not changed with offering
best-effort availability to documents. However, if many peers rely on
only a few to store data, only the *most* popular data remains. Social
inefficiencies again develop if would-be popular data is dropped as the
storage is simply insufficient to handle the requirements of freeloading
peers. Recognize technical problems as well: excessive freeloading does
affect scalability due to network congestion.
Always charging for resources can prevent both freeloading and attacks.
On the other hand, excessive cost is disadvantageous as well.
There is a balance. Consider an accountability slider: peers
negotiate how much payment is required for a resource, within a model
specified by the overall P2P system. Using only a micropayment model,
systems like Free Haven or Publius may not have much leeway. Others,
like Freenet, Gnutella, or Jabber, have notably more. When we later add
the concept of reputation, this accounting process becomes further
flexible.
This negotiation -- the slider a system can use to achieve more or less
accountability between peers -- is readily apparent with the various
micropayment systems described:
* Hashcash: Partial hashes can be made arbitrarily expensive
to compute, by choosing the desired number of bits of
collision, denoted by k. Even as k changes, they can be
verified almost instantly.
* Client puzzles: The work-factor of these puzzles is also
based on the number of bit-collisions. The number of
sub-puzzles can also be increased to limit the possibility of
random guessing being successful; this is especially important when
k becomes smaller.
* Time puzzles: The LCS35 timelock includes a parameter t
that sets the difficulty of the puzzle: 2^{2^t} (mod n)
* MicroMint: The "cost" of a coin is determined by its number
of colliding hash values. The greater the k-way collision,
the harder the coin is to generate.
* Payword: Most simply, a commitment within PayWord can be a
promise of varying amount. However, PayWord is designed for
iterative payments. To be able to use the same PayWord chain
for successive transactions, we want to always pay with coins
of the same value. Therefore, to handle variable costs, we can
just send several paywords for one transaction. The very
light-weight cost of creating and verifying paywords (a single
hash per payword) makes this multiple-coin approach more
suitable than for macropayment schemes.
* Anonymous digital cash: Coins can have different
denominations. In Chaum's design, the bank uses a different
public-key to sign the coin with for different denominations.
In Brands' model, the denomination of the coin is encoded
within the coin's attributes; the bank's public-key is unique
to currency, not denomination. Brands' digital cash system
also allows "negotiable attributes" to be revealed or kept
secret during payment -- this additional information can play a
role in setting the accountability slider.
By negotiating these various values, we can change the level of
accountability and security offered by a P2P system. Based on overall
system requirements, this process can be set by the system designers,
the administrators of individual peer machines, or even can fluctuate
between acceptable levels at run-time!
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 not 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...