[118408] in Cypherpunks
Re: Sander & Ta-Shma's ecash is revocable
daemon@ATHENA.MIT.EDU (Adam Back)
Sun Sep 26 19:18:28 1999
Date: Sun, 26 Sep 1999 23:59:09 +0100
Message-Id: <199909262259.XAA02457@server.cypherspace.org>
From: Adam Back <adam@cypherspace.org>
To: cypherpunks@cyberpass.net
CC: dbs@philodox.com
In-reply-to: <199909252259.AAA16560@mail.replay.com> (message from Anonymous
on Sun, 26 Sep 1999 00:59:20 +0200 (CEST))
Reply-To: Adam Back <adam@cypherspace.org>
I constructued a reply to this and accidentally nuked it before
posting. Damn.
Let's try again to explain what I was talking about:
> > Even if the coin by B giving the coin to C, A can still revoke both
> > payment A->B, and payment B->C again without identifying B or C.[2]
> >
> > [2] This works because there is a publically verifiable audit trail
> > showing payments in the audit log A->B->C etc. but where a given coin
> > can not be linked by the bank to the corresponding audit log entry.
> > The "coin" is a zero knowledge proof that the owner holds a preimage
> > of the audit log entry, without revealing to the bank which entry in
> > the list it corresponds to.
Actually the above is flawed I realise as I was confusing a b-money
property with Sander-Ta-Schma property which it didn't have. However
the following is also wrong, I think:
> This does not seem right. A gets a coin from the bank. It is in the
> issued coin list. He gives it to B, offering a zero knowledge proof
> that the coin's serial number is in the issued coin list. B deposits
> it and then gets a new coin to give to C.
>
> Now A decides to revoke his coin. He gets the bank to remove it from
> the issued coin list. But that has no effect. There is no way to know
> which deposited coin corresponded to A's coin. The deposit transcript
> was zero knowledge so it can not be linked to the withdrawal.
Well, there are two issues here:
What you describe above does not make the coin irrevocable. This is
because there is a linkage from A's revocation information to B's
fresh issued coin because the ZKP transcript is handed over at the
same time as the fresh coin is requested.
Issued coins are of form f(R,X) where R is kept secret, and X is the
serial number. ZKP(R) is a zero knowledge proof of knowledge of an R
corresponding to a coin in the issue list.
1. A spends coin:
A hands over ZKP(Ra), Xa to B
2. B deposits coin (note in the paper the depositor must identify
himself to the bank)
B hands over ZKP(Ra), Xa, and fresh coin f(Rb,Xb) to the bank
bank checks ZKP(Ra) is valid against issued coin list
bank puts serial number Xa in spent coin list
bank adds f(Rb,Xb) to issued coin list
3. A revokes coin
A hands over Ra and Xa to bank
bank links Xa to f(Rb,Xb) because they were presented simultaneously
bank removes f(Rb,Xb) from issued coin list revoking that coin
I think this is why Sander & Ta-Shma claim resistance to the "black
mail attack".
However, a simple protocol variation on the part of the blackmailer
allows him to avoid coin revocation. He simply exchanges the coin
twice. eg. there is a step 2a in the above protocol:
2a. B deposits new coin again to get 2nd new coin C
B hands over ZKP(Rb), Xb, and fresh coin f(Rc,Xc) to the bank
bank checks ZKP(Rb) is valid against issued coin list
bank puts serial number Xb in spent coin list
bank adds f(Rc,Xc) to issued coin list
now step 3 no longer works after 2a has completed because Xa can't be
used to link to f(Rc,Xc)
Therefore I think their claim that the protocol is resistant to the
blackmail attack is incorrect. Also my earlier claim that it is
revocable is wrong, if you use this 2 step deposit protocol. And,
with 2 step deposit it is again a final settlement; the blackmailer
doesn't release the hostage until the 2nd step has completed.
> > However, while perhaps it is nice to be able to diffuse the blackmail
> > attack argument, it seems to me that this method of doing so means
> > that you no longer have instant final settlement, because the payer
> > can go demand refund from the bank, and the bank in this case does
> > have recourse -- it can revoke the payment, even though it can't
> > identify the payee.
>
> No, once the coin is deposited there is no way to invalidate it after
> the fact. The ZK proof was only offered in the context of the list as it
> was at that moment, and there is no way to say, "the list has changed,
> let's go back and see which ZK proof transcripts are now invalid".
If the ZKP is non-interactive, the force of the proof against the
state of the list it was issued against remains in perpetuity. Yes?
> They would all be invalid once the list changes. There is no way to
> single out the particular one which was invalidated by the removal of
> a coin from the list. Hence settlement is still final.
Before it has been spent by the blackmailer the coin can be revoked as
described above. Perhaps you were already working from the assumption
that the coin is immediately spent, or exchanged a 2nd time, in which
case I agree.
Adam
