Micropayment Token-Making
Schemes
Abstract: Micropayment schemes generally use digital tokens as a form of currency. A digital token is made from a special string using a cryptographic algorithm. In this article, we will first discuss the requirements that a micropayment scheme should satisfy. Then we will briefly describe a few well-known schemes and discuss how well they attempt to meet the necessary requirements.
The Internet offers an unprecedented opportunity for access to digital content. During the Internet bubble era (about 1995 through 2000), most digital content on the Internet was free, with merchants expecting to eventually cover their costs through advertisements. This business model is now widely discredited and it is generally agreed that online merchants need to charge for their products and services [8]. Consequently, electronic financial transactions must be accommodated.
Micropayment schemes are designed to facilitate online purchases involving small amounts of money. Some situations where micropayments naturally arise include downloading a news article, a recipe, or a song, or requesting information from a specialized database, or even buying a lottery ticket [2, 5, 11]. In one example, an online software magazine charged readers 50 cents per access, while the annual subscription rate was $49. In another example, Oxford University Press, charges 5 cents per lookup in a special dictionary [12]. Micropayment schemes are specifically designed to efficiently and transparently handle such transactions.
Even before the Internet bubble, micropayment was viewed as a promising technology [13]. But in spite of the potentially large demand for micropayments, such schemes have failed to become a major method of online financial transactions. Several reasons have been suggested for this failure [7, 9]. In any case, it appears clear that micropayments will one day become an integral part of electronic commerce. In this paper we will consider a few well-known micropayment schemes and analyze how they meet the core requirements for micropayment and we will consider issues that might reduce their chance of being widely accepted by the Internet community.
To date, many micropayment schemes have been proposed. Even though these schemes vary significantly with regard to their token making algorithms, their methods to prevent forgery, and so on, they all must deal with the certain core problems and they all must meet the same common business challenges.
Generally, there are three participants in a micropayment scheme.
· Customers (or users) are the people who intend to make small online purchase and desire the convenience of a micropayment implement to help them pay for their purchases.
· Vendors (or merchants) are the companies or web sites that want to sell their low-cost products/services online and are willing to accept a micropayment for their products/service.
· Brokers (agents and financial institutions) are the companies that are the middlemen between customers and vendors. Brokers facilitate micropayment transactions. Generally, brokers are the hosts or administrators of the micropayment system.
2.1. Business Challenges.
Any realistic micropayment scheme must satisfy several business-related requirements. These requirements include the following.
· Trust and Anonymity. On the Internet, there is a physical separation between customer and merchant and this fact makes it difficult to establish trust. Customers’ desire for anonymity can exacerbate this problem. Another difficulty with online transactions is that there is no physical verification. In order to be widely accepted, a micropayment scheme must overcome these difficulties and, in particular, establish some trust between the customer and merchant [2, 13].
· Instant Payment. Typically, a micropayment system would be used for digital content or online services. Much of this would occur as a natural part of Web interactions [11]. Unlike a large purchase where, say, a credit card payment is sufficient, micropayments apply to content or services that generally must be delivered to customers immediately with little or no effort required by the customer. Therefore, payment validation must occur transparently in real time [8, 13].
· Low Processing Cost. Since micropayments are, by definition, small sized payments, the processing cost per transaction is of particular importance. Any realistic micropayment scheme must therefore minimize transaction costs [5, 14, 15, 16].
2.2. Core Requirements of Micropayment.
Currently, many micropayment implementations rely on memberships or subscriptions. In this approach, the merchant will ask the customer to register or subscribe first. Then the customer is allowed to access the content or service covered by this merchant and the small charges that accrue are subsequently billed to the user’s account. The drawback is that users need to register with various merchants.
A more universal alternative to micropayment can be developed, based on the same principles as currency. Such schemes generally include the following.
1. A highly credible broker who creates “digital tokens” based on a particular cryptographic process.
2. The digital tokens are then sold to customers who can then use them in electronic transactions.
3. Merchants collect tokens, verify that the tokens are valid and deliver the content.
4. The merchants accumulate tokens and later send the tokens to the broker to settle accounts and thereby receive payment.
Such general micropayment schemes must consider the following issues.
How do customers obtain tokens?
Micropayment schemes can be categorized as prepaid or postpaid schemes. In a prepaid scheme, the customers need to purchase the tokens before they are delivered. In a postpaid scheme, the customers “borrow” tokens and pay later after they have spent their tokens. A postpaid scheme requires much more trust in the consumer since the broker needs to collect money from the customer after content has been delivered, similar to credit cards.
How to make tokens?
This question is the core technical issue for universal micropayment schemes. A token making algorithm should meet following basic requirements.
· Token authenticity must be assured. Nobody other than the broker should be able to profitably make counterfeit tokens.
· The manufacturing cost must be low. The broker must be able to make tokens so that the cost per token is low enough to make the scheme workable.
· Duplicate spending must be prevented. Unlike physical currency, exact replicas of digital tokens are easily created. Therefore, preventing duplicated spending is a critical issue for any digital token making algorithm.
Another important concern for token making is the issue of what information the token should contain. A digital token usually is a hash or encrypted result of a certain “seed” bit string. The seed string can contain special information. This information can be customer-related or merchant-related and can be used, for example, to limit the scope of the token. That is, a token’s seed value could restrict its use to one specific customer or so that it could only be spent at one particular merchant and so on. This issue involves a fundamental tradeoff between security and convenience.
Selecting the proper token-making cryptographic function is also a major concern. Most algorithms try to avoid using public key operations because they are considered too expensive for micropayment. But with increasing computing power, this assumption may change in the future. Today, hash functions are considered to be the most appropriate cryptographic function for micropayment.
Token validation.
A merchant must be able to verify the validity of a received token. A usable micropayment scheme must provide an efficient validation function for merchants. This presents a fundamental asymmetry in micropayments, since it must be very difficult to forge tokens but very easy to validate tokens. Hash functions are the best way to satisfy this requirement.
Duplicate spending is a related problem. It is difficult for an individual merchant to determine whether duplicate spending has occurred. Among proposed algorithms, there are two general ways to deal with this problem. Some algorithms require that the tokens contain user information. In this way, the ownership of a token can be traced and the owner is required to take responsibility in case of double spending. An alternative is to have the broker enable merchants to detect duplicate spending by providing online support. A merchant could then go to a broker’s website to determine whether a specific token has already been spent.
If a broker provides online support, it will increase the overall security of the system, but this does not come without cost. First, the online support could be relatively expensive for the broker. Also, the broker itself could be a bottleneck for the entire system. For example, if the broker’s server were offline, the whole system would be unusable. Finally, the broker’s server would be an obvious target for denial of service attacks.
3. Micropayment Schemes
In the remainder of the paper, the following notation is used.
· PKN denotes public key of node N
· SKN denotes private key of node N.
· EKN denotes a symmetric key for node N.
· Message M signed by private key SKN is denoted {M}SKN
· Message M encrypted with public key PKN is dentoed PKN{M}
· Message M encrypted with symmetric key EKN is denoted EKN{M}
· A hash of message M is denoted h(M). The hash of the message M with the key K is denoted h(M, K).
3.1. PayWord and MicroMint
PayWord and MicroMint [1, 6, 14] are two micropayment schemes, both of which were developed jointly by Rivest and Shamir in 1996 [14]. These are two of the earliest micropayment proposals and many basic digital token concepts introduced in these two schemes appear in subsequent micropayment schemes. In fact, these two schemes are cited so widely that they have effectively become de facto standards against which any new proposed micropayment scheme is measured.
PayWord is a credit-based scheme. Before using PayWord, a customer must establish an account with a broker and obtain a digital certificate, which may contain information such as the broker’s name, the user’s name and IP address, the user’s public key, the expiration date, and so on. The broker signs this digital certificate.
After obtaining a certificate, the customer creates a PayWord chain. A PayWord chain is a finite set of “paywords”, where each payword represents a basic payment unit (e.g., 1 cent). A chain is created with an iterated hash algorithm developed by Lamport [4] (though for a different purpose). To make a chain the customer first selects a random number to serve as the last element in the chain. This is known as the “seed” of the chain, which we denote as wn. Then the payword in chain position i, denoted wi, is created as the hash result of payword in position i+1, that is,
wi = h(wi+1)
The first element of the chain, w0, is regarded as the “root” of the chain. All elements of the chain are paywords except for the seed, wn and the root, w0.
Before the customer can use his PayWords, he must first send a participating merchant a commitment, which serves to bind the PayWord chain to that particular merchant. The commitment contains the root of the PayWord chain, the merchant’s identity, the customer’s certificate, expiration date, and, possibly, other information, and it is signed by the customer’s private key. The merchant can use the certificate to identify the customer and verify the signature. After the merchant accepts the commitment, the chain is bound to that merchant and can only be used as payment with that particular merchant.
When the customer wants to make a purchase, he sends the merchant a pair, P=(wi, i), where 1 £ i £ n, as payment. The merchant verifies this pair based on the last payword it received for this particular chain. If this is the first purchase using this chain, the root will take the place of the valid payword from the previous transaction. For example, suppose that the last used payword is wj, and sent pair is (wj+k, j+k) (the pair is invalid if k£0). If the pair is valid, then the merchant needs to iteratively hash wj+k for k times and see if the result is equal to wj. If so, the customer is paying k units for the current purchase. After receiving the payment, the merchant needs to store wj+k for use with the next payment from this particular customer.
Periodically, the merchant sends a customer’s currently stored PayWord to the broker. After verifying the PayWord, the broker will reimburse the merchant and also bill the customer.
Unlike PayWord, MicroMint is a customer-debit scheme. In this approach, customers do not need to have an account with a broker but, instead, customers buy “coins” from the broker before using them.
In MicroMint, the coins are made based on the “k-way collisions” principle. A k-way collision is a set of k distinct x-values x1, x2, …, xk, where each of xi is m bits and
h(x1) = h(x2) = … = h(xk) = y
where y is n bits in length. It is a standard result (based on the so-called birthday paradox [3]) that for an n-bit hash function, about 2n/2 values must be hashed in order to find a 2-way collision, that is, after 2n/2 hashes we expect to have found x1 and x2 such that h(x1) = h(x2). However, if c2n/2 values are hashed, then the expected number of 2-way hashes climbs to c2. On the other hand, about 2n(k-1)/k values must be hashed before the first k-way collision can be found, but, as with 2-way collisions, subsequent k-way collisions are relatively easy to find [1]. In other words, if y is sufficiently large and k is chosen appropriately, then the cost of finding the first k-way collisions is extremely high, but the average cost of finding large number of k-way collisions is reasonable low.
The assumption underlying MicroMint is that y is big enough so that no attacker can afford to find a k-way collision (which would enable the attacker to forge coins). However, the broker will make and sell a large number of coins so that the cost per coin will be sufficiently low, due to the fact that multiple k-way collisions are relatively easy to find. In this scheme, each coin is an m-bit k-tuple, {x1, x2, …, xk} and all xi in a coin share the same n-bit hash value, y. The y value for each coin is unique but coins can share a common “criterion”, where the criterion is a t-bit string (0 < t < n). Typically, the coins have the same first t-bit in their y-values. A criterion can be used for coin verification. In practice, a criterion can be shared by all the coins a particular broker makes, or the criterion could be shared only by the coins made for a specific customer and so on. Of course, this assumes that the broker has many k-way collisions available so that he can select a sufficient number of these satisfying the appropriate criteria.
The customer needs to buy coins from the broker prior to making a purchase. Then a purchase using MicroMint coins is very simple. During the purchase, the customer sends coins to a vendor, and the vendor verifies them by checking the required hash condition. The value of each coin is known, based on its criteria and these criteria are publicly available, say, on the broker’s website. If the coins are valid, the vendor will store the coins and deliver the order. In practice, the vendor may have to contact the broker in order to prevent double spending. The vendor then needs to send the coins he’s collected to the broker and after the broker verifies the coins are valid, the broker will reimburse the vendor.
MicroMint makes its coins based on k-way collisions¾a difficult but not impossible problem for an attacker. Consequently, MicroMint coins cannot remain valid indefinitely, or else an attacker may have time to compute forged coins. One solution would be that after a certain period of time, the broker should recall all the unused coins and replace them with new coins. In this way, the chance of an attacker generating forged coin could be minimized.
PayWord and MicroMint each have certain strengths and weakness. We compare these below.
Tokens. Since PayWord is a credit-base scheme, the broker needs to have a database of customers, which reduces the convenience and increases the total cost of the system. On the other hand, MicroMint is a debit-base scheme and so it does not require a customer database. This feature should make MicroMint more acceptable to customers. However, MicroMint coins are an easier target for attackers. For example, the basic underlying assumption of MicroMint is that attackers cannot make coins cheaply enough and quickly enough. But this assumption may not be reliable. With the development of new technologies, such as distributed computing, hackers may have a reasonably good chance of generating fake coins quickly, and the hackers might be able to make money selling these forged coins. To deal with this problem, the broker might have to resort to generating customer (or vendor) specific coins. But if this is the case, then MicroMint loses much of its appeal. This clearly illustrates the tradeoff between security and efficiency, which is a common problem in security engineering.
Cryptographic algorithm. Even though PayWord and MicroMint use different methods to generate paywords (or coins), both rely on the one-way and collision-resistance properties of hash function. The benefit of hashing over, say, public key cryptography, is that it simplifies the system and greatly reduces transaction costs.
Use of public key cryptography. Avoiding the use of public key operation is one of the important goals for most micropayment schemes. PayWord uses public key operations for commitment and to authenticate customers. A significant advantage of MicroMint is that it does not use any public key operation at all.
Customer anonymity. With MicroMint, it is possible to generate generic coins, resulting in complete anonymity for the purchaser. But in practice, the broker usually needs to have a customer’s information in order to prevent forged coins and double spending. But even if the customer uses customer (or vendor) specific coin, he is still anonymous to the vendor since only the broker knows the customer-specific information.
In PayWord, the customer needs to submit his certificate to the vendor and the vendor also needs to keep a record of the customer’s last purchase. As a result, the customers are not anonymous to vendors in this scheme. In fact, this approach creates the potential for a denial of service attack, where many small purchases are made by different “customers”, in which case the vendor must keep track of the last purchase of all of these “customers” until the end of a specified time period. This could potentially deplete the computing resources of the vendor.
Instant payment. Both PayWord and MicroMint verify tokens by comparing a token’s hash result to known value. Therefore, in both cases the verification is quick and efficient. Since the hash result can be calculated in real time, both schemes satisfy the instant payment requirement.
Forgery prevention. PayWord and MicroMint have different strengths with respect to forged coins. Since the customer needs to submit a signed commitment in PayWord, it is difficult for an attacker to forge paywords. Since PayWord uses a one-way hash function and it is difficult for the vendor to find the value of next payword from current one, it is also difficult for a vendor to make forged paywords and overcharge customers.
Customers are allowed to make their own PayWord chains, so there is a small chance that two customers will generate the same chain for the same vendor. If this occurs, the vendor can find the future payword of the customer who has spent less and then forge paywords and overcharge the customer. The probability of this occurring is negligible if the seed values are sufficiently random.
MicroMint is significantly weaker than PayWord with respect to forgery prevention. One potential way to generate forged coins in MicroMint is to guess the criterion of a coin for future use. This is roughly equivalent to guessing a password from its hash result. The number of valid criteria in MicroMint can be large if we have many customers and each of them has his/her own criterion. In such a case there may be a reasonable chance of success by an attacker.
Double spending. In PayWord, if the user is honest then duplicate spending is easily prevented because the PayWord chain can only be used for one merchant and must be used in order. But in PayWord, the customer makes the chain (based on his own certificate), so a dishonest customer can make several legitimate chains for different vendors and uses them without being caught until the settlement phase. As a result, the broker and vendor both have a risk of loss in such cases. By requiring that the customer set up an account, Payword may reduce this loss to an acceptable level.
In MicroMint, vendors cannot directly detect double spending. To deal with this problem, the broker needs to keep a list of coins that have already been spent and when the vendor verifies a coin, it must go to the broker’s site to check the validity of the token.
Online support. One of the major design features of PayWord is that it does not require online support. Once a customer gets a certificate from a broker, he can create and use his PayWord chains without the support of the broker. But as we mentioned above, MicroMint does require a broker’s online support in order to prevent duplicate spending. This is considered a major drawback to MicroMint.
3.2. Other Micropayment Schemes
In this section we describe the PayFair micropayment scheme in some detail. Then we briefly mention a few other micropayment schemes.
PayFair was proposed by Yen in 2001 as an improvement of PayWord and Millicent [15]. The biggest advantage for this scheme is that it has some of the strengths of a prepaid scheme (which tends to protect vendors) and postpaid scheme (which tends to protect customers). This scheme requires no public key operations and it has a lower transaction cost than PayWord [11] or Millicent [9].
PayFair requires that each customer open an account and share a symmetric key, Kc, with the broker. Unlike PayWord, a vendor in PayFair also needs to open an account and share a symmetric key, Kv, with a broker. PayFair is a two-phase process: a prepaid phase and a micropayment phase. In the prepaid phase, the broker makes tokens and sells them to customers, while in the micropayment phase the customer uses the tokens to make payment chains, which can then be used to make purchases.
In PayFair, the broker makes the tokens. Initially, the tokens are not associated with any customer or vendor. A token is created as
ESK{N, RN}
where ESK is a broker symmetric key (known only to the broker), and is used to encrypt a serial number, N, and a random nonce, RN.
When a customer wants to purchase a token, he needs to send an order to the broker. An order contains a sequence number, Oc and the hash value h(Oc, Kc). After receiving an order, the broker authenticates the customer by verifying the hash and verifies the order by comparing the coming Oc with the Oc of any previous order. Note that the broker must keep a record of Oc for each customer. If the hash and Oc are correct, the broker encrypts tokens (and other information) with the shared symmetric key, Kc, and sends the result to the customer. The broker must also register the token for that particular customer, thereby associating a token with the specific customer. Only the customer and the broker know the value of the token.
The steps above constitute the prepaid phase. Then comes the micropayment phase, which uses the same algorithm as PayWord to create pay chains, but instead of using a random number, a PayFair customer uses the token from the prepaid phase as the root of the chain.
The first time that a customer shops with a particular vendor, that customer needs to submit an initial request. This request includes the root of a pay chain, w0, a sequence number N for the token, (the broker provides this number to the customer along with the token), and hashed with the customer’s shared symmetric key, Kc. Since this initial request is sent through public channels in plaintext, this hash is required to ensure the integrity of request. But the vendor does not know Kc, so the vendor cannot check the integrity. As a result, the vendor needs to send the request (along with certain vendor information, encrypted with its shared symmetric key, Kv) to the broker, who has the information needed to verify the request. After receiving the confirmation, the vendor will allow the customer to pay with the pay chain. The payment process is exactly the same as in PayWord.
Since the broker provides online support in this scheme and the vendors have accounts with the broker, the vendors do not have to wait until the end of a payment period to redeem tokens. Once a pay chain is completely used, the vendor can send it back to the broker. After the validity of the chain has been verified, the broker will debit the vendor’s account immediately. As a result, vendors do not have to keep records of all used chains.
In PayFair, the broker does not need to give a customer credit, which avoids potential losses due to bad credit. Also, each token is unique and associated with a customer and a vendor, and as a result, the vendor cannot overcharge a customer (which may be possible in PayWord as discussed above. The tradeoff for this increased reliability is that PayFair requires both customer and vendor to have an account with the broker, which makes PayFair somewhat less convenient.
Millicent was proposed by Mark Manasse in 1995 and is a debit-based scheme [5]. The major goal of Millicent is simplicity, low transaction costs and reasonable security. To achieve this goal, Millicent uses no public key operations but it does require a customer to set up a temporary account with a vendor. In Millicent, the currency is made by vendors for their customers and sold through brokers. For a purchase to occur, the customer needs to buy currency, and then use it to pay for the purchase. In this way, the credit risk a vendor must face will be low because the vendor only needs to deal with trusted brokers.
Millicent is a legacy scheme, and can be regarded as a prototype of token-based micropayment schemes since it can satisfy the basic requirements of micropayment. However, Millicent has some serious drawbacks, including high overhead costs. The biggest advantage for Millicent is that it allows multiple brokers in the system. As a result, the system becomes more robust because of system decentralization.
Micropayment with probabilistic polling was proposed by
Andrew Odlyzko in 1997 as an improvement to the existing micropayment schemes
[10]. It is not an independent scheme, but instead it works with another scheme.
The polling is used to improve system performance by preventing double
spending. The basic idea of this scheme is that the validation of coins does
not occur for every transaction. Polling is expected to catch most fraud
activities at a very low cost. Polling is particularly useful for schemes that
have high validation costs, such as PayWord.
PPay
PPay is an interesting micropayment scheme that was proposed by Yang and Carcia-Molina in 2003 [16]. This scheme is specifically designed for Peer-to-Peer systems. The major motivation of this scheme is to shift transactions and security from the central broker to the peers. The underlying assumption of this scheme is that peers in a peer-to-peer network will both sell and buy products and services from other peers. The basic design of PPay is that a peer can reuse coins, which are collected from other peers by selling products or service. Therefore, the broker won’t need to create coins for each transaction and, in turn, can dramatically reduce its workload for making coins.
The biggest advantage of PPay is that it can dramatically improve the system performance by reducing the broker’s load. But PPay has its limitations as well. First, PPay can only work with a peer-to-peer network. Secondly, PPay requires a balance between buying and selling for most of peers, which is not necessarily the case. In fact, in some Peer-to-Peer systems [3], only a few peers sell most of the products and service. Such an imbalance would hurt the overall system performance.
5.
Conclusions
In his paper we introduced and analyzed two classic micropayment schemes, PayWord and MicroMint. We also provided a brief discussion of PayFair, which is a hybrid of PayWord and MicroMint, and we mentioned a few other schemes. These schemes all satisfy the basic technical requirement for micropayments. However each makes different tradeoffs between convenience and security.
While there is no optimal micropayment scheme, it seems clear that any system that is going to be widely used must be an open standard and, for convenience, it probably must also work for both micropayments and regular payments. To date, there seems to have been little attention paid to broader issues such as these and this may, in part, explain the failure of micropayment schemes in the marketplace. However, since there is a legitimate need for a usable micropayment system, and since various proposed systems are technically sound, the author believes that it is a virtual certainty that online payment system that can support both micropayments and regular payments will one day become commonplace in electronic commerce.
References:
1. Chi, Ellis "Evaluation of Micropayment Schemes" HP Laboratories Technical Report, n 97-14, pp 1-29, Jan, 1997
2. Hallam-Bakeer, Phillip, "Micro Payment Transfer Protocol", http://www.w3.org/TR/WD-mptp-951122, 1995
3. KaZaA website. http://www.kazaa.com
4. Lamport, Leslie "Password authentication with insecure communication" Communications of the ACM, Volume 24 No 11 pp 770-771, November, 1981
5. Manasse, M. "The Millicent protocols for electronic commerce" proceedings of the 1st USENIX workshop on Electronic commerce, 1995
6. Micali, Silvio. and Rivest, Ronald L. "Micropayments Revisited" CT-RSA 2002
7. Michael, Lesk, "Micropayments: An Idea Whose Time Has Passed Twice?" IEEE Security and Privacy, volune 2, No 1, pp 61-63, January/February, 2004
8. Milunovich, Steve. "Micropayments's big potential" November 5, 2002 Red Herring
9. Odlyzko, Andrew "The Case Against Micropayments" Lecture Notes in Computer Science #1318, pp. 173, 1997
10. Odlyzko, Andrew "Efficient micropayment system based on probabilistic polling" Lecture Notes in Computer Science #2742, pp. 77-83, Springer, 2003
11. Palmer, Jonathan W. and Eriksen, Lars Bo "Digital newspapers explore marketing on the internet" Communications of the ACM, Volume 42 No 9 pp 33-40, September 1999
12. Patch, Kimberly and Smalley, Eric "Drop a Dime Online" http://www.infoworld.com/cgi-bin/displayStory.pl?/features/981130micropayments.htm, 1998
13. Pilioura, Thomi "Electronic Payment Systems on Open Computer Networks: A Survey" work paper http://wwwi.wu-wien.ac.at/public/ehandel/Zahlung_Ueberblick.pdf 1999
14. Rivest, Ronald L. and Shamir, Adi "PayWord and MicroMint: Two simple micropayment schemes" Lecture Notes Computer Science, 1318, pp 307-314, 1998
15. Yen, S-M. "PayFair: a prepaid internet micropayment scheme ensuring customer fairness" IEE Proceedings - Computers and Digital Techniques, Volume 148, No. 6, pp 207-213, November 2001.
16. Yang, Beverly and Garcia-Molina, Hector "Emerging applications: PPay: micropayments for peer-to-peer systems" Proceedings of the 10th ACM conference on Computer and communication security, October 2003