Week 6 part 1 mining
Miner’s role
• Validate new transactions
• Mine blocks
Copyright By PowCoder代写 加微信 powcoder
• Store and broadcast blockchains
• Vote (by hash power) on consensus
But who are the miners?
So you want to be a miner?
Klondike gold rush of 1898 (northwest Canada).
Prospective miners ascending the Chilkoot pass.
Mining in 6 easy steps
1. Join the network, listen for transactions; Validate all proposed transactions.
2. Listen for new blocks, maintain blockchain; When a new block is proposed, validate it.
Useful 3 to 4 Bitcoin
. Assemble transactions into a new block;
. Find the nonce to make your block valid; network5. Hope everybody accepts your new block;
6. Profit!
Finding a valid block
prev: H( )
mrkl_root: H( )
nonce: 0x0f0f00f700f0702f101e0…
hash: 0xd36c03029a4c2c10874c08f5… hash:
prev: H( )
mrkl_root: H( )
nonce: 0x7a83
hash: 0x0000
All changed
H( ) H( ) H() H()
transaction
transaction
transaction
Mining difficulty
25.0→A coinbase: 0x300d0f005…06501
• original_target = 0x00000000ffff000000000000000000000000000000000000000000 0000000000
• Current target sometime in Jan 2023: 0x000000000000000000077ce20000000000000000000000000000 000000000000
(https://learnmeabitcoin.com/technical/target)
• So, a successful 256-bit hash begins with about 77 zeros.
• difficulty = original_target / current_target.
• Once every 2016 blocks, update current_target so that difficulty =
previous_difficulty * (2 weeks)/(time to mine the last 2016 blocks).
• In Feb. 2023, difficulty ~= 4 x 1013, i.e., it’s about 40 trillion times harder now than the genesis block.
Time to find a block
10 minutes
CPU mining
• Keep increasing nonce in HDR until the difficulty requirement is satisfied.
while (1){
HDR[kNoncePos]++;
IF (SHA256(SHA256(HDR)) < (65535 << 208)/ DIFFICULTY)
} two hashes
• Throughput on a high-end PC < 100 M hashes/second.
• Recall about 1023 hashes/block today.
• It’ll take more than 10 million years to find a block today!
GPU mining
• GPUs designed for high-performance graphics o high parallelism
o high throughput
• First used for Bitcoin ca. October 2010
• Implemented in OpenCL
o Later: hacks for specific cards
• Observation: some errors are okay (may miss a valid block)
• Goodput: throughput × success rate
• Worth over-clocking GPU by 50% with 30% errors!
Source: LeonardH, cryptocurren ciestalk.com
GPU mining disadvantages
• poor utilization of hardware
• poor cooling
• large power draw
• few boards to hold multiple GPUs
• Not fast enough.
FPGA mining
• Field Programmable Gate Array
• First used for Bitcoin ca. June 2011
• Implemented in Verilog
• higher performance than GPUs
• excellent performance on bitwise operations
• better cooling
• extensive customization, optimization.
, thinkcomputers.org
FPGA mining disadvantages
● higher power draw than GPUs designed for ○ frequent malfunctions, errors
● poor optimization of 32-bit adds
● fewer hobbyists with sufficient expertise
● more expensive than GPUs
● marginal performance/cost advantage over GPUs
● Still not fast enough today.
Application-Specific Integrated Circuit (ASIC)
Bitcoin ASICs
• special purpose
o approaching known limits on feature sizes
o less than 10x performance improvement expected
• designed to be run constantly for life
• require significant expertise, long lead-times
• In terms of time to market, perhaps the fastest chip
development ever!
Market dynamics
• Boards often obsolete within one year (depending on crypto and energy price and chip innovations);
• A significant portion of the profits made in the first few months;
• Shipping delays are devastating to miners;
• Most individual miners should have lost...
• In the past, rising prices have saved them!
• Depending on energy cost, difficulty level, and bitcoin
exchange rate, miners may choose to turn older machines on/off, which in turn affects the difficulty level down the road—a dynamic resource management problem!
Professional mining centers
• cheap power
• cool climate
• good network
A mining facility in Norcross, GA
Evolution of mining
CPU GPU FPGA
gold pan sluice box placer mining
The future
• Can small miners stay in the game?
• Do ASICs violate the original Bitcoin vision?
• Would we be better off without ASICs?
pit mining
Thermodynamic limits
Landauer’s principle: Any non-reversible computation must consume a minimum amount of energy.
Specifically, each bit changed requires (kT ln 2) joules. SHA-256 is not reversible.
Energy consumption is inevitable.
• Embodied energy: used to manufacture mining chips & other equipment:
o should decrease over time; o returns to scale.
• Electricity: used to perform computation:
o increases over time;
o returns to scale.
• Cooling: required to protect equipment
o costs more with increased scale!
Total energy consumption
• In 2022, global Bitcoin mining consumed 161 tera Watt hours of electricity in total, according to Digiconomist.
• The consumed electricity power is about 18,000 MW.
• ~10 million U.S. households, or 0.64% of the world total
electricity consumption.
How much is a MW?
Kashiwazaki-Kariwa
nuclear power plant = 7,000 MW typical nuclear plant ≈ 4,000 MW
major coal-fired plant ≈ 2,000 MW
Three Gorges Dam = 10,000 MW typical hydro plant ≈ 1,000 MW
Estimating energy usage: top down
• Each block worth approximately US$150,000 in Jan. 2023;
• About $1 M/hour, or ~$9 B/year;
• Industrial electricity (U.S.): $0.05/kWh;
• If all new bitcoin wealth is spent on electricity, it buys 180 TWh or 20,000 MW.
Estimating energy usage:
• Efficiency: ~20 G hash/s/W
• Network hash rate: 3 x 1020 hash/s
• (excludes cooling, embodied energy)
• Using the most energy-efficient mining hardware, at least
15,000 MW is needed to sustain the current hash rate.
Total mining cost
• The global mining cost is estimated to be about $3.5 billion/year.
• The global mining revenue is about $6 billion/year at the current exchange rate.
All payment systems require energy
Cost per transaction
● 1 MWh is consumed per bitcoin transaction on average. This is enough to power a typical U.S. household for a month. (The electricity cost is something like $50.)
● In contrast, the bitcoin transaction fee is about 20 cents today (it briefly shot up to over $35 in December 2017).
● Any problem?
Data furnaces
● Observation: in the limit, computing devices produce heat almost as well as electric heaters!
● Why not install mining rigs as home heaters? ● Challenges:
○ Ownership/maintenance model
○ Gas heaters still at least 10x more efficient ○ What happens in summer?
Open questions
● drive out electricity subsidies?
● require guarding power outlets?
● Can we make a currency with no proof-of-work?
Economics of being a small miner
• Cost: ≈US$6,000
• Expected time to find a block: ≈14 months
• Expected revenue: ≈$1,000/month
Mining uncertainty
Time to find first block
# blocks found in one year
probability (Poisson dist.)
Probability density
Idea: could small miners pool risk?
Mining pools
• Goal: pool participants all attempt to mine a block with the same coinbase recipient
o send money to key owned by pool manager
• Distribute revenues to members based on how much work
they have performed
o minus a cut for pool manager
How do we know how much work members perform?
Mining shares
Idea: prove work with “near-valid blocks” (shares)
4AA087F0A52ED2093FA816E53B9B6317F9B8C1227A61F9481AFED67301F2E3FB D3E51477DCAB108750A5BC9093F6510759CC880BB171A5B77FB4A34ACA27DEDD 00000000008534FF68B98935D090DF5669E3403BD16F1CDFD41CF17D6B474255 BB34ECA3DBB52EFF4B104EBBC0974841EF2F3A59EBBC4474A12F9F595EB81F4B 00000000002F891C1E232F687E41515637F7699EA0F462C2564233FE082BB0AF 0090488133779E7E98177AF1C765CF02D01AB4848DF555533B6C4CFCA201CBA1 460BEFA43B7083E502D36D9D08D64AFB99A100B3B80D4EA4F7B38E18174A0BFB 000000000000000078FB7E1F7E2E4854B8BC71412197EB1448911FA77BAE808A 652F374601D149AC47E01E7776138456181FA4F9D0EEDD8C4FDE3BEF6B1B7ECE 785526402143A291CFD60DA09CC80DD066BC723FD5FD20F9B50D614313529AF3 000000000041EE593434686000AF77F54CDE839A6CE30957B14EDEC10B15C9E5 9C20B06B01A0136F192BD48E0F372A4B9E6BA6ABC36F02FCED22FD9780026A8F
Mining pools
Hey folks! Here’s our next block to work on
Pool manager
prev: H( )
mrkl_root: H( )
0x00000000000a877902e...
0x000000000001e8709ce...
0x00000000000490c6b00... 0x0000000000007313f89... 0x0000000000045a1611f...
0x00000000000000003f89...
Mining pool variations
● Pay per share: flat reward per share
○ Typically minus a significant fee
○ What if miners never send in valid blocks?
● Proportional: typically since last block ○ Lower risk for pool manager
○ More work to verify
● “Luke-jr” approach: no management fee
○ Miners can only get paid out in whole BTC ○ Pool owner keeps spread
Mining pool protocols
● API for fetching blocks, submitting shares ○ Stratum
○ Getblockshare
● Increasingly important; some hardware support.
Mining pool history
● First pools appear in late-2010 ○ Back in the GPU era!
● By 2014: around 90% of mining pool-based ● June 2014: GHash.io exceeds 50%
Mining pool
https://miningpools.com/ethereum/
Are mining pools a good thing?
o Make mining more predictable;
o Allow small miners to participate;
o More miners using updated validation software;
o Grows total mining power. • Cons
o Lead to centralization;
o Discourage miners from running full nodes.
Week 6, part 2 P2P networking
P2P Networking Random and Structured Graphs Engineering issues
Networking Requirements
• No centralized server
o Avoid a single point of failure o Avoid censorship
• Key Primitive: Broadcast blocks and transactions to all nodes
• Robustness
o some nodes go offline
o new nodes join
o Possibly high rate of churns
Types of Network Architecture
Each node acts as a client and a server Client server
Server stores most of the data
(Canvas, Banks, Twitter, etc.)
Peer to Peer
BitTorrent, Napster
Overlay Networks
Physical Network
Structured
Virtual links
Virtual topology
Overlay Networks
Example: CHORD
Assign a graph node identifier to each node
Well defined Peer routing rules
O(log N) routing
O(log N) connections per node
Unstructured
Overlay Networks
• Example: d-regular graph
• No node graph identifier
• Connect to any random d- nodes
• O(log N) routing (difficult to route)
• O(1) connections per node
• O(log N) broadcast
Gossip and Flooding
• Mimics the spread of an epidemic
• Onceanodeis “infected”, it “infects” its peers
• InformationSpread exponentially and reaches nodes in O(log(N)) time
An expander graph
is a sparse graph that has strong connectivity properties. Intuitively, every subset of the vertices that is not ”too large” has a “large” boundary.
• Sparse graph G(V,E): |E| = O(|V|), where |V| denotes the number of vertices; |E| denotes the number of edges.
• By an expander graph we mean |!" ≥ $ "| if |A| is not too large.
o | !"| = number of vertices outside " with at-least one neighbor in ". o The gossip reaches |!"| additional nodes.
• A random d-regular(d ≥3) graph for large |V| is an expander graph (with high probability).
• Intuition for O(log N) broadcast.
Bitcoin network
• TCP connection with peers
• At most 8 outbound TCP connections
• May accept up to 117 inbound TCP connections
• Maintains a large list of nodes(IP, port) on the bitcoin network
• Establishes connection to a subset of the stored nodes
Peer discovery
• DNS seed nodes (hard coded in the codebase)
• Easy to be compromised, do not trust one seed node
exclusively
• Hardcoded peers (fallback)
• Ask connected peers for additional peers
Version Connecting to a peer
Block transmission
Get addr addr
Gathering additional peers Addr: contains list of up to 1000 nodes
Block-First
Getdata asks for inv the same block
as inv getdata Can download block
orphan blocks and keep it in memory
getheaders headers
getdata block
• Header-First
• Getheaders asks for
the same block as inv or a few parent headers (in case of orphan block)
• Will not download orphan blocks if no header chain established
Block is broadcasted to the network using gossip-flooding Standard block relay protocol to gossip blocks
Relay after block validation
Inv(blockhash): inventory message containing blockhash
Data/transaction broadcast
• Data (transactions) broadcast using Gossip-flooding;
• Each node maintains a non-persistent memory to store
unconfirmed tx (mempool);
• inv(txid): Check if peer has a transaction with id: txid in mempool;
inv getdata transaction
• Some unconfirmed tx might be removed from mempool.
Compact blocks
inv getdata
Legacy relaying
Sendcmpct(0)
getdata Cmpctblock
getblktxn blktxn
Compact block relaying
• Legacyrelayingsends blocks which include all transactions.
• Compactrelayingfirst guesses the mempool of the receiving node;
• Acompactblockhas block header, txids, some full transactions;
• Thereceivingnode sends getblktxn to receive missing transactions.
Capacity and Propagation Delay
• C = communication/processing capacity of the network (tx/s)
• D = speed-of-light propagation delay
• End to end delay
1. Propagation delay: D
2. Processing delay: B/C (where B is block size in tx) 3. Queuing delay
• Delay increases with increase in block size
Effects of delay
• Wasted hashpower
Shortcomings of current p2p net
• Efficiency
o Not efficient (total communication is O(Nd))
o Can link transaction source to IP address
• Security
o Plausible deniability for forking
P2P topology improvement
• Random IP network
o Not related to geographic distances
• Need a geometric random network
o IP addresses do not necessarily reveal location
• Challenge
o Self-adapting network topology based on measurements
• Y. Mao, S. Deb, S. B. Venkatakrishnan, S. Kannan, and K. Srinivasan. "Perigee: Efficient peer-to-peer network design for blockchains." In Proceedings of the 39th Symposium on Principles of Distributed Computing, 2020.
• A self-adaptive network topology algorithm o Goal: mimic random geometric network
• Decentralized algorithm that selects neighbors based on past interactions o retain neighbors that relay blocks fast
o disconnect from neighbors that do not relay blocks fast
o explore unseen neighbors
• Motivated by the multi-armed bandit problem o Explore vs exploit tradeoff
Perigee Algorithm
• Assign scores for each subset of neighbors based on how fast they relay blocks
• Retain subset neighbors with best score
• Disconnect node not in the subset
• Form a connection to a random neighbor
Random Topology
Perigee: Large node delay
Perigee: Small node delay
Perigee: No node delay
Random Geometric Graph
PERFORMANCE OF PERIGEE
Efficient Networking
• Trusted networks • Privacy
o Can link transaction source to IP address
• Security
o Plausible deniability for forking o Eclipse attacks
Trusted Networks
• FRN (Fast relay network): Hub and spoke model, trusted servers, servers are fast
FRN servers Networks: Falcon
• Cut through routing for servers, only verify headers before forwarding
Legacy routing
Cut through routing a’
Latency N(a+b)
Latency Na’+b
Bitcoin System Overview
Parts of the Midterm project
1. Block and Blockchain structure 2. Miner
3. Network and blockchain
4. Transactions and validation
Block structure
LIST OF TRANSACTIONS
BLOCK HEADER (New block) Parent hash(tip of blockchain)
• Mining target • Timestamp • Merkle root
BLOCK HEADER • Parent hash
• Nonce Mining target
• Merkle root
• Timestamp
• Merklerootofthelist of transactions
• Difficulty: Mining target
• Timestamp: Local time
when a block is mined
LIST OF TRANSACTIONS
• Try different nonce in block header until, Hash(block header) < Mining target
• Equivalent to lottery due to uniform random output
• Mining target set by the protocol
• Change timestamp, Merkle root(list of transactions) if all options of nonce are exhausted
(Coinbase transaction, all other transactions)
• Miner gets its mining reward through coinbase transactions
• Coinbase transactions: Thin air -> Miner’s account (Public key)
• Coinbase transaction will be different for different miners
Network + getblocks
• ImplementaBlockFirstnode
• Inv=NewBlocks(listofblockhash)
• Getdata=getblocks(listofblockhash)
• Block=Blockheader+block
content(transactions)
• Donotneedtoimplementpeerdiscovery protocol
• Createad-regulartopologyandcentrally feed peer addresses to each node
them together
If validation passed
State reorg
Miner mines a block and
sends it to its peers
Orphan block
Receive new block and check for block
header validity
Parent = tip of local blockchain
block If parent
exits in blockchain
Peers receive the block and validates it
Peers broadcast the block to other peers
Store in orphan block buffer
(or discard for simplicity)
Validate transactions
Update blockchain and blockdb
Update blockchain and blockdb
Transactions, UTXO,
• UTXO: Unspent Transaction Output
• UTXOarestoredascoins: Coinid: Hash of tx, index of output
• InputsmustbeUTXOs
• Alternate: account model
• TransactionMempoolisoffixedsize • Minercollectstransactionsfrom
mempool (priority typically given to higher fees) and forms a block
Source: bitcoin.org
Transactions
Transaction
NewTransactions getTransactions
transactions
TRANSACTION INPUT((coinid, value, owner))
OUTPUT((value, recipient)) Signature(of all input owners)
Transactions is stored in mempool &
broadcasted to peers
Peers verify and broadcast
the transaction
Transaction is submitted to a node by a client
Transaction is verified (signature and state)
4 validation
• Each node maintains a UTXO database (state)
• Check if tx inputs are in UTXO database (state validation)
• When a new block arrives, it leads to reorganization of blockchain
• Some transactions are added (typically the scenario)
• Remove Input of the transaction from UTXO db, add outputs of tx to UTXO db
• Some transactions are removed (if a fork is now the longest chain)
• Remove output of transactions from UTXO db, add input of tx to UTXO db
State handling and
Calculate blocks added and removed
from Blockchain
Remove transactions (removed
blocks), update state
Add transactions (added
blocks), update state
New block added to blockchain
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com