Navigating Bitcoin Transactions

Navigating Bitcoin Transactions

• 1. CS 4593/6463 – Bitcoins and Cryptocurrencies Note: most of the slides used in this course are derived from those available for the book “Bitcoins and Cryptocurrencies Technologies – A Comprehensive Introduction”, Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller & Steven Goldfeder, 2016, Princeton University Press. Prof. Murtuza Jadliwala murtuza.jadliwala@utsa.edu

• 2. Lecture 3 Mechanics of Bitcoin

• 3. Recap: Bitcoin consensus Bitcoin consensus gives us: • Append-only ledger • Decentralized consensus protocol • Miners to validate transactions Assuming a currency exists to motivate miners! In this chapter we will see how such a currency can be engineered

• 4. Bitcoin transactions

• 5. An account-based ledger (not Bitcoin) Create 25 coins and credit to AliceASSERTED BY MINERS Transfer 17 coins from Alice to BobSIGNED(Alice) Transfer 8 coins from Bob to CarolSIGNED(Bob) Transfer 5 coins from Carol to AliceSIGNED(Carol) SIMPLIFICATION: only one transaction per block time Transfer 15 coins from Alice to DavidSIGNED(Alice) might need to scan backwards until genesis! is this valid?

• 6. A transaction-based ledger (Bitcoin) Inputs: Ø Outputs: 25.0→Alice No signature required Inputs: 1[0] Outputs: 17.0→Bob, 8.0→Alice SIGNED(Alice) SIMPLIFICATION: only one transaction per block time is this valid? finite scan to check for validity Inputs: 2[0] Outputs: 8.0→Carol, 7.0→Bob SIGNED(Bob) Inputs: 2[1] Outputs: 6.0→David, 2.0→Alice SIGNED(Alice) we implement this with hash pointers change address 1 2 3 4

• 7. Merging value Inputs: ... Outputs: 17.0→Bob, 8.0→Alice SIGNED(Alice) SIMPLIFICATION: only one transaction per block time Inputs: 1[1] Outputs: 6.0→Carol, 2.0→Bob SIGNED(Alice) Inputs: 1[0], 2[1] Outputs: 19.0→Bob SIGNED(Bob) .. . .. . 1 2 3

• 8. Joint payments Inputs: ... Outputs: 17.0→Bob, 8.0→Alice SIGNED(Alice) SIMPLIFICATION: only one transaction per block time Inputs: 1[1] Outputs: 6.0→Carol, 2.0→Bob SIGNED(Alice) Inputs: 2[0], 2[1] Outputs: 8.0→David SIGNED(Carol), SIGNED(Bob) .. . .. . two signatures! 1 2 3

• 9. The real deal: a Bitcoin transaction { "hash":"5a42590fbe0a90ee8e8747244d6c84f0db1a3a24e8f1b95b10c9e050990b8b6b", "ver":1, "vin_sz":2, "vout_sz":1, "lock_time":0, "size":404, "in":[ { "prev_out":{ "hash":"3be4ac9728a0823cf5e2deb2e86fc0bd2aa503a91d307b42ba76117d79280260", "n":0 }, "scriptSig":"30440..." }, { "prev_out":{ "hash":"7508e6ab259b4df0fd5147bab0c949d81473db4518f81afc5c3f52f91ff6b34e", "n":0 }, "scriptSig":"3f3a4ce81...." } ], "out":[ { "value":"10.12287097", "scriptPubKey":"OP_DUP OP_HASH160 69e02e18b5705a05dd6b28ed517716c894b3d42e OP_EQUALVERIFY OP_CHECKSIG" } ] } input(s) metadata output(s)

• 10. The real deal: transaction metadata { "hash":"5a42590...b8b6b", "ver":1, "vin_sz":2, "vout_sz":1, "lock_time":0, "size":404, ... } housekeeping housekeeping transaction hash “not valid before” more on this later... also serves as a unique ID

• 11. The real deal: transaction inputs "in":[ { "prev_out":{ "hash":"3be4...80260", "n":0 }, "scriptSig":"30440....3f3a4ce81" }, ... ], signature previous transaction (more inputs)

• 12. The real deal: transaction outputs "out":[ { "value":"10.12287097", "scriptPubKey":"OP_DUP OP_HASH160 69e...3d42e OP_EQUALVERIFY OP_CHECKSIG" }, ... ] output value recipient address?? (more outputs) more on this soon... Sum of all output values less than or equal to sum of all input values! If sum of all output values less than sum of all input values, then difference goes to miner as a transaction fee

• 13. Bitcoin scripts

• 14. Output “addresses” are really scripts OP_DUP OP_HASH160 69e02e18... OP_EQUALVERIFY OP_CHECKSIG

• 15. Input “addresses” are also scripts OP_DUP OP_HASH160 69e02e18... OP_EQUALVERIFY OP_CHECKSIG 30440220... 0467d2c9... scriptSig scriptPubKey TO VERIFY: Concatenated script must execute completely with no errors (from the redeeming transaction) (from the transaction being redeemed)

• 16. Bitcoin scripting language (“Script”) Design goals • Built for Bitcoin (inspired by Forth) • Simple, compact • Support for cryptography • Stack-based (linear) • Limits on time/memory • No looping • Result: Bitcoin script is not Turing Complete! i.e, cannot compute arbitrarily powerful functions • Advantage: No infinite looping problem! image via Jessie St. Amand I am not impressed

• 17. Bitcoin scripting language (“Script”) • 256 instructions (each represented by 1 byte) • 75 reserved, 15 disabled • Basic arithmetic, basic logic (“if” → “then”), throwing errors, returning early, crypto instructions (hash computations, signature verifications), etc. •Only two possible outcomes of a Bitcoin script • Executes successfully with no errors → transaction is valid OR • Error while execution → transaction invalid and should not be accepted in the block chain

• 18. Common script instructions Name Functions OP_DUP Duplicates top item on the stack OP_HASH160 Hashes twice: first using SHA-256, then using RIPEMD-160 OP_EQUALVERIFY Returns true if inputs are equal, false (marks transaction invalid) otherwise OP_CHECKSIG Checks that the input signature is valid using input public key for the hash of the current transaction OP_CHECKMULTISIG Checks that t signatures on the transaction are valid from t (out of n) of the specified public keys

• 19. OP_CHECKMULTISIG • Built-in support for joint signatures • Specify n public keys • Specify t • Verification requires t signatures are valid BUG ALERT: Extra data value popped from the stack and ignored

• 20. Bitcoin script execution example <sig> <pubKey> OP_DUP OP_HASH160 <pubKeyHash?> OP_EQUALVERIFY OP_CHECKSIG <sig> <pubKey> <pubKey> ✓ <pubKeyHash?> <pubKeyHash> true

• 21. Bitcoin scripts in practice (as of 2014) • Most nodes whitelist known scripts • 99.9% are simple signature checks • ~0.01% are MULTISIG • ~0.01% are Pay-to-Script-Hash • Remainder are errors, proof-of-burn More on this soon

• 22. Proof-of-burn OP_RETURN <arbitrary data> nothing’s going to redeem that

• 23. Should senders specify scripts? I’m ready to pay for my purchases! Big Box Cool! Well we’re using MULTISIG now, so include a script requiring 2 of our 3 account managers to approve. Don’t get any of those details wrong. Thanks for shopping at Big Box! ?

• 24. Idea: use the hash of redemption script OP_HASH160 <hash of redemption script> OP_EQUAL <signature> <<pubkey> OP_CHECKSIG> “Pay to Script Hash” <signature> <pubkey> OP_CHECKSIG

• 25. Pay to script hash I’m ready to pay for my purchases! Big Box Great! Here’s our address: 0x3454

• 26. Applications of Bitcoin scripts

• 27. Example 1: Escrow transactions PROBLEM: Alice wants to buy online from Bob. Alice doesn’t want to pay until after Bob ships. Bob doesn’t want to ship until after Alice pays. Pay x to 2-of-3 of Alice, Bob, Judy (MULTISIG) SIGNED(ALICE) Alice Bob To: Alice From: Bob Pay x to Bob SIGNED(ALICE, BOB) (normal case) Pay x to Alice SIGNED(ALICE, JUDY) (disputed case) Judy

• 28. Example 2: Green addresses Alice PROBLEM: Alice wants to pay Bob. Bob Bob can’t wait 6 verifications to guard against double-spends, or is offline completely. Pay x to Bob, y to Bank SIGNED(BANK) Faraday cage It’s me, Alice! Could you make out a green payment to Bob? Bank No double spend 004 days since last double spend!

• 29. Example 3: Efficient micro-payments Alice Bob PROBLEM: Alice wants to pay Bob for each minute of phone service. She doesn’t want to incur a transaction fee every minute. Input: x; Pay 01 to Bob, 99 to Alice SIGNED(ALICE)___________ Input: x; Pay 02 to Bob, 98 to Alice SIGNED(ALICE)___________ Input: x; Pay 03 to Bob, 97 to Alice SIGNED(ALICE)___________ Input: x; Pay 04 to Bob, 96 to Alice SIGNED(ALICE)___________ Input: x; Pay 42 to Bob, 58 to Alice SIGNED(ALICE)___________ ... I’m done! I’ll publish! all of these could be double-spends! Input: y; Pay 100 to Bob/Alice (MULTISIG) SIGNED(ALICE) Input: x; Pay 42 to Bob, 58 to Alice SIGNED(ALICE) SIGNED(BOB) What if Bob never signs?? Input: x; Pay 100 to Alice, LOCK until time t SIGNED(ALICE) SIGNED(BOB) Alice demands a timed refund transaction before starting

• 30. lock_time { "hash":"5a42590...b8b6b", "ver":1, "vin_sz":2, "vout_sz":1, "lock_time":315415, "size":404, ... } Block index or real-world timestamp before which this transaction can’t be published

• 31. More advanced scripts • Multiplayer lotteries • Hash pre-image challenges • Coin-swapping protocols • Don’t miss the lecture on anonymity! “Smart contracts”

• 32. Bitcoin blocks

• 33. Bitcoin blocks Why bundle transactions together? • Single unit of work for miners • Limit length of hash-chain of blocks • Faster to verify history

• 34. trans: H( ) prev: H( ) Bitcoin block structure trans: H( ) prev: H( ) trans: H( ) prev: H( ) H( ) H( ) H( ) H( ) H( ) H( ) transaction transaction transaction transaction Hash chain of blocks Hash tree (Merkle tree) of transactions in each block

• 35. The real deal: a Bitcoin block { "hash":"00000000000000001aad2...", "ver":2, "prev_block":"00000000000000003043...", "time":1391279636, "bits":419558700, "nonce":459459841, "mrkl_root":"89776...", "n_tx":354, "size":181520, "tx":[ ... ], "mrkl_tree":[ "6bd5eb25...", ... "89776cdb..." ] } transaction data block header

• 36. The real deal: a Bitcoin block header { "hash":"00000000000000001aad2...", "ver":2, "prev_block":"00000000000000003043...", "time":1391279636, "bits":419558700, "nonce":459459841, "mrkl_root":"89776...", ... } mining puzzle information hashed during mining not hashed

• 37. The real deal: coinbase transaction "in":[ { "prev_out":{ "hash":"000000.....0000000", "n":4294967295 }, "coinbase":"..." }, "out":[ { "value":"25.03371419", "scriptPubKey":"OPDUP OPHASH160 ... ” } arbitrary redeeming nothing Null hash pointer First ever coinbase parameter: “The Times 03/Jan/2009 Chancellor on brink of second bailout for banks” block reward transaction fees

• 38. See for yourself! blockchain.info (and many other sites)

• 39. The Bitcoin network

• 40. Bitcoin P2P network • Ad-hoc protocol (runs on TCP port 8333) • Ad-hoc network with random topology • All nodes are equal • New nodes can join at any time • Forget non-responding nodes after 3 hr

• 41. Joining the Bitcoin P2P network 1 6 4 7 3 5 2 8 Hello World! I’m ready to Bitcoin! getaddr () 1, 7 getaddr () getaddr ()

• 42. Transaction propagation (flooding) 1 6 4 7 3 5 2 8 New tx! A→B A→B A→B A→B A→B A→B A→B A→B A→B A→B A→B Already heard that!

• 43. Should I relay a proposed transaction? • Transaction valid with current block chain(default) • Run script for each previous output being redeemed and ensure that script returns true! • Script matches a whitelist • Avoid unusual scripts • Haven’t seen before • Avoid infinite loops • Doesn’t conflict with others I’ve relayed • Avoid double-spends Sanity checks only... Well-behaving nodes implement them! Some nodes may ignore them!

• 44. Nodes may differ on transaction pool 1 6 4 7 3 5 2 8 A→B A→B A→B A→B A→B A→B New tx! A→C A→C A→C A→B A→C A→C A→B A→C

• 45. Race conditions Transactions or blocks may conflict • Default behavior: accept what you hear first • Network position matters • Miners may implement other logic! Stay tune for the lecture on mining!

• 46. Block propagation nearly identical Relay a new block when you hear it if: • Block meets the hash target • Block has all valid transactions • Run all scripts, even if you wouldn’t relay • Block builds on current longest chain • Avoid forks Sanity check Also may be ignored...

• 47. Source: Yonatan Sompolinsky and Aviv Zohar: “Accelerating Bitcoin’s Transaction Processing” 2014

• 48. How big is the network? • Impossible to measure exactly • Estimates-up to 1M IP addresses/month • Only about 5-10k “full nodes” • Permanently connected • Fully-validate • This number may be dropping!

• 49. Fully-validating nodes • Permanently connected • Store entire block chain • Hear and forward every node/transaction

• 50. Storage costs (in 2014) 20 GB

• 51. Storage costs (in 2018) 160 GB Source: blockchain.info

• 52. Tracking the UTXO set • Unspent Transaction Output • Should be stored in memory - everything else can be stored on disk, why? 65 M Source: blockchain.info

• 53. Tracking the UTXO set • Currently ~65 M UTXOs • Out of 300 M transactions • Can require several Gigabytes to store – can it fit in the RAM of a standard computer? 300 M Source: blockchain.info

• 54. Thin/SPV clients (not fully-validating) SPV – Simplified Payment Verification (e.g., Wallet nodes) Idea: Don’t store everything • Store block headers – verify the puzzle was solved correctly, but cannot verify every transaction in each blocl! • Validate only those transactions that affect them → By requesting transactions as needed • To verify incoming payment • Trust fully-validating nodes 1000x cost savings! Requires only a few tens of Megabytes (compare to tens of Gigabytes needed for fully validating nodes)

• 55. Software diversity • About 90% of nodes run “Core Bitcoin” (C++) • Some are out of date versions • Other implementations running successfully • BitcoinJ (Java) • Libbitcoin (C++) • btcd (Go) • “Original Satoshi client”

• 56. Limitations & Improvements

• 57. Hard-coded limits in Bitcoin • 10 min. average creation time per block • 1 M bytes in a block • 20,000 signature operations per block • 100 M satoshis per bitcoin • 23M total bitcoins maximum • 50,25,12.5... bitcoin mining reward These affect economic balance of power too much to change now

• 58. Throughput limits in Bitcoin • 1 M bytes/block (10 min) • >250 bytes/transaction • 7 transactions/sec Compare to: • VISA: 2,000-10,000 transactions/sec • PayPal: 50-100 transaction/sec

• 59. Cryptographic limits in Bitcoin • Only 1 signature algorithm (ECDSA/P256) • Hard-coded hash functions Crypto primitives might break by 2040...

• 60. “Hard-forking” changes to Bitcoin 1 6 4 7 3 5 2 8 I found a nifty new block! Block 24 Block 24 Block 24 Block 24 Block 24 Block 23 Block 23 Block 23 Block 23 Block 23 Block 23 Block 23 Block 23 24 24 24 24 That’s crazy talk!! That’s crazy talk!! PROBLEM: Old nodes will never catch up

• 61. Soft forks Observation: we can add new features which only limit the set of valid transactions Need majority of nodes to enforce new rules Old nodes will approve RISK: Old nodes might mine now-invalid blocks

• 62. Soft fork example: pay to script hash OP_HASH160 <hash of redemption script> OP_EQUAL <signature> <<pubkey> OP_CHECKSIG> Old nodes will just approve the hash, not run the embedded script

• 63. Soft fork possibilities • New signature schemes • Extra per-block metadata • Shove in the coinbase parameter • Commit to UTXO tree in each block

• 64. Hard forks • New op codes • Changes to size limits • Changes to mining rate • Many small bug fixes Stay tuned for the lecture on altcoins! Currently seem very unlikely to happen

• 65. In the next lecture...

• 66. Human beings aren’t Bitcoin nodes • How do people interact with the network? • How do people exchange bitcoins for cash? • How do people securely store bitcoins? Currency needs to work for people, not nodes