Consensus protocols // back again
Anyone can reinvent it’s own consensus protocol, but all of the protocols have well known pitfalls and limits.
Wake up, any consensus protocol is just voting. Any voting can be hacked, all such hacks are known, but researchers are still trying to reinvent the bicycle.
A family of leaderless, decentralized consensus protocols, called Snow consensus was introduced in a recent whitepaper by Yin et al. These protocols address limitations of existing consensus methods, such as those using proof-of-work or quorums, by utilizing randomization and maintaining some level of resilience against Byzantine participants. Crucially, Snow consensus underpins the Avalanche blockchain, which provides a popular cryptocurrency and a platform for running smart contracts. Snow consensus algorithms are built on a natural, randomized routine, whereby participants continuously sample subsets of others and adopt an observed majority value until consensus is achieved. Additionally, Snow consensus defines conditions based on participants’ local views and security parameters. These conditions indicate when a party can confidently finalize its local value, knowing it will be adopted by honest participants. Although Snow consensus algorithms can be formulated concisely, there is a complex interaction between randomization, adversarial influence, and security parameters, which requires a formal analysis of their security and liveness. Snow protocols form the foundation for Avalanche-type blockchains, and this work aims to increase our understanding of such protocols by providing insights into their liveness and safety characteristics. First, we analyze these Snow protocols in terms of latency and security. Second, we expose a design issue where the trade-off between these two is unfavorable. Third, we propose a modification of the original protocol where this trade-off is much more favorable.
Here is a summary of the key points from the research paper:
- The paper analyzes Snow consensus protocols, which are leaderless, decentralized consensus protocols introduced in a 2019 whitepaper by Team Rocket. These protocols underpin the Avalanche blockchain.
- Snow consensus algorithms work by having nodes continuously sample random subsets of other nodes and adopt the majority opinion until consensus is reached. The protocols aim to provide low latency and high throughput.
- The paper provides a formal analysis of the liveness and security properties of Snow protocols. It establishes upper and lower bounds on the time required to reach consensus.
- For the basic Slush protocol, it shows an upper bound of O(log n) rounds and a lower bound of Ω(log n / log k) rounds to reach consensus, where n is the number of nodes and k is the sample size.
- The paper finds an unfavorable tradeoff between security and latency in the Snowflake and Snowball protocols, due to their consensus finalization mechanisms. It shows an adversary can delay consensus super-polynomially.
- The paper proposes a modified consensus protocol called Blizzard that reconciles security and fast consensus. It proves Blizzard reaches consensus in O(log n + β) rounds with negligible failure probability.
- Overall, the paper provides valuable insights into the theoretical performance of Snow-style consensus protocols relevant to real-world systems like Avalanche. Its analysis informs recommendations to optimize performance.
This paper presents a partially synchronous BFT consensus protocol powered by BBCA, a lightly modified Byzantine Consistent Broadcast (CBC) primitive. BBCA provides a Complete-Adopt semantic through an added probing interface to allow either aborting the broadcast by correct nodes or exclusively, adopting the message consistently in case of a potential delivery. It does not introduce any extra type of messages or communication cost to CBC. BBCA is harnessed into BBCA-CHAIN to make direct commits on a chained backbone of a causally ordered graph of blocks, without any additional voting blocks or artificial layering. With the help of Complete-Adopt, the additional knowledge gained from the underlying CBC completely removes the voting latency in popular DAG-based protocols. At the same time, causal ordering allows nodes to propose blocks in parallel and achieve high throughput. BBCA-CHAIN thus closes up the gap between protocols built by consistent broadcasts (e.g., Bullshark) to those without such an abstraction (e.g., PBFT/HotStuff), emphasizing their shared fundamental principles. Using a Bracha-style CBC as an example, we fully specify BBCA-CHAIN with simplicity, serving as a solid basis for high-performance replication systems (and blockchains).
Here are the key points from the paper:
- The paper presents BBCA-CHAIN, a new consensus protocol that rides on a causally ordered DAG to achieve low latency and high throughput.
- It introduces BBCA, a new broadcast primitive with an abortable Complete-Adopt interface. BBCA exposes the internal state of Byzantine broadcast to allow safely aborting it.
- BBCA-CHAIN uses a single BBCA broadcast per view to commit blocks on a sequenced backbone, removing the need for vote blocks or artificial DAG layering.
- Non-backbone blocks use a regular Best Effort Broadcast since they don’t participate in voting. This further reduces latency.
- By riding on the underlying DAG and using BBCA, BBCA-CHAIN achieves commit latency of only 1–2 network trips, compared to 4–6 trips in previous DAG protocols.
- It also simplifies the consensus logic by avoiding complex view change and cross-view justification proofs. The causal DAG history provides enough context for progressing views safely.
- Overall, BBCA-CHAIN reduces latency and improves throughput compared to prior art, while keeping the logic simple. The paper provides a full specification and proves its correctness.
What the ideal consensus protocol should be (unachievable):
- Secure and privacy preserving transactions ordering mechanism // front running/MEV prevention, hard to achieve in practice
- Scalable // solved scalability trilemma
- BFT // tolerance to internal bad actors attacks
- Privacy preserving and secure at the same time // store metadata (proofs) not plain data, real challenge
- Executed on protected hardware // keep private keys private
- Executed with unhackable cryptography // digital signatures, hash functions
- Executed in protected infra // PKI with MITM/Cybil attacks prevention
