CSCI301 Contemporary Topics in Security Blockchain and Bitcoin PDF

CSCI301 Contemporary Topics in Security Blockchain and Bitcoin Subject Coordinator: A/Prof. Fuchun Guo School of Computing and Information Technology Bitcoins and Cryptocurrencies Technologies – A Comprehensive Introduction, Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller & Steven Gol...

CSCI301 Contemporary Topics in Security Blockchain and Bitcoin Subject Coordinator: A/Prof. Fuchun Guo School of Computing and Information Technology Bitcoins and Cryptocurrencies Technologies – A Comprehensive Introduction, Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller & Steven Goldfeder, 2016, Princeton University Press. (ISBN- 9780691171692). Introduction of Blockchain Ø Blockchain history Ø How blockchain works? Ø What can we do with it? BitCoin CryptoCurrency BlockChain Now Introduction of Blockchain Ø Blockchain history Ø How blockchain works? Ø What can we do with it? What is Blockchain? Blockchain is a network of a decentralized database that is spread across multiple entities that are kept in sync, where there is no single owner or controller of data (centralized). This database permits transactions to be gathered and recorded (by anyone with some conditions) cryptographically chains blocks (contents of database) in chronological (time) order and allows the resulting ledger (history of changes) to be accessed by different servers. 6 The Blockchain works fundamentally different (Two key differences as follows) Transactions Security Money is sent directly between two parties The Blockchain records who owns what, and when Ø A blockchain public ledger keeps a shared record of all the transactions distributed over a vast network of users (P2P). Ø It is truly decentralized and doesn’t require any intermediate system for the exchange of services. Ø Everyone can participate Anyone can see where a transaction is sent to and where it came from Every X minutes, they are permanently recorded in a new block in the blockchain The Blockchain works fundamentally different Transactions Security Introduction of Blockchain Ø Why does the Blockchain exist? Ø How blockchain works? Ø What can we do with it? （applications） What is Blockchain being Used For? Application: Blockchain in Supply Chain By utilizing a distributed ledger, companies within a supply chain gain transparency into shipment tracking, deliveries, and progress among other suppliers where no inherent trust exists. Application: Blockchain in Government Blockchain offers promise as a technology to store personal identity information, criminal backgrounds, and “e-citizenship,” authorized by biometrics. Application: Blockchain in Energy Decentralized energy transfer and distribution are possible via microtransactions of data sent to blockchain, validated, and re-dispersed to the grid while securing payment to the submitter. Application: Blockchain in Healthcare Electronic medical records stored in a blockchain, accessed and updated via biometrics, allow for the democratization of patient data and alleviate (decrease) the burden of transferring records among providers. From Blockchain To CryptoCurrencies: Before that – What are Currencies? According to Merriam-Webster dictionary: Mediums for Trade Traditional Financial Systems Cash or currency or money (Fiat money, Commodity money) Credit Mediums for Online Trade Cash Credit Ecash FirstVirtual Cyberbucks SET MagicMoney Bitcoins Altcoins Key Question: Does it need a centralized trusted third This course party when A transfers money to another entity B? Some Requirements for online cash ***** Protection against double-spending Anonymity (for both spender and recipient) Should work in an offline fashion Free-floating that acquires real value Preferably, decentralized Bootstrapping an online cash (currency) that satisfies some or all of these requirements will require a clever combination of well-known cryptographic primitives and computing paradigms! Thus the name, Crypto + Currencies From CryptoCurrencies TO Bitcoin Ø What is bitcoin ? Ø Where did bitcoin come from ? Ø Bitcoin Components Ø Mechanics of Bitcoin Bitcoin Ø What is bitcoin ? Ø Where did bitcoin come from? Ø Bitcoin Components Ø Mechanics of Bitcoin What is bitcoin? Bitcoin is not a physical coin Bitcoin is digital/crypto currency Banking Controlled by a central authority Controlled by the network “Standard” fees apply Lower fees Prone to fraud Higher security Bitcoin Ø What is bitcoin ? Ø Where did bitcoin come from? Ø Bitcoin Components Ø Mechanics of Bitcoin Digital currencies before bitcoin (2008) Digicash (1990): anonymous Hashcash (1997): proof-of-work B-Money (1998) : decentralized, proof-of-work BitGold (1998): a precursor to Bitcoin (polished version) 2008 BITCOIN WHITE PAPER Satoshi Nakamoto released a Bitcoin white paper in 2008. The 8 page paper announced the vision for a decentralized digital currency 2009 In January 2009, the bitcoin network came into existence with the release of the first open source bitcoin client and the issuance of the first bitcoins, with Satoshi Nakamoto mining the first block of bitcoins ever (known as the genesis block), which had a reward of 50 bitcoins. 2010 The First Bitcoin Transaction The First Bitcoin Transaction On May 22nd 2010, Laszlo Hanyecz paid 10,000 BTC ($40) for two Papa John’s pizzas. December 2013 Mt. Gox - a bitcoin exchange based in Tokyo, Japan. Was handling over 70% of all bitcoin transactions worldwide, as the world's leading bitcoin exchange … Bitcoin Ø What is bitcoin ? Ø Where did bitcoin come from? Ø Bitcoin Components Ø Mechanics of Bitcoin Centralization vs. decentralization Centralization vs. decentralization Competing paradigms that lie on many digital technologies Centralized: Online Social Networking Services (Facebook, Google) Decentralized: Internet, Email service and the SMTP protocol Decentralization is not all-or-nothing: For example, E-mail. Email has a decentralized protocol (e.g., SMTP), but dominated by centralized webmail services Centralized System Trusted Arbiter (Centralized Authority) All users in a system believe that a single trusted arbiter. Trusted arbiter defines the current state and records initial state and the sequence of changes. We can easily find the system having a trusted arbiter: Banking system Bank provides the official sequence of transactions and account balances. When you want to spend your money, send a message to the bank. Bank executes the transaction request if you have money, and updates account balances. 40 Centralized System Client-server network Data is stored on servers, clients can access the data wherever they log-in. Clients trust that the data is securely stored. For example, the website is held on the server, and users are the clients. Client-server network is very efficient, and a traditional model in computing. 41 Problems of Centralized system Single point of failure A failure in a centralized authority is a failure in the entire system. Simply, any transaction in a banking system is unavailable when the system goes down. Concentration of power A centralized authority easily can manipulate the current state by modifying the past state. For example, in a voting system, a centralized authority can manipulate for the outcome of votes. 42 Decentralized System Decentralisation is the process by which the activities of an organization, particularly those regarding planning and decision making, are distributed or delegated away from a central, authoritative location or group. Decentralized computing is the allocation of resources, both hardware and software, to each individual workstation. Peer-to-peer File sharing applications 43 Decentralized System Peer-to-peer network Each peer has 100% of the data (or as close to it as possible) Updates are shared around. Data are replicated many times BitTorrent network where files are shared between users, works without a central server controlling the data. 44 Decentralized System： example BitTorrent 45 Decentralized System Peer-to-peer is in some ways less efficient than client-server due to the data replication and a noisy gossip. Each peer in a peer-to-peer network is more independent, it can continue operating to some extent even if it loses connectivity to the rest of the network. Peer-to-peer networks are more robust, there is no central server that can be controlled, so closing down peer-to-peer networks is harder like BitTorrent. 46 The problems of agreement With peer-to-peer models, even if all peers are ‘trusted’, there can be a problem of agreement or consensus. If each peer is updating at different speeds and have slightly different states, how do you determine the “real” or “true” state of the data? There’s no trusted arbiter to decide who is right! In an ‘untrusted’ peer-to-peer network where you can’t necessarily trust any of peers, how do you ensure that the system can’t easily be corrupted by bad peers? It was considered not to be suitable for a system requiring a high-level of trust such as a money transfer. 47 What is Blockchain in detail? In Blockchain, all users get a functionality of a trusted arbiter without having a real one. A Blockchain system requires a decentralized system Entities in Blockchain do not believe each other or a single entity. But, they want to agree the history of changes. èThat makes participants in the system agree the current state of the system. èThey will do some thing meaningful… (cryptocurrency, smart contracts, etc …) 48 Simple example: playing chess online What is necessary for Alice and Bob? Ø Agree on the initial state: Both knows the starting position of the board. Ø Agree on changing states: Both know the sequence of messages so far. Those messages make up a transcript of the game. Thus, they can reconstruct the state of the board. B1: Move 5th Pawn to E6 A1: Move 4th Pawn to D4 … A50: Checkmate! 49 Simple example: playing chess online If Alice and Bob don’t agree on the state of board, they can’t play a game! Suppose Alice wants to move bishop to f8 on chess board. Bob needs to know whether Alice’s bishop is in the valid location for this execution.  Bob needs to know the current state of system. If Bob is looking at the past states of Alice’s ledger, Alice can trick Bob by modifying the location of the bishop she already moved to the other location in the board. Can they agree on the current state of the system with some distributed system?  Blockchain! 50 Simple example: playing chess online If Alice and Bob agree on history, they agree on the present state! They all agree on the initial state of the game. Blockchain contains a history of individual transactions Starting (Initial) state + history = current state A blockchain is the technology letting Bob and Alice agree on the state of the system, even if they do not believe each other! 51 In Blockchain The purpose of Blockchain for the transaction between Alice and Bob： They agree the state of their transaction system such as How much BTC (Bitcoins) in each account? Who owns which accounts? What is the current states of the system? Moreover, we don’t want a single trusted arbiter of the state of the world. We want some level of decentralization—not a single point of failure, compromise or control. 52 How does blockchain work? A block is a sequence of hash-chained records. Once a new record is hashed and chained, the past records cannot be modified. A cryptographic Hash-function satisfies the following properties: Message Digest: Cryptographic Hash Functions are used to guarantee the integrity of data. It takes the arbitrary length inputs and outputs a fixed length value. Preimage Resistant: Given v such that Hash(d) = v, finding value of d is infeasible. Collision Resistant: It is infeasible to find the two distinct d and d’ such that Hash(d) = Hash(d’) 53 Aspects of decentralization in Bitcoin 1. 2. 3. 4. 5. Our focus in this chapter Who maintains the ledger? Who has authority over which transactions are valid? Who creates new bitcoins? Who determines how the rules of the system change? How do bitcoins acquire exchange value? Beyond the protocol: Exchanges, Wallet software, Service providers... Distributed Consensus o Distributed consensus is a fundamental concept in blockchain technology, ensuring that all nodes in the network agree on the state of the ledger Bitcoin’s key challenge Key technical challenge of decentralized e-cash: distributed consensus o o o Transactions are valid? The new block is valid? Where is the coin from? Defining distributed consensus There are “n” nodes, each have an input value. Some nodes are faulty or malicious. A distributed consensus protocol has the following two properties: 1. The protocol terminates and all honest nodes are in agreement on the same value 2. This value must have been proposed by some honest node. What does this mean in the context of Bitcoins? Bitcoin is a peer-to-peer system When Alice wants to pay Bob: she broadcasts the transaction to all Bitcoin nodes signed by Alice Pay to pkBob : H( ) Note: Bob’s computer may not be in the picture or online! In fact, running a Bitcoin node is not important for Bob to receive the funds. The Bitcoins will be his regardless What nodes need to reach a consensus on? Which transactions were broadcast on the network Order in which these transactions occurred How consensus could work in Bitcoin At any given time (in the bitcoin peer-to-peer network): All nodes have a sequence of blocks of transactions (called, ledger or block chain) they’ve reached consensus on Each node has a set of outstanding transactions it’s heard about (but not yet included in the block chain, to be added) For these transactions consensus has not yet happened Each node may have a slightly different outstanding transaction pool How consensus could work in Bitcoin Tx Tx … Tx Tx Tx … Tx Tx Tx … Tx Tx Tx … Tx Consensus protocol Tx Tx … Tx Tx Tx … Tx OK to select any valid block, even if proposed by only one node Why consensus is hard (esp. in the Bitcoin context)? Nodes may crash Nodes may be malicious Peer-to-peer network is imperfect (problems) Not all pairs of nodes connected (and may participate) Faults in network ( 51% ?) Latency No notion of global time  Limit the set of consensus algorithms that can be used Consensus Algorithm (How to prepare for the next block) 1. 2. 3. 4. 5. New transactions are broadcast to all nodes The success node (via pow) collects new transactions into a (new) block, to be added after the longest chain. In each round, the success node gets to broadcast its block Other nodes accept the block only if all transactions in it are valid (unspent, valid signatures) Nodes express their acceptance of the block by including its hash in the next block they create Now let’s analyze if this works! Assume a malicious adversary. Can this adversary subvert the implicit consensus process by: 1. Stealing Bitcoins? 2. Double spend? What can a malicious node do? CA → B signed by A Pay to pkA’ : H( ) signed by A Pay to pkB : H( ) Doublespending attack CA → A’ Honest nodes will extend the longest valid branch In practice nodes extend the block that they first detect on the peer-to-peer network (not a solid rule) From Bob the merchant’s point of view 1 confirmation 3 confirmations CA → B CA → A’ double-spend attempt Hear about CA → B transaction 0 confirmations Double-spend probability decreases exponentially with # of confirmations Most common heuristic: 6 confirmations Recap Protection against invalid transactions is cryptographic, but enforced by consensus Protection against double-spending is purely by consensus You’re never 100% sure a transaction is in consensus branch. Guarantee is probabilistic Key Consensus: Incentives and proof of work： The reason why we perform honestly: receiving coins (bonus) Assumption of honesty is problematic Can we give nodes incentives for behaving honestly? Can we reward nodes that created these blocks? Can we penalize the node that created this block? Everything so far is just a distributed consensus protocol But now we utilize the fact that the currency has value Incentive 1: Block Reward Creator of block gets to include special coin-creation transaction in the block choose recipient address of this transaction Value is fixed: currently 12.5 BTC, halves every 210,000 blocks created (or every 4 years at the current rate of block creation) We are now in the third period – first period block reward was 50 BTC Block creator gets to “collect” the reward only if the block ends up on long-term consensus branch! Subtle but powerful trick: Incentivizes nodes to behave in way that will get other nodes to extend their block There’s a finite supply of bitcoins Total bitcoins in circulation Total supply: 21 million Block reward is how new bitcoins are created First inflection point: reward halved from 50BTC to 25BTC Year Runs out in 2040. No new bitcoins unless rules change Does that mean that after 2040, nodes will no longer have incentive to behave honestly? Not really! Incentive 2: Transaction Fees Creator of transaction can choose to make output value less than input value Remainder is a transaction fee and goes to block creator (that first puts that transaction into that block) Purely voluntary, like a tip But system will evolve, and will become mandatory, as Block rewards run out Remaining problems 1. How to pick a random (succ) node (to add the blockk)? 2. How to avoid a free-for-all due to rewards? Everybody may want to run a bitcoin node in order to get this free reward (lock reward and Transaction fee) 3. How to prevent Sybil attacks? An adversary may create a large number of fake nodes to subvert the consensus process Proof of work To approximate selecting a random node: select nodes in proportion to a resource that no one can monopolize (we hope) In proportion to computing power: proof-of-work (Used in Bitcoins) In proportion to ownership of the currency: proofof-stake (Not used in Bitcoins – but a legitimate model used in other cryptocurrencies) Equivalent views of proof of work 1. Select nodes in proportion to computing power 2. Let nodes compete for right to create block 3. Make it moderately hard to create new identities (because cannot forge computing power) Hash puzzles To create block, find nonce s.t. H(nonce ‖ prev_hash ‖ tx ‖ … ‖ tx) is very small nonce prev_h Tx Tx In other words, H(nonce ‖ prev_hash ‖ tx ‖ … ‖ tx) < target Output space of hash Target space If hash function is secure (satisfies puzzle-friendliness): only way to succeed is to try enough & different nonces until you get lucky Advantage of such a PoW system? It completely does away with the problem of magically picking a random node (to propose a block) Nodes independently compete by attempting to solve hash puzzles Once in a while, one will succeed and propose the next block Result: Such a system is completely decentralized  No one gets to decide which node proposes the next block PoW property 1: difficult to compute Difficulty varies with time As of 2015: difficulty level is over 1020 hashes/block i.e., size of target space mining cost (hardware + electricity cost) → Profit Complications: Fixed (hardware) vs. variable (electricity) costs Reward depends on rate at which miners propose blocks (ratio of their hash rate to the global hash rate) Cost in dollars, but reward in BTC  profit depends on exchange rate Solving more than 1020 hashes to obtain 12.5 BTC at current exchange rate is profitable! Summary Top 4 Consensus 1/2: Node Consensus: All nodes in the Bitcoin network must agree on the validity of transactions and blocks. Each node independently verifies incoming transactions, ensuring they adhere to the rules defined by the Bitcoin protocol. The success node decides the transactions in the next block. Longest Chain Rule:Bitcoin follows the principle of the longest chain rule. In the case of competing valid chains, nodes in the network accept the longest valid chain as the true version of the blockchain. This is a key element in resolving conflicts and achieving consensus on the transaction history. Top 4 Consensus 2/2: Proof of Work (PoW): Bitcoin's consensus mechanism relies on proof-of-work. Miners compete to solve complex mathematical puzzles, and the first one to solve it gets the opportunity to add a new block to the blockchain. This process requires significant computational power and serves as a mechanism to secure the network against attacks. Difficulty Adjustment: The Bitcoin network adjusts the difficulty of the proof-of-work puzzles approximately every two weeks to ensure that blocks are added to the blockchain roughly every 10 minutes. This adjustment is crucial for maintaining a consistent block generation rate, even in the face of fluctuations in the total computational power of the network. Summary: Decentralized consensus is hard because nodes in P2P could be malicious. Bitcoins use “bonus (new coins)+tx fee” mechanism for honest nodes. Adding the new block on the longest chain with “proof of work”. The previous miner (block generator) decides the next transactions in the next block. It requires that 51% validating (computational) power is honest. What can a “51% attacker” do? Steal coins from existing address? ✗ Suppress some transactions? From the block chain From the P2P network ✓ ✗ Change the block reward? ✗ Destroy confidence in Bitcoin? ✓✓ （double spending） END