To main Internet money page

Anonymous Electronic Cash


Suppose one pays for something by check, paypal, or credit card. This creates a record, unlike cash.

We therefore desire some method of transferring promises to pay across the internet which does not require a paper trail, in the same way we can transfer paper notes in the physical world without leaving a paper trail.

Chaum developed a very ingenious system. Unfortunately he patented it.

David Wagner thought of an even more ingenious and simple system. He believed, however, Chaum's patents would cover this system.

On the coderpunks list Wei Dai suggested that existing patents would not cover a MAC based scheme for anonymous electronic cash. Then, in a later posting he interpreted Wagner's scheme as MAC based

So I looked up the patent literature to see what I could see, and I did not find any patent covering Wagner's proposal, as reinterpreted by Wei Dai.


Anonymous Transfer of promises to pay

Here is Wagner's proposal, described in terms of elliptic curve points. (Wagner described it in terms of exponentiation in a finite field.) Wagner describes his proposal only in outline. Wei Dai (in interpreting it in such a way as to avoid Chaum's patents) added detail that was not explicitly present in the original. I have added more detail still, so as to make explicit how this scheme can be used to solve various practical problems. Wagner proposed no substitute for the problems resulting from the omission of the key step patented by Chaum.

The token issuer promises to pay a specific sum of money for any secret of the form ( x, P), such that P = k * H(x) where H is a hash function mapping random integers onto random points in an elliptic curve and k is a secret known only to the token issuer. On effective way of making such a one way function is to take the hash of the integer to be the x coordinate of the curve, and calculate the y coordinate of the curve. (To impose high costs on someone attempting a DOS attack on the bank server, the bank could require that H(x) be of a special form)

The first person to reveal a token of this form to the issuer is credited with the face value of the token, and the token is recorded in the issuer's database as spent.

Let us call the token issuer "Toby".

Well, you may ask, if k is a secret known only to Toby, how does anyone know that their secret is of the form that is entitled to receive money?

Chaum had a very clever answer to this, an answer described in his very clever patent . Wagner had an even cleverer answer. In Wagner's system, as interpreted by Wei Dai, they do not know!

This creates a problem, which I discuss below in "Patents". There are several ways around this problem, none of them as good as that proposed by Chaum, but they suffice. One such solution is described here.

Toby also promises, in return for the same sum, to multiply any elliptic point anyone wishes by this secret number k .

Because it is hard to divide one elliptic point by another to get a number, whereas it is easy to multiply an elliptic point by a number, this does not reveal the secret k .

But hold on: Why is Toby doing this? If the payments are the same, where is his profit? We assume that Toby is issuing various denominations of token, and also account based money. He does not charge to convert tokens, or to convert between one form of money and the other, but he does charge when money is transferred in or out of his system, and he also makes a profit on the float (seigniorage).

Let us assume Bob wants to pay Ann some money.

One method would be for Bob to invent a random number q , construct an elliptic point Q=Hash( q ), and ask Toby to construct P= k *Q.

He now has a secret of the required form q ,P, which he can give to Ann. But this does not get us anything that electronic checks do not give us. When Ann presents P to Toby, he can see that it is the same P as he generated for Bob.

When Bob purchased some tokens, Toby discovered Bob's true name, since probably the only way to deposit money is through the existing banking system.

Similarly when Ann cashes in her tokens, Toby will discover her true name, since she will instruct him to write a check to someone, and that someone is probably the true name of Ann.

If Ann is selling videos of Lolita and a donkey, and Bob the head of United Way, this could be a problem for Bob.

Fortunately Bob has an existing used token that he received earlier from Toby, or which someone else received earlier from Toby. Bob already has an elliptic point U constructed from that token, and the elliptic point V from that token, and knows that V= k * U even though he does not know k.

So what Bob does instead is invent the random numbers t and q, constructs an elliptic point R = t *U + Hash( q ) and asks Toby to construct T= k * R.

He then calculates Q = T- t * V

He now has a token ( q , Q) of the required form, even though Toby did not generate Q, has never seen it before, and when he sees it will not recognize it as having any relationship to T or R. (If Toby requires H(x) to be of special form, he can refuse to generate tokens (T) of that form, thus ensuring that all coins he generates are blinded, that the client is not leaking information to him that he does not wish to know.)

This method also ensures that the issuer cannot mark the money by using a different secret k for different customers. If he does mark the money, then someone unaware of the marking who uses those coins for his blinding will generate badly formed coins.

So Bob can now pay Ann, and Toby cannot know. Even if Ann collaborates with Toby, because she wants to find out who Bob really is, and blackmail him, they still cannot know. That is payer anonymity. However it is not payee anonymity.

Suppose Ann; instead of cashing in the tokens right away, exchanges them with Toby for fresh tokens. If she generates new random numbers in the same way that Bob did, her new tokens are known only to her, and cannot be linked with the tokens she received from Bob, and just cashed in.

She then has payer/payee anonymity, and does not need to deposit her fresh tokens right away.

Since no one else can know this token, she can sit on it, spend it with someone else, or deposit it in an account connected to her true name. If Ann is selling bootleg music, and Bob is working for the record companies to trap sellers of bootleg music, there is nothing he can do, for only Ann knows t , and so only Ann knows the connection between the elliptic point she received, and the elliptic point she will deposit. So Ann the music pirate received a number with certain properties, and Ann the respectable citizen deposits the token under her true name from a separate computer, and there is no known connection between the elliptic point Ann the pirate received in exchange for Bob's token, and the elliptic point that Ann the respectable citizen deposited.

If Toby allows easy conversion from old tokens to new tokens, he does not need to provide account-based money. People can use tokens alone. The "Magic Money" implementation (which flagrantly violated Chaum's patents) did not provide accounts.


Patents

Wagner's proposal has elements in common with Chaum's blind undeniable signatures

In particular the blinding steps are identical to those proposed in claim 9 of the above patent, and the signing step identical to that proposed in claim 7 of the above patent, however the above patent does not seem to cover Wagner's method, because the relevant claims say:

7. The method according to claim 3
wherein said signing step comprises raising said unsigned message to a signing power derived from said private key, such exponentiation being performed in a finite structure where the inverse of such exponents is unknown.
9. The method as in claim 1, further comprising the steps of:
blinding said unsigned message responsive to a blinding key before providing the resulting blinded unsigned message to said signing party in place of said unsigned message; and unblinding said undeniably signed message returned by said signing party responsive to said blinding key.

Wagner's method does not use anything resembling the method according to claim 1 or claim 3, and as a result there is nothing stopping the token issuer from falsely denying a token.

The clever and ingenious part of Chaum's patent is a method whereby third parties can check that a token has been signed, whether or not the signature has been blinded (claims 1 and 3). In Wagner's method, third parties never check the signature.

But if third parties never check the signature, then what is to stop the issuer from marking the coins by using a different k for each customer, or for certain suspect customers? In this proposal, we prevent that by using used coins for the blinding. If customer A and customer B are given coins based on different secret keys without their knowledge, and customer A uses a used coin from customer B for blinding, the protocol will fail, alerting them that something is wrong. The issuer will suffer reputation damage as someone who embezzles, or fails to honor, correctly constructed coins.