Scaling the unscalable
BORIS DOI
Subtitle
a study about consensus
Abstract
Consensus protocols form the bedrock of various distributed systems integral to modern life, ranging from basic clock synchronization to sophisticated blockchains. Yet, the proliferation of consensus protocols reveals a fundamental limitation: their scalability.
In centralized systems, boosting performance can often be achieved with the addition of more participants. However, in decentralized systems, this approach can be counterproductive. The delicate equilibrium between safety and liveness becomes more restricting as the number of participants increases, especially in the permissionless setting, due to fortifications against sybil attacks. This thesis endeavors to make a contribution towards scaling permissionless protocols in a vast landscape of efforts currently addressing the topic.
Commencing with an exhaustive examination of Nakamoto consensus and an attempt to address throughput and latency constraints via GHOST, we establish a unified model for both protocols. This model manifests the intricate interplay between safety, liveness, and performance, paving the way for a family of protocols that arbitrarily approximate the performance of GHOST while remaining resilient against balance attacks, a primary vulnerability of GHOST. Nevertheless, the scope for improvement within the Nakamoto-GHOST paradigm remains constrained by the limitations of GHOST.
Avalanche boosts throughput orders of magnitude higher than Nakamoto and GHOST while maintaining latency in the order of seconds, employing a directed acyclic graph (DAG) instead of a chain. Despite its impressive performance, formal analyses of its safety and liveness were absent, except for the work encompassed in this thesis. Our deep analysis of Avalanche consensus reveals a significant liveness vulnerability, prompting us to enhance its mechanism with Glacier without compromising performance.
DAG protocols have revolutionized consensus protocols in the permissioned setting in recent years. These protocols achieve remarkable throughput but carry an increase in latency. In this work, we introduce an atomic broadcast protocol that continues this line of work but achieves latency similar to leader-based protocols.
These studies serve as inspiration for further results in this thesis. Leveraging techniques used to address consensus protocol performance, we devise a construction that mitigates sandwich attacks in longest-chain consensus protocols. Additionally, our exploration of Avalanche, alongside Conflux, a less familiar protocol, lays the groundwork for the last contribution in this thesis. We craft another construction that transforms a blockchain protocol into a DAG protocol, proving formally that for every blockchain protocol, a corresponding DAG protocol exists that achieves higher throughput, similar or lower latency, and maintains safety and liveness under the same assumptions. Furthermore, this construction allows to determine a set of protocols with the potential to be optimal. Furthermore, the atomic broadcast protocol introduced in this work falls in this category.
In centralized systems, boosting performance can often be achieved with the addition of more participants. However, in decentralized systems, this approach can be counterproductive. The delicate equilibrium between safety and liveness becomes more restricting as the number of participants increases, especially in the permissionless setting, due to fortifications against sybil attacks. This thesis endeavors to make a contribution towards scaling permissionless protocols in a vast landscape of efforts currently addressing the topic.
Commencing with an exhaustive examination of Nakamoto consensus and an attempt to address throughput and latency constraints via GHOST, we establish a unified model for both protocols. This model manifests the intricate interplay between safety, liveness, and performance, paving the way for a family of protocols that arbitrarily approximate the performance of GHOST while remaining resilient against balance attacks, a primary vulnerability of GHOST. Nevertheless, the scope for improvement within the Nakamoto-GHOST paradigm remains constrained by the limitations of GHOST.
Avalanche boosts throughput orders of magnitude higher than Nakamoto and GHOST while maintaining latency in the order of seconds, employing a directed acyclic graph (DAG) instead of a chain. Despite its impressive performance, formal analyses of its safety and liveness were absent, except for the work encompassed in this thesis. Our deep analysis of Avalanche consensus reveals a significant liveness vulnerability, prompting us to enhance its mechanism with Glacier without compromising performance.
DAG protocols have revolutionized consensus protocols in the permissioned setting in recent years. These protocols achieve remarkable throughput but carry an increase in latency. In this work, we introduce an atomic broadcast protocol that continues this line of work but achieves latency similar to leader-based protocols.
These studies serve as inspiration for further results in this thesis. Leveraging techniques used to address consensus protocol performance, we devise a construction that mitigates sandwich attacks in longest-chain consensus protocols. Additionally, our exploration of Avalanche, alongside Conflux, a less familiar protocol, lays the groundwork for the last contribution in this thesis. We craft another construction that transforms a blockchain protocol into a DAG protocol, proving formally that for every blockchain protocol, a corresponding DAG protocol exists that achieves higher throughput, similar or lower latency, and maintains safety and liveness under the same assumptions. Furthermore, this construction allows to determine a set of protocols with the potential to be optimal. Furthermore, the atomic broadcast protocol introduced in this work falls in this category.
Date of Publication
2024
Year of graduation
2024
Theses Type
dissertation
Language(s)
en
Author(s)
Amores Sesar, Ignacio |
Faculty/Graduate School
Institute
Access(Rights)
open.access
Primary OA Publication
true