Sybil attack vulnerability trilemma

Abstract

Public and permissionless blockchain systems are challenged by Sybil attacks, in which attackers use multiple identities to gain control. Traditionally, such attacks are prevented by consensus mechanisms relying on resource expenditure. However, such mechanisms (e.g. proof of work) face criticism for being wasteful. To address this and other concerns, novel blockchain systems backed by new consensus mechanisms have recently emerged. We formalise three key characteristics pursued by these systems: permissionlessness, Sybil attack resistance, and freeness. We demonstrate that no blockchain protocol can simultaneously achieve all three characteristics within the paradigm established by our formalisation. Thus, a trilemma emerges for distributed ledger technology designers, who must balance these characteristics thoughtfully.

GRAPHICAL ABSTRACT

Keywords:

• Blockchain
• consensus mechanism
• Sybil attack

1. Introduction

Fault tolerance is crucial for both centralised and distributed computer systems, yet it is particularly vital for the latter: in distributed systems, reliable orchestration of shared computing resources over communication networks is essential [1], as all distributed systems may, at times, face physical or human-made faults of varying durations and extents [2]. Generally, such systems can withstand a maximum of $\frac{1}{3}$ faulty participants [3], a limit that is sufficient to allow the operation of common centrally governed systems in which the number of–potentially faulty–participants can be limited by preselection.

Blockchain technology introduced a new class of systems, secure decentralised systems, by allowing public and permissionless access and thus eliminating the need for a dominant operator. Due to this change in permissioning and other technological innovations, secure decentralised blockchain systems provided some novel benefits; namely, resistance to censorship, immutability, and pseudonymity. This led some to consider them suitable systems for democratic or participatory decision-making. However, with these benefits came vulnerabilities, particularly to ‘Sybil attacks’ [4] in which ‘a single faulty entity […] present[s] multiple identities [so] it can control a substantial fraction of the system’ [4].¹ As the first large-scale system of its kind, Bitcoin [5] counteracted Sybil attacks by applying a proof of work (PoW) mechanism in which the likelihood of being selected as a system validator is proportional to the computational effort invested.

In response to challenges around energy demand [6], security [7], fairness [8], performance [9], and suitability for democratic processes [10] of PoW, numerous ‘second generation’ blockchain systems have been proposed [11]. Permissionlessness, i.e. ‘free entry’ [12], remained a central characteristic for these systems. Sybil attack resistance was equally important for such systems, even though this characteristic was often implied, as without it, permissionless systems cannot function effectively. A third characteristic many new blockchain systems strove for was freeness, i.e. the absence of an ‘explicit monetary cost’ [13, p. 1157] to participation.

While all three characteristics are desirable, it is unclear whether they are achievable: observations of existing blockchain systems, particularly around tendencies towards centralisation [14] and documented instances of Sybil attacks [15], cast doubt on the feasibility of a system embodying all three characteristics. This research gap is particularly relevant to designers of public blockchain systems, who need to develop protocols accordingly. We therefore set out to investigate the compatibility of permissionlessness, Sybil attack resistance, and freeness in blockchain systems. We do so by providing background on blockchain technology, with a particular focus on consensus mechanisms (see Subsection 1.1). We then define a formal model of a blockchain system (see Section 2) that culminates in an impossibility theorem (see Subsection 2.2) and apply it to some real-world blockchain systems (see Section 3). We close with avenues for future work (see Section 4) and conclusions (see Section 5). Examples from the blockchain space used in Section 1, Subsection 1.1, and Section 3 are provided to illustrate practical applications of the trilemma for reader comprehension, without claiming comprehensive coverage of all aspects of these systems. We recognise that these examples may extend beyond immediate definitions and assumptions.

1.1. Background

As early as the 1960s, the foundations for distributed systems research were laid in the form of multiprocess networking theory [16]. It has since evolved into a robust field that focusses on improving system reliability by developing and integrating methods to detect, mask and recover from operational and design faults [17]. Contrary to blockchain technology, in early distributed systems, a central authority controlled the admission of participants through attribute-based access control mechanisms [18] and by encoding their permissions in policies [19].

1.1.1. Motivations for decentralisation and impact beyond finance

Blockchain systems, which are positioned as decentralised transactional technologies that can facilitate the censorship-resistant replication of pseudonymous data between distrusting peers, potentially even without human intervention [20], allow the preservation of system history without exposure to the risk of nation-state censorship or regulatory overreach [21]. They were, therefore, welcomed by those who wanted to evade governmental influence [22] and by those who sought a decentralised payment mechanism that contests traditional financial hierarchies [23]. Through cryptocurrencies, blockchain has gained widespread adoption, serving as the underlying technology for both speculation [24] and payments [25]. Blockchain technology is commercially leveraged in trading platforms and payment applications for retail and institutional audiences [26]. Due to their decentralised and, therefore, difficult-to-regulate nature [27], blockchains, particularly when applied to permissionless cryptocurrencies, continue to attract criticism for their role in facilitating the financing of criminal activities [28, 29]. The use of this technology, however, extends beyond the financial realm: some notable applications are evident in fields such as internet of things (particularly ad-hoc networks [30]), healthcare, energy, public services, artificial intelligence, and big data [31].

1.1.2. Blockchain characteristics

Tai et al. [32] characterise blockchain systems as symmetric, admin-free, ledgered, and time-consensual. These key characteristics are useful to differentiate blockchain systems from prior, centrally governed, distributed systems. Most relevant for Sybil attacks is the admin-free property: it describes systems that possess 'no concept of a system administrator who is responsible for maintenance, infrastructure provisioning or access control' [32, p. 758]. Tai et al. [32, p. 758], furthermore, state that updates to a blockchain system happen ‘on an individual basis [governed by] community consensus’. Although, as described earlier, such consensus was not necessary for previous distributed systems due to the availability of centralised controls, it becomes critical in open systems where these controls are absent. Therefore, it is evident that, for successful community consensus, the group forming the community must be known and that this group, by and large [33], must follow accepted rules to reach consensus.

Blockchain systems are commonly classified along the anonymity and trust continuums (see Table 1). From an anonymity perspective, they can be classified as public, displaying data openly, or private, with centrally enforced access controls. From a trust perspective, they are either permissioned, with pre-selected validators, or permissionless,² if participation in the use, development, and governance of the system is possible without needing permission from an authority, simply by following publicly stated procedures [34].

Table 1. Tezel et al. [35, p. 549] categorise four archetypes of Blockchain architectures (adapted from Platt and McBurney [36]).

	Permissioned	Permissionless
Public	i	ii
Private	iii	iv

Therefore, the many permissioned blockchain systems (types i and iii in Table 1), in which only a limited and controlled group of participants can take part [37–39], are not of interest in the context of this study: we focus on permissionless systems (types ii and iv in Table 1), as only these are commonly threatened by Sybil attacks.

1.1.3. Sybil attack resistance

All distributed systems, but particularly permissionless systems, face the consensus problem: ‘a problem in distributed computing wherein nodes within the system must reach an agreement given the presence of faulty processes or deceptive nodes’ [40, p. 1545]. Malicious participants may worsen this problem via Sybil attacks, where large numbers of bogus processes are created to overpower genuine ones. Under the assumption that the number of malicious processes executed by an attacker is not limited, achieving consensus in systems under Sybil attacks is not possible using simple voting-based techniques [41–43]. Specifically leader-based mechanisms, such as Practical Byzantine fault tolerance [44] or Raft [45], while well suited to centrally managed distributed systems, are ineffective in public and permissionless systems, where an attacker can create arbitrary processes. There are many models to reach agreements in the presence of Sybil attacks [36], with PoW being the most popular.

1.1.3.1 Proof of work

Bitcoin [5] introduced PoW, a mechanism that fundamentally employs an ‘efficiently verifiable, but parameterisably expensive to compute’ [46], cryptographic puzzle to prevent Sybil attacks. Solving this puzzle entitles the solver to carry forward the system log as a validator and grants them a cryptocurrency reward that is automatically distributed. This ensures that those investing significant computational effort are selected as validators, irrespective of the total number of candidates, thereby making Sybil attacks ineffective. Furthermore, the underlying reward mechanism ensures the anonymity of system validators in data replication, while simultaneously disincentivising them from consolidating [47]. This approach to consensus and data replication has been remarkably effective for maintaining system stability but requires the expenditure of large amounts of electricity [6] and is thus facing resistance [48].

1.1.3.2 Alternative consensus mechanisms

Consequently, alternative blockchain systems have been introduced. These often employ less resource-consumptive [49] consensus mechanisms [36], thereby lending themselves to sustainable innovation [50]. Some of these novel systems make participation free by relying on reputation systems to determine the probability of being selected as a system validator [51]. Although these novel systems have demonstrated the ability to withstand small-scale Sybil attacks [42], there are doubts about their resistance to Sybil attacks in fully permissionless contexts [36]. We aim to address such doubts with this work.

1.1.4. Consensus mechanisms as votes on system state

Both proof of resources and majority voting can be considered forms of votes on the canonical state of a decentralised system. For example, a simple PoW scheme, like the one used by Bitcoin, can be considered a probabilistic weighted voting scheme: in it, the voting power of a participant aligns with how much computational effort they invest into solving the PoW puzzle. A miner contributing $\frac{1}{10}$ of the system-wide computational effort for solving a given PoW puzzle would be selected as a block proposer with an approximate likelihood of 10%. Likewise, in a simple proof of authority scheme based on random miner selection, the likelihood of being selected as a block proposer for a system with 10 participants is 10%.

The concept of blocks is central to drawing parallels between blockchain consensus and voting. Blocks are compiled by miners, who gather transactions over time. Blocks, furthermore, group ‘a set of transactions [and are] used as the unit of consensus’ [32, p. 759] in blockchain systems. Since the system state of a blockchain is built up by monotonically chaining such blocks: every instance of a block proposal that is subject to a vote contributes to the overall system state, and thus to the decision on the version of events that is to be considered canonical. Therefore, even if common consensus protocols do not purposively implement democratic principles, the mechanisms they apply to derive system state may show strong similarities with voting processes.

1.1.5. Consensus and social choice theory

Based on the realisation presented in the previous section, it can be shown that findings concerning collective decision-making relate to blockchain consensus mechanisms: in particular, questions of social choice theory and blockchain consensus have an overlap. For example, Arrow's impossibility theorem [52] and the Gibbard–Satterthwaite theorem [53, 54] can be applied to blockchain consensus to analyse how non-objective miners behave when they seek to advance a non-canonical version of the system's history.

1.2. Context

Many researchers have discussed blockchain systems as foundations for democratic self-governance [10, 55–58], some emphasising their suitability for democratic or participatory decision-making [59]. Indeed, it appears reasonable to assume that systems that are resistant to bad actors attempting to take over control while allowing anyone to participate freely would be ideally suited for self-governing communities [60]. Any type of community activity, such as elections [61], trade [62], or the administration of the commons [63], could be supported by such systems. However, despite the 15-year history of blockchain technology, there is little evidence that it is being used in this way [64–66], with governance challenges remaining widespread [67]. On the contrary, there is reason to suspect that public blockchain technology, especially in conjunction with cryptocurrencies, might replicate existing social disparities [68, 69] or lead to centralisation of power [14, 70, 71]. An important research gap is, therefore, to analyse whether democratic self-governed systems are implementable, and simply haven't manifested yet, or whether they cannot exist. Addressing this research gap is the purpose of our work.

1.3. Previous work

Douceur [4] introduced the term Sybil attack in a paper of the same name. In Lemma 2 of that paper, it is shown that in a distributed system in which participation is free, an attacker may present arbitrarily many Sybil identities. It is stated informally that in such a free system without trusted, centralised authority, Sybil attacks are always possible.

1.3.1. Common Sybil attack mitigation strategies

Yang et al. [15] show that Sybil attacks are not merely a theoretical threat but are observable in existing networks. The most prevalent Sybil attack mitigation strategies for blockchains are PoW, defined by Golle et al. [72] as ‘primitives which enforce either high communication or high storage complexity on some party’, and proof of stake (PoS): ‘mechanisms that extend voting power to the stakeholders of the system [73].

1.3.2. Reputation systems for Sybil attack mitigation

Beyond these, a common Sybil Attack mitigation strategy is the application of reputation systems, in which the relationships between participants in a system are used to derive a measure of trustworthiness for participants that, in turn, determines how much influence these participants have in collaborative tasks [74]. In particular, the work of Yu et al. [75], which introduces such a protocol by building on established trust relationships, predates blockchain technology. Agent-based analysis of reputation systems for Sybil attack resistance has been undertaken by Platt and McBurney [42] who find that simple Sybil attacks can be repelled by reputation systems. This result is in line with findings by Seuken and Parkes [Theorem 3][76], who show that systems may achieve ‘K-sybil-proofness’, i.e. resistance against up to K Sybil identities. However, they further prove that reputation systems alone cannot yield a fully Sybil-proof decentralised system.

1.3.3. Physical-world-linking to address sybil attacks

An alternative mitigation strategy is that of physical world linking [36, 77], in which information from the physical world, such as sensor readings, is used to ensure the individuality of participants [77, 78]. As discussed well before the era of blockchain [79], such an approach commonly requires trusted hardware, in which case it needs to be considered quasi-permissioned, with trust being anchored in the maker of said trusted hardware. Furthermore, implementations of physical world linking can be vulnerable to attacks in which groups of attackers act in concert, combining device signals to circumvent protocols.

1.4. Contribution

We formalise the notions of free and Sybil attacks for blockchain systems. In Proposition 2.2, we formalise and prove the statement by Douceur [4, p. 254], that in a free system without trusted authority, Sybil attacks are always possible. Note that a correct formalisation of without trusted authority must also exclude other, potentially very complicated, organisational structures, such as consortia or consensus systems that obfuscate centralisation. We achieve this, for blockchain systems only and not for distributed systems in general, in our definition of (strongly) permissionless.

2. Formalising some properties of blockchain systems

In this section, we will formally define a model for blockchain systems and will rigorously define what it means for such a system to be permissionless, Sybil attack resistant, and free. In the end, we will show that, in our definition of a blockchain system, there can be no system satisfying all three properties.

This is similar to classical theorems in social choice theory: Arrow's impossibility theorem states that there is no voting system satisfying three distinct fairness criteria [52]; the Gibbard–Satterthwaite theorem states that voting systems are susceptible to tactical voting if there is more than one voter and more than two options to choose from [53, 54]. In these two cases, as in our application, three desirable properties for systems are defined, and it is shown that no system can satisfy all three simultaneously.

2.1. Formal model

We approach decentralised systems from a transactional perspective: we assume that the system state is derived from a set of temporally ordered actions that comply with the rules of the underlying system protocol and form a history. Actions can change the system from one state to another, possibly identical, state. We assume them to be instantaneous and deterministic, and they are taken at discrete timesteps. This aligns with common blockchain implementations, in which transactions are sequentially ordered by compiling them into blocks [80]. We assume that, for any blockchain system, rules are in place that allow it to be determined whether an action is in accordance with the underlying protocol. Typically, protocols require that the content of every block satisfies some cryptographic property; for example, that it contains a hash of the content of the previous block. The definition of ‘action’ is intentionally abstract to encompass all rule-compliant measures a participant in a blockchain network might initiate. Common actions under existing protocols are to propose transactions and to compile transactions into blocks.

Definition 2.1

1. Let A be a non-empty set of actions, containing an element $\mathrm{none}\in A$. none is called no action. Let ${\mathrm{HIST}}_0\subset \{f:\mathbb{N}\times \mathbb{N}\to A:\begin{array}{c}\text{ex. at most finitely many }s\in \mathbb{N}\\ \text{with: }\mathrm{\exists t}\in \mathbb{N}\text{ s.t. }f(s,t)\ne \mathrm{none}\end{array}\}$and $\mathrm{HIST}\subset {\mathrm{HIST}}_0$ be defined as those histories in which every action is in accordance with the underlying protocol. $\mathrm{HIST}$ is called the set of possible histories of the protocol. An element $\mathrm{hist}\in \mathrm{HIST}$ is called finite if $f(s,t)\ne \mathrm{none}$ for at most finitely many $(s,t)\in \mathbb{N}\times \mathbb{N}$. For $(s,t)\in \mathbb{N}\times \mathbb{N}$ we call s a participant and t a point in time.

2. Let B be the set of all possible blocks. Then B is contained in A in the sense that for every block B there is the action of proposing it. An element $\mathrm{hist}\in \mathrm{HIST}$ is a collection of actions, and it defines a tree of blocks in which each branch obeys the rules of the protocol. This tree is called blockchain defined by $\mathrm{hist}$.

3. A decision function is a function $\mathrm{dec}:\mathrm{HIST}\to \left\{\right(b_1,b_2,\dots ,b_k)\in B^k\text{ for any }k\ge 0\}\cup \left\{\varnothing \right\}$satisfying the following property: if $\mathrm{dec}\left(\mathrm{hist}\right)=(b_1,b_2,\dots ,b_k)$, then $(b_1,b_2,\dots ,b_k)$ must be a branch in the blockchain defined by $\mathrm{hist}$. If $\mathrm{dec}\left(\mathrm{hist}\right)=\varnothing$ we say that $\mathrm{dec}$ makes no decision for the history $\mathrm{hist}$.

A minor point is that, in blockchain systems, views on what is the current state of the system may differ between system participants for short timeframes (e.g. due to replication delays). In our simplified model, we assume that all participants have an aligned view of all actions. The difficulty that remains is that participants may be presented with a history exhibiting multiple branches, each of which is in accordance with the underlying protocol. Decision functions, as illustrated in Figure 1, allow participants to resolve such conflicts.

Figure 1. A decision function $\mathrm{dec}$ takes an ambiguous history (e.g. one with forks) as input and derives a canonical history as output.

Commonly, system protocols employ decision functions that apply probabilistic techniques to this problem, such as the ‘longest chain’ rule in Bitcoin or the Ethereum fork-choice algorithm that takes into account the weight of a branch. In some scenarios, a decision function may select none of the existing branches as correct; for example, where multiple branches of equal length exist in Bitcoin. In our formalism, the decision function in this case would return $\varnothing$ instead of a preferred branch.

Zorn's lemma [81, 82] may be used to construct decision functions. However, it is never needed if only deciding on finite histories (which is the only case considered in this manuscript), and additional choices would need to be made if deciding on infinite histories.

Definition 2.2

Weakly permissionless

A protocol is called weakly permissionless if for all finite $\mathrm{hist}\in \mathrm{HIST}$ there exists a branch $(b_1,\dots ,b_k)\in B^k$ such that for any future behaviour of the participants in $\mathrm{hist}$ and for any participant $s^{\ast }$ not in $\mathrm{hist}$, there exists a continuation $\widetilde{\mathrm{hist}}$ of $\mathrm{hist}$ defining a branch $(b_1,\dots ,b_{k+n})$ such that for all legal blocks $b^{\ast }$ we have $\mathrm{dec}(\widetilde{\mathrm{hist}}+(s^{\ast },b^{\ast }\left)\right)=(b_1,\dots ,b_{k+n},b^{\ast }).$Here, $\widetilde{\mathrm{hist}}+(s^{\ast },b^{\ast })$ denotes the history that is equal to $\widetilde{\mathrm{hist}}$ but has one additional action added to it, namely the action of a participant $s^{\ast }$ to propose the block $b^{\ast }$ at time 1 after the last action in $\widetilde{\mathrm{hist}}$.

Informally, this means the following: $\mathrm{hist}$ is the state of the system of a blockchain at a given time, including all actions that led to its current state, potentially including forks. If the system is weakly permissionless, then a new participant can get some future block $b^{\ast }$ accepted by the decision function, and no one can stop them. If there is even a small chance that the new participant cannot get their block accepted, no matter their actions, then that protocol would not be weakly permissionless. Of course, we do not expect that the new participant can get all blocks they want accepted: before their block $b^{\ast }$ is accepted, there may come other accepted blocks $b_{k+1},\dots ,b_{k+n}$ that were not suggested by the new participant. There are no conditions on the content of $b^{\ast }$, except that it must be legal according to the blockchain protocol.

Definition 2.3

Strongly permissionless

A protocol is called strongly permissionless if for all finite $\mathrm{hist}\in \mathrm{HIST}$ and for any future behaviour of the participants in $\mathrm{hist}$, there exists an infinitely long continuation $\widetilde{\mathrm{hist}}$ of $\mathrm{hist}$ and a positive integer $N_0$ such that the following is true: for all $N>N_0$, the majority of accepted blocks in $\widetilde{\mathrm{hist}}$, cut off at time N, have been proposed by participants who did not have any activity in $\mathrm{hist}$.

In contrast to weakly permissionless protocols, strongly permissionless protocols are characterised not only by allowing new participants to occasionally propose transactions but by, eventually, allowing them to propose a majority of transactions.

The adherence of Bitcoin, the archetypal strongly permissionless protocol, to Definition 2.3 can be illustrated as follows: $\mathrm{hist}\in \mathrm{HIST}$ could be the current state of the Bitcoin blockchain. This includes the full blockchain, including forks. A new participant $s^{\ast }$ can immediately propose any legal block $a^{\ast }$, containing the required PoW, to be added to the longest chain which will be accepted by the decision function $\mathrm{dec}$, the ‘longest chain’ rule. In this case n = 0. That is, the participant $s^{\ast }$ does not need to take any actions to improve their own standing in the protocol, since a correct PoW immediately entitles them to propose a block. Given appropriate resource expenditure, the participant could propose new blocks in perpetuity. This is illustrated in Figure 2: in the strongly permissionless system shown, a majority of new blocks were created by new participants.

Figure 2. Left: a Blockchain created by some participants. Top right: an example of a Blockchain that is not weakly permissionless and not strongly permissionless. A large number of new participants (shown with a hat) joined but they are not allowed to create blocks. All blocks going forward are created by the original participants. Bottom right: an example of a Blockchain that is strongly permissionless. New participants joined and are creating a majority of new blocks (shown with a hat) going forward, which cannot be prevented by the original participants.

Definition 2.4

Sybil attack vulnerable

A system with finite history $\mathrm{hist}$ is vulnerable to Sybil attacks if for any behaviour of the participants in $\mathrm{hist}$, there exist arbitrarily long continuations $\widetilde{\mathrm{hist}}$ of $\mathrm{hist}$ such that a majority of accepted blocks in $\widetilde{\mathrm{hist}}$ have been proposed by participants not in $\mathrm{hist}$ and these participants have expended only negligible explicit monetary cost.

In the context of decentralised systems, an attack is understood as the realisation of a threat, representing a harmful action aimed at exploiting vulnerabilities within the system [83]. A type of attack that has received particular attention in the blockchain community is the Sybil attack [36]: Informally, in accordance with Douceur [4, p. 251], we define a Sybil attack on a decentralised system as a series of protocol-conforming actions through which an attacker presents multiple identities with the intent of seizing control of a substantial fraction of the system. Attackers achieve the seizure of control by skewing collective decisions, such as voting, in their favour. A potential result of a successful Sybil attack on a strongly permissionless system is the attacker increasing the probability of proposing new blocks, thereby being able to censor block contents and, ultimately, centralising power over the system. It is intuitively clear that a Sybil attack is only possible if a malicious actor can take many actions while expending only negligible explicit monetary cost. In accordance with Saleh [13, p. 1157], we formally define this as:

Definition 2.5

Free

A system is free if all actions can be taken by incurring only negligible explicit monetary cost.

Notably, staking requirements common in cryptocurrencies, which are perceived not as monetary costs but as commitments for potential financial gain, are excluded by this definition.

2.2. An impossibility theorem for Sybil attack resistance

We define three properties of interest for blockchain systems: permissionless in Definitions 2.2 and 2.3, Sybil attack vulnerable in Definition 2.4, and free in Definition 2.5. Here is how these notions are related to each other:

Proposition 2.1

Any Sybil attack vulnerable system is strongly permissionless.

Proof.

Definitions 2.3 and 2.4 are the same, except that Sybil attack vulnerability has an additional restriction that is not present in the definition of strongly permissionless.

Most importantly, there is no system that satisfies all three requirements:

Proposition 2.2

Impossibility Theorem for Sybil Attack Resistance

A blockchain protocol cannot be strongly permissionless, Sybil attack-resistant, and free.

Proof.

By definition, a system that is free and strongly permissionless must be Sybil attack vulnerable. Therefore, such a system cannot be Sybil attack-resistant, which illustrates the claim.

3. Illustration of the trilemma using existing blockchain systems

In consideration of Proposition 2.2, an analysis of existing blockchain systems has been performed for illustrative purposes, acknowledging that the described Trilemma may not encompass all aspects of these real-world systems in their entirety. To this end, we selected two particularly popular blockchain systems with associated cryptocurrencies to illustrate common combinations of characteristics, potentially extending beyond the immediate scope of defined assumptions. Both systems are representative of a large number of others that use PoW (see Subsection 3.1) or PoS (see Subsection 3.2) in similar ways. The remaining combination–strongly permissionless and free but not Sybil attack resistant–is rare, as systems with these characteristics can be disrupted as a result of targeted Sybil attacks and are, therefore, mostly of theoretical interest. To shed light on this combination of characteristics, we selected a technique that has so far been discussed only theoretically (see Subsection 3.3). Figure 3 shows the different possible combinations, visualising Proposition 2.2 (Table 2).

Figure 3. Diagram showing how free, Sybil attack vulnerable, and strongly permissionless blockchain systems are related. By Proposition 2.1, Sybil attack vulnerable systems are a subset of strongly permissionless systems. By Proposition 2.2, the intersection of the two circles ‘Free’ and ‘Strongly Permissionless’ and the complement of ‘Sybil Attack Vulnerable’ is empty.

Table 2. A comparison of common Blockchain systems. The ° symbol indicates whether they meet the definition of strongly permissionless (SP), Sybil attack-resistant (SAR), or free (F).

Sec.	System	Mechanism	SP	SAR	F
Subsection 3.1	Bitcoin	Proof of work (PoW)	°	°
Subsection 3.2	Ethereum 2	Proof of stake (PoS)		°	°
Subsection 3.3		Proof of lucky ID (PoL)	°		°

3.1. Proof of work

Proof of work (PoW) is the archetypal approach to preventing Sybil attacks. While it predates Bitcoin [84], its use in the context of decentralised networks dates back to this cryptocurrency [5]. Strong permissionlessness is central to Bitcoin's design, in which messages are exchanged on a best-effort basis between nodes that are able to leave and join the network at will [5]. Arbitrary nodes can participate in the consensus mechanism in a censorship-resistant manner that can recover from network partitions. Nakamoto [5] motivates the use of PoW by emphasising that it enables one central processing unitCPU, one vote [5, p. 3] mechanics that, under the assumption that ‘a majority of CPU power is controlled by honest nodes’ [5, p. 3], can secure the existence of the Bitcoin system in perpetuity. While attackers can easily create arbitrary numbers of accounts, PoW prevents these from interfering with consensus. However, despite the potential of block rewards offsetting the costs, participation in Bitcoin's consensus mechanism is costly, since it requires significant computational effort and, consequently, physical resources to provide it.

3.2. Proof of stake

To the best of our knowledge, the first mention of proof of stake (PoS) occurred in Bitcoin circles: here, it was proposed to align the influence in majority-based activities with ‘the number of bitcoins you can prove you own’ [85]. The most popular implementation of this concept is Ethereum, conceived as a PoW system [86] and recently successfully transitioned to PoS during the Ethereum 2 merge [87]. Note that the restrictiveness of Definition 2.3 excludes Ethereum 2: the current Ethereum 2 stakeholders possess the ability to collude and effectively bar external participation by virtue of the requirement to deposit cryptocurrency into the protocol's deposit contract to qualify as validator [88]. Consequently, those without access to the Ethereum cryptocurrency are perpetually excluded from the validator pool, making them unable to propose blocks. Ethereum's PoS system exhibits strong Sybil attack resistance: similar to other blockchain systems, users can create arbitrary accounts for the Ethereum 2 blockchain. However, due to the prerequisite of staking cryptocurrency to act as a validator, unfunded accounts would not be selected for participation in some of the network activities. Participation in Ethereum 2 (including in the role of validator) is free according to our unrestrictive Definition 2.5, which ignores transaction fees and cryptocurrency staking requirements.

3.3. Proof of lucky ID

Ogawa et al. [89] introduced proof of lucky ID (PoL), a mechanism that can be used to illustrate the class of strongly permissionless and free systems that are not Sybil attack-resistant. In PoL, a miner is selected pseudorandomly using their ID. We assume a simplified ID supply mechanism that allows users to self-generate IDs.³ The random selection of nodes from the pool of participants can be considered an approach that achieves strong permissionlessnes. Depending on the ID supply mechanism, this mechanism is, however, highly susceptible to Sybil attacks: where a self-generated ID is used [89, p. 1216] and no further restrictions on ID generation are made, an attacker can easily conduct a Sybil attack by creating many IDs, thereby increasing the likelihood of being randomly selected. Note that it is conceivable to alter the protocol by applying other ID supply mechanisms that are less free or less permissionless, but may in turn lead to Sybil attack resistance. Under the assumption of a free ID supply mechanism, PoL can be considered equally free.

4. Future work

We adopt a binary view of the three desirable characteristics of permissionlessness, Sybil attack resistance, and freeness. However, blockchain systems in actual implementation do not always lend themselves to binary classification. For instance, in our work, the characteristic of freeness is defined dichotomously. In reality, however, there is a wide range of costs of participation between blockchain systems of different characteristics and popularity. The same may apply to the remaining two characteristics. For example, PoS systems do not satisfy our definition of permissionless. Yet, they may be considered permissionless for practical purposes in some cases.

An extension of the theorem, for example by introducing a scalar representation of the desired characteristics, could provide further insight into the underpinning relationships. Furthermore, given the parallels between voting and blockchain consensus, applying social choice theory to blockchain consensus is a promising approach for future work.

We gave a very simple definition of Sybil attack vulnerable (Definition 2.4), which subsequently made it easy to formally reason about it. Instead, one may be able to formalise the notions of attack and subsequently Sybil attack, relating them to informal definitions from the literature. One could then define a Sybil attack vulnerable system as a system in which such (formally defined) Sybil attacks are possible. The difficulty in doing this is to find corresponding definitions of permissionless and free which can be related to real-world protocols and still have the property that there is no protocol that complies with all three new definitions: permissionless, free, and Sybil attack resistant.

Moreover, it should be acknowledged that the conclusions drawn in our manuscript are subject to the paradigm established by our formalisation (see Section 2). It is plausible that alternative formalisations, yet to be explored, might offer different perspectives.

5. Conclusion

Blockchain systems that are permissionless (i.e. allow public participation without limitations), resistant to Sybil attacks (i.e. not vulnerable to attackers that skew collective decisions), and free (i.e. require expenditure of only negligible explicit monetary cost) are highly desirable for many applications; notably, for democratic self-governance. However, there is reason to believe that these three properties cannot be achieved in a blockchain system simultaneously. Therefore, we raised the question of proving their compatibility.

We have shown that no blockchain system can concurrently achieve the three desirable characteristics defined within the framework outlined in Section 2, leading to the negative conclusion of this question within the defined paradigm. Furthermore, we categorised existing popular blockchain systems by the set of desirable characteristics they exhibit. For example, Bitcoin is strongly permissionless and Sybil attack-resistant but not free, whereas, Ethereum 2 is Sybil attack-resistant and free but not strongly permissionless. These findings have implications for the designers of future blockchain systems, who can apply them to address the tradeoffs between characteristics more consciously. A more deliberate treatment of these tradeoffs may enable systems that focus on two of the three dimensions and, thereby, achieve a better problem-solution fit. Our results also help to critically evaluate common claims that certain protocols are free and permissionless. A noteworthy limitation of our work is that the definition of permissionless is restrictive and excludes some systems that have been labelled permissionless by others, and this should be considered when interpreting this work.

Understanding whether given blockchain applications deliver on the promise of decentralisation remains a central challenge for the credibility of this emerging technology. While it was shown that systems that simultaneously exhibit all three desirable characteristics cannot exist under our formalisation, we recognise that blockchain technology offers great potential for applications, in self-governance and beyond, if the technological trade-offs are understood, managed, and communicated.

Acknowledgments

M.P. would like to acknowledge Daniel Körnlein for his helpful comments and Moti Yung for reviewing an earlier version of this paper. M.P. and D.P. acknowledge reviewer #1 for suggesting an alternative definition of Sybil attack vulnerability, which prompted the discussion in Section 4.

Data availability statement

Data sharing is not applicable to this article as no new data were created or analysed in this study.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

D.P. was supported by the Eric and Wendy Schmidt AI in Science Postdoctoral Fellowship, a Schmidt Futures program.

Notes

1 See Subsection 1.1 and Definition 2.4 for a more comprehensive description.

2 Notwithstanding Definitions 2.2 and 2.3.

3 This configuration is somewhat artificial and likely not in line with the intentions of Ogawa et al. [89]. It is used here solely to illustrate the class of non-Sybil attack resistant systems.