Consensus algorithm and performance

Avalanche Ecosystem
1

Hello,

Avalanche sounds very interesting. I read here that it is a unique consensus protocol that assumes a synchronous network to ensure liveness while safety is probabilistic. This approach looks more like Nakamoto-style consensus, which favours liveness over safety and belongs to the AP class of the CAP theorem, than BFT, which favours safety over liveness and belongs to the CP class of the CAP theorem.

  1. If Avalanche has probabilistic safety, what is the finality time of a block? That is, how many blocks are needed to consider a transaction final? In both the synchronous and asynchronous cases?
  2. What percentage of malicious nodes can the network tolerate? The graph shows it to be between 30-35% depending on the protocol version. This value is different from both the Nakamoto-style consensus, where it is 51%, and the BFT-style consensus, where it is 33%.

Thank you

2 Likes
2

I did some research on Avalanche consensus protocol which apparently does not fit into any of the “classic” Nakamoto and BFT categories.
According to the whitepaper:
In our system, however, nodes operate via subsampling, hence it is possible for a single sample to select a majority of adversarial nodes, and therefore the node gets stuck waiting for the responses. To ensure liveness, a node should be able to wait with some timeout. Therefore, our protocols are synchronous in order to guarantee liveness.
In particular, it is a synchronous protocol unlike the BFT style protocols that operate with partial synchrony and the Nakamoto style protocols that operate with dynamic participation link.

According to the whitepaper:
Similar to Nakamoto consensus, the Snow protocol family provides a probabilistic safety guarantee, using a tunable security parameter that can render the possibility of a consensus failure arbitrarily small.
the Snow family is more efficient when the fraction of Byzantine nodes is small, and it can be parameterized to tolerate more than a third of the Byzantine nodes by trading off liveness.

According to this:
Avalanche is different because the protocol makes trade-offs of weakened liveness for the Byzantine clients, thus higher levels of safety – 80% safety threshold. Note that the percent in Avalanche represents the percentage of the stake held by Avalanche network validators: The malicious nodes will need control the total stake amount beyond safety thresholds. Avalanche safety limits are probabilistic as the protocol performs sample-voting against validators – see IsValidatorOnly. The validator is weighted based on its stake amount for consensus queries, and non-validator is never queried for such consensus polling.
The key tradeoff is: conflicting transactions only come from malicious actors and the probability epsilon is sufficiently small, and thus the protocol does not need to guarantee liveness or finality for such transactions. In other words, the time for finality approaches infinity as the number of adversary nodes f approaches n/2.

According to the whitepaper:
The security parameters chosen in our experiments guarantee a safety violation probability below 10^-9 in the presence of 20% Byzantine nodes.

We adopt a strategy to simulate misbehaving clients where a fraction (from 0% to 25%) of the pending transactions conflict with some existing ones.

Thus, the Avalanche protocol can be configured to work with more than 33% malicious nodes, but performance and operation tests were carried out with between 20-25% malicious nodes.

4 Likes
3

Thanks to some suggestions I received in the Avalanche Telegram group, I have now found answers to my questions.
First of all, Avalanche is a BFT-type protocol that uses a probabilistic threshold as described here:

Avalanche consensus takes classical quorum-based voting protocols and makes them probabilistic.
At a super high level, the subsampling of the core primitives buys you huge performance gains, but it also means that the bounds above are dampened.
Avalanche chooses a purposefully higher quorum threshold (80%, minimum). The liveness bound, as above, is maximally about 20%, but due to dampening it is slightly lower (about 16%).

According to the source code, the parameters are k=20, alpha=beta=15 which corresponds to 75% safety and 25% liveness.

  1. Avalanche is a synchronous protocol that has probabilistic safety with 1 block confirmation and a probabilistic (not fixed) finality time of approximately 1-1.5 seconds (median transaction latency is 1.35 s, with a maximum latency of 4.25 s, see whitepaper).
  2. Avalanche can tolerate up to 25% of malicious nodes.

Best Regards

3 Likes