Why ecash is traceable

There has been considerable discussion on sci.crypt and on the 
cypherpunks list about the fact that currently proposed digital cash is 
"traceable", or to put it another way, that there is no payee anonymity.  
This is an annoying asymmetry, where the payor is protected more than 
the payee.  But there is a fundamental reason for this, which I want to 
explain here.  It is not just perversity on the part of digital cash 
designers.

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.

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.

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.

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.

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.

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.

Hal Finney
hfinney@shell.portal.com

-----BEGIN PGP SIGNED MESSAGE-----

Hal <hfinney@shell.portal.com> wrote:
>
> 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.
> 
> 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.


So Alice/TheBank are able to tell that the nym whom Alice gave the coin to
is the same as the nym who deposited it.  If Bob has a pseudonymous
account at the bank, and it was the same pseudonymous account that he used in
the transaction with Alice, then they haven't learned anything new, but if he
wants to use one pseudonym when dealing with Alice and another to deposit the
coin he got from her then he has problems.


That's the extent of the damage, right?  Seems like it can be prevented by
laundering the coin through a single pseudonym first.  That is:  Bob receives
the coin from Alice, calling himself "CyberBob".  He deposits the coin with
the bank as a one-time-nym "Nym#2837004", then he has that nym withdraw the 
same amount of money from its account (closing out the account) and transfers
it to the nym which will actually keep the money, "NormalBob".  He destroys 
the new blinding factors after the temporary nym has withdrawn the coin, 
he deposits the coin with the bank as "NormalBob", and now he is in the clear.


Am I missing anything?


If Bob's transaction with Alice was actually pseudonymous rather than
anonymous then he can just deposit the coin using the same pseudonym and they
haven't learned anything new.  Once he has done that he can safely transfer
the money to any other nym of his with no risk (except for traffic analysis,
physical surveillance, yadda yadda yadda).


So current (DigiCash "ecash") Chaumian protocol leads to complete 
anonymity/pseudonymity (there oughta be a word for that.  
"self-nym-control"?) in the case that pseudonymous accounts are allowed at
the Bank.


Now one could move this "double-blinding" (isn't that phrase already in 
use?) trick into the cash protocol itself, possibly gaining a performance 
win.  DigiCash is apparently aware of this possibility, but (rightly) 
doesn't consider it important to develop right now.


Regards,

Bryce

signatures follow:


                                    +                                           
      public key on keyservers      /.      island Life in a chaos sea        
      or via finger 0x617c6db9      /           bryce.wilcox@colorado.edu     
                                    ---*                                     

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Auto-signed with Bryce's Auto-PGP v1.0beta4

iQCVAwUBMFpTOfWZSllhfG25AQHndAQAuOfz4Fohl3e/4Q3eUKKY2nZNG+TdDQEN
FvW1q1KAuGTeGJoNmL6qD4xkV1wXuT7UScN/7BwU+8SsIh3B5Cb834saGsCTjNtb
8EV2zsYqzdJkJ3DuDHQw785gqrNPokug4KPP4LRMt5N+PnPRTAWnq6PRibegsg86
ypFcUOVbLTU=
=K+5k
-----END PGP SIGNATURE-----

This looks as though you are simulating the
'deposit-and-get-coinage-back' within a
'deposit-and-have-account-credited' system.

	I figure that they would make the transaction cost involved in
creating an account sufficiently high that this plan would be
defeated-- or they wouldn't allow psuedonymous accounts.

-- 
sameer						Voice:   510-601-9777
Network Administrator				FAX:	 510-601-9734
Community ConneXion: The NEXUS-Berkeley		Dialin:  510-658-6376
http://www.c2.org (or login as "guest")			sameer@c2.org