Cryptocurrencies ================ What problem is Bitcoin trying to solve? 1. Electronic payments Several options already exist: credit cards, ACH, Swift, ... 1b. "Smart" contracts 2. Decentralized transaction execution No servers/authorities in special roles Existing systems all involve some special entity: Credit cards (MC/Visa/Amex/..), ACH (banks / Fed reserve), .. 3. Decentralized currency No government in charge of currency (e.g., US Govt in charge of USD) What are the possible motivations for decentralization? 1. Interesting goal from a security perspective Centralized entities are trusted with some task If we can avoid them, seemingly better for security No potential compromises of these central entities 2. Avoid government control of monetary policy e.g., Venezuela, Zimbabwe have high inflation rates Government prints large amounts of new currency Currency users don't have as much trust in value of currency 3. Perhaps lower transaction fees e.g., credit card networks charge ~1% fees 4. Avoid censorship for transactions e.g., Paypal might block donations to Wikileaks 5. Avoid regulation Cross-border transactions Currency conversion Currency controls 6. Anonymity? Interestingly, 3-6 seem orthogonal of decentralization Could likely design a semi-centralized system that achieves them Strawman cryptocurrency design: Bank issues coins: Sig_bank(this coin, #52, belongs to PK_Alice) Alice can give this coin to Bob, like a signed check: Sig_Alice(this coin, #52, belongs to PK_Bob) Perhaps two signed messages mean the coin is owned by Bob Challenge: double-spending Alice can give the same coin to chuck: Sig_Alice(this coin, #52, belongs to PK_chuck) Similar to writing many checks beyond what's in your account Easy solution: deposit the check in the bank To cash Alice's check, Bob needs to send the check to the bank Bank must check that Alice still has enough money, issue new coin to Bob Centralized: bank involved in all transactions! Potential source of various problems mentioned above: high transaction fees, censorship, regulation, non-anonymity, .. Decentralization is tricky Sketch 1: broadcast transactions to everyone? Might still get two conflicting transactions, no agreement Possible network partitions Sketch 2: vote on what transactions are valid? e.g., users vote which transaction came first Significant research on Byzantine Fault Tolerance (BFT) protocols Who determines the "voters"? Decentralized system: no admission control Adversary can create many fake identities, join the system, vote both ways Bitcoin's approach: "proof-of-work" ledger Keep a list of all transactions Blocks contain some number of transactions Each block points to previous block (via cryptographic hash) Could have branches ("forks") going forward .. but on a given fork, no question about which transaction went first Block contents, simplified: H(prev), H(txns), timestamp, nonce Require significant computational effort to produce a valid block SHA256(block) must be below target value For random inputs, SHA256 is approximately a random 256-bit value Target value could be, say, 2^224 (~ initial target value in Bitcoin) Need to try 2^32 inputs on average to get a hash below 2^224 Bitcoin block contains special space ("nonce") for generating diff hashes (Valid block must contain only valid transactions) Producer of valid block gets incentives Block reward: currently 12.5 BTC Transaction fees: payment by users whose transactions appear in block Block reward is the sole source of money in Bitcoin Prefer longest chain of blocks Possible to get multiple forks Fork with larger number of blocks "wins" Incentivizes agreement on longest fork Peer-to-peer network that distributes blocks "Mining" Need significant computational power to produce a block Originally Bitcoin just computed hashes on CPUs .. then moved to GPUs .. now using specialized chips just for Bitcoin mining Mining cost dominated by electricity for powering the chips Mining strategies Why is it significant that no entity has over 50% of mining power? Can produce a longer chain from any prefix Little incentive to reveal new blocks: would win later anyway What attack does this allow? Adversary (with 50% mining power) can double-spend "Selfish mining" or "Temporary block withholding" With over 33% mining power, makes sense to wait to broadcast block (Why?) Mining pools Average out the expected reward from mining "Near-blocks" allow some confirmation of effort from participants What happens if blocks are mined every 30 seconds instead of 10 minutes? Lots of forks, takes a long time to resolve Where does 10 minutes come from? Blocks have timestamps in them Some heuristics to determine if the timestamps are plausible or not Every 2016 blocks, nodes re-adjust target value based on these timestamps How to deal with forks from an end-user perspective? Bitcoin folklore: wait for 6 blocks No formal analysis of what this guarantees Transactions Wiring: inputs, outputs All transactions must have inputs (except block rewards: "coinbase") Outputs determine where the money goes Any amount leftover is the transaction fee, goes to block miner Scripting language Used to authenticate wiring between transaction inputs and outputs Specialized, somewhat restrictive language, based on a stack machine Transaction has a script fragment for every input and every output To determine if input/output wiring is OK: First run the "input" script (of dst txn, called scriptSig) Then run the "output" script (of src txn, called scriptPubKey) Opcodes allow computing hashes, checking signatures, hard-coding values Common example: "Pay-to-PubkeyHash" Output script: require the "consuming" txn to be signed by specific pubkey Input script: constant value for a signature by that pubkey Can use this to implement more complex "smart contracts" Simple use case: require multiple signatures More clever use case: payment channels ("Lightning network") Set up a "payment channel" between two users that have frequent transactions Perhaps one useful analogy: buying a store gift card Payment channel holds some buffer of money Two users can spend money in this channel (shuffle between themselves) without involving the Bitcoin ledger Once they're done (e.g., run out of money in either direction), can settle the payment channel by issuing a real Bitcoin transaction Lots of tricky details to deal with revocation / rollback: https://lightning.network/lightning-network-paper.pdf Node storage Nodes store list of blocks, and the transactions from each block Nothing else needs to be stored: no balances, no accounts, no keys, ... Need to find a transaction based on its hash (if new txn spends it) "Altcoins" Bitcoin had crucial idea of using proof-of-work for decentralized consensus Many cryptocurrencies developed since Bitcoin e.g., Ethereum (more sophisticated scripting), Zcash (anonymity), .. Challenge: how to get people to value a new currency? (Pretty unclear.) Challenge: how to gain significant mining power? Neat trick: "merged mining" E.g., add the "alt-coin" state (e.g., hash of block) inside of a Bitcoin txn Non-currency altcoins Namecoin: mapping user names to public keys Traditionally hard problem: requires centralized CAs Decentralized plan: blockchain contains registered names Need to pay to register a name Need to pay to renew a name (every 200-250 days) Because of proof-of-work, need a currency aspect to make incentives work.. Anonymity / Pseudonymity Graph of transactions: lots of publicly available data Network adversary could observe who submits txn, so may want to use Tor Creating separate keys for each transaction to avoid linking Connects to real identities when entering/exiting via exchanges (e.g., to USD) Other designs (e.g., Zcash) have stronger anonymity support Bitcoin clients Challenge: many transactions to download, store, and continuously process SPV: Simplified Payment Verification Just keep track of longest chain of block headers (not txns themselves) Assume miners check the transaction validity Can check proofs that a transaction is in blockchain e.g., download transactions for specific block (or use Merkle tree) Challenge: securely generate and store keys Possibly many keys, if using separate keys for each transaction (Otherwise, one key used for many txns, no pseudonymity at all)