Week 8 Scaling Throughput and Latency
How to increase the throughput of a PoW longest-chain-win blockchain system?
How to reduce the confirmation latency?
Increasing Throughput
Copyright By PowCoder代写 加微信 powcoder
Performance
Throughput: transaction per second (tx/s) Bitcoin: 7 tx/s
Ethereum: 100 tx/s
Why is throughput so small in Bitcoin?
Throughput
Throughput= ! %𝐵tx/s= “‘( ) %𝐵tx/s “#!$ “# “‘( )$
• β: fraction of adversarial hash power; no control
• h: honest mining rate
• 𝜆: total mining rate; can be controlled by setting mining target easy
• 𝐵: block size; can be controlled by allowing more transaction in a block
• Δ: network delay; proportional to block size 𝐵
• hΔ: “fork rate” limits the throughput.
• Recall the fundamental fault tolerance (i.e., adversarial mining power) is
Scaling throughput
In this lecture, we study 3 efforts to improve throughput The first two are flawed to different levels
And the third scales throughput optimally, where only the network limits the throughput
Idea 1: embrace forking
GHOST: Greedy Heaviest-Observed Sub-Tree
• A modification to the mining rule: no longer mine on the tip of
the longest chain; mine on the tip of the GHOST chain
GHOST chain 1
Longest Chain
Private attack on GHOST
The GHOST chain is harder to displace by a private attack
• Because all the blocks in the sub-tree count; so forking is not wasted
• Hence the mining rate can be increased without worrying about forking
Private blocks
1 GHOST Chain 1
Longest chain
GHOST is secure?
The intuition behind GHOST refers to resistance to the private attack
We already know that the private attack was the worst case attack for the longest chain protocol
However, the worst case attack for GHOST could be different
Balance attack on GHOST
• The idea is to have two chains and honest mining is split between them
• The adversary reveals private blocks to keep the weights of two sub-trees
Private block for 24132 balance attack
Tip GHOST Chain1
GHOST chain 2 1
Balance attack on GHOST
• Balance attack is a bit more subtle than private attack in the sense that more network control is needed
• Safety attack: because the ledger swings wildly between two sub-trees
• Security threshold: essentially back to the Bitcoin level
• This limits throughput
Idea2: reduce forking
Longest chain rule: miner proposes only one block for a successful nonce Idea: why not do many blocks for one mining?
How is this different from a large block size?
• Consist of proposer blocks and transaction blocks
• Only mine the proposer block at the tip of the longest chain
• The same proposer signs transaction blocks
• K-deep rule: PoW blocks
• PoW difficulty level same as
Bitcoin: same security
• Tx blocks contain payload;
generation rate is not limited
by PoW (security)
• Ledger creation: pull in all Tx
blocks into parent PoW block
• Positive: Throughput is high because Tx blocks are many in number and only limited by network capacity
• Negative: Bitcoin-NG is permissionless but does not have the full security of longest chain protocol
• Predictability
Bribing attack on
On longest chain protocol:
a) There is unpredictability on who successfully mines
b) After mining, the block is sealed by the nonce and cannot be
Putting a) & b), Bitcoin is very resistant to bribing attacks
But in Bitcoin-NG, a) & b) are true only for PoW blocks, but not true for Tx blocks
Bribing attack on
• But in Bitcoin-NG, a) & b) are true only for PoW blocks, but not true for Tx blocks
• So Tx blocks are vulnerable to bribing attacks
• Slow-down attack
• Not a security attack
Idea 3: Prism 1.0 or
Bitcoin-NG is a good idea: it separated security from payload/data Prism 1.0 is similar to Bitcoin-NG
• Consist of proposer blocks and transaction blocks
Transaction blocks are not linked but referred by proposer blocks The PoW for transaction blocks is easy for throughput
The PoW for proposer blocks is hard for security
Fruitchains
Conclusion
Bitcoin throughput is limited by mining rate which is limited by security GHOST is a different fork choice rule
• More secure against private attack but vulnerable to balance attacks
Fruitchains achieves optimal throughput
• Other graph based schemes, each vulnerable to security attacks
Scaling Bitcoin
• ScalingBitcoin(lecture8-14)
• L1Scaling:ImproveBitcoinperformancewhilestillretainbasic
structure of the longest chain protocol • Throughput
• Storage & compute — Sharding
• Energy (#11) – Proof of Stake
• L2 Scaling: Improve performance via an “overlay” on Bitcoin
• Payment Channels
Bitcoin latency
Time from when a transaction was broadcast until the transaction is confirmed in the ledger
• 𝜏”: Time from when a transaction was broadcast until the transaction is
put into a mined block B
• 𝜏5: Time from when the transaction was put into a mined block B until
block B is 𝑘-deep in the longest chain
𝜏 = 𝜏” + 𝜏5
𝜏5 is the real bottleneck, depends on how large 𝑘 is.
Bitcoin latency
Assume low forking (𝜆Δ ≪ 1), 𝑘
From Lecture 6, error probability
Depth of blocks
1𝑐 l o g ( 1𝜖 ) 1
𝜏= 1−𝛽 𝜆=𝑂(𝜆log(𝜖))
Block arrival rate
Bitcoin latency
𝜏 = 𝑂 ( 1𝜆 l o g ( 1𝜖 ) ) Bitcoin: )” = 10 minutes
Improve Bitcoin latency
Only way to improve latency is to
• reduce 𝑘; but this reduces security
• Increase 𝜆; but this also reduces security
Ethereum: )” = 15s; 𝑘 = 100
• latency = 25 minutes
• Way better than Bitcoin performance; improvement simply by
picking better parameters.
Improve Bitcoin latency
Question: can we make relatively small changes to the longest chain protocol and PoW mining while scaling latency?
Key Requirements:
• Do not want latency to depend on security level
• Decouple security from latency
Prism achieves optimal latency
• Decoupling principle: separate performance from security
• Prism 1.0 achieves optimal throughput; last lecture
Decoupling voting
k-deep confirmation rule is a form of voting
Satoshi’s Table
1 deep => .45
25 deep => 0.0006
Can think of one block = one vote underneath B
k-deep = k votes in sequence
Really need k large to sample the miners
Bitcoin à Deconstruct Proposing
Ledger construction
1. Select votes along longest voter chain 2. Order the proposer blocks by votes
Bitcoin à Deconstruct àPrism
Fast Confirmation
Deconstruct
Proposing votes
: For each level choose the proposer block with maximum votes
…. …. …. ….
Many voter chains
Proposal rule: longest chain Voting rule:
a) each voter chain votes for one and only one proposer block at each level
b) each voter block votes for all the proposer levels that have not been voted
by its parent.
Mining rule: honest miner picks to be proposer/voter/transaction block at random
Cryptographic sortition
How do you prevent adversary from m focusing its mining power on a specific type of blocks or on a specific voter chain?
Fast confirmation
1000 votes
1000 Voter Trees
0.45 0.45 0.45 0.45
Pr(>500 votes reverted) < 0.0006
bag of weak classifiers => strong classifier
1 deep => .45 A 25 deep => 0.0006
1-deep 0.45
: For each level choose the proposer block with maximum votes
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com