From: daw@cs.berkeley.edu (David Wagner)
Date: Thu, 3 Apr 1997 23:31:43 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: No, it's PayWord, no, it's MicroMint, no, it's...
In-Reply-To: <199704040538.VAA01156@crypt.hfinney.com>
Message-ID: <5i2af3$vhq@joseph.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain


In article <199704040538.VAA01156@crypt.hfinney.com>,
Hal Finney  <hal@rain.org> wrote:
> David Wagner, daw@cs.berkeley.edu, writes:
> > 	http://www.cs.berkeley.edu/~daw/my-posts/anon-micropayments
> 
> I wonder if there is a problem with the double spending detection.
> Somebody could spend at a store, then return some of the spent coins to
> the broker before the store has a chance to update the broker with the
> most recent spending report.  Maybe the broker could contact the store and
> let them know that the stack was redeemed now, and see how many had been
> spent.

In the non-anonymous case, shops can go offline and redeem sticks nightly;
this doesn't prevent double-spending, but allows detection, so that brokers
can blacklist double-spenders.

When you move to anonymity, you need a different approach; going online at
stick commitment time works (i.e. when the shop checks the digital signature
it simultaneously goes online to the bank).  This has some of the costs of
online schemes, but isn't terrible, because you only do it when the first
coin is paid, not when subsequent coins are.

If going online is a problem, you could imagine doing probabilistic
online checking.  The shop has a 10% chance (say) of going online and
checking immediately, and a 90% chance of batching for verification on
the half hour.  If the shop sees a bunch of fraud going on during some
batched verification, then the shop has to take that as a loss, but it
then knows to increase the chance of going online significantly.  You
can imagine auditing agencies (or the bank) publishing daily statistics
on fraud, and businesses adjusting their percentages to respond with
the trends.  Again, different shops will probably have different trade-offs
(based on performance demands, risk, whether they're using durable goods
or selling just bits, and such); this gives them flexibility in choosing
their risk profile.


You mention specifically the special double-spending problem of spending
once at a shop and once when asking for a redemption of a partially-spent
stick.  To help ameliorate this particular problem, some special-purpose
solutions are available: for instance, you could enforce a one-day waiting
period on trade-ins for partially-spent sticks.  For instance, the consumer
commits today, and if no shop has collected by tomorrow, he gets the cash
back; shops are instructed to verify nightly, or else they bear much more
risk.  Consumers don't need to trade back their sticks in real-time; they
can certainly be forced to wait a day or two at no real inconvenience.

> I had an idea for doing the double-spending problem in an offline way by
> using the same technique used for Chaum's offline coins.  The customer
> embeds his identity in the coins, blinded with a random number.  A cut
> and choose technique is used during withdrawal for him to prove that
> he has set up his coins correctly.  Then when he spends the first time
> at the shop, he responds to a random challenge revealing some of his
> blinded info.  This is done in such a way that if he spends at two shops,
> his identity is revealed by combining the info from the two different
> challenges.
> 
> Unfortunately then when he returns the unspent coins at the broker,
> and goes through the protocol there, that will reveal his identity since
> he is in effect double spending the stack.

I don't know; I know nothing about Chaum's offline coins.

Can you enforce a trade-in where the new stick the user gets has the
same identity information in it that the old stick had, and the bank can
verify this equality (cut-and-choose somehow??) without needing to know
the identity informatino itself?  I don't know.

> Another concern was for the method where a stack of 87 coins gets redeemed
> for a fresh stack of 87.  This has the slight problem that the size of
> the new stack would be correlated with the size of the one turned in.

Good point.  That didn't occur to me.  Thanks.