Alternative consensus protocols
Recap: Bitcoin consensus
¡ñ Permissionless, open participation ¡ð Proof-of-work (SHA-256)
Copyright By PowCoder代写 加微信 powcoder
¡ñ ¡°Longest¡± linear chain works (Nakamoto consensus) ¡ð Really, most aggregate work
Recap: Bitcoin consensus
¡ñ Permissionless, open participation ¡ð Proof-of-work (SHA-256)
¡ñ ¡°Longest¡± linear chain works (Nakamoto consensus) ¡ð Really, most aggregate work
¡ñ Dominated by mining pools
¡ñ Dominated by ASIC miners
¡ñ Slow block frequency/small blocks
¡ñ Large ecological footprint
Necessity is the mother invention
Every characteristic problem with Bitcoin consensus has spawned new ideas:
¡ñ Dominated by mining pools ¡ð Non-outsourceable puzzles
¡ñ Dominated by ASIC miners
¡ð ASIC-resistant puzzles
¡ð Proof-of-space, -storage, -memory, -elapsed-time
¡ñ Slow block frequency/small blocks
¡ð BlockDAG protocols
¡ð Leader-based protocols
¡ñ Large ecological footprint
¡ð Permissioned protocols ¡ð Proof-of-stake
Many projects trying to fix multiple problems at once
Goals for any decentralized consensus protocol
¡ñ Security
¡ð ¡°Bad things can¡¯t happen¡± by adversary who controls some threshold of resources
¡ð Even if the adversary is adaptive
¡ñ Liveness
¡ð ¡°Eventually good things happen¡±
¡ñ Performance
¡ð Transactions are added with high throughput and low latency
¡ð Low transaction fees
¡ð Fast verification of ledger
¡ñ Fairness
¡ð Rewards are equitably distributed to consensus participants
¡ð Censorship of transactions is not difficult
Bitcoin trades off performance at almost every turn
¡ñ Security
¡ð No significant attacks
¡ñ Liveness
¡ð No significant stoppages
¡ñ Performance
¡ð Poor throughput and latency
¡ð High fees
¡ð Very expensive to verify ledger
¡ñ Fairness
¡ð Miners mostly paid equitably
¡ð No history of censorship (at the consensus layer)
Alternate mining puzzles
Generic puzzle formulation Puzzle takes three properties:
¡ñ b current blockheader hash
¡ñ d difficulty parameter
¡ñ n mining-puzzle specific information (e.g. nonce)
Puzzle predicate identifies valid blocks: Verify(b, d, n) ¡ú True/False
Recap: Bitcoin uses SHA-2562
Verify(b, d, n):
return sha256(sha256(b, n)) < 2256-d
Three essential mining puzzle requirements
¡ñ Easy to verify solutions
¡ñ Easy to precisely adjust difficulty ¡ñ Progress-free:
Three essential mining puzzle requirements
¡ñ Easy to verify solutions
¡ñ Easy to precisely adjust difficulty ¡ñ Progress-free:
The expected number of valid puzzle solutions found is linearly proportional to the number of processors and the time those processor spend.
Essential to ensure that small miners can compete ¡°fairly¡± with large miners
Progres-free puzzle ¡ú Weighted sample
A non-progress free puzzle
¡°Sequential¡± Proof of Work:
Consider a puzzle that always takes N steps to solve (e.g. SHA-256N)
Solution Found!
Bad puzzle: a sequential puzzle
Problem: fastest miner always wins the race!
Solution Found!
Brute-force puzzles are an important class
Conjecture: given blockheader b, difficulty d, there is no better approach than: def solve(b, d):
while True:
n = random()
if Verify(b, d, n):
Progress-free as long as Verify is suitably fast
ASIC resistance
Why ASIC resistance?
Ordinary people can mine with idle laptops, PCs, or even mobile devices More equitable distribution of mining rewards
More decentralization
Approach: reduce the gap between custom hardware and general machines
Why ASIC resistance?
Prevent large manufacturers from dominating the game
¡°Burn-in¡± advantage In-house designs
reduce the ¡°gap¡± between best hardware and existing chips take advantage of what existing chips already do well!
Counter argument: ASICs are commodities too now
ASICs aren¡¯t changing much
Big ASICs only marginally more performant than small ones Bitcoin ASICs becoming a commodity
Affordable ASIC
Expensive ASIC
SHA2 SHA2 SHA2 SHA2 SHA2 SHA2 SHA2 SHA2 SHA2
SHA2 SHA2 SHA2 ...
SHA2 SHA2 SHA2
SHA2 SHA2 SHA2
Ordinary SHA2 Circuit SHA2
Counter argument: ASICs are good for security
ASICs are Bitcoin-specific by design
No other application, little salvage value
Miners who¡¯ve invested in ASICs are invested in the future of the system
If they misbehave, their investment in ASICs could be worthless
Simple ASIC-resistance approach: ¡°moving target¡±
Change puzzles every ~6 months or so ASICs take at least 9-12 months to design
FPGAs, GPUs may still be superior
Who gets to decide what the new puzzle is?
Simple ASIC-resistance approach: complexity
CPUs designed for complex programs Use a suite of many puzzles Example: X11
ASICs can crush this
Temporary speedbump only, complexity remains forever
Memory-hard puzzles
Premise: a significant fraction of modern machines¡¯ cost is highly optimized RAM
Memory hard puzzles
Premise: the cost and performance of memory is more stable than for processors
10000 1000
Performance
Processors
¡°performance gap¡±
Memory Storage
¡®80 ¡®90 ¡®00 Time
A simple memory-hard function: scrypt
¡ñ Memory hard hash function
¡ñ Most widely used alternative Bitcoin puzzle
¡ñ Also used elsewhere in security (PW-hashing)
1. Fill memory with random values
2. Read from the memory in random order
scrypt - step 1 of 2 (write random values to memory)
V2 = H(V1) = H(H(X)) V3 = H(V2) = H3(X)
VN = HN(x)
scrypt - step 2 of 2 (read memory in random order)
A := HN+1(X)
For N iterations:
i := A mod N
A := H(A xor Vi)
Scrypt admits a time/memory tradeoff Why is this memory-hard?
Reduce memory by half, 1.5x the # steps
Need to access Vi where i is even? Access Vi-1
Compute Vi = H(Vi-1)
Time-memory tradeoffs are ideally very steep
Memory Memory available available
Time required
Time required
Scrypt has several other disadvantages
¡ñ Verification is memory-hard as well (requires re-execution)
¡ñ Doesn¡¯t require random writes to memory
¡ñ ASICS also crush this because parameters used are small (128 kB RAM)
¡ð Litecoin mining now dominated by ASICs as well
Cuckoo hash cycles
Memory hard puzzle that¡¯s cheap to verify Input: X
For i = 1 to E:
a := H0(X + i)
b := N + H1(X + i) edge(a mod N, b mod N)
Is there a cycle of size K? If so, Output: X, K edges
A second-generation approach: Ethhash
¡ñ Uses a dataset of 4-5 GB (regenerated every 30k blocks/4 days)
¡ñ Can be efficiently verified with 16 MB RAM
¡ñ Designed for GPU efficiency
¡ð Most mining for Ethereum is still done on GPUs!
Proof-of-space
Idea: require so much storage that disk is required
Similar to RAM, consumers own spare (optimized) disk space
This space is filled with pseudorandom data
Puzzle solutions include a proof of correctness (like a Merkle proof)
Example: Chia. ¡°Farming¡± required ~100 GB ¡°plots¡± of storage
Proof of useful work
Can we make the energy expenditure useful?
Economic upper bound on electricity consumed: 13,000 MJ/s = 13 GW
Lower bound on electricity consumed: ~6 GW
Candidates: distributed computing projects
¡ñ Natural choices:
- Protein folding (find a low energy configuration)
- Search for aliens (find an anomalous region of a signal)
¡ñ Challenges:
- Who chooses the problem?
- Most known examples are not progress-free
Puzzle based on finding large prime numbers
Cunningham chain:
p1, p2, ... pn where pi = 2¡¤pi
Each pi is a large (probable) prime
p1 encodes the bits of H(prev || mrkl_root || nonce)
¡ñ The largest known Cunningham chains are now from Primecoin miners
¡ñ Hard problem? Studied by others (e.g., PrimeGrid)
¡ñ Usefulness? Maybe...
Proof-of-storage
Permacoin: Miller et al., 2014
Idea: store useful data, rather than pseudorandom data (as in proof-of-space)
For simplicity: assume one file F, chosen once by a trusted dealer
Each user stores a random subset of the file F
Storage-based puzzle
1. Build a Merkle tree, where each leaf is a segment of the file
2. Generate a public signing key pk, which determines a random subset of file segments
3. Each mining attempt:
a) Select a random nonce
b) h1 := H(prev || mrkl_root || PK ||
c) h1 selects k segments from subset
H(prev || mrkl_root || PK || nonce || F)
F1 F2 F4 F5
e) Winner if h2 < TARGET
A modern proof-of-storage blockchain: Filecoin
¡ñ Anybody can submit data to store, for a cost
¡ñ Uses proof-of-replication to prove independent copies stored
¡ñ Over 40 petabytes stored today
Non-outsourceable puzzles
Mining pools (March 2022)
Mining pools (June 2014)
Some see large pools as an existential threat
Large mining pools are seen as a threat
¡ñ Bitcoin¡¯s core value is decentralization
¡ñ Large pool operators are targets for coercion/hacking
¡ð Many miners effectively ignorant of underlying ledger
¡ñ Position: large pools should be discouraged! voting: It¡¯s illegal (in US) to sell your vote
Mining pool design is a ¡°happy accident¡±
Observation:
Pool participants don¡¯t trust each other
Pools only work because the ¡°shares¡± protocol lets members prove cooperation
Standard Bitcoin mining pool
Payout dividing among members
Pool Operator
¡°shares¡±:
proof that a member is ¡°toeing the line¡±
Pool Members
Solution found!
Sabotage attacks
Suppose a saboteur is angry with a large pool
He submits ¡°shares¡± like normal....
... but if he finds a real solution, discards it
Pool output is reduced, saboteur loses a little
The Saboteur Attack
Payout dividing among members
Solution discarded
Pool Operator
¡°shares¡±:
proof that a member is ¡°toeing the line¡±
Pool Members
Encouraging sabotage
Whoever finds a solution spends the reward
- searching for a solution requires signing (Knowledge of a private key) - Private key can be used to spend the reward
Encouraging sabotage
Pool Operator
¡°shares¡±
Pool Members
Solution found!
Take the money and run! Also: evade detection
Nonoutsourceable puzzle
Public Key
(prev, mrkl_root, nonce, PK, s1, s2)
Signature needed to find solution
such that:
Second signature spends reward
VerifySig(PK, s1, prev || nonce)
H(prev || PK || nonce || s1) < TARGET
VerifySig(PK, s2, prev || mrkl_root)
Non-outsourceable puzzle concerns
¡ñ This puzzle discourages ALL pools, including decentralized P2Pools
¡ñ Other forms of outsourcing might drive pool members to hosted mining
Proof-of-stake
The mining ecosystem in the long-run
mining rewards
power, equipment
puzzle solutions
Do we need this side?
Mining is simply a matter of funds under ideal conditions
¡ñ Miners all attempt to turn some budget into hash power - Compete on electricity costs
- Compete on ASIC efficiency
¡ñ In the long run, both will be commodities. Everybody pays the same cost
¡ñ We don¡¯t care about rewarding innovation on either front
¡ñ Bitcoin mining is a (very) expensive signaling mechanism
Virtual mining replaces mining with a simulation Earn mining
chosen at random by lottery
¡°Mine¡± by burning or freezing funds
Virtual mining offers significant benefits
¡ñ Very low ecological costs
- Translates to economic savings to all participants too
¡ñ No ASIC advantages-perfectly fair
¡ñ Miners are all stakeholders-incentivized to be good stewards
¡ð 51% attack appears harder. Need to buy out current stakeholders
Many variations of Virtual Mining
¡ñ Proof-of-Stake
¡ð Mining power in proportion to total holdings
¡ñ Proof-of-Burn
¡ð Mining with a coin destroys it
¡ñ Proof-of-Deposit
¡ð Mining requires freezing a coin for some time period ¡ñ Proof-of-Activity
¡ð Mining in proportion to activity
A first attempt: Peercoin
H(prev || PK || nonce ) < TARGET * s
With the coin-age parameter s:
Mining with a coin resets its idle time counter
S = sum([value(x) * idle_time(x) for i in coinbase inputs])
Peercoin was a hybrid proof-of-stake system with flaws
¡ñ Proof-of-work still required (and advantageous)
¡ñ Surge attacks possible: hoard coins (don¡¯t mine) then mine many blocks
¡ñ Adaptive attacks: compromise owners of coins with high coin-age
¡ñ Miners may not bother to mine with low coin-age
Pure proof of stake: elect a random committee
Epoch 2 Epoch 3
Pseudorandom committee selection
Next committee: E, A, C
Pseudorandom committee selection
Next committee: D, B, E
Within each epoch, run like Nakamoto consensus
¡ñ Each committee member has a designated slot to pick a block
¡ñ Ignore absent, late, or invalid blocks
¡ñ Other options are possible as well
¡ð Run a BFT protocol between committee members
Committee selection must be carefully designed
¡ñ Grinding attack: committee members try to pick blocks to bias next committee
¡ñ Adaptive attack: try to subvert committee member when announced
¡ñ Committee size should ensure honest majority
¡ð Too small: might randomly pick a malicious committee
¡ð Too large: easier for adaptive attacker
Algorand: avoiding adaptive attack completely ¡ñ Cryptographic sortition: committee selection is private
Essential building block: verifiable random function (VRF)
¡ñ GenKey() ¡ú key pair Kpriv, Kpub
¡ñ Eval(input x, private key Kpriv) ¡ú output y, proof ¦Ð
¡ñ Verify(Kpub, x, y, ¦Ð) ¡ú Yes/No
Just like a signature, but:
¡ñ Output is uniformly distributed
¡ñ Output is unique
Algorand: avoiding adaptive attack completely
I propose block bn! My VRF output is yi and the proof is ¦Ði
I propose block b¡¯n! My VRF output is yj and the proof is ¦Ðj
Step 1: Each participant i computes yi = VRF(bn-1|| ¡°propose¡±, Kpriv) if yi / wi < threshold, propose a block for the round
Algorand: avoiding adaptive attack completely
I propose block bn!
Confirm block b¡¯n
I propose block b¡¯n!
Confirm block bn
Step 2: Each participant i computes yi = VRF(bn-1|| ¡°confirm¡±, Kpriv)
if yi / wi < threshold, sign to confirm the highest-priority valid proposed block
Algorand: avoiding adaptive attack completely
¡ñ Design principle: You only speak once (YOSO)
¡ð Participants only broadcast one message if selected to a ¡°committee¡±
¡ñ VRF keys are replaceable
¡ñ Erasures model: erase your private key before broadcasting
¡ñ Adaptive attacker doesn¡¯t learn who to corrupt until it is too late!
Delegated proof-of-stake
¡ñ Most deployments support delegating stake
¡ð Equivalent to joining a mining pool
¡ð Built-in to new protocols
¡ñ Staking pool participates with weight of all delegated stake
¡ñ Enables all participants to earn staking rewards
Proof-of-stake attacks
Proof-of-stake is subject to many new attacks
¡ñ Adaptive attacks - target future committee members ¡ð Some protocols prevent
¡ñ Grinding attacks - try to influence future committees
¡ñ Nothing-at-stake - can cheaply attempt attacks
¡ñ Long-range attacks - can compromise old committee members
¡ñ Economic attacks
Grinding attacks are usually addressed with combinatorics Suppose:
¡ñ there are N committee members
¡ñ we can tolerate up to f corrupt ones
¡ñ a fraction h of all users are honest
The prob. of a random committee having at least f corrupt nodes is a binomial ¡ñ Larger committees are more secure
Grinding attacks are usually addressed with combinatorics
Nothing-at-stake problem: attacks are ¡°costless¡±
Proposed solution: slashing
Participants penalized for voting in losing chain
Attacker (and others) can continue this chain cheaply
Attack attempt
Long-range attacks (post hoc compromise)
Old stakeholders (no longer participating)
Main chain
Attacker can quickly catch up to present time w/compromised stake
Long-range attacks (post hoc compromise)
¡ñ Key observation - old, inactive keys easier to compromise
¡ð Might be sold cheaply
¡ð Might be thrown out on old hard drivs
Countermeasures:
¡ñ Checkpointing- prevent very long forks (semi-centralized)
¡ñ Erasures model-participants delete secrets immediately
Economic attacks
Good news: can¡¯t gain 51% control by creating new capacity (closed system)
Bad news: new avenues to gain control
¡ñ Loan attacks-borrow stake, perform attack, repay worthless stake
¡ñ Race to the door/buy out
Buy-out attacks on proof-of-stake
I will buy 51% stake and destroy this chain
Failure grows more likely
Stakeholders sell off
Race to the door: last 49% left with nothing
Many open questions remain
¡ñ Can proof-of-stake match security of proof-of-work?
¡ð If not, why not?
¡ð Is it less or more decentralized?
¡ñ Which proof-of-X is best?
¡ñ Can it be useful?
¡ñ Outlook: alternatives will coexist for the near future
Many open questions remain
¡ñ Can proof-of-stake match security of proof-of-work?
¡ð If not, why not?
¡ð Is it less or more decentralized?
¡ñ Which proof-of-X is best?
¡ñ Can it be useful?
¡ñ Outlook: alternatives will coexist for the near future
Permissioned protocols
Classic consensus doesn¡¯t apply directly to Bitcoin
¡ñ Set of nodes not fixed or known in advance! ¡ð Anybody can run a node
¡ñ Bitcoin relaxes traditional assumptions
¡ð Probabilistic consensus
¡ð Eventual consensus
¡ð Incentives motivate correct behavior
Some projects relax these assumptions
Permissioned protocols still an active area of research
¡ñ HotStuffBFT
¡ð Originally designed for Libra/Novi. About 15 participants
¡ñ Committee-based protocols
¡ð Select random committee
¡ð Run ¡°smaller¡± protocol¡±
Consensus trilemma
Sublinear communication
Nakamoto, proof-of-stake etc.
Round-robin blockchain?
Adaptively secure
Classic BFT
Deterministic
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com