6.5840 2023 Lecture 22: Bitcoin Bitcoin: A Peer-to-Peer Electronic Cash System, by Satoshi Nakamoto, 2008 why this paper? agreement despite byzantine participants like SUNDR straw man: log of signed operations agreement on log content -> agreement on state forks are a key danger unlike SUNDR can continue even in the face of (some) malice i.e. can continue in the face of forks unlike PBFT an open/permissionless system, no specially designated servers even # of servers is not known (so voting wd be hard) the agreement scheme is new and interesting Bitcoin's success was a surprise what are the technical challenges? forgery spending someone else's money double spending what does the block chain look like? a sequence ("ledger") of transactions notation: pub(user1): public key of new owner hash(prev): hash of this coin's previous transaction record sig(user2): signature over transaction by previous owner's private key transaction example (much simplified compared to real bitcoin): X has previously paid a coin to Y: T6: pub(X), ... T7: pub(Y), hash(T6), sig(X) Y buys a hamburger from Z and pays with this coin Z sends public key to Y Y creates a new transaction and signs it T8: pub(Z), hash(T7), sig(Y) Y sends transaction record to Z Z verifies: really pub(Z) T7 exists T8's sig(Y) corresponds to T7's pub(Y) Z gives hamburger to Y only the transactions exist, not the coins themselves Z's "balance" is set of unspent transactions for which Z knows private key the "identity" of a coin is the (hash of) its most recent xaction can anyone other than the owner spend a coin? current owner's private key needed to sign next transaction danger: perhaps attacker can steal Z's private key e.g. from PC or smartphone or online exchange this is a serious problem in practice, and hard to solve well can a coin's owner spend it twice in this scheme? Y creates two transactions for same coin: Y->Z, Y->Q both with hash(T7) Y shows different transactions to Z and Q both transactions look good, including signatures and hash now both Z and Q will give hamburgers to Y double-spending is the most fundamental problem that bitcoin solves why was double-spending possible? b/c Z and Q didn't know complete set of transactions a public ledger would reveal Y's double-spend publish a log of all transactions ensure everyone sees the same log, in the same order ensure no-one can un-publish or modify a log entry result: Z will see Y->Z came before Y->Q, and will accept Y->Z Q will see Y->Z came before Y->Q, and will reject Y->Q a "public ledger" how to create such a ledger? the BitCoin block chain the block chain contains all transactions on all coins the goal: agreement on the block chain to prevent double-spending lots of peers participate in agreement some will be malicious design assumes out-numbered by honest avoids SUNDR's hard-edged dependence on a single suspect server peer organization each has a complete copy of the whole chain each has TCP connections to a few other peers -- a "mesh overlay" new chain blocks flooded to all peers, by forwarding over TCP proposed transactions also flooded to all peers flooding helps ensure everyone is aware of all transactions each block: hash(prevblock) set of transactions "nonce" (can be anything, as we'll see) current time (wall clock timestamp) new block every 10 minutes containing xactions since prev block payee believes transaction when seen in the block chain who creates each new block? this is "mining" via "proof-of-work" requirement: hash(block) has N leading zeros each peer tries random nonce values until this works out trying one nonce is fast, but most nonces won't work it's like flipping a zillion-sided coin until it comes up heads each flip has an independent small chance of success mining a block is *not* a specific fixed amount of work it would likely take one CPU months to create one block but thousands of peers are working on it such that expected time to first to find is about 10 minutes though the variance is high the winner floods the new block to all peers how does a Y->Z transaction work w/ block chain? start: all peers know ...<-B5 and are mining block B6 (trying different nonces) Y sends Y->Z transaction to peers, which flood it peers buffer the transaction until B6 computed peers that heard Y->Z include it in next block so eventually ...<-B5<-B6<-B7, where B7 includes Y->Z Q: could there be *two* different successors to B6? A: yes: 1) two peers find nonces at about the same time, or 2) slow network, 2nd block found before 1st is flooded to all two simultaneous blocks will be different miners know about slightly different sets of new transactions, &c. if two successors, the blockchain temporarily forks peers mine a successor to whichever block they heard first but switch to longer chain if they become aware of one how is a fork resolved? each peer initially believes the first new (and valid) block it sees tries to mine a successor if more saw Bx than By, more will mine for Bx, so Bx successor likely to be created first even if exactly half-and-half, one fork likely to be extended first since significant variance in mining time peers switch to the longest fork once they see it so longer fork gets more mining power extending it so agreement on a block tends to be re-enforced what about transactions in the abandoned fork? most will be in both forks but some may be in just the abandoned fork -- appear, then disappear! what if Y sends out Y->Z and Y->Q at the same time? i.e. Y attempts to double-spend correct peers will accept first they see, ignore second thus next block will have one but not both what happens if Y tells some peers about Y->Z, others about Y->Q? perhaps use network DoS to prevent full flooding of either perhaps there will be a fork: B6<-BZ and B6<-BQ thus: temporary double spending is possible, due to forks but one side or the other of the fork highly likely to disappear soon thus if Z sees Y->Z with a few blocks after it, it's very unlikely that it could be overtaken by a different fork containing Y->Q if Z is selling a high-value item, Z should wait for a few blocks before shipping it if Z is selling something cheap, maybe OK to wait just for some peers to see Y->Z and validate it (but not in block) can an attacker modify an existing block in the middle of the block chain? to erase a transaction, or change the recipient? doesn't work directly would have to mine a new nonce to make the block valid most peers will already have the original block and successors the modified block is a fork could attacker start a fork from an old block, with Y->Q instead of Y->Z? yes -- but fork must be longer in order for peers to accept it since attacker's fork starts behind main fork, attacker must mine blocks *faster* than total of other peers with just one CPU, will take months to create even a few blocks by that time the main chain will be much longer no peer will switch to the attacker's shorter chain if the attacker has more CPU power than all the honest bitcoin peers -- then the attacker can create the longest fork, everyone will switch to it, allowing the attacker to double-spend one way to think about bitcoin's proof-of-work mining random choice over all participants for who gets to choose which fork to extend weighted by CPU power if most participants are honest, they will re-inforce agreement on longest fork random choice means a (small) attacker won't get many chances to try to switch agreement to a different fork surprising that random choice is possible without knowing participant identities or even how many! what motivates miners? each new block pays miner a few newly created bitcoins block contains public key that gets the new bitcoins this is incentive for people to operate bitcoin peers consequences: arms race, since more hardware -> more reward special hardware for mining to win pools of miners that collaborate energy waste validation checks: peer, new xaction: previous transaction exists no other transaction spends the same previous transaction signature is by private key of pub key in previous transaction then will add transaction to txn list for next block to mine peer, new block: hash value has enough leading zeroes (i.e. nonce is right, proves work) previous block hash exists all transactions in block are valid peer switches to new chain if longer than current longest Z: (some clients rely on peers to do above checks, some don't) Y->Z is in a block Z's public key / address is in the transaction there's several more blocks in the chain (other stuff has to be checked as well, lots of details) Q: why is it reasonable to assume the majority of peers are honest? Q: if one started a new bitcoin-like cryptocurrency, with only a few peers, would it be reasonable to trust it? Q: 10 minutes is annoying; could it be made much shorter? Q: if lots of miners join, will blocks be created at a higher rate? Q: can bitcoins be forged, i.e. a totally fake coin created? Q: are transactions anonymous? Q: how could one steal someone else's bitcoins? Q: if I steal bitcoins, is it safe to spend them? Q: what if the block format needs to be changed? esp if new format wouldn't be acceptable to previous s/w version? "hard fork" Q: how do peers find each other? Q: what if a peer has been tricked into only talking to corrupt peers? Q: what if a peer rejoins after a long period of disconnection? Q: how rich are you likely to get with one machine mining? Q: why does it make sense for the mining reward to decrease with time? Q: is it a problem that there will be a fixed number of coins? what if the real economy grows (or shrinks)? Q: why do bitcoins have value? e.g. people seem willing to pay $42,000 per bitcoin (April 2022). Q: will bitcoin scale well? 10 minutes * 1 MB blocks -> about 5 transactions/second credit card system handles about 5000 / second disk: currently about 480 GB of storage Q: could Bitcoin have been just a ledger w/o a new currency? e.g. have dollars be the currency? since the currency part is pretty awkward. how to incentivize miners? how to transfer actual dollars? Q: why don't more people use Bitcoin for ordinary transactions? high fees; not reversible; 10 minute delay; volatile value weak points in the design? proof-of-work uses a lot of electricity too bad it's a new currency as well as a payment system transaction confirmation takes at least 10 minutes, or 60 for high confidence flooding limits performance, may be a point of attack maximum block size plus 10 minutes limits max transactions per second vulnerable to majority attack not very anonmyous anonymous enough to attract illegal activity users have trouble securing private keys key idea: block chain public agreed-on ledger is a great idea decentralization might be good mining is a clever way to resolve forks / ensure agreement ---- References ---- Bitcoin SoK: https://www.ieee-security.org/TC/SP2015/papers-archived/6949a104.pdf Scripting language: https://en.bitcoin.it/wiki/Script https://www.oreilly.com/library/view/mastering-bitcoin/9781491902639/ch08.html