Detecting Double Spending
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.
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 secret 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 MD5 algorithm from RSA, and the US government’s Secure Hash Algorithm (SHA).
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.
(To make this explanation easier to follow, I will describe a slightly simplified version of Chaum’s off-line cash. The version I describe requires the use of a non-invertable one-way function as in the f() used above. Chaum’s version does not require as strong an assumption and provides “unconditional” untraceability even if the one-way function is broken.)
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 succeeding. Each number is of the form g(xi,yi)^(1/3), where g is a two-argument one-way function similar to 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 = f(ai), where ai is a random number, and f is another one-way function. yi is kind of complicated. It is f(ai xor <info>), where <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 yi. If he chooses 0 he gets told (ai xor <info>) and xi. This will let him check the signature on the money, as described in more detail below.
Notice that when Bob gets this information, 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.
(Chaum suggests not just relying on random chance to make sure Bob and Charlie use different sets of 1’s and 0’s. At least some of the bits might be assigned to Bob and Charlie by the bank in such a way that everybody gets a different number. This way it would be guaranteed that Bob and Charlie would choose opposite values for some i.)
The reason for the money to have the form it does is so that Bob can check that it is signed by the bank. For each value of i Alice has to give him enough information to calculate xi and yi. If Bob choses a 1, she gives him ai and yi. Given ai Bob can calculate xi (=f(ai)), and with this and yi he can calculate g(xi,yi). If Bob chooses a 0, she gives him (ai xor <info>), as described before, and also xi. Given (ai xor <info>), Bob calculates yi (=f(ai xor <info>)), and with this and xi he can calculate g(xi,yi).
So for each i, whether Bob gives a 0 or a 1 he gets enough information to calculate g(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 g(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 g(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 g(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
[email protected]