Saturday, May 8, 2021

Avalanche Stake Imbalance

“Give me control of a nation’s money and I care not who makes the laws.” – M. A. Rothschild

— by Hasan Karahan, MSc ETH Zurich, @notexeditor

Dear Avalanche community, this is the first blog post of a multi-part analysis of the validator stake distribution imbalance present as of today, its potential effects on centralization, and multiple suggestions on how it could get fixed. While we will have an in-depth look at the imbalance, we will provide only a cursory elaboration on the centralization effects and potential solutions. In later blog posts, we will dive further into the latter and the former.

Proof of Stake ¶

Avalanche is a multi-blockchain platform, relying on the proof of stake (PoS) Sybil mechanism to prevent malicious actors from gaining control over a network of validator nodes that operate the platform. Each node has to provide a stake in the form of AVAX coins, and gain hence the right to judge whether a particular transaction on the network is valid or not: Hence, the validator designation for such a node.

The more stake a validator puts up, the higher its weight in terms of voting power within the network: This implies that a node $\mathcal{A}$'s vote counts twice as much compared to a node $\mathcal{B}$ with half as much in stakes compared to the node $\mathcal{A}$. Such a setup is the general case for most of the PoS blockchains.

In Avalanche, a transaction is regarded by a node valid, if it is considered by the peer nodes of the given node valid, where the node asks over 20 rounds 20 stake-weighted random peers their respective opinion. If 70% of those 20 peers (i.e. 14) in a particular round judge a transaction to be valid, then the given node considers the transaction also to be valid (for the given round). After 20 rounds the entire set of validators quickly converges to the same conclusion, thanks to the probabilistic meta-stability properties of the Avalanche algorithm.

Since peer nodes are not subsampled uniformly at random, but are given weight proportional to their stake this mandates a reasonable distribution of these stakes among the validators to ensure censorship resistance for proper decentralization. However, if the stake distribution is skewed, decentralization degrades and centralized control over the entire network reemerges allowing censorship on transactions. Let’s have a look at various stake distributions.

Equal Distribution ¶

Equal Distribution with a GINI=0%
Equal Distribution with a GINI=0%

The diagram above shows the equal distribution, i.e. the distribution in AVAX the Avalanche validators would have had if all of them would have acquired the same amount of stake of about 0.30M AVAX.

The lower diagram displays the stake distribution per validator, and the upper one the cumulative one. The red curves (or in this case lines) plot the total stake, while the blue ones exclude delegations.

The upper diagram is useful because the cumulative view allows visualizing the so-called GINI inequality coefficient. If $s_i$ is the stake (or reward) of a validator $i$, and there are $n$ validators, then the GINI coefficient $G$ is given by:

$$\require{physics} G = \frac{\sum_i\sum_j\abs{s_i-s_j}}{2n^2\bar{s}} $$

where $\bar{s}$ is the arithmetic mean i.e. average stake. Hence, the GINI $G$ measures the total difference within a population (the numerator) and then normalizes it for scale (the denominator).

The lower the GINI is the more equitable the stakes are distributed, and the higher it is the less equitable the network becomes. It ranges from 0% of total equality (and decentralization) to 100% of total inequality (and hence maximal centralization).

The dotted vertical line separates the left-hand side validators, which collectively control only 30% of the total stakes from the right-hand side ones, which control 70%. Due to this hypothetical distribution being so equitable, the number of validators is also split correspondingly between 30% left-hand side vs. 70% right-hand side validators, which is in line with proper decentralization.

Uniform Distribution ¶

Uniform Distribution with a GINI=33.3%
Uniform Distribution with a GINI=33.3%

The uniform distribution above shows the result of randomly assigning stakes to validators – which in Avalanche has of course not been the case.

Perhaps contrary to expectation, the GINI inequality is 33.3% (instead of 0%), because due to randomness there are validators that got almost no stake, while others got double the average of 0.3M AVAX. Since there are poorer and richer validators, the GINI coefficient correctly indicates this by displaying a value larger than zero.

Despite the presence of inequality the uniformly random distribution still looks decentralized enough to ensure censorship resistance, because almost half the validators would need to get corrupted to gain control over 70% of the stakes: Given a large enough total value locked (TVL) in stakes, such a scenario is rather unlikely.

Alternative definition for the GINI coefficient ¶

To gain a better understanding of the GINI inequality $G$, please note that it can also be expressed via the following formula:

$$G = \frac{A}{A+B} $$

where $A$ is the white and empty area below the dotted diagonal straight line (at the GINI of 0%) – going from the lower-left origin to the upper-right corner – and above the red curve (at for example the GINI of 33.3%). Further, $B$ represents the entire area below the red curve (all the way down to the horizontal axis). Hence $A+B$ is the area of the triangle or half the rectangular area of the entire diagram.

If we run the numbers, then the triangular area $A+B$ is equal to ${942}\times{301.1M}/2$ or about $150G$, and $A$ is equal to about $50G$ as expected by a GINI of 33.3%.

Log-logistic Distribution ¶

Log-logistic Distribution with a GINI=66.6%
Log-logistic Distribution with a GINI=66.6%

Let’s investigate the case where the GINI inequality is 66.6%: Due to the definition of the coefficient, multiple distributions lead to the same GINI. Hence, we need to choose a distribution ourselves. So, we decided to go for the so-called log-logistic function, which in economics is also known as the Fisk distribution:

$$f_\beta(x) = \beta \times x ^ {\beta-1} / \big(1+x^\beta\big)^2 $$

By plugging a uniformly distributed random variable $x$ into $f_{\beta=5}$, we managed to create a stake distribution with a GINI of 66.6%. Let’s have a closer look at the result:

  • The minimum stake is zero, and the maximum one at about 1.5M AVAX: The original uniform distribution naturally causes haves and have nots, and the log-logistic function exaggerates then the differences.

  • About 750 of the smaller validators control over only 30% of the stakes;

  • While only about 200 of the larger validators control 70% of the stakes.

As it is easily observable, inequality is up and decentralization has degraded significantly: About 20% of the validators control 70% of the stakes, and hence have the power to sway the Avalanche protocol to their liking! While this scenario is – under the assumption that the 200 larger validators do not collude – probably still censorship-resistant and hence secure enough, you do not get the same assurance levels as with the two networks from above with a GINI of 0% or even 33%.

Conclusion: The higher the GINI inequality the fewer validators are required to be able to collude against the network. Hence, low GINI is good and high GINI is bad for decentralization!

Mainnet Distribution ¶

Mainnet Distribution with a GINI=85.1%
Mainnet Distribution with a GINI=85.1%

Now, if we plot the distribution of AVAX in the Avalanche mainnet, we are confronted with a rather desolate landscape: On the left-hand side of the diagram, the stakes of the smaller validators are – even when cumulated – really tiny that they are barely visible, while on the right-hand side the larger validators tower over the rest of the network!

The GINI coefficient is a whopping 85.1%, the 860 smaller validators of the 942 total have combined access to only 30% of all staked AVAX, while the remaining 82 mega-validators own the lions share of 70% of the stakes. Therefore, this “cabal” of insiders is effectively in total control of the network with the power to censor any transaction they wish to do so.

Conclusion: The Avalanche platform with its current stake distribution of AVAX is centralized, and not censorship-resistant.

Improvement Proposals ¶

We have collected in our blog post of decentralization proposals a preliminary list of suggestions on how the Avalanche community can improve and hopefully also fix the stake imbalance as presented in this exposition. In later blog posts, we will elaborate on each, and investigate their potential impact on the current stake distribution, GINI inequality coefficient, and decentralization.

2 comments:

  1. Published with NoTex.ch — an online editor for finance, science and tech bloggers.

    ReplyDelete
  2. The code and data that was used to generate the diagrams in this blog is open source and transparently available at avalanche-stakes.

    ReplyDelete