The issue with off-line cash is this: has the coin being offered already
been spent?
With on-line cash, the offered coin is immediately deposited at the bank,
hence doubly-spent coins are detected instantly. With off-line cash
this cannot be done because by definition there is no connection to the
bank. Hence there is no way to know, off-line, if a coin has already
been spent.
The solution is to embed the identity of the withdrawer into the coin
when it is withdrawn from the bank, in such a way that this identity
will only be revealed if the coin is double-spent. That provides a
partial solution to the off-line scenario.
A coin is offered off-line, and the recipient again has no guarantee that
it hasn't been spent already. He accepts the coin anyway, and later when
he gets on-line he tries to deposit it at the bank. But he learns that
he was cheated; the coin had already been spent. Now he has a fall-back
solution: the doubly-spent coin reveals the embedded identity of the
party who withdrew it (and who doubly-spent it). He can call the cops
and try to track down and prosecute the cheater.
All off-line spending schemes work this way. All they can offer is
the hope of tracking down cheaters after the fact. They can never
offer the assurance of validity that an immediate on-line check can
provide.
With off-line coins, unlike on-line coins, the spender knows more than
he's telling. He knows secrets about those coins which would reveal his
identity; that is, his identity is embedded in some secret information
associated with the coin. When he spends it at a shop, he responds
to a random challenge from the shop, using his secret information.
The system is set up so that the shop, and later the bank, can validate
his response as being valid, proving that he truly owned a coin. For the
double-spending detection, the system is further arranged that if two
different shops offer two different random challenges, then from the
responses to these two challenges, the user's secret information and
therefore his identity is revealed.
To turn this into a transferrable system, we would allow a chain of
transfers before the bank gets involved. Alice spends the coin with Bob,
who spends it with Carol, who spends it with David, who deposits it at
the bank. There are two problems. First, only Alice knows the secret
information associated with the coin. She can't give all the secrets to
Bob, or else he would know her identity. So Bob only has a limited amount
of information about the coin. Second, after this chain of transfers,
if there was double-spending, it might have been anyone along the chain.
The system for double-spending detection has to be able to identify
which person was the cheater.
The solution which Adam describes works as follows. Each party
pre-withdraws a zero-value coin from the bank. This is an off-line
coin which has their identity encoded in it, if they double-spend it.
Alice first spends her coin with Bob in the normal off-line way. Bob ends
up with a transcript sufficient to prove that he received a presumably
valid coin from Alice (but one which might have been doubly-spent).
Now Bob wants to spend with Carol. He does two things: he gives her
the transcript of Alice's spend with him, which implicitly identifies
the value of the coin; and also he engages in the regular off-line
coin spend with her, using his zero-value coin.
If Carol then spends the coin with David, she does the same two things:
she gives David the transcript of Bob's spend with her (which itself
included the two parts above), and also spends a zero-value coin with
him. The resulting transcript now has three parts.
So it grows at each transfer, and in the end the transcript is deposited.
If there was a double-spend, someone spent his zero-value coin twice,
and his own identity is revealed.
There is one flaw, which is that Bob could use the same Alice transaction
with more than one zero-value coin, which he after all gets for free.
Carol can't tell that the Alice transaction she sees is the same one
someone else saw, and if Bob uses a unique zero-value coin for each spend,
then Bob's identity will not be revealed as it should be.
The fix for this is that when Bob receives the coin from Alice, knowing
that he is going to pass it on, he must link the specific zero-value coin
he will later use into the transcript he will receive of Alice's spend
with him. This is done by including a hash of the coin information into
the random challenge he sends to Alice. Then when he tries to pass the
coin on to Carol, she checks that the zero-value coin he is spending with
her matches the value used in the Alice transcript. That prevents Bob
from using two different zero-value coins with a single Alice transcript.
So it works, but broadly speaking there are two problems. First, off-line
coins suck, as described above. And second, because they grow, it is
possible to tell exactly how many hands a particular coin has
