Bitcoin as a Platform Notes

Bitcoin as a Platform

Key uses of Bitcoin as a platform:

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

Bitcoin as an Append-Only Log (Secure Timestamping)

  • Goal: Prove knowledge of x at time t, possibly without revealing x. Evidence should be permanent.
  • Publishing H(x) is a commitment tox. We cannot find an x' != x later such that H(x') = H(x)
  • H(x) reveals no information about x if the space of possible x is large.
  • Publish a commitment to x now and reveal x later.

Applications for Secure Timestamping

  • Proof of knowledge
  • Proof of receipt
  • Hash-based signature schemes
  • Many more

Non-Application: Proof of Clairvoyance

  • Proving clairvoyance requires proving that you didn’t timestamp multiple predictions.
  • Offline solution: Newspaper timestamp

Timestamping in Bitcoin

  • Specify the hash of your data instead of a valid public key and send 1 satoshi to the address.
    • Pros: compatible, easy
    • Cons: creates unspendable UTXO forever

CommitCoin

  • Brute-force a public key & signature starting with the first n bits of your data hash. [Cark, Essex 2012]
    • Pros: compatible, “invisible”, no UTXO bloat
    • Cons: expensive, low data rate

Provably Unspendable Commitments

  • Use the OP_RETURN opcode.
    • Syntax: OP_RETURN <arbitrary data>
    • Pros: cheap, no UTXO bloat
    • Cons: not a standard transaction

Data Rates

  • 40-byte commitments for 1 TX fee – 0.00005 BTC (Spring 2017, US$0.05)
  • Enough to commit to the hash of whatever you want!

Block Chain Poisoning

  • In general, preventing poisoning is not possible.
  • Pay-to-script-hash makes it a bit more expensive.
  • Food-for-thought: Can miners refuse to include “poison” transactions?

Overlay Currencies

  • 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

Bitcoins as "Smart Property"

  • Every Bitcoin carries a history (bad for anonymity, enables blacklisting).
  • Bitcoins aren’t fungible; every one is unique

Adding Metadata to Currency

  • Authenticated Metadata for Currency: Sign desired metadata + banknote serial #. SIGN_K(M, #)
  • 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

Colored Coins

  • Coins are issued by passing through P2SH address; issuer declares address with an exchange.
  • Special unspendable “marker” output is inserted.
    • Match colored inputs to outputs
    • Can add extra metadata
    • Pros:
      • compatible with Bitcoin
      • flexible to represent any asset
      • ignored by community
    • Cons:
      • small cost of unspendable markers
      • must check every previous transaction

Applications of Colored Coins

  • Stock certificates
  • Tickets
  • Deeds to real-world property (houses, cars)
  • Ownership of domain names
  • NameCoin

Secure Multi-Party Lotteries in Bitcoin

Real-World Lotteries without Trust

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

Lottery with Hash Commitments

  • Alice, Bob, and Carol choose random x, y, and z, respectively.
  • Round 1: Publish H(x), H(y), H(z)
  • Round 2: Reveal x, y, and z
  • w = H(x \oplus y \oplus z) \% 3
  • If w = 0, Alice wins; if w = 1, Bob wins; if w = 2, Carol wins.
  • Hash function guarantees nobody can win with probability more than 1/3 time.

Failure to Reveal Commitment

  • Timed Hash Commitments: 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!
  • Bond
    • Input: 1; Pay B to Bob: n_lock_time: t; SIGNED(Alice) SIGNED(Bob)
    • Bob can claim the bond at time t
  • Input: 1; Pay B to Alice: SIGNED(Alice), x
  • x revealed if Alice reclaims her bond

Lottery with Timed Commitments

  • Round 1: Timed commitment to H(x), H(y), H(z)
  • Round 2: Reveal x, y, and z
  • w = H(x \oplus y \oplus z) \% 3
  • If w = 0, Alice wins; if w = 1, Bob wins; if w = 2, Carol wins.
Pros:
  • Can be implemented on Bitcoin today
Cons:
  • Complexity is O(N^2)
  • Bonds must be higher than amount bet
  • Griefers might shut down large pools

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?

Cryptographic Beacons

  • Service to regularly publish random data
    • Uniform randomness
    • No party can predict in advance
    • All parties see the same values
  • Applications: lotteries, auditing, zero-knowledge proofs, cut-and-choose
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

Pros

Publicly observable, random

Cons

Slow, need a trusted observer? Sun spots, Cosmic background radiation, Weather

Stock-market Beacon

Pros

Good randomness, costly to manipulate

Cons

Slow, insider attacks?

Block Chain as Beacon

  • 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^{66}
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” 12.5 BTC.
  • Single coin flip: secure wager is < 12.5 BTC
  • N-party lottery: secure if pool is < 12.5(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 (not synchronized with real time)
  • Need to delay to ensure against forks
  • Manipulation may be too cheap for some applications

Built-in Beacon Support in Scripts

  • Add an opcode for a beacon call
  • Can build multi-party lotteries
    • Only one round
    • No bonds
    • No time delay for refunds

Prediction Markets

Assertions about the Outside World

  • Add a mechanism to assert facts about 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 potential future event
  • Shares are worth X if the event happens, 0 if not
  • Current price / X = estimated probability

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 (Clark et al. 2014)
  • BuyPortfolio(event e): one share in every outcome for $1
  • TradeShares(...): exchange shares for each other or currency
  • SellPortfolio(event e): redeem one share in every outcome for $1

Arbitration Model

  • 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!

Order Books

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
  • 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

Conclusion

  • Bitcoin can only take us so far.
  • What if we could start again from scratch?