before completing the lifetime of a directory node. Since the lifetime is set
to be $T_{\mathit{dl}}$ blocks, which amounts to at most
$\lambda_{\mathit{dl}}\mu_{b}$ epochs. The probability that an honest
directory node would stay, denoted by $P$, is at least
$2^{-\lambda_{\mathit{dl}}\mu_{b}}$.

A constant fraction of the directory nodes in a bucket are honest using
blockchain fairness. The number of honest blocks (or directory nodes) in a
bucket, denoted by $M$, is at least $(1-\rho)(1-\delta)\lambda_{d}\log^{2}N$,
with high probability, for some $\delta\leq O(1/\log N)$.

Again, due to blockchain fairness, any peer controls at most $O(\log N)$
directory nodes in a bucket. Let us say $x$ is the fraction of blocks
generated by one peer in one bucket, then whp by fairness property, for a
small $\delta^{\prime}>0$, and where $L=\lambda_{d}\log^{2}N$ is the number of
blocks in a bucket and $N_{r}$ is the network size in round $r$ in b-epoch
$e$,

$\displaystyle x$ $\displaystyle\leq
1-(1-\delta)\left(\frac{N_{r}-1}{N_{r}}\right)$
$\displaystyle\leq\delta^{\prime}+\frac{1-\delta}{N_{r}}$ $\displaystyle\leq
c\frac{\kappa}{L},$

for some suitable constant $c>0$. Note that the second term in the second
inequality is negligible, as $N_{r}\geq N^{1/y}$ in any round. Thus, the
number of blocks generated is at most $xL\leq c\kappa=c_{1}\log N$, where
$c_{1}>0$ is a constant, and $\kappa=O(\log N)$. Applying a union bound on all
the peers, each peer has at most $m=O(\log N)$ blocks in a bucket.

Let us now show that there are always at least $\lambda_{b}\log^{2}N$ honest
directory nodes in a bucket. Let $N(p)$ be the number of blocks generated by
an honest peer $p$ in a certain bucket. (Note that this is fixed once the
bucket is formed.) Let $X(p)$ be the random variable that is equal to $N(p)/m$
if $p$ stays for the entire directory node lifetime, otherwise equal to 0. The
expected value of the summation over all the honest peers is
$\sum_{p}(PN(p))/m=(PM)/m$. For large enough $\lambda_{d}$, applying a
Chernoff bound, the value of the summation is $\Theta((PM)/m)$ with high
probability. (Note that if $\lambda_{d}$ is increased, then the size of the
bucket increases, but this can be compensated by a constant factor decrease in
the number of buckets leading to a constant factor increase in the bandwidth
cost.) Multiplying the summation by $m$, gives the total number of honest
nodes that stay for the entire directory node lifetime, which is
$\lambda_{b}\log^{2}N$.

Applying a union bound on the $\mathcal{B}_{\mathit{act}}$ buckets at the
start of b-epoch $e$ and the buckets generate in b-epoch $e$, this holds for
all the buckets in the active directory in b-epoch $e$. Thus, property 1 holds
with high probability. As discussed earlier, property 2 automatically follows
if property 1 is satisfied for all the required buckets. ∎

######  Lemma 9.15.

If a b-epoch is bandwidth-adequate and the active directory is robust in that
b-epoch, then the JOIN protocol is successful with high probability.

###### Proof.

Recall that an implication of a b-epoch being bandwidth-adequate is that the
directory nodes can handle, i.e., receive and respond to all join requests
sent to them. Moreover, since the active directory is robust, the (honest)
directory nodes in each bucket have the correct membership information.

Let us first focus on any one bucket that the new node sends to join request
to. The probabilistic guarantee of the success of JOIN protocol because of the
random directory node sampling done for REQ_INFO messages. If an honest
directory node in that bucket receives REQ_INFO, then it sends the required
entry information to the new node. This is sufficient because the Byzantine
directory nodes can only under-represent the committee nodes.

Thus, we calculate the probability that the new node samples an honest
directory node in that bucket. Since it picks $\lambda_{j}\log N$ uniform and
independent samples, for large enough $\lambda_{j}$, the probability that none
of them honest nodes is
$\left[1-\frac{\lambda_{b}}{\lambda_{d}}\right]^{\lambda_{j}\log
N}\leq\frac{1}{N^{c}}$, for some constant $c>2$.

Applying a union bound over all the $O(\log N)$ buckets that the new node
contacts, the JOIN protocol is successful with a high probability. ∎

######  Theorem 9.16.

If the b-epochs $e,e-1,\dots,z$ where
$z=\mathrm{max}(1,e-\lceil\lambda_{l}\mu_{b}\rceil)$, are stable and
bandwidth-adequate, and if the active directory is robust in those b-epochs,
then whp, the overlay network is partition-resilient in b-epoch $e$.

###### Proof.

Since the last $\lambda_{l}\mu_{b}$ b-epochs are stable, the first property of
partition-resilience is ensured with high probability by Lemma 9.9 and 9.11,
for a large enough $\lambda_{n}$. (For the first b-epoch, there exists at
least $\lambda_{p}$ honest peers in each committee if the network is correctly
bootstrapped.) Observe that if the join protocols of all the nodes that joined
in the last $\lambda_{l}\mu_{b}$ are successful, then the requirements for the
connections among peers are also ensured. Since the last $\lambda_{l}\mu_{b}$
b-epochs are bandwidth-adequate and the active directory is robust, then by
Lemma 9.15, all the (honest) nodes are successful with high probability, for a
large enough $\lambda_{j}$. ∎

######  Lemma 9.17.

If b-epoch $e$ is stable and bandwidth-adequate, and the network is partition-
resilient in b-epoch $e$, then whp, the (honest) peers can calculate the
quantity $M^{\prime}_{e}$ such that
$M^{\prime}_{e}\in[(1-\delta_{\mathit{err}})(1-\rho)M^{L}_{e}/\mu_{b},(1+\delta_{\mathit{err}})\mu_{b}M^{H}_{e}]$.

###### Proof.

Unlike other protocols, the network size estimation protocol is minimally
affected by $\Delta$-synchrony. (Recall that there can be a difference of
$\mu_{b}$ blocks in the chain lengths of honest peers.) This is because the
node joins are bound to the block used in their proofs. Thus, the existing
peers consider all the node joins in phase 1 even though they may start and
end the phase 1 of b-epoch at possibly different times. Let $G^{\prime}_{e}$
and $G_{e}$ be the estimate and actual number of nodes that joined in phase 1
of b-epoch $e$ respectively. First, let us show that whp, all the honest peers
can calculate the quantity $G^{\prime}_{e}$, and
$G^{\prime}_{e}\in[(1-\delta_{1})G_{e},(1+\delta_{1})G_{e}]$ where
$\delta_{1}<1$ is a small positive constant.

Let $J_{e}$ be the expected number of new nodes that can be generated in phase
1 of b-epoch $e$. Recall that the node difficulty threshold,
$p_{n}=(\lambda_{n}\log N)/(q\alpha)$, is fixed. Since by design, phase 1 of a
b-epoch is $\Theta(\alpha)$, for a large enough $\lambda_{n}$, using Chernoff
bounds, $G_{e}\in[(1-\delta_{2})(1-\rho)J_{e},(1+\delta_{2})J_{e}]$, for a
small positive constant $\delta_{2}<1$. The lower bound has a factor of
$(1-\rho)$ because the Byzantine peers may choose not to join any of their
nodes (or even mine for nodes). For ease of exposition, let the aforementioned
bounds be $G_{e}\in[C_{1}\lambda_{n}\mathcal{C}_{e}\log
N,C_{2}\lambda_{n}\mathcal{C}_{e}\log N]$, where $C_{1}$ and $C_{2}$ are
appropriate constants.

Note that $k_{c}\geq 1$ random committees broadcast the newly joined node IDs
(Step 3 of Algorithm 3 description in Section 4.1). All the peers get to know
the number of new nodes that have joined each of those $k_{c}$ committees in
at most $\Delta$ rounds because the network is partition-resilient and b-epoch
$e$ is bandwidth-adequate. The peers need to estimate $G_{e}$ from that
information. This is analogous to showing that if $m=G_{e}$ balls are
(uniform) randomly thrown into $n=\mathcal{C}_{e}$ bins. If $k_{c}$ bins are
(uniform) randomly picked to see the number of balls in them, then the
estimate of $m$ is within a (fixed) multiplicative error of
$\delta_{1}\in(0,1]$, whp, assuming $m/n\geq C_{1}\lambda_{n}\log N$.

Let $X_{i,j}$ be a Bernoulli random variable such that $X_{i,j}=1$ if the
$i^{\mathrm{th}}$ ball is thrown into bin $j$, and $X_{i,j}=0$ otherwise. For
a given ball $i$, $X_{i,1},X_{i,2},\dots,X_{i,n}$ are zero-one random
variables, meaning that $\forall j,X_{i,j}\in\\{0,1\\}$, and their sum being
equal to 1, $\sum_{j}X_{i,j}=1$. By Lemma 8 in [DR96], these random variables
are negatively associated. Let $\mathbf{X}_{i}=\\{X_{i,j}\\}^{j=n}_{j=1}$,
then it is easy to see that $\mathbf{X}_{i}$ and $\mathbf{X}_{j}$, for $i\neq
j$, are independent. Then, by Proposition 7 in [DR96], the full vector,
$\\{X_{i,j}\\}^{i=m,j=n}_{i=1,j=1}$, is also negatively associated.

Since $k_{c}$ bins are (uniform) randomly picked, by symmetry, let them be the
first $k_{c}$ bins. Let $H_{e}=\sum^{i=m,j=k}_{i=1,j=1}X_{i,j}$. Since for all
$j$, $\mathbb{E}[\sum^{i=m}_{i=1}X_{i,j}]=m/n$, by linearity of expectation,
$\mathbb{E}[H_{e}]=k_{c}m/n$. Using both sides of Chernoff bounds,

$\displaystyle\mathrm{Pr}[H_{e}\not\in[(1-\delta_{1})mk_{c}/n,(1+\delta_{1})mk_{c}/n]]$
$\displaystyle=Pr[H_{e}\mathcal{C}_{e}/k_{c}\not\in[(1-\delta_{1})G_{e},(1+\delta_{1})G_{e}]]$
$\displaystyle\leq 2\exp(-mk_{c}\delta_{1}^{2}/3n)$ $\displaystyle\leq
2\exp(-C_{1}\lambda_{n}k_{c}\log N\delta_{1}^{2}/3).$

For a large enough $\lambda_{n}$, $C_{1}\lambda_{n}k_{c}\delta_{1}^{2}/3>1$.
This proves that whp, all the honest peers can calculate the quantity
$G^{\prime}_{e}$, and
$G^{\prime}_{e}\in[(1-\delta_{1})G_{e},(1+\delta_{1})G_{e}]$ where
$\delta_{1}<1$ is a small positive constant.

Recall that the actual number of nodes that are generated in phase 1 of
b-epoch $e$ is $G_{e}\in[(1-\delta_{2})(1-\rho)J_{e},(1+\delta_{2})J_{e}]$. By
blockchain liveness, the time elapsed in phase 1 of any b-epoch is at least
$\alpha_{1}/\mu^{2}_{b}$ rounds and at most $\alpha_{1}$ rounds. Hence,
$p_{n}\alpha_{1}M^{L}_{e}/\mu^{2}_{b}\leq J_{e}\leq p_{n}\alpha_{1}M^{H}_{e}$,
and this implies that
$G_{e}\in[(1-\delta_{2})(1-\rho)p_{n}\alpha_{1}M^{L}_{e}/\mu^{2}_{b},(1+\delta_{2})p_{n}\alpha_{1}M^{H}_{e}]$
where $M^{L}_{e}$ and $M^{H}_{e}$ are the minimum and maximum network sizes in
phase 1 of b-epoch $e$. If the constants $\delta_{1}$ and $\delta_{2}$ are
appropriately chosen, and it is given to us that
$G^{\prime}_{e}\in[(1-\delta_{1})G_{e},(1+\delta_{1})G_{e}]$, this would imply
that
$G^{\prime}_{e}\in[(1-\delta_{\mathit{err}})(1-\rho)p_{n}\alpha_{1}M^{L}_{e}/\mu^{2}_{b},(1+\delta_{\mathit{err}})p_{n}\alpha_{1}M^{H}_{e}]$.

Since $p_{n},\alpha_{1}$ and $\mu_{b}$ are known to all the peers, the
(honest) peers calculate the quantity
$M^{\prime}_{e}=G^{\prime}_{e}\mu_{b}/p_{n}\alpha_{1}$ so that
$M^{\prime}_{e}\in[(1-\delta_{\mathit{err}})(1-\rho)M^{L}_{e}/\mu_{b},(1+\delta_{\mathit{err}})\mu_{b}M^{H}_{e}]$,
thus proving the lemma. ∎

######  Theorem 9.18.

If b-epoch $e$ is stable and bandwidth-adequate, and the network is partition-
resilient in b-epoch $e$, then whp, b-epoch $e$ is synchronized.

###### Proof.

After phase 1 of b-epoch $e$, all the honest peers receive the set of nodes
that joined a (randomly selected) committee (Step 3 of Algorithm 3 description
in Section 4.1) as the network is partition-resilient and b-epoch $e$ is
bandwidth-adequate. In Step 3 of Algorithm 3 description in Section 4.1, due
to Lemma 9.17, whp, all the honest peers can calculate the quantity
$M^{\prime}_{e}$ such that
$M^{\prime}_{e}\in[(1-\delta_{\mathit{err}})(1-\rho)M^{L}_{e}/\mu_{b},(1+\delta_{\mathit{err}})\mu_{b}M^{H}_{e}]$.

Finally, by the fairness assumption, with high probability, in a segment of
length of $L=\lambda_{\mathit{lb}}\log N$, the fraction of blocks held by the
honest peers is at least $(1-\delta^{\prime})(1-\rho)$, where
$\delta^{\prime}$ is a small constant that depends on $\lambda_{\mathit{lb}}$.
The parameters are set such that $(1-\delta^{\prime})(1-\rho)>0.5$, which
means that there is an honest majority of blocks. ∎

######  Lemma 9.19.

If b-epoch $e$ is synchronized, then b-epoch $e$ has a good estimate ratio.

###### Proof.

All (honest) peers adopt the network size estimate after phase 1 of b-epoch
$e$ by setting $L^{\prime}_{e}=M^{\prime}_{e}$, where
$M^{\prime}_{e}\in[(1-\delta_{\mathit{err}})(1-\rho)M^{L}_{e}/\mu_{b},(1+\delta_{\mathit{err}})\mu_{b}M^{H}_{e}]$,
and $M^{L}_{e}$ and $M^{H}_{e}$ are the minimum and maximum network sizes in
phase 1 of b-epoch $e$ and $\delta_{\mathit{err}}<1$ is a small positive
constant. Notice that $M^{H}_{e}/2\leq L_{e}\leq 2M^{L}_{e}$ as the network
size can change by a multiplicative factor of $2$ in any b-epoch. (This is
because the number of rounds in any b-epoch is at most $\alpha$ rounds by the
blockchain liveness.)

To maximize the estimate ratio of b-epoch $e$, we need to minimize
$L^{\prime}_{e}$ and maximize $L_{e}$,

$\displaystyle\frac{L_{e}}{L^{\prime}_{e}}=\frac{2M^{L}_{e}}{(1-\delta_{\mathit{err}})(1-\rho)M^{L}_{e}/\mu_{b}}=\frac{2\mu_{b}}{(1-\rho)(1-\delta_{\mathit{err}})}.$

This upper bound is actually attained when the Byzantine peers do not join
their nodes in phase 1 (thereby reducing the total estimate of the hash power
by a factor $(1-\rho)$) and the total hash rate remains the same until phase
1, and increases by a factor of $2$ by the end of the b-epoch (which means
that this increase in hash rate was not captured by the estimation algorithm
in phase 1).

To minimize the estimate ratio of b-epoch $e$, we need to maximize
$L^{\prime}_{e}$ and minimize $L_{e}$,

$\displaystyle\frac{L_{e}}{L^{\prime}_{e}}=\frac{M^{H}_{e}}{2(1+\delta_{\mathit{err}})\mu_{b}M^{H}_{e}}=\frac{1}{2\mu_{b}(1+\delta_{\mathit{err}})}.$

And this lower bound is actually attained when all the Byzantine peers (mine
and) join their nodes in phase 1 and the total hash rate remains the same
until phase 1, and decreases by a factor of $2$ by the end of the b-epoch. ∎

######  Theorem 9.20.

If the network is partition-resilient in b-epochs $e-1$ and $e-2$, and if
b-epochs $e-1$ and $e-2$ are synchronized, and if the b-epochs $e-1$ is
bandwidth-adequate, then b-epoch $e$ is a stable b-epoch, for $e\geq 3$. If
the network is appropriately bootstrapped (Section 3), then b-epochs 1 and 2
are stable b-epochs.

###### Proof.

Let us first consider a b-epoch $e\geq 3$. For b-epoch $e$ to be a stable
b-epoch, the dimension of the hypercube should be appropriately set according
to the network size in any round in b-epoch $e$. Since there is a “lag” of one
b-epoch in increasing the dimension (see Section 4.3), the decision to change
the dimension of the hypercube must be taken by all the peers at the end of
b-epoch $e-2$; this can be done because the b-epoch $e-2$ is synchronized. By
the end of b-epoch $e-1$, the new number of committees is agreed upon by all
peers again because the b-epoch $e-2$ is synchronized. As the b-epoch $e-1$ is
bandwidth-adequate, and the network is partition-resilient in b-epoch $e-1$,
the appropriate dimension of the hypercube in b-epoch $e$ is adopted such that
the network size in any round $r$ of b-epoch $e$ satisfies the bounds given in
Definition 9.6.

Section 3 provides details about bootstrapping the network such that
Definition 9.6 is satisfied. Moreover, the dimension of the hypercube need not
be changed in both b-epoch 1 and 2 because the network size can change by at
most a factor of $2$ (as there are at most $\alpha$ rounds in a b-epoch via
blockchain liveness). In other words, the network size will remain within the
bounds given in Definition 9.6. Thus, b-epoch 1 and 2 are stable. ∎

######  Theorem 9.21.

The overlay network is partition-resilient and each honest peer sends or
receives $O(\log^{3}N)$ messages per round, for a polynomial number of rounds
with high probability.

###### Proof.

The goal is to maintain partition-resilience over a polynomial number of
b-epochs once the network is appropriately bootstrapped at time zero. We
carefully exploit the dependencies of the theorems described so far to prove
the statement. We describe a series of events that turn out to be useful.

  * •

$\mathtt{P}_{i}$ is the event that the network is partition-resilient in
b-epoch $i$.

  * •

$\mathtt{Q}_{i}$ is the event that b-epoch $i$ is synchronized.

  * •

$\mathtt{R}_{i}$ is the event that b-epochs $i,i-1,\dots,z$ where
$z=\mathrm{max}(1,i-\lceil\lambda_{l}\mu_{b}\rceil)$, are stable.

  * •

$\mathtt{T}_{i}$ is the event that b-epochs $i,i-1,\dots,z$ where
$z=\mathrm{max}(1,i-\lceil\lambda_{\mathit{dl}}\mu_{b}\rceil)$, are bandwidth-
adequate.

  * •

$\mathtt{U}_{i}$ is the event that the active directory is robust in b-epochs
$i,i-1,\dots,z$ where $z=\mathrm{max}(1,i-\lceil\lambda_{l}\mu_{b}\rceil)$.

  * •

$\mathtt{S}_{i}$ is the event that b-epoch $i$ is “successful”, meaning that,
$\mathtt{S}_{i}=\mathtt{P}_{i}\cap\mathtt{Q}_{i}\cap\mathtt{R}_{i}\cap\mathtt{T}_{i}\cap\mathtt{U}_{i}$.

Both b-epoch 1 and 2 do not require dimension change if the network is
correctly bootstrapped (Section 3). As mentioned in Theorem 9.20, b-epoch 1 is
a stable b-epoch, i.e., $\mathtt{R}_{1}$ occurs. If $\mathtt{R}_{1}$ happens,
then $\mathtt{T}_{1}$ occurs with high probability by Theorem 9.13. And if
$\mathtt{T}_{1}$ happens, then $\mathtt{U}_{i}$ occurs with high probability
due to Theorem 9.14. If $\mathtt{R}_{1}$, $\mathtt{T}_{1}$ and
$\mathtt{U}_{i}$ happen, then $\mathtt{P}_{1}$ happens with high probability
because of Theorem 9.16. This also means that $\mathtt{Q}_{1}$ happens with
high probability due to Theorem 9.18. Therefore, applying a union bound,
$\mathtt{S}_{1}$ happens with high probability. The same chain of arguments
also holds for b-epoch $2$.

For a b-epoch $i$ where $i\geq 2$, if there is a dimension change, the system,
intuitively, gets bootstrapped again (during the transformation b-epoch). The
key observation in Lemma 9.11 and Theorem 9.16 is that the lower bound on the
number of honest peers for partition resilience relies only on the honest node
joins of previous b-epoch. This is important because even though after a
dimension change (adopting the new hypercube), the nodes that joined before
the transformation b-epoch are considered invalid, Lemma 9.11 and Theorem 9.16
still apply to ensure partition-resilience for the nodes in the new hypercube.

Given that the events $\mathtt{S}_{i}$ and $\mathtt{S}_{i-1}$ have occurred,
by Theorem 9.20, $\mathtt{P}_{i}\cap\mathtt{Q}_{i}\cap\mathtt{R}_{i}$ and
$\mathtt{P}_{i-1}\cap\mathtt{Q}_{i-1}\cap\mathtt{R}_{i-1}$ imply that b-epoch
$i+1$ is a stable b-epoch, in other words, event $\mathtt{R}_{i+1}$ happens.
Once $\mathtt{R}_{i+1}$ has taken place, then again, by a similar chain of
arguments, the event $\mathtt{S}_{i+1}$ happens with high probability.
Applying a union bound over a polynomial number of b-epochs, the network is
partition-resilient and each honest peer sends or receives $O(\log^{3}N)$
messages, with a high probability. ∎

###  9.1 Recovery analysis

######  Definition 9.22.

An honest peer is said to be corrupted if it either stops functioning (i.e.,
leaves the network) or becomes Byzantine in which case it is controlled by the
adversary.

######  Definition 9.23.

A bucket is said to have failed if more than $1/2$ fraction of honest peers in
it are corrupted.

######  Definition 9.24.

Let the set of buckets in the active directory that are responsible for a
committee $C$ be denoted as $B_{C}$. A committee $C$ is said to be safe if:

  1. 1.

It has at least $20\log N$ honest peers.

  2. 2.

No bucket in $B_{C}$ has failed.

######  Definition 9.25.

Two committees $C_{1}$ and $C_{2}$ are said to be connected if:

  1. 1.

Each honest peer in $C_{1}$ is connected to $\Omega(\log N)$ honest peers in
$C_{2}$.

  2. 2.

Each honest peer in $C_{2}$ is connected to $\Omega(\log N)$ honest peers in
$C_{1}$.

######  Definition 9.26.

Let $S$ denote a set of safe committees. Let $G_{S}$ be the graph where
vertices correspond to safe committees in $S$ and edges represent the
connection between two safe committees. The overlay network is said to
experience an $(\varepsilon,\delta)$-catastrophic failure in b-epoch $e$ if
the following events occur.

  1. 1.

There are at least $(1-\varepsilon)\mathcal{C}_{e}$ safe committees for a
small constant $\varepsilon>0$.

  2. 2.

At most $\delta$ fraction of peers get corrupted for a small constant
$\delta>0$.

  3. 3.

There exists a graph $G_{S}$ with a diameter at most $2\log N$, in which at
least $\mu_{n}a$ fraction of honest peers are present161616For example, a
blockchain protocol may progress with 70% of total honest peers but no
Byzantine peers, or with 90% of total honest peers and 20% of total peers
being Byzantine. $\mu_{n}$, which depends on the maximum number of Byzantine
peers, captures the fact that the blockchain provides its guarantees even if
not all the honest peers participate. Note this is a minimal requirement to
recover from a (massive) eclipse attack., where $|S|\geq
ab\mu_{n}\mathcal{C}_{e}$ for $a>1/(1-\varepsilon^{\prime})$ and
$b=1/(1-\varepsilon^{\prime\prime})$ for an arbitrarily small positive
constant $\varepsilon^{\prime}$ and $\varepsilon^{\prime\prime}\leq
O((\log^{1/2}N)/N^{1/2y})$.

######  Lemma 9.27.

(Restated, Theorem 1 of [Dat02]) No matter which $f$ nodes are made faulty in
a multi-hypercube with $n$ nodes and $(\alpha,\beta)$ expansion, there are at
least $n-\frac{\beta f}{\beta-1}$ nodes that have $\log n$-length path to at
least $n-\frac{f}{\alpha(\beta-1)}$, such that all the nodes in the path are
not faulty.

######  Lemma 9.28.

(Restated, Lemma 4.6 of [FS07]) Let $l,l^{\prime},r,^{\prime}r,d,k,\lambda$
and $n$ be any positive values where $l^{\prime}\leq l$, $r^{\prime}\leq r$,
$0<\lambda<1$ and

$d\geq\frac{2r}{r^{\prime}l^{\prime}(1-\lambda)^{2}}\left(l^{\prime}\ln\left(\frac{le}{l^{\prime}}\right)+r^{\prime}\ln\left(\frac{re}{r^{\prime}}\right)+k\ln
n\right)$

Let $G$ be a random bipartite multigraph with left side $L$ and right side $R$
where $|L|=l$, $|R|=r$ and each node in $L$ has $d$ random neighbours in $R$.
Then, with probability at least $1-n^{-k}$, for any subset of
$L^{\prime}\subset L$ where $|L^{\prime}|=l^{\prime}$, there is no set
$R^{\prime}\subset R$ where $|R^{\prime}|\subset R$, such that all nodes in
$R^{\prime}$ share less than $\lambda l^{\prime}d/r$ edges with $L^{\prime}$.

######  Lemma 9.29.

No matter which $f$ nodes are made faulty in a multi-hypercube with $n$ nodes
and $(\alpha,\beta)$ expansion, there exists a connected component of at least
$n-3f/2$ non-faulty nodes with a diameter of at most $2\log n$, for
$\alpha(\beta-1)\geq 2/3$ and $\beta\geq 3$.

###### Proof.

This follows directly from Lemma 9.27. Viewing the multi-hypercube as a
$n$-node multi-butterfly network where a row of switches is simulated by a
node, the theorem says that any of the $\left(n-\frac{\beta
f}{\beta-1}\right)$ (non-faulty) inputs can reach any of the (non-faulty)
$\left(n-\frac{f}{\alpha(\beta-1)}\right)$. For $\alpha(\beta-1)\geq 2/3$ and
$\beta\geq 3$, consider a connected component $c$ of any one such (non-faulty)
input and the $n-3f/2$ (non-faulty) outputs including the intermediate
switches; each pair of them can reach other by a path of length at most $2\log
n$. In case of a multi-hypercube, since a row (consisting of one input, one
output and $\log n$ switches) is simulated by one node, there are at least
$n-3f/2$ _distinct_ nodes (because one output is simulated by one node and
there are $n-3f/2$ such outputs) in $c$ that have a diameter of at most $2\log
n$. ∎

######  Lemma 9.30.

For $e\geq 2$ and constant $\lambda_{p}>0$, if at most $\delta$ fraction of
peers are corrupted in a stable b-epoch $e-1$, then in b-epoch $e$, there are
at least $(1-\varepsilon^{\prime})\mathcal{C}_{e}$ committees that are
assigned with at least $\lambda_{p}\log N$ honest peers with high probability,
where $\varepsilon^{\prime}\leq O(1/\log N)$ and $\delta<1$ is a small
positive constant.

###### Proof.

First, we get a lower bound on the number of honest peers that stay in the
entire b-epoch $e-1$. By stable b-epoch property and the fact that at most
$\rho$ fraction are Byzantine, this is at least
$(1-\rho)\mathcal{C}_{e-1}/\lambda_{s}$. Then, we find a lower bound on the
number of new nodes generated in b-epoch $e-1$ by each of these peers. Recall
that the node difficulty threshold, $p_{n}=(\lambda_{n}\log N)/(q\alpha)$, is
fixed. By blockchain liveness (for number of rounds in a b-epoch), the
expected number of new honest nodes, in b-epoch $e-1$, is at least
$(\lambda_{n}\log N)/\mu^{2}_{b}$. Applying Chernoff bounds and union bound,
the total number of honest nodes by each of those peers generated is at least
$d=\Theta(\lambda_{n}\log N)$ with high probability. (We drop the other
constants unless necessary, as $\lambda_{n}$ controls the failure
probability.)

These nodes get randomly mapped to $\mathcal{C}_{e}$ committees. (Note that
$\mathcal{C}_{e}=\mathcal{C}_{e-1}$ if b-epoch $e-1$ is not a transformation
b-epoch, and even otherwise, $\mathcal{C}_{e}=\Theta(\mathcal{C}_{e-1})$.)
Here, in Lemma 9.28, we can consider these peers as the left side $L$ and the
committees in b-epoch $e$ as the right side $R$ where each vertex in $L$ has
at least $d$ random neighbours in $R$. In other words, with probability less
than $n^{-k}$ for some constant $k>2$, there exists a set $L^{\prime}\subset
L$ such that $l^{\prime}=\delta l$ and a set $R^{\prime}\subset R$ of size
$(1-\varepsilon^{\prime})\mathcal{C}_{e}$ where each vertex has less than
$\lambda_{p}c_{m}\log N$ nodes, for a positive constant $c_{m}$. Specifically,
$\lambda_{n}$ is set large enough so that $\lambda
l^{\prime}d/r\geq\lambda_{p}c_{m}\log N$. As every other parameter is fixed,
obeying the condition of Lemma 9.28 by (again) setting $\lambda_{n}$ large
enough, with high probability, we get that there are at least
$(1-\varepsilon^{\prime})\mathcal{C}_{e}$ committees that are assigned with at
least $\lambda_{p}c_{m}\log N$ honest nodes even after $\delta$ fraction of
peers get corrupted.

Finally, by Lemma 9.10, each peer controls at most $c_{m}$ nodes in a
committee with a high probability. Thus, in b-epoch $e$, there are at least
$(1-\varepsilon^{\prime})\mathcal{C}_{e}$ committees that are assigned with at
least $\lambda_{p}\log N$ honest peers with high probability. ∎

######  Lemma 9.31.

In any round $r$, if there are at least $\mu_{n}aI$ honest peers in a set $S$
of committees, the following statements hold with high probability, where
$|S|,|S^{\prime}|\geq\mu_{n}abC$, $C$ is the number of committees,
$\mu_{n}ab<1$, $a>1/(1-\varepsilon^{\prime})$ and
$b=1/(1-\varepsilon^{\prime\prime})$ for $\varepsilon^{\prime\prime}\leq
O((\log^{1/2}N)/N^{1/2y})$ and an arbitrarily small positive constant
$\varepsilon^{\prime}$. Here, $I$ is the total number of honest peers at round
$r$. $J_{r^{\prime}}$ and $L_{r^{\prime}}$ are the number of new honest peers
that joined the network and the number of peers that left the network
respectively, from round $r$ to $r^{\prime}$.

  1. 1.

There are at least $\mu_{n}a(I+J_{r_{1}}-L_{r_{1}})$ honest peers at round
$r+r_{1}$ for any $\alpha/\mu^{2}_{b}\leq r_{1}\leq\alpha$ in set $S^{\prime}$
of committees.

  2. 2.

For any round $r\leq r_{2}\leq\alpha$, there are at least
$\mu_{n}(I+J_{r_{2}}-L_{r_{2}})$ honest peers in the set $S$ of committees.

###### Proof.

The Lemma says that there exists a large enough set of committees that can be
replenished with a set of distinct honest peers in a span of a b-epoch. And
that in any round in the b-epoch, despite joins and leaves, a certain fraction
of honest peers are maintained in those set of committees. Note that this
Lemma does not deal with successful joins, robust active directory, etc., but
only talks about peers getting assigned to committees. (They will be dealt
with in Theorem 9.32.)

Let us prove the first property. Let $L^{1}_{r_{1}}$ be the number of honest
peers in round $r$ that left the network by round $r_{1}$. Let $L^{2}_{r_{1}}$
be the number of honest peers from the set of peers that joined in subsequent
rounds left the network by round $r_{1}$. Thus,
$L_{r_{1}}=L^{1}_{r_{1}}+L^{2}_{r_{1}}$. Let $J^{1}_{r_{1}}$ be the number of
(new) honest peers that joined and stayed till round $r_{1}$. Let
$J^{2}_{r_{1}}$ be the number of (new) honest peers that joined and left the
network by $r_{1}$. Thus, $J_{r_{1}}=J^{1}_{r_{1}}+J^{2}_{r_{1}}$.

Note that $(I+J_{r_{1}}-L_{r_{1}})=(I+J^{1}_{r_{1}}-L^{1}_{r_{1}})$. For a
large enough $\lambda_{n}$, each of the $(I-L^{1}_{r_{1}})$ get at least one
new (valid) node with high probability (via Chernoff bounds). Since
$J^{1}_{r_{1}}$ peers joined the network, they must have joined with at least
one (valid) node. Thus, out of the $(I+J^{1}_{r_{1}}-L^{1}_{r_{1}})$ peer
joins, on expectation, $\mu_{n}ab(I+J^{1}_{r_{1}}-L^{1}_{r_{1}})$ go to the
set $S^{\prime}$ of committees (as each node is randomly mapped to a
committee). Thus, applying Chernoff bounds, for
$\varepsilon^{\prime\prime}\leq O((\log^{1/2}N)/N^{1/2y})$, there are at least
$\mu_{n}a(I+J_{r_{1}}-L_{r_{1}})$ honest peers at round $r+r_{1}$ with high
probability.

Consider a large enough $s=\Theta(\log N)$. We batch together $s$ leaves and
$s$ joins over the rounds until round $r_{2}$ to prove the second property.
Batching the joins together is not difficult as they are independent of each
other. Batching the leaves together requires a little care. Recall that the
sequence of honest leaves are obliviously specified by the churn adversary.
Let us say that there are $n$ peers at round $r$. And, for some round
$r^{\prime}\geq r$, there are $l$ honest peer leaves and $j$ honest peer joins
from round $r$ until round $r^{\prime}$. Then, focusing on $r^{\prime}$, we
can claim that any set of $l$ honest peers (out of $n+j$ peers) has equal
probability of having left.

Applying Chernoff bounds for a batch of $s$ honest leaves, there are at most
$(1+\varepsilon^{\prime})\mu_{n}as$ honest leaves from the set $S$ of
committees with high probability for a small $\varepsilon^{\prime}>0$ and
large enough $s$. Similarly, applying Chernoff bounds for a batch of $s$
honest joins, there are at least
$\mu_{n}ab(1-\varepsilon^{\prime})s\geq\mu_{n}a(1-\varepsilon^{\prime})s$
honest joins from the set $S$ of committees with high probability for a small
$\varepsilon^{\prime}>0$ and large enough $s$.

Let the number of honest peers at round $r$ in the set $S$ of committees be
denoted as $H_{r}$. Then, for any round $r\leq r_{2}\leq\alpha$,

$\displaystyle H_{r_{2}}$
$\displaystyle\geq\mu_{n}aI-\mu_{n}a(1+\varepsilon^{\prime})L_{r_{2}}-O(\log
N)+\mu_{n}a(1-\varepsilon^{\prime})J_{r_{2}}-O(\log N)$
$\displaystyle=\mu_{n}(I+(a-1)I-L_{r_{2}}-(a(1+\varepsilon^{\prime})-1)L_{r_{2}}+J_{r_{2}}+(a(1-\varepsilon^{\prime})-1)J_{r_{2}})-O(\log
N)$
$\displaystyle=\mu_{n}(I-L_{r_{2}}+J_{r_{2}})+\mu_{n}((a-1)I-(x(1+\varepsilon^{\prime})-1)L_{r_{2}}+(a(1-\varepsilon^{\prime})-1)J_{r_{2}})-O(\log
N).$

For $a\geq 1/(1-\varepsilon^{\prime})$, we can ignore the second join term as
that would only increase the RHS,

$H_{r_{2}}\geq\mu_{n}(I-L_{r_{2}}+J_{r_{2}})+\mu_{n}((a-1)I-(a(1+\varepsilon^{\prime})-1)L_{r_{2}})-O(\log
N).$

By using the fact that if the number of honest peers at round $r$ is $I$, then
at any $r\leq r_{2}\leq\alpha$, then at most half the number of those peers
can leave the network, i.e., considering all peers are honest (which maximizes
$L_{r_{2}}$), we get that $L_{r_{2}}\leq I/2$. Thus, for
$a>1/(1-\varepsilon^{\prime})$,

$\displaystyle H_{r_{2}}$
$\displaystyle\geq\mu_{n}(I-L_{r_{2}}+J_{r_{2}})+\mu_{n}I((a-1)-(a(1+\varepsilon^{\prime})-1)/2)-O(\log
N)$
$\displaystyle\geq\mu_{n}(I-L_{r_{2}}+J_{r_{2}})+\mu_{n}I\left(a\left(\frac{1-\varepsilon^{\prime}}{2}\right)-\frac{1}{2}\right)-O(\log
N)$ $\displaystyle\geq\mu_{n}(I-L_{r_{2}}+J_{r_{2}}).$

∎

######  Theorem 9.32.

If the overlay network experiences an $(\varepsilon,\delta)$-catastrophic
failure, then it becomes partition-resilient in a constant number of epochs
with high probability.

###### Proof.

The high-level intuition for attaining recovery is to replace the entire
active directory by a new one (that has no bucket failures). If that is
posssible, then new active directory facilitates honest nodes joins to
committees as required. Catastrophic failure is defined in a way that there is
one large connected component of sufficient number of honest peers with a low
diameter, that is responsible for the progress of the blockchain. First, we
need to prove that the component gets replenished with new (honest) peers as
peers join and leave. Then, we focus on that component of committees and show
that the lemmas and theorems in Section 9 hold for them, albeit for some small
changes. If we can show that the overlay can rely on those subset of
committees until a new active directory is formed, then after one additional
b-epoch, the overlay reverts to being (fully) partition-resilient as in
Section 9. (Recall that an active directory consists of $O(\alpha/\beta)$
blocks, amounting up to a $O(\alpha)$ rounds, via blockchain liveness.) The
main technical difficulty lies in handling dimension change and showing that
the new topology has a large connected component of committees with a low
diameter, having a sufficient number of honest peers. And to handle that
difficulty, we rely on the properties of multi-hypercube [Dat02] and bipartite
expanders [FS02, FS07].

Let us say that it takes at most $K$ half-lives for an active directory to be
formed. We split the proof into three cases. (Case 2 and 3 can be merged
together, but we keep them separate for ease of understanding.)

Case 1. In this case, the overlay does not initiate a dimension change in any
b-epoch $e,e+1,\dots,e+K+1$. If $\mu_{n}ab<(1-\varepsilon)$ in Lemma 9.31
where $a,b$ as in Definition 9.26, the set $S$ of committees have a sufficient
number of honest peers in b-epoch $e$ and the subsequent b-epochs with high
probability. We now focus on the set $S$ of committees (and their buckets) and
show that the lemmas and theorems in Section 9 also hold after a catastrophic
failure. The lemmas related to bounds on the number of node assignments to
committees, number of nodes controlled by a peer and the number of join
requests handled by a peer (and the total communication cost) apply here
without any change. Instead of showing that the entire active directory is
robust, Theorem 9.14 can be used to show that the non-failed buckets have the
required properties of robustness (Definition 9.1). This can be done by
increasing $\lambda_{d}$ by a factor of 2, after which the same analysis holds
in Theorem 9.14, as at most 1/2 fraction of honest peers in a non-failed
bucket get corrupted. Thus, the node joins for those buckets are successful.

The network is not partition-resilient, even for the set $S$ of committees,
because by definition, safe committees have at least $20\log N$ honest peers
(and not at least $\lambda_{p}\log N$ honest peers). As the safe committees
have at least $20\log N$ honest peers, by Chernoff and union bounds, at least
$\Omega(\log N)$ in each safe committee would stay for another 2 b-epochs with
high probability. Thus, connectivity among committees in $S$ maintained during
those two b-epochs. Then, by Lemma 9.11, using the node joins in b-epoch
$e+1$, we can show that the properties of partition resilience (Definition
9.3) hold for the set $S$ of committees from b-epoch $e+2$ onwards. (The
definition of partition-resilience is deliberately made to be topology-
oblivious, as in, it can also apply to any subset of committees.)

The tricky part is to show that partition-resilience properties can be
maintained for $S$ if network size is allowed to significantly vary over time.
Specifically, a small modification is required for Algorithm 3 used to
estimate the network size. A random committee is selected using the hash of
the block that determines the end of phase 1 of that b-epoch. Instead of
choosing a random committee, we make a small modification to the protocol to
choose $\Theta(\log N)$ random committees. (For example, this can be done by
appending $1,2,\dots,\log N$ to the input, consisting of hash of the block,
for the hash function, and obtaining the output for each of those inputs. In
other words, the hash function can be used to generate the required verifiable
randomness, where the computational cost is negligible. Recall that each peer
can query the hash function $q>0$ number of times in a round, where $q$ is
substantially large.) Once a node receives the entry information of the nodes
that belonged to those committees, it chooses the committee that encountered
the maximum number of node joins. If this modification is done, then with a
high probability, that chosen committee would belong to $S$ because
$|S|>\mathcal{C}_{e}$. (The nodes consider the committee with maximum number
of node joins because the failed committees can only under-represent node
joins.) Thus, the rest of the lemmas and theorems regarding network size
estimation and b-epoch synchronization hold if the network size estimation can
be done securely. (Also, network size estimation is required for the
subsequent cases in which dimension change needs to be done.)

Case 2. In this case, b-epoch $i$ is a transformation b-epoch for $i>e$. The
proof arguments from Case 1 also carry over to this case until b-epoch $i$.
The tricky part is to handle dimension change, as it is important to maintain
a set $S^{\prime}$ in the new topology that has similiar properties as $S$ so
that the proof arguments from Case 1 can also apply from b-epoch $i+1$
onwards. Our first observation is that at most $\varepsilon$ fraction of
buckets have failed in a directory. This is because if there are more bucket
failures, then this would result in a number of committee failures greater
than $\varepsilon\mathcal{C}_{e}$. Since this applies to all the directories
in the active directory, at most $\varepsilon$ buckets fail in the active
directory during a catastrophic failure. This means that at most $\varepsilon$
committees have failed in the next topology as well, as the committee-
directory mappings are such that each bucket is responsible for the same
number of committees, and the sets of committees that any two buckets are
responsible for, are disjoint. We now rely on the guarantees provided by the
multi-hypercube. By Lemma 9.27, at least
$\mathcal{C}_{i+1}(1-(3\varepsilon/2))$ form a connected component171717Refer
to Definition 9.24 for connectivity between committees. with a diameter of at
most $2\log N$. If $(1-(3\varepsilon/2))>\mu_{n}ab$ as in Definition 9.26,
then using Lemma 9.31, the same arguments carry over to the next topology.
This applies to multiple dimension changes that can occur over the $K+1$
b-epochs.

Case 3. In this case, b-epoch $e$ itself is a transformation b-epoch. We
cannot just rely on the multi-hypercube as the honest peers that replenish the
committees in $S^{\prime}$ in the next topology, may get corrupted during (or
towards the end of) b-epoch $e$. We first compute an upper bound on the number
of committees that can have less than $\lambda_{p}\log N$ honest peers if in
total $\delta$ fraction of honest peers are corrupted. By Lemma 9.30, there
are at most $\delta^{\prime}\leq O(1/\log N)$ fraction of committees that have
less than $\lambda_{p}\log N$ honest peers. Thus, if
$(1-(3\varepsilon/2)-\delta^{\prime})\geq\mu_{n}ab$ as in Definition 9.26,
then using Lemma 9.31, there are a sufficient number of honest peers in
$S^{\prime}$ throughout b-epoch $i+1$ by Lemma 9.31 with high probability. In
other words, the overlay can rely on the set $S^{\prime}$ for the progress of
the blockchain for b-epoch $i+1$. Moreover, as in previous case, there are at
most $\varepsilon$ fraction of committees fail due to bucket failures. From
b-epoch $i+2$ onwards, the committees that had less than $\lambda_{p}\log N$
honest peers in b-epoch $i+1$, but whose buckets had not failed, have at least
$\lambda_{p}\log N$ honest peers with high probability by Lemma 9.11. Thus,
the set $S^{\prime}$ again resorts to the large connected component of
committees guaranteed by the multi-hypercube. Then, from b-epoch $i+2$
onwards, the overlay can rely on that set of committees for the progress of
the blockchain, where the same proof arguments of Case 1 apply.

Thus, in all these cases, the overlay network becomes partition-resilient in a
constant number of b-epochs with high probability.

∎

## References

  * [AS04] Baruch Awerbuch and Christian Scheideler.  _Group spreading: A protocol for provably secure distributed name service_.  In _International Colloquium on Automata, Languages, and Programming_ , pages 183–195. Springer, 2004.
  * [AS09] ———.  _Towards a scalable and robust dht_.  Theory of Computing Systems, 45(2):234–260, 2009.
  * [AZV17] Maria Apostolaki, Aviv Zohar, and Laurent Vanbever.  _Hijacking bitcoin: Routing attacks on cryptocurrencies_.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pages 375–392. IEEE, 2017.
  * [bit20] _BitInfoCharts - Bitcoin Explorer_, 2020 (accessed August 28, 2020).
  * [blo20] _Blockchain.com Explorer_, 2020 (accessed August 28, 2020).
  * [BNO+21] Seungjin Baek, Hocheol Nam, Yongwoo Oh, Muoi Tran, and Min Suk Kang.  _On the claims of weak block synchronization in bitcoin_.  Cryptology ePrint Archive, Report 2021/1282, 2021.  https://ia.cr/2021/1282.
  * [CDKR02] Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, and Antony Rowstron.  _One ring to rule them all: Service discovery and binding in structured peer-to-peer overlay networks_.  In _Proceedings of the 10th workshop on ACM SIGOPS European workshop_ , pages 140–145. 2002.
  * [CDP96] Bogdan S Chlebus, Krzysztof Diks, and Andrzej Pelc.  _Reliable broadcasting in hypercubes with random link and node failures_.  Combinatorics, Probability and Computing, 5(4):337–350, 1996.
  * [CGJ+17] Arka Rai Choudhuri, Matthew Green, Abhishek Jain, Gabriel Kaptchuk, and Ian Miers.  _Fairness in an unfair world: Fair multiparty computation from public bulletin boards_.  In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , pages 719–728. 2017.
  * [CH07] Michael Conrad and Hans-Joachim Hof.  _A generic, self-organizing, and distributed bootstrap service for peer-to-peer networks_.  In _International Workshop on Self-Organizing Systems_ , pages 59–72. Springer, 2007.
  * [Dat02] Mayur Datar.  _Butterflies and peer-to-peer networks_.  In _European Symposium on Algorithms_ , pages 310–322. Springer, 2002\.
  * [DG08] Chris Gauthier Dickey and Christian Grothoff.  _Bootstrapping of peer-to-peer networks_.  In _2008 International Symposium on Applications and the Internet_ , pages 205–208. IEEE, 2008.
  * [DHVR07] Danny Dolev, Ezra N Hoch, and Robbert Van Renesse.  _Self-stabilizing and byzantine-tolerant overlay network_.  In _International Conference On Principles Of Distributed Systems_ , pages 343–357. Springer, 2007.
  * [DR96] Devdatt P Dubhashi and Desh Ranjan.  _Balls and bins: A study in negative dependence_.  BRICS Report Series, 3(25), 1996.
  * [ES14] Ittay Eyal and Emin Gün Sirer.  _Majority is not enough: Bitcoin mining is vulnerable_.  In _International conference on financial cryptography and data security_ , pages 436–454. Springer, 2014.
  * [eth20] _Etherchain - The Ethereum Blockchain Explorer_, 2020 (accessed August 28, 2020).
  * [FS02] Amos Fiat and Jared Saia.  _Censorship resistant peer-to-peer content addressable networks._ In _SODA_ , volume 2, pages 94–103. 2002.
  * [FS07] ———.  _Censorship resistant peer-to-peer networks_.  Theory of Computing, 3(1):1–23, 2007.
  * [FSY05] Amos Fiat, Jared Saia, and Maxwell Young.  _Making chord robust to byzantine attacks_.  In _European Symposium on Algorithms_ , pages 803–814. Springer, 2005\.
  * [GHK13] Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec.  _Highly dynamic distributed computing with byzantine failures_.  In _Proceedings of the 2013 ACM symposium on Principles of distributed computing_ , pages 176–183. 2013.
  * [GKL15] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  _The bitcoin backbone protocol: Analysis and applications_.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 281–310. Springer, 2015.
  * [HK03] Kirsten Hildrum and John Kubiatowicz.  _Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks_.  In _International Symposium on Distributed Computing_ , pages 321–336. Springer, 2003.
  * [HKZG15] Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg.  _Eclipse attacks on bitcoin’s peer-to-peer network_.  In _24th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 15)_, pages 129–144. 2015.
  * [HL89] Johan Hastad and Thomson Leighton.  _Fast computation using faulty hypercubes_.  In _Proceedings of the twenty-first annual ACM symposium on Theory of computing_ , pages 251–263. 1989.
  * [JPS+18] Mercy O Jaiyeola, Kyle Patron, Jared Saia, Maxwell Young, and Qian M Zhou.  _Tiny groups tackle byzantine adversaries_.  In _2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_ , pages 1030–1039. IEEE, 2018.
  * [JRVJ15] Håvard D Johansen, Robbert Van Renesse, Ymir Vigfusson, and Dag Johansen.  _Fireflies: A secure and scalable membership and gossip service_.  ACM Transactions on Computer Systems (TOCS), 33(2):1–32, 2015.
  * [KS04] Valerie King and Jared Saia.  _Choosing a random peer_.  In _Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing_ , pages 125–130. 2004.
  * [LM89] Tom Leighton and Bruce Maggs.  _Expanders might be practical: Fast algorithms for routing around faults on multibutterflies_.  In _30th Annual Symposium on Foundations of Computer Science_ , pages 384–389. IEEE Computer Society, 1989.
  * [LNBK02] David Liben-Nowell, Hari Balakrishnan, and David Karger.  _Analysis of the evolution of peer-to-peer systems_.  In _Proceedings of the twenty-first annual symposium on Principles of distributed computing_ , pages 233–242. 2002.
  * [LQ19] Angelique Faye Loe and Elizabeth Anne Quaglia.  _You shall not join: A measurement study of cryptocurrency peer-to-peer bootstrapping techniques_.  In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , pages 2231–2247. 2019.
  * [MDV+20] Yifan Mao, Soubhik Deb, Shaileshh Bojja Venkatakrishnan, Sreeram Kannan, and Kannan Srinivasan.  _Perigee: Efficient peer-to-peer network design for blockchains_.  In _Proceedings of the 39th Symposium on Principles of Distributed Computing_ , pages 428–437. 2020.
  * [MHG18] Yuval Marcus, Ethan Heilman, and Sharon Goldberg.  _Low-resource eclipse attacks on ethereum’s peer-to-peer network_.  Cryptology ePrint Archive, Report 2018/236, 2018.  https://eprint.iacr.org/2018/236.
  * [Mit00] Michael Mitzenmacher.  _How useful is old information?_ IEEE Transactions on Parallel and Distributed Systems, 11(1):6–20, 2000\.
  * [Nak08] Satoshi Nakamoto.  _Bitcoin: A peer-to-peer electronic cash system (white paper)_.  2008\.
  * [NKMS16] Kartik Nayak, Srijan Kumar, Andrew Miller, and Elaine Shi.  _Stubborn mining: Generalizing selfish mining and combining with an eclipse attack_.  In _2016 IEEE European Symposium on Security and Privacy (EuroS &P)_, pages 305–320. IEEE, 2016.
  * [NW03] Moni Naor and Udi Wieder.  _A simple fault tolerant distributed hash table_.  In _International Workshop on Peer-to-Peer Systems_ , pages 88–97. Springer, 2003.
  * [NW07] ———.  _Novel architectures for p2p applications: the continuous-discrete approach_.  ACM Transactions on Algorithms (TALG), 3(3):34–es, 2007.
  * [PD16] Joseph Poon and Thaddeus Dryja.  _The bitcoin lightning network: Scalable off-chain instant payments_ , 2016.
  * [PS17] Rafael Pass and Elaine Shi.  _Fruitchains: A fair blockchain_.  In _Proceedings of the ACM Symposium on Principles of Distributed Computing_ , pages 315–324. 2017.
  * [PSS17] Rafael Pass, Lior Seeman, and Abhi Shelat.  _Analysis of the blockchain protocol in asynchronous networks_.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 643–673. Springer, 2017.
  * [RT19] Elias Rohrer and Florian Tschorsch.  _Kadcast: A structured approach to broadcast in blockchain networks_.  In _Proceedings of the 1st ACM Conference on Advances in Financial Technologies_ , pages 199–213. 2019.
  * [S+06] Atul Singh _et al._ _Eclipse attacks on overlay networks: Threats and defenses_.  In _In IEEE INFOCOM_. Citeseer, 2006.
  * [SARM21] Muhammad Saad, Afsah Anwar, Srivatsan Ravi, and David Mohaisen.  _Revisiting nakamoto consensus in asynchronous networks: A comprehensive analysis of bitcoin safety and chainquality_.  In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , pages 988–1005. 2021.
  * [SCDR04] Atul Singh, Miguel Castro, Peter Druschel, and Antony Rowstron.  _Defending against eclipse attacks on overlay networks_.  In _Proceedings of the 11th workshop on ACM SIGOPS European workshop_ , pages 21–es. 2004.
  * [Sch05] Christian Scheideler.  _How to spread adversarial nodes? rotate!_ In _Proceedings of the thirty-seventh annual ACM symposium on Theory of computing_ , pages 704–713. 2005.
  * [SCM21] Muhammad Saad, Songqing Chen, and David Mohaisen.  _Syncattack: Double-spending in bitcoin without mining power_.  In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , pages 1668–1685. 2021.
  * [SCN+19] Muhammad Saad, Victor Cook, Lan Nguyen, My T Thai, and Aziz Mohaisen.  _Partitioning attacks on bitcoin: Colliding space, time, and logic_.  In _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_ , pages 1175–1187. IEEE, 2019.
  * [SFG+02] Jared Saia, Amos Fiat, Steve Gribble, Anna R Karlin, and Stefan Saroiu.  _Dynamically fault-tolerant content addressable networks_.  In _International Workshop on Peer-to-Peer Systems_ , pages 270–279. Springer, 2002.
  * [SGG01] Stefan Saroiu, P Krishna Gummadi, and Steven D Gribble.  _Measurement study of peer-to-peer file sharing systems_.  In _Multimedia Computing and Networking 2002_ , volume 4673, pages 156–170. International Society for Optics and Photonics, 2001.
  * [SMK+01] Ion Stoica, Robert Morris, David Karger, M Frans Kaashoek, and Hari Balakrishnan.  _Chord: A scalable peer-to-peer lookup service for internet applications_.  ACM SIGCOMM Computer Communication Review, 31(4):149–160, 2001.
  * [TCM+20] Muoi Tran, Inho Choi, Gi Jun Moon, Anh V Vu, and Min Suk Kang.  _A stealthier partitioning attack against bitcoin peer-to-peer network_.  In _IEEE Symposium on Security and Privacy (S &P)_. 2020.
  * [Upf92] Eli Upfal.  _An o (log n) deterministic packet-routing scheme_.  Journal of the ACM (JACM), 39(1):55–70, 1992.
  * [YKGK10] Maxwell Young, Aniket Kate, Ian Goldberg, and Martin Karsten.  _Practical robust communication in dhts tolerating a byzantine adversary_.  In _2010 IEEE 30th International Conference on Distributed Computing Systems_ , pages 263–272. IEEE, 2010.

##  Appendix A More on Recovery

In this section, we argue that the existing solutions for join-leave attacks
cannot easily recover from the committee failures considered in Section 5.
Their join (and leave) protocols depend on the honest majority of
committees181818They are also referred to as quorums [AS04, AS09] or swarms
[FSY05] or clusters [GHK13] in the literature.. Once a committee loses the
honest majority, it can initiate new (malicious) joins, either to replenish
itself with more malicious peers or make other committees fail. In particular,
even when a small number of committees, say $O(\log N)$ committees have a
malicious majority, then the network can continue to have at least
$\Omega(\log N)$ committees with malicious majority over time. Before delving
into the technical details, we strive to provide a high-level intuition for
vulnerability to arbitrary committee failures in the existing solutions.

First, we specify the combination of network and join protocols for which
recovery is hard to achieve. We are interested in a virtual network (that has
low diameter, low degree and good expansion) of committees of $\Theta(\log N)$
peers. Typically, this is termed as a “quorum topology” [YKGK10]. More
specifically, the committees are functional units of the (virtual) network. We
recall a few important invariants of a quorum topology [YKGK10].

######  Definition A.1.

An overlay network is said to have a quorum topology if it satisfies the
following invariants.

  1. 1.

Network of committees. The overlay network is defined by a virtual graph of
committees $G_{C}$ where vertices are committees and edges between nodes
represent connections between committees.

  2. 2.

Committee size. Each committee consists of $\Theta(s)$ peers where
$s=\Omega(\log N)$.

  3. 3.

Membership. Every peer belongs to at least one committee.

  4. 4.

Intra-committee communication. Every peer can communicate with all other
members of its committees.

  5. 5.

Inter-committee communication. If $C_{i}$ and $C_{j}$ share an edge in
$G_{C}$, then a peer belonging to $C_{i}$ can communicate directly with any
member of $C_{j}$ and vice-versa.

In addition to the five invariants mentioned in Definition A.1, the challenge
is to maintain honest majority in each committee despite churn and a constant
fraction of peers being Byzantine. The committees themselves form connections
amongst themselves according to rules of an efficient network such as Chord
[AS04, FSY05], de Bruijn graph [AS09], an expander graph [GHK13] etc. Here,
two committees are said to be _connected_ if each peer of a committee is
connected to every other peer in the other committee (and vice versa). Thus,
each committee is connected with a small number of other committees; we say
that those other committees are its “neighbouring” committees.

Although it is difficult to generalize the join protocols in the literature,
we identify a few important steps or invariants that are central to all the
existing join protocols (including this work) without getting to the details
of how they are achieved.

######  Definition A.2.

The JOIN protocol for a network with a quorum topology is said to be churn-
resilient if it consists of the following steps (in the same order).

  1. 1.

Random ID. Firstly, when a peer $p$ joins the network, it is assigned a random
committee $C_{r}$.

  2. 2.

Placement. Peers in $C_{r}$ and its neighbouring committees are informed about
the new peer $p$ after which they verify that $p$ actually belongs to $C_{r}$.

  3. 3.

Perturbation. After the new peer gets placed in a random committee, the
network is “perturbed” where at most $O(\mathrm{polylog}N)$ peers shift to
different (typically random) committees.

To get an idea of how each of those steps can be achieved, we delve deeper
into the existing solutions.

  1. 1.

Random ID. Typically, a new peer $p$ is assumed to know the contact address of
an existing (honest) peer $q$. Peer $q$ belonging to committee $C_{q}$ informs
all the peers in $C_{q}$ about the new peer $p$. For structured routable
topologies [AS04, FSY05, AS09], the peers within the committee $C_{q}$ run a
distributed random number generation (RNG) protocol to determine a random
location in the network. (We use the term “location” because the previous
solutions are based on placement of peers in the virtual (continuous) interval
$[0,1)$.) For the expander topology [GHK13], the authors heavily rely on
random walks over committees. A committee internally runs a distributed RNG
protocol to determine the next walk step (random neighbour) until the walk
ends. In our work and in [JPS+18], a peer gets bound to a random committee via
hash function (which can be verified by any other peer).

Placement. In structured routable topologies [AS04, FSY05, AS09], the peers in
$C_{r}$ are informed about $p$ by $C_{q}$ through an efficient route. Then,
peers in $C_{r}$ send their contact information to peer $p$, and also inform
their neighbouring committees about the membership of peer $p$. In the
expander topology [GHK13], the path used in the random walk is used to do the
same. In our work, the bootstrapping service directly helps $p$ in contacting
the $C_{r}$ and its neighbouring committees.

Perturbation. Shuffling peers between committees is necessary upon join and
leaves to maintain honest majority in all the committees against adaptive
join-leave attacks [AS04, GHK13]. Typically, this pertubation of network
should be “small”. For e.g., every peer can be assigned a random committee
whenever a new peer joins the network, to maintain honest majority in all
committees. But that would not be efficient at all. There are different ways
to achieve small perturbation: adopting limited lifetime for peers [AS04],
k-rotation [Sch05, FSY05], cuckoo rule [AS09], and exchange all peers in
$C_{r}$ with other random peers in the network [GHK13]. In our work, we rely
on the limited lifetime method. The limited lifetime method is indeed a small
perturbation per join because the lifetime depends on churn rate (half-life)
of the system. In other words, there is a linear number of joins and leaves in
a half-life period, and therefore, setting a lifetime of a constant number of
half-lives, essentially perturbs the network (forces re-joins) over a “batch”
of joins and leaves.

The fundamental problem in the existing solutions is that steps in Definition
A.2 heavily depends on the committees having honest majority. For example, the
distributed RNG protocol is secure only if the committee has an honest
majority. Moreover, the (random) placement of a new peer is verified through
“majority vote” routing, i.e., when a committee receives a join request of a
new peer from a majority of peers in one of its neighbouring committees, it
verifies the randomness of the placement assuming such a majority vote
occurred at each committee in the route, until the committee that executed the
distributed RNG protocol. The majority vote verification is required for
random walks solution too. Thus, honest majority of committees becomes crucial
in proving the security of such join protocols. To this end, we strive to
define “committee-based” joins that heavily rely on honest majority of
committees.

######  Definition A.3.

A churn-resilient JOIN protocol for a network with quorum topology is said to
be committee-based if it has the following properties.

  1. 1.

A peer $p$ joins the network by contacting another peer $q$ which in turn
informs its committee $C_{q}$ (introducing committee). $C_{q}$ initiates the
random ID generation protocol so that $p$ gets placed in a random committee
$C_{r}$ (placed committee).

  2. 2.

Honest majority in committees is required for carrying out and verifying the
steps of the JOIN protocol (as mentioned in Definition A.2).

  3. 3.

The introducing and placed committees ($C_{q}$ and $C_{r}$) are responsible
for initiating and carrying out network perturbation if it is not done via
limited lifetime method.

Our work primarily differs in random ID and placement of the joining peer. The
insight is that blockchain provides a globally known, network-generated and
unpredictable input to the hash function. If the input is globally known, then
the hash function output can be verified by any peer. If the input is
unpredictable, then the adversary cannot launch a pre-computation attack to
populate a committee. If the input is generated by a set of committees (and
not by the entire network), then that input can be corrupt if those set of
committees have a malicious majority. Such an input is hard to generate using
completely localized algorithms. The hash function is used to map the new peer
to a random committee. The new peer is then placed in that committee by a
secure bootstrapping service, constructed using the blockchain. Finally, by
making use of the limited lifetime method to perturb the network, we do not
rely on honest majority of committees for the security of join protocol.

As it is difficult to devise a single attack that works for the family of
network and join protocols, we provide attacks to the existing solutions
(primarily exploiting the reliance on honest majority). We want to show that a
small number, say, $O(\log N)$ committees that have malicious majority to
continually maintain malicious majority with low cost. Let $C_{M}$ be the
committee having malicious majority that needs to get replenished with more
malicious peers.

  1. 1.

Structured routable topologies [AS04, FSY05, AS09]. The key idea is that the
$O(\log N)$ malicious majority committees simply route new malicious peers to
$C_{M}$ with a join request. This attack is sufficient to keep adding new
malicious peers into $C_{M}$ in [AS04]. In the k-rotation paper [Sch05,
FSY05], the introducing committee selectively picks three locations to add and
shift peers. In the cuckoo rule paper [AS09], the other $O(\log N)$ malicious
majority committees pick disjoint constant-length arcs in $C_{M}$ for placing
new malicious peers so that the perturbation does not affect the newly added
peers.

  2. 2.

Expander network topology [GHK13]. Malicious committees can have edges amongst
themselves to create join requests via random walks. Committee $C_{M}$ informs
its neighbours about a new (malicious) peer. Instead of actually exchanging
all other peers in $C_{M}$, malicious peers in $C_{M}$ can reserve a small
fraction of the peers for exchanges between legitimate committees and replaces
the rest of the peers with new malicious peers, thereby maintaining a
malicious majority. More importantly, as new malicious peers get added to
$C_{M}$, the committee can get split into two committees, each with malicious
majority. (Locally splitting/merging is done to expand/shrink the network as
the network size can vary polynomially over time.)

For some specific attacks, statistical measures such as join rate, message
rate, etc., can be used in practice, to detect and mitigate the effects of
committee failures. However, not only are those measures not consistent over
time in open P2P networks but even effectively carrying out such system-wide
measurements is a hard problem. If committees are given the power of rejecting
new peers, protesting against other committees, etc., then malicious majority
committees can easily misuse such powers. Thus, recovery from arbitrary
committee failures in networks that heavily rely on honest majority in
committees, is difficult to achieve.

##  Appendix B Pseudocodes for Sub-routines

Algorithm 4 VERIFY_PROOFS protocol

0: Let $R$ be the set of messages of the form $(m,e)$ received in this round,
where $m$ is either JOINING and REQ_INFO and $e$ is the entry information of
the node that sent the message. Let $\mathbf{H}(.)$ denote the hash function.
Let $\mathbf{Blk}(i)$ be a function that returns the block from the confirmed
chain with block number $i$ if it exists, otherise, returns $\varnothing$. Let
$l$ be the block number of the most recent block in the confirmed chain.

0: Return the subset of $R$ in which each message has a valid proof.

$V\leftarrow\\{\\}$.

for each $(m,e)\in R$ do

$\mathit{blk\\_num},N_{c},\mathit{net\\_addr}\leftarrow e$.  // Retrieve
entry information.

$\mathit{blk}\leftarrow\mathbf{Blk}(\mathit{blk\\_num})$.

$P_{\mathit{join}}\leftarrow\mathbf{H}(\mathbf{H}(\mathit{blk})\mathbin{\|}\mathit{net\\_addr}\mathbin{\|}N_{c})$.

$\mathit{c}\leftarrow$ Leftmost $\lceil\log\mathcal{C}_{e}\rceil$ bits of
$P_{\mathit{join}}$.

$\mathit{valid\\_blk}\leftarrow(l-\mathit{blk\\_num})\leq\mu_{s}$ and
($\mathit{blk}$ is not $\varnothing$).

if the verification is for the directory then

$C_{n}\leftarrow$ Set of IDs of neighbouring committees of committee
$\mathit{c}$.

$C_{\mathit{rel}}\leftarrow\\{\mathit{c}\\}\bigcup C_{n}$.

$C\leftarrow$ Set of all IDs of committees that the directory node is
responsible for.

else

$C_{\mathit{rel}}\leftarrow\\{\mathit{c}\\}$.

$C\leftarrow$ Singleton set of ID of the committee that the node belongs to.

end if

if $P_{\mathit{join}}<T_{\mathit{join}}$ and $C_{\mathit{rel}}\bigcap C$ is
not $\emptyset$ and $\mathit{valid\\_blk}$ then

$V\leftarrow V\bigcup\\{(m,e)\\}$.

end if

end for

Return $V$.

Algorithm 5 STORE_INFO protocol

0: Set $V$ consisting of all the valid JOINING messages in this round. Let
$C_{i}$ be set of all the tuples of JOINING message and network address of
valid nodes (that this directory node is aware of) in committee $i$. Let
$\mathbf{H}(.)$ denote the hash function. Let $\mathbf{Blk}(i)$ be a function
that returns the block from the confirmed chain with block number $i$ if it
exists, otherwise, returns $\varnothing$.

0: Store entry information of all the nodes that provided a valid proof in
this round.

for each $(\mathtt{JOINING},e)\in V$ do

$\mathit{blk\\_num},N_{c},\mathit{net\\_addr}\leftarrow e$.  // Retrieve
entry information.

$\mathit{blk}\leftarrow\mathbf{Blk}(\mathit{blk\\_num})$.

$P_{\mathit{join}}\leftarrow\mathbf{H}(\mathbf{H}(\mathit{blk})\mathbin{\|}\mathit{net\\_addr}\mathbin{\|}N_{c})$.

$\mathit{c}\leftarrow$ Leftmost $\lceil\log\mathcal{C}_{e}\rceil$ bits of
$P_{\mathit{join}}$.

$C_{c}\leftarrow C_{c}\bigcup\\{e\\}$.

end for

Algorithm 6 REPLY_INFO protocol

0: Set $V$ consisting of all the valid REQ_INFO messages in this round. Let
$C_{i}$ be set of all the tuples of REQ_INFO message and network address of
valid nodes (that this directory node is aware of) in committee $i$.

0: Send committee entry information to nodes that provided a valid proof in
this round.

for each $(\mathtt{REQ\\_INFO},c,e)\in V$ do

SEND (COMM_INFO, $C_{c}$) to the node with network address
$\mathit{net\\_addr}$.

end for


the SVAG algorithm is an order-1 weak approximation (Definition 2.4) of the
SDE, and the approximation error scales as $1/\ell$. One may be initially
concerned that realistic deep learning settings require $1/\ell$ to be very
small, which would make $\ell$ large and hence computationally intractable.
[11] showed that the SVAG trajectories appear to converge to the SDE
trajectory for computationally tractable small values of $\ell$. We similarly
find that our proposed SVAG-like algorithms in Definition 6.2 appear to
converge for small $\ell$ in various settings.

#### CIFAR-10.

Figures 7 and 8 show that SVAG converges and closely tracks RMSprop at smaller
$\epsilon$ (=$10^{-30}$), and at larger $\epsilon$ (=$10^{-8}$) respectively.
Figures 3 and 9 show that SVAG converges and closely tracks Adam at smaller
$\epsilon$ (=$10^{-30}$), and at larger $\epsilon$ (=$10^{-8}$) respectively.
All experiments follow the setting in Section J.1 for batch size 256.

#### Wikipedia + Books (Academic BERT).

Figure 10 shows that SVAG converges and closely tracks Adam. We use the
experimental setting for batch size $1024$ in Section J.3 except the
hyperparameters $\beta_{1}$ and $\beta_{2}$ are fixed at $0.9$ and $0.98$
respectively.

#### WikiText-103 (GPT).

Figure 23 shows that SVAG converges and closely tracks Adam. We use the
experimental setting for batch size $1024$ in Section J.3 except the
hyperparameters $\beta_{1}$ and $\beta_{2}$ are fixed at $0.9$ and $0.98$
respectively. Additionally, for computational reasons, we pretrain on
sequences of length $64$.

Figure 7: SVAG experiments on ResNet-50 trained on CIFAR-10 with RMSprop. We
use batch size $256$ and the hyperparameters
$\eta=10^{-3},\beta=0.999,\epsilon=10^{-30}$ and a weight decay of $10^{-4}$.
Since SVAG takes $\ell$ smaller steps to simulate the continuous dynamics in
$\eta$ time, we plot accuracy against continuous time defined as
$k\times\eta^{2}/\ell^{2}$.

Figure 8: SVAG experiments on ResNet-50 trained on CIFAR-10 with RMSprop. We
use batch size $256$ and the hyperparameters
$\eta=10^{-3},\beta=0.999,\epsilon=10^{-8}$, and a weight decay of $10^{-4}$.
Since SVAG takes $\ell$ smaller steps to simulate the continuous dynamics in
$\eta$ time, we plot accuracy against continuous time defined as
$k\times\eta^{2}/\ell^{2}$.

Figure 9: SVAG experiments on ResNet-50 trained on CIFAR-10 with Adam. We use
batch size $256$ and the hyperparameters
$\eta=10^{-3},\beta_{1}=0.9,\beta_{2}=0.999,\epsilon=10^{-8}$, and a weight
decay of $10^{-4}$. Since SVAG takes $\ell$ smaller steps to simulate the
continuous dynamics in $\eta$ time, we plot accuracy against continuous time
defined as $k\times\eta^{2}/\ell^{2}$.

Figure 10: SVAG experiments on RoBERTa pretrained on Bookcorpus + Wikipedia
dataset with Adam. We use batch size $1024$ and the hyperparameters
$\eta=10^{-3},\beta_{1}=0.9,\beta_{2}=0.98,\epsilon=2\times 10^{-6}$. Since
SVAG takes $\ell$ smaller steps to simulate the continuous dynamics in $\eta$
time, we plot accuracy against continuous time defined as
$k\times\eta^{2}/\ell^{2}$.

Figure 11: SVAG experiments on GPT pretrained on WikiText-103 with Adam. We
use batch size $1024$ and the hyperparameters
$\eta=10^{-3},\beta_{1}=0.9,\beta_{2}=0.98,\epsilon=2\times 10^{-8}$. Since
SVAG takes $\ell$ smaller steps to simulate the continuous dynamics in $\eta$
time, we plot accuracy against continuous time defined as
$k\times\eta^{2}/\ell^{2}$. For computational constraints, we train on
sequences of length $64$.

##  Appendix I Square Root Scaling Experiments

We experimentally evaluate the scaling rules proposed in Definitions 5.2 and
5.1 by training models with different batch sizes and modifying the
optimization hyperparameters accordingly. The number of gradient steps were
modified to keep the total amount of continuous time same across all the
batches. The warmup schedule and the learning rate decay schedule were kept
the same. See Appendix J for details about the baseline runs for each dataset.

We perform two types of ablation studies. In Section I.1, we compare our
proposed scaling rule to variants that only scale some subset of the
optimization hyperparameters. We find that our proposed scaling rule is the
best at preserving the validation accuracy and the other test functions across
different batch sizes. In Section I.2, we compare the proposed square root
scaling rule to a linear one and find that they perform comparably on
CIFAR-10, though the square root scaling significantly outperforms linear
scaling on the ImageNet dataset. We hypothesize that for simpler datasets,
like CIFAR-10, the differences between the two scaling rules is not reflected
clearly in the validation accuracies because the task is too easy to learn.

#### CIFAR-10.

Figures 14 and 12 show the performance of VGG-16 when trained with different
batch sizes with RMSprop at smaller $\epsilon$ (=$10^{-30}$), and at larger
$\epsilon$ (=$10^{-8}$) respectively. Figures 15 and 13 show the performance
of VGG-16 when trained with different batch sizes with Adam at smaller
$\epsilon$ (=$10^{-30}$), and at larger $\epsilon$ (=$10^{-8}$) respectively.
For the corresponding experiments on ResNet-50, please refer to Figures 16,
18, 17 and 19. For the details on the experimental setting, please refer to
Section J.1.

We observe that in all settings the test accuracies vary by at most $3\%$
across batch sizes when using the proposed square root scaling rule. Moreover,
the test functions stay close across multiple batch sizes, signifying that the
trajectories stay close across the batch sizes using the Square root scaling
rule.

#### ImageNet.

Figures 21 and 20 show the performance of ResNet-50 when trained with
different batch sizes with RMSprop at smaller $\epsilon$ (=$10^{-30}$), and at
larger $\epsilon$ (=$10^{-8}$) respectively. For the details on the
experimental setting, please refer to Section J.2.

We observe that on the validation set, the loss and accuracy behavior for the
model is very similar, when trained with different batch sizes. Moreover, the
difference between the validation accuracies is atmost $3\%$ between the batch
sizes $256$, $1024$, $4096$, and $16384$ for smaller $\epsilon$. The
difference between the validation accuracies is atmost $1.5\%$ between the
batch sizes $256$, $1024$, $4096$, $16384$, and $32768$ for larger $\epsilon$.

#### Wikipedia + Books (Academic BERT).

Figure 22 shows the performance of a RoBERTa model when pretrained with
different batch sizes with ADAM. The scaling rule is applied to modify the
peak values of the optimization hyperparameters. We also evaluate the
pretrained models on several downstream tasks, and show the results in Table
1. For the details on the setting for both pretraining and downstream
experiments, please refer to Section J.3.

We observe that the log perplexity on the training and validation datasets
matches across different batch sizes throughout pretraining. Moreover, we also
observe that the gradient norms across different batch sizes remain close
throughout the pretraining. Furthermore, the models pretrained across
different batch sizes can achieve very similar performance in the downstream
tasks.

#### WikiText-103 (Academic GPT).

Figure 23 shows the log perplexity behavior of GPT on training and validation
datasets, across different batch sizes of pretraining . We observe that the
log perplexity matches across different batch sizes. Moreover, we also observe
that the gradient norms across different batch sizes remain close throughout
the training.

Figure 12: VGG-16 trained on CIFAR-10 using RMSprop are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for RMSprop (Definition 5.2). We use a baseline setting
of $\eta=10^{-3}$, $\epsilon=10^{-8}$, and $(\beta_{1},\beta_{2})=(0.0,0.999)$
for batch size $256$. We use a weight decay factor of $10^{-4}$. We observe a
gap of at most $3\%$ among the different batch sizes under consideration.

Figure 13: VGG-16 trained on CIFAR-10 using Adam are close for different batch
sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for Adam (Definition 5.2). We use a baseline setting of
$\eta=10^{-3}$, $\epsilon=10^{-8}$, and $(\beta_{1},\beta_{2})=(0.999,0.999)$
for batch size $256$. We use a weight decay factor of $10^{-4}$. We observe a
gap of at most $3\%$ among the different batch sizes under consideration.

Figure 14: VGG-16 trained on CIFAR-10 using RMSprop are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for RMSprop (Definition 5.2). We use a baseline setting
of $\eta=10^{-3}$, $\epsilon=10^{-30}$, and
$(\beta_{1},\beta_{2})=(0.0,0.999)$ for batch size $256$. We use a weight
decay factor of $10^{-4}$. We observe a gap of at most $3\%$ among the
different batch sizes under consideration.

Figure 15: VGG-16 trained on CIFAR-10 using Adam are close for different batch
sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for Adam (Definition 5.2). We use a baseline setting of
$\eta=10^{-3}$, $\epsilon=10^{-30}$, and $(\beta_{1},\beta_{2})=(0.999,0.999)$
for batch size $256$. We use a weight decay factor of $10^{-4}$. We observe a
gap of at most $3\%$ among the different batch sizes under consideration.

Figure 16: ResNet-50 trained on CIFAR-10 using RMSprop are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for RMSprop (Definition 5.2). We use a baseline setting
of $\eta=10^{-3}$, $\epsilon=10^{-8}$, and $(\beta_{1},\beta_{2})=(0.0,0.999)$
for batch size $256$. $\epsilon=10^{-30}\approx 0$ for all experiments. We use
a weight decay factor of $10^{-4}$. We observe a gap of at most $3\%$ among
the different batch sizes under consideration.

Figure 17: ResNet-50 trained on CIFAR-10 using Adam are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for Adam (Definition 5.2). We use a baseline setting of
$\eta=10^{-3}$ and $(\beta_{1},\beta_{2})=(0.999,0.999)$ for batch size $256$.
$\epsilon=10^{-30}\approx 0$ for all experiments. We use a weight decay factor
of $10^{-4}$. We observe a gap of at most $3\%$ among the different batch
sizes under consideration.

Figure 18: ResNet-50 trained on CIFAR-10 using RMSprop are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for RMSprop (Definition 5.2). We use a baseline setting
of $\eta=10^{-3}$, $\epsilon=10^{-8}$, and $(\beta_{1},\beta_{2})=(0.0,0.999)$
for batch size $256$. We use a weight decay factor of $10^{-4}$. We observe a
gap of at most $3\%$ among the different batch sizes under consideration.

Figure 19: ResNet-50 trained on CIFAR-10 using Adam are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for Adam (Definition 5.2). We use a baseline setting of
$\eta=10^{-3}$, $\epsilon=10^{-8}$, and $(\beta_{1},\beta_{2})=(0.999,0.999)$
for batch size $256$. We use a weight decay factor of $10^{-4}$. We observe a
gap of at most $3\%$ among the different batch sizes under consideration.

Figure 20: ResNet-50 trained on ImageNet using Adam are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for Adam (Definition 5.2). We use a baseline setting of
$\eta=3\times 10^{-4}$, $\epsilon=10^{-8}$, and
$(\beta_{1},\beta_{2})=(0.999,0.999)$ for batch size $256$. We use a weight
decay factor of $10^{-4}$. We achieve around $74\%$ validation accuracy with
batch size $256$ and the accuracy drops by at most $1.5\%$ at batch size
$32768$.

Figure 21: ResNet-50 trained on ImageNet using Adam are close for different
batch sizes when the optimization hyperparameters are varied according to the
proposed scaling rule for Adam (Definition 5.2). We use a baseline setting of
$\eta=3\times 10^{-4}$ and $(\beta_{1},\beta_{2})=(0.999,0.999)$ for batch
size $256$. $\epsilon=10^{-30}\approx 0$ for all experiments. We use a weight
decay factor of $10^{-4}$. We achieve around $74\%$ validation accuracy with
batch size $1024$ and the accuracy drops by at most $3\%$ at batch size
$16384$.

Figure 22: The train and validation log perplexities of RoBERTa-large trained on the Wiki+Books corpus using Adam (for $48$ hours) are close for moderate batch sizes using the Square Root Scaling Rule on Adam. $\eta=10^{-3}$ and $(\beta_{1},\beta_{2})=(0.99375,0.996)$ for batch size $1024$, $\epsilon=2\times 10^{-6}$ for batch size $1024$ and scaled likewise for other batch sizes. We achieve a validation log perplexity of $2.1\pm 0.1$ for batch size $1024$, $2048$, $4096$ and $8192$. Training with batch size $256$ is computationally inefficient, but follows the same behavior during its 48-hour trajectory. Pretrain batch size $B$ | CoLA | SST-2 | MRPC | STS-B | QQP | MNLI | QNLI | RTE
---|---|---|---|---|---|---|---|---
$1024$ | $0.585$ | $0.92$ | $0.73$ | $0.866$ | $0.873$ | $0.836$ | $0.906$ | $0.682$
$2048$ | $0.563$ | $0.928$ | $0.803$ | $0.869$ | $0.875$ | $0.826$ | $0.897$ | $0.653$
$4096$ | $0.581$ | $0.921$ | $0.778$ | $0.869$ | $0.875$ | $0.839$ | $0.892$ | $0.675$
$8192$ | $0.626$ | $0.929$ | $0.778$ | $0.884$ | $0.877$ | - | $0.9$ | $0.675$
Table 1: Performance of the pretrained RoBERTa models when finetuned on
different downstream tasks in GLUE [40]. F1 scores are reported for QQP and
MRPC, Spearman correlations are reported for STS-B, Matthews correlations for
CoLA, and accuracy scores are reported for the other tasks. Here, $B$ denotes
the batch size used for pretraining. We run an extensive grid search (Table 4)
to find the best performance of each pretrained model on each of the
downstream tasks.

Figure 23: The train and validation perplexities of 12 layer GPT trained on
the Wikitext corpus using Adam (for $48$ hours) are close for moderate batch
sizes Square Root Scaling Rule on Adam on RoBERTa-large. $\eta=10^{-3}$ and
$(\beta_{1},\beta_{2})=(0.9875,0.996)$ for batch size $1024$,
$\epsilon=2\times 10^{-8}$ for batch size $1024$ and scaled likewise for other
batch sizes. We achieve a validation log perplexity of $5\pm 0.1$ for all the
batch sizes under consideration. Moreover, we observe an alignment in the
behavior of the trajectories across the different batch sizes (except $8192$
in the first half of the training).

###  I.1 Ablation study on the proposed scaling rule

#### CIFAR-10.

We conduct an ablation study on whether all the parameters
$\eta,\epsilon,\beta_{1},\beta_{2}$ need to be scaled in our proposed scaling
rule. To do so, we compare the performance of a ResNet-50 model trained with
batch size $256$ and hypeparameters
($\epsilon=10^{-8},\beta_{1}=0.999,\beta_{2}=0.999$) with the performance at a
larger batch size, across $5$ runs representing $5$ different scaling rules:
(a) Scale $\eta$, keeping others fixed, (b) Scale $\eta,\epsilon$, keeping
others fixed, (c) Scale $\eta,\epsilon,\beta_{1}$, keeping others fixed, (d)
Scale $\eta,\epsilon,\beta_{2}$, keeping others fixed, and (e) Scale
$\eta,\epsilon,\beta_{1},\beta_{2}$. Please check the behaviors of the
different scaling rules at batch size $2048$, $4096$, $8192$ and $16384$ in
Figure 24. We found that (e) consistently beats others in terms of the test
functions and the validation accuracies at all batch sizes. The closest
scaling rule (c) involved scaling only $\eta,\epsilon,\mbox{ and }\beta_{1}$
while keeping $\beta_{2}$ fixed.

###  I.2 Ablation against linear scaling rules

#### CIFAR-10.

We compared the proposed scaling rule against possible linear scaling rules,
that scale the hyperparameters linearly with the increase in training batch
size. We focused on ResNet-50 training with Adam. The linear scaling rules
that we tried were: (a) Scale $\eta$ linearly, keeping
$\beta_{1},\beta_{2},\epsilon$ fixed, (b) Scale $\eta,1-\beta_{1}$ linearly,
keeping $\beta_{2},\epsilon$ fixed, (c) Scale $\eta,1-\beta_{2}$ linearly,
keeping $\beta_{1},\epsilon$ fixed, and (d) Scale
$\eta,1-\beta_{1},1-\beta_{2}$ linearly, keeping $\epsilon$ fixed. Fig. 25
shows the behavior of these scaling rules at batch size $8192$ and $16384$, at
different values of $\epsilon$.

The linear scaling rule in (d) seems to perform as well as the proposed Square
Root scaling rule (Definition 5.2) in terms of validation accuracies. However,
with a closer look on the train accuracy plots, we observe that the Square
Root scaling rule tracks the smaller batch training trajectory better than the
linear scaling rule. The linear scaling rules seem to catch up, only after the
learning rate is decayed. Our hypothesis is that the CIFAR-10 dataset is
simple enough for different scaling rules to work well.

#### ImageNet.

We conduct ablation experiments on ResNet-50, trained with Adam on ImageNet,
where we follow a linear scaling rule to scale the hyperparameters across
batch sizes. Due to computational issues, we didn’t conduct extensive
experiments, as was done for CIFAR-10. The linear scaling rule for Adam is as
follows: the hyperparameters $\eta$, $1-\beta_{1}$ and $1-\beta_{2}$ are
scaled by $\kappa$, when the batch size is scaled by $\kappa$, and $\epsilon$
isn’t scaled. As was noted earlier, the definition of continuous time will
change to $\eta\times\\#\\{\text{gradient steps}\\}$. We keep the number of
training epochs equal to $90$ as before, follow the same learning rate
schedule, and show the performance of the models in Figure 26. We observe that
scaling the hyperparameters to larger batch training with the proposed LSR
results in a big drop in validation accuracies.

Figure 24: Ablation study for the square root scaling rule on Resnet-50
trained with Adam on CIFAR-10. We compare the performance of a model trained
with batch size $256$ and hypeparameters
($\epsilon=10^{-8},\beta_{1}=0.999,\beta_{2}=0.999$) with the performance at a
larger batch size, across $5$ runs representing $5$ variations of the square
root scaling rule: (a) Scale $\eta$, keeping others fixed, (b) Scale
$\eta,\epsilon$, keeping others fixed, (c) Scale $\eta,\epsilon,\beta_{1}$,
keeping others fixed, (d) Scale $\eta,\epsilon,\beta_{2}$, keeping others
fixed, and (e) Scale $\eta,\epsilon,\beta_{1},\beta_{2}$. We use a weight
decay of $10^{-4}$ in all the experiments. We observe that scaling all the
hyperparameters consistently gives better performance at higher batch size.
Scaling rule (c) is close second.

(a) $B=2048$
(b) $B=4096$
(c) $B=8192$
(d) $B=16384$

Figure 25: Ablation study against (possible) linear scaling rules on Resnet-50
trained with Adam on CIFAR-10. We compare the performance of a model trained
with batch size $256$ and hypeparameters
($\epsilon=10^{-8}/10^{-30},\beta_{1}=0.999,\beta_{2}=0.999$) with the
performance at a larger batch size, across $5$ runs representing $5$ possible
linear scaling rules: (a) Scale $\eta$ linearly, keeping
$\beta_{1},\beta_{2},\epsilon$ fixed, (b) Scale $\eta,1-\beta_{1}$ linearly,
keeping $\beta_{2},\epsilon$ fixed, (c) Scale $\eta,1-\beta_{2}$ linearly,
keeping $\beta_{1},\epsilon$ fixed, and (d) Scale
$\eta,1-\beta_{1},1-\beta_{2}$ linearly, keeping $\epsilon$ fixed. We use a
weight decay of $10^{-4}$ in all the experiments. We also compare the behavior
of the linear scaling rules against the square root scaling rule. Since the
continuous time definition varies across the scaling rules, we plot against
the number of epochs trained. A closer look at the training accuracy plots
shows that the square root scaling rule tracks the smaller batch training
trajectory better than the linear scaling rule.

(a) $B=8192$, $\epsilon$ of order $10^{-30}$
(b) $B=16384$, $\epsilon$ of order $10^{-30}$
(c) $B=8192$, $\epsilon$ of order $10^{-8}$
(d) $B=16384$, $\epsilon$ of order $10^{-8}$

Figure 26: Ablation study against a (possible) linear scaling rule on
Resnet-50 trained with Adam on Imagenet. We compare the performance of a model
trained with batch size $256$ and hypeparameters ($\eta=3\times 10^{-4}$,
$\epsilon=10^{-8}$, and $(\beta_{1},\beta_{2})=(0.999,0.999)$) with the
performance at a larger batch size, when the hyperparameters are scaled as
follows: scale $\eta,1-\beta_{1},1-\beta_{2}$ by $\kappa$, if the batch size
is scaled by $\kappa$, keeping $\epsilon$ fixed. We use a weight decay factor
of $10^{-4}$. We clearly observe a decrease in performance at larger batch
size, in comparison to models trained with square root scaling rule (see
Figure 20).

##  Appendix J Experiment Configuration Details

###  J.1 CIFAR-10

There are $50000$ images in the training set and $10000$ images in the
validation set of CIFAR-10 [22].

#### Architecture.

We used the architecture of ResNet-56 from [41] without modification. We used
the same architecture of VGG-16 with batch normalization from [21]. However,
we kept the final layer of the architecture fixed throughout training, to make
the model $1$-homogenous and avoid the optimization difficulties of
$2$-homogenous networks ([42]).

#### RMSprop.

To fix a baseline to compare against, we first trained the models with batches
of size $256$, sampled with replacement, at peak learning rate $\eta=10^{-3}$
and $\beta=0.999$. The model was trained for
$500\times\lfloor(50000/256)\rfloor=97500$ gradient steps (or $500$ epochs).
We followed an initial warmup for the first $2\%$ of the total gradient steps.
The learning rate schedule during the warmup phase is given by $\eta\times
10^{-3}\times(10^{3})^{\\#\text{ epochs }/10}$. We also followed a learning
rate decay schedule, the learning rate was decayed by $0.1$ when the model
reaches $80\%$ ($400$ epoch) and $90\%$ ($450$ epoch) of the total continuous
time respectively. We did experiments at two values of $\epsilon$, small
($=1e-30$) and large ($=1e-8$).

We then made multiple runs of the same model with batches of varying sizes in
$\\{1024,4096,16384\\}$, with the hyperparameters $\eta$, $\epsilon$ and
$\beta$ modified appropriately according to the scaling rule. The number of
gradient steps were modified to keep the total amount of continuous time same
across all the batches (which amounted to $500$ epochs by the equivalence
between continuous time and the number of training epochs). The warmup
schedule and the learning rate decay schedule were kept the same.

#### Adam.

We first trained the models with batches of size $256$, sampled with
replacement, at peak learning rate $\eta=10^{-3}$ and
$(\beta_{1},\beta_{2})=(0.999,0.999)$. The total continuous time of training
(or number of epochs), the amount of continuous time in the warmup phase, and
the learning rate schedule in the warmup phase were same as RMSprop. The only
difference was the learning rate schedule after the warmup phase, the learning
rate was decayed by $0.1$ when the model reaches $60\%$ of the total
continuous time (or 300 epochs).

We then made multiple runs of the same model with batches of varying sizes in
$\\{1024,4096,16384\\}$, with the hyperparameters $\eta$, $\epsilon$ and
$\beta_{1},\beta_{2}$ modified appropriately according to the scaling rule.
The number of gradient steps were modified to keep the total amount of
continuous time same across all the batches. The warmup schedule and the
learning rate decay schedule were kept the same.

###  J.2 ImageNet

There are $1281167$ images in the training set and $50000$ images in the
validation set of ImageNet [27].

#### Architecture.

We trained a ResNet-50 [41] model without modification.

#### Adam.

To fix a baseline to compare against, we first trained the models with batches
of size $256$, sampled with replacement, at learning rate $\eta=3\times
10^{-4}$ and $\beta=0.999$. The model was trained for a total of
$90\times\lfloor(1281167/256)\rfloor=450360$ gradient steps (or $90$ epochs).
We followed an initial warmup for the first $\frac{1}{18}$ fraction of the
total continuous time (or the first $5$ epochs). The learning rate schedule
during the warmup phase is increased linearly with epoch, i.e. the learning
rate is given by $\eta\times 10^{-3}\times(10^{3})^{\\#\text{ epochs }/5}$. We
then followed a learning rate decay schedule, where the learning rate was
decayed by $0.1$ when the model reaches $\frac{5}{18}$ fraction (or $50$ epoch
) and $\frac{8}{9}$ fraction (or $80$ epoch) of the total continuous time
respectively. We use two different values for $\epsilon$, small $\epsilon$
($=1e-30\approx 0$) and a larger $\epsilon$ ($=1e-8$).

###  J.3 Books and Wikipedia (Academic BERT)

We use a combination of Bookcorpus [24] plus English Wikipedia, which totals
$16$ GB of uncompressed text. We split the data uniformly with a ratio $9:1$,
to create training and validation datasets for pretraining.

#### Architecture.

We pretrain a $24$-layer RoBERTa [23] model. We pretrain on sequences of
length $128$.

#### Pre-training with Adam.

We use the code from [43]. We follow the optimization recipe from [28] for
efficient pre-training. To fix a baseline, we first trained our model with
batch size $1024$, with the optimization parameters given in table 2. In the
warmup phase, the learning rate is increased linearly over the interval, i.e.
the learning rate at step $k$ in the warmup phase is given by
$\frac{k}{k_{\mathrm{warmup}}}\eta$, where $k_{\mathrm{warmup}}$ denotes the
total number of warmup steps and $\eta$ denotes the peak learning rate.
Moreover, after the warmup phase, the learning rate is decayed linearly to
$0$, i.e. the learning rate at step $k$ after the warmup phase is given by
$\frac{k-k_{\mathrm{warmup}}}{k_{\mathrm{max}}-k_{\mathrm{warmup}}}\eta$,
where $\eta$ denotes the peak learning rate and $k_{\mathrm{max}}$ denotes the
maximum number of gradient steps intended for pretraining.

Hyperparameter | Value
---|---
Dropout | $0.1$
Attention Dropout | $0.1$
Warmup Steps | $5520$
Peak Learning Rate | $10^{-3}$
Batch Size | $1024$
Weight Decay | $10^{-4}$
Max Steps | $92000$
Learning Rate Decay | Linear
Adam $\beta_{1}$ | $0.99375$
Adam $\beta_{2}$ | $0.996$
Adam $\epsilon$ | $2\times 10^{-6}$
Gradient Clipping | $0.0$
Position embeddings | $128$
Table 2: Optimization hyperparameters of baseline RoBERTa model during
pretraining.

Fine-tuning with Adam: We also validate the performance of the pretrained
models from the previous section on the GLUE[40] datasets. For each downstream
task, we run an extensive grid search on the hyperparameters for finetuning
each pretrained model. We focused on the following hyperparameters for grid
search: batch size, the peak learning rate and the total number of training
epochs. Please see Table 4 for the hyperparameter grid. The rest of the
hyperparameters are fixed for all the runs and are given in Table 3. We follow
a similar learning rate schedule during the warmup phase as was used for
pretraining: the learning rate at step $k$ in the warmup phase is given by
$\frac{k}{k_{\mathrm{warmup}}}\eta$, where $k_{\mathrm{warmup}}$ denotes the
total number of warmup steps and $\eta$ denotes the peak learning rate.
Moreover, after the warmup phase, the learning rate is decayed linearly to
$0$, i.e. the learning rate at step $k$ after the warmup phase is given by
$\frac{k-k_{\mathrm{warmup}}}{k_{\mathrm{max}}-k_{\mathrm{warmup}}}\eta$,
where $\eta$ denotes the peak learning rate and $k_{\mathrm{max}}$ denotes the
maximum number of gradient steps intended for finetuning.

Hyperparameter | Value
---|---
Dropout | $0.1$
Attention Dropout | $0.1$
Warmup Steps |  $6\%$ of total
Weight Decay | $0.1$
Learning Rate Decay | Linear
Adam $\beta_{1}$ | $0.9$
Adam $\beta_{2}$ | $0.98$
Adam $\epsilon$ | $10^{-6}$
Gradient Clipping | $0.0$
Table 3: Optimization hyperparameters of all pretrained RoBERTa models during finetuning. Dataset | Finetune batch size | Peak Learning rate | Total training epochs
---|---|---|---
CoLA | $\\{16,32\\}$ | $\\{10^{-5},3\times 10^{-5},5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5,10\\}$
SST-2 | $\\{16,32\\}$ | $\\{10^{-5},3\times 10^{-5},5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5,10\\}$
MRPC | $\\{16,32\\}$ | $\\{10^{-5},3\times 10^{-5},5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5,10\\}$
STS-B | $\\{16,32\\}$ | $\\{10^{-5},3\times 10^{-5},5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5,10\\}$
RTE | $\\{16,32\\}$ | $\\{10^{-5},3\times 10^{-5},5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5,10\\}$
QQP | $\\{32\\}$ | $\\{5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5\\}$
MNLI | $\\{32\\}$ | $\\{5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5\\}$
QNLI | $\\{32\\}$ | $\\{5\times 10^{-5},8\times 10^{-5}\\}$ | $\\{3,5\\}$
Table 4: Hyperparameter grid for pretrained RoBERTa on the downstream tasks.

###  J.4 WikiText-103 (GPT)

WikiText-103 [26] is a dataset with 103 million tokens extracted from
Wikipedia. We split the data uniformly with a ratio $9:1$, to create training
and validation datasets for pretraining. We use Adam [6] optimization
algorithm.

#### Architecture.

We pretrain a $12$-layer GPT [25] model without modification. The model has
$12$ layers with hidden dimension $768$, feedforward network dimension $3072$,
$12$ attention heads in each attention layer, and attention head size $64$. We
pretrain on sequences of length $128$ (unless stated otherwise).

#### Adam.

We use the code from [43]. To fix a baseline, we first trained our model with
batch size $1024$, with the optimization parameters given in Table 5. In the
warmup phase, the learning rate is increased linearly over the interval, i.e.
the learning rate at step $k$ in the warmup phase is given by
$\frac{k}{k_{\mathrm{warmup}}}\eta$, where $k_{\mathrm{warmup}}$ denotes the
total number of warmup steps and $\eta$ denotes the peak learning rate.
Moreover, after the warmup phase, the learning rate is decayed linearly to
$0$, i.e. the learning rate at step $k$ after the warmup phase is given by
$\frac{k-k_{\mathrm{warmup}}}{k_{\mathrm{max}}-k_{\mathrm{warmup}}}\eta$,
where $\eta$ denotes the peak learning rate and $k_{\mathrm{max}}$ denotes the
maximum number of gradient steps intended for pretraining.

Hyperparameter | Value
---|---
Dropout | $0.1$
Attention Dropout | $0.1$
Warmup Steps | $1000$
Peak Learning Rate | $10^{-3}$
Batch Size | $1024$
Weight Decay | $10^{-4}$
Max Steps | $12500$
Learning Rate Decay | Linear
Adam $\beta_{1}$ | $0.9875$
Adam $\beta_{2}$ | $0.996$
Adam $\epsilon$ | $2\times 10^{-8}$
Gradient Clipping | $0.0$
Position embeddings | $128$
Table 5: Optimization hyperparameters of baseline GPT model during
pretraining.