rightsretained [GAIW’24]Appears at the 6th Games, Agents, and Incentives
Workshop (GAIW-24). Held as part of the Workshops at the 22st International
Conference on Autonomous Agents and Multiagent Systems.May 2024Auckland, New
ZealandAbramowitz, Aziz, Dickerson, Hosseini, Mattei, Obraztsova, Rabinovich,
Tsang, Wąs (Chairs) International Institute of Information Technology
Hyderabad India International Institute of Information Technology Hyderabad
India International Institute of Information Technology Hyderabad India

# Centralization in Proof-of-Stake Blockchains: A Game-Theoretic Analysis of
Bootstrapping Protocols

Varul Srivastava<EMAIL_ADDRESS>,  Sankarshan Damle
<EMAIL_ADDRESS>and  Sujit Gujar<EMAIL_ADDRESS>
###### Abstract.

Proof-of-stake (PoS) has emerged as a natural alternative to the resource-
intensive Proof-of-Work (PoW) blockchain, as was recently seen with the
Ethereum Merge. PoS-based blockchains require an initial stake distribution
among the participants. Typically, this initial stake distribution is called
bootstrapping. This paper argues that existing bootstrapping protocols are
prone to centralization. To address centralization due to bootstrapping, we
propose a novel game $\Gamma_{\textsf{bootstrap}}$. Next, we define three
conditions: (i) Individual Rationality (IR), (ii) Incentive Compatibility
(IC), and (iii) $(\tau,\delta,\epsilon)-$ Decentralization that an _ideal_
bootstrapping protocol must satisfy. $(\tau,\delta,\epsilon)$ are certain
parameters to quantify decentralization. Towards this, we propose a novel
centralization metric, C-NORM, to measure centralization in a PoS System. We
define a centralization game – $\Gamma_{\textsf{cent}}$, to analyze the
efficacy of centralization metrics. We show that C-NORM effectively captures
centralization in the presence of strategic players capable of launching Sybil
attacks. With C-NORM, we analyze popular bootstrapping protocols such as
Airdrop and Proof-of-Burn (PoB) and prove that they do not satisfy IC and IR,
respectively. Motivated by the Ethereum Merge, we study W2SB (a PoW-based
bootstrapping protocol) and prove it is ideal. In addition, we conduct
synthetic simulations to empirically validate that W2SB bootstrapped PoS is
decentralized.

##  1\. Introduction

_Blockchain_ , first introduced with Bitcoin Nakamoto (2009), is an append-
only, distributed ledger. To maintain a distributed ledger, we need a
_distributed consensus_ – i.e., all the parties (which we call players)
agreeing on a single state of the ledger. _Public_ blockchains employ
consensus protocols such as Proof-of-Work (PoW), Proof-of-Stake (PoS), Proof-
of-Elapsed-Time (PoET), among others Xiao et al. (2020). All these protocols
rely on _incentive engineering_ to achieve consensus. In PoW blockchains, the
players solve cryptographic puzzles to propose the next block to be added to
the ledger. In return, it obtains certain newly minted coins as a reward –
_block reward_. With such incentive engineering, PoW achieves consensus if
more than 50% of players are honest, whereas traditional consensus protocols
require $\frac{2}{3}^{\text{rd}}$ players to be honest Castro and Liskov
(1999). The blockchain community is transitioning to more energy-efficient
Proof-of-Stake (PoS) protocols (e.g. Ethereum Buterin et al. ([n.d.]), the
second largest blockchain by market capitalization and share mar (2023),
shifted to PoS via the Merge Ethereum (2022)). In PoS, a block proposer is
selected with probability proportional to its stake in the system and awarded
the new coins. With incentives involved, the strategic players would maximize
their rewards, which might affect the security of the protocols. This paper
focuses on centralization that might happen in PoS consensus protocols.

Centralization in PoS blockchains – Practical Examples Polygon Hard fork
Nambiampurath (2023) received criticism because it required signatures of just
$13$ validators out of a quorum of $100$ due to centralization of resources.
Furthermore, popular PoS-based blockchains such as ICON Foundation ([n.d.]),
Tezos Goodman (2014), Cosmos Kwon and Buchman ([n.d.]), and Irisnet are highly
centralized (top $10$ stakeholders hold $\geq{1}/{3}$ of the total stake
Schout (2020)). This centralization exposes them to the risk of potential
attacks111E.g., the Luna Crash Sandor and Genc (2022) resulted from offloading
a massive volume of USDT in a very short interval. We suspect such coordinated
de-pegging might be a repercussion of the centralization in the system..

Why is Decentralization Important? Governance and security of blockchains rely
on the decentralization of resources among players. If a player/coalition
collects disproportionate rewards, it might compromise the correctness of
protocols Garay et al. (2015); Gilad et al. (2017). In PoS blockchain,
centralization is when a coalition (aka stake pool) holds a high amount of
stake, exceeding their valuation for the system. A centralized PoS system is
susceptible to threats such as denial of service (DoS), blacklisting, and
double-spending Zhang et al. (2019), etc.

Among the multiple causes of centralization in PoS, two major causes are (1)
Centralization due to initial stake distribution — called a _bootstrapping_
protocol, and (2) centralization due to institutions like exchanges and
staking pools. This paper primarily focuses on bootstrapping. We argue that
ineffective bootstrapping can cause centralization in PoS, implying the
crucial role of bootstrapping protocol. Thus, there is a need to analyze
decentralization via bootstrapping protocols in the presence of strategic
players.

### Our Approach

##### The Bootstrapping Model.

We begin by providing a novel construction of the bootstrapping of a PoS-based
blockchain as a game, namely $\Gamma_{\textsf{bootstrap}}$ (Section 4) among
participating players. We propose that the bootstrapping protocol should
satisfy: (i) _Individual Rationality_ (IR) – participating in the protocol
should give higher utility than abstaining from it; (ii) _Nash Incentive
Compatibility_ (IC) – following the bootstrapping protocol should be a Nash
Equilibrium for all players and, (iii) _Decentralization_ (DC), – the PoS
system should be decentralized after the bootstrapping protocol. We define a
bootstrapping protocol to be _ideal_ if it simultaneously satisfies all three
conditions (Definition 4.3.3). We need a measure to quantify centralization in
PoS System to assert decentralization.

##### Quantifying Centralization.

An ideal bootstrapping protocol’s central goal must be to distribute the
initial stake such that the PoS system is not centralized. Towards this, we
use the notion of $(\tau,\delta,\epsilon)-$decentralization Kwon et al.
(2019). Naturally, to quantify centralization, we require an effective metric.
It must be resilient to a player’s _strategic_ behaviour. Unfortunately, prior
works on quantifying centralization in blockchains, such as using the Gini
coefficient Gini (1921); Gochhayat et al. (2020), the Nakamoto Coefficient Lin
et al. (2021) or Entropy-based metrics Wu et al. (2019) are susceptible to
manipulations by players who might game the metric to falsely make the system
appear decentralized.

#####  C-NORM.

Given $\Gamma_{\textsf{bootstrap}}$, the definitions of IR and IC follow the
standard template. However, it is challenging to construct a strategyproof
centralization metric. To this end, we propose the construction of a
$\mathcal{G}$ – directed cyclic graph– DAG-based representation of PoS System
transactions. $\mathcal{G}$ aims to represent (i) the current state and (ii)
the history of the PoS system. With $\mathcal{G}$, we propose our novel
centralization metric, C-NORM (Section 5.2). C-NORM incorporates the strategic
behaviour of the players. Moreover, the metric also captures the dynamic
arrival of the players to the PoS system, which corresponds to dynamic updates
to $\mathcal{G}$.

##### The Centralization Game $(\Gamma_{\textsf{cent}})$.

We introduce $\Gamma_{\textsf{cent}}$, a game that provides a unified
framework to measure the effectiveness of any centralization metric, given
$\mathcal{G}$ (Section 5.3). $\Gamma_{\textsf{cent}}$ is a two-player game
between a Metric Challenger and a Metric Descriptor. If the Metric Descriptor
can distinguish between the centralized and decentralized (less centralized)
systems presented by the challenger, then the descriptor wins the game.
Otherwise, the metric is inept. We show that for famous blockchain
centralization metrics – Nakamoto coefficient Lin et al. (2021), Entropy Wu et
al. (2019), and Gini Coefficient Gochhayat et al. (2020), the Metric
Descriptor loses the game. However, for C-NORM, the Metric Descriptor wins
with a very high probability (Theorem 1). We also show that if a protocol is
IC and has low C-NORM, then it satisfies our definition of
$(\tau,\delta,\epsilon)-$ Decentralized (Theorem 2).

Analyzing Bootstrapping Protocols. Given
$\Gamma_{\textsf{bootstrap}},\mathcal{G}$ and $\Gamma_{\textsf{cent}}$, we
proceed to discuss if the existing bootstrapping protocols are ideal or not
(Section 6). First, we prove that _Airdrop_ Fan et al. (2023) and _Proof-of-
Burn_ (PoB) Karantias et al. (2020) are not ideal as they do not satisfy IC
and IR, respectively. Second, we prove that a PoW-based bootstrapping
protocol222The recent Ethereum Merge Ethereum (2022) motivates the study of
PoW-based bootstrapping for PoS blockchains. (abbreviated as W2SB)
simultaneously satisfies IR, IC, and DC and hence is ideal. Table 1 summarizes
these results.

We validate our findings in Section 7 with experimental simulations of PoS
blockchains bootstrapped with W2SB for different valuation distributions and
duration to achieve different levels of decentralization based on the random
arrival of the players.

##### Our Contributions.

We make the following contributions.

  1. (1)

We introduce a game-theoretic model for bootstrapping of PoS System. Our model
incorporates (i) dynamic participation and (ii) Sybil-attacks by allowing
coalition formation.

  2. (2)

We define a bootstrapping protocol as ideal if it simultaneously satisfies IR
and IC and $(\tau,\delta,\epsilon)$-DC (Definition 4.3.3).

  3. (3)

To verify if a protocol is decentralized, we introduce C-NORM (Definition
5.2). The definition relies on a Directed Acyclic Graph (DAG) based modelling
of the PoS system.

  4. (4)

We model the centralization game $\Gamma_{\textsf{cent}}$ to evaluate
effectiveness of centralization metrics in Section 5.3. We show that when the
metric descriptor chooses other metrics, they do not win the game while using
C-NORM they win the game $\Gamma_{\textsf{cent}}$ with very high probability
(Theorem 1). We also show that a PoS System is
$(\tau,\delta,\epsilon)-$decentralized if C-NORM value is low (Theorem 2).

  5. (5)

Finally, we analyze existing bootstrapping protocols to show that Airdrop is
not IC (Claim 1) and Proof-of-Burn is not IR (Claim 2). We then show that W2SB
is IR and IC (Lemma 6.2) and can achieve any C-NORM value in $(0,1]$ within a
finite number of rounds (Theorem 3) Based on these results, we show that W2SB
is an ideal bootstrapping protocol (Theorem 4).

Bootstrapping Protocol IR IC DC Ideal Bootstrapping AirDrop Fan et al. (2023)
✓ $\times$ $\times^{\star}$ $\times$ Proof-of-Burn Karantias et al. (2020)
$\times$ ✓ ✓† $\times$ W2SB ✓ ✓ ✓ ✓ $\dagger$: Depends on the parent
cryptocurrency $\star$: We conjecture that it is decentralized, but no
existing metric can yet assert to it

Table 1. W2SB compared with existing bootstrapping protocols. An Ideal
bootstrapping protocol satisfies IR, IC, and DC.

##  2\. Related Work

##### Bootstrapping in Blockchains.

Proof-of-Stake (PoS) blockchain protocols employ various methods to bootstrap
their networks, e.g., Initial Coin Offering (ICO) de Andres et al. (2021);
Momtaz (2020), Airdrop Fan et al. (2023), Proof-of-Burn Karantias et al.
(2020), and others Kim et al. (2021); Kokoris-Kogias et al. (2018); Leung et
al. (2019) – which focus on optimizing miners computational, communication,
and memory costs. Airdrops are vulnerable to Sybil Attacks Liu and Zhu (2022)
and Privacy Leaks Harrigan et al. (2018). Smartdrop Johnston et al. (2018),
lacks a game-theoretic analysis of its security and effectiveness. Ethereum
Buterin et al. ([n.d.]); Wood (2014), originally a Proof-of-Work (PoW)
cryptocurrency, transitioned to a PoS-based blockchain in 2022 during
the“Merge event” Ethereum (2022). Though it was not by design, Ethereum’s PoW
to PoS transition appears serve as a good bootstrapping protocol.

Game-theoretic analysis of blockchain protocols is gaining traction Alkalay-
Houlihan and Shah (2019); Chung and Shi (2023); Grossi (2022); Karakostas et
al. (2023); Roughgarden (2020, 2021) but still lacks a formal game-theoretic
framework for analyzing bootstrap protocols.The need for such a formal study
is crucial as bootstrapping is one of the significant causes of centralization
in PoS-based blockchains Sultanik et al. (2022); Sai et al. (2021); Schout
(2020).

##### Centralization in Networks and Multi-Agent Systems.

There has been extensive research on quantifying centralization in different
multi-agent systems Istrate and Bonchis (2022); Kosny and Skibski (2023).
While some of these centrality measures and analyses are for dynamic systems
such as social networks, where agents do not behave strategically to game the
system Becker et al. (2021); Mazalov et al. (2016); Narayanam and Narahari
(2011), there are centrality measures that discuss rational parties who try to
game the metric Istrate et al. (2020); Waniek et al. (2021); Was et al.
(2020). Among these, Istrate _et al._ Istrate et al. (2020) discuss parties
trying to game the system through coalitions and analyze network
centrality.However, the work quantifies centrality in networks, while we
quantify in a system with each node having its own private and public
valuations, forming coalitions among themselves (i.e., Sybil attacks).
Moreover, it is intractable to compute the metric. Other metrics such as
Waniek et al. (2021) model the game as a Stackelberg Game where parties are
trying to spoof the metric. However, the players are restricted to changing
links in the networks, unlike our system, where they can report false
valuations and perform stake redistribution (equivalent to weight
redistribution among network nodes). Several metrics for measuring
centralization exist in the blockchain literature as well Gini (1921);
Gochhayat et al. (2020); Kusmierz and Overko (2022); Lin et al. (2021); Wu et
al. (2019). E.g., metrics based on the Gini Coefficient Gini (1921) or the
Nakamoto Coefficient Lin et al. (2021). We analyze the efficacy of these
metrics in Section 5 and show that they fail in particular cases.

Kwon _et al._ Kwon et al. (2019) focuses on achieving perfect decentralization
in blockchain protocols such as PoW, PoS, and dPoS. We note two significant
differences between Kwon et al. (2019) and our work. (i) we analyze
centralization caused during bootstrapping whereas they analyze centralization
in PoW and PoS systems post-bootstrapping. (ii) Our utility model penalizes
centralizationwhile Kwon _et al._ assume the protocol is Sybil-resistant,
which is a strong assumption.

Rauchs and Hileman Rauchs and Hileman (2017) study centralization in the
application layer due to the concentration of stake with exchanges and third-
player wallet services. Further, there also exists analysis on the governance
layer of different blockchain protocols Azouvi et al. (2018); Gervais et al.
(2014). Note that C-NORM is more general, encompassing the entire PoS system
and capturing the stake distribution across different accounts. Other forms of
centralization, e.g., due to increased storage costs Guo et al. (2019); Raman
and Varshney (2021), are out of the scope of this paper. For further details,
an extensive survey on blockchain centrality measures can be found in Sai et
al. (2021).

##  3\. Preliminaries

In this section, we (i) summarize relevant blockchain preliminaries and (ii)
existing centralization metrics in the literature.

###  3.1. Blockchain Preliminaries

A blockchain system $\mathcal{B}$ is a decentralized ledger maintained by
interested players $\mathcal{P}=\\{p_{1},p_{2},\ldots,p_{n}\\}$. They need to
agree on the state of the ledger which can be achieved through Proof-of-Work
(PoW), Proof-of-Stake (PoS), Proof-of-Burn (PoB) etc. We briefly discuss such
consensus algorithms below.

##### Proof-of-Work (PoW) Nakamoto (2009).

A blockchain-based on PoW comprises a consensus mechanism in which players
(aka _miners_) compete to solve a cryptographic puzzle to propose the next
block. A miner mines blocks in discrete periods called _round_. If a miner’s
query is successful, it gets a reward $r_{\text{b}}$ in that round. Each miner
$p_{i}$’s probability of mining a block is $a_{i}$, the fraction of the total
mining power it controls. Next, let $\chi$ denote the expected cost incurred
per unit of mining power in a single round. If the total mining power is $M$,
then the cost incurred in one round by miner $p_{i}$ is $a_{i}M\cdot\chi$. The
expected payoff for the miner $i$ becomes $a_{i}\cdot(r_{\text{b}}-M\chi)$.

##### Proof-of-Stake (PoS) David et al. (2018).

The energy-intensive nature of PoW has led to PoS-based blockchains gaining
traction due to their significantly lower carbon footprint Kapengut and
Mizrach (2023); Platt et al. (2021). In PoS, players ‘enroll’ themselves for
block creation by locking their _stake_. Then, the probability of a player
getting selected to propose the next block is proportional to its relative
stake. PoS-based blockchains face several challenges, including
centralization, fairness, and security concerns Schout (2020). Notice that a
‘decentralized’ PoS-based blockchain is one where each player has a stake
proportional to its _valuation_ for the system. This valuation, in theory, is
reflected by the stake held (equivalently, the money invested) by the player.
Thus, for any player $i$, the ratio of the stake $\omega_{i}$ held by it and
its valuation $\theta_{i}$ should be the same for all $p_{i}$. We call this
ratio as a _true effective stake_ of a system, and for each player, $i$ denote
it as
$\beta_{i}=\frac{\omega_{i}/\theta_{i}}{\sum_{j\in[n]}\omega_{j}/\theta_{j}}$.
PoS blockchains require initial stakes distribution for the consensus
mechanism to start, achieved through bootstrapping. We now discuss some
bootstrapping protocols employed in practice.

##### Proof-of-Burn (PoB) Karantias et al. (2020).

In PoB, players ‘burn’ a fraction of their cryptocurrency i.e. transfer of the
currency to a provably unspendable address Karantias et al. (2020). In PoB
bootstrapped PoS system, a player burns $y$ fraction of a certain old
cryptocurrency and obtains $x$ fraction of bootstrapped cryptocurrency’s
tokens.

##### Airdrop Liu and Zhu (2022).

Airdrop distributes digital tokens/assets to eligible players. The eligibility
is based on certain predetermined conditions specified by the cryptocurrency
organization (e.g., posting a tweet). Airdrop, while useful for marketing a
new cryptocurrency, suffers from privacy problems and is prone to _Sybil
attacks_ Harrigan et al. (2018); Liu and Zhu (2022).

##### Sybil Attack Douceur (2002).

Sybil attack is when an attacker creates pseudo-identities that enable them to
gain higher utility.In blockchain systems, a Sybil attack increases the reward
the attacker obtains. A blockchain with player $p_{i}$ and pseudo-identities
$e_{1},e_{2},\ldots,e_{k}$ and utility for $k$ being $U_{k}$ is prone to
Sybil-attack if $U_{p_{i}}<\sum_{j=1}^{k}U_{e_{j}}$.

###  3.2. Centralization Metrics

The following metrics are used to study centralization in blockchains.

##### Entropy-based Centralization.

It is an information-theoretic metric to quantify centralization Kusmierz and
Overko (2022); Lin et al. (2021); Wu et al. (2019). The entropy of a system
$H$, normalized to the range $[0,1]$ is

$H:=-\frac{1}{\log(|P|)}\sum_{p_{i}\in P}\beta_{i}\log(\beta_{i})$ (1)

##### Gini Coefficient.

It is a classic measure from economics that quantifies inequality in resource
distribution using $G\in[0,1]$ where $0$ represents perfect equality, and $1$
represents maximal inequality. The Gini coefficient for a blockchain system
$\mathcal{B}$ is Gini (1921); Gochhayat et al. (2020); Kusmierz and Overko
(2022); Lin et al. (2021)

$G:=\frac{1}{2|P|}\sum_{p_{i}\in P}\sum_{p_{j}\in P}|\beta_{i}-\beta_{j}|$ (2)

##### Nakamoto Coefficient.

Nakamoto coefficient Kusmierz and Overko (2022); Lin et al. (2021); Srinivasan
(2017), a recent metric for measuring decentralization, is the minimum number
of players in the system that together control the majority (i.e. more than
some threshold $\tau_{th}\in[0,1]$) of the system. $\tau_{th}$ is protocol-
dependent and is usually the minimum control required to disrupt the protocol.
Mathematically, for a blockchain system $\mathcal{B}$, $N$ is,

$N:=\min\left\\{|A|\;:\;\sum_{p_{i}\in A}\beta_{i}>\tau_{th},A\in
2^{P}\right\\}$ (3)

##  4\. Bootstrapping in PoS System

In this section we formulate bootstrapping as a game $\Gamma_{bootstrap}$ to
study the influence of rational agents (which can launch sybil attack) on the
performance of the bootstrapping protocol. Following this, we discuss the
game-theoretic properties desired from this Game and correspondingly define
the requirements for a bootstrapping protocol to be an _ideal bootstrapping
protocol_.

Let $\Pi$ be a bootstrapping protocol to mint the initial coins in PoS System,
which runs till round $T$, which we call _stopping time_. After $T$ rounds,
$\Pi$ terminates, and the system runs a PoS protocol. Each player $p_{i}\in P$
has a private valuation of PoS System, $\theta_{i}\in\mathbb{R}_{\geq 0}$, on
joining the system. $\theta_{i}$ indicates the amount that player $p_{i}$ will
prefer to invest in PoS System. The private valuation profile of all the
agents is $\bm{\theta}:=(\theta_{1},\theta_{2},\ldots,\theta_{n})$.

Each player $p_{i}$ elicits its valuation as
$\hat{\theta}_{i}\in\mathbb{R}_{\geq 0}$ (through some preference aggregation
procedure which is part of $\Pi$). E.g., by simply obtaining the coins of the
underlying cryptocurrency. The set of reported valuations is
$\bm{\hat{\theta}}:=(\hat{\theta}_{1},\hat{\theta}_{2},\ldots\hat{\theta}_{n})$.
In a PoS System, the goal is to ensure each player holds a stake proportional
to its valuation of the system (see discussion in Section 3.1). Thus, $\Pi$
must ensure that at the end of round $T$, the stake held by each player
$p_{i}$ is proportional to their reported valuation of the system, i.e.,
$\hat{\theta}_{i}$.

Moreover, a subset of players may collude to earn coins more than their fair
share. We assume that the valuations are _additive_ , so the total true
(private) valuation of any collusion set $A\subset P$ is
$\vartheta(A)=\sum_{i\in A}\theta_{i}$. To model such strategic behavior, our
model incorporates colluding as part of the player’s strategy space.
Certainly, collusion may lead to centralization in the PoS System. We assume
that $\Omega$ is a measure available with the PoS System to quantify
centralization. The PoS System $\mathcal{B}$ is represented by the tuple
$(\Pi,\Omega,P)$.

###  4.1. Strategy Space

As players are strategic, each player $p_{i}$’s goal in the system
$\mathcal{B}$ is to maximize its stake while keeping the recorded value of the
system’s centralization (or $\Omega$) as low as possible. Towards this, it
makes two choices, (1) $\hat{\theta}_{i}$ and (2) if it should collude with
the others.

##### Sybil-attack.

The set $P$ denotes all the identities part of the PoS System. However, if
$p_{i}$ has launched a Sybil attack and created pseudo-identities, we
represent them in our game as partition sets — each partition being the group
of sybil identities (sybil-group) of one rational player. These sybil-groups
are labelled and represented by the set
$\mathcal{A}:=\\{A_{1},A_{2},\ldots,A_{n}\\}$ where $A_{i}$ is the partition
(name of the set) which $p_{i}$ is part of. $\mathcal{A}$ follows following
three properties: (1) $|A_{i}|\in\\{1,\ldots,n\\}$. (2) $A_{i}\cap
A_{j}=\emptyset$ if $p_{i}$ and $p_{j}$ are in different partition and
$A_{i}=A_{j}$ otherwise. (3) $\cup_{i=1}^{z}A_{i}=P$. Through such collusion,
players can perform redistribution of stake, making the system appear more
decentralized to the centralization metric $\Omega$. The redistribution of the
stake cannot increase the allocated stake; therefore, $\sum_{i\in
A}\hat{\theta}_{i}$ remains constant. To summarize, the strategy space for
$p_{i}$ is $M=\mathbb{R}_{\geq 0}\times\;\mathcal{A}_{i}$; a cartesian product
of reported stake and set of all possible partitions containing $p_{i}$.

###  4.2. Utility Structure

Given a PoS System system $\mathcal{B}$, we now quantify players’ utilities.
Each player’s utility depends on (1) $\Pi$ and (2) the level of system
centralization (measured by $\Omega$), as the exchange rate for the
cryptocurrency and, therefore, the utility drops for a more centralized (and
therefore prone to attacks and censorship) cryptocurrency.

The earned reward for any player $p_{i}$ depends on its reported valuation and
the net gain of the PoS system. This reward is the difference between the
total collective rewards made by the PoS System ($r_{\text{block}}$) and the
total cost incurred by it ($b_{\text{spent}}$). We capture the loss in the
stake’s external value due to centralization via a function $g(\theta_{i})$
that is non-decreasing in $\theta_{i}$. Thus, for the described setup, the
utility for each player $p_{i}\in P$ with strategy ($\hat{\theta}_{i},A_{i}$)
is,

$U_{i}(\hat{\theta}_{i},\hat{\bm{\theta}}_{-i},A_{i},\mathcal{A}_{-i};\theta_{i}):=b\cdot\hat{\theta}_{i}-\Omega(\cdot)\cdot
g(\theta_{i})$ (4)

In Eq. 4, $\mathcal{A}_{-i}=\mathcal{A}/\\{A_{i}\\}$ and
$\hat{\bm{\theta}}_{-i}=\hat{\bm{\theta}}/\\{\hat{\theta}_{i}\\}$. The
reported valuation (aggregated through $\Pi$) is $\hat{\bm{\theta}}$ and the
true valuation is $\bm{\theta}$. The value $b$ depends on $\Pi$ and is
independent of player strategy. $b=(r_{\text{b}}-b_{\text{spent}})\cdot\gamma$
where $r_{\text{b}},b_{\text{spent}}$ and $\gamma$ are some constants
dependent on $\Pi$. The total reward for player $p_{i}$ is proportional to the
stake allocated to it (which in turn is proportional to $\hat{\theta}_{i}$).
The _cost of centralization_ depends on $g(\theta_{i})$, which is a non-
decreasing function of $\theta_{i}$ for player $p_{i}$. Note that $\Pi$ and
$\Omega$ would be typically fixed for a blockchain system under study, so
whenever clear from context, we omit mentioning these two in $U_{i}(\cdot)$.

As forming a collusion is part of strategy space, we can capture Sybil
attacks, i.e., a player creating multiple identities and forming collusion
with these identities.

In summary, the bootstrapping model for PoS system
$\mathcal{B}=(\Pi,\Omega,P)$ can be defined by
$\Gamma_{\textsf{bootstrap}}=\langle P,\bm{\theta},(U_{i})_{i\in[n]}\rangle$.

###  4.3. Ideal Bootstrapping Protocol

Given $\Gamma_{\textsf{bootstrap}}$, we now enlist the properties that $\Pi$
should satisfy to be an _ideal_ bootstrapping protocol.

####  4.3.1. Individual Rationality (IR).

– Each player $p_{i}$ prefers participating in $\Pi$ over abstaining from
participation. The strategy of abstaining for any player $p_{i}\in P$ is
$\hat{\theta}_{i}=0$ and $A_{i}=\\{i\\}$. Formally,

######  Definition  (Individual Rationality (IR)).

$\Pi$ is Individually Rational (IR) if $\forall p_{i}\in
P,\;\forall\bm{\theta}\in\mathbb{R}^{n}_{\geq
0},\;\forall\hat{\bm{\theta}}_{-i}\in\mathbb{R}^{n-1}_{\geq
0},\;\forall\mathcal{A}_{-i}$,

$U_{i}(\theta_{i},\hat{\bm{\theta}}_{-i},\\{i\\},\mathcal{A}_{-i};\theta_{i})>U_{i}(0,\hat{\bm{\theta}}_{-i},\\{i\\},\mathcal{A}_{-i};\theta_{i})$
(5)

####  4.3.2. Incentive Compatibility (IC)

IC requires, for each player $p_{i}$,$\hat{\theta}_{i}=\theta_{i}$ should give
maximum expected utility given all other players are reporting their true
valuations.

######  Definition  (Nash Incentive Compatibility (IC)).

$\Pi$ is nash incentive compatible if $\forall p_{i}\in
P,\forall\bm{\theta}\in\mathbb{R}^{n}_{\geq
0},\forall\hat{\theta}_{i}\in\mathbb{R}_{\geq 0},\forall
A_{i}\in\mathcal{A}_{i}$, where
$\mathcal{H}:=\\{\\{1\\},\\{2\\},\ldots,\\{n\\}\\}$

$\mathbb{E}[U_{i}(\theta_{i},\bm{\theta}_{-i},\\{i\\},\mathcal{H}_{-i};\theta_{i})]\geq\mathbb{E}[U_{i}(\hat{\theta}_{i},\bm{\theta}_{-i},A_{i},\mathcal{{H}}_{-i};\theta_{i})]$
(6)

The expectation taken is over the randomness in the system due to (i) random
dynamic arrival of players and (ii) randomness of $\Pi$.

####  4.3.3. Decentralization.

Lastly, we desire that the PoS System be decentralized. For this, we motivate
our definition partially from (Kwon et al., 2019, Definition 4.1) along with
the condition of Sybil-resistance. We require (1) at least a fraction
$\tau\in(0,1]$ of the total players to have joined the system, (2) the _true
scaled stake_ 333In PoS blockchain $\mathcal{B}$,
$\beta_{\max}:=\max_{i\in[n]}\beta_{i}$ and $\beta_{\delta}:=\beta_{r}$ where
$p_{r}$ is $\delta^{th}$ percentile player when arranged in decreasing order
of stake. for each player $p_{i}$ should be as close to each other as possible
(3) the system should be Sybil-resistant.Our definition differs from (Kwon et
al., 2019, Definition 4.1) as we capture each player’s valuation using _scaled
stake_ instead of the total stake held by the player. We also impose a
condition of Sybil-proofness. We define decentralization as follows:

######  Definition  ($(\tau,\delta,\epsilon)-$Decentralization).

A PoS based blockchain system is said to be $(\tau,\delta,\epsilon)-$
_decentralized_ for $\tau\in(0,1]$, $\delta\text{ (percentile)}\in[0,100]$ and
$\epsilon\in\mathbb{R}_{\geq 0}$ if it follows:

  * •

Minimum Participation: The current set of players joined the PoS system by
round $t$, $P_{t}$, is such that $\frac{|P_{t}|}{|P|}\geq\tau$.

  * •

Proportionality: The ratio of max true scaled stake ($\beta_{max}$) and the
$\delta-$percentile true scaled stake ($\beta_{\delta}$) is
$\frac{\beta_{max}}{\beta_{\delta}}\leq 1+\epsilon$.

  * •

Sybil-proofness: The ratio $\frac{\beta_{max}}{\beta_{\delta}}$ cannot be
reduced by a single player forging identities without decreasing its utility.

Now we define an _Ideal bootstrapping_ protocol for a PoS System.

######  Definition  (Ideal Bootstrapping Protocol).

Given a set of players $P$ participating in a PoS System with bootstrapping
protocol $\Pi$, we call $\Pi$ as an _ideal bootstrapping protocol_ under a
proposed metric $\Omega$ of measuring centralization of the PoS system, if it
satisfies:

  * •

$\Pi$ is _individually rational_ for each player $p_{i}\in P$.

  * •

$\Pi$ is Incentive Compatible, i.e. $\hat{\bm{\theta}}=\bm{\theta}$ is
equilibrium strategy.

  * •

After executing $\Pi$, the PoS System is
$(\tau,\delta,\epsilon)-$Decentralized.

To measure how decentralized a PoS system is, we need a metric to quantify
centralization, which is the focus of the next section.

##  5\. Measuring Centralization in a PoS System

In this section we (i)model a given PoS System $\mathcal{B}$ as a _PoS System
Graph_ (PSG), (ii) discuss C-NORM and its properties..

###  5.1. PoS System Graph

Given a complete history of transactions in a PoS system $(\mathcal{B})$
(which is available as a public ledger), we discuss how we construct a PSG
$(\mathcal{G})$ that captures strategic redistribution of stake among the
colluding players. We later use $\mathcal{G}$ to define our metric C-NORM.

####  5.1.1. Motivation.

The purpose of the PSG $(\mathcal{G})$ is to capture the following two
properties of the PoS System: (1) the current state stake owned by a
particular player – captured through the weights of each vertex in
$\mathcal{G}$ and (2) the history, i.e., redistribution of stake – captured
through the weighted directed edges between different vertexes. Additionally,
$\mathcal{G}$’s construction must only depend on publicly available
information about $\mathcal{B}$.

####  5.1.2. PoS System Graph (PSG).

The Graph $\mathcal{G}=([n],C,W)$ is a tuple consisting of a set of vertices
$[n]$ where each vertex corresponds to a player in the system. Each vertex
(player) $p_{i}$ has a total stake $c_{i}$ with it. We assign weights to these
nodes as $\bm{C}=(c_{1},c_{2},\ldots,c_{n})$. To capture the transactions
summary between players $p_{i}$ and $p_{j}$, we place a weighted directed edge
from vertex $i$ to $j$ with weight $w_{i,j}$. The set $W$ contains $w_{i,j}$
which are determined as follows:

  * $\bullet$

Define $\sum t_{i,j}$ as net positive transaction from $p_{i}$ (currently
having stake $c_{i}$) to $p_{j}$ (with stake $c_{j}$) and $\sum t_{j,i}$ as
net positive transaction from $p_{j}$ to $p_{i}$. If $\sum t_{i,j}>\sum
t_{j,i}$ then there exists an edge from $p_{i}$ to $p_{j}$ with weight
$w_{i,j}=\sum t_{i,j}-\sum t_{j,i}$ (see Figure 4 in Appendix H).

  * $\bullet$

If $\sum t_{i,j}=\sum t_{j,i}$ then there is no connection between $p_{i}$ and
$p_{j}$ i.e. $w_{i,j}=w_{j,i}=0$. By extension, $w_{i,i}=0$ for all $i\in[n]$.

  * $\bullet$

Constructing such a graph might lead to a cycle (e.g. when $p_{1}$ transfers
to $p_{2}$, $p_{2}$ transfers to $p_{3}$ and $p_{3}$ transfers to $p_{1}$). In
such cases, a cycle-elimination procedure converts the graph to a Directed
Acyclic Graph (DAG).

###  5.2. C-NORM: Quantifying Centralization in a PoS Blockchain System

We remark that most existing centralization metrics fail to capture either the
collusion of players or the valuation of a player while calculating the
centralization metric. A system is decentralized if444this notion of
decentralization follows from the idea of proportional inceitive towards
security (incentive to maintain security in PoS for any player is proportional
to their valuation of the system). It has not been proven or discussed if this
notion of valuation-proportional stake is necessary, but it is sufficient. the
stake held by each player is proportional to their valuation of the system. We
propose a new metric for measuring centralization in a PoS System. Our metric
uses the PoS system graph $\mathcal{G}=([n],C,W)$, a PSG derived from
$\mathcal{B}$, as described in Section 5.1.

Towards quantifying centralization, we first calculate the _effective stake_
of a player – capturing the net stake and the transaction value between the
player and its neighbours in $\mathcal{G}$. Considering $nbr(i)$ to be the set
of vertices adjacent to vertex $i$, the effective stake $\omega_{i}$ of player
$p_{i}$ is calculated as: $\omega_{i}:=c_{i}+\sum_{j\in
nbr(i)}w_{j,i}-\sum_{j\in nbr(i)}w_{i,j}$.

_Effective stake per unit of valuation_ is denoted by
$\frac{\omega_{i}}{\theta_{i}}$. For each $p_{i}\in P$, the normalized
effective stake is called _scaled stake_ , denoted by $\beta_{i}$.

$\beta_{i}(\theta):=\frac{\omega_{i}/\theta_{i}}{\sum_{j\in[n]}\big{(}\omega_{j}/\theta_{j}\big{)}}$
(7)

Since the allocated stake should be proportional to the reported valuation of
each player $p_{i}$, $\frac{\omega_{i}}{\theta_{i}}$ should be the same for
all players. For an IC mechanism $\Pi$, we should ideally have
$\frac{\omega_{i}}{\theta_{i}}=\frac{\omega_{j}}{\theta_{j}}\;\forall\;i,j\in[n]$.
Thus, the scaled stake should have the same value for each player in the PoS
system for the system to be fully decentralized. Upon calculation, we find
that $\beta_{i}$ should (in the ideal case) be $\frac{1}{n}$. Thus, for any
player $p_{i}$, the “error” is the deviation of their scaled stake from this
target value (in a decentralized system) of $\frac{1}{n}$. Hence, we define
our metric for measuring centralization as the summation of $L_{1}$-Norm of
this deviation for each player. The normalization factor $\frac{1}{2}$ maps
the range of $\Omega$ to $[0,1]$. Formally,

######  Definition  (C-Norm $(\Omega)$).

For a PoS system with player set $P$, PoS system graph $G$ the C-Norm of the
system $\Omega:[n]\times C\times W\rightarrow[0,1]$ is defined over
$\bm{\theta}$ as
$\Omega(\bm{\theta}):=\frac{1}{2}\sum_{j=1}^{[n]}\Big{|}\beta_{j}(\bm{\theta})-\frac{1}{n}\Big{|}$.
The centralization of the system in the worst-case is $\Omega^{\star}$ as:

$\Omega^{\star}:=\max_{\bm{\theta}|\theta_{i}>0\forall
i\in[n]}\frac{1}{2}\sum_{j=1}^{[n]}\Big{|}\beta_{j}(\theta)-\frac{1}{n}\Big{|}$
(8)

##### Note.

While constructing the PSG $\mathcal{G}$, the order of elimination of cycles
using the CycleElimination Algorithm (see Appendix H) has no effect on the
value of C-NORM. This is because the difference between $\sum_{j\in
Nbr(i)}t_{i,j}-\sum_{j\in Nbr(i)}t_{j,i}$ remains the same and therefore
$\omega_{i}$, and by extension, $\Omega^{\star}$ does not change.

##### Need for C-Norm:

C-NORM has few advantages over previous metrics. While other metrics evaluate
centralization based on the stake of each player, C-NORM include player’s
_valuation_ of the system, therefore defining effective stake. In addition,
while other metrics use the current state of the system, C-NORM uses previous
state changes (transactions) as well, which is captured through PoS System
Graph. Next, we formally argue why the proposed metric is good at capturing
centralization in a PoS System.

###  5.3. Evaluating Decentralization Metrics

We begin by introducing a novel _centralization game_ , which assesses the
efficacy of a given centralization metric for a PoS System. We illustrate with
examples that widely used metrics (discussed in Section 3) namely Gini
coefficient Gini (1921); Gochhayat et al. (2020) ($G_{c}$), Nakamoto
Coefficient Jia et al. (2022); Srinivasan (2017) ($N$) and Entropy-based
metrics Kusmierz and Overko (2022); Wu et al. (2019) ($H$) fail to capture
centralization in the proposed game. A strategic player can create instances
where metrics fail to detect centralization, whereas C-NORM detects them.
Next, we also show that any PoS System bootstrapped using an IC $\Pi$ and a
small C-NORM satisfies $(\tau,\delta,\epsilon)-$decentralization (Definition
4.3.3).

pt$\Gamma_{\textsf{cent}}=\langle\\{M_{C},M_{D}\\},S_{SA},e_{r},Q(\cdot),\kappa\rangle$
Metric Descriptor $(M_{C})$: ❶ Samples $s_{0}\in S_{SA}$ and sets
$s_{1}:=e_{r}(s_{0})$ such that $(s_{0},s_{1})\in S_{SA}\times S_{NSA}$. ❷
Chooses $(a,b)\in_{R}\\{(0,1),(1,0)\\}$ and communicates $(s_{a},s_{b})$ to
$M_{D}$. Metric Challenger $(M_{D})$: ➀ Evaluates $v_{a}:=Q(s_{a})$ and
$v_{b}:=Q(s_{b})$. ➁ Distinguishes between $v_{a},v_{b}$ to get
$(a^{\prime},b^{\prime})$ using any program $\mathcal{D}$ by
$(a^{\prime},b^{\prime})\leftarrow\mathcal{D}(v_{a},v_{b})$. Success
Probability: Consider a random variable $D(Q)$, that takes value $1$ if
$M_{D}$ successfully guesses $(a,b)$ i.e. $a^{\prime}=a,\;b^{\prime}=b$ and
$0$ otherwise. For $\kappa\in\mathbb{Z}_{\geq 1}$ trials of
$\Gamma_{\textsf{cent}}$, we have $D_{\kappa}(Q)=1$ if all $\kappa$ trials are
successful. $M_{D}$’s success depends on the centralization metric it employs.
We have, Ineffective Metric: If $Q(\cdot)$ is an ineffective metric for
quantifying centralization, success probability will be as good as a random
guess across $\kappa$ trials. Formally, for $\kappa$ trials
$\Pr(D_{\kappa}(Q)=1)\leq\textsf{negl}(\kappa)$ Where $\textsf{negl}(\kappa)$
is a negligible function in $\kappa$. Effective Metric: If $Q(\cdot)$ is an
effective metric, then $M_{D}$ can distinguish between $(s_{0},s_{1})$ and
$(s_{1},s_{0})$ with very high probability. Formally,
$\forall\textsf{negl}(\kappa)$ $Pr(D_{\kappa}(Q)=1)>1-\textsf{negl}(\kappa)$
Figure 1. The Centralization Game

####  5.3.1. Centralization Game ($\Gamma_{cent}$).

The game has two players – Metric Descriptor $M_{D}$ and Metric Challenger
$M_{C}$. There are two types of PoS System. First, $S_{SA}$, which are
centralized systems, with players (part of the PoS System) launching Sybil
attacks to make them appear decentralized. It means $S_{SA}$ is a set of PSGs
which are DAGs with at least one directed edge (having non-negligible weight).
Second, $S_{NSA}$ are decentralized systems without Sybil attack.
Additionally, there exists an onto function $e_{r}:S_{SA}\longrightarrow
S_{NSA}$ which removes edges from the PSG $\mathcal{G}$ for the given
$s_{0}\in S_{SA}$.

The Game is repeated for $\kappa\in\mathbb{Z}_{\geq 1}$ trials. At any trial,
$M_{C}$ gives randomly shuffled samplings $s_{0}\in S_{SA}$ and
$s_{1}=e_{r}(s_{0})$. $M_{D}$ uses its centralization metric under analysis
$Q(\cdot)$ to find the centralization value for both $s_{0}$ and $s_{1}$ and
uses these values as inputs to any program $\mathcal{D}$ to report the
ordering which was chosen by $M_{C}$. $M_{D}$ is successful if it correctly
guesses the ordering for all $\kappa$ trials. We use
$\Gamma_{cent}:=\langle\\{M_{C},M_{D}\\},S_{SA},S_{NSA},e_{r},Q(\cdot),\kappa\rangle$
to refer to this centralization game. Figure 1 formally defines
$\Gamma_{cent}$.

##### Comparing the Success of Centralization Metrics in
$\Gamma_{\textsf{cent}}$.

We now analyze the existing metrics for quantifying centralization (refer
Section 3.2) along with C-NORM. Towards this, we first discuss the sampling
(say) $(s_{0},s_{1})$ by $M_{C}$ and then calculate the values $Q(s_{0})$ and
$Q(s_{1})$ for different metrics in Table 2. We then argue why any program
$\mathcal{D}$ cannot distinguish between $s_{0}$ and $s_{1}$ for other metrics
except for C-NORM.

######  Example 1 (Analysing centralization metrics using $\Gamma_{cent}$).

Consider the following steps.

  * $\bullet$

Step ❶. Consider $s_{0}$ such that the player set
$P=\\{p_{1},p_{2},\ldots,p_{7}\\}$ each currently holds stake
$C=\\{2,5,5,5,5,5,5\\}$ and private valuation
$\bm{\theta}=\\{2,5,5,5,5,5,5\\}$. However, there has been a redistribution of
stake among players where $p_{1}$ has distributed a stake of $5$ to both
$p_{2}$ and $p_{3}$, which means there is a directed edge from $p_{1}$ to both
$p_{2}$ and $p_{3}$ with weight $5$ each. The state $s_{1}=e_{r}(s_{0})$ is
the same set $P$ and $C$ without any edges between nodes.

  * $\bullet$

Step ❷. $M_{C}$ now samples randomly $(a,b)\in_{R}\\{(0,1),(1,0)\\}$ and sends
$(s_{a},s_{b})$ to $M_{D}$. The reported valuation of each player is the same
(proportional) to their allocated stake.

  * $\bullet$

Steps ➀ & ➁. Based on the metric being used by $M_{D}$, it calculates
$Q(s_{a})$ and $Q(s_{b})$. Now, if both values are different (w.l.o.g.,
$Q(s_{a})>Q(s_{b})$) then $s_{a}\in S_{SA}$ and thus $(a,b)=(1,0)$. However,
if $Q(s_{a})=Q(s_{b})$555E.g., if the metric does not account for transaction
history (represented through edges in $\mathcal{G}$) which might represent
stake-redistribution among colluding parties then $M_{D}$ cannot distinguish
between $s_{a},s_{b}$ (using metric $Q(\cdot)$) better than a random guess.
Without loss of generality, considering $s_{a}=s_{1}$ and $s_{b}=s_{0}$, we
tabulate the values $Q(s_{a})$ and $Q(s_{b})$ for different centralization
metrics – Gini Coefficient $G_{c}$ (Eq. 2), Nakamoto Coefficient $S_{N}$ (Eq.
3), Entropy $H$ (Eq. 1) and C-NORM $\Omega^{\star}$ (Eq. 8) in Table 2.

Note that with Example 1, we show scenarios where C-NORM captures the
centralization while the existing metrics fail to do so. With Theorem 1, we
show that C-NORM is able to distinguish between $s_{0}\in S_{SA}$ and
$s_{1}\in S_{NSA}$ for any $s_{0}\in S_{SA}$ and $s_{1}=e_{r}(s_{0})$ with
probability $1-\textsf{negl}(\kappa)$ for $\kappa$ trials. We show this by
constructing a distinguisher $D_{\kappa}(\cdot)$ using centralization measure
C-NORM which distinguishes between any $s_{0}\in S_{SA}$ and corresponding
$s_{1}\in S_{NSA}$. The proof is provided in Appendix A. Example 1 and this
result together show that C-NORM is an effective centralization metric.

######  Theorem 1.

In
$\Gamma_{cent}\langle\\{M_{C},M_{D}\\},S_{SA},e_{r},\Omega^{\star},\kappa\rangle$,
for any $(s_{0},s_{1})$ chosen by $M_{C}$ from the set
$\\{(s_{0},s_{1})\;:\;s_{0}\in S_{SA},s_{1}=e_{r}(s_{0})\\}$, if $M_{D}$ uses
metric C-NORM ($\Omega^{\star}$) then
$Pr(D_{\kappa}(\Omega^{\star})=1)>1-\textsf{negl}(\kappa)$ for some negligible
function $\textsf{negl}(\kappa)$. Here, $S_{SA}$ is the set of all Directed
Acyclic Graphs with at least one edge with non-negligible weight.

We observe as a corollary of Theorem 1 that C-NORM ($\Omega^{\star}$) also
provides _Sybil-proofness_ because it detects any attempts of Sybil-attack and
reflects it through a change in the value of $\Omega^{\star}$.

We next show how C-NORM fits into the description of an ideal bootstrapping
protocol. Towards this, in Theorem 2, we quantify decentralization (according
to Definition 4.3.3) if we measure centralization using C-NORM
$\Omega^{\star}$ of a PoS System with an IC bootstrapping protocol $\Pi$
provided $\Omega^{\star}$ is small. The proof is in Appendix B. Note that the
theorem provides sufficient (not necessary) conditions for the protocol to be
$(\tau,\delta,\epsilon)-$decentralized.

######  Theorem 2.

If a PoS System bootstrapped using an Incentive-Compatible (IC) protocol $\Pi$
and has C-NORM value $\Omega^{\star}_{1}\leq\alpha$, then the system is
$(\tau,\delta,\varepsilon)$-Decentralized for any $\delta\in[0,100]$ and
$\varepsilon=\frac{2\alpha}{\bm{\beta}_{\delta}}$.

Centralization Metric | PoS Systems
---|---
$s_{0}$ |  $s_{1}$
Nakamoto Coefficient $(N)$ Lin et al. (2021) |  $3$ |  $3$
Entropy $(H)$ Wu et al. (2019) |  $0.1405$ |  $0.1405$
Gini Coefficient $(G)$ Gochhayat et al. (2020) |  $0.0804$ |  $0.0804$
C-NORM $(\Omega^{\star})$ |  $0.6$ |  $0$
Table 2. Scores of existing centralization metrics compared with C-NORM
distinguishing between centralized $(S_{SA})$ and decentralized $(S_{NSA})$
PoS systems (refer Example 1).

Having introduced ideal bootstrapping and a centralization metric, we now
analyze some of the widely used bootstrapping protocols for IC, IR, and
decentralization properties.

##  6\. Analysis of Bootstrapping Protocols

In this section, we (i) prove why _Airdrop_ and _Proof-of-Burn_ are not Ideal
Bootstrapping protocols. (ii) formally show that a PoW-based variant
(abbreviated as W2SB) is an Ideal bootstrapping protocol.

###  6.1. Airdrop & Proof-of-Burn

Airdrop and PoB are protocols widely employed in Blockchain space
Bitcoinwhoswho (2018); BitcoinWiki (2018); Redman (2021); Chong (2023) in
different capacities including bootstrapping of protocols. For Airdrop and
Proof-of-Burn based bootstrapping to be ideal, these protocols must satisfy
all properties outlined in Definition 4.3.3. Based on this, in Claim 1, we
show that Airdrop is not an ideal bootstrapping protocol as it is not IC.

######  Claim 1.

An Airdrop-based bootstrapping protocol is not IC.

We defer the proof to Appendix C which uses the property of airdrop that
launching a Sybil attack does not affect utility as it does not increase
$\Omega$. It is because pseudo-identities have no on-chain transactions
establishing a relationship with the player launching the Sybil attack; thus,
the collusion is undetected. Furthermore, to show that Proof-of-Burn (PoB) is
not an ideal bootstrapping protocol, Claim 2 proves that it does not satisfy
IR.

######  Claim 2.

A Proof-of-Burn-based bootstrapping protocol is not IR.

For the proof, refer to Appendix D, we show that a PoB bootstrapped
cryptocurrency will always be upward-pegged (also referred to as one-way
pegging Narayanan et al. (2016)). Thus, a player’s maximum utility from PoB
bootstrapping in expectation is less than the utility from abstaining from the
protocol.

Motivated by the switch of Ethereum from PoW to PoS Ethereum (2022), we next
discuss the potential of PoW as a bootstrapping protocol.

###  6.2. W2SB: PoW-based Bootstrapping

Proof-of-Work (PoW) is a promising choice for a bootstrapping protocol as it
offers Sybil resistance by design (Section 3.1). PoW involves solving a
cryptographic puzzle to mine (propose) a block. Let $r_{\text{b}}$ be the
reward obtained by the miner666We refer to the strategic players as miners
here, as miners may be a more accessible term for PoW-based bootstrapping. on
successfully solving the puzzle. We consider that each miner $p_{i}\in P$
invests some computational resource (aka. mining power). Consider $m_{i}$ be
the mining power if the invested cost is according to their true valuation
(i.e. $m_{i}$ is mining power when $\hat{\theta}_{i}=\theta_{i}$). The total
mining power when all miners $p_{i}\in P$ report their true valuation is
$M=\sum_{i\in[n]}m_{i}$. The cost incurred per unit of mining power in a round
is $\chi$ in expectation. For IC, we require $p_{i}$ gets a higher reward with
mining power $m_{i}$ (corresponding to $\hat{\theta}_{i}=\theta_{i}$ ) than
with $m_{i}+a$ (corresponding to $\hat{\theta}_{i}>\theta_{i}$) or $m_{i}-a$
(corresponding to $\hat{\theta}_{i}<\theta_{i}$).

##### W2SB: IC and IR.

We abstract out a Proof-of-Work based bootstrapping protocol which runs for a
specified number of rounds (say $T$) and satisfies conditions stated in Lemma
6.2 as _W ork to Stake Bootstrap_ (W2SB). We show that W2SB is an Ideal
Bootstrapping Protocol. Towards this, we first show with Lemma 6.2 that W2SB
is both IC and IR (given some conditions on $\chi,r_{\text{b}}$ and $M$).

###### Lemma

W2SB satisfies IC and IR if (1) $\frac{\chi\cdot M}{r_{\text{b}}}\leq 1$ and
(2) $\frac{\chi\cdot M}{r_{\text{b}}}\geq(1-\frac{m_{\min}}{M})$ for
$m_{\min}=\min_{i\in[n]}m_{i}$.

Appendix E presents the formal proof. In the proof, for IR, we show that the
expected utility of any miner, in a single round, is greater than or equal to
the utility of abstaining if $\frac{\chi\cdot M}{r_{\text{b}}}\leq 1$. Next,
for IC, we show that eliciting $\hat{\theta}_{i}<\theta_{i}$ and $>\theta_{i}$
both gives a lower utility when $\frac{\chi\cdot
M}{r_{\text{b}}}\geq(1-\frac{m_{\min}}{M})$.

_Note._ Condition (1) in Lemma 6.2 is a natural requirement for PoW and states
that the mining difficulty must be such that the mining cost does not exceed
the expected reward from mining. On the other hand, condition (2) requires
that for any set of valuations $\bm{\theta}$, there does not exist a miner who
is incentivized to increase its mining power. We remark that these are mild
requirements and can be satisfied by changing $\chi$, which depends on the
difficulty of the cryptographic puzzle (a tunable parameter in PoW/W2SB).

##### W2SB: Decentralization.

To show that W2SB is decentralized, we show the existence of a finite $T$ for
an arbitrary $z\in\mathbb{R}_{>0}$ such that if W2SB is run for $T$ rounds,
$\Omega^{\star}<z$ We assume the dynamic participation of miners is according
to an arbitrary distribution $J\leftarrow\mathcal{Z}(\mu,\sigma)$. The CDF
($\Psi$) is defined over non-negative integers $\Psi:\mathbb{Z}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$. Likewise, the PMF($\psi$) is also defined
over the set of non-negative integers $\psi:\mathbb{Z}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ and made discrete using the PDF $f$ as
$\psi(J=q)=\int_{q-1}^{q}f(J=x)dx$. Under this setting, Theorem 3 proves that
for every $z\in(0,1]$, there exists a finite $T$ such that if we run W2SB for
$T$ rounds, we get $\Omega^{\star}\leq z$. We prove this by first upper
bounding $\Omega^{\star}$ for a given round $T$. Then, we show that $\exists
T$ for every $z$ such that $\Omega^{\star}\leq z$. Proof is in Appendix F.

######  Theorem 3.

In W2SB with miners arriving dynamically, given an arbitrary $z\in(0,1]$,
there always exists a finite $T$ such that after $\geq T$ rounds, we have
$\Omega^{\star}\leq z$.

From Theorem 2 and Theorem 3, we see that that W2SB satisfies
$(\tau,\delta,\epsilon)-$ Decentralization if it is run for $T$ rounds.

###### Corollary

W2SB on running for finite rounds is $(\tau,\delta,\epsilon)-$ Decentralized
given miners arrive dynamically according to some distribution with CDF
$\Psi(\cdot)$.

Having shown that W2SB satisfies IR and IC (under some conditions) and is
$(\tau,\delta,\epsilon)-$decentralized if run for $T$ rounds, we conclude in
Theorem 4 that W2SB is an ideal bootstrapping protocol.

######  Theorem 4.

W2SB is an _ideal bootstrapping protocol_ for
$(1-\frac{m_{\min}}{M})\leq\frac{\chi M}{r_{\text{b}}}\leq 1$, where
$m_{\min}=\min_{i\in[n]}m_{i}$.

###### Proof.

Lemma 6.2 implies IC and IR, and Corollary 6.2 implies
$(\tau,\delta,\epsilon)-$Decentralization. Hence, W2SB is Ideal Bootstrapping
Protocol by Definition 4.3.3 ∎

##  7\. W2SB: Experiments & Discussion

We now study the empirical change in C-NORM with a change in the number of
rounds, $T$. From Theorem 3, we know that W2SB reaches an arbitrary level of
decentralization (reflected by a decrease in C-NORM) for a sufficient $T$. Our
experiments aim to quantify C-NORM in a PoS system when W2SB is run for
different values of $T$. We begin by explaining our experimental setup,
followed by the results and their discussion.

$z$ |  $T$
---|---
$0.4$ |  $21$
$0.3$ |  $35$
$0.2$ |  $82$
$0.1$ |  $350$

Figure 2. C-NORM against rounds for different stopping time $T$ for
distribution $\mathcal{N}(7,3)$

##### Experimental Setup.

We simulate a PoS-based blockchain bootstrapped using W2SB. To empirically
measure C-NORM, we run W2SB for different stopping times
$T\in\\{100,200,500,750,1000\\}$, after which the PoS protocol is run for
remaining $(1000-T)$ rounds.

To capture each participant $i$’s dynamic arrival, we define the random
variable $\mathcal{J}_{i,t}$, which takes the value $1$ if $i$ joins the
system at round $t$ and 0 otherwise. We model $\mathcal{J}_{i,t}\sim Chi(k=3)$
from a chi-squared distribution with degree of freedom $k=3$. We believe this
distribution aptly exhibits participant arrival: sudden increase at first,
which peaks closer to the starting, followed by a gradual decrease and long
tail. We simulate three different instances where each player $p_{i}$ samples
its mining power $\phi_{i}$ (proportional to $\theta_{i}$) from (1) Gaussian
$\phi\sim\mathbf{\mathcal{N}}(7,3)$, (2) Uniform
$\phi\sim\mathbf{\mathcal{U}}(0,50)$, and (3) Exponential
$\phi\sim\mathbf{Exp}(\lambda=1)$ distributions.777We remark that the general
trend presented remains similar for different distribution parameters (refer
Appendix G).

##### Results & Inference.

Figure 2 depicts our results. We make the following key observations.

  1. (1)

In W2SB $\Omega^{\star}\to 0$ as $t\to\infty$.  From Figure 2, we observe that
if the W2SB runs for a sufficiently large $T$, then C-NORM tends to zero,
i.e., $\Omega^{\star}\to 0$.

  2. (2)

C-NORM does not decrease after Bootstrapping.  We observe that for rounds
$>T$, C-NORM saturates to a fixed value. This is because the PoS protocol does
not cause any change in C-NORM of the protocol, as desired.

  3. (3)

W2SB achieves $\Omega^{\star}\leq z$ for any $z>0$.  Any $z$ can be achieved
in a finite number of rounds in W2SB, as $\Omega^{\star}$ tends to $0$
asymptotically. The smaller value of $z$, the larger number of rounds
required. E.g., the green curve in Figure 2 with small $T$ is relatively
centralized.

##### Discussion.

Our results (both theoretical and empirical) show that W2SB is an Ideal
bootstrapping protocol that achieves sufficiently small C-NORM values. The
number of rounds for which W2SB is run ($T$) is a hyper-parameter that is
decided by protocol descriptor, allowing a tradeoff between higher levels of
decentralization (by increasing $T$) and lower energy consumption (by
decreasing $T$).

Ethereum Merge – an instance of W2SB. Ethereum also used PoW initially before
switching to PoS (aka the Merge Ethereum (2022)). Although the intention of
the Merge might not have been decentralized stake distribution, the
consequence was that Ethereum became a decentralized PoS-based blockchain.

##  8\. Conclusion & Future Work

##### Conclusion.

This work attempted to resolve the problem of centralization during
bootstrapping of PoS-based blockchains. Towards this, we first presented a
game-theoretic model of bootstrapping, $\Gamma_{\textsf{bootstrap}}$. With
this, we defined an ideal bootstrapping protocol, i.e., a protocol that
simultaneously satisfies IR, IC, and decentralization. To quantify
centralization, we introduced C-NORM which measures centralization in PoS-
based blockchains. We show the effectiveness of C-NORM against existing
metrics, using the centralization game, $\Gamma_{cent}$. We then analyzed
existing protocols under our model to show that while Airdrop and Proof-of-
Burn are not IC and IR, respectively, PoW-based bootstrapping (W2SB) is an
Ideal bootstrapping protocol. Our work lays the theoretical foundations for
further analysis of PoS-based blockchains.

##### Future Work.

Decentralized bootstrapping in PoS-based blockchains is relatively new. One
potential future direction is to explore verifiable random functions Micali et
al. (1999) for greater energy efficiency than W2SB. Another challenge with
PoS-based blockchains is that centralization may occur due to stake pools post
the bootstrapping phase. Tackling post-bootstrapping threats to
decentralization may be an interesting future direction to explore.

## References

  * (1)
  * mar (2023) 2023\.  CoinMarketCap.  coinmarketcap.com/.
  * Alkalay-Houlihan and Shah (2019) Colleen Alkalay-Houlihan and Nisarg Shah. 2019.  The Pure Price of Anarchy of Pool Block Withholding Attacks in Bitcoin Mining. In _AAAI_. 1724–1731.
  * Azouvi et al. (2018) Sarah Azouvi, Mary Maller, and Sarah Meiklejohn. 2018\.  Egalitarian Society or Benevolent Dictatorship: The State of Cryptocurrency Governance. In _Financial Cryptography Workshops_.
  * Becker et al. (2021) Ruben Becker, Gianlorenzo D’Angelo, and Hugo Gilbert. 2021\.  Maximizing Influence-Based Group Shapley Centrality. In _AAMAS_. 1461–1463.
  * Bitcoinwhoswho (2018) Bitcoinwhoswho. 2018\.  2 BTC BURNED IN 2018.
  * BitcoinWiki (2018) BitcoinWiki. 2018\.  Proof of burn.
  * Buterin et al. ([n.d.]) Vitalik Buterin et al. [n.d.].  Ethereum white paper.
  * Castro and Liskov (1999) Miguel Castro and Barbara Liskov. 1999.  Practical Byzantine fault tolerance. In _Proceedings of the Third Symposium on Operating Systems Design and Implementation_ (New Orleans, Louisiana, USA) _(OSDI ’99)_. USENIX Association, USA, 173–186.
  * Chong (2023) Julie-Anne Chong. 2023\.  OpenDAO Airdrops SOS on OpenSea Community.
  * Chung and Shi (2023) Hao Chung and Elaine Shi. 2023.  Foundations of transaction fee mechanism design. In _ACM-SIAM Symposium on Discrete Algorithms (SODA)_. 3856–3899.
  * David et al. (2018) Bernardo Machado David, Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2018.  Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain. In _International Conference on the Theory and Application of Cryptographic Techniques_.
  * de Andres et al. (2021) Pablo de Andres, David Arroyo, Ricardo Correia, and Álvaro Rezola. 2021.  Challenges of the market for initial coin offerings.  _International Review of Financial Analysis_ (2021).
  * Douceur (2002) John R. Douceur. 2002\.  The Sybil Attack. In _International Workshop on Peer-to-Peer Systems_.
  * Ethereum (2022) Ethereum. 2022.  The Merge.  ethereum.org/en/upgrades/merge/
  * Fan et al. (2023) Sizheng Fan, Tian Min, Xiao Wu, and Wei Cai. 2023\.  Altruistic and Profit-Oriented: Making Sense of Roles in Web3 Community from Airdrop Perspective. In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ (Hamburg, Germany) _(CHI ’23)_. Association for Computing Machinery, New York, NY, USA, Article 551, 16 pages.
  * Foundation ([n.d.]) ICON Foundation. [n.d.].  ICON Blockchain.  https://docs.icon.foundation/ICON-Whitepaper-EN-Draft.pdf
  * Garay et al. (2015) Juan Garay, Aggelos Kiayias, and Nikos Leonardos. 2015\.  The Bitcoin Backbone Protocol: Analysis and Applications. In _Advances in Cryptology - EUROCRYPT 2015_ , Elisabeth Oswald and Marc Fischlin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 281–310.
  * Gervais et al. (2014) Arthur Gervais, Ghassan O. Karame, Vedran Capkun, and Srdjan Capkun. 2014.  Is Bitcoin a Decentralized Currency?  _IEEE S &P_ 12 (2014), 54–60.
  * Gilad et al. (2017) Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017.  Algorand: Scaling Byzantine Agreements for Cryptocurrencies.  _Symposium on Operating Systems Principles_ (2017), 51–68.
  * Gini (1921) Corrado Gini. 1921\.  Measurement of Inequality of Incomes.  _The Economic Journal_ 31 (1921), 124.
  * Gochhayat et al. (2020) Sarada Prasad Gochhayat, Sachin Shetty, Ravi Mukkamala, Peter Foytik, Georges A. Kamhoua, and Laurent Njilla. 2020.  Measuring Decentrality in Blockchain Based Systems.  _IEEE Access_ 8 (2020), 178372–178390.
  * Goodman (2014) Lisl Marburg Goodman. 2014\.  Tezos : A Self-Amending Crypto-Ledger Position Paper.
  * Grossi (2022) Davide Grossi. 2022\.  Social Choice Around the Block: On the Computational Social Choice of Blockchain. In _AAMAS_. 1788–1793.
  * Guo et al. (2019) Zhaohui Guo, Zhen Gao, Haojuan Mei, Ming Zhao, and Jinsheng Yang. 2019.  Design and Optimization for Storage Mechanism of the Public Blockchain Based on Redundant Residual Number System.  _IEEE Access_ 7 (2019), 98546–98554.
  * Harrigan et al. (2018) Martin Harrigan, Lei Shi, and Jacob Illum. 2018.  Airdrops and Privacy: A Case Study in Cross-Blockchain Analysis. In _2018 IEEE International Conference on Data Mining Workshops (ICDMW)_. 63–70.
  * Istrate and Bonchis (2022) Gabriel Istrate and Cosmin Bonchis. 2022.  Being Central on the Cheap: Stability in Heterogeneous Multiagent Centrality Games. In _AAMAS_. 651–659.
  * Istrate et al. (2020) Gabriel Istrate, Cosmin Bonchis, and Claudiu Gatina. 2020\.  It’s Not Whom You Know, It’s What You, or Your Friends, Can Do: Coalitional Frameworks for Network Centralities. In _AAMAS_. 566–574.
  * Jia et al. (2022) Yongpu Jia, Changqiao Xu, Zhonghui Wu, Zichen Feng, Yaxin Chen, and Shujie Yang. 2022\.  Measuring Decentralization in Emerging Public Blockchains. In _2022 International Wireless Communications and Mobile Computing (IWCMC)_. 137–141.
  * Johnston et al. (2018) David A Johnston, Mark Thorsen, Henry Liu, Erik Kuebler, and Grace Torrellas. 2018.  The Smartdrop Model: How To Bootstrap Dapps and Protocols Without An ICO.  djohnstonec.medium.com/the-smartdrop-model-859888916d94
  * Kapengut and Mizrach (2023) Elie Kapengut and Bruce Mizrach. 2023.  An event study of the ethereum transition to proof-of-stake.  _Commodities_ 2, 2 (2023), 96–110.
  * Karakostas et al. (2023) Dimitris Karakostas, Aggelos Kiayias, and Thomas Zacharias. 2023\.  Blockchain Nash Dynamics and the Pursuit of Compliance. In _Proceedings of the 4th ACM Conference on Advances in Financial Technologies_ (Cambridge, MA, USA) _(AFT ’22)_. Association for Computing Machinery, New York, NY, USA, 281–293.  https://doi.org/10.1145/3558535.3559781
  * Karantias et al. (2020) Kostis Karantias, Aggelos Kiayias, and Dionysis Zindros. 2020\.  Proof-of-Burn. In _Financial Cryptography and Data Security_. 523–540.
  * Kim et al. (2021) Jae-Yun Kim, Junmo Lee, Yeonjae Koo, Sanghyeon Park, and Soo-Mook Moon. 2021.  Ethanos: Efficient Bootstrapping for Full Nodes on Account-Based Blockchain. In _EuroSys_. 99–113.
  * Kokoris-Kogias et al. (2018) Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. 2018.  OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding.  _IEEE S &P_ (2018), 583–598.
  * Kosny and Skibski (2023) Wiktoria Kosny and Oskar Skibski. 2023.  Axiomatic Analysis of Medial Centrality Measures. In _AAMAS_. 2188–2196.
  * Kusmierz and Overko (2022) Bartosz Kusmierz and Roman Overko. 2022.  How centralized is decentralized? Comparison of wealth distribution in coins and tokens. In _IEEE International Conference on Omni-layer Intelligent Systems (COINS)_. 1–6.
  * Kwon and Buchman ([n.d.]) Jae Kwon and Ethan Buchman. [n.d.].  Internet of blockchains.  v1.cosmos.network/resources/whitepaper
  * Kwon et al. (2019) Yujin Kwon, Jian Liu, Minjeong Kim, Dawn Song, and Yongdae Kim. 2019.  Impossibility of Full Decentralization in Permissionless Blockchains. In _ACM Conference on Advances in Financial Technologies_. 110–123.
  * Leung et al. (2019) Derek Leung, Adam Suhl, Yossi Gilad, and Nickolai Zeldovich. 2019\.  Vault: Fast Bootstrapping for the Algorand Cryptocurrency. In _NDSS_.
  * Lin et al. (2021) Qinwei Lin, Chao Li, Xifeng Zhao, and Xianhai Chen. 2021\.  Measuring decentralization in bitcoin and ethereum using multiple metrics and granularities. In _International Conference on Data Engineering Workshops (ICDEW)_. 80–87.
  * Liu and Zhu (2022) Zheng Liu and Hongyang Zhu. 2022.  Fighting Sybils in Airdrops.  _ArXiv_ abs/2209.04603 (2022).
  * Mazalov et al. (2016) Vladimir V. Mazalov, Konstantin E. Avrachenkov, L. I. Trukhina, and Bulat T. Tsynguev. 2016\.  Game-Theoretic Centrality Measures for Weighted Graphs.  _Fundam. Informaticae_ 145 (2016), 341–358.
  * Micali et al. (1999) Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. 1999\.  Verifiable random functions.  _40th Annual Symposium on Foundations of Computer Science_ (1999), 120–130.
  * Momtaz (2020) Paul P. Momtaz. 2020\.  Initial Coin Offerings.  _PLoS ONE_ 15 (2020).
  * Nakamoto (2009) Satoshi Nakamoto. 2009\.  Bitcoin : A Peer-to-Peer Electronic Cash System.
  * Nambiampurath (2023) Rahul Nambiampurath. 2023\.  Polygon receives criticism as it completes hard fork with only 13 validators.  https://www.investopedia.com/polygon-receives-criticism-after-hard-fork-7096331
  * Narayanam and Narahari (2011) Ramasuri Narayanam and Y. Narahari. 2011.  A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks.  _IEEE Transactions on Automation Science and Engineering_ 8 (2011), 130–147.
  * Narayanan et al. (2016) Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven Goldfeder. 2016.  Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction.
  * Platt et al. (2021) Moritz Platt, Johannes Sedlmeir, Daniel Platt, Jiahua Xu, Paolo Tasca, Nikhil Vadgama, and Juan Ignacio Ibañez. 2021.  The energy footprint of blockchain consensus mechanisms beyond proof-of-work. In _International Conference on Software Quality, Reliability and Security Companion (QRS-C)_. 1135–1144.
  * Raman and Varshney (2021) Ravi Kiran Raman and Lav R. Varshney. 2021.  Coding for Scalable Blockchains via Dynamic Distributed Storage.  _IEEE/ACM Trans. Netw._ (dec 2021), 2588–2601.
  * Rauchs and Hileman (2017) Michel Rauchs and Garrick Hileman. 2017.  Global Cryptocurrency Benchmarking Study.
  * Redman (2021) Jamie Redman. 2021\.  Gas DAO Project Forms to Airdrop Tokens to Ethereum Users That Spent $1,559 in Fees.
  * Roughgarden (2020) Tim Roughgarden. 2020\.  Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559.  _arXiv preprint arXiv:2012.00854_ (2020).
  * Roughgarden (2021) Tim Roughgarden. 2021\.  Transaction fee mechanism design.  _ACM SIGecom Exchanges_ 19, 1 (2021), 52–55.
  * Sai et al. (2021) Ashish Rajendra Sai, Jim Buckley, Brian Fitzgerald, and AndrewJ. L. Gear. 2021.  Taxonomy of Centralization in Public Blockchain Systems: A Systematic Literature Review.  _Inf. Process. Manag._ 58 (2021), 102584.
  * Sandor and Genc (2022) Krisztian Sandor and Ekin Genc. 2022.  The Fall of Terra: A timeline of the meteoric rise and crash of UST and luna.
  * Schout (2020) Gisele Schout. 2020\.  Centralization of stake in Pos.  medium.com/stakin/centralization-of-stake-in-pos-f7ccb8f8254
  * Srinivasan (2017) Balaji S Srinivasan. 2017\.  Quantifying Decentralization.  https://news.earn.com/quantifying-decentralization-e39db233c28e
  * Sultanik et al. (2022) Evan Sultanik, Alexander Remie, Felipe Manzano, Trent Brunson, Sam Moelius, Sam Kilmer, Mike Myers, Talley Amir, and Sonya Schriner. 2022.  Are blockchains decentralized? Unintended centralities in distributed ledgers.  _Trail of Bits_ (2022).
  * Waniek et al. (2021) Marcin Waniek, Jan Woźnica, Kai Zhou, Yevgeniy Vorobeychik, Talal Rahwan, and Tomasz P. Michalak. 2021.  Strategic Evasion of Centrality Measures. In _AAMAS_. 1389–1397.
  * Was et al. (2020) Tomasz Was, Marcin Waniek, Talal Rahwan, and Tomasz Michalak. 2020.  The Manipulability of Centrality Measures-An Axiomatic Approach. In _AAMAS_. 1467–1475.
  * Wood (2014) Gavin Wood. 2014\.  Ethereum: A secure decentralised generalised transaction ledger.  _Ethereum project yellow paper_ 151 (2014), 1–32.
  * Wu et al. (2019) Keke Wu, Bo Peng, Hua Xie, and Zhen Huang. 2019\.  An Information Entropy Method to Quantify the Degrees of Decentralization for Blockchain Systems.  _International Conference on Electronics Information and Emergency Communication (ICEIEC)_ (2019), 1–6.
  * Xiao et al. (2020) Yang Xiao, Ning Zhang, Wenjing Lou, and Y. Thomas Hou. 2020\.  A Survey of Distributed Consensus Protocols for Blockchain Networks.  _IEEE Communications Surveys & Tutorials_ 22 (2020), 1432–1465.
  * Zhang et al. (2019) Rui Zhang, Rui Xue, and Ling Liu. 2019.  Security and Privacy on Blockchain.  _ACM Comput. Surv._ (jul 2019).

##  Appendix A Proof for Theorem 1

###### Proof.

To show that C-NORM can distinguish between $s_{0}$ and $s_{1}$ we consider
any (arbitrary) $s_{0}\in S_{SA}$ and corresponding $s_{1}\in S_{NSA}$. We
show for each such sampling for $s_{0},s_{1}$ we have
$\Omega^{\star}(s_{0})\neq\Omega^{\star}(s_{1})$ which concludes our proof.

We are considering the experiment being conducted when the stake distribution
is happening through an Incentive-Compatible bootstrapping protocol.
Therefore, $\hat{\theta}_{i}=\theta_{i}$ for any player $p_{i}$. Consider two
samples $s_{0}\in S_{SA}$ and $s_{1}=e_{r}(s_{0})$. The goal is for
$\Omega^{\star}$ to distinguish between $(s_{0},s_{1})$.

First we calculate $\Omega^{\star}$ for $s_{1}$. Since there are no edges,
$\omega_{i}=c_{i}$. According to the bootstrapping protocol, the allocated
stake $c_{i}$ is proportional to the valuation $\theta$ for a player $p_{i}$.
Therefore, we get $\omega_{i}/\hat{\theta}_{i}=\theta_{i}\cdot
z/\hat{\theta}_{i}$ for some constant $z>0$. However, due to the Incentive
Compatible property of the bootstrapping protocol, we have
$\omega_{i}/\hat{\theta}_{i}=z$. Thus, scaled stake
$\beta_{i}=\frac{z}{\sum_{i=1}^{n}z}=\frac{1}{n}$ which gives
$\Omega^{\star}=0$.

Now, to distinguish from the other case, we want $\Omega^{\star}>0$ (by more
than negligible value) for $s_{0}$. Consider $s_{0}\in S_{SA}$. There is
atleast one (non-negligible weighted) edge and the graph is a Directed Acyclic
Graph, which means there is at least one sink node (node with only incoming
edges). Wlog. let this node correspond to player $p_{i}$. The sum of weights
of incoming edges be $q$. Therefore,
$\omega_{i}/\hat{\theta}_{i}=(c_{i}+q)/\hat{\theta}_{i}=(z\cdot\theta_{i})/\hat{\theta_{i}}+q/\hat{\theta}_{i}=z+q/\theta_{i}$.
The scaled stake
$\beta_{i}=\frac{z+q/\theta_{i}}{\sum_{j=1}^{n}\omega_{j}/\hat{\theta}_{j}}\geq\frac{z+q/\theta_{i}}{nz}=\frac{1}{n}+\frac{q}{n\cdot\theta_{i}}$.
Now we get $\Omega^{\star}$ as

$\displaystyle\Omega^{\star}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{j=1}^{n}\Big{|}\beta_{j}-\frac{1}{n}\Big{|}$
$\displaystyle\geq$ $\displaystyle\beta_{i}-\frac{1}{n}$ $\displaystyle=$
$\displaystyle\frac{q}{n\cdot\theta_{i}}$

Therefore, $\Omega^{\star}\geq\frac{q}{n\cdot\theta_{i}}$ which is a non-
negligible value. Therefore, for any pair $(s_{0},s_{1})$ we can distinguish
between the two states. Let the player $M_{D}$ be given $(s_{a},s_{b})$ such
that (wlog.) $\Omega^{\star}=0$ for $s_{a}$ and $\Omega^{\star}>0$ for
$s_{b}$. Then $a=1,b=0$. Similarly, $M_{D}$ can also predict correctly in case
of $a=0,b=1$. If we are repeating this $\kappa$ times, then $M_{D}$ correctly
predicts the ordering of $(a,b)$ with probability $1-\textsf{negl}(\kappa)$. ∎

##  Appendix B Proof for Theorem 2

###### Proof.

Consider $\Omega^{\star}_{1}=\alpha$. The set of players
$P=\\{p_{1},p_{2}\ldots,p_{n}\\}$ and _scaled stake_ is
$\bm{\beta}=\\{\beta_{1},\beta_{2},\ldots,\beta_{n}\\}$. Wlog. we consider
$\beta_{1}\geq\beta_{2}\geq\ldots\geq\beta_{n}$. Therefore,
$\beta_{max}=\beta_{1}$. Now, we can write $\Omega^{\star}_{1}$ as

$\displaystyle\frac{1}{2}\sum_{i=1}^{n}\Big{|}\beta_{i}-\frac{1}{n}\Big{|}=$
$\displaystyle\;\alpha$

We consider $\delta^{th}$ percentile of $\bm{\beta}$ as the player $p_{i}$
which has the next lowest stake to $\delta$ percentile of players. Let
$\bm{\beta}_{\delta}$ be used to represent this $\delta^{th}$ percentile.
Therefore, $\bm{\beta}_{\delta}:=\beta_{\lceil(1-\delta)\cdot n\rceil}$.

Case 1: $\bm{\beta}_{\delta}\leq\frac{1}{n}$: In this case, we can write
$\Omega^{\star}_{1}=\alpha$ as,

$\displaystyle\frac{1}{2}\left(\Big{|}\beta_{max}-\frac{1}{n}\Big{|}+\Big{|}\bm{\beta}_{\delta}-\frac{1}{n}\Big{|}\right)$
$\displaystyle\leq$ $\displaystyle\alpha$
$\displaystyle\beta_{max}-\frac{1}{n}+\frac{1}{n}-\bm{\beta}_{\delta}$
$\displaystyle\leq$ $\displaystyle 2\alpha$
$\displaystyle\frac{\beta_{max}}{\bm{\beta}_{\delta}}$ $\displaystyle\leq$
$\displaystyle 1+\frac{2\alpha}{\bm{\beta}_{\delta}}$

Case 2: $\bm{\beta}_{\delta}\geq\frac{1}{n}$: In that case, we can write
$\Omega^{\star}_{1}=\alpha$ as

$\displaystyle\beta_{max}-\frac{1}{n}$ $\displaystyle\leq$ $\displaystyle
2\alpha$ $\displaystyle\frac{\beta_{max}}{\bm{\beta}_{\delta}}$
$\displaystyle\leq$
$\displaystyle\frac{1/n}{\bm{\beta}_{\delta}}+\frac{2\alpha}{\bm{\beta}_{\delta}}$
$\displaystyle\leq$ $\displaystyle 1+\frac{2\alpha}{\bm{\beta}_{\delta}}$

The last inequality comes since $\bm{\beta}_{\delta}\geq\frac{1}{n}$. We have
therefore shown that for $\Omega^{\star}_{1}=\alpha$, the system satisfies the
Proportionality condition. Additionally, $\Omega^{\star}$ (C-NORM) captures
attempts of sybil attacks successfully (as demonstrated from Theorem 1), and
we can enforce on the protocol the condition for _Minimum Participation_.
Therefore, if $\Omega^{\star}_{1}=\alpha$ then protocol (which ensures
_Minimum Participation_) is
$(\tau,\delta,\frac{2\alpha}{\bm{\beta}_{\delta}})-$Decentralized for any
$\delta\in[0,1]$. ∎

##  Appendix C Proof for Claim 1

###### Proof.

In proving non-IC property for Airdrop, we show that if a party forms pseudo-
identities, they can always obtain a higher utility than honestly disclosing
their valuations, even when other players are reporting their true valuations
and are not a part of any coalition. This is because, in Airdrop, all players
get the same reward irrespective of their valuation, which incentivizes them
to split their valuation among pseudo-identities to obtain a higher utility.
Consider an Indicator Function $\bm{1}_{\hat{\theta}_{i}>0}$ which is $1$ if
$\hat{\theta}_{i}>0$ else $0$. The utility function for _airdrop_
bootstrapping protocol for player $p_{i}$ is written as

$\displaystyle
U_{i}(\hat{\theta}_{i},\bm{\hat{\theta}}_{-i},\emptyset,\emptyset;\theta_{i})$
$\displaystyle=$ $\displaystyle
b_{airdrop}\cdot\bm{1}_{\hat{\theta}_{i}>0}-\Omega^{\star}\cdot g(\theta_{i})$

For Nash Incentive Compatibility (IC) from Equation 6 of Definition 4.3.2 we
require $\forall\;\hat{\theta}_{i}\in\mathbb{R}_{\geq
0},\forall\;A_{i}\in\mathcal{A}_{i}$

$\displaystyle
U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})$
$\displaystyle\geq$ $\displaystyle
U_{i}(\hat{\theta}_{i},\bm{\theta}_{-i},A_{i},\emptyset;\bm{\theta})$
$\displaystyle b_{airdrop}\cdot\bm{1}_{\hat{\theta}_{i}>0}-\Omega^{\star}\cdot
g(\theta_{i})$ $\displaystyle\geq$ $\displaystyle b_{airdrop}\cdot\sum_{j\in
A_{i}}\bm{1}_{\hat{\theta}_{j}>0}-\Omega^{\star}\cdot g(\theta_{i})$

We therefore observe that by forging identities (Sybil-attack) which is
equivalent to forming a coalition $A_{i}$ we observe that a player can forge
arbitrary number of identities and gain more reward than following the
protocol honestly. This means for any $A_{i}$ such that $|A_{i}|>1$ the above
inequality does not hold true. Thus, Airdrop does not satisfy Nash Incentive
Compatibility (IC). ∎

##  Appendix D Proof for Claim 2

###### Proof.

Consider a Proof-of-Burn-based bootstrapping where cryptocurrency from an _Old
Crypto Token_ $\$OCT$ is burnt to obtain _New Crypto Token_ $\$NCT$. The
conversion rate from $OCT$ to $USD$ is $1\;OCT=d\;USD$ and for $NCT$ is
$1\;NCT=e\;USD$. The rule is set such that if a player burns $a\;OCT$ they
obtain $b\;NCT$. Payoff on not participating in the protocol for a player
$p_{i}$ is
$U_{i}(0,\bm{\theta}_{-i},\emptyset,\emptyset;\bm{\theta})=-\Omega^{\star}\cdot
g(\theta_{i})$. The payoff obtained from participating in the protocol
honestly, for some constant $\gamma\in\mathbb{R}_{>0}$ is

$\displaystyle
U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})$
$\displaystyle=$ $\displaystyle(b\cdot e-a\cdot
d)\gamma\theta_{i}-\Omega^{\star}\cdot g(\theta_{i})$

However, setting an exchange rate for the New Crypto Token (which is set by
the protocol designers) does not establish the exchange rate, but sets a “one-
way peg” or price-ceiling for $NCT$ such that $b\cdot e\leq a\cdot d$ (See
Narayanan et al. (2016) Section 10.1 for more details). If we account for
transaction-fees and expected utility, then we get

$\displaystyle\mathbb{E}[U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})]$
$\displaystyle=\mathbb{E}[(b\cdot e-a\cdot
d)\gamma\theta_{i}-\Omega^{\star}\cdot g(\theta_{i})]$
$\displaystyle<-\mathbb{E}[\Omega^{\star}g(\theta_{i})]=\mathbb{E}[U_{i}(0,\bm{\theta}_{-i},\emptyset,\emptyset;\bm{\theta})]$

Therefore, PoB-based bootstrapping protocol is not Individually Rational (IR).
∎

##  Appendix E Proof for Lemma 6.2

###### Proof.

Consider a PoW blockchian protocol such that if all players invest in mining
proportionally to their true valuation then player $p_{i}$ with valuation
$\theta_{i}$ has mining power $m_{i}=\theta_{i}\cdot l$ (for some
$l\in\mathbb{R}_{>0}$). The cost incurred per unit mining power for any player
is $\chi$ and the reward obtained on mining a block be $r_{\text{b}}$.The
minimum mining power which a player can have be $m_{min}$. This means $\forall
p_{i}\in P,m_{i}\geq m_{min}$. Additionally, let $M=\sum_{i\in[n]}m_{i}$.

Consider for player $p_{i}$ a random variable $R_{i}$ which denotes the payoff
of the player.

$R_{i}=\begin{cases}r_{\text{b}}-\chi m_{i},&\text{with probability
}\frac{m_{i}}{M}\\\ -\chi m_{i},&\text{with
probability}\frac{M-m_{i}}{M}\end{cases}$

Individual Rationality: For IR, we require that expected block reward should
exceed cost of mining for all players $p_{i}$. Therefore $\forall p_{i}\in P$
the expected utility on abstaining from the protocol is

$\displaystyle\mathbb{E}[U_{i}(0,\bm{\hat{\theta}}_{-i},\emptyset,A_{-i};\theta_{i})]$
$\displaystyle=-\mathbb{E}[\Omega^{\star}\cdot g(\theta_{i})]$

The expected utility on participating in the protocol for each round is

$\displaystyle\mathbb{E}[U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})]$
$\displaystyle=\mathbb{E}[R_{i}]-\mathbb{E}[\Omega^{\star}\cdot
g(\theta_{i})]$ $\displaystyle=(r_{\text{b}}\frac{m_{i}}{M}-\chi
m_{i})-\mathbb{E}[\Omega^{\star}\cdot g(\theta_{i})]$

For IR we require
$\mathbb{E}[U_{i}(0,\bm{\hat{\theta}}_{-i},\emptyset,A_{-i};\theta_{i})]\leq\mathbb{E}[U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})]$
which gives us $\forall p_{i}\in P$

$\displaystyle(r_{\text{b}}\frac{m_{i}}{M}-\chi m_{i})$ $\displaystyle\geq 0$
$\displaystyle r_{\text{b}}\frac{m_{i}}{M}$ $\displaystyle\geq\chi m_{i}$
$\displaystyle\Rightarrow\frac{\chi M}{r_{\text{b}}}\leq 1$

Incentive Compatibility: For Incentive Compatibility, we will show for each
player $p_{i}\in P$, reporting a valuation $\hat{\theta}_{i}\neq\theta_{i}$
will lead to a lower payoff. We proceed in two cases:

Case 1 $\hat{\theta}_{i}<\theta_{i}$: In this case, let $m_{i}^{{}^{\prime}}$
be the mining power corresponding to the disclosed valuation
$\hat{\theta}_{i}$. Clearly, $m_{i}^{{}^{\prime}}<m_{i}$. Consider for some
$a>0,m_{i}^{{}^{\prime}}=m_{i}-a$. The expected difference in utility, that is
$\mathbb{E}[U_{i}(\hat{\theta}_{i},\bm{\theta}_{-i},A_{i},\emptyset;\theta_{i})-U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})]$
is therefore given by

$\displaystyle\mathbb{E}[U_{i}(\hat{\theta}_{i},\bm{\theta}_{-i},A_{i},\emptyset;\theta_{i})-U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})]$
$\displaystyle=r_{\text{b}}\left(\frac{m_{i}^{{}^{\prime}}}{M-m_{i}+m_{i}^{{}^{\prime}}}-\frac{m_{i}}{M}\right)-\chi(m_{i}^{{}^{\prime}}-m_{i})$
$\displaystyle=\frac{a}{M-a}\left((M-a)\chi-r_{\text{b}}\right)$
$\displaystyle<\frac{a}{M-a}\left(M\chi-r_{\text{b}}\right)\leq 0$

The last inequality comes from the condition obtained from Individual
Rationality $\chi M\leq r_{\text{b}}$.

Case 2 $\hat{\theta}_{i}>\theta$: In this case, let
$m^{{}^{\prime}}_{i}=m_{i}+a$ (for some $a>0$) be the mining power
corresponding to reported valuation $\hat{\theta}_{i}$. Consider
$R^{{}^{\prime}}_{i}$ be the random variable denoting reward when reported
valuation is $\hat{\theta}_{i}$. Therefore,

$R_{i}^{{}^{\prime}}=\begin{cases}r_{\text{b}}-\chi(a+m_{i}),&\text{with
probability }\frac{m_{i}+a}{M+a}\\\ -\chi(a+m_{i}),&\text{with
probability}\frac{M-m_{i}}{M+a}\end{cases}$

Now, we can write the expected difference in utility as

$\displaystyle\mathbb{E}[U_{i}(\hat{\theta}_{i},\bm{\theta}_{-i},A_{i},\emptyset;\theta_{i})-U_{i}(\theta_{i},\bm{\theta}_{-i},\emptyset,\emptyset;\theta_{i})]$
$\displaystyle=\mathbb{E}[R^{{}^{\prime}}_{i}-R_{i}]$
$\displaystyle=r_{\text{b}}\left(\frac{m_{i}+a}{M+a}-\frac{m_{i}}{M}\right)-\chi(m_{i}+a-m_{i})$
$\displaystyle=r_{\text{b}}\frac{a(M-m_{i})}{M(M+a)}-a\chi$
$\displaystyle=\frac{ar_{\text{b}}}{M+a}\left(1-\frac{m_{i}}{M}-\frac{\chi(M+a)}{r_{\text{b}}}\right)$
$\displaystyle\leq\frac{ar_{\text{b}}}{M+a}\left(1-\frac{m_{min}}{M}-\frac{M\chi}{r_{\text{b}}}\right)<0$

The last inequality uses the fact
$\left(1-\frac{m_{min}}{M}\right)<\frac{M\chi}{r_{\text{b}}}$.

In conclusion, we have shown that if
$1-\frac{m_{min}}{M}<\frac{M\chi}{r_{\text{b}}}\leq 1$ is satisfied, then the
PoW-based bootstrapping protocol (W2SB) is both Individually Rational (IR) and
Incentive Compatible (IC). ∎

Figure 3. C-NORM against rounds for different $T$ and different distributions
of miner stake

##  Appendix F Proof for Theorem 3

###### Proof.

To prove the theorem, we run the W2SB for $T$ rounds. We show that for any
arbitrary desired value $z\in(0,1)$ there always exists $T$ such that after
$T$ rounds, $\Omega^{\star}\leq z$. Out of these $T$ rounds, the first
$T_{0}<T$ rounds are such that the majority of players have joined the system
before this round. This means $T_{0}$ is such that $\Psi(T_{0})=1-\frac{x}{n}$
for $x<z$. Wlog. we assume players join the system in the order
$p_{1},p_{2},\ldots,p_{n}$. The C-NORM value is therefore given by

$\displaystyle\Omega^{\star}$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{n}\Big{|}\beta_{i}-\frac{1}{n}\Big{|}$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{\Psi(T_{0})n}\Big{|}\beta_{i}-\frac{1}{n}\Big{|}+\sum_{i=\Psi(T_{0})n}^{n}\Big{|}\beta_{i}-\frac{1}{n}\Big{|}$
$\displaystyle\leq\sum_{i=1}^{\Psi(T_{0})n}\Big{|}\beta_{i}-\frac{1}{n}\Big{|}+\sum_{i=\Psi(T_{0})n}^{n}1$
$\displaystyle=\sum_{i=1}^{\Psi(T_{0})n}\Big{|}\beta_{i}-\frac{1}{n}\Big{|}+n\cdot(1-\Psi(T_{0}))$

We get the last inequality because $|a-b|\leq\max(|a|,|b|)$ and
$|\beta_{i}-\frac{1}{n}|\leq\max(|\beta_{i}|,\frac{1}{n})\leq 1$. Now we
consider $\Big{|}\beta_{i}-\frac{1}{n}\Big{|}$, which gives us

$\displaystyle\Big{|}\beta_{i}-\frac{1}{n}\Big{|}$
$\displaystyle=\Big{|}\frac{\omega_{i}/\theta_{i}}{\sum_{j=1}^{n}\omega_{j}/\theta_{j}}-\frac{1}{n}\Big{|}$
$\displaystyle\leq\Big{|}\frac{T_{0}\cdot
r_{\text{b}}+(\omega^{{}^{\prime}}_{i}/\theta_{i})}{\sum_{j=0}^{n}\chi(T-T_{0})}-\frac{1}{n}\Big{|}$

For the last inequality, (1) $\omega_{i}^{{}^{\prime}}$ is the payoff from
round $T_{0}$ to $T$, and before that any player can get at most
$T_{0}r_{\text{b}}$. Therefore, we use the inequality
$\omega_{i}/\theta_{i}\leq T_{0}+\omega_{i}^{{}^{\prime}}/\theta_{i}$ to upper
bound the numerator. (2)
$\omega_{j}/\theta_{j}\geq\omega_{j}^{{}^{\prime}}/\theta_{j}\geq(T-T_{0})\chi$
since W2SB is IR means
$\frac{\theta_{i}r_{\text{b}}}{\sum_{j=1}^{n}\theta_{j}}\geq\chi$ and
therefore $\omega_{j}/\theta_{j}\geq\chi(T-T_{0})$ as the stake is allocated
for $T-T_{0}$ rounds.

We can also upper bound $\omega_{i}^{{}^{\prime}}/\theta_{i}$ by considering
the stake is distributed among only the players who have joined in round $\leq
T_{0}$. In this case, $\omega_{i}^{{}^{\prime}}/\theta_{i}=c\;\forall\;p_{i}$
joining before round $T_{0}$ for some constant $c$. We therefore get

$\displaystyle\Omega^{\star}$ $\displaystyle\leq
n\Psi(T_{0})\Big{|}\frac{T_{0}r_{\text{b}}+(T-T_{0})c}{n\chi(T-T_{0})}-\frac{1}{n}\Big{|}+x$
$\displaystyle=n\Psi(T_{0})\Big{|}\frac{c}{n\chi}+\frac{T_{0}r_{\text{b}}}{n\chi(T-T_{0})}-\frac{1}{n}\Big{|}+x$

When we increase $T$, we can reduce the mod term to a small enough value such
that $\Omega^{\star}\leq z$. By IR we require $c=r_{\text{b}}/M\approx\chi/n$
(for very small $m_{min}$, see Lemma 6.2). Therefore,

$\displaystyle\Omega^{\star}$
$\displaystyle\lesssim\Psi(T_{0})\Big{|}\frac{T_{0}r_{\text{b}}}{\chi(T-T_{0})}\Big{|}+x$
$\displaystyle\leq z$ $\displaystyle\Rightarrow
T\geq\frac{\Psi(T_{0})T_{0}r_{\text{b}}}{(z-x)\chi}+T_{0}$

Thus, for any $z\in(0,1]$ we can always obtain a finite $T$ such that
$\Omega^{\star}\leq z$ if W2SB is run for $\geq T$ rounds, assuming dynamic
participation according to some distribution with CDF $\Psi$. ∎

##  Appendix G Experiments

The plots are shown in figure 3 for distributions with different parameters to
show that the trend remains the same.

##  Appendix H Cycle Elimination Algorithm

##### Cycle Elimination Procedure.

Without loss of generality, consider there exists a cycle with edges from
$p_{1}$ to $p_{2}$, $p_{2}$ to $p_{3}$ and so on till $p_{k}$ to $p_{1}$.
These cycles can be found using any cycle detection algorithm such as BFS,
Floyd’s algorithm. Let weight $w_{1,2}$ be the smallest of the weights. We
eliminate the edge from $p_{1}$ to $p_{2}$ by subtracting the weight $w_{1,2}$
from each edge of the cycle. If there exist multiple cycles, the order of
elimination will result in different DAGs. However, the resultant value of the
centralization metric (proposed in Section 5.2) does not change.

(a) Edges

(b) With cycles

(c) Eliminated Cycle

Figure 4. PoS System graph and cycle elimination. Algorithm 1 CycleElimination
procedure

1:Input: $\mathcal{G}=(P,\mathcal{C},\mathcal{W})$ $\triangleright$ PoS System
Graph (might contain cycles)

2:Output: $\mathcal{G}^{{}^{\prime}}$ $\triangleright$ Directed Acyclic PoS
System Graph

3:for each cycle $(p_{1},p_{2},\ldots,p_{k})$ do

4: $w_{min}:=\infty$

5: for each $p_{i},p_{j}$ in the cycle do

6: $w_{min}=min(w_{min},w_{i,j})$

7: for each $p_{i},p_{j}$ in the cycle do

8: $w_{i,j}=w_{i,j}-w_{min}$

9:Updated weight set is $\mathcal{W}^{{}^{\prime}}$

10:$\mathcal{G}^{{}^{\prime}}:=(P,\mathcal{C},\mathcal{W}^{{}^{\prime}})$

11:Return $\mathcal{G}^{{}^{\prime}}$