CSCI301 Contemporary Topics in Security Components of bitcoin PDF

CSCI301 Contemporary Topics in Security Components of bitcoin Subject Coordinator: A/Prof. Fuchun Guo School of Computing and Information Technology This slide is copyrighted. It must NOT be distributed without permission Bitcoin Proof of Work This slide is copyrighted. It must NOT be distributed wi...

CSCI301 Contemporary Topics in Security Components of bitcoin Subject Coordinator: A/Prof. Fuchun Guo School of Computing and Information Technology This slide is copyrighted. It must NOT be distributed without permission Bitcoin Proof of Work This slide is copyrighted. It must NOT be distributed without permission Recap: Bitcoin consensus Bitcoin consensus gives us: Append-only ledger Decentralized consensus protocol Miners to validate and collect transactions Assuming a currency exists to motivate miners! In this lecture we will see how such a currency can be engineered This slide is copyrighted. It must NOT be distributed without permission Proof-of-work in Blockchain In a blockchain ØNonce is a counter in hashcash ØSummary of a payload contains a hash value of payload in a current block and other information. ØThis enables to check the validity of a new block only using headers of blocks Version Header Payload Hash(Block 99) Hash Version Hash(Block 100) Hash Version Hash(Block 101) Nonce* Summary of Payload100 Nonce* Summary of Payload101 Summary of Payload102 Payload100 Payload101 Payload102 Nonce* This slide is copyrighted. It must NOT be distributed without permission Hash 4 Proof-of-work Blockchain can resolve disagreements using Proof-of-work and the Longest chain rule ØWhen chain forks, Blockchain takes the fork with most work (i.e. longest chain). When there’s a tie, Blockchian keeps working until one of the chains has the most work. Chains have the most work This slide is copyrighted. It must NOT be distributed without permission 5 Proof-of-work Although they contain different transactions and have different hash values, all chains are valid. ØFork chains do not effect to transactions. All transactions are recorded in both chains, but they just recorded differently because they are just added by the other miner. However, incentive is going to the miner who computes the chain in the longest chain. ØIn Bitcoin, miner can use the coin it receives after 100 maturation times (10 min X 100 = 1,000 min.) Sender Reach in an (almost) The transaction is Redeeme immutable depth of chains recoded in a chain A few secondsr Within a 10 min. A few hours This slide is copyrighted. It must NOT be distributed without permission 6 Proof-of-work In this incentive system, it is a loss to one if it spends time and effort for the shorter chain (no follow, no reward). ØThis will automatically make miners to select the block with the most work. Proof-of-work discourages people trying to add invalid blocks to chain.  just like spam filtering system. ØMiners spend a significant money (mostly to buy mining devices and spend a large amount of electricity) to add a block to chain but if it’s not valid, nobody accepts it. Clever design of incentives makes blockchain works. This slide is copyrighted. It must NOT be distributed without permission 7 Proof-of-work (Disadvantage) Expensive—lots of energy used to generate proofs done by “miners” in Bitcoin ØUse special-purpose mining devices (FPGA or GPU) which are optimized for doing proof-of-work. ØHarm for the environment—uses lots of power, accomplishing no useful goal except keeping blockchain working. Slow—put a limit on transaction speed ØEven more than 10 min if you consider the potential disagreements, which must be resolved. ØBitcoin rule of thumb is waiting for 6 blocks (about an hour) to be sure of transactions. This slide is copyrighted. It must NOT be distributed without permission 8 Proof-of-work (Summary) How untrusted, self-interested miners keep the system working ØTo get a maximum benefit, miners verify and spread out a new block and start a new mining for the next block. ØEach node needs to verify a new block in order to decide whether it starts to mine the next block or keep going on current mining. ØThey have a big incentive (BTCs) to follow the protocol (12BTC and then 6.25 bitcoins, this value will halve every 210,000 blocks). ØThey have substantial capital invested in Bitcoin. So, they also have an incentive to avoid any attack that would undermine their investment. ØThis works because Bitcoin is all about moving money around. Therefore, it’s easy to build payoffs into the protocol. This slide is copyrighted. It must NOT be distributed without permission 9 Bitcoin transactions and scripts This slide is copyrighted. It must NOT be distributed without permission Bitcoin block structure Hash chain of blocks prev: H( ) prev: H( ) prev: H( ) trans: H( ) trans: H( ) trans: H( ) H( ) H( ) Hash tree (Merkle tree) of transactions in each block H( ) H( ) It must NOT transaction This slide is copyrighted. transaction be distributed without permission H( ) H( ) transaction transaction An account-based ledger (not Bitcoin) time Create 25 coins and credit to AliceASSERTED BY MINERS Transfer 17 coins from Alice to BobSIGNED(Alice) might need to scan backwards until genesis! Transfer 8 coins from Bob to CarolSIGNED(Bob) Transfer 5 coins from Carol to AliceSIGNED(Carol) Transfer 15 coins from Alice to DavidSIGNED(Alice) SIMPLIFICATION: only one transaction per block This slide is copyrighted. It must NOT be distributed without permission is this valid? A transaction-based ledger (Bitcoin) time 1 2 Inputs: Ø Outputs: 25.0→Alice No signature required change address we implement this with hash pointers Inputs: 1 Outputs: 17.0→Bob, 8.0→Alice SIGNED(Alice) 3 finite scan to check for validity Inputs: 2 Outputs: 8.0→Carol, 7.0→Bob SIGNED(Bob) 4 Inputs: 2 Outputs: 6.0→David, 2.0→Alice is this valid? SIGNED(Alice) This slide isonly copyrighted. It must NOT SIMPLIFICATION: one transaction per block be distributed without permission Merging value time 1 Inputs:... Outputs: 17.0→Bob, 8.0→Alice SIGNED(Alice)... 2 Inputs: 1 Outputs: 6.0→Carol, 2.0→Bob SIGNED(Alice)... 3 Inputs: 1, 2 Outputs: 19.0→Bob SIGNED(Bob) This slide isonly copyrighted. It must NOT SIMPLIFICATION: one transaction per block be distributed without permission Joint payments time 1 Inputs:... Outputs: 17.0→Bob, 8.0→Alice SIGNED(Alice)... 2 Inputs: 1 Outputs: 6.0→Carol, 2.0→Bob SIGNED(Alice)... 3 Inputs: 2, 2 Outputs: 8.0→David two signatures! SIGNED(Carol), SIGNED(Bob) This slide isonly copyrighted. It must NOT SIMPLIFICATION: one transaction per block be distributed without permission Transaction = Output (first) + Input (then) Input: a reference to an output from a previous transaction. (where bitcoin comes from) ØMultiple inputs are often listed in a transaction. All of new transaction's input values are added up. ØPrevious tx is a hash of a previous transaction. ØIndex is the specific output in the referenced transaction (0 or 1). ØScriptSig is the first half of a script. Output: Instruction for sending bitcoins. ØThere can be more than one output, and they share the combined value of the inputs. ØValue is the number of Satoshi (1 BTC = 100,000,000 Satoshi). This output will be worth when claimed. ØScriptPubKey is the second half of a script. Bitcoin Script is a simple, stack-based programming language that is used to define the conditions under which a certain transaction output can be spent (in the future). namely, verify the validity of spending. This slide is copyrighted. It must NOT be distributed without permission 16 Transactions Scripts ØThe script contains two components: ü ScriptSig: , a signature in Input generated by the spender (match previous output) ü ScriptPubKey: a public key of the receipient in Output. ØThe public key (in the current transaction) must match the hash given in the script of the redeemed output (previous transaction). ØThe public key is used to verify the redeemers signature. ØIt, combined with the public key, proves the transaction was created by the real owner of the address in question. This slide is copyrighted. It must NOT be distributed without permission 17 Transactions E.g., a Bitcoin transaction with 1 input and 1 output can be written as Input: …. Previous Transaction Output: Value: 5000000000 scriptPubKey: OP_DUP OP_HASH160 404371705fa9bd789a2fcd52d2c580b65d35549d OP_EQUALVERIFY OP_CHECKSIG Current Transaction Input: Previous tx: f5d8ee39a430901c91a5917b9f2dc19d6d1a0e9cea205b009ca73dd04470b9a6 Index: 0 scriptSig: 304502206e21798a42fae0e854281abd38bacd1aeed3ee3738d9e1446618c4571d10 90db022100e2ac980643b0b82c0e88ffdfec6b64e3e6ba35e7ba5fdd7d5d6cc8d25c6b241501 Output: … This slide is copyrighted. It must NOT be distributed without permission 18 Unspent Transaction Outputs UTXO (Unspent Transaction Outputs) ØThe term UTXO refers to the amount of digital currency someone has left remaining after executing a cryptocurrency transaction such as Bitcoin. ØThis implies that the all outputs which are not yet redeemed by anyone. Alice’s Wallet UTXO(1) 1 BTC UTXO(2) 3 BTC UTXO(3) 2 BTC Alice’s Wallet UTXO(1) 1 BTC UTXO(2) 3 BTC UTXO(3) 2 BTC UTXO(4) 1 BTC 6 BTC 5 BTC This slide is copyrighted. It must NOT be distributed without permission Bob’s Wallet UTXO(1) 1 BTC 1 BTC 19 Pay to Public Key (P2PK) When redeeming coins that have been sent to a Bitcoin public key, the, script validates that the provided signature was generated by the private key that also corresponds to the public key. scriptSig: (current transaction) scriptPubKey: OP_CHECKSIG (previous transaction) Stack Script Description Empty. OP_CHECKSIG scriptSig and scriptPubKey are combined. OP_CHECKSIG Signature is added to the stack. OP_CHECKSIG Pubkey is added to stack. true Empty. Signature is checked. Source: https://wiki.bitcoinsv.io/index.php/Bitcoin_Transactions This slide is copyrighted. It must NOT be distributed without permission 20 Pay-to-Pubkey-Hash (P2PKH) A Bitcoin address (of the recipient) is only a hash, so the sender can't provide a full public key (of recipient) in scriptPubKey. When redeeming coins that have been sent to a Bitcoin address, the recipient (want to spend the coin) should provide both the signature and the public key. The script verifies that the provided public key does hash to the hash in scriptPubKey, and then it also checks the signature against the public key. scriptSig: scriptPubKey: OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG This slide is copyrighted. It must NOT be distributed without permission 21 Pay-to-Pubkey-Hash (P2PKH) Stack Script Description Empty. OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG scriptSig and scriptPubKey are combined. OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG Constants are added to the stack. OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG Top stack item is duplicated. OP_EQUALVERIFY OP_CHECKSIG Top stack item is hashed. OP_EQUALVERIFY OP_CHECKSIG Constant added. OP_CHECKSIG Equality is checked between the top two stack items. true Empty. Signature is checked for top two stack items. Source: https://wiki.bitcoinsv.io/index.php/Bitcoin_Transactions This slide is copyrighted. It must NOT be distributed without permission 22 The real deal: a Bitcoin transaction { metadata input(s) output(s) } "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" } This slide is copyrighted. It must NOT ] be distributed without permission The real deal: transaction metadata { transaction hash housekeeping “not valid before” housekeeping... } "hash":"5a42590...b8b6b", "ver":1, "vin_sz":2, "vout_sz":1, "lock_time":0, "size":404, This slide is copyrighted. It must NOT be distributed without permission also serves as a unique ID message to be signed The real deal: transaction inputs previous transaction signature (more inputs) "in":[ { "prev_out":{ "hash":"3be4...80260", "n":0 }, "scriptSig":"30440....3f3a4ce81" },... ], This slide is copyrighted. It must NOT be distributed without permission The real deal: transaction outputs output value recipient address?? (more outputs) "out":[ { "value":"10.12287097", "scriptPubKey":"OP_DUP OP_HASH160 69e...3d42e OP_EQUALVERIFY OP_CHECKSIG" }, 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 This slide is copyrighted. It must NOT be distributed without permission Bitcoin scripts This slide is copyrighted. It must NOT be distributed without permission Output “addresses” are really scripts OP_DUP OP_HASH160 69e02e18... OP_EQUALVERIFY OP_CHECKSIG This slide is copyrighted. It must NOT be distributed without permission Input “addresses” are also scripts (from the redeeming transaction) scriptSig 30440220... 0467d2c9... (from the transaction being redeemed) scriptPubKey OP_DUP OP_HASH160 69e02e18... OP_EQUALVERIFY OP_CHECKSIG This slide is copyrighted. It must NOT TO VERIFY: Concatenated script must execute completely with no errors be distributed without permission 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! This slide is copyrighted. It must NOT be distributed without permission image via Jessie St. Amand 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 This slide is copyrighted. It must NOT be distributed without permission 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 This slide is copyrighted. It must NOT be distributed without permission Bitcoin script execution example ✓ true OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG This slide is copyrighted. It must NOT be distributed without permission Bitcoin scripts in practice (as of 2014) Most nodes whitelist known scripts 99.9% are simple signature checks More on this soon ~0.01% are MULTISIG ~0.01% are Pay-to-Script-Hash Remainder are errors, proof-of-burn This slide is copyrighted. It must NOT be distributed without permission Proof-of-burn: destroy (burn) some of their own cryptocurrency tokens nothing’s going to redeem that ☹ OP_RETURN The primary purpose of Proof-of-Burn is to reduce the supply of a particular cryptocurrency. Participants send their coins to a verifiably unspendable address, essentially removing them from circulation. This act of "burning" tokens signals a commitment to the network and its goals. This slide is copyrighted. It must NOT be distributed without permission 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! Pay-to-Script-Hash This slide is copyrighted. It must NOT be distributed without permission Pay to script hash I’m ready to pay for my purchases! Big Box Great! Here’s our address: 0x3454 Pay-to-script-hash: enhance the flexibility and security of Bitcoin transactions. It was implemented to address certain limitations in the scripting language of Bitcoin transactions and to enable more complex spending conditions. This slide is copyrighted. It must NOT be distributed without permission Pay-to-Multi Signature (P2MS) OP_CHECKMULTISIG offers users the capability to lock coins with a requirement for multiple parties to sign the scriptSig before coins can be spent. Stack Script Description Empty. OP_1 OP_2 OP_3 OP_CHECKMULTISIG scriptSig and scriptPubKey are combined. 1 OP_2 OP_3 OP_CHECKMULTISIG Constants from scriptSig are added to the stack. 1 2 3 OP_CHECKMULTISIG Constants from scriptPubKey are added to the stack. true Empty. Multisignature script evaluation is performed Source: https://learnmeabitcoin.com/technical/p2ms https://wiki.bitcoinsv.io/index.php/Bitcoin_Transactions This slide is copyrighted. It must NOT be distributed without permission 38 Bitcoin blocks This slide is copyrighted. It must NOT be distributed without permission Bitcoin blocks Why bundle transactions together? Single unit of work for miners Limit length of hash-chain of blocks ØFaster to verify history This slide is copyrighted. It must NOT be distributed without permission Bitcoin block structure Hash chain of blocks prev: H( ) prev: H( ) prev: H( ) trans: H( ) trans: H( ) trans: H( ) H( ) H( ) Hash tree (Merkle tree) of transactions in each block H( ) H( ) It must NOT transaction This slide is copyrighted. transaction be distributed without permission H( ) H( ) transaction transaction The real deal: a Bitcoin block { block header transaction data } "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..." ] This slide is copyrighted. It must NOT be distributed without permission The real deal: a Bitcoin block header { mining puzzle information } "hash":"00000000000000001aad2...", "ver":2, "prev_block":"00000000000000003043...", "time":1391279636, "bits":419558700, "nonce":459459841, "mrkl_root":"89776...",... hashed during mining not hashed This slide is copyrighted. It must NOT be distributed without permission The real deal: coinbase transaction redeeming nothing arbitrary "in":[ { Null hash pointer "prev_out":{ "hash":"000000.....0000000", "n":4294967295 }, First ever coinbase parameter: "coinbase":"..." “The Times 03/Jan/2009 Chancellor on brink of second bailout for banks” }, block reward "out":[ transaction fees { "value":"25.03371419", "scriptPubKey":"OPDUP OPHASH160... ” } This slide is copyrighted. It must NOT be distributed without permission See for yourself! blockchain.info (and many other sites) This slide is copyrighted. It must NOT be distributed without permission The Bitcoin network This slide is copyrighted. It must NOT be distributed without permission 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 This slide is copyrighted. It must NOT be distributed without permission Joining the Bitcoin P2P network getaddr () 5 Hello World! I’m ready to Bitcoin! 1 8 getaddr 1, 7 getaddr () () 7 3 6 2 4 This slide is copyrighted. It must NOT be distributed without permission Transaction propagation (flooding) Already heard that! 5 1 7 A→B 8 6 A→B A→B 3 New tx! A→B A→B A→B A→B 4 A→B A→B This slide is copyrighted. It must NOT be distributed without permission 2 A→B A→B 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! Haven’t seen before ØAvoid infinite loops Doesn’t conflict with others I’ve relayed ØAvoid double-spends This slide is copyrighted. It must NOT be distributed without permission Nodes mayNewdiffer on transaction pool tx! A→C A→C 1 A→C A→C 5 A→C A→C 7 A→B 8 A→B A→B A→B 3 6 A→B A→B 2 A→B 4 A→B This slide is copyrighted. It must NOT be distributed without permission Race conditions Transactions or blocks may conflict Default behavior: accept what you hear first Network position matters Miners may implement other logic! This slide is copyrighted. It must NOT be distributed without permission 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... This slide is copyrighted. It must NOT be distributed without permission 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! This slide is copyrighted. It must NOT be distributed without permission Fully-validating nodes Permanently connected Store entire block chain Hear and forward every node/transaction Note: To balance usability and efficiency This slide is copyrighted. It must NOT be distributed without permission Ø Fully validating nodes must store the entire block chain, which as of the end of 2014 is over 26 gigabytes. 20 GB This slide is copyrighted. It must NOT be distributed without permission Lightweight nodes Ø In fact, the vast majority of nodes on the Bitcoin network are lightweight nodes. These differ from fully validating nodes in that they don’t store the entire block chain. They only store the pieces that they need to verify specific transactions that they care about. This slide is copyrighted. It must NOT be distributed without permission Storage costs (in 2014) 20 GB This slide is copyrighted. It must NOT be distributed without permission Storage costs (in 2018) 160 GB This slide is copyrighted. It must NOT be distributed without permission Source: blockchain.info Tracking the UTXO set Unspent Transaction Output ØShould be stored in memory - everything else can be stored on disk, why? 65 M This slide is copyrighted. It must NOT be distributed without permission Source: blockchain.info 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 This slide is copyrighted. It must NOT be distributed without permission Source: blockchain.info 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 block! 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) This slide is copyrighted. It must NOT be distributed without permission Limitations & Improvements This slide is copyrighted. It must NOT be distributed without permission 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 This slide is copyrighted. It must NOT be distributed without permission These affect economic balance of power too much to change now 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 This slide is copyrighted. It must NOT be distributed without permission Cryptographic limits in Bitcoin Only 1 signature algorithm (ECDSA/P256) Hard-coded hash functions Crypto primitives might break by 2040... This slide is copyrighted. It must NOT be distributed without permission Cryptographic limits in Bitcoin: Changes Hard forks and soft forks are both types of upgrades or changes to a blockchain's protocol. o A hard fork is a significant and backward-incompatible change to the protocol. It requires all nodes (participants) on the network to upgrade to the latest version of the software to continue participating in the network.Hard forks often involve changes to the consensus rules. o A soft fork is a protocol upgrade that is backward-compatible with the existing rules. Unlike a hard fork, nodes running the previous version of the software can still validate and relay blocks that follow the updated protocol. Soft forks typically involve a tightening or restriction of the existing consensus rules rather than introducing entirely new rules. This slide is copyrighted. It must NOT be distributed without permission