




\subsection{Theorem Statement and Notation}
\label{sec:appendix-notation}

In this section, we consider an accountability gadget $\PIacc$ instantiated with a BFT protocol $\PIbft$ that provides $(n-2f+2)$-accountable-safety at all times, and $f$-liveness after  $\max(\GST,\GAT)$ under
$\AdvEnvPG$.
To match the accountable safety resilience of $\PIbft$ on $\PIacc$, we tune the thresholds for the number of accept and reject votes required to output a new checkpoint as $(n-f+1)$ and $f$ respectively on lines~\ref{line:threshold1} and~\ref{line:threshold2} of Algorithm~\ref{algo:pseudocode-checkpoint-extractor}.

Recall that $\PIacc$ is used on top of a Nakamoto-style permissioned longest chain (LC) protocol $\PIlc$.
For concreteness and notational purposes, we assume that $\PIacc$ is the Sleepy consensus protocol \cite{sleepy} although  we could have used any other permissioned LC protocol in its place.

Given the accountability gadget $\PIacc$ and the LC protocol $\PIlc$, goal of this section is to prove that the ledgers $\LOGacc{}{}$ and $\LOGda{}{}$ outputted by $\PIacc$ and $\PIlc$ satisfy Theorem~\ref{thm:main-security} repeated below:

Given any security parameter $\sigma$ and $f \leq \lceil n/2 \rceil$,
\begin{enumerate}
    \item (\textbf{P1:Accountability}) Under $\AdvEnvPG$, the accountable ledger $\LOGacc{}{}$ provides $n-2f+2$-accountable safety at all times, and there exists a constant $\mathbf{C}$ such that $\LOGacc{}{}$ provides $f$-liveness (with confirmation time polynomial in $\sigma$) after \linebreak $\mathbf{C}\max(\GST,\GAT)$ except with probability $\negl(\sigma)$.
    \item (\textbf{P2:Dynamic Availability}) Under $\AdvEnvDA$, the available ledger $\LOGda{}{}$ is guaranteed to be safe and live at all times, provided that $\beta<1/2$.
    \item (\textbf{Prefix}) $\LOGacc{}{}$ is always a prefix of $\LOGda{}{}$.
\end{enumerate}

Before proceeding with the proofs, we formalize the concept of \emph{security after a certain time} (We write $\LOG{}{} \preceq \LOGBLANKFIX'$ if $\LOG{}{}$ is a prefix of $\LOGBLANKFIX'$.):

\begin{definition}
\label{def:security-after}
Let $\Tconfirm$ be a polynomial function of the security parameter $\sigma$. 
We say that a ledger $\LOG{}{}$ is \emph{secure after time} $T$ and has transaction confirmation time $\Tconfirm$
if $\LOG{}{}$ satisfies:
\begin{itemize}
    \item \textbf{Safety:} For any two times $t \geq t' \geq T$, and any two honest nodes $i$ and $j$ awake at times $t$ and $t'$ respectively, either $\LOG{i}{t} \preceq \LOG{j}{t'}$ or $\LOG{j}{t'} \preceq \LOG{i}{t}$.
    \item \textbf{Liveness:} If a transaction is received by an awake honest node at some time $t \geq T$, then, for any time $t' \geq t+\Tconfirm$ and honest node $j$ that is awake at time $t'$, the transaction will be included in $\LOG{j}{t'}$.
\end{itemize}
\end{definition}

Definition~\ref{def:security-after} formalizes the meaning of `safety, liveness and security \emph{after a certain time $T$}'.
In general, there might be two different times after which a protocol is safe or live.
A protocol that is safe (live) at all times (i.e, after $T=0$) is simply called \emph{safe} (\emph{live}) without further qualification.

\subsection{Accountable Safety Resilience}
\label{sec:appendix-accountable-safety}

We first show that $\LOGacc{}{}$ provides $n-2f+2$-accountable safety under $\AdvEnvPG$.

\begin{proposition}
\label{thm:checkpoint-safety}
Suppose the number of adversarial nodes is less than $n-2f+2$. Then, if a block $b$ is checkpointed for iteration $c$ in the view of an honest node $i$ at slot $t$, for any honest node $j$ and slot $s$, either $b$ is checkpointed for iteration $c$ at slot $s$ or no block has been checkpointed for iteration $c$ yet.
\end{proposition}

Proposition~\ref{thm:checkpoint-safety} follows from the safety of $\LOGbft{}{}$ when the number of adversarial nodes is less than $n-2f+2$.










\begin{theorem}[Accountable Safety of $\LOGacc{}{}$]
$\LOGacc{}{}$ provides $n-2f+2$-accountable-safety.
\end{theorem}

\begin{proof}
To show that $\LOGacc{}{}$ provides $n-2f+2$-accountable-safety, we construct an adjudication protocol $\adj$, which in the case of a safety violation on $\LOGacc{}{}$, outputs at least $n-2f+2$ nodes as adversarial and never outputs an honest node.
For this purpose, suppose there is a safety violation on $\LOGacc{}{}$.
Then, there exist honest nodes $i$ and $j$, iterations $c$ and $c'$ (without loss of generality $c' \leq c$) and slots $s$ and $t$ such that (i) a block $b_1 \neq \bot$ is checkpointed for iteration $c'$ in the view of node $i$ at slot $s$, (ii) a block $b_2 \neq \bot$ is checkpointed for iteration $c$ in the view of node $j$ at slot $t$, (iii) $b_1,b_2$ conflict with each other.
Then, within $\LOGbft{s}{i}$, there are accept votes $\CpReq{accept}{c',b_1}{k}$ from more than $n-f$ nodes for the proposal $b_1$ and iteration $c'$.
Similarly, within $\LOGbft{t}{j}$, there are accept votes $\CpReq{accept}{c,b_2}{k}$ from more than $n-f$ nodes for the proposal $b_2$ and iteration $c$.
Thus, more than $2(n-f+1)-n=n-2f+2$ nodes voted both $\CpReq{accept}{c',b_1}{k}$ and $\CpReq{accept}{c,b_1}{k}$.
Let $S$ denote the set of these nodes.

Next, consider the following two cases:

(i) There is a safety violation on $\LOGbft{}{}$.
(Recall that $\LOGbft{}{}$ provides $n-2f+2$-accountable safety.)
In this case, since the adjudication protocol for $\LOGbft{}{}$ identifies at least $n-2f+2$ nodes as adversarial, $\adj$ simply returns the output of the adjudication protocol for $\LOGbft{}{}$. 

(ii) Suppose there is no safety violation on $\LOGbft{}{}$ and $c'<c$. 
Then, via Proposition~\ref{thm:checkpoint-safety}, every node $k$ in $S$ have either seen $b_1$ become checkpointed for iteration $c'$ before voting accept $\CpReq{accept}{c,b_2}{k}$ or voted for iteration $c$ before seeing any checkpoint for iteration $c'$.
However, an honest node votes accept for the proposal $b_2$ of iteration $c$ only if it has already seen a block checkpointed for all past iterations including $c'$, and if $b_2$ is consistent with all of the checkpoints from the past iterations, including $b_1$.
(This is because an honest node votes accept for a proposal only if it is part of the node's checkpoint-respecting LC.)
Then, no honest node could have voted both $\CpReq{accept}{c',b_1}{k}$ and $\CpReq{accept}{c,b_2}{k}$, implying that all of the nodes in $S$ have violated the protocol.
If $c'=c$, then all of the nodes in $S$ voted accept twice for two different proposals for iteration $c$, which is again a protocol violation.

Finally, when there is no safety violation on $\LOGbft{}{}$, $\LOGbft{i}{s} \preceq \LOGbft{j}{t}$ or $\LOGbft{j}{t} \preceq \LOGbft{i}{s}$.
In either case, all of the accept votes $\CpReq{accept}{c',b_1}{k}$ and $\CpReq{accept}{c,b_2}{k}$ are within the longer of $\LOGbft{i}{s}$ and $\LOGbft{j}{t}$, which can be used to prove that the nodes in $S$ violated the protocol.
Hence, in this case, $\adj$ returns $S$, which contains at least $n-2f+2$ nodes as the set of nodes that have irrefutably violated the protocol. 
\end{proof}

\subsection{Liveness Resilience}
\label{sec:appendix-liveness}

We next focus on the liveness of $\LOGacc{}{}$.

\begin{proposition}
\label{thm:bft-live}
$\PIbft$ satisfies $f$-liveness after $\max(\GST,\GAT)$ with transaction confirmation time $\Tconfirm$.
\end{proposition}

 
\begin{theorem}[Liveness of $\LOGacc{}{}$]
\label{thm:liveness-lemma}
Suppose $\PIlc$ is secure (safe and live) after some slot $T \geq \max(\GST,\GAT)+\Delta+\Tcheckpoint$.
Then, $\LOGacc{}{}$ satisfies $f$-liveness after slot $T$
with transaction confirmation time $\sigma$ except with probability $e^{-\Omega(\sigma)}$.
\end{theorem}

\begin{proof}
If there are $f$ or more adversarial nodes, we know via Proposition~\ref{thm:bft-live} that $\LOGbft{}{}$, and by implication $\LOGacc{}{}$ will not be live. 
Thus, to show $f$-liveness of $\LOGacc{}{}$, we assume that there are less than $f$ adversarial nodes and prove that $\LOGacc{}{}$ satisfies liveness.
In this case, again via Proposition~\ref{thm:bft-live}, we know that $\LOGbft{}{}$ satisfies liveness with transaction confirmation time $\Tconfirm$ after $\max(\GST,\GAT)$, a property which we will use subsequently.

Let $c'$ be the largest iteration such that a block was checkpointed in the view of some honest node before $\max(\GAT,\GST)$.
(Let $c'=0$ if there does not exist such an iteration.)
Since the honest nodes receive every message delivered before $\max(\GAT,\GST)$ by slot $\max(\GAT,\GST)+\Delta$, all honest nodes would have entered iteration $c'+1$ by slot $\max(\GAT,\GST)+\Delta$.
Then, either all honest nodes are within iteration $c'+1$ at slot $\max(\GAT,\GST)+\Delta+\Tcheckpoint$ or an honest nodes have seen a block checkpointed for iteration $c'+1$ by slot $\max(\GAT,\GST)+\Delta+\Tcheckpoint$.
In either case, entrance times of the honest nodes to subsequent iterations have become synchronized by slot  $\max(\GAT,\GST)+\Delta+\Tcheckpoint$: 
If an honest node enters an iteration $c>c'$ at slot $t \geq \max(\GAT,\GST)+\Delta+\Tcheckpoint$, every honest node enters iteration $c'$ by slot $t+\Delta$.

Suppose iteration $c>c'$ has an honest leader $\ld{c}$, which sends a proposal $\bprop{c}$ at slot $t > T + \Tcheckpoint$.
Note that $\bprop{c}$ is received by every honest node by slot $t+\Delta$.
Since the entrance times of nodes are synchronized by $T \geq \max(\GST,\GAT)+\Delta+\Tcheckpoint$, every honest node votes by slot $t+\Delta$.
Now, as $\PIlc$ is secure after slot $T$, $\bprop{c}$ is on all of the checkpoint-respecting LCs held by the honest nodes.
Moreover, as we will argue in the paragraph below, $\bprop{c}$ extends all of the checkpoints seen by the honest nodes by slot $t+\Delta$.
(Honest nodes see the same checkpoints from iterations preceding $c$ due to synchrony.)
Consequently, every honest node votes $\CpReq{accept}{c,\bprop{c}}{k}$ for $\bprop{c}$ by slot $t+\Delta$, all of which appear within $\LOGbft{}{}$ in the view of every honest node by slot $t+\Delta+\Tconfirm$.
Thus, $\bprop{c}$ becomes checkpointed in the view of every honest node by slot $t+\Delta+\Tconfirm$. 
(Here, we assume that $\Ttimeout$ was chosen large enough for $\Ttimeout>\Delta+\Tconfirm$ to hold.)

Note that $\ld{c}$ waits for $\Tcheckpoint$ slots before broadcasting $\bprop{c}$ after observing the last checkpoint block before iteration $c$.
Since $t-\Tcheckpoint>T$, during the period $[t-\Tcheckpoint,t]$, $\PIlc$ satisfies the chain growth and quality properties (see Appendix~\ref{sec:appendix-security-proof-for-the-longest-chain-protocol}). 
Thus, for a large enough $\Tcheckpoint$, the checkpoint-respecting LC of $\ld{c}$ at time $t$ contains at least one honest block between $\bprop{c}$ and the last checkpointed block on the it from before iteration $c$.
(As a corollary, $\ld{c}$ extends all of the previous checkpoints seen by $i$ and all other honest nodes.)
This implies that $\bprop{c}$ contains at least one fresh honest block that enters $\LOGacc{}{}$ by slot $t+\Delta+\Tconfirm$.

Next, we show that an adversarial leader cannot make an iteration last longer than $\Delta+\Ttimeout+\Tconfirm$ for any honest node.
Indeed, if an honest node $i$ enters an iteration $c$ at slot $t$, by slot $t+\Delta+\Ttimeout$, either it sees a block become checkpointed for iteration $c$, or every honest node votes reject.
In the first case, every honest node sees a block checkpointed for iteration $c$ by slot at most $t+2\Delta+\Ttimeout$.
In the second case, reject votes $\CpReq{reject}{c}{k}$ from at least $n-f+1 \geq f$ of the nodes appear in $\LOGbft{}{}$ in the view of every honest node by slot at most $t+\Delta+\Ttimeout+\Tconfirm$.
Hence, a new checkpoint, potentially $\bot$, is outputted in the view of every honest node by slot $t+\Delta+\Ttimeout+\Tconfirm$.

Finally, we observe that except with probability $((f+1)/n)^m$, there exist an iteration with an honest leader within $m$ consecutive iterations.
Since an iteration lasts at most $\max(\Delta+\Ttimeout+\Tconfirm,\Delta+\Tconfirm+\Tcheckpoint) \leq \Delta+\Ttimeout+\Tconfirm+\Tcheckpoint$ slots and a new checkpoint containing a fresh honest block in its prefix appears when an iteration has an honest leader, any transaction received by an awake honest node at slot $t$ appears within $\LOGacc{}{}$ in the view of every honest node by slot at most $\max(t,T)+m(\Delta+\Ttimeout+\Tconfirm+\Tcheckpoint)$ except with probability $(f/n)^m$.
Hence, via a union bound over the total number of iterations (which is a polynomial in $\sigma$), we observe that if $\PIlc$ is secure after some slot $T$, then $\LOGacc{}{}$ satisfies liveness after $T$ with a transaction confirmation time polynomial in $\sigma$ except with probability $e^{-\Omega(\sigma)}$.
\end{proof}

Observe that Theorem~\ref{thm:liveness-lemma} requires $\PIlc$ to eventually regain its security under $\AdvEnvPG$ when there are less than $f$ adversarial nodes.
Although it is not possible to guarantee any security property for $\PIlc$ before $\GST$, the following theorem states that $\PIlc$ recovers its security after $\max(\GST,\GAT)$.
Note that $\PIlc$ is initialized with a parameter $p$ which denotes the probability that a given node is elected as a block producer in a given slot.

\begin{theorem}[Security of $\PIlc$]
\label{thm:security-of-PIlc}
If $p<(n-2f-2)/(2\Delta n (n-f-1))$ and there are $f-1$ (or less) adversarial nodes, for each sufficiently large $\Tcheckpoint$, there exists a constant $\mathbf{C} > 0$ such that for any $\GST$ and $\GAT$ specified by $\AdvEnvPG$, $\PIlc(p)$ is secure after $\mathbf{C}(\max(\GST, \GAT) + \sigma)$, with transaction confirmation time $\sigma$, except with probability $e^{-\Omega(\sqrt{\sigma})}$.
\end{theorem}

Proof of the theorem is given in Section~\ref{sec:appendix-security-proof-for-the-longest-chain-protocol} and relies on a combination of the method outlined in \cite[Appendix C]{sankagiri_clc} with the concept of strong pivots from \cite{sleepy}.

Finally, since $f \leq \lceil n/2 \rceil$, we can always find a $p$ such that $p<(n-2f-2)/(2\Delta n (n-f-1))$.
Then, given Theorems~\ref{thm:security-of-PIlc} and~\ref{thm:liveness-lemma} and a sufficiently small $p$, we can assert that $\LOGacc{}{}$ satisfies $f$-liveness with a transaction confirmation time polynomial in $\sigma$ after time $\mathbf{C}(\max(\GST,\GAT)+\sigma)$ except with probability $e^{-\Omega(\sqrt{\sigma})}$.

\subsection{Recency and Gap Properties}
\label{sec:appendix-gap-and-recency}

Proof of Theorem~\ref{thm:security-of-PIlc} requires the accountability gadget $\PIacc$ to satisfy two main properties first introduced in \cite{sankagiri_clc}: \emph{recency} and \emph{gap} properties.

Gap property states that blocks are checkpointed sufficiently apart in time, controlled by the parameter $\Tcheckpoint$:
\begin{proposition}[Gap Property]
\label{thm:checkpoint-gap}
Given any time interval $[t_1,t_2]$, no more than $(1+(t_2-t_1))/\Tcheckpoint$ blocks can be checkpointed in the interval. 
\end{proposition}
Proof of Proposition~\ref{thm:checkpoint-gap} follows from the fact that upon observing a new checkpoint that is not $\bot$ for an iteration, honest nodes wait for $\Tcheckpoint$ slots before voting for the proposal of the next iteration.

Following the notation in \cite{sankagiri_clc}, we say that a block checkpointed for iteration $c$ at slot $t>\max(\GST,\GAT)$ in the view of an honest node $i$ is $\Trecent$-recent if it has been part of the checkpoint-respecting LC of some honest node $j$ at some slot within $[t-\Trecent,t]$.
Then, we can express the recency property as follows:
\begin{lemma}[Recency Property]
\label{thm:checkpoint-recency}
Every checkpointed block proposed after $\max(\GST,\GAT)$ is $\Trecent$-recent for $\Trecent = \Delta+\Ttimeout+\Tconfirm$.
\end{lemma}

\begin{proof}
We have seen in the proof of Theorem~\ref{thm:liveness-lemma} that if a block $b$ proposed after $\max(\GST,\GAT)$ is checkpointed in the view of an honest node at slot $t$, it should have been proposed after slot $t-\Delta+\Ttimeout+\Tconfirm$.
Thus, more than $n-f+1$ nodes must have voted $\CpReq{accept}{c,b}{k}$ by time $t$.
Let $j$ denote an honest nodes which voted $\CpReq{accept}{c,b}{j}$.
Note that $j$ would vote only after it sees the proposal for iteration $c$, i.e after slot $t-\Trecent = t-\Delta+\Ttimeout+\Tconfirm$.
Hence, $b$ should have been on the checkpoint-respecting LC of node $j$ at some slot within $[t-\Trecent,t]$.
This concludes the proof that every checkpoint block proposed after $\max(\GST,\GAT)$ is $\Trecent$-recent.
\end{proof}
















































\subsection{Chain Growth}
\label{sec:appendix-chain-growth}

\begin{definition}[{\cite[Section 3.2.1]{sleepy}}]
Predicate $\mathrm{growth}(\tau,k)$ is satisfied if and only if for every slot $t \leq T_{\mathrm{max}} - \tau$, $\min_{i,j}(|\chlc{j}{t+\tau}|-|\chlc{i}{t}|) \geq k$.
\end{definition}

We use the same results given in \cite{sankagiri_clc} to lower bound the chain growth in terms of convergence opportunities that lie within the inter-checkpoint intervals.

\begin{lemma}[{\cite[Lemma 5]{sankagiri_clc}}]
\label{thm:chain-growth-catch}
Let $s,t$ be two slots such that $s \in I$ and and $t \geq s + \Delta$. 
Let $\chlc{i}{s}$ be a chain held by some honest node $i$ at slot $s$. 
Then all honest nodes will hold a chain of length at least $|\chlc{i}{s}|$ in slot $t$.
\end{lemma}

Proof is (almost) the same as \cite[Lemma 5]{sankagiri_clc} and uses Lemma~\ref{thm:checkpoint-recency}.
\begin{proof}
Let $i$ and $j$ (potentially $i=j$) be honest nodes awake at slots $s$ and $t \geq s+\Delta$ respectively.
Since $s \in I$, there exists an $l$ such that $s \in I_{l}$. 
Let $b$ denote the last checkpoint block within $\chlc{i}{s}$. 
Since $s \geq \max(\GST,\GAT)$, all honest nodes accept $b$ as a checkpoint by slot $t$.
Next, consider the following two cases: (i) $b$ is the last checkpoint block in $j$'s view by slot $t$.
Then, $|\chlc{j}{t}| \geq |\chlc{i}{s}|$, as $\chlc{i}{s}$ contains all of the checkpoints observed by $j$ by slot $t$.
(ii) $j$ observes at least one new block become checkpointed by slot $t$.
In this case, let $b'$ denote the first block that becomes checkpointed in $j$'s view after $b$ within slot $t^*_{l'}$. $l'>l$.
(In this case, $t \geq t^*_{l'}$ by definition.)
Via Lemma~\ref{thm:checkpoint-recency} (recency property), $b'$ must be on the checkpoint-respecting LC $\chlc{k}{t'}$ held by an honest node $k$ at some slot $t' \in [t^*_{l'} - \Trecent, t^*_{l'}]$, during which $b'$ was not checkpointed yet in the view of any honest node.
Thus, via case (i), $|\chlc{k}{t'}| \geq |\chlc{i}{s}|$ since $t' \geq t^*_{l'} - \Trecent \geq s+\Delta$ for $l'>l$.
Note that the length of the checkpoint-respecting LC held by any honest node at the time it observes $b'$ become checkpointed must be at least $|\chlc{k}{t'}| \geq |\chlc{i}{s}|$.
Hence, by induction, we can state that all honest nodes that observe at least one new checkpoint (after $b$) by slot $t$ hold chains of length at least $|\chlc{i}{s}|$ at slot $t$, implying that $|\chlc{j}{t}| \geq |\chlc{i}{s}|$.
\end{proof}

A useful corollary of Lemma~\ref{thm:chain-growth-catch} is given below:
\begin{corollary}
\label{thm:unique}
All honest blocks produced at convergence opportunities within $I$ have distinct heights.
\end{corollary}
\begin{proof}
Suppose an honest block $b$ is produced at height $\ell$ at a convergence opportunity $t$ within $I$.
Then, the honest producer of $b$ holds a chain of length $\ell$ at slot $t \in S$.
Via Lemma~\ref{thm:chain-growth-catch}, all honest nodes will hold a chain of length at least $\ell$ at all slots $\geq t+\Delta$.
Since the next convergence opportunity after $t$ happens at some slot $\geq t+\Delta$, the next honest block will be at a height larger than $\ell$.
\end{proof}

\begin{lemma}[{\cite[Lemma 6]{sankagiri_clc}}]
\label{thm:chain-growth-lemma}
Consider a slot $s \in I$ and an honest node $i$ awake at $s$ such that $|\chlc{i}{s}|=\ell$.
(Alternatively, consider a slot $t$ and an honest node $i$ awake at $t$ such that $\chlc{i}{t}$ contains an honest block at height $\ell$ produced in some slot $s<t$.)
Then, for any slot $t \geq s+2\Delta$ and honest node $j$ awake at slot $t$, $|\chlc{j}{t}| \geq \ell + \mathrm{C}(I \cap [s+\Delta,t-\Delta])$.
\end{lemma}

Proof is similar to \cite[Lemma 6]{sankagiri_clc} and uses Lemma~\ref{thm:chain-growth-catch}.
A direct consequence of Lemma~\ref{thm:chain-growth-lemma} is that $\mathrm{growth}(\tau,k)$ is satisfied if for any interval $[t_1,t_2]$ of length $t_2-t_1 = \tau \geq 2\Delta$, $\mathrm{C}(I \cap [t_1+\Delta,t_2-\Delta]) \geq k$.

\subsection{Chain Quality}

\begin{definition}[{\cite[Section 3.2.2]{sleepy}}]
Predicate $\mathrm{quality}(\mu,k)$ is satisfied if and only if for every slot $t$ and every honest node $i$ awake at $t$, among any consecutive sequence of $k$ blocks within $\chlc{i}{t}$, the fraction of blocks produced by honest nodes is at least $\mu$.
\end{definition}

\begin{lemma}
\label{thm:chain-quality}
If $\mathrm{quality}(\mu,1/\mu)=0$, then there exist slots $s,t$ such that $\mathrm{A}([s,t]) \geq 1/\mu$ and $\mathrm{A}([s,t]) \geq \mathrm{C}(I \cap [s+\Delta,t-\Delta])-1$.
\end{lemma}

\begin{proof}
If $\mathrm{quality}(\mu,1/\mu)=0$, then there exists a slot $t'$ and an honest node $i$ awake at $t'$ such that $\chlc{i}{t'}$ contains a consecutive sequence of $1/\mu$ blocks $b_1,...,b_{1/\mu}$ produced by the adversary.
Let $b^*_s$ denote the last honest block before $b_1$ within $\chlc{i}{t'}$ and let $\ell_s$ and $s$ respectively denote its height and the slot it was produced in.
Similarly, let $b^*_t$ denote the first honest block after $b_{1/\mu}$ within $\chlc{i}{t'}$ and let $\ell_t$ and $t$ respectively denote its height and the slot it was produced in.
(Note that the genesis block can be taken as an honest block.)
If there is no honest block following $b_{1/\mu}$ within $\chlc{i}{t'}$, let $b^*_t = \chlc{i}{t'}[-1]$, $\ell_t = |\chlc{i}{t'}|$ and $t=t'$.
In either case, there exists an honest node which holds a chain of length $\ell_t-1$ at slot $t$ and this chain contains an honest block at height $\ell_s$ produced in slot $s$.
Thus, via Lemma~\ref{thm:chain-growth-lemma}, we know that $\ell_t \geq \ell_s + \mathrm{C}(I \cap [s+\Delta,t-\Delta])$.
Note that every block within $\chlc{i}{t'}$ with height in $(\ell_s,\ell_t)$ was produced by the adversary within the interval $[s,t]$, and lie on the same chain.
Hence, $\mathrm{A}([s,t]) \geq \ell_t-\ell_s-1$,
where $\ell_t-\ell_s-1 \geq \mathrm{C}(I \cap [s+\Delta,t-\Delta])-1$.
Moreover, the blocks $b_1,...,b_{1/\mu}$ were produced within the interval $[s,t]$ and lie on the same chain, implying that $\mathrm{A}([s,t]) \geq 1/\mu$.
Hence, we can conclude that if $\mathrm{quality}(\mu,1/\mu)=0$, $\mathrm{A}([s,t]) \geq 1/\mu$ and $\mathrm{A}([s,t]) \geq \mathrm{C}(I \cap [s+\Delta,t-\Delta])-1$.
\end{proof}

\subsection{Common Prefix}
\label{sec:appendix-common-prefix}

\begin{definition}[{\cite[Section 3.2.3]{sleepy}}]
Predicate $\mathrm{prefix}(\tau)$ is satisfied if and only if for all slots $s \leq t$ and honest nodes $i,j$ such that $i$ and $j$ are awake at slots $s$ and $t$ respectively, prefix of $\chlc{t}{j}$ consisting of blocks produced at slots $\leq t-\tau$ is a prefix of $\chlc{s}{i}$.
\end{definition}

To show the common prefix property in the context of checkpointed PoS protocols, we extend the definition of strong pivots in \cite[Section 5.6.1]{sleepy} as shown below:

\begin{definition}
A slot $t$ is said to be a \emph{checkpoint-strong pivot}, if for any $t_0 \leq t \leq t_1$, it holds that either $\mathrm{A}([t_0,t_1]) < \mathrm{C}(I \cap [t_0+\Delta,t_1-\Delta])$ or $\mathrm{A}([t_0,t_1])=0$.
\end{definition}

Observe that when we count the number of convergence opportunities for a checkpoint-strong pivot, we only take those that lie within the inter-checkpoint intervals. 
Intuitively, this is because the convergence opportunities that arrive during checkpoint intervals do not offer any guarantee of growth for the chains held by honest nodes.
Conversely, as Corollary~\ref{thm:unique} states, all of the honest blocks that arrive at convergence opportunities within $I$ have a unique height.
Hence, by counting only the convergence opportunities in $I$, we can inherit all of the qualitative results presented in \cite{sleepy} about the prefix property.
In this context, following proposition and lemma extend \cite[Fact 4, Lemma 5]{sleepy}:

\begin{proposition}[Unique Honest Blocks at Convergence Opportunities in $I$]
\label{thm:common-prefix-prop}
Let $i$ and $j$ be two honest nodes awake at slots $r_1$ and $r_2\geq r_1$ respectively. 
If $\chlc{i}{r_1}[\ell]$ and $\chlc{j}{r_2}[\ell]$ are both honest blocks and there exists a convergence opportunity $t^*$, $t^* \in I$, such that an honest block $b^*$ was produced at height $\ell$, then, $\chlc{i}{r_1}[\ell]=\chlc{j}{r_2}[\ell]=b^*$.
\end{proposition}

\begin{proof}
For the sake of contradiction, suppose $\chlc{i}{r_1}[\ell]$ and $\chlc{j}{r_2}[\ell]$ are both honest blocks at least one of which is different from $b^*$.
Let $k$ denote the honest producer of $b^*$ such that $\chlc{k}{t^*}[\ell]=b^*$.
Without loss of generality, suppose $\chlc{i}{r_1}[\ell]=b \neq b^*$, and let $m$ and $t$ denote the honest block producer and the production slot of $b$.
As $b \neq b^*$, either $t < t^*-\Delta$ or $t > t^*+\Delta$.
Now, if $t<t^*-\Delta$, either at least one honest node holds a checkpoint-respecting LC of length $\ell$ at time $t^*-\Delta$, or $b$ conflicts with one of the blocks checkpointed before slot $t^*-\Delta$.
In the first case, $|\chlc{k}{t^{*-}}| \geq \ell$, which implies $b^*$ could not have been produced at height $\ell$, leading to a contradiction.
In the latter case, no checkpoint-respecting LC of an honest node will contain $b$ after slot $t^*$, which is a contradiction as $b \in \chlc{i}{r_1}$.
Conversely, if $t>t^*+\Delta$, via Lemma~\ref{thm:chain-growth-catch}, $|\chlc{m}{t^-}| \geq |\chlc{k}{t^*}| \geq \ell$, which implies $b$ could not have been produced at height $\ell$, leading to a contradiction.
Thus $b=b^*$ and $\chlc{i}{r_1}[\ell]=\chlc{j}{r_2}[\ell]=b^*$.
\end{proof}

\begin{lemma}
\label{thm:checkpoint-strong-pivot}
Let $i$ and $j$ be two honest nodes awake at slots $r_1$ and $r_2\geq r_1$ respectively. 
Let $t$ be a checkpoint-strong pivot such that there is a convergence opportunity in $[t,r_1] \cap I$. 
Then, the last common block within $\chlc{i}{r_1}$ and $\chlc{j}{r_2}$ should have been produced in a slot $\geq t$.
\end{lemma}

\begin{proof}
Since $t$ is a checkpoint-strong pivot, there exist convergence opportunities $t'' \leq t \leq t'$ such that $t'',t' \in I$ and no adversary block is produced in the interval $[t'',t']$.
(Note that if $t$ is a convergence opportunity in $I$, $t''=t'=t$.)
In this case, $t'$ is also a checkpoint-strong pivot.
By the assumption that there is a convergence opportunity in $[t,r_1] \cap I$, we know that $t' \leq r_1$.

As $t' \in I$ is a convergence opportunity, there exists an honest block $b^*$ produced at some height $\ell^*$ at slot $t'$.
Next, we claim that since $t'$ is a checkpoint-strong pivot, there cannot be an adversarial block within $\chlc{i}{r_1}$ and $\chlc{j}{r_2}$ at height $\ell^*$.
For the sake of contradiction, suppose there exists an adversary block $b$ at height $\ell^*$ in a chain $\chlc{m}{s}$ held by some honest node $m$ at some slot $s \geq t'+\Delta$.
Let $b_1$, produced at slot $t_1$ and height $\ell_1<\ell^*$, denote the last honest block in the prefix of $b$ within $\chlc{m}{s}$.
If there is no such block, we take the genesis block as $b_1$.
Similarly, let $b_2$, produced at slot $t_2$ and height $\ell_2>\ell^*$, denote the first honest block in the suffix of $b$ within $\chlc{m}{s}$.
If there is no such block, we take the last block on $\chlc{m}{s}$ as $b_2$.
If $b_2$ is an honest block, by definition, all of the blocks on $\chlc{m}{s}$ at heights $(\ell_1,\ell_2)$ are adversarial (there is at least one such block $b$) and have been mined at distinct times within the interval $(t_1,t_2)$.
On the other hand, if $b_2$ is adversarial, all of the blocks on $\chlc{m}{s}$ at heights $(\ell_1,\ell_2]$ are adversarial and have been mined at distinct times within the interval $(t_1,t_2]$.
In this context, we first consider the case that $b_2$ is honest.

Observe that as $t'$ is a convergence opportunity, either $t' \leq t_1-\Delta$, $t' \in [t_1+\Delta,t_2-\Delta]$ or $t' \geq t_2+\Delta$.
First, if $t' \leq t_1-\Delta$, via Lemma~\ref{thm:chain-growth-catch}, all honest nodes will hold a chain of length at least $\ell^*$ by time $t_1$, implying that $b_1$ could not have been mined at height $\ell_1<\ell^*$, which is a contradiction.
Second, if $t' \geq t_2+\Delta$, then the honest producer of $b^*$ has already seen $b_2$; yet decided to produce a block at height $\ell^*<\ell_2$.
However, this is only possible if $b_2$ conflicts with a checkpoint observed by the producer of $b^*$ by time $t'$.
However, this checkpoint would also be seen by node $m$ by time $t'+\Delta \leq s$, implying that $b_2$ cannot be on $\chlc{m}{s}$ at time $s$, which again is a contradiction.
Consequently, the only possible scenario for $t'$ is $t' \in [t_1+\Delta,t_2-\Delta]$. 

Finally, suppose $b_2$ was produced by some honest node $m'$.
As $\chlc{m'}{t_2}$ contains an honest block, $b_1$, at height $\ell_1$ produced at slot $t_1<t_2-\Delta$, via Lemma~\ref{thm:chain-growth-lemma}, $\ell_2=|\chlc{m'}{t_2}|>\ell_1+\mathrm{C}(I \cap [t_1+\Delta,t_2-\Delta])$.
Moreover, all of the blocks between $b_1$ and $b_2$ (perhaps including $b_2$) are adversarial and has been mined in the interval $(t_1,t_2]$ at distinct times, implying that $A([t_1,t_2]) \geq \mathrm{C}(I \cap [t_1+\Delta,t_2-\Delta])$.
However, this is a contradiction with the fact that $t' \in [t_1+\Delta,t_2-\Delta]$ is a checkpoint-strong pivot.

Next, we consider the case that $b_2$ is an adversarial.
From the analysis above, we know that $t'>t_1+\Delta$.
Moreover, every block on $\chlc{m}{s}$ following $b_1$ are adversarial blocks.
As the honestly-held chain $\chlc{m}{s}$, $s > t'+\Delta$, contains an honest block, $b_1$, at height $\ell_1$ produced at slot $t_1<s-\Delta$, via Lemma~\ref{thm:chain-growth-lemma}, $\ell_2=|\chlc{m}{s}|>\ell_1+\mathrm{C}(I \cap [t_1+\Delta,s-\Delta])$.
Moreover, all of the blocks between $b_1$ and $b_2$ (including $b_2$) are adversarial and have been mined in the interval $(t_1,s]$ at distinct times, implying that $A([t_1,s]) \geq \mathrm{C}(I \cap [t_1+\Delta,s-\Delta])$.
However, this is a contradiction with the fact that $t' \in [t_1+\Delta,s-\Delta]$ is a checkpoint-strong pivot.

Consequently, there cannot exist an adversary block $b$ at height $\ell$ in any chain held by honest nodes after slot $t'+\Delta$, an assertion that includes the chains $\chlc{i}{r_1}$ and $\chlc{j}{r_2}$.
Then, as $\chlc{i}{r_1}[\ell^*]$ and $\chlc{j}{r_2}[\ell^*]$ are both honest blocks and $t'$ is a convergence opportunity, via Proposition~\ref{thm:common-prefix-prop}, \begin{IEEEeqnarray}{C}\chlc{i}{r_1}[\ell^*]=\chlc{j}{r_2}[\ell^*]=b^*.\end{IEEEeqnarray}
Hence, the last common block within  $\chlc{i}{r_1}$ and $\chlc{j}{r_2}$ must have been produced in a slot $\geq t' \geq t$.
\end{proof}

\subsection{Probabilistic Analysis}
\label{sec:appendix-probabilistic-analysis}

To lower bound the number of convergence opportunities within $I$, we can use the following observation from \cite[Proposition 4]{sankagiri_clc} which relies on Proposition~\ref{thm:checkpoint-gap} (gap property): If $t \geq s \geq \max(\GST,\GAT)$, \begin{IEEEeqnarray}{C}
\mathrm{C}([t_1+\Delta,t_2-\Delta] \cap I) \geq \mathrm{C}([t_1+\Delta,t_2-\Delta]) - (1+(t_2-t_1))(\Trecent+2\Delta+1)/\Tcheckpoint.
\IEEEeqnarraynumspace
\end{IEEEeqnarray}
Combining this expression with \cite[Lemma 2, Corollary 2, Fact 2]{sleepy} yields the following proposition:

\begin{proposition}
\label{thm:number-of-c}
For any $\epsilon>0$, there exists an $\epsilon'$ such that given $t_2 \geq t_1 \geq \max(\GST,\GAT)$, $t\triangleq t_2-t_1 \geq 2\Delta$, 
\begin{IEEEeqnarray*}{rCl}
&& \mathbb{P}\left[\mathrm{C}([t_1+\Delta,t_2-\Delta] \cap I) \leq \left((1-\epsilon)(1-2pn\Delta)\alpha-\frac{\Trecent+2\Delta+1}{\Tcheckpoint}\right)t\right] \\
&<& \exp{(-\epsilon'\alpha t)} \\
&& \mathbb{P}[\mathrm{A}([t_1,t_2]) > (1+\epsilon)\beta t] < \exp{(-\epsilon^2\beta t/3)}.
\end{IEEEeqnarray*}
\end{proposition}

We also note that for any given $p<(n-2f+2)/(2\Delta n(n-f+1))$ and sufficiently large $\Tcheckpoint$, there exists a constant $\epsilon>0$ such that
\begin{equation}
\label{eq:ineq}
    (1+\epsilon)\beta<(1-\epsilon)(1-2pn\Delta)\alpha-\frac{\Trecent+2\Delta+1}{\Tcheckpoint}
\end{equation}

Next, we define $T$ as the minimum slot $t \geq \max(\GST,\GAT)$ such that $\mathrm{C}([0, t-\Delta] \cap I)=\mathrm{A}([0,t])$.
In other words, $T$ is an upper bound on the slot by which checkpoint-respecting LCs held by honest nodes would have caught up with the checkpoint-respecting LCs held by the adversary nodes.
Thus, we can view $T$ as the time $\PIlc$ resets itself such that after $T$, it behaves like a checkpoint-respecting LC protocol that has just started running in a synchronous network.
As long as $\Tcheckpoint$ is selected sufficiently large for equation~\ref{eq:ineq} to hold, combining \cite[Propositions 2,3,4]{ebbandflow} with Proposition~\ref{thm:number-of-c}, we can assert the following proposition bounding $T$: 
\begin{proposition}
\label{thm:catch-up}
There exists a constant $\mathbf{C}$ such that for any given security parameter $\sigma$, and $\GST,\GAT$ specified by $\AdvEnvPG$, $T \leq \mathbf{C}(\max(\GST,\GAT) + \sigma)$ except with probability $e^{-\Omega(\sigma)}$.
\end{proposition}
Using Proposition~\ref{thm:catch-up}, we can complete the proof of Theorem~\ref{thm:security-of-PIlc}:
\begin{proof}
Using Proposition~\ref{thm:number-of-c} and Lemma~\ref{thm:chain-growth-lemma}, we can assert that for any given $\epsilon>0$, $\mathrm{growth}(\sigma, k)$ is satisfied after $\max(\GST,\GAT)$ except with probability $e^{-\Omega(\sigma)}$, where $k=g_0 \sigma$ for \begin{IEEEeqnarray}{C}g_0=(1-\epsilon)(1-2pn\Delta)\alpha-\frac{\Trecent+2\Delta+1}{\Tcheckpoint}.\end{IEEEeqnarray}
Similarly, using Lemma~\ref{thm:chain-quality}, Proposition~\ref{thm:number-of-c} and Proposition~\ref{thm:catch-up}, we can assert that for any given $\epsilon>0$, $\mathrm{quality}(\mu,1/\mu)$ is satisfied after slot $\mathbf{C}(\max(\GST,\GAT)+\sigma)$, except with probability $e^{-\Omega(\sigma)}$, where 
\begin{IEEEeqnarray}{C}\mu=\frac{(1-\epsilon)(1-2pn\Delta)\alpha-(1+\epsilon)\beta-(\Trecent+2\Delta+1)/\Tcheckpoint}{(1-2pn\Delta)\alpha-(\Trecent+2\Delta+1)/\Tcheckpoint}.\end{IEEEeqnarray}
Finally, we know via Lemma~\ref{thm:checkpoint-strong-pivot} that checkpoint-strong pivots force convergence of the checkpoint-respecting LCs seen by all honest nodes.
Hence, we can use \cite[Theorem 7]{sleepy} to show that $\mathrm{prefix}(\sigma)$ is satisfied after slot $\mathbf{C}(\max(\GST,\GAT)+\sigma)$ except with probability $e^{-\Omega(\sqrt{\sigma})}$.
Then, using \cite[Lemma 1]{sleepy}, we conclude that $\PIlc$ is secure with $\Tconfirm = O(\sigma/g_0)$ 
after slot $\mathbf{C}(\max(\GST,\GAT)+\sigma)$ except with probability $e^{-\Omega(\sqrt{\sigma})}$.
\end{proof}

\subsection{Security Argument for Chia}
\label{sec:appendix-pospace}

While the sections above prove Theorem~\ref{thm:main-security} for PoS, and by implication PoW protocols, security of Chia \cite{cohen2019chia} does not immediately follow from the analysis of checkpoint-strong-pivots due to nothing-at-stake attacks \cite{dem20}, which enable the adversary to mine blocks on top of each existing block via independent Poisson processes.
The first paper to show security for such protocols given the possibility of nothing-at-stake attacks is \cite{dem20} which introduced a novel method called blocktree-partitioning.
This method splits the overall blocktree into adversarial trees that build on a \emph{fictitious honest tree} with a chain growth property analogous to the one in Appendix~\ref{sec:appendix-chain-growth}.
Thus, as in the case of convergence opportunities, we can once again count only the honest blocks that arrive within inter-checkpoint intervals $I_l$ to provide a non-trivial lower bound on the growth of the fictitious honest tree in the context of checkpoint-respecting LCs.
This lower bound follows from the fact that each honest block produced during such an interval $I_l$ has the potential to contribute to the growth of honest chains just like in the case of original LC protocols.
Using the modified definition for the fictitious honest tree, we can then prove \cite[Theorem 3.2]{dem20} that ties protocol security to the evolution of the fictitious honest tree for checkpoint-respecting LC protocols.
Finally, the probabilistic analysis of \cite[Section 4.2]{dem20} goes through provided that $\beta<1/e$ and the parameters $p$ and $1/\Tcheckpoint$ are sufficiently small.
Details of this analysis is left as future work. 


\subsection{Accountability and Dynamic Participation}
\label{sec:intro-accountability}

Safety and liveness are the two fundamental security properties of consensus protocols. A protocol run by a distributed set of nodes is safe if the ledgers generated by the protocol are consistent across nodes and across time. It is live if all honest transactions eventually enter into the ledger.
Traditionally, consensus protocols are developed for fault-tolerant distributed computing, where a set of distributed computing devices aims to emulate a reliable centralized computer.
In modern decentralized applications such as cryptocurrencies,
consensus nodes are no longer just disinterested computing devices but are agents acting based on economic and other rationales. To provide the proper incentives to encourage nodes to follow the protocol, it is important that they can be held accountable for their protocol-violating behavior. %
This point of view is advocated by Buterin and Griffith \cite{casper} in the context of their effort to add accountability (among other things) to Ethereum's Proof-of-Work (PoW) longest chain protocol, and is also central to the design of Gasper \cite{gasper}, the protocol running Ethereum~2.0's Proof-of-Stake (PoS) beacon chain. In these protocols, accountability is used to incentivize proper behavior by slashing of the stake of protocol-violating agents.




PoW protocols 
like
Bitcoin \cite{nakamoto_paper} or Ethereum 1.0 do not
assign identities to miners, and hence cannot be expected to provide accountability.
Even Nakamoto-style PoS protocols such as Cardano's Ouroboros family \cite{kiayias2017ouroboros,david2018ouroboros,badertscher2018ouroboros}
lack accountability.
On the other hand,
protocols that are designed to provide accountability include Polygraph \cite{CGG19} and Tendermint \cite{tendermint}, and a recent comprehensive work \cite{forensics} shows that accountability can be added on top of
many (but not all) `traditional' propose-and-vote-style Byzantine fault tolerant (BFT) protocols,
such as HotStuff \cite{yin2018hotstuff}, PBFT \cite{pbft}, or Streamlet \cite{streamlet,snapandchat}.
There is, however, another crucial difference between Nakamoto-style and propose-and-vote-style protocols.
While protocols from the first group
do not provide accountability,
they tolerate dynamic participation, a sought after feature of public permissionless blockchains not only for censorship resistance.
In Bitcoin, \eg,
the total hash rate varies over many orders of magnitude over the years. Yet, the blockchains remain continuously \emph{available}, \ie, live.
Protocols from the second group, oppositely,
provide accountability but do not tolerate dynamic participation.%
\footnote{%
For completeness, there are also protocols which neither provide accountability nor tolerate dynamic participation, \eg, Algorand \cite{algorand}.}
Why is there no protocol that both supports accountability and tolerates dynamic participation?

























  



\subsection{Availability-Accountability Dilemma\xspace and Resolution via Accountability Gadgets}
\label{sec:aad}

Our first result says that it is impossible to support accountability for
\emph{dynamically available} protocols, \ie, protocols that are live under dynamic participation (\cf Theorem~\ref{thm:aa-dilemma}).
We call this the \emph{availability-accountability dilemma\xspace}.




\label{sec:resolution-via-acc-gadgets}


Our second contribution is
to provide a resolution to the dilemma.
As no \emph{single} ledger protocol can simultaneously
be available and accountable,
we design and implement an accountability gadget which,
when applied to a longest chain protocol,
generates a dynamically available ledger $\LOGda{}{}$ and a checkpointed prefix ledger $\LOGacc{}{}$ with provably optimal security properties.

Consider a network with a total of $n$ permissioned nodes, and an environment where the network may partition and the nodes may go online and offline.
\begin{enumerate}
    %
    \item (\textbf{P1: Accountability}) The accountable ledger $\LOGacc{}{}$ can provide an accountable safety resilience\xspace of $n/3$ at all times (\ie, identify that many protocol violators in case of a safety violation), and it is live after the partition heals and greater than $2n/3$ honest nodes come online.
    \item (\textbf{P2: Dynamic Availability}) The available ledger $\LOGda{}{}$ is guaranteed to be safe after network partition and live at all times, provided that fewer than $1/2$ of the online nodes are adversarial.
\end{enumerate}

Note that while the checkpointed ledger is by definition always a prefix of the full available ledger, the above result says that the checkpointed ledger will catch up with the available ledger when the network heals and a sufficient number of honest nodes come online.

The achieved resiliences are optimal, which
can be seen by comparing this result with \cite[Theorem B.1]{forensics} (for P1) and
\cite[Theorem 3]{pass2017} (for P2).
The checkpointed ledger $\LOGacc{}{}$ cannot achieve better accountable safety resilience\xspace than $n/3$; it in fact achieves exactly that. The dynamically available ledger $\LOGda{}{}$ cannot achieve a better resilience than $1/2$; the ledger in fact achieves it.
Moreover, even if the network was synchronous at all times,
no protocol could have generated an accountable ledger with better resilience
(Theorem~\ref{thm:aa-dilemma}). So we are getting partition-tolerance for free, even though accountability is the goal.


\begin{figure}[t]
    \centering
    \begin{tikzpicture}[
        %
        x=2cm,
        %
        y=1.12cm,
    ]
        %
        \scriptsize

        \node [align=center,draw,fill=white] (PIlc) at (0.65,0) {Checkpoint-\\respecting\\longest\\chain};
        \node [align=center,draw,rotate=90,fill=white] (cpvotegenerator) at (2,0) {Vote\\generator};
        \node [align=center,draw,rotate=90,fill=white] (PIbft) at (2.9,0) {Accountable\\consensus};
        \node [align=center,draw,rotate=90,fill=white] (cpvoteinterpreter) at (4,0) {Vote\\interpreter};
        \draw [Latex-] (PIlc.west) -- ++(-0.25,0) node [above] {$\txs$};
        \draw [-Latex] (PIlc) -- (cpvotegenerator);
        \draw [-Latex] (cpvotegenerator) -- (PIbft) node [midway,above,rotate=90,anchor=west] {Votes};
        \draw [-Latex] (PIbft) -- (cpvoteinterpreter) node [midway,above,rotate=90,anchor=west] {Votes};
        \draw [-Latex] (PIbft) -- (cpvoteinterpreter) node [midway,below] {$\LOGbft{}{}$};
        \draw [-Latex] (cpvoteinterpreter.south) -- ++(0.1,0) -- ++(0,0.9) -| (cpvotegenerator) node[pos=0.25,above] {Checkpoint decisions};
        
        \draw [-Latex] (cpvoteinterpreter.south) -- ++(0.3,0) -- ++(0,1.5) -| (PIlc) node[pos=0.25,above] {Checkpoint decisions};
        
        \node [rotate=90,anchor=west,align=left] at ($(PIlc.east)+(0.2,0)$) {Confirmed\\blocks};

        \begin{pgfonlayer}{bg1}
            \draw [fill=myParula06LightBlue!30,draw=none] ($(cpvotegenerator.north east)+(-0.2,0.75)$) rectangle ($(cpvoteinterpreter.south west)+(0.2,-0.65)$);
            \node [anchor=south east] at ($(cpvoteinterpreter.south west)+(0.2,-0.65)$) {\emph{Accountability gadget}};
        \end{pgfonlayer}
        \begin{pgfonlayer}{bg2}
            \node [circle,draw=black!60,text=black!80,fill=black!20,inner sep=1pt,xshift=-2pt,yshift=-2pt] at ($(PIlc.south west)$) {$\PIlc$};
            \node [circle,draw=black!60,text=black!80,fill=black!20,inner sep=1pt,xshift=-2pt,yshift=-2pt] at ($(PIbft.north west)$) {$\PIbft$};
            
            \draw [-Latex,myparula61] (cpvoteinterpreter.south) -- ++(0.75,0) node[above] {$\LOGacc{}{}$};
            \draw [-Latex,myparula21] (PIlc.east) -- ++(0.15,0) -- ++(0,-1.5) -- ($(cpvoteinterpreter.south)+(0.75,-1.5)$) node[above] {$\LOGda{}{}$};
        \end{pgfonlayer}
        \coordinate (c1) at ($(cpvoteinterpreter.south west)+(0.2,-0.65)$);
        \coordinate (c2) at ($(cpvotegenerator.north east)+(-0.2,0.75)$);
        \node [circle,text=myParula06LightBlue,draw=none,inner sep=1pt,fill=white,xshift=5pt,yshift=5pt] at (c1 -| c2) {$\PIacc$};
    \end{tikzpicture}
    %
    \caption[]{%
        We construct an accountability gadget $\PIacc$
        from any accountable BFT protocol $\PIbft$
        and apply it to a longest-chain-type protocol $\PIlc$
        as follows:
        The fork choice rule of $\PIlc$ is modified
        to respect the latest checkpoint decision.
        Blocks confirmed by $\PIlc$
        are output as available ledger $\LOGda{}{}$.
        They are also the basis on which nodes
        generate a proposal and vote for the next checkpoint.
        To ensure that all nodes reach the same checkpoint decision, consensus is reached on which votes to count
        using $\PIbft$.
        Checkpoint decisions are output as accountable ledger $\LOGacc{}{}$ and fed back into the protocol
        to ensure consistency of future block production in $\PIlc$
        and future checkpoints with previous checkpoints.%
    }
    \label{fig:protocol-description-overall-diagram}
\end{figure}


The accountability gadget construction is shown in Figure~\ref{fig:protocol-description-overall-diagram}.
It is built on top of any existing longest chain protocol modified to respect the checkpoints. That is, new blocks are proposed and the ledger of confirmed transactions is determined based on the longest chain among all the chains containing the latest checkpointed block.
This gives the available full ledger $\LOGda{}{}$.
Periodically, 
nodes vote on the next checkpoint
(following a randomly selected leader's proposal).
To ensure that when tallying votes all nodes
base their decision for the next checkpoint
on the same set of votes,
any accountable BFT protocol designed for a fixed level of participation
can be used
(entirely as a black box)
to reach consensus on the votes.
The chain up to the latest checkpoint constitutes the accountable prefix
ledger $\LOGacc{}{}$.
The gadget ensures that block production and confirmation
in $\PIlc$ and future checkpoints honor established checkpoints.

\input{introduction_figure_ledger_dynamics}

Since there are many accountable BFT  protocols \cite{forensics}, we have a lot of implementation choices.
Due to its
maturity and the availability of a high quality open-source implementation
which we could employ practically as a black box,
we decided to implement
a prototype of our accountability gadget using the HotStuff protocol \cite{yin2018hotstuff}. Taking the Ethereum 2.0's beacon chain as a target application
and matching its key performance characteristics
such as latency and block size,
we performed Internet-scale experiments to
demonstrate that our solution can meet the target specification
with over $4{,}000$ participants (see Figure~\ref{fig:prototype-results-ledgers-nofaults}(l)).
In particular,
for the chosen parameterization
and
even
before taking reduction measures,
the peak bandwidth required for a node to participate
does not exceed $1.5\,\mathrm{MB/s}$
(with a long-term
average of $78\,\mathrm{KB/s}$)
and hence 
is feasible even for many
consumer-grade Internet connections.
At the same time, our prototype provides
$5\times$
better average latency
of $\LOGacc{}{}$ compared to the
instantiation of Gasper
currently used
for Ethereum 2's beacon chain.




















\subsection{Related Work}
\label{sec:related}

\subsubsection{Accountability}

Accountability in distributed protocols has been studied in earlier works.
\cite{HKD07} designed a system, PeerReview, which detects faults. \cite{HK09} classifies faults into different types and studies their detectability. Casper \cite{casper} focuses on accountability and fault detection when there is violation of safety, and led to the notion of accountable safety resilience we use in this work. Polygraph \cite{CGG19} is a partially synchronous BFT protocol which is secure when there are less than $n/3$ adversarial nodes, and when there is a safety violation, at least $n/3$ nodes can be held accountable.
\cite{RG20} builds upon \cite{CGG19} to create a blockchain which can exclude Byzantine nodes that were found to have 
violated the protocol.


Many of these previous works focus on studying the accountability of \emph{specific} protocols and think of accountability as an add-on feature in addition to the basic security properties of the protocol. \cite{forensics} follows this  spirit but broadens the investigation to formulate a framework to study the accountability of many existing BFT protocols. More specifically, their framework augments the traditional resilience metric  with accountable safety resilience (which they call forensic support). The present work is more in the spirit of \cite{casper}
where accountability is a central design goal, not just an add-on feature. To formalize this spirit, we split traditional resilience into safety and liveness resiliences, upgrade safety resilience to accountable safety resilience, and formulate accountable security as a tradeoff between liveness resilience and accountable safety resilience. Further, we broaden the study to the important dynamic participation environment, where  we discovered the availability-accountability dilemma\xspace (Theorem~\ref{thm:aa-dilemma}).
While at its heart the impossibility result Theorem~B.1 of \cite{forensics} is really about the tradeoff between liveness and accountable safety resiliences, although not stated as such, and it is indeed applicable very generally, when applied to the dynamic participation setting it would give a loose result and would not have been able to demonstrate the availability-accountability dilemma\xspace.





\subsubsection{Availability-Finality Dilemma and Finality Gadgets}


The \emph{avail\-ability-finality dilemma} \cite{PS_partition,lewispye2020resource,ebbandflow} states that no protocol can provide both finality, \ie, safety under network partitions, and availability, \ie, liveness under dynamic participation. The \emph{availability-accountability dilemma\xspace} states that no protocol can provide both accountable safety and liveness under dynamic participation. Although they are different, it turns out that some, but not all, protocols that resolve the availability-finality dilemma can be used to resolve the availability-accountability dilemma\xspace.
Casper \cite{casper} and Gasper \cite{gasper} pioneered resolution of the dilemmata
but lacked a specification of the desired security properties
and suffered from attacks \cite{ethresearch-bouncing-attack-analysis,ethresearch-balancing-attack,ethresearch-balancing-attack2,ebbandflow}.
The first provably secure resolution of the availability-finality dilemma is the class of snap-and-chat protocols \cite{ebbandflow}, which combines a longest chain protocol with a partially synchronous BFT protocol in a black box manner to provide finality. If the partially synchronous BFT protocol is accountable, it is not too difficult to show \cite{snapandchat} that the resulting snap-and-chat protocol would also provide a resolution to the availability-accountability dilemma\xspace. On the other hand, checkpointed longest chain \cite{sankagiri_clc}, another resolution of the availability-finality dilemma, is not accountable, as shown in Appendix \ref{sec:appendix-non-accountability-clc}.

A strength of snap-and-chat protocols is its black box nature which gives it flexibility to provide additional features. A drawback is that the  protocol may reorder the blocks from the longest chain protocol to form the final ledger \cite{snapandchat}. This means that when a proposer proposes a block on the longest chain, it cannot predict the ledger state and check the  validity of transactions by just looking at the earlier blocks in the longest chain.  This lack of \emph{predictable validity} opens the protocol up to spamming and prohibits the use of standard techniques for sharding and light client support.
Checkpointed longest chain builds upon a line of work called finality gadgets \cite{casper,dinsdale2019afgjort,stewart2020grandpa,gasper} and overcomes this limitation of snap-and-chat protocols because the longest chain protocol is modified to respect the checkpoints so that the order of blocks can be preserved. However, checkpointed longest chain's finality gadget is not black box, but specifically uses Algorand BA \cite{algorand_agreement}, which is not accountable \cite{forensics}. It is not readily apparent if and how Algorand BA could be replaced with any accountable BFT protocol.

The accountability gadget we design combines structural elements from snap-and-chat protocols and from the checkpointed longest chain to uniquely achieve the best of both worlds.
It builds on the checkpointed longest chain and 
earlier (not provably secure)
finality gadgets
in that it complements a longest chain protocol with a checkpointing mechanism
and thus achieves predictable validity.
Like snap-and-chat protocols, it allows the use of any BFT protocol as a black box for checkpointing, retaining simplicity and flexibility and, when an accountable BFT protocol like HotStuff is used, the checkpointed ledger is accountable.




















\subsection{Outline}

We introduce in Section~\ref{sec:model} the notation and model for the proof of the availability-accountability dilemma\xspace in Section~\ref{sec:availability-accountability-dilemma} and the construction and security proof of accountability gadgets in Section~\ref{sec:acc-gadgets-section}.
Finally, we discuss details of a prototype implementation
and
experimental performance results
in Section~\ref{sec:experiments}.



\section{Introduction}
\input{introduction}


\section{Model}
\input{model}


\section{The Availability-Accountability Dilemma}
\input{availability-accountability-dilemma}



\section{Accountability Gadgets}
\label{sec:acc-gadgets-section}

In this section, we give a detailed description of the accountability gadget introduced in Section~\ref{sec:resolution-via-acc-gadgets}.
For ease of exposition, we construct
it
from 
an accountable BFT protocol $\PIbft$ 
with
accountable safety and liveness resilience of $\lfloor n/3 \rfloor$.

Like the checkpointed longest chain \cite{sankagiri_clc},
accountability gadgets %
output a prefix ledger safe under partial synchrony along with a full ledger live under dynamic participation.
For this purpose, both protocols
start with a dynamically available longest chain protocol
and periodically checkpoint its output to protect
against reversals under network partition.
Accountability gadgets can use any partially-synchronous BFT SMR protocol
as a black box for checkpointing.
If the selected protocol provides accountability,
then adversarial nodes can be held to account
should there ever be a reversal of a checkpoint.
In contrast,
the checkpointed longest chain is interwoven with a variant
of a particular protocol, Algorand BA \cite{algorand_agreement},
which does not provide accountability \cite{forensics} (\cf Appendix~\ref{sec:appendix-non-accountability-clc}).
Furthermore,
it is not readily apparent how to use another protocol instead.
As a result, the checkpointed longest chain cannot provide a resolution
to the availability-accountability dilemma\xspace, whereas accountability gadgets can.


\subsection{Protocol Description}
\input{protocol_description}

\subsection{Security Properties}
\input{protocol_proof_sketch}



\section{Experimental Evaluation}
\input{prototype_implementation}















\bibliographystyle{splncs04}









