Taipei Sharding Workshop 2018.03.19-21

​

Proposer/collator separation

Separation of roles

• Proposers propose “collations” (think: shard blocks)
• Collators approve collations and combine them into a chain
• Executors calculate state

Separation of roles

• Proposers are shard-specific
• Collators are randomly shuffled between shards
• Executors are shard-specific (or possibly reshuffled infrequently)

Proposer / collator game, version 1

• Proposers create proposals
• Collator co-signs available proposal with highest fee

Proposer / collator game, version 1

• Proposers create proposals
• Collator co-signs available proposal with highest fee
• Problem: collator can “steal” winning proposal, take txfees for themselves

Proposer / collator game, version 2

• Proposers create proposals, reveal headers only
• Collator pre-co-signs all available proposals, cryptoeconomically commits to not co-signing anything outside the list or expanding the list
• Proposer of winning proposal reveals body
• Collator co-signs

Verifier’s dilemma

Mitigation

• Proposer can challenge collator that included their proposal, or up to 25th-degree descendants
• Challenge = index in collation Merkle tree
• Response = Merkle branch of that piece of data
• If responder can’t answer, deposit transferred to proposer

Fee payment, version 1

• Fee always paid by proposer to collator in the main chain
• Problem: too easily corrupted into a way to bribe collators to extend a non-canonical chain

Fee payment, version 2

• Fee paid only if proposal gets into the canonical chain

Fee payment, version 2

1. Fee always subtracted from on-main-chain proposer deposit
2. Receipt can be included in shard to add to on-collation proposer balance
3. When executing collation in shard, fee transferred from proposer to collator

Taipei Sharding Workshop 2018.03.19-21

​

Execution

Simple (non-scalable) execution

• No cross-shard communication allowed
• Clients can download the canonical chain of any shard, and compute the state themselves

A light client protocol framework, version 1

• Executors can register with deposits
• Executors can make claims of the form “I think the post-state root of block N is H”. Correct claims rewarded, incorrect claims penalized.
• Light clients can download the claims, reason “either the claim is true, or executors burned a lot of money to trick me"

• Problem 1: executors take on chain reversion risk
• Solution: make claims dependent on collation hash

• Problem 2: for light clients, this is still no better than a majority vote
• 51% malicious executors in one shard can trick light clients

A light client protocol framework, version 2

• Idea: similar to interactive verification (Truebit-style)
• If substantial (~10%) disagreement exists, then light clients can isolate the point of disagreement, and execute it themselves
• Secure against up to 90% attacks

A light client protocol framework, version 2

• Claims are dependent on collation hash and previous state root
• Each claim only attests to veracity of state transition of one particular collation

A light client protocol framework, version 2

• If at some link in the chain there’s >10% disagreement, download the full collation, plus witnesses, yourself and execute it yourself

Questions

• How often can executors make claims?
• Option 1: everyone for every collation; overhead too high
• Option 2: randomly sample N executors every collation

Questions

• How do light clients learn about claims?
• Option 1: from peers; but what about eclipse attacks?
• Option 2: from the blockchain; but what about efficiency?
• Require claims to be at start of collation?

• Alternative proposal: disagreements can be published to main chain; run Truebit-like protocol on main chain to determine who’s right
• Difference: is escalation in-consensus or subjective?

Efficiency

• Overhead per shard
• Cost of attacker causing a given amount of computational expense to a node

A light client protocol, version 2

• If at some link in the chain there’s >10% disagreement, download the full collation, plus witnesses, yourself and execute it yourself

Taipei Sharding Workshop 2018.03.19-21

​

Stateless clients

You can verify execution of collations without the state

• State -> state root
• Block -> block + witness
• State transition function -> STF with DB query replaced with Merkle branch query

Uses

• Light clients verifying specific blocks in case of any kind of “alert”
• Executing some forms of cross-shard communication
• Ultra-fast-sync
• Clients with HDDs or serious storage constraints
• VPSes: storage typically expensive, bandwidth typically super-cheap and fast

Stateless client models

• Block producers must be stateful, clients can be stateless
• Everyone can be stateless, except users need to maintain Merkle branches for their accounts

Concrete efficiency

• Length of Merkle branch now: 512 * log₁₆(N) ~= 3840 at N = 1 billion
• Also note: witnesses need to include code, max size 24000 bytes

Concrete efficiency

• EXTCODECOPY: 700 gas
• Data: 24000 bytes + 3840 bytes
• Max witness size: 8000000 / 700 * 27840 ~= 318 MB (!!!)

Can we improve this?

• Lowest hanging fruit: Merkle ASTs
• Charge SLOAD-style fees for accessing specific 32-byte chunks of code
• Now: 700 + 24000 * 200 / 32 = 150700 gas for 28 KB

Can we improve this?

• BALANCE: 400 gas
• Data: 4000 bytes
• SLOAD: 200 gas
• Data: 2560 bytes (assuming 1m storage keys; suppose this is a DOS)
• Max size: 8000000 / 200 * 2560 ~= 102 MB

Can we improve this?

• Next lowest hanging fruit: replace hexary patricia tree with binary
• Add witness compression: if depth N node is (H(x), H(y)), and depth N+1 node is y, then H(y) is redundant info and can be elided

Can we improve this?

• Branch length: 32 * log₂(N) -> 960 at N=10⁹, 640 at N=10⁶
• SLOAD: 8000000 / 200 * 640 = 25.6 MB

Can we improve this?

• Third lowest hanging fruit: charge execution gas directly based on witness length
• State reading costs generally need to be increased

Some practical examples

• Regular transactions
• 380 txs per 8m gas * 2 branch lookups per simple tx
• 380 * 2 * 960 = 729600 bytes
• ERC20 transfers
• 190 txs per 8m gas * 3 branch lookups per simple tx
• 190 * 3 * 960 = 547200 bytes

Witness branch deduplication!

• Regular transactions
• ~550000 bytes
• ERC20 transfers
• ~420000 bytes
• Even more efficiency gains are possible if you are verifying many collations in series

Taipei Sharding Workshop 2018.03.19-21

​

Security models in mechanism design

Security goals: Safety

• Agreement
• If node A sees X as finalized and node B sees Y as finalized, then X and Y cannot conflict
• Validity
• If node A sees X as finalized, then X is valid
• Availability
• If node A sees X as finalized, then X is available

Security goals: Liveness

• Chain growth
• New blocks continue getting finalized
• Non-censorship
• Sufficiently fee-paying transactions are not excluded

Security models: honest majority

• Assume that 50%+ of participants (or possibly more) “follow the protocol” regardless of incentives
• Adversary adaptiveness
• How long ago before the attack must the adversary choose which nodes to “corrupt”?

Security models: uncoordinated majority

• Assume that 50%+ of participants (or possibly more) “follow the protocol” by default, and no more than 50% (or possibly less) are capable of coordinating their actions
• eg. Bitcoin relies on a non-coordination assumption of 23.21% (see optimal selfish mining paper)

Security models: ε-rational majority

• Participants are willing to sacrifice up to ε returns in order to continue following the protocol, but not more

Security models: bribing attacker

• Participants are rational; there is an attacker who is capable of giving bribes to participants if they follow specific strategies
• Parameters: cost, budget
• Similar to maximally adaptive adversary, but strictly stronger, as this is an adaptive adversary that can elicit private information
• For example, Micali’s algorand is secure under adaptive adversary, but NOT bribing attacker!

Security models: coordinated majority

• Some portion p (0.5 < p < 1) of participants are controlled by the same actor, who is economically rational
• Goal is to maximize the cost they pay for breaking network guarantees

Evaluating sharding

• Secure under honest majority with adversaries less adaptive than the lookahead time
• Secure under uncoordinated majority; resistance to bribes similar to main chain assuming in-shard fee payment
• Not secure against bribes
• For that, wait until “tight coupling”