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 ...
Whereas in the external indicator scenario, the receiver had to wai...
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