Micropayments, redux

[Anton Stiglic]

Here is an email I sent to a private list right after I heard about
the Peppercoin startup.  I summarized PayWord, the lottery
scheme, and the new schemes which form the basis of what
Peppercoin wants to develop (Peppercoin is *not* developing
the older lottery scheme).  Might be useful to someone!

------------

As I suspected the micropayment scheme they want to develop is
based on their recent paper, for which I attended a presentation by
Ron Rivest at RSA conference last February.

The idea is simple, it's based on a scheme Rivest published in a
paper in '97 called "Electronic lottery tickets as micropayments".

Here is a small description for those who are interested:

U: user who wants to purchase something
M: merchant
B: bank
In the descriptions let's assume that each micropayment is worth 0.01$
(the schemes can be generalized to accept different amounts).

*PayWord:  recall that PayWord was one of the first micropayment
schemes Rivest and Shamir came up with.  In payword, a user U
chooses an initial value x_{n-1} and computes a chain of hashes
all the way down to x_0
            x_i = Hash(x_{i+1})
U then signs x_0.   U gives M x_0 and the signature on x_0.  When U
wants to make a payment to M, U provides the next value in the hash
chain, x_i (he initially gives x_1, then x_2, etc...).
Each x_i is worth some predetermined amount of money,
0.01$ in our example.
At the end of the day M will deposit the payments to the bank B:
M simply provides x_0 and U's signature on x_0, along with the x_i
with largest index i, the bank can verify by simply hashing x_i
all the way down to x_0 and verifying U's signature on x_0.
This provides a way for the merchant to aggregate payments of a
specific user.

*Lottery Scheme.
This is a probabilistic scheme.  A payment can have a value 1/p
with some probability p.  For instance a payment can value 10$
with probability 1/1000 (we continue to assume that each
merchandise is sold at 0.01$)
This time the Merchant computes a hash chain w_0, ..., w_{n-1} in
the same way that a user computes a hash chain in PayWord.
When U wants to give a payment to M, M provides the root value
w_0 to the user and the user computes his own hash chain with
w_0 integrated into his commitment x_0 (the user signs x_0
*and* w_0 and some other information in the same sig).
For the i th payment, U gives x_i to M,  the payment is worth
10$ if x_i == w_i mod 1000, and worth nothing otherwise.  As you
can see there is a probability of 1/1000 that the payment is
worth 10$, 999/1000 that it is worth 0$.
This allows the merchant to
 *aggregate payments from different users*
something you couldn't do with PayWord.
One problem with this scheme is that the payment protocol is interactive,
the other problem is that if U is unlucky he might
(with prob 1/1000) need to pay 10$ on his first payment of a merchandise
worth 0.01$.  If he is very unlucky he might pay another 10$ on his
second payment, this might be enough to discourage the user from
using the system anymore.

*The new schemes
Rivest and Micali propose 3 new schemes that circumvent the problems
of the above schemes.
Note that they assume that computing digital signatures is not a problem
anymore due to advancement of hardware performance, a user can compute
a digital signature on each transaction.  You still want the property
of aggregating payments however, so that the bank doesn't have to many
to verify.

1st scheme (MR1):
We still have a probability p that a payment be worth something or not.
There is a public function F which takes an arbitrary bit string and
produces
a value between 0 and 1 in a uniform way (F can make use of a hash
function..).
Let T be the encoding of a transaction (contains info like U, M and B's id,
merchandise description, value of payment, etc..).  Note that here U or M
defines what the payment is worth in the transaction, but for simplicity we
will assume that it's always 0.01$ and that p is fixed to 1/1000 as
previously.
U pays M for a T by providing a signature C = sig_U(T)  (U signs T).
Call C a check.
M, upon reception of C compute his own signature on C and verifies if
     F(sig_M(C)) < p,
if so then the check is deemed payable, if not it is not worth anything.
U cannot figure out beforehand if a check will be payable or not because
for what U is concerned with, sig_M(C) is like a random variable chosen
when M applies his signature.
Advantage of this scheme:  the payment is non-interactive.

MR2 scheme:
There is still the "psychological" (as Rivest and Micali state it) problem
that a user faces where he might need to pay 10$ right off for his first
payment.  Users like to be charged the amount corresponding exactly to
what they bought.
This solution solves the problem.
As in MR1,  U pays M by computing a signature C = sig_U(T) on T, but this
time U includes date/time and a serial number SN in T.  SN should start
at 1 and be incremented by 1 for each payment.
As in MR1, check C is payable if F(sig_M(C)) < p, but the deposit differs
on the side of the bank:
  let maxSN_U denote the maximum serial number of a payable check of U
  processed by B so far (initially maxSN_U = 0).  Assume that C is a new
  payable check.  Then B credits M's account with 1/p cents and if SN
  is greater than maxSN_U, B will debit U's account by SN - maxSN cents,
  and set MaxSN_U to be SN.  An exception might occur if B notices
  that the new check has the same serial number as a previously processed
  check, or if the new check's serial number and time are out of order,
  or for some other reasons.  The bank may keep statistics and throw out
  of the system (by revoking certificates) users whose payable checks cause
  exceptions.  B may also throw out merchants (who might have a to high
  rate of payable checks: merchants might collaborate with users to get
  more payable checks, users have nothing to loose).  This is the part that
  I see as hard to implement, I discussed this briefly with Ron Rivest after
  his presentation but he seemed convinced that it was not a problem, we
  will see!
So in this scheme a user is never charged more than what he actually
spends, the risk of excessive payments (which Rivest and Micali
qualify as small) is shifted from the user to the bank (R&M argue that
Banks are more accustomed to managing substantial risk so they
will not mind the rare risk of a small excessive payment).

MR3 is based on MR2 but renders the deposit of M to B more efficient.

The paper of course has more details on the schemes, and allot of proposed
little variants.
I'm anxious to see how the company will develop the technology!

--Anton






---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com