Impossibility of Full Decentralization in Permissionless Blockchains

Overview

Decentralization is an essential factor that should be inherently considered in the design of blockchain systems. Even though people design systems for good decentralization, in practice, we often observe that blockchain systems are highly centralized. Bitcoin and Ethereum, as representative examples, are already well known to be highly centralized in terms of network and mining. In fact, poor decentralization appears not only in PoW-based coins but also in coins adopting other mechanisms such as proof-of-stake (PoS) and delegated proof-of-stake (DPoS).

Our work targets the centralization issue in blockchains. In this work, we first state two requirements, 1) a good power distribution among participants (i.e., good decentralization in the consensus protocol) and 2) non-reliance on a trusted third party (TTP), that a system should have in order to achieve good decentralization. Then, we find sufficient conditions for a system to reach a good power distribution. In fact, to satisfy these conditions, the cost for one participant running multiple nodes should be greater than the total cost for multiple participants each running one node in the system. Unfortunately, a way to achieve this in a permissionless blockchain that meets the non-reliance on a TTP is not known yet, which implies that permissionless blockchains cannot currently satisfy the sufficient conditions. To make matters worse, we formally prove that even if given infinite time, a permissionless blockchain cannot achieve the good decentralization among the participants whatever mechanism it has. In other words, we face that the two requirements of good decentralization, a good power distribution among participants and non-reliance on any TTP, contradict each other.

In addition, to validate our theory, we both analyze protocols (or incentive systems) of all PoW, PoS, and DPoS coins in the top 100 coins and conduct data analysis of these coins. We see that none of them can satisfy the sufficient conditions, and quantitatively confirm that the current systems do not exhibit good decentralization. More specifically, these systems do not have both enough participants running nodes and an even power distribution among the participants.

Good decentralization of a system

First, we state the requirements of good decentralization. For a blockchain system to achieve a high level of decentralization, the followings are required:

1. [Good power distribution] There are sufficient players (i.e., participants) running nodes in a consensus protocol, and effective power* is not biased toward a few players.
2. [Non-reliance on a TTP] The system does not rely on any TTP.

* Effective power of a player indicates the total resource power of nodes run by that player. Here, a resource can be computational power and stakes in proof-of-work and proof-of-stake mechanisms, respectively

Sufficient conditions for good power distribution

Next, we find sufficient conditions for a system to reach a high level of power distribution (see Section IV-B in the paper for details).

1. Players can earn net profit by running a node in a consensus protocol.
2. Players can earn a higher profit when running a node in a consensus protocol than that of when delegating their resource.
3. For given the same amount of resource, participation with multiple nodes is not more profitable than participation with one node.
4. The ratio between resource power of rich and poor nodes can reach a similar value to 1 if sufficient time is given.

Sybil costs

We can find an incentive system satisfying the above conditions as follows: A node can earn a block reward with a probability in proportion to the square root of the node's resource power (Quadratic Voting by Vitalik).

This mechanism satisfies the conditions except for the 3rd one (see Section IV-C in the paper for details). Naturally, a rational player would run multiple nodes for a higher profit in the mechanism. So, for the third condition to be met, we need an additional mechanism, which causes one participant running multiple nodes to pay a greater cost than the total cost for multiple participants each running one node. The difference between the former cost and the latter cost is called a Sybil cost* in this paper.

* Note that the definition of Sybil costs does not just imply that it is expensive to run many nodes, which is usually mentioned as Sybil costs in the consensus protocol.

Impossibility of good decentralization

For a system to implement the Sybil cost, we can easily consider real identity management in which a trusted third party (TTP) manages real identities of players. When real identity management exists, it is certainly possible to implement the Sybil cost. For example, players can be required to have a certificate issued by a bank to run a node. However, such a method contradicts the second requirement of full decentralization. Currently, it is not yet known how permissionless blockchains without real identity management can implement the Sybil cost. As such, it remains an open problem to satisfy the four conditions without a contradiction of non-reliance of a TTP.

To put it bluntly, we cannot create a system to reach a good power distribution without a Sybil cost, considering a large rich-poor gap in the real world. This is supported by the fact that the probability of reaching a good power distribution is upper bounded by a value close to 0. The following figure depicts the upper bound depending on the rich-poor gap, and one can see that the upper bound is significantly small for a large rich-poor gap (see Section V in the paper for details).

Our result represents that blockchain systems suffer from a contradiction between the two requirements of good decentralization (good power distribution and non-reliance on a TTP), which implies the impossibility of good decentralization of blockchain systems.

Protocol analysis & Data analysis

Next, to determine if what condition each system satisfies or not, we extensively analyzed the PoW, PoS, and DPoS coins in top 100 coins. The above table shows the result of protocol analysis (see Section VI in the paper for details).

In addition, to validate our theory, we conducted data analysis on these coins. Based on this analysis, we were able to observe rational behaviors that degrade the level of decentralization in most coins, which is in agreement with our theory. Moreover, this analysis quantitatively confirms that the current systems do not exhibit good decentralization (see Section VII in the paper for details).

Q&A

• We also provide more detailed answers to the following questions in the paper (see Section V-C).

[Q1] "Sybil attacks are when one physical node claims multiple identities but creating more identities does not increase your mining power, so why is this a problem?"

In this work, we do not claim that the more Sybil nodes exist, the lower decentralization level is. We simply assert that a system should be able to know the current power distribution among players to reach a good power distribution, and the system without real identity management can know the distribution when each player runs only one node.

[Q2] "Would a simple puzzle for registering as a block-submitter not be a possible Sybil cost, without identity management?"

According to the definition of Sybil cost in this work, the cost to run one node should depend on whether a player runs another node. More specifically, the cost to run one node that a player with other nodes should pay should be more expensive than that for a player with no other nodes. Therefore, the proposed scheme cannot give a Sybil cost.

[Q3] "If mining power is delivered in proportion to the resources one has available (which would be an ideal situation in permissionless systems), achievement of good decentralization is clearly an impossibility. This seems rather self-evident."

Naturally, a system would be significantly centralized in the initial state because the rich-poor gap is large in the real world. Considering this fact, our work studies whether there is a mechanism, which allows a system to achieve good decentralization. Note that our goal is to reduce the gap between the effective power of the rich and poor, not the gap between their resource power. In other words, even if the rich possess significantly large resource power, the decentralization level can be high when the rich participate in the consensus protocol with only part of their resource power and so not large effective power. To this end, we can consider an incentive system where the reward rather decreases when a node possesses too large resource power. However, this cannot satisfy the third condition.

Unfortunately, our result states that it is almost impossible for us to create a system with a good power distribution without any Sybil cost, even if infinite time is given. As a result, we're currently facing the contradiction between the two requirements of good decentralization, which implies the impossibility of good decentralization in blockchains.

• Paper information

Yujin Kwon, Jian Liu, Minjeong Kim, Dawn Song, Yongdae Kim, "Impossibility of Full Decentralization in Permissionless Blockchains", ACM Advances in Financial Technology (AFT), 2019, Full version with proofs, Camera-ready version

• Contact

If you have any questions or comments, please don't hesitate to contact the first author Yujin Kwon (dbwls8724@kaist.ac.kr), a PhD student at System Security Lab at KAIST, Korea.