Re: Why ecash is traceable

[tcmay@got.net (Timothy C. May)]

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."