Lecture 11
Performance & Scalability, continued
Recap: Many performance goals for cryptocurrencies
Copyright By PowCoder代写 加微信 powcoder
● Throughput: transactions per unit time ○ Typically tps (transactions per second)
● Latency: time to confirm transactions
○ A distribution, never just one number. Often median is reported
● Expressiveness: Complexity of transactions/contracts supported ○ No simple measure
● Cost: Transaction fees which go to miners
Existing performance doesn’t get us nearly far enough
metro (Octopus card): 170 tps, over 20x Bitcoin!
Scalability is not the same as performance
● Performance: how much the system can do
● Scalability: ability to increase performance by adding resources
The ideal is usually linear scaling: double resources, double performance
Horizontal scaling vs. Vertical scaling
Vertical scaling or “scaling up”
Building a faster monolithic system
Horizontal scaling or “scaling out”
Building a more parallel system
Horizontal scaling
Why not just use many different blockchains?
● Some might be optimized for specific tasks or communities
● Robustness from multiple independent projects
● Atomic cross-chain swaps enable inter-chain commerce
Multiple blockchains impose transaction costs
● Need to find trade partner ○ Need liquidity
● May need to pay fees
Decentralized finance
aims to improve this A key goal of Bitcoin originally was to reduce currency exchange headaches
Multiple blockchains introduce exchange rate risk
Recall: Sidechains enable trading w/fixed two-way peg Main chain
X Maincoins escrowed
X Maincoins released
Y Sidecoins created
Y Sidecoins destroyed
Side chain
Exchange rate X:Y is fixed
Challenges to deploying sidechains
● Mainchain needs to verify activity on any sidechain
○ SPV proofs: efficient, but risky
○ Full verification typically to expensive
● Bitcoin is not powerful enough without a hard fork
● Ethereum can verify side chains, though it’s expensive
Many sidechain projects exist, unclear success
● Dedicated “mainchains” designed to facilitate sidechains
● Sidechain projects built off of Ethereum and other smart contract chains
What if we just want N equal “sidechains” working together?
Sharding: Dividing state up into equal, randomly divided pieces
Sharding splits the chain into N shards Shard 1
… Shard N
Validators only keep state for one shard. Factor N scaling!
Sharding splits the chain into N shards Shard 1
… Shard N
Blocks include hash of most recent blocks on all other shards
Cross-shard transactions in two blocks Shard 1
C(1)→ D(1)
A(2)→ B(N)
… Shard N
Inclusion proof of A→B transaction in Shard 2’s state
B(N)→ C(1)
Easiest if all inputs live on the same shard
Multi-shard transactions get complicated Shard 1
Shard 2 Shard N
… Shard N
Multi-shard transactions get complicated Shard 1
Shard 2 Shard N
… Shard N
Need a timeout to avoid freezing funds forever if some inputs fail
2-phase commit is a common (complex) solution
Eth 2.0 plans to introduce sharding
Sharding is promising, but is very complex
● N shards provide N-wise scaling
● If attackers get majority on any shard, can compromise system
○ By design, validators on one shard accept majority decision of other shards
● Validators must be randomly assigned to shards
● Cross-shard transactions have added latency
Off-chain channels
● Uni-directional payment channels
● Bi-directional payment channels
● Multi-hop
● Lightning network
● State channels
Idea: we don’t need to record every transaction
Rai stones used until the 20th century by Yapese Islanders Most debts maintained orally
Heavy rai stones moved only when large debts accumulated
Modern payment networks are similarly hierarchical
Reserve bank
Modern payment networks are similarly hierarchical
Intra-bank transactions not seen by other banks, reserve bank. Bank simply updates balances
Reserve bank
Modern payment networks are similarly hierarchical
Reserve bank
Most payments between users at different banks simply recorded between banks, don’t lead to an actual transfer
Modern payment networks are similarly hierarchical
Banks periodically process settlement transactions, which summarize the net of thousands of smaller transactions
Reserve bank
Cryptocurrency exchanges avoid trading on-chain as well
Trade 1BTC for 12 ETH
Blockchain
BTC Balance
Eth Balance
Fees encourage users to avoid withdrawal
Withdraw 50 ETH
Blockchain
BTC Balance
Eth Balance
Trusting exchanges exposes users to counterparty risk
Can we move most transactions off-chain without counterparty risk?
Uni-directional payment channel Bitcoin
100 coins:
if time() < T1:
multisig(KA,KB) else:
Signed(KA)
42 coins: sig(KA) 58 coins: sig(KB)
Signed(KB)
Signed(KA)
99 coins: sig(K )
One channel-closing transaction A
1 coin : sig(K )
the net of many off-chain transac B Signed(KA)
97 coins: sig(KA) 3 coins: sig(KB)
Signed(KA)
Bob (merchant)
Alice (customer)
42 coins: sig(KA) 58 coins: sig(KB)
Signed(KA)
Alice can recover after T1 if Bob never closes the channel
100 coins:
if time() < T1:
multisig(KA,KB) else:
Signed(KA)
Bitcoin network
100 coins: sig(KA)
Alice (customer)
Bob (merchant)
Signed(KA)
42 coins: sig(KA) 58 coins: sig(KB)
Signed(KA)
No counterparty risk for either party
● Bob can always sign and post the last transaction received (before time T1)
42 coins: sig(KA) 58 coins: sig(KB)
● Alice can recover all of her money at time T1, if Bob never closes
Signed(KA)
100 coins:
if time() < T1:
multisig(KA,KB) else:
Signed(KA)
Payment channels keep most logical payments off-chain ● A logical payment of 4 coins, because Bob’s position has improved by 4:
42 coins: sig(KA) 58 coins: sig(KB)
Signed(KA)
● Only two transactions actually appear on chain (also benefits privacy)
46 coins: sig(KA) 62 coins: sig(KB)
Signed(KA)
42 coins: sig(KA) 58 coins: sig(KB)
Signed(KB)
Signed(KA)
100 coins:
if time() < T1:
multisig(KA,KB) else:
Signed(KA)
Channel closing (normal)
100 coins: sig(KA)
Signed(KA)
Channel opening Channel closing (refund)
Payment channels offer huge scaling in the right situation
● No chain-induced latency (confirmation as fast as sending a network packet)
● Only two transactions actually appear on chain
100 coins:
if time() < T1:
multisig(KA,KB) else:
Signed(KA)
Channel deadline
Channel capacity
● Unlimited payments until channel capacity is spent ○ Larger capacity requires locking up more funds initially
● Channel must be closed by deadline
○ Longer deadline means more lockup if one party goes offline
Simple design doesn’t enable bidirectional payments
100 coins:
if time() < T1:
multisig(KA,KB) else:
Signed(KA)
Bitcoin network
90 coins: sig(KA) 10 coins: sig(KB)
Signed(KA)
Alice (customer)
Bob (merchant)
97 coins: sig(KA) 3 coins: sig(KB)
Signed(KB)
Both parties can close the channel at this point, for different amounts
Bidirectional payments with locktimes (refund transaction)
50 coins: sig(KA) 50 coins: sig(KB)
Signed(KA)
LOCK TIME: T
Signed(KB)
100 coins: multisig(KA,KB)
Signed(KB)
Signed(KA)
Signed(KA)
LOCK TIME: T-1
48 coins: sig(KA) 52 coins: sig(KB)
Alice (customer)
Bob (merchant)
LOCK TIME: T-2
54 coins: sig(KA) 46 coins: sig(KB)
Signed(KB)
Locktimes ensure last transaction can always be confirmed first
Locktime must decrease every time directionality changes
100 coins: multisig(KA,KB)
Signed(KB)
Signed(KA)
Signed(KA)
LOCK TIME: T-1
48 coins: sig(KA) 52 coins: sig(KB)
Signed(KA)
LOCK TIME: T-1
47 coins: sig(KA) 53 coins: sig(KB)
Alice (customer)
Bob (merchan
Arbitrarily many A→B payments
Signed(KA)
LOCK TIME: T-1
34 coins: sig(KA) 66 coins: sig(KB)
LOCK TIME: T-2
54 coins: sig(KA) 46 coins: sig(KB)
Signed(KB)
Optimistically both parties can cooperate to close early
100 coins: multisig(KA,KB)
Signed(KB)
Signed(KA)
Signed(KA)
LOCK TIME: T-1
48 coins: sig(KA) 52 coins: sig(KB)
47 coins: sig(KA) 53 coins: sig(KB)
It’s been great Alice, but I
Signed(K ) LOCK think we should start paying
other people. Please close?
Okay, fine 😢
Alice (customer)
Bob (merchant)
LOCK TIME: T-2
54 coins: sig(KA) 46 coins: sig(KB)
Signed(KB)
54 coins: sig(KA) 46 coins: sig(KB)
Signed(KA)
Signed(KB)
Both parties incentivized to close to get their money back earlier
Channel capacity is now bidirectional (refund transaction)
60 coins: sig(KA) 40 coins: sig(KB)
Signed(KA)
LOCK TIME: T
Signed(KB)
100 coins: multisig(KA,KB)
Signed(KB)
Signed(KA)
This channel starts with a capacity of 40 (to Alice) and 60 (to Bob) Unlimited payments possible, while abs(deficit) < max deficit
Channel must also be closed once Lock Time reaches current time ○ Lock time decreases with every switch in payment direction
Max channel deficit
Initial balances
Choosing locktimes/deadlines is tricky in practice (refund transaction)
60 coins: sig(KA) 40 coins: sig(KB)
Signed(KA)
LOCK TIME: T
Signed(KB)
100 coins: multisig(KA,KB)
Signed(KB)
Signed(KA)
● Need to ensure high probability that lower lock times can be confirmed first ○ Must deal with network latency, congestion
● In practice, lock times decrease by quanta of ~hours
○ Larger quantum means channel must be closed sooner, hurts scaling
● Risk: denial of service to prevent partner from closing channel Alternate approaches exist, including revocation keys
Problem: what if Alice and Bob don’t have a channel?
● Payment channels require at least two transactions
● Not worthwhile if Alice is only going to pay Bob once
○ Or even a small number of times
Can Alice pay Bob through their mutual partner Mitt?
payment channel
payment channel
Simply making two payments introduces counterparty risk I want to pay Bob 10...
payment channel payment channel
30 coins: sig(KM) 20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
50 coins: sig(KA) 50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
40 coins: sig(KA) 60 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
Mitt can steal the payment if Alice pays first
Simply making two payments introduces counterparty risk I want to pay Bob 10...
payment channel payment channel
30 coins: sig(KM) 20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
50 coins: sig(KA) 50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
20 coins: sig(KM) 30 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
Alice can steal the payment if Mitt pays first
“Who goes first” dilemma is similar to that in atomic swaps...
Multi-hop payments with hash-based locking y=H(x) x
payment channel payment channel
30 coins: sig(KM) 20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
50 coins: sig(KA) 50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
10 coins: sig(KB) && (x | H(x)=y) 20 coins: sig(KM)
20 coins: sig(KB)
Signed(KM)
Signed(KB)
LOCK TIME: T2-1
10 coins: sig(KM) && (x | H(x)=y) 40 coins: sig(KA)
50 coins: sig(KM)
Signed(KA)
Signed(KM)
LOCK TIME: T1 -1
Mitt will learn x if Bob posts his transaction, ensuring Mitt is paid
Multi-hop payments: recovery modes y=H(x)
payment channel payment channel
30 coins: sig(KM) 20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
50 coins: sig(KA) 50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
10 coins: sig(KM) && (x | H(x)=y) 40 coins: sig(KA)
50 coins: sig(KM)
Signed(KA)
Signed(KM)
LOCK TIME: T1 -1
Extra timeout needed for this TXO
What if Mitt never pays Bob?
Alice never reveals x. Payment to Mitt times out back to -hop payments: recovery modes y=H(x) What if Alice never reveals x?
payment channel payment channel
30 coins: sig(KM) 20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
50 coins: sig(KA) 50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
10 coins: sig(KB) && (x | H(x)=y) 20 coins: sig(KM)
20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2-1
10 coins: sig(KM) && (x | H(x)=y) 40 coins: sig(KA)
50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1 -1
Neither transaction is signed by Mitt/Bob, never posted
After both transactions post, can regularize the channels
payment channel
payment channel
30 coins: sig(KM) 20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
50 coins: sig(KA) 50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
10 coins: sig(KB) && (x | H(x)=y) 20 coins: sig(KM)
20 coins: sig(KB)
Signed(KM)
Signed(KB)
LOCK TIME: T2-1
10 coins: sig(KM) && (x | H(x)=y) 40 coins: sig(KA)
50 coins: sig(KM)
Signed(KA)
Signed(KM)
LOCK TIME: T1 -1
After both transactions post, can regularize the channels y=H(x) x
payment channel payment channel
30 coins: sig(KM) 20 coins: sig(KB)
Signed(KM)
LOCK TIME: T2
Signed(KB)
50 coins: sig(KA) 50 coins: sig(KM)
Signed(KA)
LOCK TIME: T1
Signed(KM)
20 coins: sig(KM) 30 coins: sig(KB)
Signed(KM)
LOCK TIME: T2-1
Signed(KB)
40 coins: sig(KA) 60 coins: sig(KM)
Signed(KA)
LOCK TIME: T1 -1
Signed(KM)
End result: logical payment of 10 coins from Alice to -based locking works for arbitrary number of hops! y=H(x) x
● Latency is still only limited by network speed
● At each hop, payment is assured if next party pays using x
● Complexity: need to ensure lock times are in increasing order
○ Otherwise next participant could pay after previous channel closed
○ Revocation keys more commonly used
Payment-channel networks
● Network of users connected by payment channels of different capacities
● Can pay any other user if a path exists of sufficient capacity (or multiple paths)
Design challenges with payment channel networks
● Network topology
○ How should users choose whom to peer with?
○ How should capacity be distributed?
○ What’s the most efficient path from A to B?
○ Where is routing info stored?
○ Connecting nodes (hubs) will want fees
○ Compensate for tying up capital
○ How much do payment hubs learn?
Re-centralization is a natural trend
● Hub-and-spoke model is the most efficient and simple (worst case: star network)
● Hubs could be a risk to privacy, censorship
Lightning network is deployed and running for Bitcoin
https://lnrouter.app/graph
● Thousands of nodes connected
Lightning network is deployed and running for Bitcoin
https://1ml.com/
● Currently only a small fraction of BTC transaction volume...
Raiden (Ethereum Lightning network) is fledgling
https://explorer.raiden.network/
Many extensions to payment channels
● Virtual channels
○ Alice, Bob can make multiple payments with only one interaction with Mitt
● Private channels
○ Amounts are hidden from public view
● State channels
○ Support smart contracts
Tic-Tac-Toe on the blockchain: classic implementation
Smart contract
contract TicTacToe{
function join()
function move()
Every moved posted, verified on-chain
Tic-Tac-Toe: a state-channel implementation Smart contract
join(), $, KB
● Further optimization: Alice can just send an “I lost” message Signed(KA)
join(), $, KA
Signed(KA)
● Alice’s signature asserts she approves of all prior moves
Signed(KA)
Signed(KB)
Signed(KA)
● Contract only verifies last move in the game
Signed(K ) B
State channels must recover if a player stops responding Smart contract
join(), $, KA
join(), $, KB
Signed(KB)
Signed(KA)
Signed(KB)
Alice stops sending
Signed(KA)
Can’t yet award game to Bob: he might be faking
1. Alice can respond on-chain with her next move. Continue normally
2. If Alice doesn’t respond on chain, Bob wins by default
State channels offer huge improvement in right situation
● Multi-party, turn-based protocols
● Need to deal with timeouts/network problems
○ Worst-case scenario: malicious user can force every move to run on-chain
Challenges:
○ Asynchronous protocols (e.g. multi-party auctions)
○ Randomness (e.g. playing Monopoly)
○ Private state (e.g. playing Poker)
Holy grail: general compiler from Ethereum contracts into state channels
● Optimistic
● Zero-Knowledge
Payment channel networks tend towards centralization
Payment channel networks tend towards centralization
Rollups: an efficient implementation of centralized payment network
Rollup servers process transactions, maintain account state Smart contract
Rollup server
contract Rollup{
mapping(uint ->
bytes32) states;
mapping(uint ->
bytes32) txs;
function update(
bytes32 newState,
bytes32 newTxs)
67691979593
3220105979
Signed(KB)
State commitment
Tx commitment
Rollup server commits to account state and txs in each epoch
42→KB (3) Signed(KA) receipt
108→KA (4) Signed(Kc) receipt
Users can withdraw their account balance on-chain
Smart contract
Rollup server
contract Rollup{
mapping(address->uint)
withdrawable;
withdraw() {
Withdraw update
withdraw()
withdraw (5) Signed(Kc)
Question: what if the rollup server tries to cheat? Rollup server
Where did my 😈 money go??
State commitment
Smart contract
contract Rollup{
mapping(address->uint)
withdrawable;
withdraw() {
Need a way to prevent a malicious server from stealing
Optimistic rollup servers use fraud proofs to catch cheating
The server cheated me (KB) between epochs 6 and 7
Smart contract
I can prove Bob’s balance is right: Balance at epoch 6: 456
Balance at epoch 7: 431
Tx: 16→KC (5)
Tx: 9→KA (6)
contract Rollup{
The server ignored a tx in Epoch 7: Tx: 12→KB (5)
Signatures
As long as one party is honest, they can prove it to the contract
Optimistic servers use fraud proofs, many tricky details ● Need a waiting period before withdrawing funds
○ Time for users to notice fraud, initiate fraud proof protocol
● Users need to monitor the chain constantly
○ Or pay a “watchtower” service
● Multiple rounds, multiple deadlines
○ Need to ensure both parties can provide evidence
● Fraud proofs complicated, costly in gas
○ Ideally, never need to actually be run!
Recall: Verifiable computation for any NP statement program f
statement s: f(x) = y proof π
ZK-rollup servers provide proof of correct updates
Smart contract
Rollup server
contract Rollup{
mapping(uint -> bytes32) states;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com