Bitcoin mechanics & Nakamoto Consensus
This lecture
● Models for a public ledger
Copyright By PowCoder代写 加微信 powcoder
○ Centralized ledgers
○ Byzantine consensus
○ The goal of decentralization
● Nakamoto Consensus
● Computational puzzles
● Bitcoin transactions
● Bitcoin scripts
Recap: prevent double-spending via a public ledger
signed by pkGoofy
CreateCoin [unique ID X]
signed by pkGoofy
Pay to pkAlice : X
signed by pk to pkBob : X
signed by pk to pkChuck : X
Invalid transactions not included…
Ledger represented via a blockchain
H() H() H() H()
H() H() H() H() H() H() H() H()
F1 F2 F3 F4 F5 F6 F7 F8
Efficiency properties of a blockchain
● Providing appension (new block added): O(1)
● Proving old block chains to current head: O(n) for n blocks
● Proving inclusion of a transaction in a block: O(lg k) for k transactions
Required properties of a ledger
● Append-only
○ Data can never be removed
● Total ordering
○ Can observe which transaction came first
● Global consensus
○ Everybody needs to agree on contents
● Global availability
○ No censorship
Central question: who maintains the ledger?
Centralized consensus: ScroogeCoin
Scrooge signs all blocks in the chain
prev: H( )
prev: H( )
prev: H( )
Scrooge can create new coins
Valid, because I said so.
transID: 72 type:CreateCoins
coins created
coinID 72(0) coinID 72(1) coinID 72(2)
Transactions consume some coins, create new ones
transID: 73 type:PayCoins
consumed coinIDs: 68(1), 42(0), 72(2)
coins created
signatures
● consumed coins valid,
● not already consumed,
● total out = total in
● signed by owners of all
consumed coins
Pros and cons of centralization Don’t worry, I’m honest.
● Simplicity
● Efficiency
● Coordinated changes
● Security risks (double-spending)
● Censorship risks
● Economic risks (monopoly)
Most cryptocurrencies aim for decentralization Don’t worry, I’m honest.
Can we decentralize the currency, and operate without any central, trusted party?
Centralization vs. decentralization
Decentralized
Centralized
Whatsapp/iMessage/Wechat etc.
Facebook/Twitter etc.
BitTorrent
Apple Music, Spotify etc.
Commercial VPNs
Cryptocurrencies
VISA network/government currencies
Centralization is a spectrum, not a binary property
Centralization (anti)-patterns
● Political centralization
○ Who sets the rules?
● Administrative centralization
○ Who determines the current state?
● Infrastructure centralization
○ Where is the data/machines? Who makes and operates them?
● Economic centralization
○ Who is capturing the economic surplus?
Several centralization points for a cryptocurrency
● Who maintains the ledger?
● Who has authority over which transactions are valid?
● Who creates new coins?
● Who determines how the rules of the system change?
● How do coins acquire exchange value?
Beyond the core protocol:
exchanges, wallet software, service providers…
Decentralized Consensus
Bitcoin’s challenge: consensus on ledger
user transaction Bitcoin network blockchain (decent. ledger)
When Alice wants to pay Bob:
she broadcasts the transaction to all Bitcoin nodes
… and anybody can run a Bitcoin node!
signed by to pkBob : H( )
Distributed consensus is a classic goal
● Traditional motivation: reliability in distributed systems
● Replicated state machine abstraction:
○ Distributed hash table, DNS, public key directory, …
● Byzantine consensus: assume some nodes fail arbitrarily ○ Also called Byzantine/malicious/traitorous nodes
Classic distributed consensus (RSMs)
● N total, known nodes
● f faulty nodes
● Can accept any valid tx
● Message integrity (signatures)
● Safety (all honest nodes agree)
● Liveness (progress is made)
Consensus protocol
Practical challenges in consensus
● Nodes may crash
● Nodes may be malicious
● Network is imperfect
○ Not all pairs of nodes connected
○ Faults in network ○ Latency
Many classic results on consensus protocols
● Limits/impossibility results:
○ Byzantine generals problem (need >2/3 honest) ○ Fischer-Lynch-Paterson
● Classic consensus protocols ○ Paxos
○ RAFT ○ PBFT
Byzantine general’s problem impossibility result
Byzantine node
Conclusion: attack!
Conclusion: retreat!
Consensus requires f
Bitcoin script execution example
Bitcoin script instructions
256 opcodes total (15 disabled, 75 reserved)
● Arithmetic
● Logic/data handling
○ Signature verification
○ Multi-signature verification
OP_CHECKMULTISIG
● Built-in support for joint signatures ● Specify n public keys
● Specify t
● Verification requires t signatures
BUG ALERT: Extra data value popped from the stack and ignored
Bitcoin scripts in practice (as of 2014)
● Most nodes whitelist known scripts ● 99.9% are simple signature checks ● ~0.01% are MULTISIG More on this soon
● ~0.01% are Pay-to-Script-Hash
● Remainder are errors, proof-of-burn
Proof-of-burn
nothing’s going to redeem that ☹
OP_RETURN
Should senders specify scripts?
I’m ready to pay for my purchases!
Cool! Well we’re using MULTISIG now, so include a script requiring 2 of our 3 account managers to approve. Don’t get any of those details wrong. Thanks for shopping at Big Box!
Idea: use the hash of redemption script
signature>
OP_HASH160
“Pay to Script Hash”
Pay to script hash
I’m ready to pay for my purchases!
Great! Here’s our address: 0x3454
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com