Avalanche x Filecoin: combining Snowball and Expected Consensus

[xuechao2]

Description

We explore the possibility of adopting Snowball consensus from Avalanche to improve the finality of Expected Consensus (EC) in Filecoin.

Background

Snowball is a Byzantine agreement protocol and it works as an important building block in the Avalanche network In two different ways:

• Avalanche instantiates a Snowball instance for each set of conflict transactions to decide a single one to be accepted.
• Snowman instantiates a Snowball instance for each height of the blockchain to decide a single block to be accepted.

A summary of these protocols can be found here.

EC is a longest-chain style protocol. At a high level, it operates by running a leader election every epoch in which, on expectation, a set number of participants may be eligible to submit a block. All valid blocks submitted in a given epoch form a tipset. Particularly, a tipset is a set of blocks that each has the same height (i.e., epoch number) and parent tipset; in EC, the blockchain is a chain of tipsets, rather than a chain of blocks. Every block in a tipset adds weight to its chain of tipsets, while the fork choice rule is to choose the one with the highest weight. A closer look at tipsets can be found here. Although the idea of tipset can slightly improve the throughput of the blockchain, EC still suffers from the same long finality issue as many other longest-chain style protocols.

Proposal

In EC, we can use Snowball to finalize one tipset per epoch. Following the same design principle of Avalanche and Snowman, we can take advantage of the DAG structure. For example, when a block/tipset is queried, all blocks/tipsets reachable from it by following the DAG edges are implicitly part of the query. We need to smartly design a voting rule such that 1) the votes converge fast, 2) all honest blocks should be included in the finalized tipset.

Challenge

1. We need to formalize the security proof for Snowball consensus, particularly the liveness proof for multi-value version. Alternatively, we can design an efficient scheme to invoke multiple binary Snowball in parallel. Knowing the design details of Snowman will be very helpful. Currently, there is only one short video introducing it. Maybe try to reach the Avalanche team?
2. Design the voting rule and formally analyze the entire scheme. Again liveness will be the major concern here.