(essentially just as in Section 9.1) that $Q_{1}$ and $Q_{2}$ constitute an
appropriate certificate of guilt, it remains to show that these QCs will be
seen by all active honest players within time $2\Delta^{*}$ of any honest
player entering epoch $e+1$.

If some first honest player enters epoch $e+1$ at timeslot $t$, then all
active honest players do so by $t+\Delta^{*}$. This means $p_{i}$ (for
$i\in\\{1,2\\}$, as specified above) must enter epoch $e+1$ by $t+\Delta^{*}$
and, since $p_{i}$ sees $Q_{i}$ before $t+\Delta^{*}$, $Q_{i}$ must be seen by
all active honest players by time $t+2\Delta^{*}$. All active honest players
therefore see $Q_{1}$ and $Q_{2}$ by time $t+2\Delta^{*}$, as required.

Overall summary of the PosT protocol. Before giving a formal protocol
specification, we informally review the different phases of the PosT protocol.

_Before the recovery procedure is triggered._ During “normal” operation (i.e.,
while not under attack), PosT acts essentially like a version of Tendermint,
but with three phases of voting in each view, and with the set of players that
are responsible for proposing and voting on blocks (i.e., the ‘validators’)
changing with each epoch. To act as a validator, players must place stake in-
escrow. Removal of stake from escrow is subject to a delay of one epoch, with
the duration of each epoch greater than $2\Delta^{*}$. Since any consistency
violation during epoch $e$ will be seen by honest players before epoch $e+1$
is completed, this suffices to ensure that Byzantine players contributing to a
consistency violation can be ‘slashed’ before their stake is removed from
escrow. Since PosT acts essentially like Tendermint in all other respects, in
the case that the adversary is $\rho$-bounded for $\rho<1/3$, the protocol
achieves liveness with respect to a parameter $T_{l}$ that depends on $\Delta$
only (i.e., $T_{l}$ is independent of $\Delta^{*}$) and also satisfies
consistency.

_Once the recovery procedure is triggered._ If a consistency violation occurs
in some least epoch $e$, then active honest players will see a corresponding
certificate of guilt before epoch $e+1$ completes, and will trigger the
recovery procedure. Once the recovery procedure is triggered, the validators
for epoch $e$ then carry out repeated instances of the Dolev-Strong protocol
to determine an updated genesis block. This updated genesis block will contain
all transactions confirmed prior to epoch $e$, and also certificates of guilt
for at least 1/3 of the validating stake for epoch $e$, and will be signed by
the honest majority of validating stake that remains after slashing (using
that $\rho^{*}<2/3$). If desired, the main protocol can resume operation from
this new genesis block.

###  9.4. The formal specification of the main protocol (prior to recovery)

We give a specification that is aimed at simplicity of presentation, and do
not concern ourselves with issues of efficiency, such as communication
complexity and latency. It is convenient to assume that whenever honest $p$
disseminates a message at some timeslot $t$, $p$ regards that dissemination as
having been received (by $p$) at the next timeslot. We assume that all
messages are signed by the player disseminating the message.

Transaction gossiping and the variable $\mathtt{T}^{\ast}$. We assume that,
whenever any honest player first receives a transaction $\mathtt{tr}$, they
disseminate $\mathtt{tr}$ at the same timeslot. Each honest player $p$
maintains a variable $\mathtt{T}^{\ast}$, which is the set of all transactions
received by $p$ thus far.

The stake allocation function. We take as given an initial distribution
$\mathtt{S}^{*}$. The stake allocation function $\mathtt{S}$ should be thought
of as specifying the amount of stake a player has in escrow and which has not
been earmarked for removal from escrow (after one epoch), i.e. a player’s
validating stake. For the sake of simplicity, we suppose that the total number
of units of currency is fixed at some value $N\in\mathbb{N}_{>0}$ and that,
for some determined $x^{*}\in\mathbb{N}_{>0}$, each identifier can hold either
0 or $N/x^{*}$ units of currency in escrow (this still allows a player to put
large amounts of stake in escrow by using multiple identifiers). Stake is
added or removed from escrow via special transactions: an _add-to-escow_
transaction corresponding to identifier $id$ is used to put stake in escrow,
while a _remove-from-escrow_ transaction corresponding to $id$ is used to
remove stake from escrow. To specify how the stake may be updated, we
stipulate that players may create and disseminate ‘epoch’ transactions that
will be used to mark the end of each epoch. ‘Certificates of guilt’ will also
be formally defined in what follows as a special form of transaction. For any
given certificate of guilt $\mathtt{G}$ and any identifier $id$, $\mathtt{G}$
may or may not _implicate_ the identifier $id$. We require that $\mathtt{S}$
satisfies the following conditions:242424Throughout this paper, we use
‘$\ast$’ to denote concatenation.

  1. (1)

If $\mathtt{T}_{2}$ does not contain any epoch transactions, then
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T}_{1}\ast\mathtt{T}_{2},id)=\mathtt{S}(\mathtt{S}^{*},\mathtt{T}_{1},id)$,
i.e.  _$\mathtt{S}$ only updates at the end of an epoch_.

  2. (2)

Suppose $\mathtt{T}$ ends with an epoch transaction. If $\mathtt{T}$ contains
an add-to-escrow transaction corresponding to $id$ that is not followed (in
$\mathtt{T}$) by a remove-from-escrow transaction corresponding to $id$, and
also $\mathtt{T}$ contains no certificate of guilt implicating $id$, then
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)=N/x^{*}$. Otherwise,
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)=0$.252525While a remove-from-escrow
transaction impacts a player’s $\mathtt{S}$-balance immediately at the end of
an epoch, the stake should be considered as remaining in escrow for one
further epoch; this will be reflected in the definitions of the investment and
valuation functions in Section 9.9.

The length of an epoch. Choose $x>2x^{*}$ (where $x^{*}$ is as specified
above) and such that $x\Delta>\Delta^{*}$. We think of epoch $e$ as being
responsible for confirming blocks of heights in $(ex,(e+1)x]$ (block height
will be formally defined below). We will later specify a value $\mathtt{e}(b)$
corresponding to each block $b$, which records the epoch of the block. We will
say a block $b$ is _epoch $e$ ending_ if $\mathtt{e}(b)=e$ and $b$ is of
height $(e+1)x$.

The genesis block. We consider a fixed _genesis block_ $b_{g}$. We set
$\mathtt{h}(b_{g})=\mathtt{e}(b_{g})=\mathtt{v}(b_{g})=0$. These values
indicate the _height_ of the block, and the epoch and view numbers
corresponding to the block respectively. We consider the empty set, denoted
$\emptyset$, a stage 1 QC for $b_{g}$, and set $\mathtt{b}(\emptyset)=b_{g}$,
$\mathtt{e}(\emptyset)=\mathtt{v}(\emptyset)=0$. No set of messages is a stage
2 QC for $b_{g}$. The block $b_{g}$ has no parent, has only itself as an
ancestor and is $M$-_valid_ for any set of messages $M$.

The variable $M$. Each player $p$ maintains a variable $M$, which is the set
of all messages received by $p$ thus far: Intially $M$ is set to be
$\\{b_{g}\\}$.

Blocks. A block $b$ other than the genesis block is entirely specified by the
following values:

$\mathtt{h}(b)$: The height of $b$.

$\mathtt{v}(b)$: The view corresponding to $b$.

$\mathtt{e}(b)$: The epoch corresponding to $b$.

$\mathtt{par}(b)$: The parent of $b$. We also call $b$ a _child_ of
$\mathtt{par}(b)$. The ancestors of $b$ are $b$ and all ancestors of
$\mathtt{par}(b)$. The _descendants_ of any block $b$ are $b$ and all the
descendants of its children. Two blocks are _incompatible_ if neither is an
ancestor of the other. For $b$ to be $M$-valid it must hold that:

  * •

$b\in M$;

  * •

$\mathtt{par}(b)$ is $M$-valid;

  * •

The ancestors of $b$ include $b_{g}$;

  * •

$h(b)=h(\mathtt{par}(b))+1$;

  * •

If $\mathtt{par}(b)$ is epoch $e=\mathtt{e}(\mathtt{par}(b))$ ending, then
$\mathtt{e}(b)$ is $e$ or $e+1$;262626Thus, a block whose parent is epoch $e$
ending can still belong to the same epoch. This is due to the considerations
outlined in Section 9.3, i.e. further blocks may need to be built in the same
epoch so as to confirm the block that is epoch $e$ ending. Once that block $b$
is confirmed, the first blocks of the next epoch will be children of $b$.

  * •

If $\mathtt{par}(b)$ is not epoch $e=\mathtt{e}(\mathtt{par}(b))$ ending, then
$\mathtt{e}(b)=e$.

$\mathtt{QCprev}(b)$: This value plays a similar role as in Section 9.1. For
$b$ to be $M$-valid:

  * •

$M$ must contain $\mathtt{QCprev}(b)$;

  * •

$\mathtt{QCprev}(b)$ must be a stage 1 QC for $\mathtt{par}(b)$.

$\mathtt{T}(b)$: The sequence of transactions in $b$. For $b$ to be $M$-valid,
we require that $\mathtt{T}(b)$ ends with an epoch transaction iff $b$ is
epoch $\mathtt{e}(b)$ ending.272727This condition is important because epoch
transactions inform $\mathtt{S}$ of the end of an epoch.

$\mathtt{Tr}(b)$: The sequence of transactions in all ancestors of $b$. For
$b$ to be $M$-valid, we require
$\mathtt{Tr}(b)=\mathtt{Tr}(\mathtt{par}(b))\ast\mathtt{T}(b)$.

$\mathtt{Tval}(b)$: The sequence of transactions used to determine who should
vote on $b$. We set $\mathtt{Tval}(b_{g})=\emptyset$. For $b$ to be $M$-valid,
we require:

  * •

If $\mathtt{e}(b)=\mathtt{e}(\mathtt{par}(b))$ then
$\mathtt{Tval}(b)=\mathtt{Tval}(\mathtt{par}(b))$;

  * •

If $\mathtt{e}(b)=\mathtt{e}(\mathtt{par}(b))+1$ then
$\mathtt{Tval}(b)=\mathtt{Tr}(\mathtt{par}(b))$.

Votes. A vote $V$ is entirely specified by the following values:

$\mathtt{b}(V)$: The block for which $V$ is a vote.

$\mathtt{c}(V)$: The amount of stake corresponding to the vote.

$\mathtt{s}(V)$: The stage of the vote (1, 2 or 3).

$\mathtt{id}(V)$: For the vote to be _valid_ , it must be signed by
$\mathtt{id}(V)$.

$\mathtt{vprev}(V)$: For the vote to be valid, this must equal
$\mathtt{v}(\mathtt{QCprev}(\mathtt{b}(V)))$.

Quorum certificates. Let $\mathtt{T}:=\mathtt{Tval}(b)$ and set:

$\mathtt{N}(b):=\sum_{p\in\mathcal{P}}\sum_{id\in\mathtt{id}(p)}\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id).$

For any block $b$ other than $b_{g}$, and for $s\in\\{1,2,3\\}$, we say a set
of valid votes $Q$ is a stage $s$ QC for $b$ if the following conditions are
all satisfied:

  1. (i)

For each $V\in Q$ we have $\mathtt{b}(V)=b$, and $\mathtt{s}(V)=s$;

  2. (ii)

For each $V\in Q$ it holds that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},\mathtt{id}(V))=\mathtt{c}(V)$;

  3. (iii)

There do not exist $V\neq V^{\prime}$ in $Q$ with
$\mathtt{id}(V)=\mathtt{id}(V^{\prime})$;

  4. (iv)

$\sum_{V\in Q}\mathtt{c}(V)\geq\frac{2}{3}\mathtt{N}(b)$.

If $Q$ is a stage $s$ QC for $b$, we define $\mathtt{b}(Q):=b$,
$\mathtt{e}(Q):=\mathtt{e}(b)$, $\mathtt{v}(Q):=\mathtt{v}(b)$,
$\mathtt{vprev}(Q)=\mathtt{v}(\mathtt{QCprev}(b))$, and $\mathtt{s}(Q):=s$.

In an abuse of notation, we’ll say $Q\in M$ when every element of $Q$ is in
$M$.

_Recall that $\mathtt{Tval}(b)$ is the sequence of transactions used to
determine who should vote on $b$. So, this sequence determines the ‘validating
stake’. The conditions above stipulate that votes from 2/3 of the validating
stake are required to form a QC._

Defining the confirmation rule. A block $b$ is $M$-confirmed if there exists a
descendant $b^{\prime}$ of $b$ with $\mathtt{e}(b^{\prime})=\mathtt{e}(b)$,
such that $b^{\prime}$ is $M$-valid with stage 1, 2 and 3 QCs in $M$, and if
it also holds that $b$ is of height $\leq(\mathtt{e}(b)+1)x$. Let $b$ be of
greatest height amongst the $M$-confirmed blocks. The sequence of
$M$-confirmed transactions is $\mathtt{Tr}(b)$.282828Once an honest player $p$
sees that the recovery procedure has been triggered and has terminated,
outputting a new genesis block $b_{g}^{\prime}$, it is technically convenient
for $p$ to regard $b_{g}^{\prime}$ as the only confirmed block. If a
consistency violation occurs in some least epoch $e$, then $b_{g}^{\prime}$
will contain all transactions confirmed by the end of epoch $e-1$.

For any block $b$ other than $b_{g}$ to be $M$-valid we require that:

  * •

If $\mathtt{e}(b)>\mathtt{e}(\mathtt{par}(b))$, then $\mathtt{par}(b)$ is
$M$-confirmed.

$M$-validity. A block is $M$-valid if it satisfies all of the conditions for
$M$-validity listed above (in this section).

Defining certificates of guilt. A certificate of guilt for epoch $e$
(considered a special form of transaction) is a pair of QCs $(Q,Q^{\prime})$
such that:

  * •

$Q$ is a stage 2 QC for some $b$ with $\mathtt{e}(b)=e$ and $\mathtt{v}(b)=v$
(say);

  * •

$Q^{\prime}$ is a stage 1 QC for some $b^{\prime}$ with
$\mathtt{e}(b^{\prime})=e$ and $\mathtt{v}(b^{\prime})=v^{\prime}$ (say);

  * •

$b^{\prime}$ is incompatible with $b$;

  * •

$v^{\prime}\geq v$ and $\mathtt{vprev}(Q^{\prime})<v$.

A certificate of guilt $(Q,Q^{\prime})$ _implicates_ $id$ if there exist votes
$V\in Q$, $V^{\prime}\in Q^{\prime}$ with
$\mathtt{id}(V)=\mathtt{id}(V^{\prime})=id$.

The local variable $Q^{+}$. This plays a similar role as in Section 9.1.
Initially $Q^{+}:=\emptyset$, i.e. $Q^{+}$ is set to be a stage 1 QC for
$b_{g}$.

The local variable $\mathtt{e}$. The value $\mathtt{e}$ records the current
epoch for $p$. Initially, $\mathtt{e}=0$.

The local value $\mathtt{rec}$. This is initially 0, and is set to 1 to
indicate that $p$ should start executing instructions for the recovery
procedure.

The $\mathtt{eupdate}$ procedure. The following procedure called
$\mathtt{eupdate}$ is responsible for updating $\mathtt{e}$:

  1. (1)

If $\mathtt{rec}=0$, then let $e$ be greatest such that there exists a block
$b$ which is $M$-confirmed and epoch $e$ ending, or, if there exists no such
$e$, let $e=-1$. Set $\mathtt{e}:=e+1$. If this is the first timeslot at which
$\mathtt{e}=e+1$, then we say _epoch $e+1$ begins at $t$ for $p$_.

  2. (2)

If $\mathtt{rec}=1$ and $M$ contains a certificate of guilt for epoch
$\mathtt{e}-1$, set $\mathtt{e}:=\mathtt{e}-1$.

_(1) above specifies the present epoch for $p$ before the recovery procedure
is triggered. This is defined in the obvious way: $p$ looks to see which epoch
it has seen completed and begins work on the next epoch. (2) updates the epoch
when the recovery procedure is triggered because of a consistency violation in
epoch $\mathtt{e}-1$. If the recovery procedure is triggered because of a
consistency violation in epoch $\mathtt{e}$, there is no need to update
$\mathtt{e}$._

When $p$ is ready to enter the recovery procedure. We say $p$ is ready to
enter the recovery procedure if either:

  * •

$M$ contains a certificate of guilt for epoch $\mathtt{e}-1$, or;

  * •

Epoch $\mathtt{e}$ began for $p$ at a timeslot $t^{\prime}<t-2\Delta^{*}$, and
$M$ contains a certificate of guilt for epoch $\mathtt{e}$.

_The conditions above specify when the recovery procedure is triggered, and
stipulate that one must wait time $2\Delta^{*}$ after entering epoch $e$
before triggering the recovery procedure because of a consistency violation in
epoch $e$. This is to give sufficient time for a consistency violation in the
previous epoch to be revealed, and to ensure that the recovery procedure is
only triggered because of a consistency violation in a single epoch._

The function $\mathtt{Qset}$. This function is used to update $Q^{+}$ after
entering a new epoch, and is defined as follows. Amongst the $M$-confirmed and
epoch $\mathtt{e}-1$ ending blocks, choose $b$ such that $\mathtt{v}(b)$ takes
the greatest value. Let $Q$ be some stage 1 QC for $b$ and define
$\mathtt{Qset}(M,\mathtt{e}):=Q$.

Defining $\mathtt{lead}(M,\mathtt{e},v)$. Player $p$’s belief as to who should
be the leader for view $v$ depends on their values $M$ and $\mathtt{e}$. If
there does not exist a unique $b\in M$ which is $M$-confirmed and epoch
$\mathtt{e}-1$ ending, then $\mathtt{lead}(M,\mathtt{e},v)$ is
undefined.292929Generally, we write $x\uparrow$ to indicate that the variable
$x$ is undefined, and we write $x\downarrow$ to indicate that $x$ is defined.
Otherwise, let $b$ be such a block and set $\mathtt{T}:=\mathtt{Tr}(b)$ and
$v:=\mathtt{v}(b)$. Recall our assumption that, for some determined
$x^{*}\in\mathbb{N}_{>0}$, if $\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$
then $\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)=N/x^{*}$. Let
$id_{0},\dots,id_{k-1}$ be an enumeration of the identifiers $id$ such that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$. For $i\in\mathbb{N}_{>0}$, we
define $\mathtt{lead}(M,\mathtt{e},v+i)$ to be the identifier $id_{j}$, where
$j=i\text{ mod }k$.

Admissible blocks. When $p$ determines whether to vote on a block $b$ in view
$v$, it will only do so if the block is _admissible_. At any point, $p$
regards $b$ as admissible for view $v$ if all of the following conditions are
satisfied:

  * •

$b$ is $M$-valid;

  * •

$\mathtt{v}(b)=v$ and $b$ is signed by $\mathtt{lead}(M,\mathtt{e},v)$;

  * •

$\mathtt{v}(Q^{+})\leq\mathtt{v}(\mathtt{QCprev}(b))$;

  * •

$\mathtt{e}(b)=\mathtt{e}$;

The $\mathtt{disseminate\ new\ block}$ procedure. If
$\mathtt{lead}(M,\mathtt{e},v)$ (as locally defined for $p$) is an identifier
$id\in\mathtt{id}(p)$ then, at the beginning of view $v$, $p$ proceeds as
follows in order to specify and disseminate a new block:

  1. (1)

Amongst the $M$-valid $b^{\prime}$ with a stage 1 QC in $M$ such that
$\mathtt{e}(b^{\prime})=\mathtt{e}$, choose $b^{\prime}$ such that
$\mathtt{v}(b^{\prime})$ is maximal and set $Q$ to be a stage 1 QC for
$b^{\prime}$ in $M$. Or, if there exists no such block in $M$, set
$Q:=\mathtt{Qset}(M,\mathtt{e})$ and let $b^{\prime}:=\mathtt{b}(Q)$.

  2. (2)

Let $\mathtt{T}$ be the set of transactions in
$\mathtt{T}^{*}-\mathtt{Tr}(b^{\prime})$. Let $b$ be a new block with
$\mathtt{e}(b)=\mathtt{e}$, $\mathtt{v}(b)=v$, $\mathtt{par}(b)=b^{\prime}$,
$\mathtt{QCprev}(b)=Q$, $\mathtt{T}(b)$ the transactions of $\mathtt{T}$ (in
some arbitrary order and, if appropriate, concluding with a transaction
indicating the end of epoch $\mathtt{e}$), and which satisfies all conditions
for $M$-validity (note that these conditions suffice to specify
$\mathtt{Tval}(b)$ and $\mathtt{h}(b)$).

  3. (3)

Disseminate $b$, signed by $id$.

The pseudocode. The pseudocode is described in Algorithm 1.

###  9.5. The formal specification of the recovery procedure

Upon setting $\mathtt{rec}:=1$, indicating that the recovery procedure is
triggered, player $p$ will run the $\mathtt{eupdate}$ procedure, which will
set $\mathtt{e}$ to be the least epoch in which a consistency violation
occurs. The aim of the recovery procedure is then to reach consensus on an
updated genesis block $b_{g}^{\prime}$ at which the slashing instructions have
been carried out. To specify $b_{g}^{\prime}$, one need only specify the
transactions in $b_{g}^{\prime}$, although honest players will also produce
votes for $b_{g}^{\prime}$, ensuring that it is uniquely determined.

$M$-admissible genesis proposals. Let $M$ and $\mathtt{e}$ be as locally
defined for $p$ during the recovery procedure. Let $b$ be an epoch
$\mathtt{e}-1$ ending block that is $M$-confirmed, and set
$\mathtt{T}:=\mathtt{Tr}(b)$. A genesis proposal $(b_{g}^{\prime},i)$ is
$M$-admissible if
$\mathtt{T}(b_{g}^{\prime})=\mathtt{T}\ast\mathtt{G}\ast\mathtt{tr}$, where
$\mathtt{G}$ is a certificate of guilt for epoch $\mathtt{e}$ and
$\mathtt{tr}$ is an epoch transaction. The second coordinate $i$ in the
genesis proposal $(b_{g}^{\prime},i)$ indicates that the proposal is made
during the $i^{\text{th}}$ instance of the Dolev-Strong protocol.

Defining $\mathtt{reclead}(M,i)$ and $\mathtt{signed}(M,i,j)$. We use a
similar notation for signed messages as in Section 9.2. For any message $m$,
and for distinct identifiers $id_{1},\dots,id_{j}$, we let
$m_{id_{1},\dots,id_{j}}$ be $m$ signed by $id_{1},\dots,id_{j}$ in order. As
above, let $M$ and $\mathtt{e}$ be as locally defined for $p$ during the
recovery procedure. Let $b$ be an epoch $\mathtt{e}-1$ ending block that is
$M$-confirmed, and set $\mathtt{T}:=\mathtt{Tr}(b)$. Let
$id_{0},\dots,id_{k-1}$ be an enumeration of the identifiers $id$ such that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$ and set
$\mathtt{Id}(M):=\\{id_{0},\dots,id_{k-1}\\}$. For $i\in\mathbb{N}_{\geq 0}$,
we define $\mathtt{reclead}(M,i)$ to be the identifier $id_{j}$, where
$j=i\text{ mod }k$. This value specifies the leader for the $i^{\text{th}}$
instance of the Dolev-Strong protocol.

For $i\in\mathbb{N}_{\geq 0}$ and $j\in\mathbb{N}_{\geq 1}$, we define
$\mathtt{signed}(M,i,j)$ to be the set of all messages in $M$ which are of the
form $m_{id_{1}^{\prime},\dots,id_{j}^{\prime}}$, such that $m$ is an
$M$-admissible genesis proposal $(b_{g}^{\prime},i)$ and
$id_{1}^{\prime},\dots,id_{j}^{\prime}$ are all distinct members of
$\mathtt{Id}(M)$, with $id_{1}^{\prime}=\mathtt{reclead}(M,i)$.

The variable $O_{p}$. This plays the same role as in Section 9.2.

Votes for the final output. Honest players will disseminate _output votes_ for
a value $b_{g}^{\prime}$ that may be used as an updated genesis block. These
output votes $V$ are entirely specified by three values $\mathtt{b}(V)$,
$\mathtt{c}(V)$ and $\mathtt{id}(V)$, and must be signed by $\mathtt{id}(V)$
to be valid.

The pseudocode. The pseudocode is described in Algorithm 2.

Algorithm 1 The instructions for player $p$ before the recovery procedure is
triggered.

1:At timeslot $1$:

2: Set $\mathtt{end}:=0$, $\mathtt{rec}:=0$;

3:

4:At every timeslot $t$ if $\mathtt{end}=0$:

5: $\mathtt{eupdate}$; $\triangleright$ Defined in Section 9.4, responsible
for updating $\mathtt{e}$

6: If epoch $\mathtt{e}$ begins at $t$ for $p$ then set
$Q^{+}:=\mathtt{Qset}(M,\mathtt{e})$; $\triangleright$ Set $\mathtt{Q}^{+}$ at
start of epoch

7: If $p$ is ready to enter the recovery procedure then: $\triangleright$
Condition defined in Section 9.4

8: Set $\mathtt{rec}:=1$ and perform $\mathtt{eupdate}$; $\triangleright$
Start recovery procedure

9: Set $\mathtt{end}:=1$.

10:

11:At timeslot $4v\Delta$ for $v\in\mathbb{N}_{>0}$ if $\mathtt{end}=0$:

12: If $\mathtt{lead}(M,\mathtt{e},v)\in\mathtt{id}(p)$ then
$\mathtt{disseminate\ new\ block}$; $\triangleright$ Disseminate a new block

13:

14:At timeslot $4v\Delta+\Delta$ for $v\in\mathbb{N}_{>0}$ if
$\mathtt{end}=0$:

15: Set $\mathtt{b}^{*}$ to be undefined;

16: If there exists a first $b$ enumerated into $M$ which is admissible for
view $v$ then:

17: Set $\mathtt{b}^{*}:=b$ and $\mathtt{T}:=\mathtt{Tval}(b)$,
$Q:=\mathtt{QCprev}(b)$;

18: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$: $\triangleright$ Disseminate
stage 1 votes

19: Let $c:=\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)$;

20: Disseminate $V$ with $\mathtt{b}(V)=\mathtt{b}^{*}$, $\mathtt{c}(V)=c$,
$\mathtt{s}(V)=1$, $\mathtt{id}(V)=id$, $\mathtt{vprev}(V)=\mathtt{v}(Q)$;

21:

22:At timeslot $4v\Delta+2\Delta$ for $v\in\mathbb{N}_{>0}$ if
$\mathtt{end}=0$:

23: If $\mathtt{b}^{*}\downarrow$ and $M$ contains a stage 1 QC for
$\mathtt{b}^{*}$ then:

24: Set $Q^{+}$ to be a stage 1 QC for $\mathtt{b}^{*}$ in $M$;
$\triangleright$ Set new lock

25: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$: $\triangleright$ Disseminate
stage 2 votes

26: Let $c:=\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)$;

27: Disseminate $V$ with $\mathtt{b}(V)=\mathtt{b}^{*}$, $\mathtt{c}(V)=c$,
$\mathtt{s}(V)=2$, $\mathtt{id}(V)=id$, $\mathtt{vprev}(V)=\mathtt{v}(Q)$;

28:

29:At timeslot $4v\Delta+3\Delta$ for $v\in\mathbb{N}_{>0}$ if
$\mathtt{end}=0$:

30: If $\mathtt{b}^{*}\downarrow$ and $M$ contains a stage 2 QC for
$\mathtt{b}^{*}$ then:

31: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$: $\triangleright$ Disseminate
stage 3 votes

32: Let $c:=\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)$;

33: Disseminate $V$ with $\mathtt{b}(V)=\mathtt{b}^{*}$, $\mathtt{c}(V)=c$,
$\mathtt{s}(V)=3$, $\mathtt{id}(V)=id$, $\mathtt{vprev}(V)=\mathtt{v}(Q)$;

Algorithm 2 Recovery procedure instructions for $p$: to be carried out when
$\mathtt{rec}=1$.

1:At timeslot $4\Delta((\mathtt{e}+2)x+1)$: $\triangleright$ Initialization

2: Set $\mathtt{recend}:=0$;

3: Let $b$ be epoch $\mathtt{e}-1$ ending and $M$-confirmed; Set
$\mathtt{T}:=\mathtt{Tr}(b)$;

4: Set $k=|\\{id:\ \mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0\\}|$;
$\triangleright$ Number of participants

5: Set $t_{i}:=4\Delta((\mathtt{e}+2)x+1)+(k+1)i\Delta^{*}$,
$i\in\mathbb{N}_{\geq 0}$; $\triangleright$ First instance of Dolev-Strong
begins at $t_{0}$

6:

7:At timeslot $t_{i}$ for $i\in\mathbb{N}_{\geq 0}$ if $\mathtt{recend}=0$:
$\triangleright$ Begin $i^{\text{th}}$ instance of Dolev-Strong

8: Set $O_{p}=\emptyset$;

9: If $\mathtt{reclead}(M,i)\in\mathtt{id}(p)$ then: $\triangleright$ Propose
updated genesis block

10: Disseminate a genesis proposal $(b_{g}^{\prime},i)$ signed by
$\mathtt{reclead}(M,i)$ which is $M$-admissible;

11:

12:At timeslot $t_{i}+j\Delta^{*}$ for $i\in\mathbb{N}_{\geq 0}$ and
$j\in[1,k]$ if $\mathtt{recend}=0$:

13: For each message $m=y_{id_{1}^{\prime},\dots,id_{j}^{\prime}}$ in
$\mathtt{signed}(M,i,j)$: $\triangleright$ Multi-signed $M$-admissible
proposals

14: If $y\notin O_{p}$ and $j<k$:

15: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$, disseminate $m_{id}$;

16: If $y\notin O_{p}$, enumerate $y$ into $O_{p}$;

17:

18:At timeslot $t_{i}+k\Delta^{*}$ if $\mathtt{recend}=0$: $\triangleright$
End of $i^{\text{th}}$ instance of Dolev-Strong

19: If $O_{p}$ contains a single value $(b_{g}^{\prime},i)$ then:
$\triangleright$ Send votes for updated genesis block

20: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(S^{*},\mathtt{T},id)>0$:

21: Let $c:=\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)$;

22: Disseminate output vote $V$ with $\mathtt{b}(V)=b_{g}^{\prime}$,
$\mathtt{c}(V)=c$, $\mathtt{id}(V)=id$;

23: Set $\mathtt{recend}:=1$. $\triangleright$ Terminate

###  9.6. Certificates of guilt and consistency

In this section, we show that the protocol is consistent for $\rho$-bounded
adversaries when $\rho<1/3$. In the next section, we show liveness.

Further terminology. We let $\mathcal{M}^{*}$ be the set of all messages
disseminated during an execution. If $id\in\mathtt{id}(p)$ and $p$ is
Byzantine, then we say $id$ is Byzantine.

###### Lemma 9.1.

If a certificate of guilt in $\mathcal{M}^{*}$ implicates $id$, then $id$ is
Byzantine.

###### Proof.

Let $(Q,Q^{\prime})$ be a certificate of guilt for epoch $e$, and let
$b,b^{\prime},v,v^{\prime}$ be as specified in the definition of certificates
of guilt in Section 9.4. Suppose there exist votes $V\in Q$ and $V^{\prime}\in
Q^{\prime}$ with $\mathtt{id}(V)=\mathtt{id}(V^{\prime})=id$ and let $p$ be
such that $id\in\mathtt{id}(p)$. If $v=v^{\prime}$, then the claim is
immediate because honest players do not vote for two different blocks in the
same view. If $v^{\prime}>v$, then the claim follows because, if $p$ is
honest, then it must set $Q^{+}:=v$ upon disseminating $V$ while in view $v$,
and then could not disseminate $V^{\prime}\in Q^{\prime}$ because
$\mathtt{vprev}(Q^{\prime})<v$, i.e. $p$ would not regard
$\mathtt{b}(Q^{\prime})$ as admissible when voting in view $v^{\prime}$. ∎

Next, recall that $\rho^{*}<2/3$. In particular, every quorum certificate must
contain at least one vote from an honest player. Thus, for $s=2,3$, no stage
$s$ QC can be formed for a block $b$ without some honest player previously
seeing a stage $s-1$ QC for $b$. Similarly, no stage 1 QC can be formed for a
block $b$ without some honest player seeing a stage 1 QC for $b$’s parent.

###### Lemma 9.2.

Suppose two incompatible blocks for epoch $e$ are both
$\mathcal{M}^{*}$-confirmed. Then $\mathcal{M}^{*}$ contains a certificate of
guilt for epoch $e$. Let $t$ be the first timeslot at which any honest player
enters epoch $e+1$ or sets their local value $\mathtt{rec}:=1$ (i.e. starts
the recovery procedure). If message delay prior to GST is bounded by
$\Delta^{*}$, then all active honest players receive a certificate of guilt
for epoch $e$ by time $t+2\Delta^{*}$.

###### Proof.

In the argument that follows, we restrict attention to blocks $b$ with
$\mathtt{e}(b)=e$. Given the conditions in the statement of the lemma, there
must exist a least $v$, a least $v^{\prime}\geq v$, and incompatible blocks
$b$ and $b^{\prime}$ which both receive stage 1, 2 and 3 QCs in
$\mathcal{M}^{*}$, such that $\mathtt{v}(b)=v$ and
$\mathtt{v}(b^{\prime})=v^{\prime}$. Let $v^{\prime\prime}$ be the least view
$\geq v$ such that some block $b^{\prime\prime}$ that is incompatible with $b$
(with $\mathtt{v}(b^{\prime\prime})=v^{\prime\prime}$) receives a stage 1 QC,
$Q_{1}$ say, that is seen by some honest player $p_{1}$ before they enter
epoch $e+1$ or start the recovery procedure. As $b^{\prime}$ is one such
block, $v^{\prime\prime}\leq v^{\prime}$. Let $Q_{2}$ be a stage 2 QC for $b$
that is seen by an honest player $p_{2}$ before disseminating a stage 3 vote
during view $v$. Then $(Q_{2},Q_{1})$ is a certificate of guilt for epoch $e$
since, by our choice of $v^{\prime\prime}$, $\mathtt{vprev}(Q_{1})<v$.

It remains to show that $Q_{1}$ and $Q_{2}$ will be seen by all active honest
players by time $t+2\Delta^{*}$. If some first honest player enters epoch
$e+1$ or starts the recovery procedure at timeslot $t$, then all active honest
players do so by $t+\Delta^{*}$. This means $p_{i}$ (for $i\in\\{1,2\\}$, as
specified above) must enter epoch $e+1$ or start the recovery procedure by
$t+\Delta^{*}$. Player $p_{i}$ must therefore have seen $Q_{i}$ before
$t+\Delta^{*}$, and so $Q_{i}$ must be seen by all active honest players by
time $t+2\Delta^{*}$. All active honest players therefore see $Q_{1}$ and
$Q_{2}$ by time $t+2\Delta^{*}$, as required. ∎

The validating stake. Suppose there exists a unique
$\mathcal{M}^{*}$-confirmed block $b$ that is epoch $e$ ending. By the
_validating stake_ for epoch $e+1$, we mean the set of identifiers $id$ such
that $\mathtt{S}(\mathtt{S}^{*},\mathtt{Tr}(b),id)>0$.

###### Lemma 9.3.

PosT is consistent for $\rho$-bounded adversaries when $\rho<1/3$.

###### Proof.

This follows almost directly from Lemmas 9.1 and 9.2. Suppose the adversary is
$\rho$-bounded for $\rho<1/3$ and that there exists a least epoch $e$ that
sees a consistency violation, i.e. such that incompatible blocks $b$ and
$b^{\prime}$ with $\mathtt{e}(b)=\mathtt{e}(b^{\prime})=e$ are both
$\mathcal{M}^{*}$-confirmed. Because QCs for blocks in epoch $e$ require votes
from at least 2/3 of the validating stake for epoch $e$, any certificate of
guilt implicates at least 1/3 of the validating stake for epoch $e$. By Lemma
9.2, $\mathcal{M}^{*}$ contains a certificate of guilt for epoch $e$, which
implicates at least 1/3 of the validating stake for epoch $e$. By Lemma 1, all
the implicated identifiers must be Byzantine. This gives the required
contradiction. ∎

###  9.7. Establishing liveness

Suppose the adversary is $\rho$-bounded for $\rho<1/3$. Lemma 9.3 establishes
consistency in this case, which means that, if two honest players are in the
same epoch $e$, then their local values $\mathtt{lead}(M,e,v)$ agree for all
$v$. We may therefore refer unambiguously to the value $\mathtt{lead}(e,v)$
for each $e,v$. Let $k^{*}$ take the minimum value $\geq 1$ such that, for any
$e$ and $v$, at least one $v^{\prime}\in(v,v+k^{*}]$ must satisfy the
condition that $\mathtt{lead}(e,v^{\prime})$ is honest. Note that $k^{*}$ is a
function of $x^{*}$ (the maximum number of validators), but is independent of
$\Delta^{*}$.

###### Lemma 9.4.

Suppose the adversary is $\rho$-bounded for $\rho<1/3$. Then the protocol is
live with respect to a liveness parameter $T_{l}$ that is $O(k^{*}\Delta)$.

###### Proof.

The proof shows (essentially) that each honest leader after GST confirms a new
block of transactions, but is complicated slightly by transitions at the end
of an epoch. Recall that, by the assumptions of the quasi-permissionless
setting, honest validators are always active.

Suppose the adversary is $\rho$-bounded for $\rho<1/3$. As noted above, we can
refer unambiguously to the value $\mathtt{lead}(e,v)$ for each $e,v$. Suppose
that the environment sends a transaction $\mathtt{tr}$ to an honest player at
$t$ and let $t_{0}=\text{max}\\{t,\text{GST}\\}+\Delta$. Let $e$ be the
greatest epoch that any honest player is in at $t_{0}$, and suppose that all
active honest players are in view $v_{0}$ at $t_{0}$. Let $v_{1}>v_{0}$ be the
least such that $\mathtt{lead}(e,v_{1})$ is honest (noting that $v_{1}\leq
v_{0}+k^{*}$). There are now various possibilities to consider. If no honest
player enters epoch $e+1$ by timeslot $4v_{1}\Delta+3\Delta$, then let $Q^{+}$
be the lock amongst honest players at time $4v_{1}\Delta-\Delta$ such that
$\mathtt{v}(Q^{+})$ is greatest. The leader for view $v_{1}$ will receive
$Q^{+}$ and $\mathtt{tr}$ by time $4v_{1}\Delta$. Assuming $\mathtt{tr}$ has
not already been confirmed, this leader will therefore propose a block
containing $\mathtt{tr}$ that is admissible for all honest players (when they
judge admissibility at timeslot $4v_{1}\Delta+\Delta$). All honest players
will then produce stage 1, 2 and 3 votes for that block $b$, and $b$ will be
confirmed by the end of view $v_{1}$.

If $\mathtt{h}(b)\leq(e+1)x$ then $\mathtt{tr}$ will also be confirmed by the
end of view $v_{1}$, and so the argument is complete in that case. If either
$\mathtt{h}(b)>(e+1)x$ or some honest player enters epoch $e+1$ before
timeslot $4v_{1}\Delta+3\Delta$, all honest players will be in epoch $e+1$ by
timeslot $4(v_{1}+1)\Delta$. In this case, let $v_{2}>v_{1}+1$ be the least
such that $\mathtt{lead}(e+1,v_{2})$ is honest (noting that $v_{2}\leq
v_{1}+1+k^{*}$). Then all honest players will be in epoch $e+1$ for the
entirety of view $v_{2}$. Let $Q^{+}$ be the lock amongst honest players at
time $4v_{2}\Delta-\Delta$ such that $\mathtt{v}(Q^{+})$ is greatest. The
leader for view $v_{2}$ will receive $Q^{+}$ and $\mathtt{tr}$ by time
$4v_{2}\Delta$. Assuming $\mathtt{tr}$ has not already been confirmed, this
leader will therefore propose a block containing $\mathtt{tr}$ that is
admissible for all honest players at timeslot $4v_{2}\Delta+\Delta$. All
honest players will then produce stage 1, 2 and 3 votes for that block, and
the block (and $\mathtt{tr}$) will be confirmed by the end of view $v_{2}$. ∎

###  9.8. Proving that the recovery procedure carries out slashing

###### Lemma 9.5.

Suppose the adversary is $\rho^{*}$-bounded for $\rho^{*}<2/3$ and that all
message delays prior to GST are at most $\Delta^{*}$. If a consistency
violation occurs in some least epoch $e$, then the recovery procedure produces
a unique updated genesis block $b_{g}^{\prime}$ such that:

  * •

$\mathtt{Tr}(b_{g}^{\prime})$ contains a certificate of guilt that implicates
at least 1/3 of the validating stake for epoch $e$.

  * •

$b_{g}^{\prime}$ receives output votes from more than half the validating
stake for epoch $e$ that is not implicated by certificates of guilt in
$\mathtt{Tr}(b_{g}^{\prime})$.

###### Proof.

The argument resembles that in Section 9.2. We again use the fact, implied by
the assumptions of the quasi-permissionless setting, that honest validators
are always active.

Assume the conditions in the statement of the lemma, and let $b$ be an epoch
$e-1$ ending block that is $\mathcal{M}^{*}$-confirmed. Because $e$ is the
least epoch in which a consistency violation occurs, $b$ is uniquely
determined. Set $\mathtt{T}:=\mathtt{Tr}(b)$. Let $id_{0},\dots,id_{k-1}$ be
the enumeration of the identifiers $id$ such that
$\mathtt{S}(\mathtt{S}^{*},\mathtt{T},id)>0$ as specified in Section 9.5, and
set $\mathtt{Id}:=\\{id_{0},\dots,id_{k-1}\\}$. Let $P$ be the set of players
with identifiers in $\mathtt{Id}$. For $i\in\mathbb{N}_{\geq 0}$, define
$\mathtt{reclead}(i)$ to be the identifier $id_{j}$, where $j=i\text{ mod }k$.
Note that $\mathtt{reclead}(i)=\mathtt{reclead}(M,i)$ however $M$ is locally
defined during the recovery procedure for honest $p\in P$.

For each $i\in\mathbb{N}_{\geq 0}$, let $t_{i}$ be as defined in Algorithm 2,
so that the $i^{\text{th}}$ instance of Dolev-Strong begins at time $t_{i}$.
Note that the recovery procedure might not be triggered by time $t_{i}$. If
$p=\mathtt{reclead}(i)$ is honest, and if $p$ has not received a certificate
of guilt for epoch $e$ by $t_{i}$, then $O_{p^{\prime}}$ will remain empty for
every honest $p^{\prime}\in P$ during the $i^{\text{th}}$ instance of Dolev-
Strong, and no honest player in $P$ will output a vote in this instance. If
$p=\mathtt{reclead}(i)$ is honest, and if $p$ has received a certificate of
guilt for epoch $e$ by $t_{i}$ and has not terminated the recovery procedure
by time $t_{i}$, then $p$ will disseminate a genesis proposal
$(b_{g}^{\prime},i)$ which is $M$-admissible, where $M$ is as locally defined
for any honest $p^{\prime}\in P$ during the recovery procedure.
$\mathtt{Tr}(b_{g}^{\prime})$ will contain a certificate of guilt $\mathtt{G}$
implicating at least 1/3 of the validating stake for epoch $e$. Every honest
player $p^{\prime}\in P$ will trigger the recovery procedure by time
$t_{i}+\Delta^{*}$ and will enumerate this single value $(b_{g}^{\prime},i)$
into $O_{p^{\prime}}$ during this instance of Dolev-Strong. All honest players
in $P$ will then produce output votes for $b_{g}^{\prime}$ in this instance.
Since the honest players control a majority of the validating stake for epoch
$e$ that is not implicated by $\mathtt{G}$ (using that $\rho^{*}<2/3$),
$b_{g}^{\prime}$ receives output votes from more than half the validating
stake for epoch $e$ that is not implicated by certificates of guilt in
$\mathtt{Tr}(b_{g}^{\prime})$.

If $p=\mathtt{reclead}(i)$ is Byzantine and if $p^{\prime}\in P$ is honest and
enumerates some value into $O_{p^{\prime}}$ during the $i^{\text{th}}$
instance of Dolev-Strong, it remains to show that every honest
$p^{\prime\prime}\in P$ will do the same. This suffices to show that either
all honest players in $P$ will vote for a common updated genesis block and end
the recovery procedure, or none will. The argument is the same as in Section
9.2. There are two cases to consider:

  * •

Case 1. Suppose that some honest $p^{\prime}\in P$ first enumerates $y$ into
$O_{p^{\prime}}$ at time $t_{i}+j\Delta^{*}$ with $j<k$. In this case,
$p^{\prime}$ receives a message of the form
$m=y_{id_{1}^{\prime},\dots,id_{j}^{\prime}}\in\mathtt{Signed}(M,i,j)$ at
$t_{i}+j\Delta^{*}$. Player $p^{\prime}$ then adds their signature to form a
message with $j+1$ distinct signatures and disseminates this message. This
means every honest player $p^{\prime\prime}\in P$ will enumerate $y$ into
$O_{p^{\prime\prime}}$ by time $(j+1)\Delta^{*}$.

  * •

Case 2. Suppose next that some honest $p^{\prime}$ first enumerates $y$ into
$O_{p^{\prime}}$ at time $t_{i}+k\Delta^{*}$. In this case, $p^{\prime}$
receives a message of the form
$m=y_{id_{1}^{\prime},\dots,id_{k}^{\prime}}\in\mathtt{Signed}(M,i,k)$ at time
$t_{i}+k\Delta^{*}$, which has $k$ distinct signatures attached. At least one
of those signatures must be from an honest player $p^{\prime\prime}$, meaning
that Case 1 applies w.r.t. $p^{\prime\prime}$.

∎

A further relaxation of the synchronicity assumption. As foreshadowed in
footnote 15, bounded message delays are required only during a limited period
around the time of an attack. Specifically, suppose there exists a consistency
violation in some least epoch $e$. Let $t_{0}^{*}$ be the least timeslot at
which some honest player enters epoch $e+1$ or triggers the recovery
procedure. While the statements of Lemmas 9.2 and 9.5 assume for the sake of
simplicity that message delays prior to GST are always bounded by
$\Delta^{*}$, the following weaker assumption suffices for the proofs: If $p$
disseminates a message at any timeslot $t_{1}^{*}$, and if honest $p^{\prime}$
is active at $t_{2}^{*}:=\text{max}\\{t_{1}^{*},t_{0}^{*}\\}+\Delta^{*}$, then
$p^{\prime}$ receives that message at a timeslot $\leq t_{2}^{*}$.

###  9.9. Completing the proof of Theorem 5.1: Establishing the EAAC property

To complete the proof of Theorem 5.1, we must specify $t_{f}$, as well as the
investment and valuation functions.

Defining $t_{f}$. If there is a consistency violation in some least epoch $e$,
let $t_{f}$ be any timeslot after which all honest players active during epoch
$e$ have terminated the recovery procedure and outputted an updated genesis
block $b_{g}^{\prime}$. By Lemma 9.5, such a timeslot $t_{f}$ exists, and
$b_{g}^{\prime}$ is uniquely defined and can be determined from the locally
defined $M$ values of active honest players at $t_{f}$.

The canonical PoS investment function. Let $C$ be the cost of each unit of
stake. To specify $\mathtt{R}(p,t)$, we define $\mathtt{R}(id,t)$ for each
identifier $id$ and then set
$\mathtt{R}(p,t)=\sum_{id\in\mathtt{id}(p)}\mathtt{R}(id,t)$. The rough idea
is that a player’s investment should correspond to the value of their
validating stake, the value of any of their stake which is no longer
validating but remains in escrow, and the value of any of their stake which
was lost to slashing. Formally, for a timeslot $t$, denote by $e(t)$ the
greatest epoch such that, for all $e\leq e(t)$, there exists a unique epoch
$e$ ending block that is confirmed for some honest player at $t$. (If no such
epoch exists, define $b_{1}(t)$ and $b_{2}(t)$ as the genesis block.) Let
$b_{1}(t)$ be the unique epoch $e(t)$ ending block that is confirmed for some
honest player at $t$, and $b_{2}(t)$ the unique epoch $e(t)-1$ ending block
that is confirmed for some honest player at $t$. (Or if $e(t)=0$, define
$b_{2}(t)$ as the genesis block.) First, suppose that no honest player has
triggered the recovery procedure by $t$. Then, if either:

  * (i)

the identifier is currently a validator (i.e.,
$\mathtt{S}(\mathtt{S}^{*},\mathtt{Tr}(b_{1}(t)),id)>0$);

  * (ii)

the identifier no longer controls a validator but their stake has not yet been
removed from escrow (i.e.,
$\mathtt{S}(\mathtt{S}^{*},\mathtt{Tr}(b_{2}(t)),id)>0$); or

  * (iii)

the identifier has been slashed (i.e., $\mathtt{Tr}(b_{1}(t))$ includes a
certificate of guilt implicating $id$),

we define $\mathtt{R}(id,t)=N/x^{*}$; otherwise, $\mathtt{R}(id,t)=0$.

Now suppose that some honest player has triggered the recovery procedure by
$t$, due to a consistency violation in epoch $e(t)+1$. Here, because the
validating stake from epoch $e(t)-1$ need not still be in escrow, we consider
only $b_{1}(t)$. That is, we define $\mathtt{R}(id,t)=N/x^{*}$ if (i) or (iii)
holds, and $\mathtt{R}(id,t)=0$ otherwise.

This investment function is $\Gamma$-liquid in the sense of Section 3.2,
provided $\Gamma$ is chosen to be larger than the maximum time needed to
complete an epoch after GST (which is proportional to $\Delta\cdot
x>\Delta^{*}$).

The canonical valuation function. If there is no consistency violation at
timeslots $\leq t$, then, for any set of players $P$, we define the valuation
function as the value (at the market price $C$) of the investments made (and
not already recouped) by $P$:

$v(P,t,\\{\mathtt{R}(p,t)\\}_{p\in P},C,\mathcal{M})):=\sum_{p\in
P}\mathtt{R}(p,t)\cdot C,$

where $\mathcal{M}$ specifies the sets of messages received by each player by
timeslot $t$ in the execution.

If the event of a consistency violation, the valuation function should
discount stake that has been slashed. Formally, consider a consistency
violation and let $t_{f}$ and $b_{g}^{\prime}$ be as specified above. Let
$\mathtt{Id}$ be the set of identifiers that are not implicated by any
certificates of guilt in $\mathtt{Tr}(b_{g}^{\prime})$. For any set of players
$P$ and $t\geq t_{f}$, we set:

$v(P,t,\\{\mathtt{R}(p,t)\\}_{p\in P},C,\mathcal{M})):=\sum_{p\in
P}\sum_{id\in\mathtt{id}(p)\cap\mathtt{Id}}\mathtt{R}(id,t)\cdot C,$

where $\mathcal{M}$ specifies the sets of messages received by each player by
timeslot $t$ in the execution. This valuation function is consistency-
respecting in the sense of Section 3.2. (It is generally undefined following a
consistency violation, up until the timeslot $t_{f}$ at which the recovery
procedure completes.)

Because Lemma 9.1 establishes that certificates of guilt can implicate only
Byzantine identifiers, condition (a) in Definition 3.1 is satisfied. By Lemma
9.5, in the case of a consistency violation in some least epoch $e$,
$\mathtt{Tr}(b_{g}^{\prime})$ contains certificates of guilt for at least 1/3
of the validating stake for epoch $e$, so condition (b) in Definition 3.1 is
also satisfied and the protocol is $(\alpha,\rho,\rho^{*})$-EAAC for
$\alpha=\max\\{0,(\rho^{*}-\tfrac{1}{3})/\rho^{*}\\}$. ∎

How is the impossibility result in Theorem 4.2 avoided? As discussed at the
end of Section 8, the proof of Theorem 4.2 shows that non-trivial EAAC
protocols are possible only if the protocol’s liveness parameter or the
investment function’s liquidity parameter scales with the worst-case message
delay. In Theorem 5.1, crucially, we do assume a finite bound $\Delta^{*}$ on
the worst-case message delay. The liveness parameter $T_{l}$ of the protocol
scales only with $\Delta$ and the maximum number $x^{*}$ of validators, and
thus may be arbitrarily smaller than the worst-case message delay
$\Delta^{*}$. The canonical PoS investment function, however, is
$\Gamma$-liquid only for values $\Gamma$ that exceed the minimum length of an
epoch, which is, by our choice of the number $x$ of blocks per epoch, at least
$4\Delta x>4\Delta^{*}$ timeslots. This delay, combined with our use of three
stages of voting (and using the fact that $\rho^{*}<2/3$), allows us to ensure
that any consistency violation is seen by honest players before those
responsible for it can cash out of their positions (with honest players
learning of a consistency violation in epoch $e$ within $2\Delta^{*}$
timeslots of any honest player completing the epoch).

### Acknowledgments

The research of the third author at Columbia University is supported in part
by NSF awards CCF-2006737 and CNS-2212745, and research awards from the Briger
Family Digital Finance Lab and the Center for Digital Finance and
Technologies.

## References

  * (1) Joseph Bonneau.  Why Buy When You Can Rent? - Bribery Attacks on Bitcoin-Style Consensus.  In Financial Cryptography and Data Security: 20th International Conference, pages 19–26. Springer, 2016.
  * (2) Ethan Buchman.  Tendermint: Byzantine fault tolerance in the age of blockchains.  PhD thesis, 2016.
  * (3) Ethan Buchman and Jae Kwon and Zarko Milosevic.  The latest gossip on BFT consensus.  arXiv preprint arXiv:1807.04938, 2018.
  * (4) Eric Budish.  The economic limits of bitcoin and the blockchain.  Technical report, National Bureau of Economic Research, 2018.
  * (5) Eric Budish.  Trust at scale: The economic limits of cryptocurrencies and blockchains.  Technical report, Becker Friedman Institute, 2023.
  * (6) Vitalik Buterin.  Slasher: A Punitive Proof-of-Stake Algorithm, 2014.  Accessed on 4th April, 2024.  URL: https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm.
  * (7) Vitalik Buterin.  Proof-of-stake: How I learned to love weak subjectivity, 2014.  Accessed on 8th February, 2024.  URL: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity.
  * (8) Vitalik Buterin.  A proof of stake design philosophy, 2016.  Accessed on 12th February, 2024.  URL: https://medium.com/@VitalikButerin/a-proof-of-stake-design-philosophy-506585978d51.
  * (9) Vitalik Buterin.  Minimal slashing conditions, 2017.  Accessed on 12th February, 2024.  URL: https://medium.com/@VitalikButerin/minimal-slashing-conditions-20f0b500fc6c.
  * (10) Vitalik Buterin and Virgil Griffith.  Casper the friendly finality gadget.  arXiv preprint arXiv:1710.09437, 2017.
  * (11) Christian Cachin, Rachid Guerraoui, and Luís Rodrigues.  Introduction to reliable and secure distributed programming.  Springer Science & Business Media, 2011.
  * (12) Miguel Castro, Barbara Liskov, et al.  Practical byzantine fault tolerance.  In OsDI, volume 99, pages 173–186, 1999.
  * (13) Jing Chen, Sergey Gorbunov, Silvio Micali, and Georgios Vlachos.  Algorand agreement: Super fast and partition resilient byzantine agreement.  IACR Cryptol. ePrint Arch., 2018:377, 2018.
  * (14) Jing Chen and Silvio Micali.  Algorand.  arXiv preprint arXiv:1607.01341, 2016.
  * (15) Pierre Civit, Seth Gilbert, and Vincent Gramoli.  Polygraph: Accountable byzantine agreement.  In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pages 403–413. IEEE, 2021.
  * (16) Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, and Jovan Komatovic.  As easy as abc: Optimal (a) ccountable (b) yzantine (c) onsensus is easy!  Journal of Parallel and Distributed Computing, 181:104743, 2023\.
  * (17) Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, and Adi Seredinschi.  Crime and punishment in distributed byzantine decision tasks.  In 2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS), pages 34–44. IEEE, 2022.
  * (18) Bram Cohen and Krzysztof Pietrzak.  The chia network blockchain.  2019\.
  * (19) Phil Daian, Rafael Pass, and Elaine Shi.  Snow white: Robustly reconfigurable consensus and applications to provably secure proof of stake.  In Financial Cryptography and Data Security: 23rd International Conference, pages 23–41. Springer, 2019.
  * (20) Soubhik Deb, Robert Raynor, and Sreeram Kannan.  STAKESURE: Proof of Stake Mechanisms with Strong Cryptoeconomic Safety.  arXiv preprint arXiv:2401.05797, 2024.
  * (21) Danny Dolev and Raymond Strong.  Authenticated algorithms for Byzantine agreement.  In SIAM Journal on Computing, vol 12, 4, pages 656-666, SIAM, 1983.
  * (22) Cynthia Dwork, Nancy A. Lynch, and Larry Stockmeyer.  Consensus in the presence of partial synchrony.  Journal of the ACM, 35(2):288–323, 1988.
  * (23) Joshua S. Gans and Hanna Halaburda.  “Zero cost” majority attacks on permissionless blockchains.  SSRN preprint 4505460, 2023.
  * (24) Juan A Garay, Aggelos Kiayias, and Nikos Leonardos.  The bitcoin backbone protocol: Analysis and applications.  2018\.
  * (25) Hanna Halaburda, Guillaume Haeringer, Joshua Gans, and Neil Gandal.  The microeconomics of cryptocurrencies.  Journal of Economic Literature, 60(3):971–1013, 2022.
  * (26) Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In Annual International Cryptology Conference, pages 357–388. Springer, 2017.
  * (27) Jae Kwon.  Tendermint: Consensus without Mining.  2014\.
  * (28) Leslie Lamport, Robert Shostak, and Marshall Pease.  The Byzantine generals problem.  In Concurrency: the works of Leslie Lamport, pages 203–226, 2019.
  * (29) Jacob Leshno, Rafael Pass, and Elaine Shi.  Can open decentralized ledgers be economically secure?  IACR Cryptol. ePrint Arch., 2023:1516, 2023.
  * (30) Andrew Lewis-Pye and Tim Roughgarden.  Permissionless consensus.  arXiv preprint arXiv:2304.14701, 2023.
  * (31) Nancy A Lynch.  Distributed algorithms.  Elsevier, 1996.
  * (32) Satoshi Nakamoto et al.  Bitcoin: A peer-to-peer electronic cash system.(2008), 2008.
  * (33) Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman.  Cogsworth: Byzantine view synchronization.  2021\.
  * (34) Joachim Neu, Ertem Nusret Tas, and David Tse.  The availability-accountability dilemma and its resolution via accountability gadgets.  In International Conference on Financial Cryptography and Data Security, pages 541–559. Springer, 2022.
  * (35) Alejandro Ranchal-Pedrosa and Vincent Gramoli.  Zlb: A blockchain to tolerate colluding majorities.  arXiv preprint arXiv:2007.10541, 2020.
  * (36) Alex Shamis, Peter Pietzuch, Burcu Canakci, Miguel Castro, Cédric Fournet, Edward Ashton, Amaury Chamayou, Sylvan Clebsch, Antoine Delignat-Lavaud, Matthew Kerner, et al.  $\\{$IA-CCF$\\}$: Individual accountability for permissioned ledgers.  In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), pages 467–491, 2022.
  * (37) Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, and Pramod Viswanath.  Bft protocol forensics.  In Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pages 1722–1743, 2021.
  * (38) Srivatsan Sridhar, Dionysis Zindros, and David Tse.  Better safe than sorry: Recovering after adversarial majority.  arXiv preprint arXiv:2310.06338, 2023.
  * (39) Ertem Nusret Tas, David Tse, Fangyu Gai, Sreeram Kannan, Mohammad Ali Maddah-Ali, and Fisher Yu.  Bitcoin-enhanced proof-of-stake security: Possibilities and impossibilities.  In 2023 IEEE Symposium on Security and Privacy (SP), pages 126–145. IEEE, 2023.
  * (40) Ertem Nusret Tas, David Tse, Fisher Yu, and Sreeram Kannan.  Babylon: Reusing bitcoin mining to enhance proof-of-stake security.  arXiv preprint arXiv:2201.07946, 2022.
  * (41) Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham.  HotStuff: Bft consensus with linearity and responsiveness.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347–356, 2019.

##  Appendix A Modeling PoW in Bitcoin

In this section, we show how to model proof-of-work, as used in the Bitcoin
protocol, using the permitter formalism. The basic idea is that, at each
timeslot, a player should be able to request permission to publish a certain
block, with the permitter response depending on the player’s resource balance
(i.e., hashrate). To integrate properly with the “difficulty adjustment”
algorithm used by the Bitcoin protocol to regulate the average rate of block
production (even as the total hashrate devoted to the protocol fluctuates), we
define the permitter oracle so that its responses can have varying “quality.”
Each PoW oracle response will be a 256-bit string $\tau$, and we can regard
the quality of $\tau$ as the number of 0s that it begins with.

An example. As an example, suppose that $\mathtt{R}^{O}(p,t)=5$. Then $p$
might send a single query $(5,\sigma)$ at timeslot $t$, and this should be
thought of as a request for a PoW for $\sigma$ (which could represent a block
proposal, for example). If $p$ does not get the response that it’s looking
for, it might, at a later timeslot $t^{\prime}$ with
$\mathtt{R}^{O}(p,t^{\prime})=5$, send another query $(5,\sigma)$ to the PoW
oracle.

Formal details. We consider a single-use permitter. All queries to the
permitter must be of the form $(b,\sigma)$, where $\sigma$ is any finite
string. As already stipulated in Section 2.3, the fact that $O$ is a single-
use permitter means that $p$ can send the queries
$(b_{1},\sigma_{1}),\dots(b_{k},\sigma_{k})$ at the same timeslot $t$ only if
$\sum_{i=1}^{k}b_{i}\leq\mathtt{R}^{O}(p,t)$. If $p$ submits the query
$(b,\sigma)$ to the permitter at $t$, then the permitter independently samples
$b$-many 256-bit strings uniformly at random and lets $\tau$ be the
lexicographically smallest of these sampled strings. Player $p$ then receives
the response $r:=(\sigma,\tau)$ signed by the oracle.