Before I describe a micro-payment scheme, let me say that micropayments for accessing web pages are not needed. The only people it helps are those with popular sites, and they already have advertisers paying all their maintenance costs. The readers pay indirectly with their time by reading the advertisements.

Micropayments would raise monthly access fees for normal readers twice, once to pay for the sites they are reading, once to pay for the overhead of micropayments. Costs are already high. Half my relatives who used to have internet access no longer do because the monthly costs were too high. On the other hand, micropayments could make it profitable to have a popular site, and it could reduce web advertising.

Alice wants to read Bob's web site, and both have bank accounts (and share secret keys) with Tom. Tom gives Bob a set of hashes of keys, for which Alice has the keys. Alice pays by providing Bob the keys to match his hash values. The (key, hash) pairs form an exponential set of coins, each worth twice as much as the previous coin. At the end of the day, Bob reports to Tom how much Alice owes him, and turns in his highest complete (key,hash) pair (which is worth even more) as proof. If Bob wants to cheat, the (key,hash) pair is worth at most twice what Alice really owes, so he can't cheat much. I assume that hyperlinks give the cost of what they link to.

- (x),b(x),k(x) are symmetric-encrypted x with keys a,b,k respectively.
- H(x) is a one-way hash of x.
- Bob has a bank account with Tom and shares a secret key b with him.
- Alice has a bank account with Tom and shares a secret key a with him. Alice also has a counter.

- Alice wants to read Bob's web site.
- Alice chooses i from her counter and bumps her counter by 12.
- Alice sends Tom, "Alice, a(i, Bob, date), I want Bob's X-page."
- Tom sees it is from Alice, decodes it with a, checks Alice's account for funds, checks that the date is recent, and records a(i) as identifying an unfinished payment from Alice to Bob.
- Tom sends Bob "Tom, Alice, b(session key k=a(i+11)). Here are puzzles H(a(i))...H(a(i+10)), worth .1 cent to $1.02.4. The solution to the .1 cent puzzle is a(i). Alice wants your X-page."
- Bob sees it is from Tom, notes that Tom gave him the .1 cent payment.
- Bob sends Alice, ".1, the X-page".
- (Alice could have sent Tom a bunch of i's earlier, and Tom could have precomputed all the sets of puzzles offline. In that case Bob would have to tell Alice a(i) in his first response.)

- Alice now wants the Y-page, worth 5 cents.
- Alice sends Bob, "Alice, a(i+6), .1, I want the Y-page".
- Bob checks that the hash of a(i+6) is H(a(i+6)), which means Alice has payed up to 6.4 cents. This page is worth stealing so Bob encrypts it.
- Bob sends Alice "5.1, k(the Y-page)".
- Alice knows k=a(i+11) and decrypts the Y-page.

- Alice now wants the Z-page, worth .1 cent. She doesn't have to pay Bob any more, she's already paid up to 6.4 cents, but she has to identify herself (otherwise Mallet could request pages in her name). So she hashes her account balance and session key.
- Alice sends Bob, "Alice, h(5.1,k), I want the Z-page".
- Bob checks h(5.1,k) to check this really is Alice. The new account balance is 5.2, which is less than 6.4.
- Bob sends Alice, "5.2, the Z-page".
- Alice logs off.

- At the end of the day, Bob has collected puzzle solutions from many people. He turns them all in to Bob.
- Bob sends Tom, "Bob, Alice, b(a(i)). Balance is 5.2. a(i+6)."
- Tom notes that Alice's a(i) is unspent, belongs to Bob, and that the hash of a(i+6) is H(a(i+6)). Tom deletes a(i) from Alice's unspent list and transfers 5.2 cents from Alice to Bob. He also transfers some constant amount from Alice's account to himself for accounting costs.

References: The web commerce page, DEC's Millicent, MIT's Kerberos, IBM's iKP, CMU's NetBill, MicroMINT, PayWord. MicroMINT is worth looking at, if only for its sheer wierdness.

The HOMFLY polynomial for knots and links

Hash Functions and Block Ciphers

Ms Lucy Had a Boyfriend

Table of Contents