Real-world digicash

I've been reading digicash papers lately, and it appears there are three
approaches to preventing double-spending:

1) Catch the cheater after the fact, by matching up two copies of the
   same coin in such a way as to reveal his identity. This requires a
   challenge-response sequence between the user and the shop.

2) Combine (1) with an observer, a piece of secure hardware which
   signs transfers and prevents double spending.

3) Use an online server which checks off coins as they are spent.

After-the-fact detection probably won't fly, because organized multiple
spending could kill it. There are people who are dumb enough to write
their PIN numbers on their ATM cards. Such people will also be careless
with their digicash and any secret keys used to protect it. A thief could
compromise a few coins belonging to such careless people, distribute
them to a network of many thieves, and spend them hundreds of times before
being detected. This would make the shops either abandon digicash or
refuse to deliver merchandise until the coins cleared the bank, making it
effectively an online system. Using this type of digicash over the net
would be particularly troublesome. A person receiving a double-spent coin
would be in the same situation as a person receiving a bad check from
another state. Legally, he has all kinds of rights. Practically, he is
flat out of luck. It will cost him more to take action than the amount
of the coin or check.
 
Observer-based protocols can protect privacy. All data going to and from
the observer is blinded by the user's software so the observer cannot
learn anything about the user. The design of the observer can be public;
the only secret in the observer is a key. Observer-based protocols also
include the after-the-fact detection, so anyone who cracked his observer
(i.e. extracted the secret key) would still be caught later. To cheat,
you would have to steal someone else's observer, extract the key, and use
it. If the time required to crack an observer was longer than what it
would take a person to notice and report his stolen observer, fraud would
be uncommon. Because the observer is hard to crack, it would be much like
counterfeiting paper money: possible, but requiring a large organization
to be profitable. Such an organization would be susceptible to traditional
methods of law enforcement.

Since observers require hardware, this method cannot easily be used on a
guerrilla basis. The banking industry could do it, but since people are
willing to use credit cards, which are online, insecure, and a
dossier-builder's dream, there is no particular motive for the banks
to create such a system. Most people, if surveyed, will say that they
are concerned about their privacy. But when made to choose between
privacy and convenience, they choose convenience.

That leaves online digicash as the most practical system for use on the
net right now. Online digicash will probably be the only system
trustworthy enough for large transactions in any case. Are there any
published online systems which include strong privacy and which allow
multiple banks/servers? NetCash does not provide strong anonymity;
the user has to trust the coin issuer not to record who gets which coins.
An investigator could go to the coin issuer and demand that the issuer
track a particular user's coins.

--- MikeIngle@delphi.com

Mike Ingle:
> After-the-fact detection probably won't fly, because organized multiple
> spending could kill it. There are people who are dumb enough to write
> their PIN numbers on their ATM cards.

Nevertheless, millions use ATM cards, with substantially less loss to
fraud than with credit cards.  Improvement in privacy and reduction
of incidence of fraud over credit cards are sufficient goals for a 
digital cash system.

For Pretty Good Digicash, which would probably far exceed those
goals, how about a "mostly offline" system as follows:

* Modify offline cash to be "stochastically online", so that
1 out of every N coin transactions are checked for double spending 
online, and the remainder of the coins are kept offline.  The chances 
of getting away with K+1-spending a coin are (1-1/N)^K.  The chances of 
getting away with K+1-spending each of M different coins are (1-1/N)^MK.
In general, with a fixed upper limit on coin denominations, the chances of
getting caught at the scene of double-spending increase exponentially
with the amount double-spent.  This means penny-ante fraud will
be easy to get away with (at the scene), but large scale fraud
quickly becomes impractical.  This also means that most 
low-value transactions will be offline and most high-value
transactions online.   Note that above formulae are the odds
of getting the goods before being caught.  Even if by chance all
coins are kept offline during the fraudulent transactions, the odds
of two making it back to the bank increase exponentially
with the number of times they change hands.  Thus even penny-ante
double-spenders will soon be caught, with odds quickly approaching 
certainty, after the fact.  The double-spender's 'nym is then 
revealed, and its reputation damaged or destroyed.

* N is the credit rating of the customer. 'Nyms with good,
solid credentials and/or long-standing reputations can be trusted 
to spend large amounts of digital cash per online check.
New 'nyms, 'nyms with bad credit ratings, and anonymous spenders 
have lower N and are thus checked more often.  Attempting
to defraud via rapid turnover of penny-ante double-spending
'nyms won't pay, because the odds of a new 'nym getting caught
online can be placed as high as needed to make this strategy a loser.

At the first sign of double-spending, or if other signs of
bad credit accumulate, credit rating N is lowered for the customer.  
N should be set by credit rating agencies so that
(Max coin denomination)*MK*(1-1/N)^MK is less than the 'nym's
accumulated "reputation capital", so that it does not pay to build a 
reputation and then "cash in the reputation chips" with a spectacular 
act of digicash fraud.  Since the reputation capital of most customers
will dwarf the average size of their purchases, in practice
the vast majority of purchases will be offline, with only
a few (mostly large) purchases held up for online verification
(which need not take any longer than online verification of
credit cards today).

I envision a decentralized credit-rating system, so that the
integrity of ratings cannot be jeopardized by corrupting one or a 
related few credit rating agencies with false information.  (The IP 
paradigm: an economy should be able to route around node failures).

Nick Szabo				szabo@netcom.com
HEx symbol: N  :-)