比特币和区块链

1 .Bitcoin and Blockchains Hakim Weatherspoon [ slide liberally taken from Kevin Seqniqi , Ittay Eyal, Emin Gun Sirer, Robbert van Renesse] CS6410 1

2 .A Brave New World - The Vision of David Chaum David Chaum PhD CS/Business Adm from Berkeley 1982 Founded International Association for Cryptologic Research (IACR) same year K nown for eCash , mix nets, voting systems…

3 .A Brave New World - The Vision of David Chaum [1983] http://www.hit.bme.hu/~buttyan/courses/BMEVIHIM219/2009/Chaum.BlindSigForPayment.1982.PDF

4 .A Brave New World - The Vision of David Chaum [1983]

5 .Basically ... Electronic payment systems suffer from loss of privacy and cumbersome trust on single entities. Privacy protection, however, encounters issues of security and safety of data. A Brave New World - The Vision of David Chaum [1983]

6 .Nick Szabo [1998]

7 .Nick Szabo [1998]

8 .Nick Szabo [1998] http://unenumerated.blogspot.com/2005/12/bit-gold.html

9 .Satoshi Nakamoto and the Anon Post [2008]

10 .Satoshi Nakamoto and the Anon Post [2008]

11 .Satoshi Nakamoto and the Anon Post [2008]

12 .Goals An electronic payment system: Guarantees safety of transactions, protects against double spends, gives full freedom to owners. Yet no central trusted authority, no reliance on quorum since identities are not known.

13 .A Replicated Ledger of Transactions give 10 bitcoins to Jane Ledger Judy (owns 15 bitcoin ) Joe (owns 1 bitcoin ) give 10 bitcoins to Joe give 3 bitcoins to Judy Jane

14 .Bitcoin Blockchain Permissionless , open membership Proof-of-Work There are thousands of B itcoin miners they use ASIC hardware to compute SHA256 hashes use about more energy than the country of Denmark O verall rate is a few transactions per second 14

15 .The Blockchain Ledger   HASH( ) < target nonce “ cryptopuzzle ”

16 .Cryptographic One-Way Hash Function hash(X) = Y Given X it is easy to compute Y (the digest ) Given Y it is computationally infeasible to find - unless you already know X, of course In some sense, Y identifies X Examples: MD5, SHA-256, SHA-3 Note: unlike an ordinary hash function where you typically have fewer buckets than objects and thus multiple objects per bucket, with cryptographic hash functions you typically have many more “virtual buckets” than objects, and at most one object in a bucket HASH( ) < target

17 .SHA256(SHA256(PrevHash ||Tx||Tx||…||Nonce )) < {0} k {0,1 }* Mining: Find Nonce that when hashed with block of transactions results in k leading 0’s. Block Identifier: Hash of block identifies the block Each hash identifies the entire prefix of the ledger The Blockchain : Proof-of-work / Mining HASH( ) < target nonce

18 .The Blockchain

19 .The Blockchain

20 .The Blockchain Exponentially distributed, with constant mean interval target automatically adjusted every 2016 blocks so that mean interval is 10 minutes

21 .Incentives for Mining Prize: “Minting” Transaction Fees Wins proportional to computation power

22 .Forks Two blocks “mined” at approximately the same time by two different miners

23 .Fork Resolution Longest chain wins Transactions on short chain are reverted

24 .Fork Resolution A transaction is confirmed when it is buried “deep enough” (typically 6 blocks – i.e., one hour)

25 .Security Threat!  

26 .Security Threat!   Threat: attacker outruns good miners

27 .Security Threat!   Threat: attacker outruns good miners  Security Assumption : good miners own >.5 of the total compute power [ blockchain.inf o, April 2015] 20%

28 .1. New transactions are broadcast to all nodes. 2. Each node collects new transactions into a block. 3. Each node works on finding a difficult proof-of-work for its block. 4. When a node finds a proof-of-work, it broadcasts the block to all nodes. 5. Nodes accept the block only if all transactions in it are valid and not already spent. 6. Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash. Nodes always consider the longest chain to be the correct one and will keep working on extending it. Bitcoin: Network

29 .Bitcoin: Network N1 N2 N3 N4 N6 N5 TX1 = [Alice → Bob] TX2 = [Alice → Carol]