[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Detecting double-spending (long)
- To: cypherpunks@toad.com
- Subject: Detecting double-spending (long)
- From: nobody@alumni.cco.caltech.edu
- Date: Fri, 15 Oct 93 08:50:34 PDT
- Comments: This message is NOT from the person listed in the Fromline. It is from an automated software remailing service operating atthat address. Please report problem mail to <hal@alumni.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