Lecture 9

Bitcoin as a platform

In this lecture

We’ve built Bitcoin. What can we build on top?

​

• Commitments
• Token tracking
• Multiparty lotteries
• Public randomness
• Prediction markets

A fine stew o’ ideas

Lecture 9.1:

​

Bitcoin as an append-only log

Secure timestamping

Goal: Prove knowledge of x at time t

​

If desired, without revealing x at time t

​

Evidence should be permanent

Hash commitments

Recall: Publishing H(x) is a commitment to x

​

• Can’t find an x’≠x later s.t. H(x’) = H(x)

​

• H(x) reveal no information* about x

*assuming the space of possible x is big

Can publish a commitment to x, reveal later

Secure timestamping applications

• Proof of knowledge
• Proof of receipt
• Hash-based signature schemes
• many, many more...

Non-application: proof of clairvoyance

Proof that FIFA is corrupt??

Proving clairvoyance requires proving you didn’t timestamp multiple predictions

Offline solution: newspaper timestamp

Timestamping in Bitcoin

• Idea: Specify the hash of your data instead of a valid public key
• Send 1 satoshi to the address

​

Pros: compatible, easy

Cons: creates unspendable UTXO forever

Timestamping in Bitcoin: CommitCoin

• Clark, Essex 2012
• Idea: Brute-force a public key & signature starting with the first n bits of your data hash

​

Pros: compatible, “invisible”, no UTXO bloat

Cons: more expensive, low data rate

Provably unspendable commitments

OP_RETURN

<arbitrary data>

Pros: cheap, no UTXO bloat

Cons: not a standard transaction

Data rates

40-byte commitments for 1 TX fee

• 0.0001 BTC (currently ≈ US$0.05)

​

Enough to commit to the hash of whatever you want!

Block chain poisoning

☹

Can we prevent poisoning?

• In general, no ☹

​

• Pay-to-script-hash makes it more expensive

​

​

Overlay currencies

• Observation: timestamping is all we need!

​

• Write all data to the Bitcoin block chain
• No new mining/consensus required
• Invalid transactions may now be included
• Need new rules-first valid tx wins

​

​

Mastercoin

• Goals: overlay currency with richer transaction set
• Smart property, smart contracts
• User-defined currency

Pros: more features, faster development

Cons: reliant on Bitcoin, can be inefficient

Lecture 9.2:

​

Bitcoins as “smart property”

Recall: the transaction graph

Every bitcoin* carries a history

Coinbase

Coinbase

*There are no “bitcoins”, just unspent tx outputs

• Bad for anonymity
• Enables blacklisting
• Observation: bitcoins aren’t fungible! Every one is unique

​

​

Can this property be useful?

Adding metadata to currency

Without limitations on issuance, just a novelty

Authenticated metadata for currency

Stadium

Idea: sign desired metadata + banknote serial #

“Bill #L11180916G hereby grants the holder admission to the Yankees game on Aug 18, 2014”

SIGN_K(M, #)

Authenticated metadata for currency

• Currency can now

represent anything!

• Anti-counterfeiting

properties are inherited

• Underlying value also maintained!
• New meaning relies on trust in the issuer
• Some users may not understand new metadata

Can we build this on top of Bitcoin?

Colored coins

ISSUE 5

12

5

7

ISSUE 4

4

9

4

5

9

3

1

ISSUE 9

9

5

13

Implementation: OpenAssets protocol

• Coins issued by passing through P2SH address
• Issuer declares address with an exchange
• Special unspendable “marker” output inserted
• Match colored inputs to outputs
• Can add extra metadata

Colored Coins

• Pros
• compatible with Bitcoin
• flexible to represent any asset
• ignored by community
• Cons
• small cost of unspendable markers
• must check every previous tranasction

Applications

• stock certificates
• tickets
• deeds to real-world property
• houses?
• cars?
• ownership of domain names

NameCoin... stay tuned for our lecture on Altcoins!

Lecture 9.3:

​

Secure multi-party lotteries in Bitcoin

Real-world lotteries without trust*

*The outcome is fair, but both parties have to trust the other will actually pay up

Alice

Bob

Wanna bet $5

Sure, I’ll take heads!

Online lotteries without trust?

Alice

Bob

Problem: Alice and Bob want to bet on a coin flip remotely

I’ll bet $5 on heads!

But I can’t see your coin!

Network

Hash commitments

Recall: Publishing H(x) is a commitment to x

​

• Can’t find an x’≠x later s.t. H(x’) = H(x)

​

• H(x) reveal no information* about x

​

*assuming the space of possible x is big

A lottery with hash commitments

Alice

Bob

Carol

time

Choose random y

Choose random x

Choose random z

Round 1

Publish H(x)

Publish H(y)

Publish H(z)

Publish x

Publish y

Publish z

Round 2

w= H(x⊕y⊕z) % 3

switch (w){

case 0:

winner = Alice;

case 1:

winner = Bob;

case 2:

winner = Carol;

}

Hash function guarantees nobody can win with probability more than 1/3

Failure to reveal commitment

Alice

Bob

Carol

time

Choose random y

Choose random x

Choose random z

Round 1

Publish H(x)

Publish H(y)

Publish H(z)

Publish x

Publish y

Round 2

w= H(x⊕y⊕z) % 3

switch (w){

case 0:

winner = Alice;

case 1:

winner = Bob;

case 2:

winner = Charlie;

}

I’m about to lose...

Ø

Sorry! I, uhh, forgot z

Sorry! I, uhh, forgot z

Not cool Carol ☹

Timed hash commitments

Idea: Force x to be revealed by time t

Input: ...; Pay B to EITHER OF:

Alice & Bob, or

Alice & anybody who knows x st. H(x) = c

​

SIGNED(Alice)

1

MULTISIG

New script!

Input: 1; Pay B to Bob:

n_lock_time: t

​

SIGNED(Alice) SIGNED(Bob)

2

Bob can claim the bond at time t

Bond

Input: 1; Pay B to Alice:

​

SIGNED(Alice), x

3

x revealed if Alice reclaims her bond

Lottery with timed commitments

Alice

Bob

Carol

time

Choose random y

Choose random x

Choose random z

Round 1

Timed commitment to H(x)

Timed commitment to H(y)

Timed commitment to H(z)

Publish x

Publish y

Round 2

w= H(x⊕y⊕z) % 3

switch (w){

case 0:

winner = Alice;

case 1:

winner = Bob;

case 2:

winner = Carol;

}

I’m about to lose...

But I’ll lose my bond if I don’t publish ☹

Lottery with timed commitments

Pros:

• can be implemented on Bitcoin today
• Andrychowicz, Dziembowski, Malinowski, Mazurek 2014

Cons:

• complexity is O(N²)
• bonds must be higher than amount bet
• griefers still might shut down large pools

Lecture 9.4:

​

Bitcoin as randomness source

Public randomness protocols

• Too many interested parties to use hashes?
• More convincing randomness to the public?
• Designers don’t know alternatives available?

​

NBA draft lottery

1985: Knicks win rights to Patrick Ewing

1969 Vietnam conscription lottery

Late-year birthday bias

Cryptographic beacons

Idea: service to regularly publish random data

• Uniform randomness
• No party can predict in advance
• All parties see the same values

01010001 01101011 10101000 11110000 10010100

Applications: lotteries, auditing, zero-knowledge proofs, cut-and-choose, ...

Public display of randomness

Pros: cheap, easy, simple to understand

Cons: must trust/audit operator

hard to trust remotely!

NIST beacon

Pros: quantum-mechanical randomness

Cons: must trust NIST

Natural phenomena

Sun spots

Cosmic background radiation

Weather

Pros: publicly observable, random

Cons: slow, need a trusted observer?

Stock-market beacon

Pros: good randomness, costly to manipulate

Cons: slow, insider attacks?

Why not use the block chain?

Recall: miners find random nonce for each block

​

​

If you could predict the next nonce with a greater than 1/d probability, you’d have a mining shortcut

Currently, d > 2⁶⁶

​

​

Turning the block chain into a beacon

mrkl_root: H( )

prev: H( )

mrkl_root: H( )

hash: 0x0000

nonce: 0x7a83

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

mrkl_root: H( )

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

Extract

Extract

Extract

01010001 10101000 10010100

Cost of manipulation

Attacker might mine a block but discard it

• Or bribe other miners to do so

​

Bernoulli trials: forcing a beacon outcome with probability p requires discarding 1/p - 1 blocks

​

Discarding a block “costs” 25 BTC

Cost of manipulation

Single coin flip: secure if wager is < 25 BTC

​

N-party lottery: secure if pool is < 25 (n-1) BTC

​

Pros

• First proposal for fully decentralized beacon
• Output every 10 minutes
• Can precisely analyze manipulation costs
• Can extend security with multiple blocks
• Not very efficient

Cons

• Timing is imprecise
• Block chain not synchronized w/ real time
• Need to delay to insure against forks
• Manipulation may be too cheap for some applications

Built-in beacon support in script

• Idea: add an opcode for a beacon call
• Can build multi-party lotteries
• only one round
• no bonds
• no time delay for refunds

Lecture 9.5:

​

Prediction markets & real-world data feeds

Assertions about the outside world

• Idea: add a mechanism to assert facts
• election outcomes
• sports results
• commodity prices
• Bet or hedge results using smart contracts
• Forwards, futures, options...

Most general formulation: prediction market

Prediction markets

• Idea: trade shares in a potential future event
• Shares worth X if the event happens, 0 if not
• Current price / x = estimated probability

Example: World Cup 2014

0.12 0.09 0.22 0.01 0.05

pre-tournament

0.18 0.15 0.31 0.06 0.00

after group stage

0.26 0.21 0.45 0.00 0.00

before semis

0.64 0.36 0.00 0.00 0.00

before finals

1 0 0 0 0

final

Can immediately profit!

Should have shorted

Example: 2008 US Presidential election

source: Iowa Electronic Markets

Prediction markets

• Economists love them
• reveal all knowledge about the future
• (under a number of assumptions)
• allows profit from accurate predictions
• “a tax on BS”
• Often beat polls and expert opinions
• Significant regulatory hurdles
• InTrade shut down in 2013

Decentralized prediction markets?

• Decentralized payment & enforcement
• Decentralized arbitration
• Decentralized order book

​

Decentralized payment & settlement

• Simple solution: Bitcoin + trusted arbiters
• Better solution: altcoin with built-in support

Payment & settlement - FutureCoin

• BuyPortfolio(event e)
• one share in every outcome for $1
• TradeShares(...)
• exchange shares for each other or currency
• one way of profiting
• SellPortfolio(event e)
• redeem one share in every outcome for $1

Clark et al. 2014

Arbitration models

• Trusted arbiters
• allow anybody to define & open a market
• risk of incorrect arbitration, absconding
• Users vote
• requires incentives, bonds, reputation
• keynesian beauty contest?
• Miners vote
• may be disinterested or not know

​

RealityKeys

Reality can be complicated!

Super Bowl XLVIII:

what color gatorade will be poured on the winning coach?

Clear:0.31 Orange:0.22 Yellow:0.22 Blue:0.08 Red:0.08 Green:0.08

Orange?

Yellow?

Order books

• Goal: match best bid and ask offers

​

Predictious.com

Centralized order books

• Traditional model
• Promise to split surplus between buyer, seller
• Front-running is considered a serious crime!
• require regulation, auditing, monitoring

​

Decentralized order books

• Idea: Submit orders to miners, let them match any possible trade
• Spread is retained as a transaction fee
• Front-running now not profitable!
• May be less efficient
• Higher fees
• Slower trades to avoid higher fees

​

Decentralized order books

• Idea: Submit orders to miners, let them match any possible trade
• Spread is retained as a transaction fee
• Front-running now not profitable!
• May be less efficient
• Higher fees
• Slower trades to avoid higher fees

​

What can be built on Bitcoin?

Bitcoin isn’t enough

In the next lecture

​

Bitcoin can only take us so far

​

​

​

What if we could start again from scratch?

​