CS计算机代考程序代写 data structure chain Excel Blockchains

Blockchains
CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Based on material provided by Mark Stamp
Ryszard Janicki
Blockchains 1/38

Digital Currency
We want create an all-digital currency Like $, or 􏱁, or £, or …., but “better”
Real cash is (relatively) anonymous So digital currency should be too
Digital currency is “better” since. . .
No central authority (i.e., banks)
No government to issue currency, etc.
Ryszard Janicki
Blockchains 2/38

Preliminaries: Work
How to measure (digital) work ? Our unit of work will be 1 hash
Suppose that we have a hash function h(x) that generates an N-bit output
Then randomly chosen input generates one of 2N equally likely outputs
For any input R, have, 0 ≤ h(R) ≤ 2N Different R yield uncorrelated hashes
Ryszard Janicki
Blockchains 3/38

Hashing and Work
Suppose we have a 16-bit hash function
For any R, we have 0 ≤ h(R) < 65,536 If we want R so that h(R) < 64 = 000000000010000, then how many R values do we need to hash? Since h(R) = y = (y15y14y13y12y11y10y9y8y7y6y5y4y3y2y1y0) we want output like (10 leading 0s). . . h(R) = y = (0000000000y5y4y3y2y1y0) For 16-bit hash, how many hashes until h(R) = y = (0000000000y5y4y3y2y1y0)? For random R, we have a 1/2 chance that y = (0y14y13y12y11y10y9y8y7y6y5y4y3y2y1y0) And 1/4 chance that y = (00y13y12y11y10y9y8y7y6y5y4y3y2y1y0) And 1/8 chance that y = (000y12y11y10y9y8y7y6y5y4y3y2y1y0) And so on... Ryszard Janicki Blockchains 4/38 Work and Hashing For 16-bit hash, if someone gives us an R such that h(R) < 64 = 000000000010000 Then expected number of hashes computed is 210 = 1024 (“expected” means average case) That is, they have done 1024 units of work We use hashing to show work was done We can adjust parameter so more work (or less) is required For N-bit hash, if we require h(R) < 2n then expected work is 2N−n hashes Note: We can easily verify that the expected amount of work was done Only requires a single hash No matter how much work to find R Ryszard Janicki Blockchains 5/38 Preliminaries: Ledgers Ledger is a book of financial accounts Suppose Alice, Bob, Charlie, Trudy play weekly poker game online They all insert ledger entries such as, “Bob owes Alice $10”, “Charlie owes Trudy $30”, “Trudy owes Alice $25”, and so on Once a month, they meet and settle up Any possible problems here? Ryszard Janicki Blockchains 6/38 Signed Ledger Entries How to prevent Trudy from inserting, say, “Bob owes Trudy $1M” ? Let’s require digital signatures For ledger entry to be valid, Bob must sign “Bob owes Alice $10”, Trudy must sign “Trudy owes Alice $25”, and so on . . . Then we know ledger entries are valid That is, the payer agrees to pay Public Key Notation Sign message M with Alice’s private key: [M]Alice Encrypt message M with Alice’s public key: {M}Alice Ledger now looks like [Bob owes Alice $10]Bob [Charlie owes Trudy $30]Charlie [Trudy owes Alice $25]Trudy and so on ... And we know ledger entries are valid But, still some problems here. . . Ryszard Janicki Blockchains 7/38 Signed Ledger in Detail Ledger now looks like [Bob owes Alice $10]Bob [Charlie owes Trudy $30]Charlie [Trudy owes Alice $25]Trudy and so on ... As an aside, note that signatures above really look like (M1,[h(M1)]Bob), where M1 = “Bob owes Alice $10” (M2, [h(M2)]Charlie ), M2 = “Charlie owes Trudy $30” (M3, [h(M3)]Trudy ), M3 = “Trudy owes Alice $25” And so on ... We’ll use the shorthand from the beginning of this slide Ryszard Janicki Blockchains 8/38 Ledger Duplication and Unique Ledger Entries Still, nothing to prevent Trudy from duplicatinga line. . . [Bob owes Alice $10]Bob [Charlie owes Trudy $30]Charlie [Trudy owes Alice $25]Trudy [Charlie owes Trudy $30]Charlie Signatures are still all valid How to prevent this attack? Include unique transaction numbers [1, Bob owes Alice $10]Bob [2, Charlie owes Trudy $30]Charlie [3, Trudy owes Alice $25]Trudy and so on ... Why does this help? We will never have an exact duplicate So any duplicate is invalid Ryszard Janicki Blockchains 9/38 Ledger Prepayment I How to be sure participants pay up? Can start with Alice, Bob, Charlie, and Trudy all putting money into the pot And don’t allow any transaction that would result in negative balance Transaction must still be signed and . . . . . . now, nobody can “overdraw” account Ledger example. . . Alice has $100 // Alice’s initial stake Bob has $100 // Bob’s initial stake Charlie has $100 // Charlie’s initial stake Trudy has $100 // Trudy’s initial stake [1, Bob owes Alice $10]Bob // valid [2, Charlie owes Trudy $30]Charlie // valid [3, Trudy owes Alice $25]Trudy // valid [3, Trudy owes Bob $120]Trudy // invalid Ryszard Janicki Blockchains 10/38 Ledger Prepayment II Ledger example. . . Alice has $100 // Alice’s initial stake Bob has $100 // Bob’s initial stake Charlie has $100 // Charlie’s initial stake Trudy has $100 // Trudy’s initial stake [1, Bob owes Alice $10]Bob // valid [2, Charlie owes Trudy $30]Charlie // valid [3, Trudy owes Alice $25]Trudy // valid [3, Trudy owes Bob $120]Trudy // invalid Note that we must know the entire transaction history So that we can know current balances Then we can be sure a given transaction does not cause user to be overdrawn This seems like kind of a hassle, but some big benefits come from it Ryszard Janicki Blockchains 11/38 Eternal Ledger? Alice, Bob, Charlie, and Trudy could continue to settle accounts each month But, as the ledger currently stands, settling accounts is not necessary! We know the current balances, and no risk of anyone being “overdrawn” So, could play poker for months, years, or forever, without settling accounts Ryszard Janicki Blockchains 12/38 Ledger as Currency This ledger can act as its own currency! We need a symbol, let’s use “§” Transactions within ledger are all in terms of § currency protocol Anyone can exchanged ledger currency (i.e., §) for $, or £, or 􏱁, or ... But, such exchanges occur outside the ledger currency protocol Ryszard Janicki Blockchains 13/38 Ledger Currency For example, Alice could pay Bob $10 in real world dollars for, say, §5 of currency in the ledger system Comparable to exchanging, say, CAN$ for £ But, ledger is a history of transactions within the ledger currency system In fact, the ledger is the currency This is the key insight for cryptocurrency Ryszard Janicki Blockchains 14/38 Distributed Ledger I The ledger is the currency So who is in charge of the ledger? A government? The UN? A bank? An individual? We don’t trust them, so let’s make everybody in charge of the ledger Anybody can have copy of ledger, anyone can add entries (there is a protocol. . . ) Protocol without a central authority What problem(s) do you foresee? Ryszard Janicki Blockchains 15/38 Distributed Ledger II 1 Transactions must be signed 2 Nobody can be overdrawn 3 Transactions broadcast to everybody How to have a consistent view of this distributed ledger? Multiple ledgers exist at any time This is the heart of the issue for a distributed cryptocurrency (e.g. Bitcoin) Ryszard Janicki Blockchains 16/38 Distributed Ledger and Work Every ledger will have some amount of work associated with it And, ledger with most work “wins” That is, everyone accepts ledger that has the most work put into it Recall, work is measured in hashes So, more hashes is “more better” Ryszard Janicki Blockchains 17/38 Blocks and Hashes Each transaction is signed Transactions grouped into blocks Let B be one such block Find (nonce) R so that h(B, R) < 2n Just fancy way of saying h(B,R) starts with a specified number of 0s Work required to find R? On average 2N−n hashes for N-bit hash Ryszard Janicki Blockchains 18/38 Chain We don’t want to revalidate each block, want to order blocks, and so on We’ll chain blocks together Put hash of previous block in header of current block before computing hash So, must find a nonce R so that h(Y,B,R) < 2n Where Y is hash of previous block Ryszard Janicki Blockchains 19/38 Blockchain We now have Yi+1 = h(Yi,Bi,Ri) < 2n Yi+2 = h(Yi+1, Bi+1, Ri+1) < 2n Yi+3 = h(Yi+2, Bi+2, Ri+2) < 2n Each B is a block Block is a group of signed transactions Each nonce R is chosen so inequality holds Much work to find R, easy to verify Yj < 2n Ryszard Janicki Blockchains 20/38 Mining? Anyone can create a new block But lots of work to find a valid hash So what is the incentive to do work? “Free” money! Get (new) money for doing work, say, § 1 Put this info at start of block, does not need to be signed (since new money) Ryszard Janicki Blockchains 21/38 One Block One Block lock B looks like... iBlockBi lookslike... chain Ryszard Janicki Blockchains 22/38 B k Mining I Free money, so miners are in a race to find hashes that yield valid blocks The more computing power a miner has, the better chance to win race Once a valid hash is found, miner sends the block out to everybody Again, easy to verify hash is correct Ryszard Janicki Blockchains 23/38 Blockchain Blockchain Blockchain looks like... Blockchainlooks like. . . Blockchain Ryszard Janicki Blockchains 24/38 Mining II Why is “mining” called mining ? Really, just finding a valid block hash Miner is doing work, and creating new money that did not previously exist In a sense, this is comparable to mining gold or silver (for example) This may be the most misunderstood part of cryptocurrency protocols Ryszard Janicki Blockchains 25/38 Non-Miners Users do not have to be miners Non-miner just wants blockchain Needed to know how many §s others have Also, non-miner sends out transactions for others to make blocks (and mine) User might see conflicting blockchains What to do in such cases??? More work is “more better”! Ryszard Janicki Blockchains 26/38 More Work If conflicting blockchains, how to know which represents more work? Each block is a fixed amount of work In terms of expected number of hashes So, longer block chain is more work Thus, longer block chain always wins If it’s a tie, wait until one is longer Ryszard Janicki Blockchains 27/38 Summary of Protocol 1 New transactions broadcast 2 Miners collect transactions into blocks 3 Miners race to find valid block hash 4 When miner finds hash, broadcast it 5 Block accepted if all transactions signed, no overdraft, and block hash valid 6 New block extends blockchain Miners use hash of new block in next block Ryszard Janicki Blockchains 28/38 Attack Scenario Suppose Trudy makes a block B that includes transaction [Trudy pays Alice §100]Trudy Trudy sends B to Alice only, nobody else Question: Why would Trudy do this? Answer: So she can spend that §100 again Trudy likes double spending! It’s free money! Ryszard Janicki Blockchains 29/38 Double Spending For Trudy’s double spending attack to work, she must compute valid hash. That is, find R, so that h(Y,B,R) < 2n And send chain with block B to Alice But, nobody else knows about B, or the chain that contains it All other miners working on other chains Those other chains can (and will) grow Trudy is in ongoing race with all miners Ryszard Janicki Blockchains 30/38 Double Spending Attack Alice will reject Trudy’s chain once a longer chain appears Trudy would need most of computing power in the network to win Trudy needs to win a lot! Or, miners collude with Trudy But is it in their interest to do so? Ryszard Janicki Blockchains 31/38 Blockchain From users perspective. . . Transaction in last block might not be entirely trustworthy Possibility of double spending attack But, the more blocks that follow, the more certain that a transaction is valid Just wait until a few more blocks are added before accepting a transaction Ryszard Janicki Blockchains 32/38 Refinements I Number of hashes can change so that winning hash takes constant time Computing power in network can increase In Bitcoin, new block every 10 minutes Can decrease mining reward so money supply does not grow forever E.g., maximum of 21,000,000 bitcoins Then what will be incentive for miners? Ryszard Janicki Blockchains 33/38 Merkle Tree A hash tree or Merkle tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures. Hash trees are a generalization of hash lists and hash chains. Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes of the tree This contrasts with hash lists, where the number is proportional to the number of leaf nodes itself. Ryszard Janicki Blockchains 34/38 Merkle Tree Example An example of a binary hash tree. Hashes 0-0 and 0-1 are the hash values of data blocks L1 and L2, respectively, and hash 0 is the hash of the concatenation About this interface | Discussion | Help of hashes 0-0 and 0-1. Ryszard Janicki Blockchains 35/38 Refinements II Merkle tree can be used to reduce storage requirements Transactions in a block hashed in a tree, only the root is needed in block hash Simplified payment verification In effect, rely on others to verify for you Combining and splitting value Transaction can have multiple input/output Ryszard Janicki Blockchains 36/38 Privacy? Can use pseudonym in public key But, can still connect transactions to a specific public key Might be able to tie public key to an individual based on transactions We’ll see examples like this later. . . Not a strong form of anonymity Bitcoinis said to be “pseudonymous” Ryszard Janicki Blockchains 37/38 Future of Blockchains? Blockchaincan be viewed as a way to implement a distributed ledger Useful for cryptocurrency, but many other possible applications too Blockchain are said to be a “foundational” and/or “disruptive” technology Controversial , but probably neither... See an excellent video about bockchains: https://www.youtube.com/watch?v=bBC-nXj3Ng4 Read a paper about ’bitcoins’ that on the course website Ryszard Janicki Blockchains 38/38