# Free2Shard: Adaptive-adversary-resistant sharding via Dynamic Self
Allocation

Ranvir Rana<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign ,
Sreeram Kannan<EMAIL_ADDRESS>University of Washington at Seattle ,  David
Tse<EMAIL_ADDRESS>Stanford University and  Pramod Viswanath
<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign

###### Abstract.

Propelled by the growth of large-scale blockchain deployments, much recent
progress has been made in designing sharding protocols that achieve throughput
scaling linearly in the number of nodes. However, existing protocols are not
robust to an adversary adaptively corrupting a fixed fraction of nodes. In
this paper we propose Free2Shard– a new architecture that achieves near-linear
scaling while being secure against a fully adaptive adversary.

The focal point of this architecture is a dynamic self-allocation algorithm
that lets users allocate themselves to shards in response to adversarial
action, without requiring a central or cryptographic proof. This architecture
has several attractive features unusual for sharding protocols, including: (a)
the ability to handle the regime of large number of shards (relative to number
of nodes); (b) heterogeneous shard demands; (c) requiring only a small
minority to follow the self-allocation; (d) asynchronous shard rotation; (e)
operation in a purely identity-free proof-of-work setting. The key technical
contribution is a deep mathematical connection to the classical work of
Blackwell in dynamic game theory.

LaTeX template, ACM CCS, ACM

##  1\. Introduction

A classical problem in distributed systems is one of maintaining a state
machine given $N$ nodes, some fraction of which are adversarial (also termed
Byzantine). Classical mechanisms for Byzantine-fault-tolerant (BFT) state-
machine-replication (SMR) rely on full replication of data across multiple
nodes; thus offering no scaling in efficiency as the number of replica nodes
increase (Castro et al., 1999; Dolev and Strong, 1983; Dwork et al., 1988;
Abraham et al., 2019a). Since SMR is the key primitive underlying blockchains,
it is no surprise that the first generation of blockchains also relied on full
replication (Nakamoto, 2008; Research, 2020).

Given the unprecedented scale of blockchains, for example, Bitcoin has $N\geq
10,000$ nodes running its protocol (Telegraph, 2019), there is compelling
practical interest in protocols whose efficiency increases with the number of
nodes. This problem has attracted wide interest in the distributed systems
community with many protocols being proposed (Luu et al., 2016; Kokoris-Kogias
et al., 2018; Zamani et al., 2018). These pioneering methods offer provable
security as well as near-linear scaling in $N$ of efficiency across various
resources at an individual node including computation, storage and
communication.

While existing solutions offer excellent performance as well as security
against static (or slowly adapting) adversaries, their security fails under an
adaptive adversary. This problem is compounded in permissionless blockchain
deployments where the possibility of the adaptive adversary threat is high
since nodes do not have persistent identities. This is evidenced in the
significant practical interest in designing protocols robust to this setting
(Zilliqa, 2017; Wood, 2016; Research, 2020; Al-Bassam, 2019).

The main result of this paper is the Free2Shard architecture, whose
performance scales near-linearly with the number of nodes while being secure
against fully adaptive adversaries controlling up to 50% of the nodes. While
existing sharding solutions build upon a cryptographically certifiable node-
to-shard allocation algorithm, we take the complete opposite view: nodes can
allocate themselves to shards as they please. Our sharding architecture is
designed in such a way that even when the majority of a shard is adversarial,
the safety is not violated. However, an adversary can congregate in a shard,
significantly reducing the fraction of honest shard blocks, and creating
corresponding security threats (especially, liveness) and also restricting
throughput. This is solved by our core contribution: a dynamic shard
allocation algorithm.

The core idea underneath our algorithm is that the honest nodes re-allocate
themselves into shards throttled by the adversary. However, the adversary can
observe the honest nodes’s actions and re-allocate itself to nullify the
honest nodes’ actions. The main technical contribution of this paper is the
identification of a (computationally simple) dynamic self-allocation policy
that can successfully ensure that the fraction of honest to adversarial nodes
in every shard is greater than $0.5$ (thus ensuring sufficient throughput in
all shards). The core technical result is a complete and striking solution to
a dynamic Stackelberg game (von Stackelberg, 2011); our approach is distinct
but inspired by the classical Blackwell approachability in game theory
(Blackwell et al., 1956).

The Free2Shard architecture also uses well-established primitives to achieve
its requisite properties: (1) an SMR engine, resistant to adaptive
adversaries, to maintain an ordered log of all shard block hashes, (2) a data
availability engine (Al-Bassam et al., 2018; Yu et al., 2019) that guarantees
that data written into the SMR are actually available, and a (3) state-
commitment engine based on interactive verification (Teutsch and Reitwießner,
2019; Kalodner et al., 2018) to ensure low complexity of bootstrapping while
rotating.

Furthermore, the protocol has several desirable properties that makes it
attractive from a systems view: (a) asynchronous shard rotation - nodes do not
all rotate at the same time; (b) requires only a small number of honest nodes
per shard; (c) guarantees the aforementioned properties even when only a small
minority of nodes follow the proposed rotation protocol; (d) can support
heterogeneous shard throughput even when the number of shards is greater than
the number of nodes; (e) the ability to operate in a (permissionless) proof-
of-work setting with the same guarantees of throughput scaling and security
against a fully adaptive adversary.

The paper is organized as follows. There is a very large number of recent
literature on sharding solutions for blockchains and we conceptually organize
them in terms of their architecture (and building blocks) in Section 2; this
survey also sets the stage to put the proposed Free2Shard architecture in
context (and provide a brief overview). The key building block of Free2Shard
is the dynamic self allocation engine which is discussed in detail in Section
3. We describe Free2Shard architecture and various parameter choices in
Section 4; we also provide the security guarantees and efficiency scaling
properties. We conclude in Section 5 with a discussion on the various system
properties of Free2Shard in the context of real world implementation concerns
(especially in a distributed permissionless setting) – synchronization,
partial deployment, incentives, inter-shard transaction handling.

##  2\. Background and Motivation

Security Model. We consider a distributed system maintained by $N$ nodes on a
synchronous network. We assume that there is a natural mechanism to partition
the ledger into $K$ distinct shards of equal size (for example, think of these
as distinct applications sharing a common blockchain or as distinct accounts
in a payment system). The goal is to have the total throughput scaling
linearly with the number of nodes, while each node expends only constant
amount of resources. We will particularly be concerned about three types of
resources: (1) computation resource - the number of transactions executed per
second, (2) storage resource - the number of transactions / second that can be
incrementally stored by the node 111We will make the simplifying assumption
that the storage per node is growing with time. This is required for Bitcoin
for example. Ideas to relax this requirement, for example (Jedusor, 2016), can
be naturally applied to our setting too. and (3) communication resource - the
total amount of data communicated by a node. We will assume that at every
node,  all three resources are sufficient to run a non-sharded blockchain with
$R$ transactions-per-second. We will assume that, at any given time, a
fraction $\beta$ of nodes are controlled by the adversary - they can deviate
arbitrarily from the proposed protocol. We want to prove security against a
fully adaptive adversary, which can corrupt any subset of nodes based on the
public state till that time (as long as the total number of corrupted nodes is
less than its “budget” $\beta N$). Security encompasses two aspects: (1)
safety: transactions once confirmed remain confirmed for ever, and (2)
liveness: new honest transactions will continue to be added within a finite
amount of time.

This problem has elicited much recent interest owing to the scalability
bottleneck in blockchains; the corresponding solutions in the literature are
broadly referred to as sharding methods. Blockchain sharding methods in the
literature can be broadly divided into two categories: multiconsensus (most
sharding solutions) and uniconsensus architectures. Each of these
architectures provide different scaling gains and have distinct security
vulnerabilities; we discuss this next.

###  2.1. Multiconsensus architecture

The multiconsensus architecture relies on each shard having a separate
consensus engine and has a secure cryptographic allocation of nodes randomly
to shards. A further periodic random reallocation of nodes to shards protects
against a weakly adaptive adversary. The random reallocation is enabled by a
node to shard allocation engine (N2S) which assigns nodes to shards using a
(common) distributed randomness, generated using a consensus engine shared
across all shards and commonly referred to as beacon consensus engine. A state
commitment engine posts root of a Merkle Trie (Luu and Rush, 2017) of a
shard’s execution state (the so-called “state commitment”) (Research, 2020) to
the beacon consensus engine at regular intervals; this facilitates fast
reallocation and synchronization to new shards. Figure 1 illustrates a simple
example with a node-to-shard allocation that allocates nodes to distinct
shard, on which independent consensus is performed.

Security. If a (super)majority exists in the overall set of nodes, then the
random node to shard allocation engine transfers this property to each shard
(as long as each shard is large enough – this weakness is discussed in detail
shortly). This guarantees security of the shard consensus engine, against a
static adversary. Periodic reallocation of nodes to shards enhances the
security of shard consensus against a slowly adaptive adversary.

Scaling. Multiconsensus architecture allows nodes to maintain only the state
of the shard consensus engine and the beacon consensus engine, with beacon
consensus engine only containing state commitments and N2S allocation
metadata. Splitting the set of nodes into $K$ different shards, enables
parallel execution of $K$ shard consensus engines, thus scaling transaction
execution by factor $K$.

A key question is how large can $K$ be, relative to $N$. With a random
allocation of node to shards, a majority fraction of honest nodes overall (eg:
60%) translates to majority of honest nodes in a given shard with high
probability (eg. $10^{-10}$) only if the size of the shard is large (i.e.,
$G=1100$ nodes). Since each shard should have $G$ members, the total number of
shards $K$ has to be smaller than $N/G$ (i.e,, $N/1100$). This restricts the
number of shards and thus the scaling capability.

Figure 1. Multiconsensus architecture

Elastico (Luu et al., 2016) and Omniledger (Kokoris-Kogias et al., 2018)
pioneered the study and design of sharding methodologies for blockchain in
academic literature. Omniledger, built on top of ideas from Elastico, runs N2S
allocation using Randhound(a randomization protocol) on an identity
blockchain. The nodes are gradually rotated between shards to decrease the
synchronization load on the network. Rapidchain (Zamani et al., 2018) further
proposed several improvements by reducing the communication complexity to sub-
linear in the number of nodes, and secure reallocation of nodes to shards
building on the Cuckoo rule.

Key Vulnerability. The key property enabling security of the multiconsensus
architecture is that there is sufficient honest (super)majority in each shard
(this suffices for a static adversary) and the N2S allocation is periodically
updated (this allows security against a weakly adaptive adversary). However
the scheme is insecure against adaptive adversaries: The N2S allocation is
posted on the beacon chain, hence an adversary knows the list of nodes
participating in any given shard. An adversary can then adaptively target all
nodes allocated to a particular shard and completely corrupt it (this is well
within the corruption budget, since the total number of nodes in a shard is
small relative to the network size). Once a shard is taken over by the
adversary, both safety (i.e., the adversary can approve invalid blocks) and
liveness (the adversary can block honest transactions) can be compromised.

In permissionless settings, the possibility of the adaptive adversary threat
is severe. This is reflected in the fact that permissionless sharding
protocols have designed heuristic mechanisms to deal with this threat.
Consider the case of Ethereum 2.0 (Research, 2020) or Polkadot (Wood, 2016).
In these protocols, the primary mechanism for dealing with adaptive
adversaries is to submit commitments of shard state into the beacon consensus
engine, and any node can contest this commitment by proving that the state
transition from previous commitment includes an invalid transaction. This
short proof is called as a fraud proof and can be posted by anyone to
invalidate a set of shard blocks (Al-Bassam et al., 2018).

While fraud proofs can be used to detect safety violations caused due to an
adaptive adversary, they cannot detect liveness violations. Indeed, an
adaptive adversary can corrupt the majority of any given shard and ask them to
censor all honest transactions. Thus since no invalid transactions have been
included in the ledger, no fraud-proof can be created. Every time the node-to-
shard allocation is rotated, the adaptive adversary corrupts the newly
allocated members, thus imposing a permanent liveness ban on that shard.

While cryptographic scaling alternatives have been proposed, we note that this
liveness attack persists. For example, mechansims of verifiable computing
(Parno et al., 2013) such as SNARKs (Ben-Sasson et al., 2014), ZK-STARKs (Ben-
Sasson et al., 2018) and bullet-proofs(Bünz et al., 2018) have been proposed
for scaling blockchains under differing assumptions on trust and setup. These
mechanisms enable scaling by letting the block proposer guarantee that the
posted state accurately reflect the state after executing the transactions in
the block. While these mechansims can be used as a non-interactive alternative
to fraud-proofs for scaling, they have no way of guaranteeing that
transactions have been censored, and are thus subject to the liveness attack
by the adaptive adversary described above.

###  2.2. Uniconsensus architecture

Figure 2. Uniconsensus architecture

The requirement for node-to-shard allocation in multiconsensus architecture
comes from the necessity of allocating nodes to each of the shard consensus
groups. The uniconsensus architecture avoids this requirement by instead
relying on a single consensus engine to maintain the ordering information of
all shard blocks. Thus the safety of each shard can be directly derived from
the safety of the main consensus engine. The consensus engine only maintains a
log of hash of shard blocks and hence is scalable. A honest consensus
(super)majority is no longer needed in each shard to preserve safety, thus
each node is free to join a shard of it’s choice (self-allocation). Shard
block execution is performed by shard nodes and is decoupled from shard block
ordering performed by the consensus engine. This architecture does not require
each transaction in every shard block to be valid, rather only guaranteeing
the order of transactions in the shards. Since the consensus engine only
maintains the hash of each block, a separate mechanism is required to ensure
that the full block is available to the shard nodes - this is guaranteed by a
data availability engine. Figure 2 illustrates the 3 engines and their
interactions.

Security. If a majority of honest nodes exist in the overall set of nodes, the
consensus engine is secure. Consider a shard with less than a majority of
honest nodes, the adversarial nodes in the shard cannot change the log of
shard blocks without violating safety of the consensus engine, thus an
adaptive adversary with less than a global consensus majority cannot violate
safety of any shard. The lack of requirement of a honest majority constraint
within a shard also allows for small shard size. We observe that uniconsensus
architecture solves the shard ledger safety and shard size vulnerabilities of
multiconsensus architecture, but introduces serious liveness vulnerabilities
discussed below.

Scaling. Nodes maintaining the uniconsensus architecture only maintain the
consensus engine and shard log of one shard, the consensus engine contains a
log of shard block hashes, the size of which is much smaller than shard
blocks. Thus, $K$ shards can be processed in parallel with each node
processing only one shard log.

Related work. The idea of scaling by a distributed system by maintaining a
single consistent log with distributed data is propounded by distributed
systems architectures like Corfu (Balakrishnan et al., 2012) and Tango
(Balakrishnan et al., 2013). Corfu proposed an architecture to maintain a log
whose data is distributed across a cluster of flash drives. Tango built a
sharded system on top of Corfu, where execution is decoupled from validity and
application nodes only need to execute the subset of entries from the log
which are relevant to that application. At a high level, this fits into the
uniconsensus architecture described here, but Corfu and Tango are designed for
resilience to the simpler crash-faults as compared to the more complex
Byzantine faults considered in this paper.

To handle more complex fault models, works like Aspen (Gencer et al., 2017)
require consensus nodes to maintain and compute the entire ledger data.
However, the data is organized like in Tango, so that client nodes running an
application only need to download the relevant data. Lazyledger (Al-Bassam,
2019) took this idea further to reduce storage and communication burden on the
consensus nodes by allowing data availability proofs (Al-Bassam et al., 2018).

Vulnerability. Removing N2S allocation by allowing node self-allocation
introduces a serious liveness attack on a shard where an adversary can
concentrate it’s mining power on one shard and drown out honest shard blocks.
We note that to execute this liveness attack, we do not even require an
adaptive adversary. In this attack, the fraction of honest blocks to the
adversarial blocks is greatly reduced due to a large fraction of adversarial
nodes in the shard. Since the shard has limited resources, it can only support
a fixed number of shard blocks, hence a low honest block to total block
fraction would lead to a throttling of the number of honest shard blocks added
to the shard log and hence throttle throughput. The honest transactions can no
longer be processed in finite time, thus leading to loss of liveness. An
example of this attack is shown in Figure 5.

###  2.3. Partial Scaling Approaches

The approaches considered till now achieve scaling while maintaining constant
resource usage, i.e., these protocols are computation, communication and
storage efficient. There are other approaches that are efficient only in some
dimensions while being fully resilient to an adaptive adversary. For example,
Zilliqa (Zilliqa, 2017) achieves computation-efficient scaling, but it is not
communication or storage efficient. Polyshard (Li et al., 2018) and coded
state machines (Li et al., 2019) can achieve storage efficient scaling but
they are not communication efficient.

To summarize: (1) the multiconsensus sharding architecture is safe against
weakly adaptive adversaries, but loses safety and liveness against adaptive
adversaries, (2) the uniconsensus sharding architecture is safe against
adaptive adversaries but liveness is compromised even under static
adversaries, and (3) approaches fully secure against an adaptive adversary are
not efficient in all dimensions.

###  2.4. Overview of Free2Shard

The main contribution of this paper is the introduction of the Free2Shard
architecture which provides full horizontal scaling (in all the 3 dimensions
of storage, compute and communication) while being secure against fully
adaptive adversaries. The architecture builds on the uniconsensus architecture
described above with a new component: the dynamic self-allocation (DSA)
engine. The DSA engine provides an algorithm for honest nodes to re-allocate
themselves to shards, thus reacting to adversaries congregating in individual
shards, and guarantees a strong mathematical property: the time average
fraction of honest to adversarial nodes in every shard approaches the
theoretical optimal (fraction of all honest nodes, total across all shards).
Deriving this dynamic self-allocation engine and its mathematical guarantee is
a core algorithmic and theoretical contribution of this paper and is discussed
in detail in the next section.

The Free2Shard architecture comprises of the following: (1) State machine
replication (SMR) consensus engine run by all nodes for maintaining a total
order of block hashes, (2) data availability engine to certify that every
block hash written into the SMR is actually available in that shard, (3)
dynamic self-allocation (DSA) engine to ensure that the fraction of honest
nodes in any given shard is high and (4) state commitment engine, that
provides nodes migrating between shards a quick boostrapping ability to get
the state of the new shard without requiring them to download the entire other
shard. We note that the primitives (1), (2) and (4) are independently well-
understood from the literature and have been used in different ways in
sharding architectures. The unique properties of Free2Shard arise primarily
from the DSA and the way in which it leverages the other primitives. Figure 3
illustrates the 5 engines and their interactions and Figure 4 is an example of
a Free2Shard system in action. At a high level, the DSA remedies the liveness
vulnerability of the uni-consensus architecture.

###  2.5. Key Primitives

We require three key primitives from previous literature in our Free2Shard
architecture, we describe these primitives briefly here.

State Machine Replication. A totally ordered log of the shard block headers is
maintained using a SMR (Bessani et al., 2014). We assume that the SMR is
robust to an adversary adaptively corrupting at most $\beta_{c}$ fraction of
the nodes. To achieve scalability, we require that the total message
complexity of SMR be linear in the number of nodes (so that the communication
complexity per node is a constant).

Examples of SMR that satisfy these properties include Ouroboros Praos and
Algorand, since they are robust to fully adaptive adversaries. We note that
Ouroboros Praos has $\beta_{c}=0.5$ whereas Algorand has
$\beta_{c}=\frac{1}{3}$. Other protocols which have efficient communication
complexity such as HotStuff (Yin et al., 2019), Sync HotStuff (Abraham et al.,
2019b), and Streamlet (Chan and Shi, 2020) are robust to varying degrees of
adaptivity by the adversary.

Data Availability engine. We require data availability engine as a key
primitive. Input: Commitment $c$ for a shard block (of size $B$) from a honest
/ adversarial node. Output: Every node deduces correctly if the block is
available. Properties: Nodes inside that shard expend at most $O(B\log B)$
resources. Every node expends at most $O(\log B)$ resources. Assumption:
Correct if at least one honest node inside the shard.

State commitment engine. The state commitment engine is used to commit the
execution state of a shard into the SMR after executing a block of
transactions. We use the interactive state verification engine from (Teutsch
and Reitwießner, 2019) that satisfies the following properties. We note that
verifiable computing methods such as ZK-STARK (Ben-Sasson et al., 2018) can be
used instead too. Input: Prior state commitment $c$, block $B$ of
transactions, claimed state $s$ after executing $B$ beyond $c$. The claimed
state can be posted either by a honest node or an adversary. Output: Every
node correctly agrees on whether $s$ is correct or not. Properties: Requires a
distinct committee for $O(\log B)$ rounds. Every committee member spends at
most $O(N\log B)$ resources. All other nodes expend at most $O(\log B)$
resources. Assumption: Correct if there is at least one honest node in the
committee of each round.

Figure 3. Free2shard Architecture Figure 4. Free2shard System in Action

###  2.6. Our Contribution

Key Properties Free2Shard satisfies the following properties:

  * •

Free2Shard is safe as long as $\beta$ (fraction of nodes are controlled by the
adversary) is less than $\beta_{c}$, the critical threshold of fraction
adversaries that can be tolerated by the underlying SMR consensus engine.

  * •

Free2Shard is live as long as $\gamma>0$ fraction of nodes follow the self-
allocation policy.

  * •

Free2Shard can support $K<\Theta(\frac{N}{\log N})$ shards each of throughput
at least $R/2$ transactions per second. Thus we get a total scaling of
$\Theta(\frac{N}{\log N})$ relative to running a single shard.

We provide a short summary of why Free2Shard achieves the security and
scalability properties below. A detailed discussion is deferred to Section 4.

  * •

Each shard block is safe as long as the SMR engine is safe, which is true till
$\beta<\beta_{c}$ for the SMR even under an adaptive adversary.

  * •

The shard continues to include honest transactions as long as honest nodes get
to propose blocks. Since our DSA guarantees that the long term fraction of
honest blocks in a given shard is close to $0.5$, liveness is guaranteed even
against an adaptive adversary. Furthermore, we show that even a constant
fraction $\gamma$ of nodes following the DSA is sufficient to ensure a long
term fraction of honest blocks in any shard is close to $\gamma$.

  * •

The overhead for each node associated with a block of size $B$ in any shard is
$O(\log B)$ since the overhead of each primitive is $O(\log B)$. SMR requires
$O(\log B)$ overhead to read the Merkle proof of each chunk, data availability
and state commitment also require $O(\log B)$ resources as stated in the
primtives above. The total overhead ratio is $O(\frac{K\log B}{B})$, which can
be made arbitrarily small by making $B$ large.

##  3\. Dynamic Self Allocation Engine

The dynamic self allocation engine is a sequential algorithm that guides
honest nodes to allocate themselves to shards in different proportions,
adapting to the past adversarial allocation behavior. The DSA algorithm aims
to guarantee that the time average fraction of honest to adversarial nodes in
any shard is above any desired level. A fundamental information theoretic
question is a characterization of the space of time average fractions that can
be achieved by the best DSA algorithm (here we do not constrain the
computational complexity of algorithm). A practical, and also theoretical,
question is the characterization of the performance of computationally simple
DSA algorithms and the explicit identification of such algorithms. We formally
state these questions below; the main result of this section is a complete
solution to these theoretical questions – this comprises the key technical
contribution of this paper. We discuss connections of our results to game
theoretic literature (dynamic Stakelberg games (von Stackelberg, 2011)) and is
of independent mathematical interest.

Problem Statement. There are $N$ nodes (including both honest and adversarial)
and $K$ shards. The fraction of honest nodes is $(1-\beta)=\gamma$ (the
“power” of honest nodes) and each honest node uses the DSA algorithm to
allocate itself to a shard. The adversaries collude, observe the honest node
allocations and then allocate themselves. The goal of the adversary is to
minimize the ratio of honest to total nodes (the “honest fraction”) in any
shard – this will throttle the throughput of the shard leading to liveness
vulnerabilities (as discussed in Section 2.2). The honest nodes switch at
periodic intervals (time scale of confirmed blocks in the consensus engine).
Even though the adversarial nodes can switch faster, we see that they cannot
reduce the time average honest fraction of the worst performing shard further
than reallocating themselves at the same rate as honest nodes. This leads to
the following mathematical formulation of a vector dynamic game described
below, focusing on the mean honest fraction allocations to each shard. The
actual DSA algorithm is to be implemented by every node and is necessarily
distributed – a randomized distributed implementation (with the goal of
mimicking the mean honest fraction prescribed by the solution to the dynamic
game below) is discussed in a later Section 3.3.

We suppose a timescale where the consensus engine confirms one block per unit
time. We measure the honest node fractions in shard at integer times $t$; this
fraction would correspond to the ratio of honest blocks to total blocks in any
shard, formed in time $[t-1,t]$ referred by the consensus block confirmed at
time $t$. We refer to the interval $[t-1,t]$ as round $t$. Let $r_{i}[t]$
denote the honest node fraction at time $t$ (for round $t$) in shard $i$ and
$\bar{r}_{i}(t)$ denote the time-average.

(1) $\displaystyle r_{i}(t)$
$\displaystyle=\frac{\gamma_{i}(t)}{\gamma_{i}(t)+\beta_{i}(t)};\quad\bar{r}(t)=\frac{1}{t}\sum_{j=1}^{t}r_{i}(j).$

Let $\mathbf{r}(t)=[r_{1}(t),r_{2}(t),..,r_{K}(t)]$ and
$\mathbf{\bar{r}}(t)=[\bar{r}_{1}(t),\bar{r}_{2}(t),..,\bar{r}_{K}(t)]$ denote
the corresponding vectors encompassing all the $K$ shards.

We define the main optimization objective function, the solution of which is
the honest strategy that can achieve a worst case shard honest fraction of
$\psi(K)$ given any worst-case adversarial action:

(2)
$\psi(T)=\max_{\\{f_{t}\\}_{t}}\,\min_{\\{\beta_{i}(t)\\}_{i,t}}\,\min_{i}\left\\{\bar{r}_{i}(T)\right\\}.$

A DSA algorithm specifies the honest node re-allocation strategy: for each $t$
the re-allocation is a function as follows:

(3)
$f_{t}:(\boldsymbol{\beta}(1),...\boldsymbol{\beta}(t-1),\boldsymbol{\gamma}(1),\ldots\boldsymbol{\gamma}(t-1))\rightarrow\boldsymbol{\gamma}(t),$

satisfying the constraint $\sum_{i=1}^{K}\gamma_{i}(t)=\gamma$.

We define $\psi_{f_{t}}(K)$: the honest fraction of the worst performing shard
under a worst case adversary as follows:

(4)
$\psi_{f_{t}}(T)=\,\min_{\\{\beta_{i}(t)\\}_{i,t}}\,\min_{i}\left\\{\bar{r}_{i}(T)\right\\}.$

Note that the adversary action in round $t$ is allowed to depend on the honest
node re-allocation policy at round $t$.

Information Theoretic Limits. We see that any optimal honest strategy cannot
obtain a time averaged honest fraction greater than $\gamma$ in the worst
performing shard under an optimal adversarial strategy:

(5) $\displaystyle\psi(T)\leq\gamma.$

The above inequality is obtained since irrespective of the honest allocation,
an adversary can simply replicate the honest node allocation and set
$\beta_{i}(t)=\frac{\beta}{\gamma}\gamma_{i}(t)$, thus rendering the honest
fraction of each shard as $\gamma$. The key question is whether this upper
bound is actually achievable. If so, then this would be a striking and
positive result: the honest nodes can rebalance the allocations optimally,
i.e., the time average fraction of honest nodes in each shard is always the
same as the overall fraction of honest nodes (which is $\gamma$). This would
imply that the adversary is ineffective in overcrowding any shard, even
minimally. The main result of this section is that this is indeed achievable,
for large enough time window $T$ over which the average is taken. Towards
building an intuition towards this result, and the nature of the optimal
honest policy and the corresponding performance, we discuss next a few
baseline honest node strategies and analyze their performance.

Figure 5. Throughput suppression: Adversaries congregate in shard 1.

###  3.1. Approach

Static strategies. Consider a static self-allocation scheme where honest nodes
allocate themselves uniformly to one of $K$ shards, i.e.,
$\gamma_{i}(t)=\frac{\gamma}{K}\forall i\in[K]$. This strategy is very
vulnerable to adversarial action: an adversary simply targets shard $1$ and
throttles its honest fraction by allocating all its power to this shard (i.e.,
$\beta_{1}(t)=\beta$). This renders the honest fraction of shard 1 as
$\frac{\gamma/K}{\gamma/K+\beta}=O(1/K)$ which approaches 0 for large $K$ and
is very sub-optimal compared to the information theoretic limit. Thus the
honest nodes have to adapt to adversarial action.

A simple dynamic strategy. A simple adaptive action by the honest nodes is the
following: half the honest nodes distribute themselves uniformly randomly
across $K$ shards and the other half follows the adversarial distribution of
the past round.

(6) $\displaystyle
f_{t}:={\gamma_{i}}(t)=\\{\frac{\gamma}{2\beta}\beta_{i}(t-1)+\frac{\gamma}{2K}\\}.$

The idea is that if the adversary congregates in one shard, then at least half
the honest nodes react to this congregation and ameliorate any degradation in
performance in that shard. We are able to show the following performance
result; the proof is in Appendix A.1.

###### Proposition 3.1.

For large enough $T$,

(7) $\displaystyle\Omega\left(\frac{1}{\log K}\right)\leq\psi_{f_{t}}(T)\leq
O\left(\frac{\log\log K}{\log K}\right).$

This shows that this dynamic allocation policy is much improved compared to
the static allocation policy (from $O(1/K)$ to $O(1/\log K)$), but the
performance still degrades to zero as $K$ grows, while the information
theoretic limit is a constant (independent of $K$). An adversarial attack on
shard 1 which renders a honest fraction of $O(\frac{\log(K)}{\log(\log(K))})$
is illustrated in Figure 6. We see from the proof in Appendix A.1 that the
analysis is very specific to the structure of the dynamic honest policy in
Equation (6) and this does not provide any intuition towards designing an
improved honest policy. We make connections to game theoretic literature next,
which provides us a broader view of this problem and classical results
associated with this class of $\max\min$ games.

Figure 6. Simple DSA policy from Equation (6): adversary gradually attacks
shard 1, and honest nodes follow it with a delay of one round, the attack is
reset when the adversary has allocated all it’s power to shard 1

Dynamic games. Our core optimization problem in Equation (2) looks somewhat
similar to an online convex optimization problem (Arora et al., 2012).
However, the combinatorial optimization $\min_{i}\bar{r}_{i}(T)$ outside the
summation is a key aspect of departure from the online convex optimization
setting, rendering that approach nowhere immediate. An alternative view is
provided by dynamic Stackelberg games (von Stackelberg, 2011), with zero step
rewards and a terminal reward of $\min_{i}\bar{r}_{i}(T)$, where the adversary
can take action after knowing the action of the honest nodes. However, solving
the optimal honest policy iteratively (dynamic programming approach) does not
yield an analytical form due to the specific reward design we have. If the
reward of $\min_{i}\bar{r}_{i}(T)$ were replaced by the vector
$\boldsymbol{\bar{r}}$, then this game is related to the classical Blackwell
approachability (Blackwell et al., 1956) (an extension of von Neumann’s
classical minimax matrix game (Von Neumann, 1953)) and provides guidance as to
how the scalar reward of $\min_{i}\bar{r}_{i}(T)$ be addressed. This is the
crux of our main result, presented next.

###  3.2. Dynamic Self allocation

Consider the following Free2Shard policy, $f_{t}^{\textit{F2S}}$ where
$\gamma_{i}(t)$ is generated as follows:

(8) $\displaystyle
f_{t}^{\textit{F2S}}:\gamma_{i}(t)=\gamma\frac{u_{i}(t-1)}{\sum_{i=1}^{K}u_{i}(t-1)};\quad\quad
u_{i}(t-1)=(\gamma-\bar{r}_{i}(t-1))^{+}.$

The main idea is to allocate honest power to shards that are performing the
worst, i.e., shards with highest lag from the target honest fraction $\gamma$
and not waste any honest power by allocating zero power to shards which have
time averaged honest fraction greater than the target. Our main result is in
the following theorem.

###### Theorem 3.2.

For any adversarial strategy,

(9)
$\displaystyle\psi_{f_{t}^{\textit{F2S}}}(T)\geq\gamma\left(1-\sqrt{\frac{K}{T}}\right).$

We observe that $\psi_{f_{t}^{\textit{F2S}}}(T)\geq c\gamma$ for all
$T>\frac{K}{(1-c)^{2}\gamma^{2}}$, this means that we achieve
$\psi_{f_{t}^{\textit{F2S}}}(T)$ is arbitrarily close to the information
theoretic limit of $\gamma$ for $T$ large enough, thus providing tight bounds
on approaching the information theoretic limit.

Proof: We show that following $f_{t}^{\textit{F2S}}$ allocation, the average
honest fraction vector $\boldsymbol{\bar{r}(t)}$ approaches the convex set
$C_{\gamma}$ in $\mathbb{R}^{K}$ defined as follows:

(10) $\displaystyle C_{\gamma}$ $\displaystyle=[\gamma,1]^{K}\quad x\in[0,1]$

so $\boldsymbol{\bar{r}(t)}\in C_{\gamma}$ implies
$\min_{i}\bar{r}_{i}(t)\geq\gamma$. Let $\boldsymbol{\pi(t)}$ denote the
Euclidean projection of $\boldsymbol{\bar{r}(t)}$ to the convex set
$C_{\gamma}$. Let $\boldsymbol{P_{t+1}}(\boldsymbol{x})$ denote the hyperplane
perpendicular to $\boldsymbol{\pi(t)}-\boldsymbol{\bar{r}(t)}$ and containing
$\boldsymbol{\pi(t)}$. Observe that
$\boldsymbol{\pi(t)}-\boldsymbol{\bar{r}(t)}=\boldsymbol{u(t)}$:

(11) $\displaystyle\boldsymbol{P_{t+1}}(\boldsymbol{x})$
$\displaystyle:\boldsymbol{u(t)}.\boldsymbol{x}-\gamma\sum_{i=1}^{K}u_{i}(t)=0.$

We show using the strategy space inequality in Appendix A.2.1 (Equation (27),
set $s=K$), the following:

(12)
$\displaystyle\boldsymbol{u(t)}\cdot\boldsymbol{r(t+1)}-\gamma\sum_{i=1}^{K}u_{i}(t)$
$\displaystyle\geq 0\;\quad\forall\boldsymbol{\beta(t+1)}$
$\displaystyle\boldsymbol{u(t)}\cdot\boldsymbol{\bar{r}(t)}-\gamma\sum_{i=1}^{K}u_{i}(t)$
$\displaystyle\leq 0$

The above two inequalities imply that $\boldsymbol{r(t+1)}$ and
$\boldsymbol{\bar{r}(t)}$ lie on different sides of $\boldsymbol{P_{t+1}}$ as
depicted in figure 7

Figure 7. $\boldsymbol{\bar{r}(t)}$ and $\boldsymbol{r(t+1)}$ lie on different
sides of the hyperplane $P_{t+1}$

Let us define $d_{t}$ as the euclidean distance of $\boldsymbol{\bar{r}}(t)$
from the convex set $C_{\gamma}$, i.e.
$d_{t}=||\boldsymbol{\bar{r}}(t)-\boldsymbol{\pi(t)}||$ ,
$d(\boldsymbol{a,b})=||\boldsymbol{a}-\boldsymbol{b}||$ for any
$\boldsymbol{a},\boldsymbol{b}\in\mathbf{R}^{K}$. we show that

$\displaystyle d^{2}_{t+1}$
$\displaystyle=d^{2}(\mathbf{\bar{r}(t+1)},\boldsymbol{\pi(t+1)})\leq
d^{2}(\mathbf{\bar{r}(t+1)},\boldsymbol{\pi(t)})$
$\displaystyle=\left\lVert\mathbf{\bar{r}(t+1)}-\boldsymbol{\pi(t)}\right\rVert^{2}_{2}$
$\displaystyle=\left\lVert\frac{t}{t+1}\mathbf{\bar{r}(t)}+\frac{1}{t+1}\mathbf{r(t+1)}-\boldsymbol{\pi(t)}\right\rVert^{2}_{2}$
$\displaystyle=\left\lVert\frac{t}{t+1}(\mathbf{\bar{r}(t)}-\boldsymbol{\pi(t)})+\frac{1}{t+1}(\mathbf{r(t+1)}-\boldsymbol{\pi(t)})\right\rVert^{2}_{2}$
$\displaystyle=(\frac{t}{t+1})^{2}\left\lVert\mathbf{\bar{r}(t)}-\boldsymbol{\pi(t)}\right\rVert^{2}_{2}+(\frac{1}{t+1})^{2}\left\lVert\mathbf{r(t+1)}-\boldsymbol{\pi(t)}\right\rVert^{2}_{2}$
$\displaystyle+\frac{2t}{(t+1)^{2}}(\mathbf{\bar{r}(t)}-\boldsymbol{\pi(t)}).(\mathbf{r(t+1)}-\boldsymbol{\pi(t)}).$

$\displaystyle(t+1)^{2}d^{2}_{t+1}-t_{2}d^{2}_{t}$
$\displaystyle\leq\left\lVert\mathbf{r(t+1)}-\boldsymbol{\pi(t)}\right\rVert^{2}_{2}$
$\displaystyle+2t\cdot((\boldsymbol{\pi(t)}-\mathbf{\bar{r}(t)})\cdot(\boldsymbol{\pi(t)}-\mathbf{r(t+1)})).$

(a) Convergence to $C_{0.5}$

(b) 5x Zoom

Figure 8. Evolution of ($\bar{r_{1}(t)}$,$\bar{r_{2}(t)}$), observe that the
distance of ($\bar{r_{1}(t)}$,$\bar{r_{2}(t)}$) from ($0.5$,$0.5$) reduces
with time (arrows signify causality)

$\boldsymbol{r(t+1)}$ and $\boldsymbol{\bar{r}(t)}$ lie on different sides of
$\boldsymbol{P_{t+1}}$ hence,

$\displaystyle
2t\cdot((\boldsymbol{\pi_{C_{\gamma}}(t)}-\mathbf{\bar{r}(t)}).(\boldsymbol{\pi_{C_{\gamma}}(t)}-\mathbf{r(t+1)}))\leq
0$

Moreover,
$\left\lVert\mathbf{r(t+1)}-\boldsymbol{\pi_{C_{\gamma}}(t)}\right\rVert^{2}_{2}\leq\gamma^{2}K$
and combining the above two inequalities, we get:
$(t+1)^{2}d^{2}_{t+1}-t^{2}d^{2}_{t}\leq\gamma^{2}K$. Summing terms over
$t\in\\{1,..,T-1\\}$, we get $d_{T}\leq\gamma\sqrt{\frac{K}{T}}$ and observe
that $d_{T}\geq(\gamma-\min_{i}\bar{r}_{i}(T))^{+}$. Equivalently,
$\min_{i}\bar{r}_{i}(T)\geq\gamma-d_{T}$ and thus
$\psi_{f_{t}^{\textit{F2S}}}(T)\leq\gamma(1-\sqrt{\frac{K}{T}})$.

The convergence of $\bar{r}_{i}(t)$ for 2 worst performing shards is
illustrated in figure 8.

###  3.3. Distributed Dynamic Self Allocation

Thus far we have studied the dynamic self allocation policy in the lens of the
mean fraction of the honest nodes. What we really need is a (randomized) DSA
policy that can be run by each node locally. A natural strategy is the
following: each honest node uses the Free2Shard DSA policy to calculate the
honest node fractions for each shard and then allocates itself to one of the
shards randomly, proportional to the fractions prescribed by the Free2Shard
policy. While this strategy is natural and performs well in experiments (cf.
Section 3.5) we have not been able to formally evaluate its theoretical
performance. A slightly modified strategy, described below, does enable a
theoretical evaluation.

Free2Shard-dist DSA policy diverges from Free2Shard DSA policy in the
following way: The policy aims to achieve a honest node fraction in each shard
of $h$, strictly smaller than the information theoretic optimal value of
$\gamma$. With a slight abuse of notation, we define
$u_{i}(t-1)=(h-\bar{r}_{i}(t-1))+$. The algorithm allows honest nodes to focus
on $s$ out of $K$ shards at a time; we order the quantities
$u_{1}(t-1),\ldots,u_{K}(t-1)$ and define $\tilde{u_{i}}(t-1)=u_{i}(t-1)$ if
the index $i$ is in the highest $s$ order statistics. For other indices $i$,
we set $\tilde{u_{i}}(t-1)=0$. We follow the Free2Shard policy by substituting
$\tilde{u_{i}}(t-1)$ in place of $u_{i}(t-1)$ in Equation (8), so
$\tilde{\gamma}_{i}=\gamma\frac{\tilde{u}_{i}}{\sum_{i=1}^{K}\tilde{u}_{i}}$.
Moreover, to ensure that each of the $s$ prioritized shards get some honest
nodes, we lower bound their prescribed honest policy to $q/(1+2q)s$, for some
constant $q$ close to 0. We ensure this by projecting the non-zero prescribed
honest power $\tilde{\gamma}_{i}(t)$ to the set $C_{q/s}$; we use the notation
${\rm Proj}(\boldsymbol{\tilde{\gamma}(t)},C_{q/s})$ to denote such Euclidean
projection. In summary, Free2Shard-dist DSA policy is the following:

(13) $\displaystyle f_{t}^{\textit{F2S-dist}}(h,q,s):\boldsymbol{\gamma(t)}$
$\displaystyle=\frac{1}{1+q/\gamma}\quad{\rm
Proj}(\boldsymbol{\tilde{\gamma}(t)},C_{q/s}).$

Notice that the honest node fraction is no longer deterministic since the
honest node allocation is randomized (and follows a multinomial distribution);
each shard’s marginal distribution of honest power is $\Gamma_{i}(t)$ is
distributed as $\frac{1}{N}{\rm Binomial}(n,\gamma_{i}(t))$ and each shard’s
marginal distribution of honest node fraction $r_{i}(t)$ is distributed as
$\frac{\Gamma_{i}(t)}{\Gamma_{i}(t)+\beta_{i}(t)}$. Notice that
$\psi_{f_{t}^{\textit{F2S-dist}}}$ is now a random variable, and we show a
concentration bound below; the proof is deferred to Appendix A.2. This result
shows that with high probability the information theoretic upper bound of
$\gamma$ can be achieved by the appropriate honest policy.

###### Theorem 3.3.

For any adversarial strategy, with probability $1-\delta$,

(14)
$\displaystyle\psi_{f_{t}^{\textit{F2S-dist}}(h,q,s)}(T)\geq\gamma\left(\frac{h}{\gamma}-\frac{1}{\gamma}\sqrt{h^{2}\frac{K}{T}+4hs\sqrt{\frac{2}{T}\log\frac{2}{\delta}}}\right).$

We note that
$h=(1-se^{-n\frac{q}{(1+2q)s}(-c+clogc+1)})\frac{cs}{K(1-2q)}\gamma$ can be
set close to $\gamma$ by choosing the variables $q,s,c$ appropriately.

Outline of Proof. Following the same pattern as the proof of Free2Shard DSA,
we show that the average honest fraction vector $\boldsymbol{\bar{r}(t)}$
approaches the convex set $C_{h}$.

We first prove a strategy space inequality which states the following:

(15)
$\displaystyle\max_{\mathbf{\gamma}}\min_{\mathbf{\beta}}\sum_{i=1}^{K}u_{i}(t-1)\frac{\tilde{\gamma}_{i}(t)}{\tilde{\gamma}_{i}(t)+\beta_{i}(t)}\geq\gamma\frac{s}{K}\sum_{i=1}^{K}u_{i}(t-1)$

We then modify the target allocation policy as $\boldsymbol{\gamma}$ which
ensures that $\gamma_{i}\geq\frac{b}{s}$ as shown in Equation (13) where $b$
is a constant and $q=b/(1-2b)$. The new allocation policy leads to a modified
strategy space inequality given by:

(16)
$\displaystyle\min_{\boldsymbol{\beta}}\sum_{i}u_{i}(t-1)\frac{\gamma_{i}(t)}{\gamma_{i}(t)+\beta_{i}(t)}$
$\displaystyle\geq\frac{s}{K}\gamma(1-2b)\sum_{i=1}^{K}u_{i}(t-1)$

We now show that if every honest node chooses a shard randomly according to a
choice distribution given by $\boldsymbol{\gamma}$ defined in Equation (13),
we get a stochastic strategy space inequality given by:

(17) $\displaystyle\mathbb{E}_{\boldsymbol{\Gamma(t)}}$
$\displaystyle\left[\min_{\boldsymbol{\beta(t)}}\boldsymbol{u(t-1)}.\boldsymbol{r(t)}\right]\geq
h\sum_{i=1}^{K}u_{i},$

similar to Equation (12) in Free2Shard DSA proof. We then show that following
the above honest allocation strategy time averaged honest fraction approaches
the convex set $C_{h}$ with distance decreasing with time $T$ as:

(18) $\displaystyle d^{2}_{T}$ $\displaystyle\leq
h^{2}\frac{K}{T}+\frac{2}{T}\sum_{t=1}^{T-1}\frac{t}{T}(Y_{t})$

where
$Y_{t}=(\mathbb{E}_{\Gamma_{i}(t)}\left[\sum_{i}u_{i}(t-1)r_{i}(t)\right]-((\boldsymbol{u(t-1)})\cdot\mathbf{r(t)})$
is a martingale difference sequence with respect to the history at time $t$
and $|Y_{t}|\leq 2hs$. Using the Azuma- Hoeffding inequality, we have

(19)
$\displaystyle\mathbb{P}\left(\frac{1}{T}\left\lVert\sum_{t=1}^{T-1}Y_{t}\right\rVert>\epsilon_{m}\right)\leq
2e^{-\frac{T\epsilon_{m}^{2}}{8h^{2}s^{2}}}.$

This allows us to conclude that with probability $(1-\delta)$, the distance to
convex set converges to 0 as $d^{2}_{T}\leq
h^{2}\frac{K}{T}+4hs\sqrt{\frac{2}{T}\log(\frac{2}{\delta})}$. We observe that
$d_{T}\geq(\gamma-\min_{i}\bar{r}_{i}(T))^{+}$. Equivalently,
$\min_{i}\bar{r}_{i}(T)\geq\gamma-d_{T}$ and thus
$\psi_{f_{t}^{\textit{F2S-dist}}(h,q,s)}(T)\geq\gamma\left(\frac{h}{\gamma}-\frac{1}{\gamma}\sqrt{h^{2}\frac{K}{T}+4hs\sqrt{\frac{2}{T}\log\frac{2}{\delta}}}\right)$.

###  3.4. Number of Shards and Nodes

Conventional modeling (and the corresponding sharding literature) supposes
that the number of nodes $N$ is much larger than the number of shards $K$.
This modeling is central to the working of node to shard (N2S) allocations:
this way each shard has a sufficient number of honest nodes. In practice, one
can imagine several shards being inactive during certain periods of time and
conceivably $K>N$. In this scenario, we can derive a tighter information
theoretic bound than the one in Equation (5) since $\psi(T)=\gamma$ implies
that each shard remains active at all rounds even if there aren’t sufficient
honest nodes to maintain all the shards in any round; this is done next.

Information Theoretic Limit The sum of honest nodes of all shards is limited
by the total number of honest nodes in the system, since at every round, there
will be at most $N$ shards which can be maintained by honest nodes, and the
adversary can set it’s policy:
$B_{i}(t,\Gamma_{i}(t))=\frac{\beta}{\gamma}\Gamma_{i}(t)$. Thus, the honest
fraction of the $N$ out of $K$ shards which are non zero is $\gamma$, yielding
the following bounds:

(20) $\displaystyle\max_{\\{f_{t}\\}_{t}}\,\min_{\\{\beta_{i}(t)\\}_{i,t}}\,$
$\displaystyle\sum_{i}\left\\{\bar{r}_{i}(T)\right\\}\leq\gamma N$
$\displaystyle\max_{\\{f_{t}\\}_{t}}\,\min_{\\{\beta_{i}(t)\\}_{i,t}}\,\min_{i}\bar{r}_{i}(T)$
$\displaystyle\leq\frac{1}{K}\sum_{i}\bar{r}_{i}(T)$ (21)
$\displaystyle\psi(T)\leq\gamma N/K.$

We note that the Free2Shard-dist self allocation strategy smoothly meets this
new upper bound; this is done via the honest nodes focusing only on a subset
of shards in a round to achieve $\psi_{f_{t}^{\textit{F2S-dist}}(h,q,s)}(T)$
which is within a $O(\frac{1}{\log N})$ multiplicative factor of the improved
information theoretic upper bound: Theorem 3.3 states that for large enough
$T$, $\psi_{f_{t}^{\textit{F2S-dist}}(h,q,s)}(T)\geq 0.5h$. We observe that
$h\geq\frac{a}{\log N}\frac{N}{K}$ where $a$ depends on the choice of $c,q$
and $s=\frac{N}{4\log N}$. Thus,
$\psi_{f_{t}^{\textit{F2S-dist}}(h,q,s)}(T)\geq\frac{a}{2\log
N}\frac{N}{K}\gamma$ which is within $O(\frac{1}{\log N})$ multiplicative
factor of the information theoretic limit in Equation (21).

###  3.5. Experiments

We empirically verify the robustness of our protocol against various
randomness associated with a practical implementation such as the
(theoretically accounted for) randomness in honest node allocation and the
bias in estimation of adversarial and honest distributions. Our implementation
consists of $K=100$ shards with varying number of nodes $N$ and heterogenous
target honest node fractions. This experiment models a realistic setting where
the honest nodes do not know the honest fraction of all shards, have to
estimate the honest node fraction in the shards by calculating the net power
(i.e., total number of nodes) and the estimated honest node allocation. We set
$\beta=0.5$ in all our experiments, the largest possible adversarial power
that can be tolerated for security of the consensus engine (and the overall
Free2Shard architecture).

##### Adversarial strategy

. The adversarial action is worst-case and cannot be empirically evaluated, so
we identify an adversary that has the following capabilities. It can throttle
the honest node fraction in any shard to be as small as $\frac{\log K}{K}$ for
as long as $\tau=\frac{\log K}{\log\log K}$. We state this formally, deferring
the proof to Appendix A.3.

###### Proposition 3.4.

Consider an adversary that works in periods of length $\tau$. In any period at
a round $t$, the adversary uniformly allocates its power on the
$K\left(\frac{1}{\log K}\right)^{t}$ worst performing shards. The period ends
at $t=\tau$ and the adversary restarts with $t=1$.

Then for any honest policy, the worst case shard’s honest node fraction is
less than $O(\frac{\log K}{K})$ for all rounds $t\leq\tau$.

Homogeneous sharding with $N>K$. With $K=100,N=1000,\beta=0.5$ we simulate the
adversarial strategy above and the distributed (randomized) versions of
Free2Shard and Free2Shard-dist as the honest policy. In this homogeneous
setting, we aim to maintain the same honest node fraction in each of the
shards (equal to 0.5 here). We plot the worst time average honest node
fraction across the shards as a function of time in Figure 9(a) and make the
following observations. (a) Free2Shard and Free2Shard-dist have similar
performances and favorable to the theoretical upper bound (derived for the
worst-case adversary); (b) since $N$ is sufficiently larger than $K$, there
are enough honest nodes to allocate to each shard and thus the honest node
fraction in each shard is able to meet the target.

Homogeneous sharding with $N<K$. With $N=10,K=100,\beta=0.5$, we simulate the
adversarial strategy above and the distributed (randomized) versions of
Free2Shard and Free2Shard-proj as the honest policy. In this homogeneous
setting, we aim to maintain the same honest node fraction in each of the
shards – since there are more shards than nodes, the largest possible target
is $\frac{N(1-\beta)}{K}=0.05$. We plot the worst time average honest node
fraction across the shards as a function of time in Figure 9(b) and make the
following observations. (a) Free2Shard and Free2Shard-proj have similar
performances and favorable to the theoretical upper bound (derived for the
worst-case adversary); (b) even though $N$ is sufficiently smaller than $K$,
so each node’s randomized decision cannot be expected to average the honest
node fraction in each shard to the deterministic values proposed by
Free2Shard, we see that the performance in meeting the targets is surprisingly
strong. A theoretical justification for this phenomenon is of great interest
and is deferred to future work.

(a) $N=10K$

(b) $N=0.1K$

Figure 9. Homogeneous sharding comparison between Free2Shard and Free2Shard
-dist

##### Heterogeneous sharding with $N<K$

. In practice, different shards have different activity levels, demanding
different target levels of participation from the nodes. We propose the target
honest fraction of each shard to decrease as
$1/(\left\lceil{i/5}\right\rceil+1)$, with $N=10,K=100,\beta=0.5$; where $i$
is the index of the shard. We plot the time average honest node fraction
across the shards at the end of the simulation in Figure 10 and make the
following observations. (a) Free2Shard supports heterogeneous target honest
fraction vector allocation across shards; (b) even though $N$ is sufficiently
smaller than $K$, we can set some shards to achieve a target honest factor of
$1-\beta$ which is the best we can achieve even with $N>K$. We see that the
performance in meeting the targets is strong; a theoretical justification for
this strong performance for heterogeneous sharding is of great interest and is
deferred to future work.

Figure 10. Comparison between target honest fraction set for heterogeneous
sharding and average honest fraction achieved at the end of the experiment

##  4\. Free2Shard Architecture Design

In this section we discuss in detail the Free2Shard sharding architecture, an
overview of which was provided in Section 2.4.

Each node $i$ in the network has an identity which is comprised of a pair
$(nsk_{i},npk_{i})$ the node secret key (known only to the node) and node
public key (known to everyone). We will assume that the overall blockchain can
be split into $K$ sub-ledgers (called shards) each comprising of a entirely
independent set of transactions (submitted by shard clients). We can use
methods developed for inter-sharding in other sharding algorithms (for
example, (Kokoris-Kogias et al., 2018)), and will briefly allude to this in
Section 5. Each shard will have its own peer-to-peer (p2p) network in which
shard transactions are broadcasted. Any node desirous of reading the
activities of the shard can join the p2p network.

Free2Shard sharding architecture relies on a State Machine replication engine
(SMR) maintained by all the peers in the network to create a total ordered
log. Shard blocks are ordered using the hash pointers on the ordered log.
Since the ordered log contains only hash of each shard block, data
availability is ensured by invoking a separate voting mechanism based on a
recent primitive, Coded Merkle Tree (Yu et al., 2019). Free2Shard-dist DSA
policy ensures liveness and high throughput against adaptive adversary.
Finally, the rotation of nodes to a new shard is facilitated by periodic state
commitments on the ordered log. We explain each of these functionalities below
and show that they have $o(1)$ overhead as the shard block size $B$ becomes
large.

The adaptive-adversary resistant SMR has a mechansim for growing the ordered
log based on transactions sent to it, we further assume that it has an upper-
bound on the latency of including honest transactions into the ordered log
(which is independent of $N$). This property holds for both the Algorand and
Ouroboros Praos protocols. We will assume that the ordered log is comprised of
a sequence of transactions organized into blocks (we will refer to the SMR-
block-number as the latest block number in the SMR). We do not require fresh
randomness from the ledger, but in practice, this can be useful and in which
case instead of the SMR-block-number, we will use the randomness associated
with SMR-block-number. We are now ready to discuss the Free2Shard architecture
and its components in detail.

###  4.1. Free2Shard components and design

Shard block mining: We create a “mining” mechanism (a permissioning mechanism)
for allowing the creation of shard blocks. A node $i$ can propose a shard
block for inclusion in the ordered log if $H(npk_{i},SMR_{no})$ is small,
where $H$ is a cryptographic hash function. A node will have to specify one of
the shard-id on which wishes to mine a block, as well as the hash of the shard
block. The SMR engine collects all the hash outputs from the nodes, and
selects the smallest $\kappa$(a constant) output values per shard to propose
blocks. The shard-hashes enter the ordered log. Note that each peer can only
generate at most one shard-block per SMR-block. This ensures that even
adversarial nodes have to make a choice on which shard it is mining.

The above mining protocol ensures if $\Gamma_{i}\cdot N$ and $\beta_{i}\cdot
N$ nodes are interested in mining in shard $i$, then, owing to the uniform
nature of the hash output string, the average fraction of honest shard blocks
mined is $\Gamma_{i}/(\Gamma_{i}+\beta_{i})$, and consistent with the quantity
studied in Section 3. The mining mechanism thus ensures that if a shard has a
capacity to process $R$ transactions per second it will process
$R\Gamma_{i}/(\Gamma_{i}+\beta_{i})$ honest transactions per second.

While we describe our protocol using hash functions for simplicity, in order
to be resilient to an adaptive adversary, we will use verifiable random
functions (VRF) (Micali et al., 1999; Dodis and Yampolskiy, 2005). VRF ensures
that the output of the function is not predictable by any other node a priori.
We refer the reader to Section B.1 for a brief description of VRF.

Shard ledger: The ordered log of shard block hash pointers corresponding to a
given shard-id induces a shard ledger comprising of the corresponding shard
blocks. We note that the architecture does not guarantee validity of every
transaction in the shard ledger, since SMR nodes do not checked for validity.
However, this is not an issue as long as there is a consistent execution
engine that will interpret the shard transactions. This is a classic idea in
distributed systems of decoupling execution from ordering (Yin et al., 2003),
and has found applications in blockchain scaling architectures as well
(Balakrishnan et al., 2013).

Data Availability: Even though the shard blocks need not be valid, they still
need to be available for retrieval. We accomplish this availability check
using a mechanism by which all nodes vote through the SMR on whether a block
is available. The key idea is the following: the node whose shard block hash
got included in the ordered log, now sends forth small chunks of the block
encoded appropriately, one for each node. The original block is divided into
$K$ chunks and is coded to form $N$ chunks. Which chunk is to be sent to which
node is determined by a $H(npk_{i},SMR_{no})$ (a random mapping of the public
key of the recipient $npk_{i}$ along with the SMR block number).

Now in the SMR, each node casts its vote on whether a previous shard block
pointer is valid or not, depending on whether it received its chunk. We need
to establish three properties: (1) enough number of nodes received the chunk,
(2) the chunk satisfied the hash of the coded block, and (3) the block was
correctly coded (as an adversary may do otherwise). The first constraint can
be satisfied as long as there is a majority of votes cast for validity. The
$\beta<0.5$ fraction of nodes are adversarial and may lie, however, the
remaining $a=0.5-\beta$ honest nodes have indeed received the chunk. Thus as
long as $aN$ chunks are sufficient to reconstruct the block using the code,
property (1) is satisfied. Property (2) can be satisfied by requiring that the
posted hash pointer corresponds to the coded block rather than the uncoded
block. Finally, Property (3) is the most subtle property to satisfy. We note
that recent work on Coded-Merkle-Tree has solved this problem by enabling
short fraud proofs (short statements of length $\Theta(\log B)$) that can
prove that the block was incorrectly coded - and such proofs are readily
forthcoming as long as there is enough chunks to decode a correctly coded
block. A shard block, even when voted for by a majority, will be considered
invalid, if some node posts a fraud proof.

State commitment: When nodes rotate between shards, they will need to fully
download the new shard ledger as well as execute it from the beginning of
history in order to synchronize to that shard. This can be extremely resource
intensive and can completely drown out any gain due to sharding. We point out
the multi-consensus protocols such as (Luu et al., 2016; Kokoris-Kogias et
al., 2018; Zamani et al., 2018) which assume majority-honest in each shard do
not have this problem, as they can immediately assume that any previous
transaction that has been signed by a majority is valid. Instead, if the node
could acquire a trustworthy state after executing till the previous block, it
can easily rotate into the shard. We note that one possibility is to use
verifiable computing primitives to assert that the state of the shard ledger
as executed by another node is correct (Parno et al., 2013; Ben-Sasson et al.,
2014, 2018), however, these results are still not yet practically applicable
to general program execution, so we resort to a different mechansim for state
commitments.

State commitments consists of the merkle root of a Merkle Patricia Trie (Luu
and Rush, 2017) of a shard’s execution state, which is posted at regular
intervals of $E$ SMR-blocks called epochs. They serve as checkpoints for fast
bootstrap and inter-shard transactions. The state commitment is posted to the
SMR engine by a epoch leader who is elected every epoch. Each node locally
computes H($nsk_{i}$,$SMR_{no}$, shard-id) for all $K$ shards. If for shard
$i$, the output of the hash is less than a threshold, the node assigns itself
as a epoch leader for the next epoch in that shard. The threshold is set
globally to ensure that roughly a constant number of nodes are always elected
as epoch leaders per shard.

The state commitment is termed invalid if it corresponds to an incorrect
execution state. We can assume that epoch leaders can be byzantine and post
invalid state commitments. We use a round based interactive fraud proof
protocol inspired from Truebit (Teutsch and Reitwießner, 2019) and Arbitrum
(Kalodner et al., 2018) to detect such invalid commitments (we refer the
reader to (Teutsch and Reitwießner, 2019) for a detailed explanation of the
protocol). An epoch is split into $R$ rounds with each round consisting of $G$
SMR blocks. The interactions between the epoch leader and a challenger is
illustrated in Figure 11 can be briefly described as follows:

  1. (1)

The epoch leader posts $S_{s}$ intermediate states for the challenged state.

  2. (2)

A challenger responds with a number indicating the first intermediate state
when the challengers view differs from the leader

  3. (3)

The game continues to the next round with the leader posting intermediate
states for the smaller challenged state and a new challenger responding
according to 2.

Figure 11. State Commitment challenge

The game ends when the conflict is resolved down to one transaction and that
transaction is posted on the SMR. We note that the number of rounds is
$\Theta(\log B)$.

Note that any node can be a challenger to exactly one shard of its choice in a
round, by doing so, it elects itself to the challenge committee of that shard,
however it is free to join any other shard’s challenge committee in the next
round. The dynamic challenge committee makes the challenge protocol robust to
an adaptive adversary and we can claim that the state commitment protocol
satisfies validity and liveness:

  * •

Validity: A state commitment corresponds to a valid state if every challenge
committee has at least one honest node, which will not be violated w.h.p.
since $\gamma_{i}\geq q/(1+2q)K$ (the expected number of honest nodes is
$Nq/(1+2q)K$ which is $\Omega(\log K)$).

  * •

Liveness: A valid state commitment will be posted in expected constant number
of epochs.

###  4.2.  Data Structures and Resource Consumption

Let us define the overhead ratio as the ratio of (resource used to maintain
the SMR) to (resource used to maintain any one shard). We define resource
usage as a 3-dimensional vector: (1) Computation (2) Communication and (3)
Storage. We will compute the overhead as the maximum value of the
$3$-dimensions. Here, we account for resources consumed by all data structures
involved in maintaining the total ordered log; this is discussed in detail
next.

Total ordered log: The ordered log is maintained by the SMR and consists of
the following entries:

  * •

Shard block pointers: Consists of the tuple (hash of the shard block, shard-
id, mining proof). $K$ such shard block pointers are appended to the log for
every shard block and each pointer is of size $\log K$. Resource usage =
$O(K\log K)$.

  * •

Shard State commitments: There are $O(K)$ state commitments per epoch. We set
the epoch duration $E$ such that in expectation, there is one shard block per
epoch. Resource usage = $O(K)$.

  * •

State commitment challenge interactions: Consists of challenges and replies
from epoch leaders. There are $O(N)$ challenges in total which accounts for
$R=O(\log B)$ interactions. Resource usage = $O(N\log B)$.

  * •

Data availability votes: Signed (Availability, shard block hash). Constant
size posted for $K$ shard blocks and needs $O(N)$ votes per shard block.
Resource usage = $O(NK)$.

  * •

Data availability fraud proofs: Incorrect coding proofs of size $O(\log B)$
for at most $K$ shards. Resource usage = $O(K\log B)$.

Shard rotation: A node rotating to a new shard needs to synchronize to the
state of the new shard. The synchronization involves downloading the state
corresponding to the latest state commitment and processing shard blocks
proposed after the latest state commitment. The resource cost is $O(1+B)$ per
new allocation. We set the rotation interval every $T_{r}$ blocks for the
Free2Shard DSA policy. A node also needs to synchronize to another shard if it
is chosen as its leader. The epoch leader election will elect a node with
probability $O(K/N)$ per epoch. We set $T_{r}=K$ to get the resource usage as
$O(B/K+BK/N)$.

Data availability requests: A newly mined block receives requests for $O(N)$
random chunks for the base CMT symbol of size $O(B/N)$, resource usage =
$O(B\log N)$ per shard. Since each shard has $O(N/K)$ nodes, the load can be
distributed equally amongst all nodes, resource usage per node =
$O(\frac{BK}{N}\log N)$. Each node receives $K$ chunks of size
$O(\frac{B}{N}\log N)$. Resource usage = $O(\frac{KB}{N}\log N)$.

Total resource usage

The total resource usage per shard block is given by $O(K\log K+N\log
B+NK+B/K+BK/N)$ in all 3 resource dimensions, Thus Overhead-ratio =
$O\left(\frac{K\log K}{B}+\frac{N\log B}{B}+\frac{NK}{B}+\frac{K\log
N}{N}\right)$ $=o(1)$, as $B$ becomes large and $N>\Omega(K\log K)$. Note that
we require $N>\Omega(K\log K)$ to ensure that our DSA algorithm throughput
approaches $\gamma$; this requirement is also essential to guarantee the
safety of state commitment.

###  4.3. Summary

The building blocks and their interactions and the resources consumed therein
allow us to infer the following properties of Free2Shard.

  1. (1)

Safety of the shard ledger directly follows from the safety of the total
ordered log, maintained by the SMR engine. In this manner, the core safety
property (under adaptive adversaries, cf. Section 2.5) of the SMR engine is
extended to Free2Shard.

  2. (2)

Liveness. The DSA engine, along with the shard block mining mechanism,
guarantees that at least $\gamma$ fraction of blocks are honest in each shard
over a long enough timescale (Theorem 3.3). The random dynamic rotation
ensures new honest blocks are produced in each shard to maintain a consistent
$\gamma$ fraction of honest blocks; this ensures liveness under adaptive
adversaries.

  3. (3)

Scaling. As discussed above, the overhead ratio can be made arbitrarily small
by making $B$ large. The average time interval between consecutive shard
blocks in a shard can increased to ensure that the shard processes $O(R)$
honest transactions per second.

##  5\. Free2Shard system view

We conclude the paper by discussing a variety of practical and real-world
system issues in implementing Free2Shard (and sharding protocols in general)
in distributed permissionless blockchains.

Heterogeneous shard throughputs. While most sharding protocols focus on
allocating equal resources to all shards, in practice different shards will
have different throughput requirements. The Free2Shard architecture is unique
in being able to handle arbitrary throughput requirements for different
shards. In particular, consider the extreme example where the number of shards
is much larger than the number of active nodes ($N\ll K$). Existing protocols
cannot operate in this regime, even though most of the shards are at low
levels of activity and throughput. As we showed in Sec 3.5, the DSA algorithm
can achieve optimal performance even in this regime.

Heterogeneous resources. In practice, different nodes will have different
amount of computation resources. Particularly in permissionless deployments,
for example, in proof-of-stake, the amount of stake held by a node need not
match the amount of computation power held by the node. In typical sharding
protocols with a N2S allocation, the nodes are allocated proportional to the
stake and not to their computation power. However in Free2Shard if a node has
high computation power, it can participate in multiple shards and contribute
state commitments as well as challenges in different shards.

Asynchronous rotation. We have assumed that the honest nodes rotate at every
round $t$; however, this may not be feasible in a realistic setting. We now
argue that our results hold if honest nodes rotate only once every $\Delta$
rounds. Let $\gamma_{i}(t)$ = $\gamma_{i}[n]\;\forall
t\in\\{(n-1)\Delta+1,..,n\Delta\\}$ and
$\beta_{i}[n]=\sum_{t=(n-1)\Delta+1}^{n\Delta}\frac{1}{\Delta}\beta_{i}(t)$ We
observe that $\frac{\gamma_{i}(t)}{\gamma_{i}(t)+\beta_{i}(t)}$ is convex in
$\beta_{i}(t)$, thus, the time-average of a given round is lower bounded as
follows:

(22)
$\displaystyle\sum_{t=(n-1)\Delta+1}^{n\Delta}\frac{\gamma_{i}[n]}{\gamma_{i}[n]+\beta_{i}(t)}$
$\displaystyle\geq\sum_{t=(n-1)\Delta+1}^{n\Delta}\frac{\gamma_{i}[n]}{\gamma_{i}[n]+\beta_{i}[n]}.$

Thus, the optimal adversarial strategy is to modify $\boldsymbol{\beta}$ at
the same rate as $\boldsymbol{\gamma}$; this shows that the previous results
transalte to slower rotation dynamics as well. Moreover, the results hold when
nodes randomize their rotation choice (choosing to rotate with probability
$\frac{1}{\Delta}$). This makes for a distributed implementation and has the
added benefit that asynchronous rotation alleviates network load by preventing
focused communication load at the same time.

A small minority can stabilize the entire protocol. Not all honest nodes need
to follow Free2Shard-dist policy: Theorem 3.3 remains true even if a small
(but constant) fraction of the honest nodes follow the policy. For example,
the Free2Shard-dist policy allows us to set $\gamma=0.1$. We note that this is
a very valuable practical setting, since many blockchains have their own
foundations that own sub-majority stake. In contrast to existing protocols,
even a small minority following the rotation policy can stabilize the
throughput of all shards in Free2Shard.

Inter-shard transactions: While we previously only discussed intra-shard
transactions, a large class of applications require inter-shard support. State
commitments can be used to facilitate inter-shard transactions. Since a state
commitment satisfies validity and liveness, we can directly use existing
inter-shard transaction protocols like Atomix (Kokoris-Kogias et al., 2018). A
recent work (Sonnino et al., 2019) reported that these existing protocols are
susceptible to fatal synchronization attacks and message replay attacks, we
note that Free2Shard is not susceptible to these attacks due to global
ordering. Inter-shard transactions using this method require a latency larger
than shard-commitment duration. However, since there is a global ordering of
transactions, computationally powerful nodes can maintain a view of multiple
shard chains and certify an inter-shard transaction for a fast inter-shard
swap (earning some rewards on the way).

Incentives. Rational nodes are incentivized to follow the DSA policy since the
transaction fees on shards with lower than desired throughput will be higher
due to a high supply-demand gap. Moreover, state commitment and data
availability fraud proofs can require deposits that can be snatched under
clearly provable malicious behavior. Thus nodes will be incentivized further
to follow the protocol.

Permissionless setting. An obvious extension of Free2Shard is to
permissionless proof-of-stake (PoS) systems. Here all that really needs to be
done is to replace the underlying SMR with a proof-of-stake system like
Algorand (Gilad et al., 2017) rather than a permissioned system. Finally, we
consider the adaptation of Free2Shard to proof-of-work (PoW). A natural
approach is to elect a committee of PoW mining participants from within the
part of the blockchain that has reached consensus and this committee serves as
the participants of the permissioned Free2Shard architecture. One way to
achieve this is via the hybrid consensus approach (Pass and Shi, 2017b): the
committee consists of a set of successive miners that are deep enough in the
longest chain. However, this approach is not safe against an adaptive
adversary - who can clearly bribe the set of chosen miners. A problem with
simply applying Free2Shard to this setting is the issue that miners may
arbitrarily decide to attack a given shard. We can solve this problem here by
using a hash-sortition between the SMR engine and the shard block mining
process - this idea is adapted from (Bagaria et al., 2019) and was originally
used in (Garay et al., 2015; Pass and Shi, 2017a). The key properties of
Free2Shard all translate to this setting as well.

## References

  * (1)
  * Abraham et al. (2019a) Ittai Abraham, TH Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2019a.  Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 317–326.
  * Abraham et al. (2019b) Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. 2019b.  Sync hotstuff: Simple and practical synchronous state machine replication.  IACR Cryptology ePrint Archive 2019 (2019), 270.
  * Al-Bassam (2019) Mustafa Al-Bassam. 2019\.  LazyLedger: A Distributed Data Availability Ledger With Client-Side Smart Contracts.  (2019).  arXiv:cs.CR/1905.09274
  * Al-Bassam et al. (2018) Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin. 2018\.  Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities.  arXiv preprint arXiv:1809.09044 (2018).
  * Arora et al. (2012) Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012\.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of Computing 8, 1 (2012), 121–164.
  * Bagaria et al. (2019) Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. 2019.  Prism: Deconstructing the blockchain to approach physical limits.  ACM Computer and Communications Security Conference (2019).
  * Balakrishnan et al. (2012) Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobbler, Michael Wei, and John D Davis. 2012.  CORFU: A Shared Log Design for Flash Clusters. In Presented as part of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). 1–14.
  * Balakrishnan et al. (2013) Mahesh Balakrishnan, Dahlia Malkhi, Ted Wobber, Ming Wu, Vijayan Prabhakaran, Michael Wei, John D Davis, Sriram Rao, Tao Zou, and Aviad Zuck. 2013.  Tango: Distributed data structures over a shared log. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. 325–340.
  * Ben-Sasson et al. (2018) Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018.  Scalable, transparent, and post-quantum secure computational integrity.  IACR Cryptology ePrint Archive 2018 (2018), 46.
  * Ben-Sasson et al. (2014) Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014.  Succinct non-interactive zero knowledge for a von Neumann architecture. In 23rd USENIX Security Symposium (USENIX Security 14). 781–796.
  * Bessani et al. (2014) Alysson Bessani, João Sousa, and Eduardo EP Alchieri. 2014\.  State machine replication for the masses with BFT-SMaRt. In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. IEEE, 355–362.
  * Blackwell et al. (1956) David Blackwell et al. 1956\.  An analog of the minimax theorem for vector payoffs.  Pacific J. Math. 6, 1 (1956), 1–8.
  * Bünz et al. (2018) Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. 2018.  Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 315–334.
  * Castro et al. (1999) Miguel Castro, Barbara Liskov, et al. 1999\.  Practical Byzantine fault tolerance. In OSDI, Vol. 99. 173–186.
  * Chan and Shi (2020) Benjamin Y Chan and Elaine Shi. 2020.  Streamlet: Textbook Streamlined Blockchains.  Technical Report. Cryptology ePrint Archive, Report 2020/088. https://eprint. iacr. org/2020/088.
  * Dodis and Yampolskiy (2005) Yevgeniy Dodis and Aleksandr Yampolskiy. 2005.  A verifiable random function with short proofs and keys. In International Workshop on Public Key Cryptography. Springer, 416–431.
  * Dolev and Strong (1983) Danny Dolev and H. Raymond Strong. 1983.  Authenticated algorithms for Byzantine agreement.  SIAM J. Comput. 12, 4 (1983), 656–666.
  * Dwork et al. (1988) Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988\.  Consensus in the presence of partial synchrony.  Journal of the ACM (JACM) 35, 2 (1988), 288–323.
  * Garay et al. (2015) Juan Garay, Aggelos Kiayias, and Nikos Leonardos. 2015\.  The bitcoin backbone protocol: Analysis and applications. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer.
  * Gencer et al. (2017) Adem Efe Gencer, Robbert van Renesse, and Emin Gün Sirer. 2017\.  Short paper: Service-oriented sharding for blockchains. In International Conference on Financial Cryptography and Data Security. Springer, 393–401.
  * Gilad et al. (2017) Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017.  Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles. ACM.
  * Jedusor (2016) Tom Elvis Jedusor. 2016\.  Mimblewimble.  (2016).
  * Kalodner et al. (2018) Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S Matthew Weinberg, and Edward W Felten. 2018\.  Arbitrum: Scalable, private smart contracts. In 27th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 18). 1353–1370.
  * 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. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 583–598.
  * Li et al. (2019) Songze Li, Saeid Sahraei, Mingchao Yu, Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath. 2019\.  Coded State Machine–Scaling State Machine Execution under Byzantine Faults. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 150–152.
  * Li et al. (2018) Songze Li, Mingchao Yu, Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath. 2018.  Polyshard: Coded sharding achieves linearly scaling efficiency and security simultaneously.  arXiv preprint arXiv:1809.10361 (2018).
  * Luu et al. (2016) Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. 2016\.  A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 17–30.
  * Luu and Rush (2017) Loi Luu and Nate Rush. 2017\.  PeaceRelay Merkle-Patricia Trie Proof Verification.  (2017).
  * Micali et al. (1999) Silvio Micali, Michael Rabin, and Salil Vadhan. 1999\.  Verifiable random functions. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039). IEEE, 120–130.
  * Nakamoto (2008) Satoshi Nakamoto. 2008\.  Bitcoin: A peer-to-peer electronic cash system.  (2008).
  * Parno et al. (2013) Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. 2013\.  Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy. IEEE, 238–252.
  * Pass and Shi (2017a) R. Pass and E. Shi. 2017a.  Fruitchains: A fair blockchain. In Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM.
  * Pass and Shi (2017b) Rafael Pass and Elaine Shi. 2017b.  Hybrid consensus: Efficient consensus in the permissionless model. In LIPIcs-Leibniz International Proceedings in Informatics. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * Research (2020) Ethereum Research. 2020\.  Ethereum 2.0.  https://github.com/ethereum/eth2.0-specs. (2020).
  * Sonnino et al. (2019) Alberto Sonnino, Shehar Bano, Mustafa Al-Bassam, and George Danezis. 2019.  Replay Attacks and Defenses Against Cross-shard Consensus in Sharded Distributed Ledgers.  arXiv preprint arXiv:1901.11218 (2019).
  * Telegraph (2019) Coin Telegraph. 2019\.  10,000 Nodes Are Running BTC Lightning Network in New All-Time High.  https://cointelegraph.com/news/10-000-nodes-are-running-btc-lightning-network-in-new-all-time-high. (2019).
  * Teutsch and Reitwießner (2019) Jason Teutsch and Christian Reitwießner. 2019\.  A scalable verification solution for blockchains.  arXiv preprint arXiv:1908.04756 (2019).
  * Von Neumann (1953) John Von Neumann. 1953\.  A certain zero-sum two-person game equivalent to the optimal assignment problem.  Contributions to the Theory of Games 2, 0 (1953), 5–12.
  * von Stackelberg (2011) Heinrich von Stackelberg. 2011\.  Market Structure and Equilibrium.  Springer.
  * Wood (2016) Gavin Wood. 2016\.  Polkadot: Vision for a heterogeneous multi-chain framework.  (2016).
  * Yin et al. (2003) Jian Yin, Jean-Philippe Martin, Arun Venkataramani, Lorenzo Alvisi, and Mike Dahlin. 2003\.  Separating agreement from execution for byzantine fault tolerant services. In Proceedings of the nineteenth ACM symposium on Operating systems principles. 253–267.
  * Yin et al. (2019) Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019\.  Hotstuff: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 347–356.
  * Yu et al. (2019) Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath. 2019\.  Coded Merkle Tree: Solving Data Availability Attacks in Blockchains.  Cryptology ePrint Archive, Report 2019/1139. (2019).  https://eprint.iacr.org/2019/1139.
  * Zamani et al. (2018) Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018\.  Rapidchain: Scaling blockchain via full sharding. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. ACM.
  * Zilliqa (2017) Zilliqa. 2017.  The ZILLIQA Technical Whitepaper.  https://docs.zilliqa.com/whitepaper.pdf. (2017).

##  Appendix A Proofs

###  A.1. Proof of Proposition 7

Proof:  Lower bound:
Let $a_{t}:=\beta_{1}(t)$,
$b_{t}=\frac{\gamma}{2\beta}a_{t}+\frac{\gamma}{2K}$, $l=\frac{\gamma}{2K}$,
$u=\frac{\gamma}{2}+\frac{\gamma}{2K},\omega=\frac{2\beta}{\gamma}$. We have
$\frac{\gamma}{2K}\leq b_{t}\leq\frac{\gamma}{2}+\frac{\gamma}{2K}$.

$\displaystyle\psi(K)$ $\displaystyle=\min_{\\{\frac{\gamma}{2K}\leq
b_{t}\leq\frac{\gamma}{2}+\frac{\gamma}{2K}\\}}\quad\left\\{\frac{1}{T}\sum_{t=1}^{T}\frac{b_{t-1}}{b_{t-1}+(\frac{2\beta}{\gamma}b_{t}-\frac{\beta}{K})}\right\\}$
(23) $\displaystyle\geq\min_{\\{\frac{\gamma}{2K}\leq
b_{t}\leq\frac{\gamma}{2}+\frac{\gamma}{2K}\\}}\quad\left\\{\frac{1}{T}\sum_{t=1}^{T}\frac{b_{t-1}}{b_{t-1}+\frac{2\beta}{\gamma}b_{t}}\right\\}=:\phi(K)$
(24) $\displaystyle\phi(K)$ $\displaystyle=\min_{\\{l\leq b_{t}\leq
u\\}}\quad\left\\{\frac{1}{T}\sum_{t=1}^{T}\frac{b_{t-1}}{b_{t-1}+\omega
b_{t}}\right\\}$

Now, we call a time-instant $t$ $g$-good if the throughput at that time is
greater than $g$. We will show that the adversary does not have the ability to
have a consecutive run of $g$-bad instances for more than $\tau$-periods.
Suppose an instant $t$ is not $g$-good. Then

$\displaystyle\frac{b_{t-1}}{b_{t-1}+\omega b_{t}}\leq g$

which implies ${b_{t}}\geq b_{t-1}r$ where $r=\frac{1-g}{\omega g}$. Note
$g\leq\frac{1}{1+\omega}$ implies $r\geq 1$. Suppose there are $\tau$
consecutive $g$-good instances at time $t$. Then ${b_{t}}\geq
b_{t-\tau}r^{\tau}$. Given $b_{t}\leq u$ and $b_{t-{\tau}}\geq l$, we have
$u\geq lr^{\tau}$. This implies $tau\leq\log_{r}\left(\frac{u}{l}\right)$.
Thus there is a $g$-good instant every $\tau+1$ instances. This implies that
the throughput is at least $\frac{g}{\tau+1}$.

$\displaystyle\phi(K)\geq\frac{g\log
r}{\log\left(\frac{ur}{l}\right)}\geq\frac{g\log\left(\frac{1-g}{\omega
g}\right)}{\log\left(r\frac{\frac{\gamma}{2}+\frac{\gamma}{2K}}{\frac{\gamma}{2K}}\right)}.$

Consider a worst case scenario where $\beta=0.5$, $\gamma=0.5$, for all
$g\leq\frac{1}{1+\omega}=1/3$, choosing $g=1/4$, and $1/2+1/2K\leq 1$, we get:

(25) $\phi(K)\geq\frac{0.14}{\log_{2}(3K)}.$

Upper Bound: We demonstrate an adversarial strategy which holds to the
following claim: $\psi(K)\leq O(\frac{\log\log K}{\log K})$. Compare the
denominators of $\psi(K)$ and $\phi(K)$:

$\displaystyle{\frac{\gamma}{6\beta}a_{t-1}+\frac{\gamma}{6K}+\frac{\gamma
a_{t}}{3\beta}+\frac{\gamma}{3K}}$
$\displaystyle\leq{\\{\frac{\gamma}{2\beta}a_{t-1}+\frac{\gamma}{2K}\\}+a_{t}}$
$\displaystyle\leq{\\{\frac{\gamma}{2\beta}a_{t-1}+\frac{\gamma}{2K}\\}+a_{t}+\frac{\gamma}{K}}$

We Observe $\phi(K)\leq\psi(K)\leq 3\phi(K)$ and hence can rewrite our claim
as : $\phi(K)\leq O(\frac{\log\log K}{\log K})$.

We show an adversarial sequence to establish the upper bound.

Let the sequence $b_{t}$ be $\ell,\ell r,..,\ell{r^{\tau}},0,\ell,\ell
r,..,\ell{r^{\tau}}$. We will calculate $\phi(K)$ based on a single period.
Recall $\ell=\frac{\gamma}{2K}$, $u=\frac{\gamma}{2}+\frac{\gamma}{2K}$. Note
$lr^{\tau}=u$, so $\tau=\log_{r}(\frac{u}{l})$.

$\displaystyle\phi(K)\leq\frac{\tau}{\tau+1}\frac{1}{1+2r}+\frac{1}{\tau+1}$
$\displaystyle=\frac{\tau}{\tau+1}\frac{1}{1+2r}+\frac{1}{\tau+1}\left[\frac{1}{1+2r}+\frac{2r}{1+2r}\right]$
$\displaystyle=\frac{1}{1+2r}+\frac{2r}{2r+1}\frac{1}{\tau+1}$
$\displaystyle=\frac{1}{1+2r}+\frac{2r}{2r+1}\cdot\frac{\log r}{\log(cr)}$

where $c=\frac{u}{l}={K+1}$. Choosing $r=\log K$, we get

$\displaystyle\phi(K)\leq\frac{1}{1+2\log K}+\frac{2\log K}{2\log
K+1}\cdot\frac{\log\log K}{\log(K+1)}$ (26)
$\displaystyle=O\left(\frac{\log\log K}{\log K}\right)$

###  A.2. Proof of Theorem 3.3

####  A.2.1. Strategy space inequality

Let us define $f(\mathbf{\gamma})$ as follows:

$\displaystyle
f(\mathbf{\gamma})=\min_{\mathbf{\beta}}\sum_{i=1}^{K}u_{i}\frac{\gamma_{i}}{\gamma_{i}+\beta_{i}}$

We now show that $f(\mathbf{\gamma})=(\sum_{j}\sqrt{u_{j}\gamma_{j}})^{2}$,
using constrained Lagrange optimization.

$\displaystyle f(\mathbf{\gamma})$
$\displaystyle=\min_{\mathbf{\beta}}\sum_{i=1}^{K}u_{i}\frac{\gamma_{i}}{\gamma_{i}+\beta_{i}}\,s.t.\sum_{i=1}^{K}\beta_{i}=\beta$
$\displaystyle obj$
$\displaystyle=\sum_{i}u_{i}\frac{\gamma_{i}}{\gamma_{i}+\beta_{i}}+\lambda(\sum_{i=1}^{K}\beta_{i}-\beta)$
$\displaystyle\frac{\partial obj}{\partial\beta_{i}}$
$\displaystyle=\frac{-u_{i}\gamma_{i}}{(\gamma_{i}+\beta_{i})^{2}}+\lambda=0$
$\displaystyle\gamma_{i}+\beta_{i}=\frac{\sqrt{u_{i}\gamma_{i}}}{\sqrt{\lambda}}\,$
$\displaystyle\text{and}\,\sqrt{\lambda}=\sum_{i=1}^{K}\sqrt{u_{i}\gamma_{i}}$

substituting the value of $\lambda$ in $f(\mathbf{\gamma})$, we get:

$\displaystyle f(\mathbf{\gamma})$
$\displaystyle=\sum_{i=1}^{K}(\sqrt{u_{i}\gamma_{i}}\sum_{i=1}^{K}\sqrt{u_{i}\gamma_{i}})=(\sum_{i=1}^{K}\sqrt{u_{i}\gamma_{i}})^{2}$

Let $\boldsymbol{v}$ denote a sorted list of $\boldsymbol{u}$ sorted in a
descending order and $pos(u_{i})$ denote the position of $u_{i}$ in
$\boldsymbol{v}$ with $pos(\max u_{i})=1$.

We define $\tilde{u_{i}}$ as follows:

$\tilde{u}_{i}=\begin{cases}u_{i},&\text{if }pos(u_{i})\leq s\\\
0,&\text{otherwise}\end{cases}$

substituting
$\gamma_{i}=\gamma\frac{\tilde{u}_{i}}{\sum_{i=1}^{K}\tilde{u}_{i}}$, we get:

$\displaystyle
f(\mathbf{\gamma})=\frac{\gamma}{\sum_{i=1}^{K}\tilde{u}_{i}}(\sum_{i=1}^{K}\tilde{u}_{i})^{2}$
$\displaystyle=\gamma\sum_{i=1}^{K}\tilde{u}_{i}\geq\gamma\frac{s}{K}\sum_{i=1}^{K}u_{i}$
(27)
$\displaystyle\max_{\mathbf{\gamma}}\min_{\mathbf{\beta}}\sum_{i=1}^{K}u_{i}\frac{\gamma_{i}}{\gamma_{i}+\beta_{i}}$
$\displaystyle\geq f(\mathbf{\gamma})\geq\gamma\frac{s}{K}\sum_{i=1}^{K}u_{i}$

####  A.2.2. Modified strategy space inequality

Let us now modify the policy $\boldsymbol{\gamma}$ to ensure that
$\gamma_{i}\geq\frac{b}{s}if\tilde{\gamma}_{i}>0$. Let
$\tilde{\gamma_{i}}=\gamma\frac{\tilde{u}_{i}}{\sum_{i=1}^{K}\tilde{u}_{i}}$,
we have
$f(\boldsymbol{\tilde{\gamma}})\geq\frac{s}{K}\gamma\sum_{i=1}^{K}u_{i}$ let
us define $\boldsymbol{\gamma}$ as follows:

$\displaystyle\boldsymbol{\gamma}=\frac{1}{1+q/\gamma}Proj(C_{q/s},\boldsymbol{\tilde{\gamma}}),$

where $Proj(C_{q/s},\cdot)$ is a projection of the $s$ non-zero values of
$\tilde{\gamma}_{i}$to the set $C_{q/s}=[q/s,1]^{s}$, the projection will
cause at most $s$ values to grow by $\frac{q}{s}$. Thus, we normalize all
values by $1+q/\gamma$. We need to ensure that
$\gamma_{i}\geq\frac{b}{s}\forall i\in[K]$, hence we get the inequality:

$\displaystyle\frac{q/s}{1+q/\gamma}\geq\frac{q/s}{1+2q}$
$\displaystyle\geq\frac{b}{s}\Rightarrow q\geq\frac{b}{1-2b}$

we set $q=\frac{b}{1-2b}$, our modified $\boldsymbol{\gamma}$ now satisfies
$\gamma_{i}\geq b/s$.

We now have the following inequality

$\displaystyle f(\boldsymbol{\gamma})$
$\displaystyle\geq\frac{1}{1+q/\gamma}f(\boldsymbol{\tilde{\gamma}})\geq(1-2b)f(\boldsymbol{\tilde{\gamma}})$
$\displaystyle\min_{\boldsymbol{\beta}}\sum_{i}u_{i}\frac{\gamma_{i}}{\gamma_{i}+\beta_{i}}$
$\displaystyle\geq\frac{s}{K}\gamma(1-2b)\sum_{i=1}^{K}u_{i}$

####  A.2.3. Stochastic strategy space inequality

We define the event $E_{i}(t):\Gamma_{i}(t)\geq cN\gamma_{i}(t)$, and
$\boldsymbol{E(t)}:\bigcap_{i=1}^{K}E_{i}(t)$

Let us compute the tail bound on $\Gamma_{i}(t)$ using the divergence bound on
binomial distributions, we get

$\displaystyle P(\Gamma_{i}(t)$ $\displaystyle\leq cN\gamma_{i}(t))\leq
e^{-nD(c\frac{\gamma_{i}(t)}{\gamma}||\frac{\gamma_{i}(t)}{\gamma})}$
$\displaystyle D(c\frac{\gamma_{i}(t)}{\gamma}||\frac{\gamma_{i}(t)}{\gamma})$
$\displaystyle=c\frac{\gamma_{i}(t)}{\gamma}\log(c)+(1-c\frac{\gamma_{i}(t)}{\gamma})\log(\frac{1-c\frac{\gamma_{i}(t)}{\gamma}}{1-\frac{\gamma_{i}(t)}{\gamma}})$
$\displaystyle\geq(-c+c\log c+1)\frac{\gamma_{i}(t)}{\gamma}$
$\displaystyle\geq(-c+c\log c+1)\gamma_{i}(t)$ $\displaystyle\geq(-c+c\log
c+1)\frac{b}{K}$ (28) $\displaystyle P(\Gamma_{i}(t)$ $\displaystyle\leq
cN\gamma_{i}(t))\leq e^{-n\frac{b}{K}(-c+c\log c+1)}.$

We use the divergence bounds derived above to lower bound the event
probability

(29) $\displaystyle P(\boldsymbol{E(t)})$
$\displaystyle=1-P(\boldsymbol{E(t)}^{c})\geq 1-\sum_{i=1}^{K}P(E_{i}(t)^{c})$
(30) $\displaystyle\geq 1-se^{-n\frac{b}{s}(-c+c\log c+1)}$

where equation 29 uses a union bound amd the fact that $P(E_{i}(t)^{c})=0$ for
$K-s$ shards which have $\gamma_{i}=0$ and equation 30 is derived from
equation 28.

$\displaystyle\mathbb{E}_{\boldsymbol{\Gamma(t)}}$
$\displaystyle\left[\min_{\boldsymbol{\beta(t)}}\sum_{i}u_{i}(t-1)\frac{\Gamma_{i}(t)}{\Gamma_{i}(t)+N\beta_{i}(t)}\right]$
$\displaystyle\geq
P(\boldsymbol{E(t)})\min_{\boldsymbol{\beta(t)},\boldsymbol{E(t)}}\sum_{i}u_{i}(t-1)\frac{\Gamma_{i}(t)}{\Gamma_{i}(t)+N\beta_{i}(t)}$
$\displaystyle\geq
P(\boldsymbol{E(t)})(\sum_{i=1}^{K}\sqrt{u_{i}c\gamma_{i}})^{2}$
$\displaystyle\geq P(\boldsymbol{E(t)})c(1-2b)\gamma\sum_{i=1}^{K}u_{i}$
$\displaystyle\geq(1-se^{-n\frac{b}{s}(-c+c\log
c+1)})c(1-2b)\gamma\sum_{i=1}^{K}\tilde{u}_{i}$
$\displaystyle\geq(1-se^{-n\frac{b}{s}(-c+c\log
c+1)})c(1-2b)\frac{s}{K}\gamma\sum_{i=1}^{K}u_{i}$
$\displaystyle\mathbb{E}_{\boldsymbol{\Gamma(t)}}$
$\displaystyle\left[\min_{\boldsymbol{\beta(t)}}\boldsymbol{u(t-1)}.\boldsymbol{r(t)}\right]\geq
h\sum_{i=1}^{K}u_{i}$

We want to lower bound $(1-se^{-n\frac{b}{s}(-c+c\log c+1)})\geq 1-\epsilon$,
thus we need

$\displaystyle se^{-n\frac{b}{s}(-c+c\log c+1)}$
$\displaystyle\leq\epsilon\Rightarrow
n\geq\frac{s\log(\frac{s}{\epsilon})}{b(-c+c\log c+1)}$ (31) $\displaystyle N$
$\displaystyle\geq\frac{s\log(\frac{s}{\epsilon})}{\gamma b(-c+c\log c+1)}$

####  A.2.4. Approach to the convex set

We will now show that $\boldsymbol{\bar{r}(t)}$ approaches $C_{h}$ with
$h=(1-se^{-n\frac{b}{s}(-c+clogc+1)})c(1-2b)\frac{s}{K}\gamma$.

Let $\pi_{C_{h}}(t)$ be the projection of $\boldsymbol{\bar{r}(t)}$ on
$C_{h}$. Let us define a halfspace $\boldsymbol{H}_{t+1}$ formed by the
hyperplane $\boldsymbol{P}_{t+1}$, such that $\boldsymbol{P}_{t+1}$ is normal
to $(\boldsymbol{\bar{r}(t)}-\boldsymbol{\pi_{C_{h}}(t)})$ and passes through
$\pi_{C_{h}}$ and $\boldsymbol{H}_{t+1}$ contains $C_{h}$. The variables
defined above satisfy the following equations:

$\displaystyle\boldsymbol{\pi_{C_{h}}(t)}$
$\displaystyle=arg\min_{\boldsymbol{y}\in
C_{h}}||\boldsymbol{y}-\boldsymbol{\bar{r}}(t)||$
$\displaystyle\pi_{C_{h}}(t)_{i}$
$\displaystyle=hI_{\\{\bar{r_{i}}(t)<h\\}}+\bar{r_{i}}(t)I_{\\{\bar{r_{i}}(t)<h\\}}$
$\displaystyle\boldsymbol{\pi_{C_{h}}(t)}-\mathbf{\bar{r}(t)}$
$\displaystyle=\boldsymbol{u(t)}\quad u_{i}(t)=(h-\bar{r}_{i}(t))$
$\displaystyle\boldsymbol{P}_{t+1}(\boldsymbol{x})$
$\displaystyle:\sum_{i=1}^{K}(h-\bar{r_{i}}(t))_{+}x_{i}-h\sum_{i=1}^{K}(h-\bar{r_{i}}(t))_{+}=0$
$\displaystyle\mbox{such that }\quad\boldsymbol{u\cdot
x}-h\sum_{i=1}^{K}u_{i}=0$ $\displaystyle\boldsymbol{H}_{t+1}(\boldsymbol{x})$
$\displaystyle:\sum_{i=1}^{K}(h-\bar{r_{i}}(t))_{+}x_{i}-h\sum_{i=1}^{K}(h-\bar{r_{i}}(t))_{+}\geq
0$ $\displaystyle\mbox{such that }\quad\boldsymbol{u\cdot
x}-h\sum_{i=1}^{K}u_{i}\geq 0$

Let us define $d_{t}$ as the distance of $\boldsymbol{\bar{r}}(t)$ from the
convex set $C_{h}$, i.e.
$d_{t}=||\boldsymbol{\bar{r}}(t)-\boldsymbol{\pi}_{C_{h}}(t)||$ ,
$d(\boldsymbol{a,b})=||\boldsymbol{a}-\boldsymbol{b}||$ for any
$\boldsymbol{a},\boldsymbol{b}\in\mathbf{R}^{K}$.

$\displaystyle d^{2}_{t+1}$
$\displaystyle=d^{2}(\mathbf{\bar{r}(t+1)},\boldsymbol{\pi_{C_{h}}(t+1)})\leq
d^{2}(\mathbf{\bar{r}(t+1)},\boldsymbol{\pi_{C_{h}}(t)})$
$\displaystyle=\left\lVert\mathbf{\bar{r}(t+1)}-\boldsymbol{\pi_{C_{h}}(t)}\right\rVert^{2}_{2}$
$\displaystyle=\left\lVert\frac{t}{t+1}\mathbf{\bar{r}(t)}+\frac{1}{t+1}\mathbf{r(t+1)}-\boldsymbol{\pi_{C_{h}}(t)}\right\rVert^{2}_{2}$
$\displaystyle=\left\lVert\frac{t}{t+1}(\mathbf{\bar{r}(t)}-\boldsymbol{\pi_{C_{h}}(t)})+\frac{1}{t+1}(\mathbf{r(t+1)}-\boldsymbol{\pi_{C_{h}}(t)})\right\rVert^{2}_{2}$
$\displaystyle=(\frac{t}{t+1})^{2}\left\lVert\mathbf{\bar{r}(t)}-\boldsymbol{\pi_{C_{h}}(t)}\right\rVert^{2}_{2}+(\frac{1}{t+1})^{2}\left\lVert\mathbf{r(t+1)}-\boldsymbol{\pi_{C_{h}}(t)}\right\rVert^{2}_{2}$
$\displaystyle+\frac{2t}{(t+1)^{2}}(\mathbf{\bar{r}(t)}-\boldsymbol{\pi_{C_{h}}(t)}).(\mathbf{r(t+1)}-\boldsymbol{\pi_{C_{h}}(t)})$

$\displaystyle(t+1)^{2}d^{2}_{t+1}-t_{2}d^{2}_{t}$
$\displaystyle\leq\left\lVert\mathbf{r(t+1)}-\boldsymbol{\pi_{C_{h}}(t)}\right\rVert^{2}_{2}$
$\displaystyle+2t*((\boldsymbol{\pi_{C_{h}}(t)}-\mathbf{\bar{r}(t)}).(\boldsymbol{\pi_{C_{h}}(t)}-\mathbf{r(t+1)}))$

we know the following equations:

$\displaystyle\left\lVert\mathbf{r(t+1)}-\boldsymbol{\pi_{C_{h}}(t)}\right\rVert^{2}_{2}$
$\displaystyle\leq h^{2}K$
$\displaystyle(\boldsymbol{\pi_{C_{h}}(t)}-\mathbf{\bar{r}(t)}).\boldsymbol{\pi_{C_{h}}(t)})$
$\displaystyle=h\sum_{i=1}^{K}u_{i}$
$\displaystyle(\boldsymbol{\pi_{C_{h}}(t)}-\mathbf{\bar{r}(t)}).\boldsymbol{\pi_{C_{h}}(t)})$
$\displaystyle\leq\mathbb{E}_{\Gamma_{i}(t+1)}\left[\sum_{i}u_{i}(t)r_{i}(t+1)\right]$

Summing terms for $t\in[T]$, we get

$\displaystyle d^{2}_{T}$ $\displaystyle\leq
h^{2}\frac{K}{T}+\frac{2}{T}\sum_{t=1}^{T-1}\frac{t}{T}(\mathbb{E}_{\Gamma_{i}(t)}\left[\sum_{i}u_{i}(t-1)r_{i}(t)\right]-(\boldsymbol{u(t-1)}).\mathbf{r(t)})$

The term
$Y_{t}=(\mathbb{E}_{\Gamma_{i}(t)}\left[\sum_{i}u_{i}(t-1)r_{i}(t)\right]-((\boldsymbol{u(t-1)}).\mathbf{r(t)})$
is a martingale difference sequence w.r.t. history at time $t$ and
$|Y_{t}|\leq 2hs$

Given $\epsilon_{m}>0$, by the Azuma- Hoeffding inequality we have:

$\displaystyle\mathbb{P}\left(\frac{1}{T}\left\lVert\sum_{t=1}^{T-1}Y_{t}\right\rVert>\epsilon_{m}\right)\leq
2e^{-\frac{T\epsilon_{m}^{2}}{8h^{2}s^{2}}}$

Let us set $\epsilon_{m}=2hs\sqrt{\frac{2}{T}\log(\frac{2}{\delta})}$, we get

$\displaystyle\mathbb{P}\left(\frac{1}{T}\left\lVert\sum_{t=1}^{T-1}Y_{t}\right\rVert>\epsilon_{m}\right)\leq\delta$

Thus with a high probability of $1-\delta$, we have distance to the convex set
reducing as:

$\displaystyle d^{2}_{T}$ $\displaystyle\leq
h^{2}\frac{K}{T}+4hs\sqrt{\frac{2}{T}\log(\frac{2}{\delta})}$

###  A.3. Proof of Proposition 3.4

At $t=1$ the adversary is focused on $\frac{K}{\log K}$ shards, let those
shards form a set $S_{1}$. Let the honest node allocate themselves as
$\boldsymbol{\gamma(2)}$

$\displaystyle\frac{1}{|S_{1}|}\sum_{i\in
S_{1}}\gamma_{i}(2)\leq\frac{1-\beta}{|S_{1}|}$

The median of ${\gamma_{i}(2)}$ is less than twice its mean, thus
$\text{median}\leq\frac{1(1-\beta)(\log K)}{K}$. This implies that the last
$\frac{K}{2\log K}$ shards (arranged in descending order of their honest
fraction) will have honest fraction less than $\frac{1(1-\beta)(\log K)}{K}$.

The adversary now spreads only to $\frac{K}{(\log K)^{2}}$ lowest performing
shards, this set is made up of the subset of the $\frac{K}{2\log K}$ shards
discussed above since $\frac{K}{2\log K}\leq\frac{K}{(\log K)^{2}}$ (for
$K>e^{2}$).

We can again show that the adversary allocates as $\boldsymbol{\gamma(3)}$ and
show that the last $\frac{K}{2^{2}\log K}$ shards (arranged in descending
order of their honest fraction) will have honest fraction less than
$\frac{1(1-\beta)(\log K)}{K}$ and the adversary now spreads only to
$\frac{K}{(\log K)^{3}}$ lowest performing shards, this set is made up of the
subset of the $\frac{K}{2^{2}\log K}$ shards discussed above since
$\frac{K}{2\log K}\leq\frac{K}{(\log K)^{2}}$ (for $K>e^{2}$).

The attack continues till $\frac{K}{(\log K)^{\tau}}=1$, the adversary cannot
concentrate further. Solving the above equation, we get $\tau=\frac{\log
K}{\log\log K}$, completing the proof.

##  Appendix B Other Preliminaries

###  B.1. Verifiable Random Function

Verifiable Random Functions (VRF), first introduced in (Micali et al., 1999),
generates a pseudorandom number with a proof of its correctness. A node with a
secret key $sk$ can call VRFprove$(\cdot,sk)$ to generates a pseudorandom
output $F_{sk}(\cdot)$ along with a proof $\pi_{sk}(\cdot)$. Other nodes that
have the proof and the corresponding public key $pk$ can check that the output
has been generated by VRF, by calling VRFverify$(\cdot,{\rm
output},\pi_{sk}(\cdot),pk)$. An efficient implementation of VRF was
introduced in (Dodis and Yampolskiy, 2005). This ensures that the output of a
VRF is computationally indistinguishable from a random number even if the
public key $pk$ and the function VRFprove is revealed.