Blockchain Scaling
...in the CBC Casper Framework
A talk by Vlad Zamfir
EthCC 2019
Outline
Primer: Consensus Protocols
Primer: Consensus Protocols
Consensus protocols are all about…
... making consistent decisions in a distributed system�
Normally we want:
And there are some other things we may want (e.g. non-triviality, validity)
Primer: What are decisions?
Consensus protocols decide on either:
Examples:
�They are usually taken to be “output” or “committed” by the nodes in the protocol
Primer: What are consistent decisions?
Decisions on values are consistent if they are the same values
Decisions on predicates or properties of values are consistent if there are values that jointly satisfy the predicates
Primer: Consensus Protocols
Consensus protocols are all about distributed systems making consistent decisions about a predefined domain of consensus values
Primer: Sharding
Primer: Sharding
Primer: Sharding
Sharding is all about…
...splitting up work in a distributed system in order to scale its capacity
Primer: Sharding
Sharding came from
“Computer Corporation of America's [1988] "A System for Highly Available Replicated Data"”
Or
“the critically acclaimed 1997 MMORPG video game Ultima Online”
Primer: Sharding
“Sharded” means …
…has more than one component
Primer: Sharding
�Ergo...
A bit is not sharded
Primer: Sharding
�Ergo...
A binary consensus protocol is not sharded
Sharded Consensus Protocols, in Theory
Sharded Consensus Protocols, in Theory
As we just learned...
...there cannot be a sharded binary consensus protocol.
Sharded Consensus Protocols, in Theory
The takeaway is:
To shard consensus, we need sharded consensus values!
Decisions in Sharded Consensus Protocols
Decisions in Sharded Consensus Protocols
Remember:
Decisions are on consensus values or their predicates
Decisions in Sharded Consensus Protocols
Because the goal of sharding is to scale the throughput of the consensus protocol…
… we want to assume that nodes make decisions on predicates that describe some but not all of the “shards” of the consensus value.
Decisions in Sharded Consensus Protocols
These decisions are consistent if…�
… there is a (sharded) consensus value that � jointly satisfies all of their decisions
Sharding Clients as Light Clients
Sharding Clients as Light Clients
We will imagine that…�
… sharding clients are light clients
Sharding Clients as Light Clients
There are two kinds of light clients:
Sharding Clients as Light Clients
“Consensus value” light clients are all about…�
...Using the commitments of (crypto) proof systems as consensus values
Commitments (like merkle root hashes) can allow for the verification of (cryptographic) proofs of predicates of “full” consensus values
Sharding Clients as Light Clients
“Consensus value” light client examples:
Sharding Clients as Light Clients
“Protocol message” light clients are all about…
… only receiving the messages that are relevant to their interests
Imagine that clients interested in a decision only need to receive protocol messages that are relevant to that decision, in some sense.
Sharding Clients as Light Clients
“Protocol message” light client examples:
Sharded (Blockchain) Consensus Values
Sharded (Blockchain) Consensus Values
We begin by specifying sharded consensus values…
… a blockchain for every shard
… sent and received message queues between neighbor shards
… so that shards can represent “threads” of communicating EVM executions
Sharded (Blockchain) Consensus Values
A block has:
A shard ID, out of a set of shard names
Sharded (Blockchain) Consensus Values
A block has:
A previous block (with the same shard ID)
Or it’s a genesis block (which have no prev blocks)
Sharded (Blockchain) Consensus Values
A block has:
A transaction list and an EVM “Post” State
Or it’s a genesis block (which have no tx lists)
Sharded (Blockchain) Consensus Values
A block has:
A source block for each of its neighbor shards
This is where incoming XShard messages will be drawn
Sharded (Blockchain) Consensus Values
A block has:
A list of sent messages for each of its neighbors
Sharded (Blockchain) Consensus Values
A block has:
A list of received messages for each of its neighbors
Sharded (Blockchain) Consensus Values
A cross-shard message has:
A message payload
(can think of this as call data, gaslimit, eth balance)
Sharded (Blockchain) Consensus Values
A cross-shard message has:
A Time To Live (TTL)
Which is used to identify when messages cannot be received, and to force messages to be received by expiry
Sharded (Blockchain) Consensus Values
A cross-shard message has:
A “base” or “target” block
(The block from which cross-shard messages must be received by the TTL)
Sharded (Blockchain) Consensus Values
In summary, a Block has:
Sharded (Blockchain) Consensus Values
And a cross-shard message has:
Sharded (Blockchain) Consensus Values
BUT
We have a bunch of additional constraints on the definition of blocks, to guarantee that from the point of view of any block, “things have gone well”
Validity Condition: Monotonic Sources
VS
Validity Condition: Receive Messaged by Expiry
�
VS
Validity Condition: Source-Source Consistency
�
Sharded (Blockchain) Consensus Values
Blocks on the same shard are inconsistent when they aren’t in the same blockchain�
Sharded (Blockchain) Consensus Values
��Blocks on different shards are inconsistent when they either disagree with the others’ sources or fail to receive each others’ messages by expiry.
Sharded (Blockchain) Consensus Values
�
A “decision on a block” represents a decision on a property of the consensus values, which are a collection that includes a blockchain for every shard
Sharded (Blockchain) Consensus Values
�
A “decision on a block” represents a decision that a block will be part of the multi-threaded execution of the EVM (with communiation)
Sharded (Blockchain) �CBC Casper Consensus Client
Sharded (Blockchain) �CBC Casper Consensus Client
Recall that to achieve scalability we need to have light clients
And there are two kinds of light clients:
Sharded (Blockchain) �CBC Casper Consensus Client
To use consensus value light clients, we will redefine our consensus values to use hashes instead of nesting
Sharded (Blockchain) �CBC Casper Consensus Client
A (new, light client friendly) block (header) has:
Sharded (Blockchain) �CBC Casper Consensus Client
A (new, light client friendly) cross-shard message has:
Sharded (Blockchain) �CBC Casper Consensus Client
To use consensus protocol message light clients, we will need to modify our Minimal CBC Casper specification
Sharded (Blockchain) �CBC Casper Consensus Client
The “Minimal” CBC Casper spec describes “full node” consensus protocols:��If you have a message in your protocol state, then you must also have the messages in its justification in your state
Sharded (Blockchain) �CBC Casper Consensus Client
�In a “Light Client” CBC Casper spec, we will need to allow nodes to selectively download the messages in the justifications of protocol messages.
Sharded (Blockchain) �CBC Casper Consensus Client
�In a “Light Client” CBC Casper spec, we need to replace message nesting with reference by cryptographic hash,���as we just did for our sharded (blockchain) consensus values
Sharded (Blockchain) �CBC Casper Consensus Client
�But in a “Light Client” CBC Casper spec, we still need to satisfy the same proof of consensus safety.
Sharded (Blockchain) �CBC Casper Consensus Client
The consensus safety result relies on the following theorem:
�If there are less than t (weighted) equivocation faults observable in the union of nodes’ protocol states, then they have a common future protocol state.
Sharded (Blockchain) �CBC Casper Consensus Client
Recall that in CBC Casper, protocol states are sets of messages, and the state transition corresponds to receiving messages (superset)
Sharded (Blockchain) �CBC Casper Consensus Client
Recall that, in the CBC Casper full node specification,
two distinct messages from the same validator are an equivocation if they do not include one another in their justification
Sharded (Blockchain) �CBC Casper Consensus Client
Sharded (Blockchain) �CBC Casper Consensus Client
Now, in the light client spec, we must modify the definition:
two distinct messages from the same validator are an equivocation if they do not include one another’s hash in their justification
Sharded (Blockchain) �CBC Casper Consensus Client
Sharded (Blockchain) �CBC Casper Consensus Client
Sharded (Blockchain) �CBC Casper Consensus Client
Now, in the light client spec, we are able to detect the weight of equivocation faults from a protocol state (which is now allowed to be any* set of consensus protocol messages).
Sharded (Blockchain) �CBC Casper Consensus Client
Now, in the light client spec, we can restrict protocol states to only exhibit not more than t weight of equivocation faults.
As we do in the full node CBC Casper protocol
Sharded (Blockchain) �CBC Casper Consensus Client
Now, we can show that �
if light nodes have not more than t weight of equivocation faults in the union of their states, they have a common future state (witness: the union itself)
Sharded (Blockchain) �CBC Casper Consensus Client
Furthermore, if the client do not have a common future state, then it must be that the union of their states exhibit more than t weight of equivocation faults.
Sharded (Blockchain) �CBC Casper Consensus Client
After establishing that nodes have a common future state if there aren’t too many faults, the consensus safety result describes decisions on properties of consensus values
Sharded (Blockchain) �CBC Casper Consensus Client
The decisions on properties of the consensus are defined by the “estimator”, something that takes a slightly more generic role than the traditional fork choice rule.
Sharded (Blockchain) �CBC Casper Consensus Client
The estimator maps protocol states to the possible “valid” choices of consensus values that a consensus client can “estimate” from that state
Sharded (Blockchain) �CBC Casper Consensus Client
A property of consensus values is called decided if for all future protocol states, the estimator only returns values that satisfy this property.
Sharded (Blockchain) �CBC Casper Consensus Client
�Decisions between nodes are thereby guaranteed to be consistent if they have a common future protocol state�
Which is guaranteed if the union of their states does not exhibit too many equivocation faults!
Sharded (Blockchain) Fork Choice Rule
Sharded (Blockchain) Fork Choice rule
The role of the fork choice rule is to map protocol states to choices of consensus values.
In our context, our consensus values are blocks from the sharded blockchain, and our protocol states are the CBC Casper light client states just described
Sharded (Blockchain) Fork Choice rule
���For clients to make decisions, they must be able to understand which consensus messages they need to see.
Sharded (Blockchain) Fork Choice rule
�
We will therefore structure the fork choice rule in order to create a clear connection between decisions and subsets of the validator set that are responsible for that decision.
Sharded (Blockchain) Fork Choice rule
We will assign different (mutually exclusive) subsets of the validator set to each shard.
This way clients know which validators are on what shards.
Sharded (Blockchain) Fork Choice rule
And we will insist that shard “neighbors” are of one of two types:
And that every shard has at most one parent, and that only one shard has no parents. Setting up a tree structure
Sharded (Blockchain) Fork Choice rule
���Furthermore, we will make the fork choice rule of a shard independent of the fork choice rule of its children.
Sharded (Blockchain) Fork Choice rule
This tree structure achieves a few important things:
Sharded (Blockchain) Fork Choice rule
��Recall that blocks on different shards are inconsistent when they either disagree with each others’ sources or fail to receive each others’ messages by expiry
Which is why the “non-independence” property is critical
Sharded (Blockchain) Fork Choice rule
�We will now give a concrete example of a sharded fork choice rule that fits these constraints and guarantees that cross-shard communication atomicity won’t fail.
�
Sharded (Blockchain) Fork Choice rule
The root shard executes latest message driven GHOST completely independently of any other shards�
Sharded (Blockchain) Fork Choice rule
�
All other shards execute the latest message driven GHOST fork choice rule, while additionally orphaning any blocks that fail to synchronize with the parent shard.��There are four such “filter conditions”
Sharded Fork Choice Filter condition: �Child block out of synch with parent source
Sharded Fork Choice Filter condition: �Child source out of synch with parent fork choice
Sharded Fork Choice Filter condition: �Child block failed to receive message by expiry
Sharded Fork Choice Filter condition: �Child block sent message not received by expiry
Sharded (Blockchain) Fork Choice rule
�Claim: ��This fork choice rule guarantees that cross-shard atomicity failure cannot be violated, because such violations will be orphaned by the fork choice of the child shard.
Sharded (Blockchain) Fork Choice rule
Claim:�
CBC Casper light clients for this sharded blockchain protocol will not make inconsistent cross-shard decisions (if there aren’t too many faults)
Sharded (Blockchain) Fork Choice rule
Claim:�
CBC Casper light clients can determine which validators they must hear from to make decisions on a given shard, and they don’t need to hear from all validators (at least if any shard has more than one child)
Sharded (Blockchain) Fork Choice rule
Claim:�
CBC Casper light clients deciding on blocks in the described domain of sharded consensus values implement a scalable (blockchain) consensus protocol.
Other Relevant Work, Future Directions
Other Relevant Work, Future Directions
Conclusion
Conclusion
Takeaways:
CBC Casper Workshop
Title: “Safety & Liveness in CBC Casper”
Presenter: Aditya Asgaonkar
Time: 16:45, Day 1
Location: Jean Fourastié
Q&A
Thanks for listening!
Thanks for having me!
Please reach out,
contribute!