,
17 tweets,
4 min read
Read on Twitter
TL;DR: Avalanche paper has a typo which makes it unsafe, and that typo cripples into existing cryptocurrencies implementations.
1/ Few days ago I posted an article in which I showed few common misconceptions about Avalanche.
1/ Few days ago I posted an article in which I showed few common misconceptions about Avalanche.
2/ While rerunning the experiments for the article I stumbled on a very suspicious behavior, which after some debugging resulted in a discovery of a strategy that would allow adversaries to break *safety* of avalanche (with default parameters) with just 17% malicious actors!
3/ After running the discovery by @kevinsekniqi, the most likely original author of the Avalanche paper, he said that the paper has a typo, without providing much further context.
4/ The algorithm indeed has a typo. Specifically, both Snowball and Avalanche must reset `count` if a particular sample didn't return `alpha*k` votes for the same color. With this change the naive way to break Avalanche safety no longer works.
5/ That would not be a big deal if there weren't protocols that implemented Avalanche, but naturally there are. For example, @PerlinNetwork until few month ago was using Avalanche.
6/ While their code is not open, the relevant parts of the Avalanche implementation are available in this @opentokeninc's post: medium.com/opentoken/perl…
(Open Token, obviously, failed to find the safety failure issue, and only verified that the implementation follows the paper).
(Open Token, obviously, failed to find the safety failure issue, and only verified that the implementation follows the paper).
7/ Specifically, search there for `conflicts.Count = 0` <- the count is only reset if the vote returned `alpha*k` votes for the opposite color, like in the paper, but not if vote didn't return `alpha*k` votes for any color (the condition missing in the paper necessary for safety)
8/ While @perlinnetwork doesn't use Avalanche any longer, for a long time the safety bug was there, and it was not detected despite multiple code reviews.
9/ The code of a simulation that breaks safety can be found here: github.com/SkidanovAlex/s…
The particular command line that runs the safety-breaking adversarial simulation is
python run.py --adversary_percent=0.17 --adversary_strategy BREAK_SAFETY experiment
The particular command line that runs the safety-breaking adversarial simulation is
python run.py --adversary_percent=0.17 --adversary_strategy BREAK_SAFETY experiment
10/ The exact strategy for the adversaries is in a conflict set of two elements (red and blue) to first bring it to metastability by always responding red to half of participants and blue to the remaining half.
11/ Once it is achieved, slightly shift the balance and start responding Blue to ~55% and Red to 50% of participants. With 17% of adversaries it is enough to maintain metastability for a very long time.
12/ Importantly, the actual number of honest participants that vote for blue will become slightly more than 50%. Now for the honest participants to whom adversaries respond Blue there's a reasonable chance to sample 80% of blue, but very little chance to sample 80% red.
13/ Thus, slowly the `count` for Blue will be growing for all the blue participants, even though the algorithm is in a metastable state.
14/ Once any participants reaches `count = beta` for Blue, that participants commits to blue. At that point all the adversaries start responding Red to all honest actors always.
15/ After a very long time the metastability breaks and all participants commit to Red, thus creating a safety failure.
If count reset when a sample doesn't return 80% for any color, naturally (13) above doesn't work, and the safety with this particular approach is not violated.
If count reset when a sample doesn't return 80% for any color, naturally (13) above doesn't work, and the safety with this particular approach is not violated.
16/ The moral is: don't blindly trust papers, even if the papers are endorsed by high profile professors. Everybody messes up.
(Since twitter by default doesn't show that part of the thread, posting here a relevant discussion with Perlin's CTO above. They independently discovered this issue and it is presently fixed in their implementation)
