is weighted by the proportion of units who receive the treatment at time $t$:
$\pi_{t}=\sum_{i=1}^{n}\mathbf{1}\\{A_{i}=t\\}/\sum_{i=1}^{n}\mathbf{1}\\{A_{i}\in\mathcal{T}\\}$.

Here, we provide a generalization of the parallel trends assumption, which
incorporates both the standard parallel trends assumption and the parallel
trends-in-trends assumption.

######  Assumption A2 ($k$-th Order Parallel Trends for Staggered Adoption
Design).

For some integer $k$ such that $1\leq k\leq T,$ and for $k\leq t\leq T-s,$

$\Delta_{s}^{k}\left(\mathbb{E}[Y_{i,t+s}(0)\mid
G_{its}=1]\right)=\Delta_{s}^{k}\left(\mathbb{E}[Y_{i,t+s}(0)\mid
G_{its}=0]\right),$

where $\Delta_{s}^{k}$ is the $k$-th order difference operator defined in
Assumption A1.

Under Assumption A2, the SA-ATT at post-treatment time $t+s$ is identified as
follows.

$\tau^{\textsf{SA}}(s,t)=\Delta_{s}^{k}\left(\mathbb{E}[Y_{i,t+s}\mid
G_{its}=1]\right)-\Delta_{s}^{k}\left(\mathbb{E}[Y_{i,t+s}\mid
G_{its}=0]\right).$

Since conditional expectations can be consistently estimated via the sample
analogue,

$\widehat{\tau}^{\textsf{SA}}_{k}(s,t)=\Delta_{s}^{k}\left(\frac{\sum_{i\colon
G_{its}=1}Y_{i,t+s}}{n_{1,t+s}}\right)-\Delta_{s}^{k}\left(\frac{\sum_{i\colon
G_{its}=0}Y_{i,t+s}}{n_{0,t+s}}\right)$

is a consistent estimator for the SA-ATT at post-treatment time $t+s$ under
Assumption A2.

In general, we combine $K$ DID estimators to obtain the generalized $K$-DID
for the SA-ATT at post-treatment time $t+s$ as follows.

$\widehat{\tau}^{\textsf{SA}}(s,t)=\operatornamewithlimits{argmin}_{\tau^{\textsf{SA}}}\bm{g}(\tau^{\textsf{SA}})^{\top}\widehat{\mathbf{W}}\bm{g}(\tau^{\textsf{SA}})$

where
$\bm{g}(\tau^{\textsf{SA}})=(\tau^{\textsf{SA}}-\widehat{\tau}^{\textsf{SA}}_{1}(s),\ldots,\tau^{\textsf{SA}}-\widehat{\tau}^{\textsf{SA}}_{K}(s))^{\top}$.
The optimal weight matrix is $\widehat{\mathbf{W}}={\rm
Var}(\widehat{\tau}^{\textsf{SA}}_{(1:K)}(s))^{-1}$ where
$\widehat{\tau}^{\textsf{SA}}_{(1:K)}(s)=(\widehat{\tau}^{\textsf{SA}}_{1}(s),\ldots,\widehat{\tau}^{\textsf{SA}}_{K}(s))^{\top}.$

To estimate the time-average SA-ATT, we first define the time-average $k$-th
order time-average DID estimator as,

$\widehat{\overline{\tau}}^{\textsf{SA}}_{k}(s)=\sum_{t\in\mathcal{T}}\pi_{t}\widehat{\tau}^{\textsf{SA}}_{k}(s,t).$

Finally, the generalized $K$-DID combines $K$ moment conditions as follows.

$\widehat{\overline{\tau}}^{\textsf{SA}}(s)=\operatornamewithlimits{argmin}_{\overline{\tau}^{\textsf{SA}}}\bm{g}(\overline{\tau}^{\textsf{SA}})^{\top}\widehat{\mathbf{\overline{W}}}\bm{g}(\overline{\tau}^{\textsf{SA}})$

where
$\bm{g}(\overline{\tau}^{\textsf{SA}})=(\overline{\tau}^{\textsf{SA}}-\widehat{\overline{\tau}}^{\textsf{SA}}_{1}(s),\ldots,\overline{\tau}^{\textsf{SA}}-\widehat{\overline{\tau}}^{\textsf{SA}}_{K}(s))^{\top}$.
The optimal weight matrix is $\widehat{\mathbf{\overline{W}}}={\rm
Var}(\widehat{\overline{\tau}}^{\textsf{SA}}_{(1:K)}(s))^{-1}$ where
$\widehat{\overline{\tau}}^{\textsf{SA}}_{(1:K)}(s)=(\widehat{\overline{\tau}}^{\textsf{SA}}_{1}(s),\ldots,\widehat{\overline{\tau}}^{\textsf{SA}}_{K}(s))^{\top}.$

###  E.4 Double DID Regression for Staggered Adoption Design

We now extend the double DID regression to the SA design setting. We first
extend the standard DID regression (Appendix E.1) to the SA design. In
particular, to estimate the SA-ATT at time $t$, we can fit the following
regression for units who are not yet treated at time $t-1$, that is,
$\\{i:G_{it}\geq 0\\}$.

$Y_{iv}\sim\alpha+\theta G_{it}+\gamma
I_{v}+\beta^{\textsf{SA}}(t)(G_{it}\times
I_{v})+\mathbf{X}_{iv}^{\top}\bm{\rho},$

where $v\in\\{t-1,t\\}$ and the time indicator $I_{v}$ (equal to $1$ if $v=t$
and $0$ if $v=t-1$). Note that $G_{it}$ defines the treatment and control
group at time $t$, and thus, it does not depend on time index $v$. The
estimated coefficient $\widehat{\beta}^{\textsf{SA}}(t)$ is consistent for the
SA-ATT under the conditional parallel trends assumption.

Similarly, we can extend the sequential DID regression to the SA design. Using
the connection to the linear regression of equation (A.3), we can adjust for
additional pre-treatment covariates as:

$\Delta
Y_{iv}\sim\alpha_{s}+\theta_{s}G_{it}+\gamma_{s}I_{v}+\beta^{\textsf{SA}}_{s}(t)(G_{it}\times
I_{v})+\mathbf{X}_{iv}^{\top}\bm{\rho}_{s},$

where $v\in\\{t-1,t\\}$ and $\Delta Y_{iv}=Y_{iv}-(\sum_{i\colon
G_{it}=1}Y_{i,v-1})/n_{1,v-1}$ if $G_{it}=1$ and $\Delta
Y_{iv}=Y_{iv}-(\sum_{i\colon G_{it}=0}Y_{i,v-1})/n_{0,v-1}$ if $G_{it}=0$. The
estimated coefficient $\widehat{\beta}^{\textsf{SA}}_{s}(t)$ is consistent for
the SA-ATT under the conditional parallel trends-in-trends assumption.

Therefore, the double DID regression for the SA design combines the two
regression estimators via the GMM:

$\widehat{\beta}^{\textsf{SA}}_{\texttt{d-DID}}(t)=\operatornamewithlimits{argmin}_{\beta^{\textsf{SA}}_{d}(t)}\begin{pmatrix}\beta^{\textsf{SA}}_{d}(t)-\widehat{\beta}^{\textsf{SA}}(t)\\\\[-5.0pt]
\beta^{\textsf{SA}}_{d}(t)-\widehat{\beta}^{\textsf{SA}}_{s}(t)\end{pmatrix}^{\top}\mathbf{W}(t)\begin{pmatrix}\beta^{\textsf{SA}}_{d}(t)-\widehat{\beta}^{\textsf{SA}}(t)\\\\[-5.0pt]
\beta^{\textsf{SA}}_{d}(t)-\widehat{\beta}^{\textsf{SA}}_{s}(t).\end{pmatrix}$

where the choice of the weight matrix follows the same two-step procedure as
Section 4.2. We also provide further details in Appendix E.3. The optimal
weight matrix $\mathbf{W}(t)$ is equal to ${\rm
Var}(\widehat{\beta}^{\textsf{SA}}_{(1:2)}(t))^{-1}$ where
$\widehat{\beta}^{\textsf{SA}}_{(1:2)}(t)=(\widehat{\beta}^{\textsf{SA}}(t),\widehat{\beta}^{\textsf{SA}}_{s}(t))^{\top}.$

To estimate the time-average SA-ATT, we extend the double DID regression as
follows.

$\widehat{\overline{\beta}}^{\textsf{SA}}_{\texttt{d-DID}}=\operatornamewithlimits{argmin}_{\overline{\beta}^{\textsf{SA}}_{d}}\begin{pmatrix}\overline{\beta}^{\textsf{SA}}_{d}-\widehat{\overline{\beta}}^{\textsf{SA}}\\\\[-5.0pt]
\overline{\beta}^{\textsf{SA}}_{d}-\widehat{\overline{\beta}}^{\textsf{SA}}_{s}\end{pmatrix}^{\top}\overline{\mathbf{W}}\begin{pmatrix}\overline{\beta}^{\textsf{SA}}_{d}-\widehat{\overline{\beta}}^{\textsf{SA}}\\\\[-5.0pt]
\overline{\beta}^{\textsf{SA}}_{d}-\widehat{\overline{\beta}}^{\textsf{SA}}_{s}\end{pmatrix}$

where

$\widehat{\overline{\beta}}^{\textsf{SA}}=\sum_{t\in\mathcal{T}}\pi_{t}\widehat{\beta}^{\textsf{SA}}(t),\hskip
14.45377pt\mbox{and}\hskip
14.45377pt\widehat{\overline{\beta}}^{\textsf{SA}}_{s}=\sum_{t\in\mathcal{T}}\pi_{t}\widehat{\beta}^{\textsf{SA}}_{s}(t).$

The optimal weight matrix $\overline{\mathbf{W}}$ is equal to ${\rm
Var}(\widehat{\overline{\beta}}^{\textsf{SA}}_{(1:2)})^{-1}$ where
$\widehat{\overline{\beta}}^{\textsf{SA}}_{(1:2)}=(\widehat{\overline{\beta}}^{\textsf{SA}},\widehat{\overline{\beta}}^{\textsf{SA}}_{s})^{\top}.$

##  Appendix F Equivalence Approach

Here, we provide technical details on the equivalence approach we introduced
in Section 3.1. In the standard hypothesis testing, researchers usually
evaluate the two-sided null hypothesis $H_{0}:\delta=0$ where
$\delta=\\{\mathbb{E}[Y_{i1}(0)\mid G_{i}=1]-\mathbb{E}[Y_{i0}(0)\mid
G_{i}=1]\\}-\\{\mathbb{E}[Y_{i1}(0)\mid G_{i}=0]-\mathbb{E}[Y_{i0}(0)\mid
G_{i}=0]\\}$ when we are conducting the pre-treament-trends test. However,
this approach has a risk of conflating evidence for parallel trends and
statistical inefficiency. For example, when sample size is small, even if pre-
treatment trends of the treatment and control groups differ (i.e., the null
hypothesis is false), a test of the difference might not be statistically
significant due to large standard error. And, analysts might “pass” the pre-
treatment-trends test by not finding enough evidence for the difference.

The equivalence approach can mitigate this concern by flipping the null
hypothesis, so that the rejection of the null can be the evidence for parallel
trends. In particular, we consider two one-sided tests:

$H_{0}:\theta\geq\gamma_{U},\ \ \mbox{or}\ \ \theta\leq\gamma_{L}$

where $(\gamma_{U},\gamma_{L})$ is a user-specified equivalence range. By
rejecting this null hypothesis, researchers can provide statistical evidence
for the alternative hypothesis:

$H_{0}:\gamma_{L}<\theta<\gamma_{U},$

which means that $\theta$ (i.e., the difference in pre-treament-trends across
treatment and control groups) are within an interval
$[\gamma_{L},\gamma_{U}].$

One difficulty of the equivalence approach is that researchers have to choose
this equivalence range $(\gamma_{U},\gamma_{L})$, which might not be
straightforward in practice. To overcome this challenge, we follow [19] to
estimate the 95% equivalence confidence interval, which is the smallest
equivalence range supported by the observed data. Suppose we obtain $[-c,c]$
as the symmetric 95% equivalence confidence interval where $c>0$ is some
positive constant. Then, this means that if researchers think the absolute
value of $\theta$ smaller than $c$ is substantively negligible, the 5%
equivalence test would reject the null hypothesis and provide the evidence for
the parallel pre-treatment-trends. In contrast, if researchers think the
absolute value of $\theta$ being $c$ is substantively too large as bias in
practice, the 5% equivalence test would fail to reject the null hypothesis and
cannot provide the evidence for the parallel pre-treatment-trends. In sum, by
estimating the equivalence confidence interval, readers of the analysis can
decide how much evidence for the parallel pre-treatment-trends exists in the
observed data. Researchers can estimate the 95% equivalence confidence
interval by the following general two steps. First, estimate 90% confidence
interval, which we denote by $[b_{L},b_{U}].$ Second, we can obtain the
symmetric 95% equivalence confidence interval as $[-b,b]$ where we define
$b=\max\\{|b_{L}|,|b_{U}|\\}.$ See [39, 19] for more details.

Figure A1: Figure 1 from [19] on the difference between the standard
hypothesis testing and the equivalence testing.

##  Appendix G Simulation Study

We conduct a simulation study to compare the performance of the various DID
estimators discussed in this paper. We demonstrate two key results. First, the
double DID is unbiased under the extended parallel trends assumption or under
the parallel trends-in-trends assumption. Second, the double DID has the
smallest standard errors among unbiased DID estimators. In particular,
standard errors of the double DID are smaller than those of the extended DID
(i.e., the two-way fixed effects estimator) even under the extended parallel
trends assumption.

We compare three DID estimators — the double DID, the extended DID, and the
sequential DID — using two scenarios. In the first scenario, the extended
parallel trends assumption (Assumption 2) holds where the difference between
potential outcomes under control $\mathbb{E}[Y_{it}(0)\mid
G_{i}=1]-\mathbb{E}[Y_{it}(0)\mid G_{i}=0]$ is constant over time. This
corresponds to time-invariant unmeasured confounding, and we expect that all
the DID estimators are unbiased in this scenario. The second scenario
represents the parallel-trends-in-trends assumption (Assumption 3) where
unmeasured confounding varies over time linearly. Here, we expect that the
double DID and the sequential DID are unbiased, whereas the extended DID is
biased.

For each of the two scenarios, we consider the balanced panel data with $n$
units and five-time periods where treatments are assigned at the last time
period. We vary the number of units $(n)$ from $100$ to $1000$ and evaluate
the quality of estimators by absolute bias and standard errors over 2000 Monte
Carlo simulations. We describe the details of the simulation setup next.

###  G.1 Simulation Design

We consider the balanced panel data with $T=5$ ($t=\\{0,1,2,3,4\\}$) where the
last period ($t=4$) is treated as the post-treatment period. We vary the
number of units at each time period as $n\in\\{100,250,500,1000\\}$. Thus, the
total number of observations are $nT\in\\{500,1250,2500,5000\\}$. We compare
three estimators: the double DID, the extended DID, and the sequential DID.

Note that we consider four pre-treatment periods here, and thus the
generalized double DID is not equal to the sequential DID even under the
parallel trends-in-trends assumption because it combines two other moments and
optimally weight them (see Appendix E.2). The equivalence between the
sequential DID and the double DID holds only when there are two pre-treatment
periods. We see below that the generalized double DID improves upon the
sequential DID even under the parallel trends-in-trends assumption as they
optimally weight observations from different time periods.

We study two scenarios: one under the extended parallel trends assumption
(Assumption 2) and the other under the parallel-trends-in-trends assumption
(Assumption 3). In the first scenario, the difference between potential
outcomes under control $\mathbb{E}[Y_{it}(0)\mid
G_{i}=1]-\mathbb{E}[Y_{it}(0)\mid G_{i}=0]$ is constant over time. In
particular, we set

$\mathbb{E}[Y_{it}(0)\mid G_{i}=g]=\alpha_{t}+0.05\times g$ (A.6)

where $(\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})=(1,2,3,4,5).$
In the second scenario, we allow for linear time-varying confounding. In
particular, we set

$\mathbb{E}[Y_{it}(0)\mid G_{i}=g]=\alpha_{t}+0.1\times g\times(t+1)$ (A.7)

where $(\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})=(1,2,3,4,5).$

Then, potential outcomes under control are drawn as follows.
$Y_{it}(0)=\mathbb{E}[Y_{it}(0)\mid G_{i}]+\epsilon_{it}$ where
$\epsilon_{it}$ follows the AR(1) process with autocorrelation parameter
$\rho.$ That is,

$\displaystyle\epsilon_{it}$ $\displaystyle=\rho\epsilon_{i,t-1}+\xi_{it},$
$\displaystyle\epsilon_{i0}$ $\displaystyle=\mathcal{N}(0,3/(1-\rho^{2})),$
$\displaystyle\xi_{it}$ $\displaystyle=\mathcal{N}(0,3).$

The causal effect is denoted by $\tau$ and thus, $Y_{it}(1)=\tau+Y_{it}(0)$
where we set $\tau=0.2.$ Finally, $Y_{it}=Y_{it}(0)$ for $t\leq 3$ (pre-
treatment periods) and $Y_{it}=G_{i}Y_{it}(1)+(1-G_{i})Y_{it}(0)$ for $t=4$
(post-treatment period). The half of the samples are in the treatment group
($G_{i}=1$) and the other half is in the control group ($G_{i}=0$).

In Figure A2, we set the autocorrelation parameter $\rho=0.6$. This value is
similar to the autocorrelation parameter used in famous simulation studies in
[9] ($\rho=0.8$). We pick a smaller value to make our simulations harder as we
see below. In Figure A3, we also provide additional results where we consider
a full range of the autocorrelation parameters
$\rho\in\\{0,0.2,0.4,0.6,0.8\\}$ (the same positive autocorrelation values
considered in [9]). Both figures show the absolute bias and the standard
errors which are defined as

$\displaystyle\text{absolute
bias}=\bigg{|}\frac{1}{M}\sum^{M}_{m=1}(\widehat{\tau}_{m}-\tau)\bigg{|}\quad\text{and}\quad\text{standard
error}=\sqrt{\frac{1}{M}\sum^{M}_{m=1}(\widehat{\tau}_{m}-\tau)^{2}},$

where $M$ is the total number of Monte Carlo iterations. Note that this
standard error is a true standard error over the sampling distribution.

###  G.2 Results

Figure A2 shows the results when the autocorrelation parameter $\rho=0.6$. To
begin with the absolute bias, visualized in the first row, all estimators have
little bias under the extended parallel trends assumption (Scenario 1), as
expected from theoretical results. In contrast, under the parallel-trends-in-
trends assumption (Scenario 2), the extended DID (white circle with dotted
line) is biased, while the double DID (black circle with solid line) and the
sequential DID (white triangle with dotted line) are unbiased.

The second row represents the standard errors of each estimator. Under the
extended parallel trends assumption (the first column), the double DID
estimator has the smallest standard error, smaller than the extended DID
estimator (i.e., the two-way fixed effects estimator). This efficiency gain
comes from the fact that the double DID uses the GMM framework to optimally
weight observations from different time periods, although the two-way fixed
effects estimator uses equal weights to all pre-treatment periods.

Under the parallel trends-in-trends assumption (the second row; the second
column), the double DID has almost the same standard error as the sequential
DID. This shows that the double DID changes weights according to scenarios and
solves a practical dilemma of the sequential DID — it is unbiased under the
weaker assumption of the parallel trends-in-trends, but not efficient under
the extended parallel trends.

Figure A2: Comparing DID estimators in terms of the absolute bias and the
standard errors. The first row shows that the double DID estimator (black
circle with solid line) is unbiased under both scenarios. The second row
demonstrates that the double DID has the smallest standard errors among
unbiased DID estimators.

In Figure A3, we provide additional results where we consider a full range of
the autocorrelation parameters $\rho\in\\{0,0.2,0.4,0.6,0.8\\}$ (the same
positive autocorrelation values considered in [9]). We find that when the
autocorrelation of errors is small, standard errors of the double DID are
smaller than those of the sequential DID even under the parallel trends-in-
trends assumption.

Figure A3: Comparing DID estimators in terms of the absolute bias and the
standard errors according to the autocorrelation of errors. Note: The first
row shows that the double DID estimator (black circle with solid line) is
unbiased under both scenarios. The second row demonstrates that the double DID
has the smallest standard errors among unbiased DID estimators. Under the
extended parallel trends assumption (the first column), the efficiency gain
relative to the extended DID (i.e., two-way fixed effects estimator) is large
when the autocorrelation parameter $\rho$ is large. Under the parallel trends-
in-trends assumption (the second column), the efficiency gain relative to the
sequential DID is large when $\rho$ is small.

The first row of Figure A3 shows that our results on the (absolute) bias do
not change regardless of the autocorrelation of errors. In particular, the
double DID is unbiased under the extended parallel trends assumption (the
first column) or under the parallel trends-in-trends assumption (the second
column). In terms of the standard errors (the second row), two results are
important. First, under the extended parallel trends assumption (the first
column), the standard errors of the double DID is the smallest for all the
values of $\rho$ and the efficiency gain relative to the extended DID (i.e.,
two-way fixed effects estimator) is large when the there is high auto-
correlations (i.e., $\rho$ is large). Second, under the parallel trends-in-
trends assumption (the second column), the standard errors of the double DID
is the smallest among unbiased DID estimators (the extended DID is biased).
The efficiency gain relative to the sequential DID is large when $\rho$ is
small.

##  Appendix H Empirical Application

###  H.1 Malesky, Nguyen, and Tran (2014): DID Design

In Section 3.4, we have focused on three outcomes to illustrate the advantage
of the double DID estimator. Each outcome is defined as follows. “Education
and Cultural Program” (binary): This variable takes one if there is a program
that invests in culture and education in the commune. “Tap Water” (binary):
What is the main source of drinking /cooking water for most people in this
commune? “Agricultural Center” (binary): Is there any agriculture extension
center in a given commune? Please see [30] for further details.

In this section, we provide results for all thirty outcomes analyzed in the
original paper. To assess the underlying parallel trends assumptions, we
combine visualization and formal tests, as recommended in the main text. The
assessment suggests that we can make the extended parallel trends assumption
for fifteen outcomes. Specifically, for those fifteen outcomes, p-values for
the null of pre-treatment parallel trends are above 0.10 (i.e., fail to reject
the null at the conventional level), and the 95% standardize equivalence
confidence interval is contained in the interval $[-0.2,0.2]$. This means that
the deviation from the parallel trends in the pre-treatment periods are less
than 0.2 standard deviation of the control mean in 2006.

Figure A4 shows estimated treatment effects under the extended parallel trends
assumption.

Figure A4:  Comparing Standard DID and Double DID under Extended Parallel
Trends Assumption. The double DID estimates are similar to those from the
standard DID, and yet, standard errors are smaller because the double DID
effectively uses pre-treatment periods within the GMM.

As in Section 3.4, the double DID estimates are similar to those from the
standard DID, and yet, standard errors are smaller because the double DID
effectively uses pre-treatment periods within the GMM. Here, we only have two
pre-treatment periods, but when there are more pre-treatment periods, the
efficiency gain of the double DID can be even larger.

We rely on the parallel trends-in-trends assumption for eight outcomes out of
the fifteen remaining outcomes. These outcomes have the 95% standardized
equivalence confidence interval wider than $[-0.20,0.20]$, but show that
treatment and control groups’ pre-treatment trends have the same sign. The
same sign of the pre-treatment trends suggests that parallel trends-in-trends
assumption, which can account for the linear time-varying unmeasured
confounder, can be plausible for these outcomes, even though the stronger
parallel trends assumption is possibly violated.

Figure A5 shows results under the parallel trends-in-trends assumption. As in
Section 3.4, the double DID estimates are often different from those of the
standard DID because the extended parallel trends assumption is implausible
for these outcomes. Importantly, standard errors of the double DID are often
larger than the standard DID. This is because the double DID needs to adjust
for biases in the standard DID by using pre-treatment trends.

Figure A5:  Comparing Standard DID and Double DID under Parallel Trends-in-
Trends Assumption. The double DID estimates are often different from those of
the standard DID because the extended parallel trends assumption is
implausible for these outcomes.

For the remaining seven outcomes of which treatment and control groups’ pre-
treatment trends have the opposite sign, it is difficult to justify either the
extended parallel trends or parallel trends-in-trends assumption without
additional information. Thus, there is no credible estimator for the ATT
without making stronger assumptions. When there are more than two pre-
treatment periods, researchers can apply the sequential DID estimator to pre-
treatment periods in order to formally assess the extended parallel trends-in-
trends assumption. We emphasize that, although we use the equivalence range of
$[-0.20,0.20]$ as a cutoff for an illustration, it is recommended to base this
decision on substantive domain knowledge whenever possible in practice.

###  H.2 Paglayan (2019): Staggered Adoption Design

In this section, we apply the proposed double DID estimator to revisit [34],
which uses the staggered adoption (SA) design to study the effect of granting
collective bargaining rights to teacher’s union on educational expenditures
and teacher’s salary. [34] applies the standard two-way fixed effect models to
estimate the effect of the introduction of the mandatory bargaining law in the
US states on the two outcome. The original author exploits the variation
induced by the different introduction timing of the law: A few states
introduced the law as early as in the mid 1960’s, while some states, such as
Arizona or Kentucky, never introduced the mandate. Among the states that
granted the bargaining rights, the introduction timing varies from the mid
1960’s to the mid 1980’s (Nebraska was the last state that adopted the law).

####  H.2.1 Assessing Underlying Assumptions

We apply the proposed double DID for the SA design to the panel data consists
of state-year observations. A state is treated at a particular year, if the
state passes the law or has already passed the law of mandatory bargaining.
Following the original study, we study two outcome: Per-pupil expenditure and
annual teacher salary, both are on a log scale. There are 2,058 observations,
containing 49 states (excluding Washington DC and Wisconsin, due to the short
availability of the pre-treatment outcomes) and spanning from 1959 through
2000.

Figure A6: Treatment Variation Plot. Note: Cells in gray are state-year
observations that are not treated (i.e., the mandatory bargaining law is not
implemented), while cells in blue are observations that are under the
treatment condition. Rows are sorted such that states that adopt the policy at
earlier years are shown near the top, while states that never adopt the policy
are shown near the bottom. The figure indicates that there are variations
across states in adoption timings, and that some states never adopt the
policy.

Figure A6 shows the variation of the treatment across states and over time.
Cells in gray indicate state-year observations that are not treated and blue
cells indicate the treated observations. We can observe that there are 14
unique treatment timings (the earliest is 1965 and the latest is 1987) where
the number of states at each treatment timing varies from one to six (the
average number of states at a treatment timing is 2.3). We can also see that
there is no reversal of a treatment status in that once a state adopts the
policy, the state has never abolished it during the sample period.

Figure A7: Assessing Underlying Assumptions Using the Pre-treatment Outcomes
(Left: logged expenditure; Right: logged teacher salary). Note: We report the
95% standardized equivalence confidence intervals.

We assess the underlying parallel trends assumption for the SA design by
utilizing the pre-treatment outcome. As in the pre-treatment-trends test in
the basic DID design, we apply the standard DID estimator for the SA design to
pre-treatment periods. For example, to test the pre-treatment trends from
$t-1$ to $t$ for units who receive the treatment at time $t$, we estimate the
SA-ATT using the outcome from $t-2$ and $t-1$ (See Section 4.2 for more
details). To further facilitate interpretation, we standardize the outcome by
the mean and standard deviation of the baseline control group, so that the
effect can be interpreted relative to the control group.

Figure A7 shows 95% standardized equivalence confidence intervals for the two
outcomes of interest (See Section 3.1 for details on the standardization
procedure). It shows that for both outcomes, the equivalence confidence
intervals are within 0.2 standard deviation from the means of the baseline
control groups through $t-5$ to $t-1$. This suggests that the extended
parallel trends assumption is plausible for both outcomes.

####  H.2.2 Estimating Causal Effects

We apply the double DID for the SA design as described in Section 4. The
standard errors are computed by conducting the block bootstrap where the block
is taken at the state level and we take 2000 bootstrap iterations. Analyses
for the two outcomes are conducted separately. In addition to the proposed
method, we apply two existing variants of synthetic control methods that can
handle the staggered adoption design: the generalized synthetic control
method, gsynth [40], and the augmented synthetic control method, augsynth [7].
While the proposed double DID is better suited for settings where there are a
small to moderate number of pre-treatment periods, we evaluate, in the setting
of long pre-treatment periods, whether it can achieve comparable performance
to these variants of synthetic control methods that are primarily designed to
deal with long pre-treatment periods (see more discussions in Section B.3).

Figure A8: Plot of the Average Treatment Effect on the Treated on Two
Outcomes. Note: We compare estimates from the double DID, the generalized
synthetic control method, and the augmented synthetic control method. The
causal estimates are similar across methods for both outcomes and treatment
effects are not statistically significant at the conventional 5% level for
most of the time periods.

Figure A8 shows the estimates of the treatment on the per-pupil expenditure
(the first row) and the teacher’s salary (the second row), where both effects
are on a log scale. We estimated the average treatment effect on the two
outcomes $\ell$ periods after the treatment assignment where
$\ell=\\{0,1,\ldots,9\\}.$ Note that $\ell=0$ corresponds to the
contemporaneous effect. Each column corresponds to different estimators. The
first column shows the proposed double DID estimator for the staggered
adoption design, whereas the second (third) column shows estimates based on
the generalized synthetic control method (the augmented synthetic control
method). We can see that estimates are similar across methods for both
outcomes and treatment effects are not statistically significant at the 5%
level for most of the time periods. This result is consistent with the
original finding of [34] that the granting collective bargaining rights did
not increase the level of resources devoted to education.

As in this example, when there are a large number of pre-treatment periods, it
is important to apply both synthetic control methods and the proposed double
DID, and evaluate robustness across those approaches. This is critical because
they rely on different identification assumptions. We found such robustness in
this application, which provides us with additional credibility.


11institutetext:  IRT SystemX, Paris-Saclay, France 11email:
<EMAIL_ADDRESS>22institutetext: CNRS, Univ Rennes, Inria, IRISA
France 22email<EMAIL_ADDRESS>33institutetext: IMT Atlantique,
IRISA France 33email<EMAIL_ADDRESS>
#  StakeCube: Combining Sharding and Proof-of-Stake to build Fork-free Secure
Permissionless Distributed Ledgers

Antoine Durand 11 Emmanuelle Anceaume 22 Romaric Ludinard 33

###### Abstract

Our work focuses on the design of a scalable permissionless blockchain in the
proof-of-stake setting. In particular, we use a distributed hash table as a
building block to set up randomized shards, and then leverage the sharded
architecture to validate blocks in an efficient manner. We combine verifiable
Byzantine agreements run by shards of stakeholders and a block validation
protocol to guarantee that forks occur with negligible probability. We impose
induced churn to make shards robust to eclipse attacks, and we rely on the
UTXO coin model to guarantee that any stakeholder action is securely
verifiable by anyone. Our protocol works against adaptive adversary, and makes
no synchrony assumption beyond what is required for the byzantine agreement.

###### Keywords:

Blockchain Proof-of-Stake Distributed Hash Table Sharding

##  1 Introduction

Permissionless blockchains, also called distributed ledgers, initially
appeared as the technological solution for the deployment of the Bitcoin
digital cryptocurrency and payment system [23]. Permissionless blockchains aim
at achieving the impressive result of being a persistent, distributed,
consistent and continuously growing log of transactions, publicly auditable
and writable by anyone. Despite the openness of the environment and thus the
inescapable presence of malicious behaviors, security and consistency of
permissionless blockchains do not demand the presence of a trusted third
party.

This is a real achievement, which mainly results from the tight combination of
two ingredients: a randomized election of the next block of transactions to be
appended to the blockchain and a short latency broadcast primitive. While the
latter one relies on the properties of peer-to-peer networks, the former one
has so far been commonly implemented by solving proof-of-work (PoW), a
cryptographic puzzle that is provably secure against a large proportion of
participants that may wish to disrupt the system, and allows to keep the rate
at which blocks are created parametrizable and independent of the size of the
system. This second aspect is important to guarantee that the ratio between
the message transmission delay and the block time interval remains low enough
whatever the system activity, guaranteeing accordingly an easy management of
conflicting blocks, if any.

Unfortunately, resilience of PoW-based solutions fundamentally relies on the
massive use of computational resources, which is a real issue today. Lot of
investigations have been devoted to find a secure alternative to PoW, but most
of them either rely on the intensive use of a large quantity of physical
resources (e.g., proof-of-space [5], proof-of-space/time [22]) or makes
compromises in their trust assumptions (e.g. proof-of-elapsed-time [18],
delegated proof-of-stake [14]). In contrast, solutions based on proof-of-stake
(PoS) seem to be a quite promising way to build secure and permissionless
blockchains. Indeed, proof-of-stake rely on a limited but abstract resource,
the crypto-currency, in such a way that the probability for a participant to
create the next block of the blockchain is generally proportional to the
fraction of currency owned by this participant. It is an elegant alternative
in the sense that all the information needed to verify the legitimacy of a
stakeholder to create a block (i.e., crypto-currency possession) is already
stored in the blockchain. Finally, by being a sustainable alternative
(creating a block requires a few number of operations), scalability concerns,
exhibited by PoW-based solutions, should be a priori more tractable.

An important condition for a PoS-blockchain to be secure is randomness. The
creator of the next block must be truly random, and the source of randomness
must not be biaised by any adversarial strategy. So far, this has been
achieved by two main approaches: chain-based consensus and block-wise
Byzantine agreement with respectively Ourobouros [8] and Algorand [16] as main
representatives. In the former approach, a snapshot of the current users’
status is periodically taken, from which the the next sequence of leaders is
computed. In the latter one, a Byzantine agreement per block, relying on the
properties of verifiable random cryptographic schemes, is achieved. High
robustness against adaptive adversarial strategies results from the dynamic
participation of thousands of users, each one participating for a single step
of the algorithm.

In this paper we present a new blockchain protocol called StakeCube which aims
at improving scalability of the block-wise Byzantine agreement approach by
combining sharding techniques, users presence and stake transfer to operate in
a PoS setting. The key idea of StakeCube is to organise users (i.e.
stakeholders) into shards— such that the number of shards increases sub-
linearly with the total number of active UTXOs— and within each shard, to
randomly choose a constant size committee in charge of executing the
distributed algorithms that contribute to the creation of blocks. Each block
at height $h$ in the blockchain is by design unique (no fork), and once a
block is accepted in the blockchain, the next one is created by a sub-
committee of shards whose selection is random with a distribution that depends
on the content of the last accepted block.

To make such a solution correct in presence of a Byzantine adversary, we
guarantee that the adversary cannot predict the shards in which users will
sit, and that the sojourn time of users in their shard is limited. Doing so is
an effective way to protect the system against eclipse attacks [2, 6]. We
introduce the notion of unpredictable and perishable users’ credentials. Then
to cope with this induced churn, shards’ views are updated, signed and
installed once, and this occurs right before the acceptation of a new block.
Finally, the creation of blocks is efficiently handled by an agreement among a
verifiable sub-committee of shards. We might expect that solely relying on
stakeholders (i.e., owners of the coins of the crypto-currency system) to the
secure construction of the blockchain makes sense due to their incentive to be
fully involved in the blockchain governance, rather than delegating it to
powerful miners. However the analysis against rational players is left as
future work.

The remaining of the paper organised as follows. Section 2 presents related
work, Section 3 details our model and assumptions while Section 4 formalises
the addressed problem. Section 5 describes an high-level view of the required
building blocks of StakeCube while Section 6 presents the design principles of
the proposed solution. A security analysis is provided in Section 7 before
concluding in Section 8.

##  2 Related work

Omniledger [20] is the closest work to ours. It is a PoS-compatible, sharded,
distributed ledger, resilient against a weakly dynamic adversary that corrupts
up to $\frac{1}{4}$ of participants. In contrast to our approach, Omniledger
assumes a strongly synchronous setting, and each shard maintains its own
ledger and, global synchronisation of transactions is achieved through an
atomic commit protocol tailored to their usage. Ouroboros [19], representative
of the chain-based approach, is a synchronous PoS protocol resilient against a
weakly dynamic adversary that owns $1/2-\epsilon$ of stake. Moreover,
Ouroboros has been recently improved to work in the partially synchronous
setting against a dynamic adversary [8, 7], but keeping the same design
principles as the original one. In Ouroboros, a unique leader is elected at
each round to broadcast its block which contrasts with our sharded approach
where the block creation process is distributed. Snow White [13] is a
synchronous PoS protocol resilient against a weakly dynamic adversary that
owns $1/2$ of the _active_ stake. This protocol also relies on a leader
election. Algorand [16], is a representative of the blockwise Byzantine
agreement approach. It provides a distributed ledger against an strongly
adaptive adversary without assuming strong synchrony assumptions. However, by
its design, agreement for each block of the blockchain is achieved by
involving a very large number of stakeholders so that each one needs to
effectively participate only for one exchange of messages.

##  3 Model

We assume a large, finite set of users whose composition may change over time.
Users do not have synchronized clocks, but their individual clocks drift at
the same rate. Users communicate by propagating messages within the system.
The delivery of network messages is at the discretion of the adversary, but
subject to synchrony assumptions. Our construction in itself makes no
synchrony assumption except for what is required for the Byzantine resilient
building blocks. Since our construction uses multiple building blocks,
synchrony assumptions may be changed if they are instantiated differently than
suggested. Users have access to basic cryptographic functions, including a
cryptographic hash function $\mathfrak{h}$, and a CPA-secure signature scheme.
Function $\mathfrak{h}$ is modeled as a random oracle. Users own some minimal
amount of stake (i.e. money), which gives them the right to participate to
StakeCube. We adopt (a simplified version of) what is commonly known as the
Bitcoin Unspent Transaction Output (UTXO) model. An UTXO can be roughly seen
as a user’s account credited by some stake. An UTXO is uniquely characterized
by a public key $pk_{i}$ and its associated amount of stake $s_{i}$. Each
public key is related to the digital signature schema $\Sigma$ with the
uniqueness property, which allows stakeholders to use the public keys (or a
hash thereof) of their UTXOs as a reference to them, as demonstrated in the
”Public Keys as Identities principle” of Chaum [10]. Note that the number of
users evolves according to the UTXO set. At any time, a user can own multiple
UTXOs. UTXOs can be debited only once, and once debited, an UTXO does not
exist anymore. To simplify discussion, transactions outputs do not contain
$\mathfrak{h}(pk_{i})$ but directly $pk_{i}$.

#### Threat model: A weakly adaptive adversary

We assume the presence of Byzantine (i.e. malicious) users which controls up
to $\mu\leq 1/3-\epsilon$ of the total amount of stake currently available in
the system. Here, $\epsilon$ quantifies the gain in the effective adversarial
power, related to the security parameter. This model, named the ”Stake
Threshold Adversary” by Abraham and Malkhi [1], is an alternative to the
common Threshold Adversary Model, which bounds the total number of parties the
adversary controls relative to the total population of the system, and an
extension (or modification) of the Computational Threshold Adversary
introduced by Bitcoin, which bounds the proportion of the computational power
owned by parties. Byzantine users can deviate from the protocol. They are
modeled by an adversary. The adversary can perfectly coordinates all malicious
users. It can learn the messages sent by honest users (i.e. non malicious
users), delay them, and then chooses messages sent by malicious ones. Further
the adversary is weakly adaptive: it can select at any time which users to
corrupt in replacement of corrupted ones (i.e. corruptions are ”moving”),
however a corruption becomes effective $T$ blocks after the adversary has
selected the user to be corrupted. The adversary is computationally bounded so
that it can neither forge honest nodes’ signatures nor break the hash function
and the signature scheme. Finally, we assume that all users (honest and
malicious) share an initial knowledge that we call _genesis block_ which
contains an initial arbitrary UTXO set. We assume this block also shares the
same properties as regular blocks. How to setup the genesis block is out of
the scope of this paper.

##  4 The Addressed Problem

StakeCube aims at allowing any honest user $i$ to locally maintain a sequence
of blocks $B_{0}^{i},B_{1}^{i},\ldots,B_{h}^{i}$, where $h$ represents the
index (or the height) of the block in the sequence. This sequence of blocks
represents $i$’s copy of the distributed ledger, and satisfies both Safety and
Liveness properties. In addition, the orchestration of the shards allows
StakeCube to satisfy both Scalability and Efficiency properties. StakeCube is
parametrized with an arbitrary security parameter $\kappa$, so that all its
properties are guaranteed with probability at least $1-e^{-O(\kappa)}$.

######  Property 1 (Safety)

If honest user $i$ accepts a block $B_{h}^{i}$ at height $h$ in its copy of
the ledger then, for any honest user $j$ that accepts a block at height $h$ in
its copy ledger, $B_{h}^{j}=B_{h}^{i}$.

######  Property 2 (Liveness)

If a honest user submits transaction $tx$, then eventually $tx$ appears in a
block accepted in the copy of all honest users.

In StakeCube, participation of honest users is conditional to the possession
of UTXOs. Participation is voluntary: Any honest user can join a shard
(determined by the protocol), whenever she wishes, with the objective of
eventually being involved in the Byzantine resilient protocols executed in
this shard. Participation is temporary: The sojourn time of an honest user in
a shard is defined by the time it takes for StakeCube to create $T$ blocks.
Once she leaves, she can participate again by joining another shard, and does
so until she spends her UTXO. As users may own multiple UTXOs, they can
simultaneously and verifiably sit in different shards. In the following, a
user that issues a join request with its current credential is called an
_active_ user. StakeCube satisfies Scalability and Efficiency properties. This
is achieved due to the properties of the block creation process. Adding a new
block takes two Byzantine fault tolerant protocols to be run in parallel
within each shard, one network wide diffusion by each shard, one inter-shard
byzantine agreement, and finally one broadcast for the block (more details
will be given in Section 6.3).

######  Property 3 (Scalability)

All Byzantine fault tolerant protocols we rely on have an (overall) $O(n^{3})$
message complexity. However in StakeCube these protocols are executed by
committees whose size is small and fixed. Because the number of shard is
$O(\sqrt{N})$, the overall communication cost is $O(NC_{1}^{3}+C_{2}^{3})$,
with $C_{1}$ and $C_{2}$ some constants depending on $\kappa$. Thus, each
participant’s average communication cost is sublinear in $N$.

######  Property 4 (Efficiency)

All Byzantine fault tolerant protocols we rely on use a constant number of
rounds. Thus adding a new block also takes a constant number of rounds.
Because a transaction, once diffused, will be included in the next block and
blocks are permanently attach to the blockchain, it takes at most two blocks
to include a newly received transaction.

##  5 A Set of Ingredients

To solve the addressed problem, StakeCube relies on the orchestration of the
following ingredients.

Cryptographic Primitives Digital signature together with random hash functions
allow the implementation of verifiable random functions (VRF) [21]. In a VRF,
a secret key $sk$ allows the evaluation $y$ of hash function $\mathfrak{h}$ on
input $x$ as well as the computation of a non-interactive proof that shows
that the secret key $sk$ is the only one that can compute $y$. Verification of
the proof is done with respect to the public key $pk$ only. The proof must
remain sound even when $pk$ is computed maliciously and $\mathfrak{h}(sk,x)$
must remain pseudorandom even when an adversary can query values of
$\mathfrak{h}$ and proofs for them for any input value $x^{\prime}$.

Byzantine Vector Consensus A vector consensus protocol [12] is a Byzantine
resilient protocol where $n$ participants agree on a vector representing the
input value of each participant. Validity condition states that in presence of
$f\leq\lfloor(n-1)/3\rfloor$ Byzantine nodes, the vector contains at least
$f+1$ non-null values, and for each non-null value $v_{i}\neq\bot,1\leq i\leq
n$, this value was initially proposed by participant $i$.

Random Beacon A Random beacon is a service that provides a public source of
randomness. It was first proposed by Rabin [24] in the context of contract
signing. In our case, we need the random beacon to be emulated by a
distributed protocol without trusted third parties, that is, a protocol that
satisfies the following security properties:

  1. 1.

_Guaranteed output delivery._ All honest participants eventually output a
value.

  2. 2.

_Unpredictable._ Any adversary’s ability to predict any information about the
beacon prior to it being published is negligible.

  3. 3.

_Unbiased._ For all adversarial strategies, the output is statistically close
to a uniformly random string.

  4. 4.

_Publicly verifiable._ The protocol also produces a proof that can be verified
by third parties to be convinced that a beacon is indeed the output of the
protocol.

Suitable instantiations for the distributed setting includes SCRAPE [9] and
RandHerd [25]. In the following we denote by $\mu_{core}$ the minimum of the
fractional resiliency of the vector consensus and random beacon protocols.

Verifiable Byzantine Agreement We use a verifiable Byzantine agreement in
order to agree on the next signed block despite corrupted shards. Our main
requirement for this algorithm is to be optimistic, i.e. efficient in the
absence of faults. Indeed, the analysis in Section 7 shows that the
probability for a shard to be corrupted exponentially decreases with shards
core size. Any verifiable Byzantine algorithm satisfying our assumptions can
be used. We rely on the solution proposed by Shen et al [11] since it is
leader-based, efficient and tolerant to temporary partitions. The fractional
resiliency of this protocol is noted $\mu_{corrupted}$.

Distributed Hash Table (DHT) Distributed hash tables (DHTs) build their
topology according to structured graphs, and for most of them, the following
principles hold: each node of the system has an assigned identifier, and the
identifier space, e.g., the set of 256-bit strings, is partitioned among all
the nodes of the system. Nodes self-organize within the graph according to a
distance function based on the identifier space.

Sharded DHT The notion of Sharded DHT is similar to a regular DHT, except that
each vertex of the DHT is a set of nodes instead of a single node. That is,
nodes gather together into shards, and shards self-organize into a DHT graph
topology. Sharded DHTs can be made robust to adversarial strategies as
achieved in SChord [15], and PeerCube [3], and robust to high churn as
achieved in PeerCube [3] by running Byzantine tolerant algorithms within each
shard. For these reasons, we rely on PeerCube architecture, while weakening
its model by removing the assumption of a global trusted party supplying
verifiable random identifier, and by removing the assumption of a static
adversary. For self-containment reasons, we now recall the main design
features of PeerCube. Briefly, this is a DHT that conforms to an hypercube.
Each vertex (i.e. shard) of the hypercube is dynamically formed by gathering
nodes that are logically close to each other according to a distance function
applied on the identifier space. Shards are built so that the respective
common prefix of their members is never a prefix of one-another. This
guarantees that each shard has a unique common prefix, that in turn serves as
a shard’s _label_. The shard’s label characterizes the position of the shard
in the overall hypercubic topology, as in a regular DHT. Shards size is upper
and lower bounded. Whenever the size of shard $\mathcal{S}$ exceeds a given
value $s_{\max}$, $\mathcal{S}$ splits into two shards such that the label of
each of these two new shards is prefixed by $\mathcal{S}$ label, and whenever
the size of $\mathcal{S}$ falls under a given value $s_{\min}$, $\mathcal{S}$
merges with another shard to give rise to a new shard whose label is a prefix
of $\mathcal{S}$ label. Each shard self-organizes into two sets, the core set
and the spare set. The core set is a fixed-size random subset of the whole
shard. It is responsible for running the Byzantine agreement protocols in
order to guarantee that each shard behaves as a single and correct entity (by
for example forwarding all the join and lookup requests to their destination)
despite malicious participants [4]. Members of the spare set merely keep track
of shard state. Joining the core set only happens when some existing core
member leaves, in which case the new member of the core set is randomly
elected among the spare set. By doing this, nodes joining the system weakly
impact the topology of the hypercube [3].

##  6 Design Principles of StakeCube

StakeCube allows the creation of a permissionless distributed ledger in a PoS
setting. The key idea of StakeCube is to organise users (i.e. stakeholders)
into shards— such that the number of shards increases sub-linearly with the
total number of active UTXOs— and within each shard, to randomly choose a
constant size committee in charge of executing the distributed algorithms that
contribute to the creation of blocks.

The randomization of shards members gives a statistical bound the number of
malicious participants sitting at each shards, ensuring the correct execution
of the agreement primitives. More precisely, we compute bounds that may still
cause some shards to have too much malicious participants (i.e. they become
_corrupted shards_), but the overall number of corrupted shards is bounded.
This technique allows us to fix a small shard size while keeping the ability
to make security-efficiency trade-offs.

Each block at height $h$ in the blockchain is unique, and is obtained by
running an inter-shard agreement procedure among a sub-committee of shards.

To be able to tolerate the presence of a Byzantine adversary, we must
guarantee that the adversary cannot predict the shards in which users will
sit, and that the sojourn time of users in their shard is limited. To achieve
this, we introduce the notion of unpredictable and perishable users’
credentials in Section 6.1. Then to cope with this induced churn, we show how
to update, sign a install the shards’ views in Section 6.2. This process
occurs right before the acceptation of a new block. Finally, as described in
Section 6.3 the creation of blocks is efficiently handled by an agreement
among a verifiable sub-committee of shards.

###  6.1 Unpredictable and Perishable Users’ Credentials

As described in Section 5, Peercube critically relies on a (global) trusted
party supplying verifiable random identifiers to nodes. In this section, we
detail how to construct those in our decentralized setting, using the already
known public keys and some randomness present in each block. For each unspent
public key, i.e. for each UTXO, owned by a user, a sequence of unpredictable
and perishable credentials are tightly assigned to her. Validity of a
credential spans $T$ blocks, with $T$ some positive integer. The credential
$\sigma$ assigned to user $i$ for its UTXO ($pk_{i},sk_{i}$) is computed as
follows. Let $B_{h_{0}}$ be the block at height $h_{0}$ of the blockchain such
that $pk_{i}$ was created in $B_{h_{0}}$, i.e., it exists a transaction in
$B_{h_{0}}$ such that $pk_{i}$ appears in the output list of that transaction.
For any blockchain height $h\geq h_{0}+T$, such that UTXO ($pk_{i},sk_{i}$)
still exists when $B_{h}$ is accepted in the blockchain,

$\displaystyle\sigma_{pk_{i}}(h):=H(pk_{i}||B_{h^{\prime}}.\rho),$
$\displaystyle\quad\text{where }\quad
h^{\prime}:=h_{0}+\lfloor\frac{h-h_{0}}{T}\rfloor T,$ (1)

with $B_{h^{\prime}}.\rho$ a random number whose computation is detailed in
Section 6.3. Suppose that $i$’s UTXO ($pk_{i},sk_{i}$) is created in block
$B_{h}$. Then by Relation 1, $i$’s first credential for UTXO ($pk_{i},sk_{i}$)
is computed based on the content of block $B_{h+T}$ and perishes at block
$B_{h+2T}$. Then, $i$’s second credential for ($pk_{i},sk_{i}$) is computed
based on the content of block $B_{h+2T}$ and perishes at block $B_{h+3T}$, and
so on until $i$ spends ($pk_{i},sk_{i}$). User $i$’s credential uniquely
characterizes the shard to which user $i$ is allowed to sit, and this shard is
the one whose label prefixes $i$’s current credential $\sigma_{pk_{i}}(h)$. By
the non-inclusion property of PeerCube [3], there does not exist a shard whose
label is the prefix of another shard, and thus, there is a unique shard whose
label prefixes credential $\sigma_{pk_{i}}(h)$. When her current credential
expires, $i$ leaves the shard she is in, and if she wants to continue to
participate to StakeCube, joins a new shard based on her new credential.

There are a couple of details that should be noted.

  1. 1.

User $i$ does not need to participate in StakeCube for the entire life of her
UTXO ($pk_{i},sk_{i}$). She can join StakeCube (i.e. join a shard) at any time
$h$ under credential $\sigma_{pk_{i}}(h)$, however once a user joins her
shard, she must stay online (and actively participates if she is a core
member) until $\sigma_{pk_{i}}(h)$ expires. As a result, there does not exist
any explicit leave request. A leave simply consists in not issuing a join
request upon credential renewal. A consequence of this rule is that, in case
user $i$ participates under credential $\sigma_{pk_{i}}(h)$ and spends her
UTXO ($pk_{i},sk_{i}$) before $\sigma_{pk_{i}}(h)$ expires, then $i$ continues
to participate under $\sigma_{pk_{i}}(h)$ until $\sigma_{pk_{i}}(h)$ expires.
Note that because a transaction only grants credentials after a delay, this
rule does not allow a user to simultaneously own multiple credentials for the
same stake. Note also that if $i$ is disconnected for a small amount of time
this does not jeopardized the safety of the shard only its liveness.

  2. 2.

Recall that the adversary has a bounded fraction $\mu$ of _stake_ in
StakeCube. To defend StakeCube against Sybil attacks (i.e., the fact that the
adversary creates a considerable number of UTXOs with the objective of
overpopulating each shard with malicious owners of those UTXOs), we require
that each UTXO cannot be credited with more than $M$ stake, with $M$ some
predefined constant. Consequently, by the fact that for any $h>0$ one
credential $\sigma(h)$ represents exactly one UTXO, there is a bound
$\mu_{cred}>\mu$ on the fraction of malicious credentials in StakeCube, which
is reached when all malicious UTXOs have $1$ stake and all honest ones
maximize their stake, i.e., each honest UTXO has $M$ stake. Note that UTXOs
with $M^{\prime}$ stake, such that $M^{\prime}>M$ may be handled by granting
them $\lceil M^{\prime}/M\lceil$ credentials, although we do not treat this
case explicitly. Section 7 analyzes the distribution of malicious credentials
among shards.

Regarding the behavior of the adversary, there are a couple of remarks to
note.

  1. 1.

At any time, the adversary might spend some selected UTXOs in order to create
new ones and thus new credentials with the objective of targeting some shards.
However, because of the initial $T$ blocks delay required to obtain the first
credential for an UTXO (see Relation 1), any newly created UTXO will give rise
to a credential only after all existing credentials are renewed as well.
Therefore, the adversary has no preferred strategy regarding transactions and
forced renewal.

  2. 2.

Each block $B_{h}$ contains a random seed, denoted by $B_{h}.\rho$, which
cannot, by construction, be either biased or predictable before the block is
created (how such seeds are generated is detailed in Section 6.3). Thus by
Relation 1, the adversary cannot determine nor influence the value of renewed
credentials. Consequently, for any blockchain height $h\geq 0$ and for any
$pk_{i}$, $\sigma_{pk_{i}}(h+T)$ is unpredictable while for any $0\leq
h^{\prime}\leq h$, the sequence $(\sigma_{pk_{i}}(h^{\prime}+T))_{0\leq
h^{\prime}\leq h}$ is computable and verifiable from the blockchain.

###  6.2 Shard Membership

As described above, during the period of time that elapses between the
creation of an UTXO to its spending, the UTXO owner can participate to the
blockchain construction by successively joining a series of shards. In
practice this may give rise to a voluminous amount of join requests, which
might be highly prejudicial to StakeCube’s scalability and efficiency if each
joining request led to the insertion of the newcomer in the core which run the
distributed operations. Rather, by relying on PeerCube design (see Section 5),
a newcomer joins the spare set of the shard and not its core set. This
newcomer will be a candidate for being elected as a member of the core set
whenever the core set will undergo a membership modification. Management of
the view composition, and election in the core set is the purpose of the
remaining of the section.

View of a Shard The view of a shard $\mathcal{S}$ reflects the composition of
both its core and spare sets, denoted respectively by $\mathcal{S}_{c}$ and
$\mathcal{S}_{s}$. Update of the view is strongly correlated to blockchain
events: any block appended to the blockchain is preceded, in each shard, by
the update and the installation of the shard view. In the following, the view
of shard $\mathcal{S}$ installed right before block $B_{h}$ is appended to the
blockchain is denoted by _view_ ${}_{\mathcal{S}}(h)$. We have
$view_{\mathcal{S}}(h)=(\mathcal{S}_{c}(h),\mathcal{S}_{s}(h))$, where
$\mathcal{S}_{c}(h)$ (resp. $\mathcal{S}_{s}(h)$) represent the composition of
$\mathcal{S}$’s core set (resp. spare set) at time $h$.

Update of the Shard View When a newcomer (i.e. a user under a valid
credential) issues a request to join her shard $\mathcal{S}$, her request is
propagated and broadcast to the members of $\mathcal{S}_{c}$. Core members $i$
locally store the join request in their buffer $b_{i}$ of pending requests.
Note that expiration of credentials do not need to be locally memorized, prior
to being handled by the view update algorithm, since by Relation 1,
credentials can only expire when a new block is appended to the blockchain.
Let $view_{\mathcal{S}}(h-1)$ be the current view of $\mathcal{S}$ when a
(honest) core member $i\in\mathcal{S}_{c}(h-1)$ receives some valid block
$B_{h}$ (Section 6.3 details the creation of blocks). The following three
steps are successively executed:

  1. 1.

A Byzantine vector agreement protocol is run among $\mathcal{S}_{c}(h-1)$
members to decide on the set of newcomers: core members $i$ propose their
local buffer $b_{i}$, and the outcome of the protocol is a vector $v(h)$ of
newcomers such that non-null values for honest core members $i$ are equal to
their buffer $b_{i}$. Each honest core member $i$ replaces its local buffer
$b_{i}$ with the union of the users of the decided vector. We have
$b_{i}=\cup_{b_{j}\in v(h),b_{j}\neq\bot}b_{j}$.

  2. 2.

Each user $i\in\mathcal{S}_{c}(h-1)$ removes from $b_{i}$ the set
$r_{\mathcal{S}}(h)$ of users whose credential expires with $B_{h}$. User $i$
initializes a new spare set $S_{s}(h)$ with $S_{s}(h)=b_{i}\cup
S_{s}(h-1)\setminus r_{\mathcal{S}}(h)$, and orders $S_{s}(h)$.

  3. 3.

Each user $i\in\mathcal{S}_{c}(h-1)$ initializes a new core set $S_{c}(h)$
with $S_{c}(h)=S_{c}(h-1)\setminus r_{\mathcal{S}}(h)$. If
$\mathcal{S}_{c}(h-1)\cap r_{\mathcal{S}}(h)\neq\emptyset$, some previous core
members $i\in\mathcal{S}_{c}(h-1)$ have credential that expire with $B_{h}$.
As a consequence, an election among the users of $\mathcal{S}_{s}(h)$ is
carried out for $i$’s replacement, so as to keep
$|\mathcal{S}_{c}(h)|=s_{\min}$. The core election works as follows:

    1. (a)

A random beacon protocol is run among $S_{c}(h-1)$ members to decide on a
common random seed $\rho$.

    2. (b)

A pseudo-random number generator $PRG(\rho)$ is initialized with $\rho$ as
seed.

    3. (c)

$PRG(\rho)$ is used to draw a random number $j\in\llbracket
1,|S_{s}(h)|\rrbracket$. The $j$-th member of $\mathcal{S}_{s}(h)$ is removed
from $\mathcal{S}_{s}(h)$ and added to $\mathcal{S}_{c}(h)$. This process is
repeated until $|\mathcal{S}_{c}(h)|=s_{\min}$.

Once these steps are completed, each core member $j$ installs her new view
$view^{j}_{\mathcal{S}}(h)$ with the new values of $S_{c}(h)$ and $S_{s}(h)$,
signs it, and sends it to the spare members. Once a spare receives
$\mu_{core}s_{\min}+1$ signatures on the same view, it installs it. In the
meantime, each core member $j$ resets its buffer $b_{j}=\emptyset$. Note that
multiple join requests may lead a shard $\mathcal{S}$ to split into two
shards, or, on the contrary, may lead two shards $\mathcal{S}^{\prime}$ and
$\mathcal{S}^{\prime\prime}$ to merge within a single one $\mathcal{S}$. The
treatment of such topological changes are omitted in the above procedure for
space reasons, but can be derived from [2].

To summarize, the shard membership procedure ensures that, for any shard
$\mathcal{S}$ of StakeCube, all members of $\mathcal{S}$ install the same view
$view_{\mathcal{S}}(h)$ before appending block $B_{h}$ to their copy of the
blockchain.

Diffusing Views Merely installing the new view for each shard is not
sufficient. We need the other shards of StakeCube to maintain this knowledge
to be able to verify any signed information exchanged during inter-shard
communication (e.g. during the block proposal procedure, see Section 6.3).
Therefore, whenever a new view $view_{\mathcal{S}}(h)$ is installed along with
its $\mu_{core}s_{\min}+1$ signatures, it is also broadcast to the whole
network as a notification of the view update. Note that shards only store the
last view $view_{\mathcal{S}^{\prime}}(h)$ of any other shard
$\mathcal{S}^{\prime}$ and not the whole history of $\mathcal{S}^{\prime}$
views. Moreover, a new view $view_{\mathcal{S}^{\prime}}(h+1)$, can be
verified against the last view $view_{\mathcal{S}^{\prime}}(h)$, so that
corrupted shards can only lie on their core members and omit newcomers.

###  6.3 Construction of the Next Block of the Blockchain

We propose a Byzantine resilient cross-shard mechanism to agree on a unique
valid block, despite the presence of at most $f_{shard}$ corrupted shards (see
Section 7 for $f_{shard}$ computation). Indeed, the presence of an adaptive
adversary may compromise the safety of some shards by succeeding in having
more than a proportion $\mu_{core}$ of malicious users sitting in their core
set. Although the probability of such event can be made arbitrarily low (see
the analysis in Section 7), we must handle it. The presence of corrupted
shards put us in the same situation as in a consensus protocol: given the same
initial chain, any shard is able to create the next block, and the decision
must be a unique block, despite malicious users lying or not responding. As
will be shortly described, agreeing on a unique valid block is efficiently and
robustly achieved by running a Verifiable Byzantine Agreement among a subset
of the shards of StakeCube randomly selected.

Reaching Consensus on the Next Block  The process of creating a new block
$B_{h}$ starts right after $B_{h-1}$ has been accepted. A committee of shards,
denoted in the sequel by $\mathbb{C}$, is elected among the shards of
StakeCube. The election of each of these shards relies on the seed of block
$B_{h-1}$, derived from the random beacon protocol. Once elected, committee
$\mathbb{C}$ executes a verifiable Byzantine agreement to decide on the unique
block $B_{h}$ to be appended to the blockchain. The main steps of this process
are as follows:

  1. 1.

All shards $\mathcal{S}$ compute the elected committee $\mathbb{C}$, similarly
to the core election procedure (see Section 6.2), i.e.,

    1. (a)

Let $\mathbb{L}$ be the set of all the shards’ labels (recall from Section 6.2
that each shard diffuses its new view $view_{\mathcal{S}}(h)$). $\mathbb{L}$
is then ordered through a canonical order.

    2. (b)

A pseudo-random number generator $PRG(B_{h-1}.\rho)$ is initialized, where
$B_{h-1}.\rho$ is the seed of the last block $B_{h-1}$.

    3. (c)

$PRG(B_{h-1}.\rho)$ is used to draw a random number $j\in\llbracket
1,|\mathbb{L}|\rrbracket$. The $j$-th member of $\mathbb{L}$ is removed from
$\mathbb{L}$ and added to $\mathbb{C}$ (initially initialized to $\emptyset$).
This process is repeated until $\mathbb{C}$ contains $s_{\mathbb{C}}$ shards,
with $s_{\mathbb{C}}=(f_{shard}/\mu_{corrupted})+1$. Recall that $f_{shard}$
is the maximal number of corrupted shards in StakeCube (whose computation is
presented in Section 7), and $\mu_{corrupted}$ is the fraction of malicious
nodes tolerated by the Verifiable Byzantine Agreement protocol (see Section
5).

  2. 2.

Members of committee $\mathbb{C}$ run the verifiable Byzantine Agreement
protocol, with their proposed block $B_{h}$ as input (the construction of the
proposed block is described in the next paragraph). Finally the decision is a
block $B_{h^{\prime}}$ signed by $2f_{shard}+1$ shards.

  3. 3.

Block $b_{h}$ is broadcast in StakeCube and appended to StakeCube users’ copy
of the blockchain.

_Security remark:_ By definition of $s_{\mathbb{C}}$, committee $\mathbb{C}$
cannot be corrupted, independently of the shards selected by the election.
Committee $\mathbb{C}$ is still chosen randomly for two reasons. First, it
naturally spreads the load of creating a block across the whole network.
Second, it prevents corrupted shards from trying to manipulate the election
process to get in the committee and slow it down. Note that at this stage a
random seed is already available from the last block and thus there is no need
to run a distributed random beacon.

_Efficiency remark:_ We rely on a leader-based Byzantine Agreement algorithm
to benefit from its optimistic efficiency. Indeed, since $f_{shard}$ can be
made arbitrarily small (see Section 7), and the members of committee
$\mathbb{C}$ are randomly selected, we expect the first leader to almost
always be an honest shard.

Construction of the Proposed Block.  We finally describe how each shard
$\mathcal{S}$ of $\mathbb{C}$ constructs its block $B_{h}$ (see the above case
2). The construction results from an agreement on the content of block $B_{h}$
among the core members of $\mathcal{S}$ and on the generation of the seed of
$B_{h}$. Let $view_{\mathcal{S}}(h)=(\mathcal{S}_{c}(h),\mathcal{S}_{s}(h))$
be the current view of shard $\mathcal{S}$.

  1. 1.

Each core member in $\mathcal{S}_{c}(h)$ proposes _(i)_ its list of pending
transactions and _(ii)_ its VRF value seeded with $B_{h-1}.\rho$ together with
the VRF proof, to the Byzantine Vector consensus protocol. The decision value
is a vector of input values, such that non-null values for honest core members
are equal to their list of pending transactions and their VRF value and VRF
proof.

  2. 2.

Construction of block $B_{h}$ is then realized as follows.

     * •

The hash of the previous block $B_{h-1}$ is inserted in $B_{h}$’s header.

     * •

The union of transactions from the decided vector defines $B_{h}$’s body.

     * •

The hash of the concatenation of the VRF values of the decided vector defines
the seed $B_{h}.\rho$ of $B_{h}$.

     * •

The list of VRF proofs of the decided vector is inserted in $B_{h}$’s header
as a proof of randomness for seed $B_{h}.\rho$.

The reason why the random beacon protocol is not reused is because it is
supposed to be run within a non corrupted shard. For the We have different
requirements. First, we want the seed to be close to random even in the case
of corrupted shards. This does come at the cost of giving the adversary a
bounded number of choices for the seed. Second, we do not mind that a
corrupted shard may decide to abort the computation of the seed, because we
cannot prevent it from not proposing a block anyway.

##  7 Security Analysis

We analyze the probability that some of the shards of StakeCube are corrupted,
that is that their core set contain more than $\mu_{core}s_{\min}$ malicious
users. In the following we denote by $\nu$ the fraction of corrupted shards.
To conduct such an analysis, we examine a simplified scenario. We approximate
the behavior of StakeCube by taking the amortized execution over one period of
$T$ blocks. That is, we study the corruption probability when all the shards
are built and the cores are elected over one period. This is equivalent to the
scenario in which all credentials are synchronously renewed at the same block.
Note that, for a fixed number of active users, the number of credential
renewals, core election, and topological changes is statistically the same for
every period of length $T$.

###  7.1 Corruption Probability of a Core Set during a Period of $T$ Blocks

Let $s$ be the size of shard $\mathcal{S}$, $\mu_{shard}$ be a bound on the
ratio of malicious users within $\mathcal{S}$, and $\mu_{core}$ be the
fractional resiliency of both the Vector Agreement protocol and Random Beacon
one. We assume that $0\leq\mu_{shard}<\mu_{core}\leq\mu$. We compute an upper
bound on the probability that the fraction of malicious users in the core set
is higher than $\mu_{core}$ by the end of the period. As described in Section
6.2, the core set is elected by randomly taking $s_{\min}$ credentials from
shard $\mathcal{S}$, without replacement. Let $Y$ be the random variable equal
to the number of malicious credentials within the core, i.e., $Y$ follows an
hypergeometric distribution whose probability mass function is given by

$\forall k\in\llbracket 0,s_{\min}\rrbracket,\mathbb{P}[Y=k]=\binom{\lfloor
s\mu_{shard}\rfloor}{k}\binom{\lfloor
s(1-\mu_{shard})\rfloor}{s_{\min}-k}\binom{s}{s_{\min}}^{-1}.$ (2)

We are interested in deriving the probability that after $T$ core renewals the
core set $\mathcal{S}$ is corrupted. The core set corruption refers to the
situation where the proportion of malicious credentials in the core exceeds
$\mu_{core}$. Applying the Hoeffding bound [17] on Relation (2) leads to the
following bound

$\displaystyle\mathbb{P}[Y/s_{\min}\geq\mu_{core}]\leq
e^{-2(\mu_{core}-\mu_{shard})^{2}s_{\min}}.$

Thus, assuming that the fraction of malicious users in a shard is below
$\mu_{shard}$, the corruption probability over $T$ blocks exponentially
decreases when $s_{\min}$ increases.

###  7.2 Distribution of Malicious Credentials among all Shards

The above section assumes that the fraction of malicious users in all the
shards is below $\mu_{shard}$. In this section we compute an upper bound on
the probability that this assumption does not hold. We make simplification
assumptions on how the shards are formed. First, we assume that there are $K$
shards of size $S$, giving rise to i.e. $N:=SK$ credentials in total. Second,
we assume that shards configuration in StakeCube during the concerned period
results from a random credential assignment to all the shards. Recall that
$\mu_{cred}$ is the overall ratio of malicious credentials. Let $X_{i}$ be the
random variable representing the number of malicious credentials in the $i$-th
shard, with $1<i<K$. And finally, we note
$\mathbf{X}=(X_{1},\dots,X_{k})\in\\{0,S\\}^{K}$ be the vector made of these
$K$ random variables. Random variable $\mathbf{X}$ represents the distribution
of malicious credentials in StakeCube. It follows a multivariate
hypergeometric distribution, i.e., each of the $N=SK$ credentials is assigned
to a shard. We analyse the shard assignment of a random sample of size
$N\mu_{cred}$. Let $I$ be the set of vectors representing StakeCube when
$N\mu_{cred}$ credentials are malicious. We have

$\mathrm{I}=\\{\mathbf{x}\in[0,S]^{K}\mid\sum_{i=1}^{K}x_{i}=N\mu_{cred}\\}$

a͡nd

$\forall\mathbf{x}\in\mathrm{I},\mathbb{P}[\mathbf{X}=\mathbf{x}]=\binom{N}{N\mu_{cred}}^{-1}\prod_{i=1}^{K}\binom{S}{x_{i}}.$

We are interested in computing the probability that a given shard $j$ among
the $K$ ones contains more than $m$ malicious credentials, that is, let
$\mathrm{I}_{m,j}$ be defined as follows

$\mathrm{I}_{m,j}=\\{\mathbf{x}\in\mathrm{I}\mid x_{j}\geq m\\}.$

We have:

$\displaystyle\mathbb{P}[X_{j}\geq m]$ $\displaystyle=$
$\displaystyle\mathbb{P}[\mathbf{X}\in\mathrm{I}_{m,j}]$ $\displaystyle=$
$\displaystyle\sum_{x\in\mathrm{I}_{m,j}}\binom{N}{N\mu_{cred}}^{-1}\prod_{i=1}^{K}\binom{S}{x_{i}}$
$\displaystyle=$
$\displaystyle\sum_{k=m}^{S}\binom{S}{k}\binom{N}{N\mu_{cred}}^{-1}\sum_{\begin{subarray}{c}x_{1},\dots,x_{K-1}\in[0,S]\\\
\sum_{1\leq i\leq K-1}x_{i}=N\mu_{cred}-k\end{subarray}}\prod_{1\leq i\leq
K,i\neq j}\binom{S}{x_{i}}.$

Knowing that $\sum_{1\leq i\leq K-1}x_{i}=N\mu_{cred}-k$ and $\sum_{1\leq
i\leq K-1}S=N-S$, we can apply Vandermonde’s identity:

$\displaystyle\forall
j,\mathbb{P}[\mathbf{X}\in\mathrm{I}_{m,j}]=\sum_{k=m}^{S}\binom{N}{N\mu_{cred}}^{-1}\binom{S}{k}\binom{N-S}{N\mu_{cred}-k}.$

We now get our result by applying first the (univariate) Hoeffding bound, and
then the union bound.

$\displaystyle\forall
j,\mathbb{P}[\mathbf{X}\in\mathrm{I}_{S\mu_{shard},j}]\leq
e^{-2(\mu_{shard}-\mu_{cred})^{2}S}.$

Thus the probability that at least one shard of the system contains more than
$\mu_{shard}S$ malicious credentials is bounded by

$\displaystyle\mathbb{P}[\mathbf{X}\in\cup_{j=1}^{K}\mathrm{I}_{S\mu_{shard},j}]$
$\displaystyle\leq$ $\displaystyle Ke^{-2(\mu_{shard}-\mu_{cred})^{2}S}$
$\displaystyle=$ $\displaystyle e^{-(2(\mu_{shard}-\mu_{cred})^{2}S-\ln{K})}.$

Term $\cup_{j=1}^{K}\mathrm{I}_{S\mu_{shard},j}$ is the set of shards
assignations to malicious credentials, such that at least one shard has a
fraction greater than or equal to $\mu_{shard}$ of malicious credentials.
Moreover, due to the union bound, this upper bound also holds if the shards
have different sizes and $S$ is the minimum, hence, we can simply use
$S:=s_{\min}$. As for $K$, the worst case is reached when there is a maximal
number of shards, i.e. $K:=N/s_{\min}$.

###  7.3 Putting it all Together

In the previous subsection we got exponentially decreasing bounds on the
probability that at least one shard is corrupted, i.e., proving security when
the bound on the number of malicious shards $f_{shard}$ is set to $0$. We let
for future work the generalization of this calculation with arbitrary values
of $f_{shard}$, which would give us tighter parameters.

The adversary has a fraction $\mu$ of stake. Requiring each credential to be
associated to at most $M$ stake gives us the following (worst case) ratio of
malicious credentials, which is reached when each malicious UTXOs has $1$
stake and each honest one maximizes its stake, i.e., has $M$ stake. We then
have:

$\mu_{cred}=\frac{1}{1+M^{-1}(\mu^{-1}-1)}.$

Thus $M$ should be as small as possible to decrease the adversary effective
stake. However low values of $M$ may require users to participate with a large
number of credentials in parallel, increasing the communication cost for
individual users. Knowing $\mu$ and security parameter $\kappa$, the
parameters $\mu_{shard}$ and $s_{\min}$ can be obtained by solving the
following inequalities

$\displaystyle\mu_{shard}\leq\mu_{cred}+\sqrt{\frac{\kappa-\ln{\frac{N}{s_{\min}}}}{2s_{\min}}}\;\;\;\;\;\mbox{and}\;\;\;\;\;s_{\min}\geq\frac{\kappa}{2(\mu_{core}-\mu_{shard})^{2}}.$

##  8 Conclusion & future work

In this paper we have presented StakeCube a new blockchain protocol which aims
at improving scalability of the block-wise Byzantine agreement approach by
combining sharding techniques, users presence and stake transfer to operate in
a PoS setting. Each block at height $h$ in the blockchain is by design unique
(no fork), and once a block is accepted in the blockchain, the next one is
created by a sub-committee of shards whose selection depends on the random
seed of the last accepted block.

The next step is to take into account the stake associated with each
credential as weights into both the core election and the election of the
shard in charge of creating the next block. This will allow us to get rid of
the $\mu_{cred}-\mu$ gain in adversarial power, while keeping the remaining of
the security arguments similar. More generally, refinements of the security
analysis will give us the ability to instantiate StakeCube with better
parameters while keeping the same security level.

We also plan to implement a prototype of StakeCube to demonstrate its
efficiency and scalability properties, and to showcase some possible
applications.

##  9 Acknowledgements

We are thankful to Gérard Memmi (LTCI Telecom ParisTech), and David Leporini,
Guillaume Hebert and Thomas Domingos (Atos BDS) for their help and fruitful
discussions. This work was carried as part of the Blockchain Advanced Research
& Technologies (BART) Initiative and the Institute for Technological Research
SystemX, and therefore granted with public funds within the scope of the
French Program Investissements d’Avenir.

## References

  * [1] Abraham, I., Malkhi, D.: The blockchain consensus layer and bft. Bulletin of the European Association for Theoretical Computer Science (123) (2017)
  * [2] Anceaume, E., Sericola, B., Ludinard, R., Tronel, F.: Modeling and Evaluating Targeted Attacks in Large Scale Dynamic Systems. In: International Conference on Dependable Systems and Networks (DSN) (2011)
  * [3] Anceaume, E., Ludinard, R., Ravoaja, A., Brasileiro, F.: PeerCube: A Hypercube-Based P2P Overlay Robust against Collusion and Churn. In: IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO) (2008)
  * [4] Anceaume, E., Ludinard, R., Sericola, B.: Performance evaluation of large-scale dynamic systems. ACM SIGMETRICS Performance Evaluation Review 39(4) (2012)
  * [5] Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of Space: When Space Is of the Essence. In: International Conference on Security and Cryptography for Networks (SCN) (2014)
  * [6] Awerbuch, B., Scheideler, C.: Towards scalable and robust overay networks. In: International Workshop on Peer-to-Peer Systems (IPTPS) (2007)
  * [7] Badertscher, C., Gaži, P., Kiayias, A., Russell, A., Zikas, V.: Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability. In: ACM SIGSAC Conference on Computer and Communications Security (CCS) (2018)
  * [8] Bernardo, D., Gaži, P., Kiayias, A., Russell, A.: Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain. In: International Conference on the Theory and Applications of Cryptographic (EUROCRYPT) (2018)
  * [9] Cascudo, I., David, B.: SCRAPE: Scalable randomness attested by public entities. In: International Conference on Applied Cryptography and Network Security (ACNS) (2017)
  * [10] Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM 24(2), 84–90 (1988)
  * [11] Chen, J., Gorbunov, S., Micali, S., Vlachos, G.: Algorand agreement: Super Fast and Partition Resilient Byzantine Agreement. Tech. rep. (2018), https://eprint.iacr.org/2018/377
  * [12] Correia, M., Neves, N.F., Veríssimo, P.: From consensus to atomic broadcast: Time-free Byzantine-resistant protocols without signatures. The Computer Journal 49(1) (2006)
  * [13] Daian, P., Pass, R., Shi, E.: Snow White: Provably Secure Proofs of Stake. Cryptology ePrint Archive, Report 2016/919 (2016), https://eprint.iacr.org/2016/919
  * [14] EOS.IO: Technical white paper v2 (2019), https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md, accessed: 2019-03-10
  * [15] Fiat, A., Saia, J., Young, M.: Making chord robust to byzantine attacks. In: Annual European Symposium on Algorithms (AESA) (2005)
  * [16] Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In: Symposium on Operating Systems Principles (SOSP) (2017)
  * [17] Hoeffding, W.: Probability inequalities for sums of bounded random variables. In: The Collected Works of Wassily Hoeffding (1994)
  * [18] Intel: Hyperledger Sawtooth description (2019), https://sawtooth.hyperledger.org/docs/core/releases/latest/architecture/poet.html, accessed: 2019-03-10
  * [19] Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. Cryptology ePrint Archive, Report 2016/889 (2016), https://eprint.iacr.org/2016/889
  * [20] Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., Ford, B.: Omniledger: A secure, scale-out, decentralized ledger via sharding. In: IEEE Symposium on Security and Privacy (SSP) (2018)
  * [21] Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: IEEE Symposium on Foundations of Computer Science (1999)
  * [22] Moran, T., Orlov, I.: Proofs of space-time and rational proofs of storage. In: Cryptology ePrint Archive, Report 2016/035 (2016)
  * [23] Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf (2008)
  * [24] Rabin, M.O.: Transaction protection by beacons. Journal of Computer and System Sciences 27(2), 256–267 (1983)
  * [25] Syta, E., Jovanovic, P., Kogias, E.K., Gailly, N., Gasser, L., Khoffi, I., Fischer, M.J., Ford, B.: Scalable bias-resistant distributed randomness. In: IEEE Symposium on Security and Privacy (SSP) (2017)