 |
Claims  |
|
|
What we claim is:
1. A fault-tolerant method of purchasing digital goods with a digital token in which the token's value resides either with a customer or with a merchant, comprising the steps
of:
initiating a transaction with a merchant for a digital good;
sending a merchant-signed invoice and the digital good in encrypted form from the merchant to a customer;
signing the invoice with the customer's signature to produce a countersigned invoice;
sending the countersigned invoice, a token, and identifying information for the token from the customer to the merchant;
sending the countersigned invoice, the token, and the identifying information for verification;
verifying the token with the identifying information and verifying the other information in the countersigned purchase order;
committing the transaction when the token and other information in the countersigned purchase order are verified such that the value of the token is transferred from the customer to the merchant;
completing the transaction by making a key for decrypting the digital good available to the customer; and
retaining records of the transaction.
2. The method of claim 1 wherein said step of sending identifying information for the token includes the step of sending a hash of the token.
3. The method of claim 2 wherein said step of sending the countersigned invoice for verification includes the step of sending the countersigned invoice to an archive for verification.
4. The method of claim 1 wherein said step of verifying the other information in the countersigned invoice includes the step of determining if the price of the goods and the value of the token are the same.
5. The method of claim 1 additionally comprising the step of communicating to the merchant's bank the transfer of the token's value to the merchant.
6. The method of claim 1 wherein said step of retaining records includes the step of storing the identifying information and the token.
7. The method of claim 1 additionally comprising the steps of:
sending verification information for the encrypted digital good with the merchant-signed invoice from the merchant to the customer;
calculating corresponding verification information for the received encrypted digital good;
comparing the calculated verification information to the received verification information; and
one of terminating the purchase or resending the encrypted digital good if the verification information is not the same.
8. The method of claim 1 wherein said token is an anonymous token and wherein said identifying information includes registration information.
9. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
transferring the digital good in an encrypted form from the merchant to a customer;
locking at least a portion of the value of the token to the transaction;
sending a digital token and transactional information to the merchant;
verifying the transactional information and the value of the token;
providing a decryption key to the customer;
unlocking said locked value of the token and transferring said value to the merchant; and
retaining a record of the transaction.
10. The method of claim 9 wherein said step of verifying the value of the token includes the step of verifying if the value of the token has been previously spent.
11. The method of claim 9 wherein said step of providing the decryption key to the customer includes the step of sending the key to the customer.
12. The method of claim 9 additionally comprising the step of reusing the token until the entire value of the token is transferred.
13. The method of claim 9 wherein said step of sending the digital token includes the step of sending an anonymous token and identifying information.
14. The method of claim 9 wherein the token has a key associated therewith, said method including the step of generating a customer signature with the key associated with the token, and wherein said step of sending transactional information
includes the step of sending the customer signature.
15. The method of claim 9 wherein said step of sending a token includes the step of sending multiple tokens.
16. The method of claim 15 wherein each token has a key associated therewith, said method including the step of generating customer signatures with the keys associated with the tokens, and wherein said step of sending transactional information
includes sending the generated signatures.
17. The method of claim 9 wherein said step of verifying the transactional information includes the step of determining if the price of the goods and the value of the token are the same.
18. The method of claim 9 additionally comprising the step of communicating to the merchant's bank the transfer of the token's value to the merchant.
19. The method of claim 9 wherein said step of sending transactional information includes the step of sending a public half of a customer chosen asymmetric key pair.
20. The method of claim 9 wherein said step of verifying the value of the token is performed by one of a bank, the merchant, or an archive.
21. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
locking at least a portion of the value of the token to the transaction;
sending an entity signed purchase approval including a digital token and transactional information to the merchant;
transferring the digital good in an encrypted form from the merchant to a customer after the value of the token is locked to the transaction;
providing a decryption key to the customer;
unlocking said locked value of the token and transferring said value to the merchant; and
retaining a record of the transaction.
22. The method of claim 21 wherein said step of initiating a transaction includes the step of sending a merchant signed invoice from the merchant to the customer.
23. The method of claim 21 wherein said step of locking at least a portion of the value of the token includes the step of sending a customer signed purchase authorization from the customer to an entity for verification.
24. The method of claim 21 wherein said entity performs the step of sending the entity signed purchase approval.
25. The method of claim 24 additionally comprising the step of verifying the entity signed purchase approval.
26. The method of claim 25 wherein said step of verifying the entity signed purchase approval is performed by one of the merchant or an archive.
27. The method of claim 26 wherein the merchant forces the transaction to commit by sending a copy of the message transferring the digital good and a copy of the message verifying the entity signed purchase approval to an archive.
28. The method of claim 27 wherein the decryption key is encoded.
29. The method of claim 21 wherein said step of transferring the encrypted digital good includes the step of transferring a merchant signature with the encrypted good.
30. The method of claim 29 additionally comprising the steps of adding a customer signature to the merchant signature and sending the encrypted good and the signatures from the customer to the merchant.
31. A method for purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
transferring the digital good in an encrypted form from the merchant to a customer;
sending a digital token and transactional information to an entity for verification;
locking at least a portion of the value of the token to the transaction;
verifying the transactional information and the value of the token;
providing a decryption key to the entity;
unlocking said locked value of the token and transferring said value to the merchant;
completing the transaction by making the key available to the customer; and
retaining a record of the transaction.
32. The method of claim 31 wherein said step of transferring the digital good includes the step of sending a merchant signed invoice and the encrypted digital good from the merchant to the customer.
33. The method of claim 31 wherein said step of sending transactional information includes the step of sending a customer-signed authorization from the customer to an entity for verification.
34. The method of claim 31 wherein said step of providing a decryption key to the entity includes the step of sending a merchant-signed key from the merchant to the entity.
35. The method of claim 31 wherein said step of completing the transaction includes the step of sending an entity-signed key from the entity to the customer and wherein said step of unlocking said locked value of the token includes the step of
sending an entity-signed unlocked value of the token from the entity to the merchant.
36. The method of claim 31 wherein said step of verifying the value of the token includes the step of verifying if the value of the token has been previously spent.
37. The method of claim 31 wherein said step of providing the decryption key to the entity includes the step of storing the key at an archive which both the entity and the merchant can access.
38. The method of claim 37 additionally comprising the step of verifying that an expiration time for the transaction has not passed before the decryption key is stored at the archive.
39. The method of claim 37 additionally comprising the step of the archive countersigning the decryption key and wherein said step of retaining records includes the step of retaining the countersigned decryption key.
40. The method of claim 39 additionally comprising the step of the merchant demonstrating that the value of the token has been transferred by providing a copy of the archive countersigned decryption key.
41. The method of claim 31 wherein the value of the token remains locked until the transaction is one of aborted or completed by providing the decryption key to the customer.
42. The method of claim 31 wherein said step of providing the decryption key to the entity includes the step of sending the key to the entity.
43. The method of claim 31 additionally comprising the step of reusing the token until the entire value of the token is transferred.
44. The method of claim 31 wherein said step of sending the digital token includes the step of sending an anonymous token and identifying information.
45. The method of claim 31 wherein the token has a key associated therewith, said method including the step of generating a customer signature with the key associated with the token, and wherein said step of sending transactional information
includes the step of sending the customer signature.
46. The method of claim 31 wherein said step of sending a token includes the step of sending multiple tokens.
47. The method of claim 46 wherein each token has a key associated therewith, said method including the step of generating customer signatures with the keys associated with the tokens, and wherein said step of sending transactional information
includes sending the generated signatures.
48. The method of claim 31 wherein said step of verifying the transactional information includes the step of determining if the price of the goods and the value of the token are the same.
49. The method of claim 31 additionally comprising the step of communicating to the merchant's bank the transfer of the token's value to the merchant.
50. The method of claim 31 wherein said step of sending transactional information includes the step of sending a public half of a customer chosen asymmetric key pair.
51. The method of claim 31 wherein said step of verifying the value of the token is performed by one of a bank, the merchant, or an archive.
52. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
transferring the digital good in an encrypted form from the merchant to a customer;
sending a digital token and transactional information to an entity for verification;
locking at least a portion of the value of the token to the transaction;
verifying the transactional information and the value of the token;
providing a decryption key to the customer;
unlocking said locked value of the token and transferring said value to the merchant;
retaining a record of the transaction; and
repeating the foregoing steps until a sequence of transactions is completed.
53. A fault-tolerant method of purchasing digital goods with a digital token in which the delivery of goods is atomic, comprising the steps of:
establishing a price with a merchant for a digital good;
sending a merchant-signed invoice and the digital good in encrypted form from the merchant to a customer;
sending a customer-signed purchase authorization including the token from the customer to a bank for verification;
verifying the customer-signed purchase authorization;
sending a bank-signed purchase approval from the bank to the merchant for verification;
verifying the bank-signed purchase approval;
completing the transaction by making the key for decrypting the digital good available to the customer; and
retaining records of the transaction.
54. A fault-tolerant method of purchasing digital goods with a digital token in which the token's value resides either with a customer or with a merchant, comprising the steps of:
initiating a transaction with a merchant for a digital good;
sending a merchant-signed invoice and the digital good in encrypted form
from the merchant to a customer;
signing the invoice with the customer's signature to produce a countersigned invoice;
sending the countersigned invoice, a token, and identifying information for the token, including a hash of the token, from the customer to the merchant;
sending the countersigned invoice to an archive for verification, wherein said archive stores the hash of the token in conjunction with a key for the token;
sending the token and the identifying information for verification;
verifying the token with the identifying information by using the key stored in conjunction with the hash of the token, and verifying the other information in the countersigned purchase order;
committing the transaction when the token and other information in the countersigned purchase order are verified such that the value of the token is transferred from the customer to the merchant;
completing the transaction by making a key for decrypting the digital good available to the customer; and
retaining records of the transaction.
55. A fault-tolerant method of purchasing digital goods with a digital token in which the token's value resides either with a customer or with a merchant, comprising the steps of:
initiating a transaction with a merchant for a digital good;
sending a merchant-signed invoice and the digital good in encrypted form from the merchant to a customer;
signing the invoice with the customer's signature to produce a countersigned invoice;
sending the countersigned invoice, a token, and identifying information for the token from the customer to the merchant;
sending the countersigned invoice, the token, and the identifying information for verification;
verifying the token with the identifying information and verifying the other information in the countersigned purchase order;
committing the transaction when the token and other information in the countersigned purchase order are verified such that the value of the token is transferred from the customer to the merchant;
completing the transaction by making a key for decrypting the digital good available to the customer; and
storing the identifying information, the token, and the countersigned invoice.
56. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
transferring the digital good in an encrypted form from the merchant to a customer;
locking at least a portion of the value of the token to the transaction;
sending a digital token and transactional information to the merchant;
verifying the transactional information and the value of the token;
storing a decryption key at an archive which both the customer and the merchant can access;
unlocking said locked value of the token and transferring said value to the merchant; and
retaining a record of the transaction.
57. The method of claim 56 additionally comprising the step of verifying that an expiration time for the transaction has not passed before the decryption key is stored at the archive.
58. The method of claim 56 additionally comprising the step of the archive countersigning the decryption key and wherein said step of retaining records includes the step of retaining the countersigned decryption key.
59. The method of claim 58 additionally comprising the step of the merchant demonstrating that the value of the token has been transferred by providing a copy of the archive countersigned decryption key.
60. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
transferring the digital good in an encrypted form from the merchant to a customer;
locking at least a portion of the value of the token to the transaction;
sending a digital token and transactional information to the merchant;
verifying the transactional information and the value of the token;
providing a decryption key to the customer;
unlocking said locked value of the token and transferring said value to the merchant; and
retaining a record of the transaction, wherein the portion of the value of the token remains locked until the transaction is one of aborted or completed by providing the decryption key to the customer.
61. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
transferring the digital good in an encrypted form from the merchant to a customer;
locking at least a portion of the value of the token to the transaction;
sending a digital token and transactional information to the merchant;
verifying the transactional information and the value of the token;
providing a decryption key to the customer;
sending a hash of the encrypted digital good to the customer;
calculating a hash of the received encrypted digital good;
comparing the calculated hash to the received hash;
one of aborting the transaction or resending the encrypted digital good if the hashes are not equal;
unlocking said locked value of the token and transferring said value to the merchant; and
retaining a record of the transaction.
62. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
locking at least a portion of the value of the token to the transaction;
the entity sending an entity-signed purchase approval including a digital token and transactional information to the merchant;
one of the merchant and an archive verifying that the entity signed the purchase approval;
transferring the digital good in an encrypted form from the merchant to a customer after the value of the token is locked to the transaction;
the merchant forcing the transaction to commit by sending a copy of a message transferring the digital good and a copy of a message verifying that the entity signed the purchase approval to the archive;
providing a decryption key to the customer, wherein the decryption key is encoded using a one-time pad;
unlocking said locked value of the token and transferring said value to the merchant; and
retaining a record of the transaction.
63. A method of purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
locking at least a portion of the value of the token to the transaction;
sending an entity-signed purchase approval including a digital token and transactional information to the merchant;
transferring the digital good in an encrypted form from the merchant to a customer after the value of the token is locked to the transaction;
storing a decryption key at an archive which both the customer and the merchant can access;
unlocking said locked value of the token and transferring said value to the merchant; and
retaining a record of the transaction.
64. A method for purchasing digital goods with a digital token belonging to a customer in which the value of the token resides with only one party at a time, comprising:
initiating a transaction with a merchant for a digital good;
transferring the digital good in an encrypted form from the merchant to a customer;
sending a digital token and transactional information to an entity for verification;
locking at least a portion of the value of the token to the transaction;
verifying the transactional information and the value of the token;
sending a hash of the encrypted digital good to the customer;
calculating a hash of the received encrypted digital good;
comparing the calculated hash to the received hash;
one of aborting the transaction or resending the encrypted digital good if the hashes are not equal;
providing a decryption key to the entity;
unlocking said locked value of the token and transferring said value to the merchant;
completing the transaction by making the key available to the customer; and
retaining a record of the transaction. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND
1. Field
The present disclosure is directed generally to communications protocols, and more particularly to methods of carrying out commercial transactions over a computer network.
2. Description
There is a trade-off between anonymity and reliability in transactions in all current electronic commerce systems. The relationship between anonymity and atomicity in electronic transactions is an open question. Some systems make reliability
paramount and limit anonymity. Some systems attempt to provide both by providing conditional anonymity. Some systems provide anonymity at the price of reliability.
U.S. patent application Ser. No. 519,074, filed Aug. 24, 1995 and entitled Method and Apparatus for Purchasing and Delivering Digital Goods Over a Network, which application is assigned to the same assignee as the present invention, discloses
a method for conducting an atomic transaction in which delivery of digital goods is carried out in a certifiable manner. In that protocol, provision is made for allowing transactions to take place under pseudonyms. However, the protocol is designed to
provide the merchant with a customer identity, albeit a pseudonym. Thus, the need exists for an atomic transaction protocol that is anonymous.
There has been other work on Electronic commerce systems that:
provide methods for anonymous payment (type 1) or
provide highly atomic protocols so that receiving a merchandise item is strongly associated with paying for the same merchandise (type 2).
Type 1 methods (anonymous payment) have revolved around protecting customer privacy through the use of token-based electronic payment protocols (so-called "digital cash" protocols.) These tokens are meant to act as a type of currency: they can be
used to purchase merchandise, but like coins, they do not reveal the identity of the holder. These systems offer privacy in making a purchase. They provide customers with the ability to make anonymous purchases, purchases which cannot 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 merchandise. This raises the question of how the merchant will transmit the merchandise to
the consumer without knowing the consumer's identity. A standard way of accomplishing this is through the use of intermediaries known as anonymizers or anonymous forwarders. If we have non-trackable tokens, then it is straightforward to use anonymizers
to realize purchases that are anonymous to merchants, banks, and third parties.
The present prior art systems, however, are not fault tolerant. That is, ambiguous states arise when things go wrong. For example, if the network or merchant server goes down during a purchase, there is no mechanism to complain about
non-delivered goods. If the purchases are anonymous, there is no way to prove that the customer really did pay and did not receive the merchandise. There is no trail to enable automated judges to adjudicate these complaints. Existing protocols are not
sufficiently robust to enable judges or merchants to determine whether the customer was really denied the merchandise or whether the customer is just trying to illegitimately acquire merchandise for free. There is no mechanism in place to enable a
customer to 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 World Wide Web knows that communications often
fail. Unscrupulous customers and merchants will certainly attempt to take every advantage of system failures.
To illustrate the problem, consider the following simplified digital cash protocol: customers pay for digital merchandise with tokens. These tokens are anonymous, but designed so that if the customer ever uses the same token twice, the
customer's identity is revealed. Suppose a customer pays for merchandise, but before she can receive acknowledgment that the merchant received payment, the network fails. Because the customer doesn't know whether the merchant received the payment or
not, she has two basic strategies.
The first strategy is to spend the token again, by returning her token to the bank or spending it with a second merchant. But then, if the first merchant really did receive the token, she may be creating a race condition (i.e., a situation
where, depending on timing, an inconsistent state may be created.) Whoever gets the token to the bank first will get the money. Worse, when both tokens do reach the bank, the customer will be accused of double-spending. One can imagine variations on
the digital cash protocol where a customer might file a special type of complaint with a bank, but the design of this variation is non-trivial. Most types of variations will either reveal the customer's identity, allow a new type of fraud, be subject to
ambiguous results if a message is not delivered, or have other undesirable effects. This topic is considered at length in: L. Jean Camr, Marvin Sirbu, and J. D. Tygar, Token and notational money in electronic commerce, In Proceedings of the First USENIX
Workshop in Electronic Commerce, pages 1-12, July 1995; J. D. Tygar, Atomicity in electronic commerce, In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 8-26, May 1996 (based on a presentation given in
August 1995.); and Bennet S. Yee, Using Secure Coprocessors, PhD thesis, Carnegie Mellon University, 1994.
The second strategy is to wait and not spend the money. But in that case, the customer has locked up her funds. If the merchant did not receive her payment, then the customer may be waiting for a very long time.
Methods of type 2 have addressed the question of reliability through the use of ACID (atomic, consistent, isolated, durable) transactions. See, for example, J. Gray and A. Reuter, Transaction Processing, Morgan-Kaufmann, 1993. These protocols
have achieved fault-tolerance, that is, the ability to handle arbitrary communication failures and component failures of any party. In any case, the distributed system should always be in a consistent state: parties should agree on whether a transaction
succeeded or not; when repairs are made, the distributed system should be able to continue processing without interruption.
In the distributed systems community, ACID transactions have been widely adopted as a standard mechanism for realizing fault-tolerant distributed transactions. 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.
The literature has suggested that these transactions be interpreted in the context of electronic commerce by using the classifications set forth below. Suppose we have a model where customers are purchasing digital merchandise and services that
will be delivered over a network (e.g. a World Wide Web page). For tangible physical merchandise, 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). The literature (See, for example, Tygar, Supra.) gives three classes of atomicity for digital merchandise.
Money atomic transactions feature atomic transfer of electronic money--the transfer either completes entirely or not at all. In money atomic protocols, money is not created or destroyed by purchase transactions.
Goods atomic transactions are money atomic and also ensure that the customer will receive merchandise if and only if the merchant is paid. Goods atomic transactions provide an atomic swap of the digital merchandise and funds--similar to the
effect of "cash on delivery" parcels.
Certified delivery protocols are goods atomic and also allow both the customer and merchant to prove exactly what was delivered. If there is a dispute, this evidence can be shown to a judge to prove exactly what merchandise were delivered.
Using this classification, we can see that the simplified digital cash protocol described above is not money atomic.
Additional problems are raised in an anonymous atomic transactions. Indeed, the literature has speculated that anonymous atomic transactions might not even be possible. A traditional attempt to solve this question might be to use standard ACID
techniques to make a digital cash transaction atomic. The most common method for ACID transactions is two-phase commitment. 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 archive. 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 cannot 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.
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 or system failure, but not by lying or otherwise trying to cheat. In electronic commerce protocols, of course, we must be able to tolerate arbitrary faults (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, Ripping coins for a fair exchange, In Louis C. Guillou and Jean-Jacques Quisquater, editors, Advances in Cryptology: Eurocrypt '95 Proceedings, Springer-Verlag 1995, 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 customer has committed to buying from the merchant but has not yet spent the money--some partial information is
transferred, so that if the customer attempts to abort the transaction, the digital cash is either lost (becomes unusable), or the identity of the customer is revealed. This approach is not satisfactory: each of the half protocols themselves may be
interrupted, leaving the digital cash again in an ambiguous state. Thus, the need exists for a fault tolerant, atomic, transaction protocol that can maintain the anonymity of the customer.
SUMMARY
In this disclosure, we disprove the commonly held belief that an atomic transaction (money atomic, goods atomic, certified delivery) cannot be accomplished anonymously. We present a protocol and several variations for electronic commerce
transactions which combine anonymity and atomicity while requiring very limited trust assumptions. We also discuss the goods atomicity properties of the protocols.
The disclosed system has four elements: a customer, a bank, a merchant and a public archive. The bank can issue verifiable token currency. The technique for creating or verifying a token is known in the art and not considered here. The
customer can generate primes and composites necessary for a public key set. A customer can sign documents and verify signatures. A merchant can verify public key signatures, sign documents and accept payment. The archive can create write-once records,
sign documents and verify signatures. Those capabilities imply certain security assumptions: that the secret key of a set of public keys is not disclosed and that the bank can distinguish those tokens to be used with certified delivery and refuse
deposit of them without archive approval.
There are four functions that need to be distinguished in the disclosed protocol. There is a one way collision free hash function, and public and private key encryption. Those are denoted as follows, when the variable being encrypted or hashed
is x:
h(x) the hash of x
E.sub.k (x) | | |
