IOTA and Avalanche
People have told me recently of claims that “IOTA cloned Avalanche”, which are being expressed since the release of Shimmer. Initially, I thought “Ah, it must be those ‘Twitter experts’… not worth even a second of attention”, and went back to work. However, to my great sadness and dismay, I have learned that among these people, there are some which enjoyed great respect (including mine) in the DLT community.
Please understand me: I have devoted my whole life to the Academy. I can’t unfortunately claim to have made any globally important contributions, but still there are some papers about which I can perhaps be proud. I have learned to respect the work of other people, even when I could see imperfections and flaws in it. I really, really, hate to speak badly about others’ work. However, in the present situation, and in view of the statements which are so blatantly untrue, I am unfortunately forced to respond.
OK, so, let’s first go back to the 70s. That period was marked by the beginning of rigorous mathematical treatment of the so-called “Interacting Particle Systems”, which include the so-called “Voter Model” (Clifford and Sudbury, 1973; Holley and Liggett, 1975). This last model (in fact, a class of models) can be roughly described in the following way: there is a graph, each site of which has an “opinion”, 0 or 1. At random moments, each site consults some neighbor(s), and adopts his (their) opinion (using a majority rule, in case it consults several). A very important observation is that, in most cases, voter models have only two extremal invariant measures: one concentrated on the “all-0” configuration, and the other one concentrated on the “all-1” — we can naturally call these two configurations “consensus states”. Since then, there has been an enormous amount of work on all kinds of voter models (see for example http://summit.sfu.ca/item/17718 and references therein) for specific applications of voter-type models for reaching consensus; or just google for “probabilistic consensus”, to see what I mean.
A year ago, I learned about the “Avalanche” paper and quickly skimmed through it. My impressions were the following:
- The authors (who preferred to remain anonymous) are happily reinventing the wheel — see above.
- For some reason, they like using words of which they don’t know the meaning, such as “metastability”. If I remember correctly, they call it a “tool” (metastability is a phenomenon rather than a tool). They call “metastable” a model named “slush” (which is a random walk on a concave potential, which therefore doesn’t have any potential wells, those that give rise to metastability). And they apparently think that “metastability” (which indeed manifests itself in the presence of Byzantine actors) is something cool, while in reality, it is completely the opposite — in this context, if the system is in a metastable state, it means that it is stuck in an “away-from-consensus” regime for a very long time, which obviously can’t be a good thing.
- The academical level of that paper is low. Besides not mentioning the previous relevant work, when the authors try to write any serious math, the result is, to put it gently, unconvincing. I recall my impression that, what they called a “proof”, was simply not.
- Most importantly, their system was very likely unsafe. This is because an adversary is able to maintain the system in an “undecided” (metastable) state for a very long time, and during this very long time, by the force of chance, some nodes may finalize their opinions while the others still stay undecided — then the adversary may even sway the system to the other side to make others adopt a different opinion. By the way, this intuition was recently confirmed. So, I’ve just forgot about all that, and moved on.
Now, back to IOTA. As you may know, in the beginning we were trying to embed everything (security, incentives to behave correctly, etc.) into the tip-selection algorithm. This gave rise to interesting theoretical and practical developments, but we were never completely satisfied with it. Most probably, it would have worked without the Coo but with a few additional protective mechanisms (see the 2018 “Coordicide” blog series, e.g. “stars”), but we were looking for more. Then, one member of our research group (you can probably guess who it was :) — and no, it was not me) had the following idea: Since IOTA is about freedom, the nodes are also free to communicate between themselves proactively, to decide which transactions are valid, and which are not. Great, but how should they communicate?
The problem with the voter-type models (“rediscovered” in the Avalanche paper) is that those are typically not resilient to a significant number of Byzantine nodes. They can usually admit no more than the square root of N adversarial nodes, where N is the total number of nodes; otherwise the adversary would be able to prevent the consensus from occurring, for at least some initial conditions. While the known (probabilistic) BFT-algorithms normally have high communicational complexity (in each round, any node has to query at least a fixed proportion of all other nodes) and therefore scale poorly.
After many discussions with other researchers in our research department (I take this occasion to express my gratitude to all of them) I had an idea of the “randomly moving threshold” which avoids the metastable behavior altogether — see https://arxiv.org/pdf/1905.10895.pdf. An important note: I do not consider it a very major development. Rather, it is a small brick laid upon a huge body of previous work. However now I am forced to stress that the “Avalanche” paper is not a part of that work. As a simple mental exercise though, try to think why these thresholds must be global (i.e. it is not enough if each node chooses its own random thresholds independently).
In parallel, we are also exploring other approaches (specifically, the CA one). Of course, as is the case of any serious scientific work, they also stand on other’s shoulders while adding a bit of new insight. We, the researchers of the IOTA Foundation, firmly believe that the scientific advances are always fruits of collective efforts and should belong to everyone. In particular, we will be of course happy if our contributions find their way to be used in other projects (including, obviously, Avalanche).
Well, hopefully this clarifies the question. As hinted to in the very beginning, I really did not enjoy writing the above text, so please permit me to end it here.
