Is the following digicash protocol possible?

A question about offline digicash:

Is it possible to arrange digicash as follows:

If A, the original issuer, issues a unit of digicash to 
to B, and B gives it to C, and C gives it to D, and D,
gives it to E, and E cashes it with A,  --  and
everyone colludes except C and D, it is impossible
to prove that C got this unit from D.

If A, the original issuer, issus a unit of digicash to 
to B, and B gives it to C, and C gives it to D, and D,
gives it to E, and E cashes it with A,  --  and
C double spends it to D', who then gives it to E'
who then attempts to cash it with A, -- then A
will detect the double spending and rebuff the attempt,
E' will complain to D', and D', with information
supplied by E' and A, can then prove that C dishonorably 
double spent the money, without discovering that C gave 
the money to D, and hence without discovering that D 
gave the money to E.



-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com

jamesd@netcom.com (James A. Donald) writes:

>A question about offline digicash:

>Is it possible to arrange digicash as follows:
(I have rearranged James' two paragraphs)

>If A, the original issuer, issus a unit of digicash to 
>to B, and B gives it to C, and C gives it to D, and D,
>gives it to E, and E cashes it with A,  --  and
>C double spends it to D', who then gives it to E'
>who then attempts to cash it with A, -- then A
>will detect the double spending and rebuff the attempt,
>E' will complain to D', and D', with information
>supplied by E' and A, can then prove that C dishonorably 
>double spent the money, without discovering that C gave 
>the money to D, and hence without discovering that D 
>gave the money to E.

There are protocols to do essentially this, although they get
rather complicated.  It is necessary for each person in the chain
to have some knowledge of the person he is passing the money to,
so that he can confirm that that person is in fact revealing something
about himself that will incriminate him if he double-spends.  If all
parties in the transactions are totally anonymous then there is no
hope of tracking down a double-spender.

>If A, the original issuer, issues a unit of digicash to 
>to B, and B gives it to C, and C gives it to D, and D,
>gives it to E, and E cashes it with A,  --  and
>everyone colludes except C and D, it is impossible
>to prove that C got this unit from D.

My reading of Chaum's paper "Transferred Cash Grows in Size" is that
if you have a system to satisfy the 1st paragraph, it cannot also satisfy
this.  It appears that if B, E and the bank collude, and B knows he gave
the cash to C and E knows that he got it from D, then they can tell that
C gave it to D.  Basically B recognizes the money E got from D, with
the bank's help.  Although Chaum wrote as though his results applied to
any conceivable transferrable double-spending-detecting cash system,
it wasn't clear to me how general his results really were.

Hal Finney

> A question about offline digicash:
> 
> Is it possible to arrange digicash as follows:
> 
> If A, the original issuer, issues a unit of digicash to 
> to B, and B gives it to C, and C gives it to D, and D,
> gives it to E, and E cashes it with A,  --  and
> everyone colludes except C and D, it is impossible
> to prove that C got this unit from D.

I assume you mean the last line to read "to prove that D got
this unit from C".

Chaum has demonstrated (In a paper I discussed here a little
over a month ago) that when A, B and E collude they can be sure
that the cash D gave to E is part of the same banknote that B
gave to C.

HOWEVER, it is possible to design a protocol such that
it is NOT possible for A, B and E to be sure that C gave
his money directly to D. (i.e. a protocol can be designed
such that A, B and E can not rule out the possibility that
the cash went from C to F to G to H to I to J to D. Thus,
the solution for entities that are worried about having
their cash marked is to exchange banknotes anonymously
with randomly selected entities before using them again.

> If A, the original issuer, issus a unit of digicash to 
> to B, and B gives it to C, and C gives it to D, and D,
> gives it to E, and E cashes it with A,  --  and
> C double spends it to D', who then gives it to E'
> who then attempts to cash it with A, -- then A
> will detect the double spending and rebuff the attempt,
> E' will complain to D', and D', with information
> supplied by E' and A, can then prove that C dishonorably 
> double spent the money, without discovering that C gave 
> the money to D, and hence without discovering that D 
> gave the money to E.

Anonymous e-cash can be created such that the identity
of the cheat is immediatelly known as soon as the second
copy of the banknote (or of a part of the banknote)
reaches A. I should think that any protocol which requires
backtracking would be highly undesirable (i.e. D' and
idealy E' should not be bothered).

Cheers,

Jason W. Solinsky