Get direct links to references, BibTeX extraction and comments on all arXiv papers with: Librarian
The author of this paper is Ronald L. Rivest . Rivest (along with L...
This paper was published in 1997. Internet payments were still rath...
Here is a quick overview of some of the topics Rivest believes are ...
In this scenario, let’s say you issue a lottery ticket with a face ...
The idea in PayWord is to try to minimize the number of public-key ...
Rivest would go on to start Peppercoin Inc in 2001, a micropayments...
Electronic Lottery Tickets as Micropayments
Ronald L. Rivest
MIT Lab for Computer Science
(RSA / Security Dynamics)
rivest@theory, lcs .mit. edu
Abstract.
We present a new micropayment scheme based on the use of
"electronic lottery tickets." This scheme is exceptionally efficient
since
the bank handles only winning tickets, instead of handling each micro-
payment.
1 Introduction
We present a paradigm for micropayments: probabilistic payments with "elec-
tronic lottery tickets." The probabilistic nature of lottery tickets makes payment
of small values simple. For example, an electronic lottery ticket for a $10.00 prize with a 1/1000 chance of winning has an expected value of one cent. A user can pay a vendor one cent by giving the vendor such a lottery ticket. With conventional payment schemes, a bank or broker must process each payment: the bank issues each digital coin, and processes it again when it is re- deemed. Electronic lottery tickets are the first payment scheme in which the bank does not have to process each payment, since the bank only sees the "winners." From a bank's point of view, lottery tickets are significantly more efficient than all previously known micropayment schemes. We assume the reader is familiar with the genera] notions of public-key cryp- tography, digital signatures, hash functions, and electronic payment schemes. The next section introduces the details of electronic lottery tickets; following sections describe a standard implementation and variations, and discuss issues arising from this proposal. 2 Electronic lottery tickets An electronic lottery ticket contains the following items of information (either explicitly or implicitly): - The name of the issuer who created the electronic lottery ticket. - The name of the buyer who is using the electronic lottery ticket as a means of payment. (The buyer may be the same as the issuer.) - The name of the recipient who will collect the payment if the lottery ticket turns out to be a winner. We also call the recipient the "vendor," since the buyer gives the ticket to the vendor to pay for some good or service. 308 - A ticket number, which is compared to the "winning number" to determine if the ticket wins or not. - A winning number indicator that indicates how the winning number will be determined. - A ticket face value that specifies the payment to be received if the lottery ticket turns out to be a winner. - The name of the payer who will make the payment to the recipient if the lottery ticket turns out to be a winner. - A ticket credential that provides the recipient with evidence that the payer will actually pay if the ticket wins. The electronic lottery ticket is signed or otherwise authenticated by the ticket issuer. We now discuss and exemplify each of these items for our standard applica- tion wherein a user wants to pay a vendor a penny for downloading a web page from the vendor's web site. The ticket issuer in our scenario would typically be the user. In an alternative formulation, the issuer and the payer might be the user's bank, and the user would have purchased the lottery ticket from his bank. The buyer is the user who is surfing the web and and wants to pay for some information or service. The recipient is the vendor who receives the lottery ticket as payment for some information or service provided by the vendor to the buyer. The ticket number might be a short number of, say, three decimal digits. This number is determined by the ticket issuer, and is typically chosen randomly. The winning number indicator can be "external" or "internal": - An "external indicator" refers to some source or authority who will an- nounce a winning number, such as "the last three digits of the forthcoming Massachusetts state lottery number for (specified date)." - An "internal indicator," contains no such external reference; an example of an internal indicator is "the last three digits of the 30-digit decimal number w whose MD5 hash value is h(w) = 0x3f...13." (The value ofw is "unique": we don't ever expect to see two w values with the same hash value.) Here the issuer would not know w when he issues the ticket; he would know only the hash of w. Someone else would have created the value w and supplied h(w) to the issuer. The recipient would then have to know w in order to determine if he has a winning ticket; this is arranged most easily by having the recipient generate w himself at random in the first place and give the issuer h(w) before the issuer creates the ticket. The issuer, when he sees h(w), should not learn anything useful about the last three digits of w. (The "hash-function" h could be an information-theoretically secure commitment function.) In any case, the chance of the ticket being a winning ticket must be clear to both the issuer and the recipient, so that they can calculate the expected value of the ticket. 309 The face value (or "prize value") of the lottery ticket would, for our micro- payment application, be a modest amount like ten dollars. It should be large enough so that the cost of processing the payment by the bank is small com- pared to the payment itself. The expected value of the lottery ticket is the face value of the ticket times the probability that the ticket will turn out to be a winning ticket. The payer would, in our example application, be the user's bank or credit card company. When the recipient presents a winning lottery ticket to the bank, the bank pays the recipient the face value of the ticket, and charges the user's account that much. In some cases, a bank might be both payer and issuer, and the buyer would purchase the lottery tickets from his bank. The ticket credential might be a signed statement from the payer (bank) that the issuer has an electronic lottery micropayment account in good standing with the bank, and that the bank will pay for winning lottery tickets issued by that issuer during the month of (specify month). This credential might give other terms and conditions, or limitations, on the payer's liability for such lottery tickets, but the net effect is to provide evidence to the recipient that, if the ticket wins, he is likely to receive payment from the payer. The basic ideas sketched above can be woven into a number of existing pay- ment protocols. In some cases it may add little, in other cases it may greatly reduce processing costs. These ideas are best suited for micropayments, since it is difficult to achieve low-value payments if each and every payment must be separately processed by the user, the vendor, and the bank. Electronic lottery tickets greatly reduce the bank's processing costs, since it sees only the winning tickets. The computational costs to the user and the vendor are comparable to the costs of other payment protocols--they still have to do a little work for each payment. When a sequence of micropayments is made using electronic lottery tickets, there is a risk to the issuer that too many of them will turn out to be winners, and a risk to the recipient(s) that too few of them will turn out to be winners. But the law of large numbers takes over quickly; it takes many micropayments before you are into "real money." The expected value of the payments is correct, and the variance is not large. For example, if an issuer makes 10,000 micropayments with an expected worth of$100 by issuing lottery tickets with a face value of $10 and a 1/1000 chance of winning, then the probability that he actually pays less than$50 is less than 3%, and the probability that he pays more than $200 is less than 0.4%. Also, when internal indicators of the winning number are used, the protocol may have the vendor notify the issuer immediately whenever a ticket wins, so the issuer can track his micropayment obligations. This completes the description of the basic scheme. The next sections discuss various details and variations of the scheme. 3 The "standard" version of electronic lottery tickets We sketch in more detail the "standard" version. 310 Here the issuer is also the buyer. He has a signed credential from his bank (the payer) stating that his account is in good standing, and that he may is- sue electronic lottery tickets based on this credential for the month of (specify month). This credential is the ticket credential. The winning ticket number is determined by an internal indicator, as de- scribed above. The recipient makes up a random number w, and gives the issuer h(w) to include in the lottery ticket itself. This hash value is given to the issuer early in the payment protocol. (If the payment protocol must be non-interactive, as for an emailed purchase order, then an external indicator would have to be used.) The issuer may issue as many electronic lottery tickets as he likes, to whomever he likes, to pay for goods and services. These payments may be viewed as "prob- abilistic checks" on the user's account with the bank. There is a risk that the user may issue too many winning tickets, and be unable to pay for the winnings from his account. How should this risk be handled? In the simplest model, the recipient (vendor) absorbs this risk; the vendor may not get paid if the issuer lacks sufficient funds with the payer. In this case the payer will not re-certify the issuer for the next time period. This model works reasonably well when the items being sold are low-value information items, so that the vendor has lost little. While some fraction of the winning electronic lottery tickets will turn out to be worthless, the system is self-correcting in that bad issuers will get weeded out over time. A vendor may be perfectly happy if he can collect on 90% of his winning tickets. Over time, he can adjust prices to cover such lossage. It is not worthwhile for the vendor to do an on-line verification for each micropayment received. On the other hand, he can determine immediately if ticket wins (assuming it has an internal indicator), and deposit that ticket immediately, receiving notice if the issuer's account has insufficient funds. Or, the vendor could verify on-line the issuer's good standing with the payer when the vendor receives his first electronic lottery ticket from an issuer, and thereafter just deposit the winners. (This is reminiscent of the techniques of Jarecki and Odlyzko [4] for "probabilistic polling".) There is also some risk to the user that he might be issuing too many winning tickets, and so run up a large bill for his "micropayments." As noted above, the chance of this happening are small, and the users of electronic lottery tickets should be aware that there will be some variability in the actual amount they owe, even though the expected amount paid is correct. Furthermore, a user can be notified immediately by the recipient whenever he issues a winning ticket (assuming internal indicators), so he can track his actual expenditures. For every 1000 penny web pages visited, a window could pop up explaining that the user has just been billed$10 for micropayments.
Since the issuer may create as many lottery tickets as he wishes, it is appro-
priate (and necessary) that he take on the obligation of paying off all winning
tickets.
My favorite version of this scheme is based on the micropayment scheme
PayWord by Adi Shamir and myself [6]. A user commits to a given vendor a