Consumer privacy is an important goal of electronic payment systems. Some researchers have approached this question by adopting a token-based model. These tokens are meant to act as a type of currency: they can be used to purchase a good, but like coins, they do not reveal the identity of the holder. These systems offer privacy in making a purchase. Some typical examples of token-based electronic payment protocols (``digital cash'' protocols) are [2, 3, 7, 5, 15]. These protocols provide consumers with the ability to make anonymous purchases, purchases which can not be tracked by a bank to identify the purchaser. A stronger form of anonymity can be considered -- anonymity in which the identity of the purchaser is hidden from both the bank and the merchant selling the goods.
But what happens when things go wrong? If the network (or merchant server) goes down during a purchase, how can users complain about non-delivered goods? If their purchases are anonymous, how can they prove that they really did pay and did not receive the goods? How can electronic judges and merchants adjudicate these complaints? How can they determine whether the consumer was really denied the goods, or whether the consumer is just trying to illegitimately acquire merchandise for free? And how can a consumer obtain satisfaction when the purchase is anonymous? These questions are especially important because the Internet today is an unreliable network -- anyone who has spent some time browsing the web knows that communications often fail. Unscrupulous consumers and merchants will certainly attempt to take every advantage of system failures.
To illustrate the problem, consider the following simplified digital cash protocol: consumers pay for electronic goods with tokens. These tokens are anonymous, but designed so that if the consumer ever uses the same token twice, the consumer's identity is revealed. Suppose a consumer pays for a good, but before she can receive acknowledgment that the merchant received payment, the network fails. Now, what can the consumer do? She doesn't know whether the merchant received the payment or not. She has two basic strategies:
A standard approach to addressing the question of reliability is the notion of ACID (atomic, consistent, isolated, durable) transactions [10]. In the distributed systems community, ACID transactions have been widely adopted as the standard mechanism for realizing distributed transactions. The payment transactions should be failure-atomic, so that failures in parts of the system will not leave the entire system in some ambiguous, intermediate state.
How can we interpret these transactions in the context of electronic commerce? Tygar [17] has proposed using the classification below. Tygar began by assuming a model where consumers are purchasing electronic goods and services that will be delivered over a network (such as WWW page, for example). For tangible physical goods, alternative definitions are required to properly satisfy the atomicity property (motivating a multi-billion dollar industry in tracked, receipted courier delivery of messages and packages!) Tygar defines three classes of atomicity for electronic goods.
Using this classification, we can see that the simplified digital cash protocol described above is not money atomic. The obvious question is: are anonymous atomic transactions possible? [17] This has been an open question.
Our first attempt to solve this question would be to use standard techniques to make a digital cash transaction atomic. The standard method for doing this is two-phase commitment [1, 9, 10, 11, 12]. In short, in two-phase commitment, one party assumes the role of transaction coordinator. That party knows and records the identities of all other parties in a non-volatile log. Each of the parties records its state before the transaction begins. As the transaction moves forward, various parties complete their required computation. Before changing the permanent store of those values, the parties send a message to the coordinator indicating that they are ready to commit. (Alternatively, they may abort the transaction by sending a negative message to the coordinator.) After receiving ready messages from all parties, the coordinator issues a commit message to all parties, causing the transaction to become permanent. Alternatively, if the coordinator receives an abort request or if the coordinator can not establish contact with one of the parties, the coordinator can abort the transaction by sending an abort message; in that case, all parties reverse the computation that they conducted towards the transaction.
So, as we see, the two-phase commit protocol requires that at least one party participating in the protocol (the transaction coordinator) knows the identity of all the parties involved. Additionally, two-phase commit assumes a fail-stop fault model, where the parties to the protocol can fail by stopping due to a crash, but not by lying or otherwise trying to cheat. In electronic commerce protocols, of course, we must be able to tolerate arbitrary Byzantine faults; one way to do this is to provide sufficient auditing information to detect these faults and later assign responsibility. This makes the standard two-phase commit protocol inappropriate for use in anonymous electronic commerce systems.
An alternative approach to this problem was attempted by Jakobsson [14], where the payment protocol is divided into two halves. Here, the digital cash is ``rip-spent'': after the first half of the spending protocol, the consumer has committed to buying from the merchant but has not yet spent the money -- some partial information is transferred, so that if the consumer attempts to abort the transaction, the digital cash is either lost (becomes unsable), or the identity of the consumer is revealed. This approach, unfortunately, is not satisfactory: each of the half protocols themselves may be interrupted, leaving the digital cash again in an ambiguous state.