Hal, a very nice summary! I have some questions, though. At 5:32 AM 9/15/95, Hal wrote:

The problem is that there is a conflict between the desire for payee anonymity and the need to prevent double spending. And preventing double spending is far more important, since without that the cash would be worthless. Here is how the conflict occurs.

Agreed, any system which allows makes double spending possible results in a currency collapse as the currency becomes worthless. Chaum points out that there "is no digital coin," that is, that software (numbers) must by their nature be easily copyable. Thus, any system to prevent double (triple, quadruple, etc.) spending must take this into account. Why not "online clearing" as the preferred model, then? To use your example:

Suppose Alice has a piece of digital cash which she wants to spend with Bob. She goes through some protocol and transfers data to him. Bob, then or later, sends some resulting data to the bank and gets his account credited. Now if Alice spent that same coin with Charlie, we need to have the bank find it out. When Charlie deposits his data with the bank, and the bank compares that with what Bob sent in, there must be a red flag that goes up.

With online clearing, Bob sends his data to the relevant bank, confirms that his account has been credited, and tells Alice that her "check has cleared," so to speak, and the transaction is completed. Then, when Alice tries to spend the "same" digital cash with Charlie, he sends his data to the bank and the bank tells him the money has already been spent. Charlie informs Alice that the transaction has failed, that her money is no good. I'm not claiming this is how Chaum's currently-available system works, only that nothing in Chaum's scheme hinges on a True Name, of course. So with online clearing, the second spending is blocked, but there is still no leakage of identity, is there?

The fundamental requirement of preventing double spending implies that Bob's and Charlie's data, when sent to the bank, has some correlation which will identify the fact that they both come from the same coin. It doesn't matter exactly what the form of this data is, or how it has been blinded and stirred, but if double spending is to be detected there must be a correlation which the bank can see.

I agree. But this is like the following analogy: Alice has a special kind of money, called a "train locker combination." This special kind of money is the location of a storage locker and the combination of a lock on the locker. She "spends" this special kind of money by giving this information to the person she is paying. The recipient has a couple of basic options: 1. Send someone to verify that the locker contains the specified goods, at which point the transaction is completed. This is equivalent to ONLINE CLEARING. (I'm not going to get into the situation where he gets the money, then cancels or reneges on the deal....this is a possibility in "cash" transactions as well, save with escrow schemes, and even then...) 2. Accept the word of Alice (in the sense of not actually transferring the money via online clearing) and count on systems which implicate her if she tries to spend the money a second time, i.e., tries to tell someone else the locker and combination. (The "observer chip" option Chaum raises, and which may have a parallel here, I'm not considering. I'm deeply suspicious of solutions calling for tamper-resistant hardware...just not very strong by cryptographic standards, etc. Maybe I'm just ignorant, but the observer chip approach Chaum described in his "Scientific American" article a few years ago was unconvincing to me.) The elegance of the first option, online clearing, is that Alice is motivated to keep her secret information (the money) secret, and that once it is "spent," or cleared and transferred, there's no going back. She can't renege, she can't collude with the bank to see where it went. The bank, upon valid receipt of an order to "cash" the "check" then could place the money in an "envelope" (in Chaum's terms) supplied by Bob and then post it in a message pool. (Bob can submit his claim to the money via remailers, and receive the money-in-envelope via remailer return replies (if they ever get perfected, as I suspect they will be) or via message pools. Bob receives the envelope and reverses the blinding operation, thus having cash not traceable to him in any way. I'm persuaded that the second approach, involving protocols for revealing double spending, is much messier than the "he who gets there first" protocol. The online clearing model largely emulates how real physical cash works, where there is a direct transfer, where the cash must be protected against loss (lose it and you're just out of luck, unlike, say, as with traveller's checks, which are account-based), and where a kind of "online clearing" is actually done when the cash is checked to see if it's counterfeit.

But this correlation is what makes the coin traceable. Suppose Alice is paying a coin to Bob via an anonymous network, and she and the bank are going to try to figure out who he really is. She goes through the payment transaction, and Bob sends his resulting data to the bank. Before doing so, though, Alice simulates a payment of the same coin to Charlie. Charlie doesn't actually have to be involved, Alice can just go through what she would have done if she had spent the coin elsewhere. The result of this simulated payment has been shared with the bank.

With online clearing, this kind of "sting" by Alice is impossible (at least in the way described here). Alice pays Bob, Bob sends his data to the bank, the bank reports the money has already been transferred (or, simply reports back "invalid transaction"). An account-based system, one that doesn't do online clearing, will need the correlation that Hal cites. An online system will not...whoever gets to the money first gets it, as with real cash. (There are more abstract ways of viewing this advantage. While mere software is always duplicable, and cash numbers are of course duplicable, one thing that is not duplicable is this: "the first agent to present a valid number at this bank." There can be only one of these, and this uniqueness is what keeps the currency from collapsing, what introduces _conservation_ into the system.)

Now, when Bob deposits his data, the bank compares it with the data Alice sent, the result of her simulated spending of the same coin. By the argument presented above, Bob's deposit will be flagged. It will correlate with the data Alice sent in since this will be the equivalent of a double-spending. So when Bob makes the deposit he can be linked to the specific coin payment which Alice made, and his anonymity is lost.

Well, since Alice knows her own blinding factors, she will always be able to say to the bank: "My cash will look like this. Watch for it." The key is for Bob to take the cash Alice gives him and communicate to and from the bank with mixes, as described above. Bank / \ / \ / \ Alice - - - Bob (Sorry I can't flesh out this diagram....ASCII just won't cut it. Mere English is even worse at describing these transactions.) Another elegant way of viewing things: If Alice colludes with the bank, by doing a fake-spend with the fake "Charlie," or by reporting to the bank what her blinding factor will be and hence what "her" cash will look like, then effectively the transaction collapses to: Alice/Bank \ \ \ Bob But if Bob can get cash from the bank that the bank cannot trace, via the blinding factors, then Bob can get cash from the Alice/Bob collusion. The fact that Alice can correlate a particular transaction to Bob's contact with the bank can be defeated by Bob using anonymous remailers to protect his identity. My Apologies: I suspect I've been rambling a bit, thinking out loud by typing. There are different issues involved here: offline vs. account-based systems, the use of remailers and message pools to sever the links between transactions and identities, and the (mostly unmentioned) role of third-part escrow agents and "anonymizers." (Think of what happens when online clearing is used to shuttle the cash between N different agents...even if Alice is colluding, will Candy, Devon, Eric, Floyd, etc. all be in the same collusion set?)

It would seem that any system which is capable of detecting double- spending just from the information which the payees send in to the bank would be vulnerable to this. Systems which use tamper-proof observer chips to prevent double spending beforehand can avoid it, but of course if someone breaks an observer the whole cash system might crash. In general it does not look like payee anonymity is possible without giving up other very important features.

I don't think all systems must be able to deal with double spending. For example, the first person to read this number: 45%2)d[12ks&Qmdx and to then submit it any form--in person, by e-mail, via remailer, etc.--to The First Bank of Cyberspace will have $10 sent to him or her, as cash or as a spendable amount of digicash (untraceable to recipient, of course). Where's the payee traceability that I, the payer, have? (The key is that I don't have to deal with double spending, as there is only one "first person to ....") I believe Chaum has thought about the issues in creating "Pure Digital Cash." While a pure "digital coin" may not be possible, I believe a two-way untraceable digital cash system is possible. Frankly, I think Chaum's work on DC-Nets points the way, though even simpler realizations may be enough for practical purposes. My hunch, just a hunch, is that Chaum has been concentrating on the particular protocols which avoid online clearing and which avoid avoid the payer/payee untraceability for pragmatic reasons. Pragmatic as in "politically wise." --Tim May ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^756839 | black markets, collapse of governments. "National borders are just speed bumps on the information superhighway."