Casper Highway Protocol
In the previous post on Casper CBC, we saw the foundation of a consensus protocol framework of “correct-by-construction” consensus protocols that each shared the same proof of Byzantine-fault-tolerant consensus safety, allowing refinements and improvements without needing to re-prove safety each time. The issue of liveness was not addressed however. The development of the Casper Highway Protocol by CasperLabs provided
- Strong Optimistic Finality
- Flexibility
- Guarantee of liveness
Over the course of this post you will be introduced to these exciting details and of course you can read the original paper here .
Strong Optimistic Finality
Historically, the vast majority of research in the field of consensus protocols has worked under the semi-formal assumption that the existence of more than n/3 dishonest nodes removes the existence of any provable safety guarantee. This is due to a paper written by Dwork, Lynch and Stockmeyer which proved that it is not possible for a partially synchronous protocol to guarantee both liveness and finality if n < 3f + 1, where f is the number of nodes exhibiting Byzantine faults. Put more simply, at least 2/3 of network validators must be honest in order to achieve finality. Despite this result, it is nevertheless possible to provide additional finality guarantees during a period when even dishonest nodes do not deviate from the protocol and actively work to finalize blocks. This means that we can assume, based on the economic incentives, that most of the time almost all the nodes will work honestly to achieve consensus. We are therefore able to optimistically provide much stronger finality guarantees during periods when more than 2/3 of nodes behave honestly.
One practical consequence is that block finality is no longer binary but expressed by a number. Eg if a block reaches finality confidence of 0.8, then at least 80% of the nodes would need to violate the protocol in order to revert the block from the chain.
Flexibility
Having left behind the classical n < 3f + 1 bound, we then find a natural tradeoff between finality and liveness: the stronger finality guarantee we require, the more nodes or validators we need to honestly collaborate to finalize the block with such a guarantee. Requiring all validators to agree on a common finality threshold would solve this but introduce yet another parameter requiring consensus. Instead, Highway does not mandate a common threshold to be agreed upon. Each validator is able to use a different threshold. An important implication here is that validators can play different roles in the network. For example, some validators may deal mainly with finalizing small transactions where small latency is more important than high security, while others can prioritize safety over latency.
Guarantee of Liveness
As mentioned above, Highway provides the first-ever specification for a liveness strategy in the CBC Casper framework. In other words, Highway prescribes a strategy for when participants in the network should create protocol messages and proves that the strategy results in the protocol being live. The guarantee can be proven by structuring the protocol using a DAG (a directed acyclic graph) to capture the existing blockchain, and by showing that certain combinatorial structures – called summits – when found within the DAG can be used to conclude finality of a block.
As a side note: voting in the DAG framework uses the GHOST rule for fork selection and we have already seen this introduced in an earlier post.
Having established this, to prove that summits will appear in the DAG and that adversaries cannot indefinitely prevent any progress from happening, a strategy is required to define how and when validators should produce new units and when to include new blocks in them.
To understand how this works, we can use a simplified model. Time is divided up into rounds; during each round there is a leader who starts the message production. Others wait until they receive the leader’s message, before producing one themselves. Then, near the end of a round everyone sends another message. At each stage another level of agreement is being produced, eventually leading to a summit which can be considered a decision.
However, fixed length rounds are not practical in real systems, so Highway uses dynamic length. To achieve this, we imagine a real life highway. On this highway, movement takes place in the form of hops, while the speed of all cars is constant. In any given lane n a car makes 2^n hops on a distance of one meter. Therefore, if you switch to the lane on your left, you increase the frequency of hopping x2. If you switch to the lane on your right, you decrease the frequency x2. Cars from the lane on your left meet you at every jump you make, and cars on your right meet you only every second hop. These “hops” are ticks, and each “meter” a round passes. Thus, the length of a round depends on what lane you are in.
The idea of using such a creation schedule, coupled with the use of (i) a confidence parameter and (ii) an assumption of the upper limit of crashing (permanently offline) nodes, allows us to prove that after some point in time, for every state reached by any honest validator, finality has been achieved. We can effectively provide a bound of the number of honest validators needed to guarantee that the protocol will continue to finalize blocks within the given confidence threshold.
Other features
A few other interesting featuresare included in the Highway protocol which we will summarise here, though a more in depth look is out of the scope of today’s post
- Spam prevention: the Highway protocol provides protection against
- Vertical Spam – a dishonest validator produces new messages at a fast pace. This is defended against since the correct broadcast frequency of messages is known
- Horizontal Spam – a dishonest validator or group of validators produce a large number of messages sent in parallel to overload the size of the DAG. This is defended against using a strategy known as endorsements
- Weighted Consensus: each validator can be assigned a weight based on voting power. This is the feature that allows support for a Proof of Stake blockchain
Conclusion
The introduction of the Casper Highway protocol gave birth to a new consensus protocol that is both safe and live in the classical partially synchronous Byzantine Fault Tolerant model, while at the same time offering a number of practical improvements over the existing Casper CBC protocol:
- Strong Optimistic Finality: Highway enables the network to reach higher thresholds of finality based on real life assumptions about the reliability of validators
- Flexibility: validators can choose different finality thresholds, allowing them to optimise for different roles in the ecosystem
The result is an advanced state-of-the-art Proof of Stake blockchain architecture that boasts impressive scalability and performance that will help to drive forward broader blockchain adoption.
Disclaimer: This article is written for the purposes of research and does not constitute financial advice or a recommendation to buy.