Electronic Payment Systems

20-763

Lecture 9:
Micropayments II

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 MicroMint
• Brokers produce “coins” having short lifetimes, sell
coins to users
• Users pay vendors with coins
• Vendors exchange the coins with brokers for “real”
money

PURCHASE NEW COINS BROKER EXCHANGE COINS FOR

RETURN UNUSED COINS OTHER FORMS OF VALUE

NEW COINS

SPENDING OF COINS

CUSTOMER VENDOR
TRANSFER OF INFORMATION
SOURCE: SHERIF

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Minting Coins in MicroMint
• Idea: make coins easy to verify, but difficult to create
(so there is no advantage in counterfeiting)
• In MicroMint, coins are represented by hash-function
collisions, values x, y for which H(x) = H(y)
• If H(•) results in an n-bit hash, we have to try about
2n/2 values of x to find a first collision
• Trying c•2n/2 values of x yields about c2 collisions
• Collisions become cheaper to generate after the first
one is found

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Coins as k-way Collisions
• A k-way collision is a set { x1, x2, . . ., xk } with
H(x1) = H(x2) = . . . = H(xk)
• It takes about 2n(k-1)/k values of x to find a k-way
collision
• Trying c• 2n(k-1)/k values of x yields about ck collisions
• If k > 2, finding a first collision is slow, but subsequent
collisions come fast
• If a k-way collision { x1, x2, . . ., xk } represents a coin,
easily verified by computing H(x1), H(x2), . . ., H(xk)
• A broker can easily generate 10 billion coins per
month using one machine

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Selling MicroMint Coins

• Broker generates 10 billion coins and stores (x, H(x))

for each coin, having a validity period of one month
• The function H changes at the start of each month
• Broker sells coins { x1, x2, . . ., xk } to users for “real”
money, records who bought each coin
• At end of month, users return unused coins for new
ones

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Spending MicroMint Coins
• User sends vendor a coin { x1, x2, . . ., xk }
• Vendor verifies validity by checking that
H(x1) = H(x2) = . . . = H(xk). (k hash computations)
• Valid but double-spent coins (previously used with a
different vendor) cannot be detected at this point
• At end of day, vendor sends coins to broker
• Broker verifies coins, checks validity, checks for
double spending, pays vendor
• (Need to deal with double spending at this point)

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Detecting MicroMint Forgery
• A forged coin is a k-way collision { x1, x2, . . ., xk }
under H(•) that was not minted by broker
• Vendor cannot determine this in real-time
• Small-scale forgery is impractical
• Forged coins become invalid after one month
• New forgery can’t begin before new hash is announced
• Broker can issue recall before the month ends
• Broker can stay many months ahead of forgers

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Statistical Schemes
• During World War II, Cola-Cola raised the price of a
bottle from 5 cents ($0.05) to 6 cents ($0.06)
• It was expensive to change the coin mechanism
• Coca-Cola randomly removed 1/5 of the bottles from
its machines but kept the 5-cent mechanism
• 4/5 of the time a customer would receive a bottle for 5
cents
• 1/5 of the time a customer would pay 5 cents and get
NOTHING
• The AVERAGE price of a bottle was 6 cents
• Rarely, a user might pay a lot for a bottle (1 in 625
bottles cost 20 cents)

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Statistical Payment
User needs to pay Mapquest $0.01

1/1000 999/1000
FAIRNESS:
• User, merchant and bank cannot cheat
• Not always fair to user (might be overcharged)
• Fair to merchant and bank on average $10 VOID

Enable 1000 Transactions

at Cost of 1

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 MR1 (Micali, Rivest)
• Three parties: user U, merchant M, bank B
• For simplicity, assume every transaction is worth
$0.01 but we only want to process transactions with
probability 1/1000
• U and M have public-private key pairs
• Let F be a publicly available function (everyone can
obtain the code) that returns a number between 0
and 1 uniformly. (The values of F are uniformly
distributed between 0 and 1.)
• A transaction string
T = User ID || Merchant ID ||Bank ID ||timestamp
SOURCE: RON RIVEST

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 MR1, continued
• When User U wants to pay Merchant M, he sends M
his digital signature C for transaction string T
C = SigU(T) (hash of T encrypted with U’s private key)
• Merchant M now signs C
D = SigM(C) (hash of C encrypted with M’s private key)
• Merchant M computes F(D)
– If F(D) < .001, then C is worth $10; otherwise C is worth $0
– This occurs 1/1000 of the time
• If C has value, M sends to bank C & D = SigM(C)
• Bank verifies signatures and F(D), charges U $10
and credits M with $10
• No risk to bank; U may pay a lot more than the
transaction value SOURCE: RON RIVEST

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Properties of MR1
• Payment is off-line
– U and M do not have to be in contact during transaction
– U can send C by email
– M does not have to contact Bank during transaction
• Bank only sees 0.1% of transactions
• No risk to bank
• Because of signatures, neither U nor M can cheat (if
protocol is implemented properly)
• U may pay a lot more than the transaction value
• Want a protocol in which U never pays more than the
transaction value

SOURCE: RON RIVEST

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 MR2 (Micali, Rivest)
• Goal: make sure U never pays more than transaction
value he uses
• Shift risk from User to Bank. This is OK because
Bank processes large number of transactions
• U includes a serial number S as part of the
transaction string
• Let MaxS be the highest serial number the Bank has
processed for user U so far (starts at 0)
• When Bank processes a payable transaction:
– credits M with $10
– debits U by S – MaxS
– MaxS  S

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Why Does MR2 Work?
• User NEVER pays more than the number of
transactions he creates
• After n transactions, serial number S = n. Suppose
he has to pay m times
• Total payment =
m m 1

S
i 1
i  MaxSi   MaxS
i 1
i 1  MaxSi  S m  n

• User can cheat (by not incrementing S), but Bank will
catch him
• Bank on average receives as much as it pay out

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Properties of MR1 and MR2
• Highly scalable: billions of transactions handled with
only millions of payments
• Inexpensive
• Payments are offline
• Global aggregation (can handle payments to many
merchants from many customers)

SOURCE: RON RIVEST

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Millicent
• Vendors produce vendor-specific “scrip”, sell to brokers
for “real” money at discount
• Brokers sell scrip from many vendors to many users
• Scrip is prepaid: promise of future service from vendor
• Users “spend” scrip with vendors, receive change

USER EXCHANGES BROKER BROKERS PAY

BROKER SCRIP FOR FOR VENDOR SCRIP
VENDOR SCRIP ($$$ MONTHLY)
(AS NEEDED) USER BUYS BROKER
SCRIP ($ WEEKLY)

USER SPENDS VENDOR

SCRIP FOR INFORMATION
USER (¢ DAILY) VENDOR
TRANSFER OF INFORMATION
(CHANGE IN MESSAGE HEADER) SOURCE: COMPAQ

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Millicent
• Broker
– issues broker scrip to user
– exchanges broker scrip for vendor scrip
– interfaces to banking system
– collects funds from users
– pays vendors (less commission)
• User
– buys broker scrip from brokers
– spends by obtaining vendor-specific scrip from broker
• Vendor
– sells scrip to brokers
– accepts vendor scrip from users
– gives change to users in vendor scrip

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 MilliCent Components

• Wallet
– integrated with browser
as a “proxy” Tokens Vendor
Wallet Server
– User Interface
(content, usage)
New Spent
• Vendor software tokens tokens
– easy to integrate User Vendor
as a web relay
– utility for price
management Broker $
$
• Broker software Server
– handles real money
Broker

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 MilliCent System Architecture
Broker (tens?)

Broker Vendor (thousands)

Server
Price
File Price
Configurator
HTTP Document
User (millions Tree
of consumers) Site Map

Browser Wallet Vendor Web

Server Server
HTTP
Browser Wallet
Cache Contents

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Millicent Scrip Verification
• Token attached to HTTP requests
• Scrip can not be: Client Vendor
– Spent twice
Web Web
– Forged Browser Server
– Stolen
• Scrip is validated:
– By each vendor, on the fly Scrip
– Low computational overhead
– No network connection
Broker
– No database look up Broker Server
 MilliCent Scrip

Vendor Value ID# Cust ID# Expires Props Stamp Secret

wellsfargo.com / 0.005usd / 0081432 / 101861 / 19961218 {co=us/st=ca} 1d7f4a734b7c02282e48290f04c20

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Vendor Server
• Vendor server acts as a proxy
for the real Web server
• Vendor server handles all
requests: Vendor Web
– Millicent Server Server
– relay to web-server
• Millicent processing:
– Validates scrip and
generates change Price Document
File Tree
– Sells subscriptions
– Handles replays, cash-outs, and refunds Vendor Site

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
 Major Ideas
• Micropayment systems must be fast and cheap
• They MUST lack features of higher-value payment
systems
• Use of hashing instead of cryptography
• Micropayment parties: buyer, seller, broker
• Micromint models minting coins
– High overhead to prevent counterfeiting
• Fraud is not a serious problem with micropayments

ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS
ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT © 2004 MICHAEL I. SHAMOS