Detecting double-spending (long)

[nobody@alumni.cco.caltech.edu]

Here is an attempt to describe Chaum's digital cash from his paper,
Untraceable Electronic Cash, by Chaum, Fiat, and Naor, from the Crypto 
88 proceedings.  This cash has the property that the user of the cash 
can remain anonymous so long as she does not spend it more than once, 
but if she does double-spend then her identity is revealed.  The 
explanation is kind of complicated, but I'm hoping to improve this 
description to the point where people can actually understand it, so I'd 
appreciate feedback.

This is how it works in general terms:  Alice opens an account with a 
bank non-anonymously.  She shows ID so that the bank knows who she is; 
both she and the bank know her account number.  When she withdraws cash, 
she goes to the bank or contacts them electronically and presents some 
proof of who she is and what her account number is, and the bank gives 
her some digital cash.  The digital cash is an information pattern, 
perhaps stored in a computer file on a smart card or magnetic disk.  
Later, she spends the digital cash by sending or giving it to Bob, a 
merchant.  Bob can check and verify that the cash must have come from 
the bank.  He accepts the cash if it is valid, giving Alice the 
merchandise.  Later, he sends the cash to the bank to be added to his 
own account.

Note that this much could basically be done with a simple RSA signature.  
The bank could give Alice a statement saying, "this is worth $1", signed 
by the bank's public key.  Bob could verify that the statement was in 
fact signed by the bank, and know therefore that no one else than the 
bank could have created that statement.  He accepts it and sends it to 
the bank, which honors it since it recognizes its own signature.

One problem with this trivial money is that double-spending can not be 
detected or prevented since all the cash looks alike.  This can be 
remedied by having the cash include a unique serial number.  Now when 
Bob goes to accept the cash from Alice, he can call the bank and say, 
has anyone else deposited serial number 123456?  If not, he accepts the 
cash and deposits it.  This is called on-line electronic money; the 
merchant must check with the bank for each transaction.

This improved simple system does not deserve to be called cash, though, 
because it lacks the distinguishing characteristic of digital cash: it 
is not anonymous.  When the bank sees money with serial number 123456 
being deposited, the bank recognizes that this was the same bill that 
Alice withdrew.  The bank can therefore deduce that Alice spent the 
money at Bob's, and from this kind of information a dossier could be 
built up with all kinds of privacy-destroying information about her.

To allow anonymity, we have to get into the mathematics.  What we want 
is for Alice and the bank collectively to create an RSA signature from 
the bank that could not be forged, but one which the bank will not 
recognize as coming from Alice.  This is the first thing Chaum's paper 
discusses.

The money in this system is of the form (x, f(x)^(1/3)) mod n, where n 
is the bank's public modulus.  f() (and, below, g()) is a one-way 
function, one which can be calculated easily but for which it is 
infeasible to calculate the inverse.  It should also be infeasible to 
come up with two different y,z such that f(y) = f(z).  Today there are 
several suitable choices for one-way functions, the most common being 
the MD4 and MD5 algorithms from RSA.

The reason the expression above would be accepted as cash is two-fold.  
First, only the bank can calculate anything ^ (1/3) mod n.  This is 
basically the RSA signing operation for the exponent of 3.  Nobody else 
can find cube roots.  The reason f(x) is used is this.  Suppose we 
proposed that (x, x^(1/3)) should be the cash, for some random x, 
reasoning that only the bank could find the cube root of x.  Can you see 
how to forge cash like this?  (Take a few moments and try to see how you 
could construct a pair like this even if you can't take cube roots.)

The answer is that it is easy to forge this by first choosing a random 
y, and exhibiting the pair (y^3, y).  Now we have a number and then its 
cube root.  Yet we didn't have to take any cube roots to find it.  
That's why this kind of money would be no good.

Chaum's system avoids this by taking the cube root of a one-way function 
of x.  To forge it without taking a cube root you'd have to produce 
(finv(y^3),  y), which would match the above pattern, but you can't 
invert the one-way function like that.  So only the bank can create 
money of the proper form.  This can be thought of as the formal, 
mathematical form of my informal "money" above which was a digitally 
signed note with a serial number.  Here, x is the serial number, and 
it's digitally signed in this special way.  Nothing more is needed.

The nice thing about this money is that it allows for blinding, a method 
of having the bank sign the value without knowing what value it is 
signing.  It works like this.  Alice chooses x, which will be the x in 
the cash.  She calculates f(x), but instead of sending it to the bank to 
be signed (raised to the 1/3 power) she first chooses a random number r, 
and sends f(x)*r^3 to the bank.  The bank takes this number to the 1/3 
power, getting r * f(x)^(1/3).  Remember, though, that the bank doesn't 
see r or f(x) separately, but just their product.  It doesn't know what 
r or f(x) is.  They could each be anything, actually.

The bank sends this r * f(x)^(1/3) back to Alice, and she divides it by 
r, which she knows.  This gives her f(x)^(1/3), and she puts that 
together with x to get her digital cash: (x, f(x)^(1/3)).  She has a 
piece of money which could only have been signed by the bank, yet the 
bank won't recognize it when it is deposited.

Other, non-mathematical, things take place as this withdrawal goes on.  
Alice must prove her identity to the bank, as mentioned above.  And the 
bank will debit her account by the value of the cash.  In this system, 
we are assuming for simplicity that all cash has the same value.  In a 
real system, different values might be encoded by different exponents 
than 3.

When Alice deposits the money, Bob must call the bank to make sure that 
it hasn't been deposited before, this being an "on-line" system.  
Although the bank won't recognize x (it's never heard of it) it will 
remember all the x's which have been deposited and so can alert Bob if 
the money has been spent before.  Both Bob and the bank can verify the 
digital signature on the money and so will honor it.

All the material above takes up less than one page of Chaum's nine-page 
paper.  For Chaum, this much is trivial.  Now we get to the interesting 
part.  Now we will see the scheme that allows double-spenders to lose 
their anonymity.  This will allow for "off-line" electronic cash; Bob 
will no longer have to check with the bank to see if the money has 
already been spent.  He accepts it from Alice knowing that if she does 
cheat, the bank will honor the cash and sue Alice to make up the loss.

Let's start with the form of the cash itself.  It is the product of k/2 
numbers, where k is a "security parameter" that affects the chance of a 
cheater getting away with it.  Each number is of the form 
f(xi,yi)^(1/3), where f is a two-argument one-way function like the f 
above.  (The "xi", "yi", "ai", etc. here are separate values for each i 
from 0 to k/2.)

xi and yi are like this:  xi = g(ai, ci), where ai and ci are random, 
and g is another one-way function.  yi is kind of complicated.  It is 
basically g(ai xor <info>, di).  di is another random number, and 
<info>, the key to this whole operation, is identifying information 
about Alice's account!  It is her account number concatenated with a 
serial number for the cash.

Now, why go through all this?  Here's why.  If you could find out both 
ai and (ai xor <info>), for some i, you would know Alice's identity.  
(Xor'ing them would produce <info>.)  When Alice double-spends, both ai 
and ai xor <info> will be revealed.

What happens when Alice spends the coin is this.  For each i from 0 to 
k/2 Bob chooses 0 or 1 at random.  If he chooses 1 he gets told ai (and 
some other stuff).  If he chooses 0 he gets told ai xor <info> (and 
other stuff).  The other things he gets told are sufficient to let him 
confirm that the money is of the proper form.

Now, if Bob does this, he'll know a bunch of ai's, and he'll know a 
bunch of (ai xor <info>)'s, but they are for different i's.  He doesn't 
know both ai and (ai xor <info>) for any one i.  So he can't break 
Alice's anonymity.

When Bob deposits the money at the bank, he passes along the information 
he got from Alice regarding the ai's and such.

Now, suppose Alice cheats.  She spends the money again somewhere else, 
at Charlie's.  Charlie goes through the same procedure as Bob, choosing 
0 or 1 at random for each value of i.  Here is the catch.  Since he is 
choosing at random, it would be very unlikely that he will choose 
exactly the same 0's and 1's that Bob chose.  (Here is where the size of 
k matters - making it bigger makes it less likely that Charlie and Bob 
will choose the same pattern of 0's and 1's.  But it makes the 
calculations take longer.)  That means for one or more values of i, 
Charlie will probably choose a 0 where Bob chose a 1, or vice versa.

Because of this, if Bob got ai for that i, Charlie will get 
ai xor <info>.  Or if Bob got ai xor <info>, Charlie will get ai.  
Either way, when Charlie sends his record of this information to the 
bank, the bank will put Bob's and Charlie's information together and get 
both ai and ai xor <info>.  Xor'ing these together reveals <info>, and 
Alice is caught!  This is the main idea.

All the other things, the ci's and di's and such, are there so that Bob 
can confirm that the money is of the proper form.  For each value of i 
Alice has to give him enough information to calculate xi and yi.  If Bob 
chooses a 1, she gives him ai, ci, and yi.  Given ai and ci Bob can 
calculate xi (=g(ai,ci)), and with this and yi he can calculate 
f(xi,yi).  If Bob chooses a 0, she gives him (ai xor <info>), as 
described before, and also di and xi.  Given (ai xor <info>) and di, Bob 
calculates yi (=g(ai xor <info>, di)), and with this and xi he can 
calculate f(xi,yi).

So for each i, whether Bob gives a 0 or a 1 he gets enough information 
to calculate f(xi,yi).  He multiplies these all together and confirms 
that they are equal to Alice's original "money" value when it is taken 
to the 3rd power (recall the money was product of f(xi,yi)^(1/3) for all 
i).  Only the bank could have produced a signature on this one-way 
function f whose arguments take this special form.

One more complication exists.  (Well, actually, an almost infinite 
number of complications exist if you look hard enough.  But we'll just
focus on one more.)  Alice needs to get this special form of money 
from the bank in such a way that the bank won't recognize it.  That 
means she has to blind it.  But in this case the bank wants to be sure 
that the money is of the proper form when it signs it; in particular, it 
wants to make darned sure that Alice's <info> which is buried deep in 
all of those f's of g's is actually the right one for her.  But since 
the bank can't see what it is signing, this is hard to do.

Chaum uses cut-and-choose for this.  He has Alice prepare all these f's 
and g's according to the form above, carefully embedding her own 
incriminating <info> in each one.  Then she multiplies each f(xi,yi) by 
a blinding factor ri^3 just like in the first cash.  These are what she 
sends to the bank to be signed.

The trick, though, is that she sends twice as many as will be used.  She 
sends k of them, but only k/2 will be used.  (That's why the loop above 
used k/2 as the limit.)  The bank chooses k/2 at random out of the k she 
sent as the ones which will actually be used.  Alice then has to send 
the blinding ri values for the ones which the bank didn't pick.

The idea is that if Alice tries to cheat, embedding "Bozo" instead of 
"Alice" in that <info> field, she's taking a chance.  First, to be 
useful, she's going to have to embed it in a lot of <info> fields for 
different values of i.  When Bob and Charlie compare notes after she 
double-spends, every value of i for which they chose different 0's and 
1's, which will be on the average half of them, will reveal an <info> 
field.  If she only fakes a few, chances are her real identity will 
still be revealed.

But if she falsifies a great many of them, then when the bank chooses 
half, chances are at least some of the fake ones will be in the set the 
bank didn't choose.  Then when Alice has to reveal her blinding r's, the 
jig will be up.  The bank will un-blind all those f(xi,yi)'s which 
aren't being used, and see the fake <info> fields.

This cut-and-choose methodology has the disadvantage that Alice has to 
do twice as much work in preparing the money, half of which will just be 
thrown away.  But it is a simple, "brute force" way to make sure that 
blinding signatures are actually being done on properly-formed data.

So, there you have it.  Anonymity as long as you don't cheat, and 
double-spenders get caught.  It's a little complicated but that's what 
computers are for; Bob and Alice wouldn't do all this stuff by hand.  
Alice would push the "generate a money candidate" button and get 
something to be sent to the bank (lots of the new PDA's have infrared 
wireless communications that would be perfect for face-to-face 
transactions).  Bob would push the "check money" button when Alice spent 
it and it would flash red or green.  As long as the calculations don't 
actually take too much time, which they really wouldn't in this case 
despite this long-winded explanation, the people involved can ignore the 
details.

Hal Finney
hfinney@shell.portal.com