Electronic payments
===================

Overall goal: Users/organizations want to pay each other money.
    Ideal: some representation of "value" that can be passed between parties.
    Why would something possess value?  Mostly a matter of convention.
	E.g. in physical world, gold has value (everyone agrees they want gold).
	If total amount of gold is "stable", can think of value of unit of gold.
	At the lowest level, can think of gold atoms having some value.
    We want an electronic representation of value (ideally in terms of bits).
	Big problem, if we have purely a string of bits represent value:
		    bits can be copied
		 => total amount is infinite
		 => any individual bits are worthless?
	Typically the problem is called "double-spending" in cryptography.

How to avoid the double-spending problem?
    Account-based system
	account keeper (bank) tracks how much value users have in their accounts
	double-spending prevented by trusting the bank to not copy the bits
	everyone must trust the bank not to fabricate money
	by far the most popular scheme today (EFT, ACH, credit/debit cards, ..)
    Use smartcards instead of pure bits
	money stored in bits, but kept by a (trusted) smartcard
	effectively a distributed version of a bank / account keeper
	in practice used for lower-value applications requiring offline support
	    transit cards: MBTA charliecard, London's oyster card, etc
    Use quantum bits?
	intuition: in theory impossible to clone
	many big research questions on how/whether it can work, not this class

Deployed payment systems today
    bank account transfers, credit card purchases
    no analogue of a signed check to a given party for a specified amount
    your account# (or credit card#) is a blank check to anyone for any amount
    how to guard against double-spending/copying/fraud?
	use online verification to check account#, balance (customer fraud)
	try to control who gets your CC# (encrypt over the network: SSL)
	bank absorbs remaining "merchant-side" fraud (charge merchants e.g. 2%)
    important idea: focus on risk/costs, not on absolute security

Electronic checks (simple scheme)
    One bank, with a public/private key pair PK_B / SK_B
    Each user has a public/private key pair PK_U / SK_U
    Users have accounts at the bank
    Bank generates certificates for each customer (e.g. account# and PK_U)

    Check from A to merchant M looks like:
	{ Cert_A, Sign(SK_A, "Pay M $100; serial#; date") }

    M presents this check to bank B, ask for amount to be deposited in M's acct

    Guard against M double-spending (depositing the same check twice)?
	Bank checks serial# on the check, only allows depositing it once
	For efficiency, can use date as part of ser#
	Would only need to store last N days of ser#s (all earlier are invalid)
    Guard against A double-spending?
	Check that A's account has enough money, might tell M "sorry"
	Cashier's check: bank removes money from A's acct, counter-signs check

What properties would an ideal system provide?
    non-forgeability (cannot synthesize money out of thin air)
    cannot double-spend
    offline transactions (Alice can pay Merchant while both are offline)
    transferability (Merchant can use received money to pay others in turn)
    divisibility (in cash-like schemes, can create smaller denominations)
    anonymity (can't trace who has been paying who)
    accountability (if sth goes wrong, Alice/Merchant can prove what happened?)
	at some level, fundamentally at odds with anonymity
    scalability (avoid single points of failure, perf bottlenecks, trust roots)
    reliability (backups in some cases at odds with no-double-spending)
    we will look at a few of these..

Offline transactions
    Our simple e-check scheme requires online access to bank to either:
	generate a cashier's check, or
	verify a non-cashier's check
    Ideally, would like offline transactions

    One approach: use trusted hardware (smartcards) to distribute the bank
	each user's smartcard is a clone of the bank
	has the bank's PK_B/SK_B
	keeps user's account balance

    What happens if M wants to cash a check from A?
	M talks to A's smartcard to convert A's check into a cashier's check
	    A's smartcard uses its SK_B to counter-sign the cashier's check
	    this operation decrements A's account balance
	M talks to M's smartcard to deposit cashier's check into its own account
	    M's smartcard need not talk to anyone else; check signed by SK_B
	    key property: each account stored on exactly one smartcard
	    (otherwise, could deposit the same cashier's check twice)

Anonymous transactions
    In our e-check scheme, all parties know everyone
	bank knows what customers bought what amounts from what merchants
	merchant knows customer
	customer knows merchant
	merchant and customer know the bank

    How important are each of these?
	merchant, customer know the bank: seems OK.
	merchant, customer know each other: problem for anonymous services
	    or users (e.g. users or services communicating over Tor).
	bank knows transaction details: potential worry that bank, or
	    anyone with access to bank's computer, can spy on purchases?

    What does anonymity mean in an account-based system?

	  +--------- Bank <---------+
	  |			    |
	  | Withdraw		    | Deposit
	  |			    |
	  V			    |
	Alice ----------------> Merchant
		    Pay

    One goal: we want bank to not know who withdrew the money being deposited

    Do we really want anonymity?
	problem: what happens if Merchant runs off with your money?
	today: complain to bank, bank will compel Merchant to provide service,
	    or revert the transaction.
	with anonymity: bank doesn't know what transaction was yours, so can't
	    tell who is right and who is wrong.
	problem might be solvable if we can formally define Merchant's service
	    e.g. reveal a string whose SHA-1 hash value is h (buy a PDF?)
	    typical solution is to use a trusted third party (could be the bank)
	    TTP ensures response is correct before forwarding payment
	    some optimizations might eliminate TTP on common path (Micali's
		Fair Electronic Exchange)

Anonymous cash scheme (David Chaum)
    Bank uses RSA:
	PK_B = (n, e)
	SK_B = (d)

    Blind signature protocol:

	    user					bank

	picks random r
	picks message m
				x = m * r^e
		    ------------------------------->
						      y = x^d
							= (m * r^e)^d
							= m^d * r^ed
							= m^d * r
				y = m^d * r
		    <-------------------------------
	z = y/r
	  = (m^d * r) / r
	  = m^d
	  = Sign(SK_B, m), even though bank does not know m!

    We can use blind signatures to create coins:
	user picks a random coin serial number# for m
	a valid coin is (m, m^d) -- i.e. serial# signed by the bank
	user & bank authenticate each other, so bank knows the user
	bank withdraws coin value from user's account for each blind signature
	(i.e. bank needs a separate PK/SK for each coin value it supports)

    Already an improvement over the e-checks scheme
	a coin (m, m^d) is a fixed-value cashier's check to any recipient
	payer (Alice) can pre-generate coins ahead of time
	when coin is deposited, bank doesn't know where it came from
	bank still checks for duplicate serial numbers

    Slight RSA problem: can generate new signatures by multiplying signatures
	solution: structure m to be so that product of two m's will not be valid
	e.g. m = r || h(r), where r is randomly chosen
	verify that m has the right structure before accepting coin

What can we do about double-spending?
    Double-spending with anonymity is problematic; don't know who to blame.
    One solution is merchants immediately deposit all coins; can we do better?
    Idea: make payment anonymous _except_ if the user double-spends
    .. next lecture