Xiaoling Dai, School of Multimedia Information Technology, Southern Cross University, PO Box 157, Lismore, NSW 2480, Australia xdai10@scu.edu.au
Bruce W N Lo, School of Multimedia Information Technology, Southern Cross University, PO Box 157, Lismore, NSW 2480, Australia blo@scu.edu.au
One of the major challenges of electronic payment systems is the high cost associated with the processing of payments. This is particularly serious in transactions where the transaction amount is small. This paper introduces Netpay, a secure, economical, easily implementable, and debit-based protocol for a micropayment system for the WWW. Netpay differs from previous protocols in the following aspects: Netpay uses touchstones signed by the broker and indices signed by vendors and passed to other vendors. The signed touchstone is used to verify the electronic currency - paywords, and the signed index is used to prevent double spending by customers and to resolve disputes between vendors.
The rapid growth of the Internet has led to the appearance of thousands of different web sites, which are created to provide information to millions of people around the world. Producing and maintaining a quality web site takes a great deal of time, dedication and money. To help offset the development costs, web site producers are keen to use their site as a source of income. Therefore, an efficient system to handle such a trade is needed. Because the transactions involve only a small amount of money, such a system is called a micropayment system. An Internet micropayment system would allow small amounts of money to be spent at web sites in exchange for content or services. Micropayment system's designs are usually quite different from the existing "macro-payment" systems, since micropayment systems must be very simple, secure, and efficient, with a very low overhead cost per transaction.
Currently there are a number of different payment systems at various stages of development. These range from proposals in research literature to systems currently in commercial trials. Payment systems are often classified as either on-line or off-line. Example of on-line payment system include DigiCash [HREF1], NetBill [HREF2]. In an on-line payment system, every payment needs to be authorized by the bank that issued the coin in order to prevent double spending by the customers. This introduces a central bottleneck. A single point of transaction will raise the risk of system failure, reducing system reliability and will also cause transaction traffic congestion, increasing payment latency. It also raises the cost of transactions, and imposes a minimum cost per transaction, as the bank is faced with the real cost of authorizing each transaction.
Protocols that do not rely on a third party to guard against double spending are called offline micropayment protocols, e.g. Agora [HREF3], MPTP [HREF4], Mini-pay [HREF5], PayWord and MicroMint [HREF6]. Typically, these protocols are credit based, since the purchase is made available to the customer before the customer is debited with the payment. In such a system, there is no protection mechanism to prevent a customer from double spending, and spending more than the balance in their account (overspending). Double spending is detected at the time of the clearing process, when the vendor turns in the received coins to their respective banks. Once double spending is detected, the customer is penalized and expelled.
Though offline protocols have received a lot of attention from researchers and cryptographers, no offline payment systems are currently in general public use. The experimental system, Millicent [HREF7] uses no public-key cryptography and is optimized for repeated micropayments to the same vendor. Its distributed approach allows a payment to be validated and double spending prevented without the overhead of contacting a third party (often called broker) online during purchase from same vendor. However the third party must be online whenever the user wishes to interact with a new vendor. The system places a heavy real-time burden on the third party in such circumstances.
In this paper, we present a new protocol called Netpay that allows customers to purchase information from vendors on the WWW without having to involve a third party in every transaction. At same time, Netpay protocol minimises the number of expensive public-key operations (Rivest, Shamir, and Adleman 1979) required per payment. Hash function operations (Rivest 1992) will be used, in order to reduce the transaction overhead. In addition, the Netpay system is capable of preventing customers from double spending, vendors from double depositing and both from forgery. Obviously, the application of Netpay is not limited to purchasing information from web page. It can be applied to the conduct of e-commerce in general where the transaction amount is small.
The proposal micropayment protocol, Netpay, is based on the PayWord [HREF6] system. However, Netpay is a debit-based system and it also addresses the problem of double spending and overspending by the customer. The customers generate their own "coins," or paywords, which are sent to vendors and then verified by brokers. Each customer has a "certificate," a block containing the customer's identity and public key, digitally signed by a broker. When a user wishes to make a purchase at a vendor for the first time in a day, the customer first randomly picks a payword seed wn, where n is a reasonable estimate of the number of purchases a customer would make at a typical vendor in a day. The customer then computes a payword chain by repeatedly hashing wn: wi-1 = h(wi), where i=n, n-1, ..., 1. Before making a purchase the customer sends the vendor a digitally signed commitment which includes the root of the payword chain. The customer then sends the vendor w1 through wm where m is the number of the paywords the customer wish to spend. The vendor can easily verify this chain by hashing wm m times until he reaches w0, along with wm, which the broker uses to credit the vendor's account for m coins. PayWord system is an offline and credit-based scheme where a user's account is not debited until some time after purchases. This provides more opportunity for fraud since a large number of purchases can be made against an account with insufficient funds. The protocol of PayWord does not protect double spending at different vendors. The proposed protocol in this paper attempts to overcome these limitations.
In this section, the details of the micropayment system Netpay will be discussed. Consider a trading community consisting of customer (C), vendor (V), and broker (B). Assume that the broker is honest and is trusted by both the customers and the vendors. The customers and the vendors may be or may not be honest. The vendors and the customers open accounts and deposit funds with the broker. The payment only involves C and V, and B is responsible for the registration of customers and for crediting the vendor's account and debiting the customer's account. We adopt the following notations:
IDa --- pseudonymous identity of any party A in the trade community issued by the broker.
PK-a --- A's public key.
SK-a --- A's digital signature.
{x}SK-a --- x signed by A.
{x}PK-a --- x is encrypted by A's public key.
In any e-commerce transaction, three subtransactions may be identified. There are customer-broker, customer-vendor, and vendor-broker transactions. But the vendor-vendor transaction will be added in this system. How the Netpay protocol works in each subtransaction will now be described in more detail.
Transaction 1: Customer - Broker
Before a customer asks for service from the first vendor (V1), the customer has to send a message M1 which consists of an integer n (the number of paywords in a payword chain the customer applied for), IDc, and the IP address of V1 to the broker.
M1 = { IDc, n, IP address of V1 }
The broker completes two actions:
1. Debit money from the account of C and creates a payword chain W0, W1, W2, ..., Wn, Wn+1 which satisfy Wi = h(Wi+1), where i = n, ..., 0 (here h(.) is a one way hash function). Root W0 is used to verify the validity of the paywords W1, W2, ..., Wn by vendors and the broker. Seed Wn+1 is kept by the broker to be used to prevent the customer from overspending and forging paywords in that chain. The customer only receives W1, W2, ..., Wn that are encrypted by customer's public key from the broker (M2).
M2 = { W1, W2, ..., Wn } PK-customer
2. Computes the touchstone for that chain:
M3 = T = {IDc, W0} SK-broker
and sends it to V1. T is signed by the broker. This touchstone authorises V1 to verify the paywords-using root W0 and may later redeem the paywords with the broker.
The customer-broker transaction guarantees no overspending and forging, and has much less possibility of being attacked. The broker selects the seed Wn+1 to create the payword chain which satisfy Wn = h(Wn+1), Wn-1 = h(Wn), ..., W1 = h(W2), W0 = h(W1) and keep the seed secretly. It is not possible for the customer, the vendor or any outsider to forge paywords in that chain, since none of them have the seed Wn+1. This means they can not generate another paywords in that chain.
Transaction 2: Customer - Vendor
The following sequence of messages describes a transaction between a customer and a vendor in the course of a purchase. The customer and vendor need to agree on the amount that C pays. In a typical situation, the price of a web page may be one-cent, but it could be any other amount.
When a customer makes a purchase from V1, he/she sends a message M4 to V1;
M4 = { IDc, P, O};
where payment P = {(Wj, j), ( Wj+1, j+1), ..., (Wj+m-1, j+m-1)}, m is the number of the paywords the customer wish to spend, and O is an order. For example, to make a one cent payment, the customer sends the first payword W1 with its index 1: P = {(W1, 1)} to V1.
The payment P is verified by the vendor by hashing the paywords Wi's in the payment P. The payword W1 is valid if the hash matches the root of the chain (W0) in the touchstone (W0 = h(W1)). This works because the hash function has the property Wi-1= h(Wi) (i = 1, 2, ..., n) and V1 holds W0. On the other hand, it is hard for V1 to create W1 even though he knows W0 since the generation of a value that would hash to W0 is computationally difficult due to the one-way nature of the hash function. For the same reason, it is also hard for any outsider to generate valid paywords in the chain even if the outsider knows W0. If each payword is worth one cent and each web page costs one cent, then the customer spends W1, W2, ..., Wm to V1 when he/she purchases m web pages from V1. If the payment P is valid, P will be stored for redemption at a later time with the broker. In the meantime the customer is supplied with the goods and an acknowledgment (M5),
M5 = {IDv1, the receipt of the payment}
If the paywords are stolen by an attacker, only the paywords in P can be spent by the attacker, and only to V1. Multiple payments can be charged against the length of the payword chain, until the payword chain is fully spent or the customer no longer requires information goods from vendors.
Transaction 3: Vendor-Vendor Payword Relocation
When a customer wishes to make a purchase at a different vendor V2, he/she sends a message
M6 = {IP address of V1, IDc, P, O}
to V2. V2 transmits
M7 = {IDc, IDv2}
to V1. After examining the receipt, V1 signs the index
Index = {IDv1, IDv2, i}SK-v1
(where i is the label of the last payword V1 received) and then transmits
M8 = {T, Index}
to V2. The index may be used for disputes between the vendors, and the touchstone is used to make future transaction with the customer and to redeem the paywords from the broker. After V2 verifies the touchstone and the Index, and then stores them, the customer is notified with M9.
M9 = {IDv2, the receipt of the payment}
This transaction has two advantages: firstly, the transfer of the message M8 from V1 to V2 does not involve the broker, it reduces the communication burden of the broker; secondly, the message M8 includes the index of the paywords, it prevents the customer from double spending when the customer purchases from another vendor.
Transaction 4: Vendor - Broker Offline Redeem Processing
At the end of each day (or other suitable period), for each chain, the vendor must send the following message to the broker
M10 = {IDc, IDv, P}
The broker needs to verify each payword received from the vendor by performing hashes on it and counting the amount of paywords. If all the paywords are valid, the broker deposits the amount to the vendor's account, and then sends an acknowledgement
M11 = {Statement of the vendor's account}
to the vendor.
Netpay computational and storage requirements
The broker needs to create payword chains for each customer, sign the touchstones of these chains, verifies paywords. All these computations can be done offline. The broker also needs to store the touchstones and maintains the accounts of both the customers and the vendors. The customer spends the paywords and needs to store the index of the last payword spent. The vendor needs to verify all the touchstones and the indexes that the broker or the last vendors sent, and paywords received from customers, and sign the indices of the last paywords received. The vendor also needs to store all the touchstones, indices from the last vendors and to the next vendors, and the paywords received.
Table 1 summary the requirement of computational and storage in the Netpay protocol.
Comparison with PayWord
The Netpay protocol shares some similarities with PayWord system. Like PayWord, Netpay transfers money to vendors in the form of the payword chain. The difference between PayWord and Netpay is the allocation and distribution of the payword chain. In the PayWord, a payword certificate authorises a customer to generate payword chains and guarantees that a specific broker will honor them. The payword chain is vendor-specific and customer-specific. Hence the paywords in the chain have no value to another vendor.
In contrast, Netpay is a debit based scheme, in which the payword chain is generated by the broker for every customer. The customer spends paywords from one vendor to another without involving of the broker. The payword chain remains active at only one vendor at a time, thus preventing customers from double spending. The payword chain in Netpay system is customer-specific but not vendor-specific. The paywords can be spent with any vendor.
The customer anonymity
The customer anonymity is an important issue in the micropayment system. The customer anonymity should be protected. A fundamental property of physical cash is that the relationship between customers and their purchases is untraceable. This means that even if all the brokers and vendors colluded they would not be able to discover the identity of the purchaser provided the purchaser has not breached security. This is called fully anonymity.
DigiCash [HRFE1] is fully anonymous Internet payment system and demonstrates a relatively simple anonymous on-line protocol using blind signatures. The system protects the information about which customer went to which vendor. The broker knows who withdrawn money and who deposits it. It can't match them up. However, it requires every spent coin to be authorized by the bank to prevent double spending.
So far, no fully anonymous, off-line micropayment system has been introduced in the marketplace, due to the after-the-fact policing requirements. Thus the broker is able to collect a complete purchasing profile of their customer. The payword chain in Neypay system is sold by a broker and redeemed by different vendors, the broker cannot determine where the customer is going to spend the paywords except for the first purchase by the customer, because the payword chain is not vendor-specific. But the broker knows the vendors that a customer traded with when the vendor redeems paywords. In a other word, Netpay offers partial anonymity.
From the above discussion, we conclude that Netpay is therefore extremely convenient for customers and a quite efficient offline micropayment system preventing customer double spending, and attackers from forging.
The Netpay system introduced so far has only one payword value. In this section, we shall describe how to extend the system to paywords with any values. This means users can extend the system to any number of values as required by simply following the changes illustrated below.
The broker could generate payword chains that have different values for the customer, e.g, assume 6 values of these chains, $0.01, $0.02, $0.05, $0.10, $0.20, and $0.50 are required for every customer. Let these payword chains be
W1 1, W1 2, ..., W1 n
W2 1, W2 2, ..., W2 n
......
W6 1, W6 2, ..., W6 n
Where Wi j satisfy Wi j = h(Wi j+1) ( j = n, ...,0 and i = 1, ...,6) and h() is the hash function introduced before. Roots W1 0, W2 0, ..., W6 0 are used to verify the validity of the paywords by the vendors and broker. Seeds W1 n+1, W2 n+1, ..., W6 n+1 are kept by the broker to prevent the customer from forging and overspending.
The messages in Netpay should be changed as follows:
M2 = { W1 1, W1 2, ..., W1 n , ..., W6 1, W6 2, ..., W6 n } PK-customer
M3 = T = {IDc, W1 0, W2 0, ..., W6 0 } SK-broker
P = { (Wi j , i, j) } where i = 1, ..., 6 and j = 1, ..., n.
Index = {IDv1, IDv2 , i1, i2, ..., i6 } SK-v1.
All other procedures in the process remain unchanged.
This paper presented a basic off-line protocol suitable for micropayments in distributed systems on the WWW. Since only the broker knows the mapping between the pseudonyms (IDc) and the true identity of a customer, the protocol protects the privacy of the customer. The protocol prevents customers from double spending and any internal and external adversaries from forging, so it satisfies the requirements of security that a micropayment system should have. The protocol is economical since it involves only a small number of public-key operations per purchase. Netpay can easily handle more transactions. In an extended Netpay system, a coin can be divided into smaller denominations, i.e, it has divisibility. Netpay is extremely powerful for a customer performing many purchases from a vendor, then changing to another vendor. The major thrust of Netpay protocol is that it shifts the communication traffic bottleneck from the broker and distributes it among the vendors, thus placing some processing burden on the first vendor when a customer wishes to purchase from a new vendor. Therefore, the success of the protocol depends somewhat on the goodwill of the first vendor. Works are underway to implement a trading community on the proposal protocol to evaluate its feasibility.
Rivest, R. (1992). The MD5 Message-Digest Algorithm, RFC 1321, Internet Activities Board.
Rivest, R., Shamir, A., & Adleman, L. (1978). A method for obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Vol. 21, 21(2):120-126.
Schneier, B. (1996). Applied Cryptography, Second Edition, John Wiley & Sons, USA.
Xiaoling Dai and Bruce W N Lo, © 1999. The author assigns to Southern Cross University and other educational and non-profit institutions a non-exclusive licence to use this document for personal use and in courses of instruction provided that the article is used in full and this copyright statement is reproduced. The author also grants a non-exclusive licence to Southern Cross University to publish this document in full on the World Wide Web and on CD-ROM and in printed form with the conference papers and for the document to be published on mirrors on the World Wide Web.
[ Proceedings ]