Lecture 10
Performance & Scalability
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
Scalability is not the same as performance
● Performance: how much the system can do
“Bag of tricks” ideas that can usually only be done once
● Scalability: ability to increase performance by adding resources Repeatable tricks that can be played as often as needed
The ideal is usually linear scaling: double resources, double performance
Scalability is not the same as performance
Performant but not scalable: Low-performance but scalable:
Finding truffles with hogs Growing tomatoes in a greenhouse
Limits in Bitcoin
Bitcoin performance is limited by several constraints
● Blocksize: 1MB
● Block frequency: 10 minutes
This gives 1.75 kB/s of space in the blockchain to represent transactions
Blockchain is large, but sustainable with Moore’s law
Joining the network is also very expensive
Typical synch. times: 1-5 days
How many transactions can fit in limited space? Critical information: public keys, signatures, output values
P2PKH outputs: ~25 bytes P2PKH inputs: ~107 bytes
Median tx size: ~275 bytes Mean tx size: ~566 bytes
Larger transaction types: MULTISIG, non-standard scripts
Bitcoin throughput varies between 3-8 tps
Bitcoin throughput is far behind that in centralized systems
Average: Peak: Claimed:
1,700 tps 25,000 tps 65,000 tps
Throughput requirements for a truly global system? 1 transaction/person/day:
10 transactions/person/day:
~1 million tps
~8 billion people
Bitcoin has a very long way to go
metro (Octopus card): 170 tps, over 20x Bitcoin!
Cash is the only system that meets global demand today
Important goal for global equity:
serving billions who lack access to today’s financial services
Latency in Bitcoin is also far too slow for retail use
(1 confirmation)
Fees are also an order of magnitude above payment cards
1-3%, min. ~$0.10
Improving latency ● Green addresses
● BlockDAGs
● Hybrid consensus
○ Bitcoin-NG and ByzCoin
Latency in Bitcoin is also far too slow for retail use
“0-conf” transactions are “accepted” right away
Bitcoin network
It’s in the mempool, it’ll probably get confirmed…
“0-conf” transactions are risky, but still used
● Network provides no guarantees of acceptance
● In practice, high probability
● Can be combined with fraud analytics, like with payment cards
Bitcoin nodes take some steps to help:
● Conflicting transactions not stored, relayed or mined ○ Even for a higher fee!
● Led to the “child pays for parent” strategy to advance stuck transactions
Green addresses: promising not to double-spend
Bitcoin network
A, C,… A→B
A is on my green address list… they won’t double-spend
Green addresses never widely took off ● Requires a trustworthy, up-to-date list of addresses
Idea: enforce with a smart contract
● Establish a fidelity bond in an Ethereum smart contract
● If any address registered double spends, burn the bond
Stepping back: why 10 minutes between blocks?
Source: and : “Accelerating Bitcoin’s Transaction Processing” 2014
Higher frequency → more collisions, which harms security Public chain, high frequency: length 9, 18 blocks
Private chain, high frequency: length 9, 9 blocks
Bitcoin’s block frequency is extremely conservative
● Propagation time is now quite fast, especially between large miners
● Less than 1 stale block per day (< 0.1%)
Bitcoin could easily cut latency by 10x with a simple parameter change Downside: 10x more blockheaders for light clients to store
Handling higher block frequency securely: GHOST Idea: Blocks point to one parent block and one or more “uncle” blocks
● Aggregate chain length includes uncle blocks-no security loss to private chains
● Uncle blocks receive partial rewards-more fair to smaller miners
● Transactions included in uncle blocks are ignored completely
Ethereum uses a GHOST variant, enabling higher frequency
Taking the idea one step further: General BlockDAGs
● No single “canonical” chain. Transactions can appear anywhere
● Complex rules for assigning priority between conflicting transactions
● Many variants, widely implemented: GHOST, Spectre, Chainweb, Hashgraph,
Avalanche, IOTA, DLattice, Tangle, Conflux, BlockClique...
New leader: A
New leader: B
New leader: C
New leader: D
Another approach to faster blockchains: hybrid protocols Idea: Bitcoin-NG
● Use proof-of-work to choose a new leader rarely
● Leader produces microblocks quickly until a new leader is found (signed only)
Key blocks (with PoW)
Microblocks (signed only)
Bitcoin-NG can provide arbitrarily fast microblock times, but
● Challenge #1: More microblocks = more overhead (signatures)
● Challenge #2: Careful incentives split fees between key block finders
● Challenge #3: How much confirmation does a microblock really give you?
Arbitrary hybrid consensus: Byzcoin (4-of-5 shown here)
PoW blocks for committee i
PoW blocks for committee i + 1
Microblocks signed by committee i-1 Microblocks signed by committee i
Arbitrary hybrid consensus
● PoW blocks used to elect a committee of size N
○ After N PoW blocks found, new committee is formed
● Microblocks agreed on by committee running a PBFT protocol ○ Bitcoin-NG is a special case for N=1
● Larger committee=lower probability of a corrupt committee ○ Also more overhead...
Decreasing transaction size
● Address compaction ● SegWit
● Aggregate signatures
What takes up space in a Bitcoin transaction?
"hash":"5a42590fbe0a90ee8e8747244d6c84f0db1a3a24e8f1b95b10c9e050990b8b6b", "ver":1,
"vin_sz":2,
"vout_sz":1,
"lock_time":0,
"size":404,
{ "prev_out":{
"hash":"3be4ac9728a0823cf5e2deb2e86fc0bd2aa503a91d307b42ba76117d79280260",
"scriptSig":"30440..." },
{ "prev_out":{
"hash":"7508e6ab259b4df0fd5147bab0c949d81473db4518f81afc5c3f52f91ff6b34e",
"scriptSig":"3f3a4ce81...." }
], "out":[
"value":"10.12287097",
"scriptPubKey":"OP_DUP OP_HASH160 69e02e18b5705a05dd6b28ed517716c894b3d42e OP_EQUALVERIFY OP_CHECKSIG"
What takes up space in a Bitcoin transaction?
Size (bytes)
Prev transaction pointer
scriptSig (P2PKH)
scriptPubKey
Several avenues to compact transaction sizes
● Nibble around the edges
○ Smaller version numbers
○ Lock time?
● Shrink transaction pointers
● Don’t repeatedly include public keys
Optimization: use serial txids, not transaction hashes
Inputs: f7a1749335a44b21877683ce2eca42ae[0] Outputs: 25.0→ : 7c919bfd4748b656317d26e73d2b779e[0] Outputs: 17.0→Bob, 8.0→ IGNED(Alice)
Inputs: 509e750158a916ea37931c5eb0617b75[0] Outputs: 8.0→Carol, 7.0→ IGNED(Bob)
Inputs: 509e750158a916ea37931c5eb0617b75[1] Outputs: 6.0→David, 2.0→ IGNED(Alice)
Optimization: use serial txids, not transaction hashes
Outputs: 25.0→Alice
Inputs: 1[0]
Outputs: 17.0→Bob, 8.0→ IGNED(Alice)
Inputs: 2[0]
Outputs: 8.0→Carol, 7.0→ IGNED(Bob)
Inputs: 2[1]
Outputs: 6.0→David, 2.0→ IGNED(Alice)
Optimization: use serial txids, not transaction hashes
● How many bytes needed?
○ 83M UTXOs so far
○ 5 bytes would enable 240 transactions-1,000 years at current rates
○ 8-10 bytes likely future-proof
● Total savings: 20-25 bytes per transaction input (perhaps 10%)
● Breaks some existing protocols
○ Txids are now unpredictable for future transactions
Optimization: don’t include public keys repeatedly
Outputs: 25.0→b5f74a496bb30674784c43f96ae0d294
Inputs: 1[0]
Outputs: 17.0→14f9e940a66d81f4e2d0536ab5d07059, 8.0→b5f74a496bb30674784c43f96ae0d294
Inputs: 2[0]
Outputs: 8.0→9e1694ac780a1af856cfc5382a7cdef7, 7.0→14f9e940a66d81f4e2d0536ab5d07059
Inputs: 2[1]
Outputs: 6.0→7202cdbaa85db31cbd24f615e8fc7ca7, 2.0→b5f74a496bb30674784c43f96ae0d294
Optimization: don’t include public keys repeatedly
Inputs: Ø Outputs: 25.0→A
Inputs: 1[0]
Outputs: 17.0→B, 8.0→A
Inputs: 2[0]
Outputs: 8.0→C, 7.0→B
Inputs: 2[1]
Outputs: 6.0→D, 2.0→A
Public key
b5f74a496bb30674784c43f96ae0d294
14f9e940a66d81f4e2d0536ab5d07059
9e1694ac780a1af856cfc5382a7cdef7
7202cdbaa85db31cbd24f615e8fc7ca7
Optimization: don’t include public keys repeatedly
● Similar potential savings to using serial txids
● Account-based ledgers already achieve this
○ Ethereum actually does one better, public keys are never included
○ ECDSA in “ecrecover” mode
● Signatures remain the major use of space
○ By definition, they are unique and cannot be compressed
SegWit: moving signatures out of transactions
"hash":"5a42590fbe0a90ee8e8747244d6c84f0db1a3a24e8f1b95b10c9e050990b8b6b", "ver":1,
"vin_sz":2,
"vout_sz":1,
"lock_time":0,
"size":404,
{ "prev_out":{
"hash":"3be4ac9728a0823cf5e2deb2e86fc0bd2aa503a91d307b42ba76117d79280260",
"scriptSig":"30440..." },
{ "prev_out":{
"hash":"7508e6ab259b4df0fd5147bab0c949d81473db4518f81afc5c3f52f91ff6b34e",
"scriptSig":"3f3a4ce81...." }
], "out":[
"value":"10.12287097",
"scriptPubKey":"OP_DUP OP_HASH160 69e02e18b5705a05dd6b28ed517716c894b3d42e OP_EQUALVERIFY OP_CHECKSIG"
SegWit: moving signatures out of transactions
Outputs: 25.0→Alice
Inputs: 1[0]
Outputs: 17.0→Bob, 8.0→ IGNED(Alice)
Inputs: 2[0]
Outputs: 8.0→Carol, 7.0→ IGNED(Bob)
Inputs: 2[1]
Outputs: 6.0→David, 2.0→ IGNED(Alice)
Witness (scriptSig)
a8b22eb95143e946...
001afa352977f92f...
dd1dd875a9929722...
What does SegWit actually accomplish?
● No savings in total blockchain size
● Transactions smaller (after verification)
● No more transaction malleability, txids known before signing
● SegWit SoftFork (2017) counts Witness data at 1/4... effective 4x increase
○ This was controversial... Arguably just an accounting trick
SegWit transactions are now the majority in Bitcoin
The heavy-duty solution: aggregate signatures
First published in 2003, but little known when Bitcoin was launched
Recap: API for digital signatures
(sk, pk) := GenKey(security λ) σ := Sign(sk, message m) isValid := Verify(pk, m, σ)
Aggregate signatures add two new algs
(sk, pk) := GenKey(security λ) σ := Sign(sk, message m) isValid := Verify(pk, m, σ)
σAgg := Aggregate({σ1, ... σk})
Anybody can aggregate (in any order)
Valid iff all individual sigs are valid
isValid := VerifyAggregate({pk1, ... pkk}, {m1, ... mk}, σAgg)
How is this possible? Intro to BLS signatures
KeyGen() →x, gx (points on an elliptic curve, sometimes written as x, xG)
Sign(x, m) → H(m)x (Hash function must produce pseudrandom curve point)
Verify(y=gx, m, σ=H(m)x) →e(g,σ) ≟ e(gx,H(m))
e() is a bilinear pairing, doing the heavy work here
Bilinear pairings (first discovered by Weil in 1940)
e() : G1 ⨉ G2 → G3 (usually G1=G2) Bilinear property: for all a, b, g∊G1, h∊G2:
e(ga, hb) = e(g, h)ab
Useful corollary: for all x, y ∊G1, h∊G2:
e(xy, g) = e(x, g)·e(y, g)
BLS signature verification is straightforward given a pairing
KeyGen() →x, gx (points on an elliptic curve, sometimes written as x, xG) Sign(x, m) → H(m)x (Hash function must produce pseudorandom curve point) Verify(y=gx, m, σ=H(m)x) → e(g,σ) ≟ e(gx,H(m))
e(g,H(m)x) ≟ e(gx,H(m)) e(g,H(m))x = e(g,H(m))x
BLS Aggregation is very straightforward: multiply!
KeyGen() →{xi, gx_i} Sign(xi, mi) → H(mi)x_i
Product of k signatures
Aggregate({σ1, ... σk}) →σ1 · ... · σk = H(m1)x_1 · ... · H(m2)x_2
Product of k keys Product of k messages
VerifyAggregate({pk1, ... pkk}, {m1, ... mk}, σAgg) =
e(g,σAgg) ≟ e(gx_1 · H(m1)) · ... · e(gx_k · H(mk))
Aggregate signatures can greatly shrink the witness block
Outputs: 25.0→Alice
Inputs: 1[0]
Outputs: 17.0→Bob, 8.0→ IGNED(Alice)
Inputs: 2[0]
Outputs: 8.0→Carol, 7.0→ IGNED(Bob)
Inputs: 2[1]
Outputs: 6.0→David, 2.0→ IGNED(Alice)
Witness (sacgrgirpetgSaigt)e)
ad84b2e229eb849f5a1e4538e3954b6...
001afa352977f92f...
dd1dd875a9929722...
(M(Mineinreprurbelcisehiveess1kasgign. astiugrneast)ure)
Aggregate signatures offer significant space savings
● Only one (short) signature for an entire block
● No savings in verification time
○ Linear in number of aggregated signatures
○ Pairing operation is relatively expensive
● Several blockchains have already deployed this
Decreasing verification time
● MimbleWimble ● FlyClient
● : joining the network is also very expensive
Typical synch. times: 1-5 days
Why is joining the network so expensive?
Why is joining the network so expensive?
Why is joining the network so expensive? (full nodes)
● Data to download: 400 GB
● Signatures to verify: nearly 1.5 billion
● At 15k verifys/sec: 28 hours just for signature verification!
Costs are lower for light/SPV nodes
● Data to download: ~36 MB (750k blocks · 48 bytes)
● Hashes to compute: 750k
● Seconds of computation time to hash. Download time dominates
FlyClient: fast PoW verification for light clients Range: Each block commits to all previous blocks
FlyClient: fast PoW verification for light clients Range: Each block commits to all previous blocks
tx1 tx2 tx3 tx4
FlyClient: fast PoW verification for light clients Range: Each block commits to all previous blocks
tx1 tx2 tx3 tx4
FlyClient: fast PoW verification for light clients Range: Each block commits to all previous blocks
tx1 tx2 tx3 tx4
tx5 tx6 tx7
FlyClient: fast PoW verification for light clients Range: Each block commits to all previous blocks
tx1 tx2 tx3 tx4
tx5 tx6 tx7 tx8
FlyClient: fast PoW verification for light clients
Range: Each block commits to all previous blocks b9
Properties:
Store root of all subtrees of size exactly 2k for some k O(lg n) storage
Adding a new tx block can only add a new singleton or causes a logarithmic number of merges
tx2 tx3 tx4 tx5 tx6 tx7 tx8 tx9
FlyClient: Random sample of old PoW blocks
Random PoW sampling:
Each block includes full path to O(lg n) old blocks Light clients verify only these
tx1 tx2 tx3 tx4 tx5 tx6 tx7 tx8 tx9
FlyClient greatly speeds up light (SPV) clients ● Random sample determined by current block hash
○ A variant of the powerful Fiat-Shamir transformation
● Random audit highly likely to detect any blocks which miss PoW target ○ Sample is biased towards recent nodes (to detect short forks)
● Ethereum light clients, traditional synch.: 4 GB
● Ethereum light clients w/FlyClient: 500 kB
No help with verifying transactions...
MimbleWimble: fast transaction verification
"Mimblewimble, which prevents your opponent from accurately casting their next spell."
( book series)
Recall: Confidential transactions w/Pedersen commitments
K2 gx2hr2 gx4hr4 K4
● x1, x2, ... are the input/output values
● Random blinding factors hr1, hr2 ensure nobody can learn x1, x2, ...
● Additive homomorphism ensures that sum(inputs) = sum(outputs)
MimbleWimble treats blinding factors as secret keys
K3 K2 gx2hr2 gx4hr4 K4
● Need to prove that gx1hr1gx2hr2=gx3hr3gx4hr4he, where e is the excess
● Assuming x1+x2=x3+x4, then e=r1+r2-(r3+r4)
● Can authenticate transaction by proving knowledge of e!
○ Prove knowledge of discrete log of he to the base h
MimbleWimble transactions can be joined easily
Non-interactive join
Essential building block:
● Given two PoKs for excess values he1,he2
● Anybody can multiply them to get a PoK for he1he2=he1+e2
MimbleWimble cut-through: can drop matched input/outputs
Non-interactive join
MimbleWimble can summarize the entire chain to one tx!
Coinbase1 Coinbase2
... Coinbasem
Add new tx
UTXOa UTXOb
UTX Wimble can summarize the entire chain to one tx!
Coinbase1 Coinbase2
... Coinbasem
UTXOk-1 UTXOk
UTXOk+1 UTXOb
UTX Wimble reduces tx verification costs significantly
● Traditional UTXO-based blockchain: O(n) for n total transactions
● MimbleWimble based blockchain: O(m) for m current UTXOs
Currently a 10x speedup
MimbleWimble reduces tx verification costs significantly
● Also naturally supports privacy (Confidential Transactions)
● Downside: payments only. No scripts/multisig
● Downside: range proofs for each input/output. More costly than signatures
● Deployed by Grin
Ultimate fast verification: succinct blockchains Can we efficiently verify both transactions and PoW in a blockchain?
Yes! Using incrementally verifiable computation (IVC) A very powerful crypto trick
Verifiable computation possible for any NP statement program f
statement s: f(x) = y proof π
Untrusted prover
Other verifiers
Blockchain validity is an NP statement
proof π for statement that:
● bi chains back to b0
● all transactions are valid
● chain length is q
● final state is s
prover Problem: very expensive to compute this proof
Recursive proof composition enables efficient updates
Proof πi states that:
● bi chains back to bi-1 with state si and
aggregate work qi
● new transactions ti are valid
● transactions ti change si-1 to si
● nonce n increases qi-1 to qi
● bi-1 has a valid proof πi-1 (or is b0)
Untrusted prover Proving cost now proportional only to # new transactions
must locate any prover who is honest, current
q > q’ (bi’, q’), π’
Forking prover
(bi, q), π
Honest prover
The power of succinct blockchains
Traditional Full Client
Traditional Light Client
Traditional Ultralight client
Succinct chain client
Bandwidth (startup)
Bandwidth (daily)
Trust model
Need connectivity to an honest node
Vulnerable to:
● bad blocks ● SPV
Totally delegated
Need connectivity to an honest node
Succinct blockchains deployed in practice
● Proofs < 1 kB, < 10 ms to verify entire chain history
● Proving time is a challenge, limiting throughput currently
● Full nodes must still maintain entire state
● Mina implements a succinct blockchain w/Proof-of-stake
○ “The world’s lightest blockchain”
Does fast verification matter?
● None of these systems relieve the cost for validators ○ Still need entire current state to validate new transactions
● In practice most clients that care about performance are ultralight ○ Just take the most recent block + state root from a “trusted” source
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com