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.