Avalanche
Protocol
Scalable and Probabilistic Leaderless BFT Consensus through Metastability
Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gun Sirer
Model
Probabilistic safety in exponential distribution of message delay
This is used for epidemic networks Ref, Ref, Ref
Probabilistic liveness in full synchrony
Adaptive adversary
DAG-based
Only for the purpose of batching queries in the underlying Snowball instances (the score "confidence" is cumulative along with the DAG)
Do not use graph vertices directly as votes (like IOTA)
Avalanche is different in that the voting result is a one-time chit that is determined by a query, while the votes in PHANTOM are purely determined by transaction structure
No liveness for conflicting blocks
Other contents in the paper
Performance comparison to Algorand and Conflux
Formal model with continuous-time Markov processes (CTMC)
Variants
Wavelet
Perlin
Medium, White paper
Tweet by Alex
A malicious actor with ~10% of stake can stall @PerlinNetwork Wavelet indefinitely.
The Coordicide
White paper
Coordicide Team, IOTA Foundation May 2019
Based on On fast probabilistic consensus in the Byzantine setting by Serguei Popov (University of Campinas, IOTA)
Remove the so-called IOTA Coordinator, a centralized service that finalizes transactions on IOTA
Similar to Snowball but randomize the threshold (after the query of beliefs for other nodes)
Article by NEAR
Rebuttals
By NEAR
What Avalanche paper is not by Alex (Tweet)
Also, tweet about "typo"
Exploring Liveness of Avalanche (… or any consensus algorithm that relies on an unstable equilibrium)
By Nintemoto Labs
On pseudo-profound bullshit in the Avalanche whitepaper
Ash Ketchum, Misty Williams
Tweet
Related: herding
Consensus through Herding
T-H. Hubert Chan Rafael Pass Elaine Shi
EUROCRYPTO'19 Video
Goal:
Communication-efficiency: polylogarithmically many rounds & honest messages to be multicast
Adaptive security without assuming erasures or PoW
Batch agreement: Multi-valued agreement on batch of transactions, with quality metrics (against censorship)
Herding
Initial (subjective) score is quality i.e. how much does the block contains transactions which has been outstanding for a sufficiently long time
VRF-based "mining": vote-specific election unlike Algorand, Ouroboros (Praos), Dfinity
The VRF inputs are (secret_key, batch, round_number)
Adaptive corruption to vote for a different batch doesn't make sense
Based on Communication complexity of byzantine agreement, revisited (see in Block-based consensus)
Assumptions: PKI model, synchronous network, and standard cryptographic assumptions
Proof: based on convergence opportunity
Others
Avalanche for conflict resolusion in zero conf transaction
See in Zero confirmation
Committee Selection is More Similar Than You Think: Evidence from Avalanche and Stellar
we show that Avalanche, a protocol that uses multiple rounds of MPC
nrryuya.icon > ???