WorksComputer Science
Playing the SMR Game with Existential Honesty
Abstract
State machine replication protocols are usually proven secure in the honest-Byzantine setting, which requires an honest supermajority of validators. Deployed systems offer no such guarantee: validators participate for profit and may deviate from the protocol whenever doing so increases their gains. In our work, every validator is rational or Byzantine, and none is honest. Rational validators may collude with each other and with the Byzantine ones, who may also bribe them to deviate. Known impossibility results show that, without honest validators, clients that decide whether to accept a transaction based on a non-interactive certificate and without further communication cannot be kept safe. To bypass these results, we let clients relay the certificates they receive to full nodes and wait before confirming transactions. We also assume that one full node, whose identity is unknown, is honest and always online. Under this assumption, we build a finalization layer over any certifiable quorum-based protocol in a synchronous network. Clients run an existing freezing gadget and fetch past certificates from the honest full node, which makes the protocol always-safe: no two honest clients confirm conflicting ledgers, for any strategy of the validators. We incentivize participation through rewards, which the adversary may use to bribe rational validators into censoring transactions. In this setting, we formalize censorship and characterize it tightly: paying only with his rewards, the adversary censors less than a \bw fraction of the available fees at each height, where \bw is the fraction of the quorum he signs, and every coin of censorship beyond that comes from his own funds.
Introduction
State machine replication (SMR) lets a set of validators agree on a single ordered log of transactions, and it is the core of proof-of-stake blockchains that today secure hundreds of billions of dollars. Quorum-based SMR protocols such as PBFT [11], Tendermint [10], and HotStuff [36] are typically analyzed in the honest-Byzantine setting: every validator either follows the protocol or deviates arbitrarily. These protocols remain safe and live as long as fewer than a third of the validators are Byzantine, so their security rests on an honest supermajority. Clients rely on the same assumption when they accept a transaction from a quorum certificate: the quorum is guaranteed to contain honest validators that have followed the protocol.
This setting may not describe how validators behave in deployed proof-of-stake systems. Validators participate for profit: they follow the protocol when doing so pays, and may deviate when they can earn more by doing so. An adversary may offer them a bribe to deviate, or validators may collude by pooling their stake and profiting from a double-spend. Thus, the honest supermajority may fail not because validators are intrinsically malicious, but because deviating has become more profitable than following the protocol. An analysis in the honest-Byzantine setting provides no guarantees in this case. This raises the question we study: what happens to the security of a quorum-based SMR protocol when every validator is rational or Byzantine, and no validator is assumed to be honest?
Related Work
Rational and Byzantine validators. BAR [3] introduced a model with Byzantine, altruistic, and rational participants, and a line of work since then has studied consensus with rational validators [4, 5, 22, 18]. These works either assume that rational validators act independently or rule out collusion between rational and Byzantine validators against clients. Abraham et al. [1, 2] introduced solution concepts that allow coalitions of rational and Byzantine players, and TRAP [25] used these concepts to solve consensus on a single value by baiting rational players into exposing a coalition. In TRAP, the single-shot setting bounds the amount that can be double-spent against clients. Multi-shot state machine replication has no such bound, as shown by CoBRA [6]. CoBRA instead considers quorum-based SMR with silent clients and shows that, without honest validators, safety is impossible even in a synchronous network. Here, a silent client is one that decides whether to confirm a transaction based only on the certificates it receives, without communicating with other parties. Such a client cannot tell whether a certificate it sees belongs to a history that conflicts with one another client has accepted.
Safety beyond the honest majority. Another line of work keeps clients safe when Byzantine validators exceed the classic thresholds, by changing what clients do. Sridhar et al. [31] show that the achievable resilience depends on the client model, whether clients are sleepy or always on, and silent or communicating, and characterize it for each combination. In flexible BFT [21, 23], clients trade liveness for safety by requiring larger quorums. Better Safe than Sorry [32] introduces the freezing gadget we build on: a client that sees two conflicting histories confirms neither, which keeps clients safe under an adversarial majority, and a recovery procedure restores progress once an honest majority returns. Sridhar et al. prove the gadget safe against any number of adversarial validators when past messages reach a client that wakes [31 Theorem 4], and note that querying online parties provides this. Our safety theorem instantiates theirs with one honest full node. In both works liveness is lost while the adversary holds the majority, and in a purely Byzantine model this cannot be avoided, since Byzantine validators can simply stop voting.
Accountability and recovery. Accountable protocols [13, 30, 14, 24] identify the validators responsible for a safety violation so that their stake can be slashed, and recoverable protocols [26, 17, 20] restore a consistent state after a violation. Both act after the violation. Punishment deters a rational validator only when the gain from an attack is smaller than the stake it risks, and in multi-shot SMR the gain from a double-spend has no natural bound.
Censorship. The cost of censorship by an outside briber has been studied for a single proposer [16], and concurrent proposers raise it [29, 33, 35]; colluding proposers are left open [29]. CoBRA [6] observes that Byzantine validators can use their participation rewards to bribe rational ones. We quantify this effect: the share of the fees that the adversary earns by signing is exactly what he can spend on censorship at every height.
Changing committees. A committee that has withdrawn its stake can sign a competing history at no cost. Snow White [15 Theorem 2], Tas et al. [34 Theorem 1] and Lewis-Pye and Roughgarden [19 Theorem 10.1] show that a client that joins late cannot then identify the correct history without further trust. Deployed systems therefore require a recent checkpoint [7] and bound the trusting period of light clients by the unbonding period [9]. We carry this bound over to rational validators and an honest full node, and show that it is exact.
Our Work
The lines of work above leave a gap. Work on rational and Byzantine validators models profit-driven validators that may collude, but it retains honest validators; CoBRA shows that, with silent clients, such an assumption is necessary. Work on accountability, recovery, and safety beyond the Byzantine threshold treats every validator that is not honest as Byzantine, and therefore gives up liveness while such validators hold a majority. Our work lies in the middle: we keep the Byzantine validators within the resilience of the underlying protocol, while every other validator is rational and may collude with the adversary; none is honest.
Assumptions. Within these limits, we ask what minimal assumptions at the client level suffice to solve SMR. We make two assumptions, each of which removes a known impossibility. First, the network is synchronous with a known bound , and clients communicate: a client relays every certificate it sees to the full nodes and waits before confirming. CoBRA shows that, without honest validators, no protocol is secure under partial synchrony [6 Theorem 3.1], and that even under synchrony, clients cannot remain silent when the number of rational and Byzantine validators exceeds the quorum threshold [6 Theorem 3.5]. Synchrony escapes the first result, and a client that relays certificates and waits a known multiple of falls outside the second. Second, we assume the existence of full nodes that store the certificates they receive and provide them to clients on request. We assume existential honesty: at least one full node is honest and has been online since the start of the execution, every client can reach it, and no party knows which one it is. Sleepy clients cannot be kept both safe and live once half of the validators are adversarial [31 Theorem 3], while always-on clients can [31 Corollary 3]; the honest full node is an always-on party that sleepy clients consult. Full nodes hold no stake and cast no votes, and an honest validator that stores and serves certificates could play the role of this full node, so existential honesty is weaker than assuming one such honest validator.
Contributions. We formulate an SMR model in which every validator is rational or Byzantine: rational validators may collude with the adversary and accept his bribes, clients are sleepy, and the only honest party is an always-on full node whose identity is unknown. The first two contributions concern a static committee, where clients may sleep arbitrarily long and join at any time; the third lets the committee change, which forces a bound on how long clients may sleep.
A tight characterization of censorship. We define the adversary’s bandwidth as the fraction of a quorum certificate that he signs. Paying only with the rewards of a height, he censors less than his bandwidth times the fee value available, and every further unit of censored fees costs him a unit of his own budget, tightly (Theorem 2). Conflicting certificates cost him more than a validator’s stake minus one block reward (Lemma 1), so a smaller budget never freezes a client, and a freeze is permanent. Transactions above the resulting fee threshold are included within a bounded number of certified heights (Corollary 1 and Theorem 3).
An always-safe finalization layer. We build a finalization layer that runs on top of any certifiable quorum-based protocol under synchrony and changes only how ledgers are finalized (§ 3). Clients use the freezing gadget of [32]: they relay every certificate to the full nodes, wait , and confirm a ledger only if no conflicting ledger reaches them. Full nodes serve past certificates to clients that were offline. Adapting [31 Theorem 4], no two honest clients confirm conflicting ledgers, whatever the validators do (Theorem 1).
An extension to dynamic committees. We extend the construction to committees that change every epoch (§ 5). Safety holds for every client, whenever it joins. Liveness holds for a client that sleeps no longer than the number of epochs for which stake stays slashable (Theorem 5). Adapting the classical lower bound for long-range attacks, we show that this threshold is exact when a committee may choose its successor, even with an honest full node and against any positive budget (Theorem 6).
Organization. Section 2 fixes the model and the definitions. Section 3 gives the construction for the static validator set and Section 4 analyzes it. Section 5 extends the construction to changing committees, and Section 6 discusses its limits. The proofs are in the appendix.
Model
System Model
We consider three types of actors: validators, clients, and full nodes. We define the three types of actors precisely below.
Validators. Validators run the SMR protocol to maintain an ordered ledger of transactions. In Section 3, we consider a static setting, in which there is a fixed set of validators known to all parties. In Section 5, we consider a dynamic setting, in which the execution is divided into epochs, and we denote the validator committee of epoch by . In both settings, each validator holds a signing key pair, and every party knows the public key of every validator. Validators are always awake. Each validator locks coins as stake. We model an entity that locks coins as controlling validators.
Full nodes. Full nodes store certificates, relay them, and send them to any party that requests them. They hold no stake, cast no votes, and earn no rewards. They are not registered as part of the system and therefore require no PKI; their number is unbounded and unknown.
Clients. Clients use the ledger by holding coins, submitting transactions, and deciding whether to accept transactions, but they do not participate in the execution of . An honest client submits a transaction by sending it to every validator. Clients are sleepy: they may remain offline for extended periods and receive no messages while asleep. Clients communicate with validators and full nodes, but not with each other. We assume that at least one full node, which we denote , is honest and has been awake since the beginning of the execution, and that it and every client can reach each other. No party knows which full node is . We call this assumption existential honesty.
Time and network. Time proceeds in rounds, and parties have synchronized clocks. The network is synchronous with a known delay : a message sent at round to a party reaches by round , provided is awake from round to round . A sleeping party receives nothing, and messages it missed are not delivered when it wakes. A party multicasts a message by sending it to every party it communicates with.
Assumptions. We assume unforgeable digital signatures and collision resistant hash functions. Moreover, we assume that a genesis block , available to every party, specifies the initial validators, their public keys, and their stake.
Adversarial model. In the static setting, ; in the dynamic setting, every committee satisfies . In either case, validators are Byzantine and the remaining validators are rational. Byzantine validators may behave arbitrarily, while rational validators maximize their monetary profit, which we define precisely in Section 2.3. Rational validators may collude with one another and with the adversary, accept bribes from the adversary, and deviate from the protocol whenever doing so increases their profit.
The adversary controls all Byzantine validators and may corrupt any number of clients and of full nodes other than . He controls message delivery subject to the synchronous bound and is rushing: in each round, he observes the messages sent by other parties before choosing his own actions. The adversary starts with a budget of coins that are not staked. He also receives the rewards of his validators, and we write for the reward he receives from the block of height . Given enough heights, saved rewards pay for any finite attack. We therefore charge each side payment to the height of the action it buys, whenever it is paid, and measure the payments charged to height against . Any excess is drawn from . We write for the amount drawn at height , so that . Fees that the adversary pays on his own transactions count as side payments.
Definition 1 (Repeatable attack). An adversarial strategy is repeatable at height if , that is, if the side payments it makes at height are at most .
A repeatable strategy can run at every height. A strategy that is not repeatable draws on , which rewards do not replenish.
We make one assumption on how certificates are formed, which we call adversarial participation. The adversary chooses how many of his validators, , sign the certificate of a block, and their signatures are included. A rational signer of a block compares signing with signing extended by the transactions it holds. The rational validators can certify the second block without the adversary, and it pays each signer of its fees. A rational validator recruited to replace a signer that refuses makes the same comparison.
Notation. Throughout, we use the following terminology for ledgers and blocks. A block has height , the hash of its parent , and an ordered sequence of transactions. Two blocks conflict if neither extends the other. A ledger is a sequence of blocks. We write for the ledger output by client by round . We write if is a prefix of . Two ledgers are consistent, written , if one is a prefix of the other, and conflicting, written , otherwise. Two conflicting ledgers contain conflicting blocks at the first position where they differ.
Certifiable protocols. Our transformation applies to any protocol for which a party that did not monitor the execution can verify the protocol’s output using a non-interactive certificate. We refer to such protocols as certifiable protocols, as defined in [32].
Definition 2 (Certifiable protocol [32]). An SMR protocol is certifiable if it comes with a witness producer W and a deterministic non-interactive witness consumer C: a party invoking W at round obtains a witness with C, the ledger has output at that party by round , and C for every that is not a valid witness.
Quorum-based protocols. We focus on protocols in which a block is finalized after a set of signatures on by distinct members of the committee, such as PBFT [11], HotStuff [36] and Tendermint [10]. Validators that follow certify at most one block per height. We call the certificate that finalizes a valid quorum certificate, denote it by , and write for the members whose signature is on . A witness for a ledger consists of the ledger together with a quorum certificate for each block: . The consumer checks every certificate and every parent hash, and executes the ledger from . It returns if a check fails or a transaction is invalid, since no quorum is guaranteed to contain a validator that checked the block.
Equivocations and accountability. We assume that is accountable: the quorum certificates and for any two conflicting blocks and prove that every validator in their intersection has deviated from the protocol specification. The pair is the evidence of the equivocation. A validator that equivocates loses its stake . Most quorum-based protocols are accountable or become so with small changes [30, 13], and any consensus protocol can be made accountable by a generic transformation [14].
Transactions and fees. We assume that every transaction submitted by clients carries a fee . We write for the set of transactions pending in the view of validator during the round , and for the total fee value of a set of transactions, such as a block or the set . A block may contain any number of transactions, and including a transaction in a block costs its proposer nothing. We write for an upper bound on the fee value of a block and assume .
Ledger Properties
We consider the standard state machine replication (SMR) problem, but state its properties from the perspective of clients. In the usual formulation, safety and liveness are defined with respect to the ledgers of correct validators, together with a requirement that clients can learn those ledgers. In our model, however, no validator is assumed to be correct: validators may be Byzantine or rational and may deviate from the protocol. We therefore state the ledger properties directly over the ledgers output by honest clients, following the perspective adopted in [32, 31]. We first define safety and liveness and then introduce a weaker liveness notion that tolerates transaction censorship.
Definition 3 (Safety). A protocol satisfies safety if, for all honest clients and all rounds , the ledgers of are consistent, i.e., .
Definition 4 (Liveness). A protocol satisfies liveness if, for every transaction submitted by an honest client at round , there exists a round such that every honest client that outputs a ledger at a round outputs a ledger containing .
Censorship. The liveness property above is too strong for our setting, where the adversary may use his budget to bribe rational validators and thereby prevent some transactions from being included in certified blocks. We therefore define -censorship resistance, which ensures that the value of transactions that can be censored at any height is bounded by a -fraction of the transaction value available to the rational signers, in addition to the adversary’s budget. We measure the adversary’s share of a certificate as follows.
Definition 5 (Adversarial bandwidth). Let be a quorum certificate and let be the number of Byzantine validators among its signers. The adversarial bandwidth of is .
Definition 6 (Censored value). Let be the block certified at height , proposed at round , and let be the set of rational signers of . Let be the transactions of together with the transactions held by every rational signer. The censored value at height is .
Definition 7 (-censorship resistance). Fix . A protocol is -censorship resistant if at every height at which a block is certified.
Utilities
The game. An execution of induces a game whose players are the validators. A strategy maps a validator’s local view to its actions. Byzantine validators may also make side payments to other validators, subject to the adversary’s budget.
Utility. For any execution and any interval of that execution, the utility of a rational validator is , where is the protocol reward received by during , is the side payment received by from the adversary, is its share of any double-spent value (if any such attack is successful), and is the stake lost to slashing. A validator receives the reward of a block only once an honest client confirms the block. A side payment is made before the action it buys, and a rational validator that accepts it performs that action; a promise of a future payment does not enter the utility. A rational validator deviates only when doing so strictly increases its utility and follows the protocol when indifferent. We assume that it propagates every certificate it holds unless withholding one strictly increases its utility.
Construction
The construction is a finalization layer over . Validators run unchanged and send every certificate they hold to the full nodes. Full nodes run Algorithm 1, and clients run the freezing gadget of [32] (Algorithm 2).
Full nodes. A full node keeps a store of certificates indexed by height. On receiving a message it stores the certificates it did not hold (Algorithm 1) and relays them (Algorithm 1), before any other action. On receiving a request it sends its store (Algorithm 1). Full nodes confirm nothing.
Clients. A client that wakes multicasts a request (Algorithm 2). On every message it stores the certificates and relays the message (Algorithm 2). Every chain of certified blocks in that starts at genesis is a witness. For every witness with a ledger not yet in , the client adds the ledger to (Algorithm 2) and schedules confirm for round , where is the current round (Algorithm 2). confirm outputs the ledger if holds no conflicting ledger and the ledger extends (Algorithm 2). A client that has seen two conflicting ledgers confirms neither, nor
Algorithm 1 The relay run by every full node. A full node stores every certificate it receives, relays it at once, and serves its store on request.
1: quorum_store ← ∅ ▷ Certificates received, indexed by height
2: upon receive a message m
3: Q ← the valid certificates carried by m that are not in quorum_store
4: if Q = ∅ then ▷ Nothing new
5: return
6: end if
7: quorum_store ← quorum_store ∪ Q
8: multicast(Q) ▷ Relay before anything else
9: end upon
10: upon receive request from party P
11: send quorum_store to P
12: end upon
any ledger that extends either. We say it freezes. A frozen client keeps relaying. Within a round, a client processes messages before scheduled confirmations. A client that falls asleep keeps and discards , and its pending confirmations.
The client waits , one more than in [32], because clients reach each other only through full nodes: a relayed certificate reaches within , and its relay reaches every awake client within another . The same covers the request round trip of a client that has just woken. Here delivers the past messages that the network of [32, 31] delivers.
Validity. A quorum may certify a block that moves coins their owner never had, which creates no conflict for the freezing gadget to detect. The consumer therefore executes the whole ledger of a witness and rejects invalid transitions (§ 2).
Rewards. A block pays the fees it carries, split equally among the signers of its certificate, once an honest client confirms it. A proposer-only reward would let the adversary stall a block by bribing one signer for any positive amount. A signer is paid only if the certificate of its block reaches the clients, so a rational signer sends it to the full nodes.
Intuition. Safety needs no incentive. When a client confirms a ledger, has already shown its certificates to every awake client, and serves them to every client that wakes later, so a client that would confirm a conflicting ledger afterwards freezes instead. Incentives keep clients from freezing and blocks from being censored. Two conflicting certificates share signers, so at least one rational validator signs both and loses its stake . The adversary must pay it more than his reward from one height, which only can cover. Omitting a transaction from a block lowers the reward of every signer. The adversary must compensate the rational signers, and his own share of the fees is what he can spend on side payments. A repeatable strategy therefore censors less than a fraction of the available fees (§ 4).
Algorithm 2 The freezing gadget of {citep}`[32]`, run by a client. Every message is relayed on arrival. The ledger of a witness is confirmed $2\Delta$ after the witness is complete, if no conflicting ledger has been seen.
1: $R \leftarrow \emptyset$ ▷ Certificates received
2: $S \leftarrow \emptyset$ ▷ Ledgers seen
3: $\hat{L} \leftarrow \emptyset$ ▷ Confirmed ledger, the output
4: upon waking
5: multicast(request) ▷ Ask the network for their store
6: end upon
7: upon receive a message $m$ at round $t$
8: $R \leftarrow R \cup \{\text{valid certificates carried by }m\}$
9: multicast($m$) ▷ Relay before anything else
10: for all witnesses $w$ formed by certificates in $R$ with $C(w) \ne S$ do
11: $S \leftarrow S \cup \{C(w)\}$
12: schedule(confirm, $t + 2\Delta$, $C(w)$)
13: end for
14: end upon
15: function confirm($L$)
16: if $\exists L' \in S: L \not\sim L'$ then ▷ Conflict seen: do not confirm
17: return
18: end if
19: if $\hat{L} \preceq L$ then
20: $\hat{L} \leftarrow L$ ▷ Output
21: end if
22: end function
Analysis
We prove the results of this section in Section A. Lemma 1 bounds the cost of a freeze, Theorem 2 the cost of censorship, and Theorem 3 combines them.
Safety
Theorem 1 (Safety). The construction of § 3 satisfies safety (Definition 3) for every strategy of the validators.
The proof follows [31 Theorem 4]. The new step is Lemma 2: a certificate that an honest client relays at round reaches, through , every honest client that confirms at a round , even one asleep at round . In particular, the term of every rational validator is zero.
Liveness
Lemma 1 (Cost of equivocation). In the static setting, if two conflicting blocks are certified, then at least validators equivocate and at least one of them is rational. In both settings, under client freshness in the dynamic one, for every rational validator that loses its stake for an equivocation, the adversary pays it more than before it signs and draws more than from , so the attack is never repeatable. In particular, if , then no two conflicting blocks are certified and no honest client freezes.
Two quorums share members, at least one rational, which loses and gains at most one block reward.
Theorem 2 (Censorship). Assume adversarial participation. At every height at which a block is certified with bandwidth and ,
The bound is tight. Suppose the rational signers hold the same transactions. For every set of transactions in of total fee and every , the adversary can censor exactly this set at height with once the block is confirmed.
Every rational signer of a censoring block loses its share of the censored fees and must be paid more than that. The adversary pays with his own share of the fees, so, when the rational signers hold the same transactions, censoring fee value at a height is repeatable if and only if . Since , the construction is -censorship resistant (Definition 7), and censoring all of is never repeatable when . Without side payments, no rational signer signs a block that omits a transaction with a positive fee that it holds.
Corollary 1 (Price of inclusion). Let a block be certified at height with bandwidth , and let with . Then whenever
Since , it suffices that
Theorem 3 (Liveness). Assume adversarial participation and . Then no honest client freezes, and the following hold.
If the certificates of a valid ledger have reached by round , then every honest client that is awake throughout for some outputs, by round , a ledger that extends .
Let be submitted by an honest client at round , and let be such that at every height whose block is proposed after round . Then at most such heights certify a block without before is included.
Remark 1. Theorem 3 is weaker than liveness (Definition 4). By Theorem 2, a transaction whose fee stays below at every height can be excluded at every height by a repeatable strategy when the rational signers hold the same transactions. We claim safety in full and liveness only for transactions that clear this threshold, which is of the other pending fees when . A stall, or a certificate withheld from every full node, pays the adversary nothing and needs a paid rational validator, so neither is repeatable. We do not bound the delay they cause.
Changing Committees
We now let the validator set change. Each committee signs a handover certificate that fixes the last block of its epoch, and each client validates forward from an anchor taken from the last ledger it confirmed. Safety needs nothing more (Theorem 4). Liveness holds when stake stays slashable for epochs and no client sleeps longer (Theorem 5), and the second bound is necessary (Theorem 6).
Setting and Construction
Epochs and committees. Fix an epoch length . Epoch consists of the rounds . A block carries the round at which it is proposed and belongs to the epoch of that round, and the rounds of the blocks of a ledger increase with height. We write for the last height of epoch , that is, the height of the last block whose epoch is at most , and for the state after the block of height . The committee of epoch is , where is a fixed public function, and is the genesis committee. We abstract how transactions determine the committee. During epoch the members of run , and a quorum certificate for a block of epoch carries signatures of distinct members of . How the members of obtain the ledger at the start of the epoch is part of . Full nodes run the static construction and store every well-formed certificate, since they track no committees.
Handover certificates. The transition from epoch to epoch is certified by the outgoing committee. Every member of signs the pair , where is the block of height (Algorithm 3). A quorum of such signatures forms the handover certificate (Algorithm 3), which the first block above height includes (Algorithm 3). A certificate for a block of epoch that extends , together with , is evidence of an equivocation by every validator that signed both, as is a pair of certificates for conflicting blocks.
Slashing. Fix . The stake of every validator in remains locked, and slashable on evidence of an equivocation on the blocks of epoch or on , until rounds after the end of epoch . We call this period the bonding window of . A committee that receives such evidence within the period includes it in a block of its epoch, and its members share the slashed stake equally. The bound on Byzantine members of Section 2 holds for the committees that a ledger designates when the quorum certificate of every block of the ledger was formed within the bonding window of its signers; other ledgers may designate any keys.
Anchors. A client checks the certificates of epoch against , which it learns only after validating epoch , and so on recursively from the genesis. It therefore needs a point in the history from which to validate forward every time it wakes up. To this end, the client keeps a commitment to the last epoch it validated before sleeping. We call this point the client’s anchor. The anchor of a client is a triple : an epoch , its committee , and the hash of the block of height . The client takes its anchor from the last ledger it confirmed, and is the epoch of the last block of . A client that has never confirmed a ledger holds the genesis anchor . The hash fixes the block of height and, through the parent hashes, every block below it. The committee alone would not fix them, since two different ledgers may designate the same committee.
Clients. The client keeps running finalization of Algorithm 2 unchanged except for the witness consumer of the certifiable protocol. Algorithm 3 gives the witness consumer bootstrap, which verifies the committee changes across epochs. The client initializes to and keeps its anchor, the state after , and across sleeps. A witness carries the blocks, certificates and handover certificates from height onward. bootstrap checks that the witness extends the block that fixes, with increasing rounds and no block of an epoch below above it (Algorithm 3). It then validates one epoch at a time from : every block of epoch is valid and carries a quorum certificate of (Algorithm 3), the next committee is derived from the state (Algorithm 3), and is a quorum of (Algorithm 3). The ledger of a witness is the prefix of that ends at height , followed by the blocks that bootstrap returns above it.
Assumptions. The liveness results of this section rest on the bonding window and on one assumption on clients, which we call client freshness. An honest client that wakes during epoch holds an anchor of epoch . While it stays awake, its anchor must stay equally recent, except during the first rounds after it wakes, which it needs to confirm a new ledger: at every round at least rounds after it woke, its anchor is of epoch , where is the epoch of .
Analysis
The proofs of this subsection are in Section B.
Theorem 4 (Dynamic safety). The construction of § 3 with bootstrap in place of satisfies safety (Definition 3), whether or not the bonding window and client freshness hold.
The proof applies Lemma 2, and the anchor ledger serves as the base of an induction over the confirmations of honest clients.
Theorem 5 (Dynamic liveness). Assume the bonding window, client freshness, adversarial participation and . Then no honest client freezes, and the conclusions of Theorem 3 hold for every honest client, for the ledgers that honest clients confirm.
Algorithm 3 The epoch handover, run by the committee of an ending epoch, and the witness consumer bootstrap, run by a client with anchor .
upon entering epoch ▷ Run by every member of
the block of height
cast a signature over
a quorum of such signatures by
include in the first block above height
end upon
function bootstrap ▷ carries blocks, certificates and handovers from height on
if is not a hash chain with increasing rounds, its block of height does not hash to , or a block above it is of an epoch below then
return ▷ Diverges before the anchor
end if
for to the last epoch in do ▷ is known here
if some block of epoch in has no quorum certificate of or is invalid then
return ▷ Uncertified or invalid
end if
▷ is the state after height
the block of height in
if has a block above height and in is not a quorum of over then
return
end if
end for
return the blocks of above height
end function
Two conflicting witnesses that pass bootstrap first differ in an epoch whose committee both designate, and the handover certificate makes the fork an equivocation of (Lemma 3), which is still slashable, so Lemma 1 applies.
Necessity of Client Freshness
Client freshness cannot be dropped. The obstacle is the long-range attack of proof-of-stake systems: a committee whose stake has been released sells signatures on a conflicting ledger, and the adversary extends it with committees of his own. The attack uses one property of committee: for every set of keys and every block , some valid block of epoch with parent , which may output, makes committee designate as .
The long-range attack. Fix epochs and and a budget . Let the committees designated after the last block of epoch consist of keys that no earlier committee holds. Let an honest client be awake during epoch , fall asleep before is proposed, and wake during epoch , after step 2 below. The adversary acts as follows.
He follows the protocol until an always-on honest client has output a ledger that contains a block of epoch and the bonding window of has ended.
He pays to each rational member of . In return, it signs a block of epoch with the parent and height of , after which committee designates keys he generated, and the handover certificate that names .
He extends epoch by epoch up to epoch , certifying every block and handover with keys he holds.
He answers the requests of from a full node he controls, exactly as would answer them in the execution in which was certified in epoch and was produced by steps 1 to 3.
Theorem 6 (Necessity of client freshness). Consider any protocol in the model of § 2, with epochs, a bonding window of epochs and a function committee with the property above, in which honest clients output only ledgers of certified blocks. Let , let the adversary hold any budget , and let . Then the protocol does not guarantee all of the following: safety; that every always-on honest client outputs a ledger with a block of epoch by the end of epoch ; and that the client above eventually does.
In the execution with the attack and in the one where and exchange roles, has the same local state and receives the same messages, so it outputs the same ledger. By safety, that ledger extends in one execution and in the other. does not help, because cannot tell it apart from the full node of the adversary.
The two-execution argument is the classical lower bound for long-range attacks [15, 34, 19], which assumes that old keys become corrupt. Here rational members of old committees sell their signatures for any positive amount, and existential honesty does not remove the bound. With Theorem 5, the threshold is exact: a client whose last confirmed block is in epoch keeps the guarantees of the static case in epoch if , and not necessarily if . Ouroboros Genesis [8] avoids the bound by having honest validators erase old keys, which a rational validator has no reason to do.
Discussion
Recovery. A freeze is permanent: the construction has no recovery, and recovery as in [32, 31] needs an honest majority to return. A freeze slashes at least validators, his own among them, and the adversary must pay a rational one more than (Lemma 1), for instance from saved rewards.
Censorship. Transactions whose fee is below a fraction of the available fees can be censored forever at no cost to the adversary (Remark 1). Adversarial participation is the worst case for censorship.
Block size and synchrony. With bounded blocks, a reward for fuller blocks invites padding, and the remedy is a burned fee [27, 28, 12]; whether Theorem 2 then holds is open. CoBRA [6], Theorem 3.1 rules out partial synchrony without honest validators, and which weaker guarantee it admits is open.
Acknowledgements
This work was partially supported by the Austrian Science Fund (FWF) through the SFB SpyCode project (F8512-N), and by the Vienna Science and Technology Fund (WWTF) through the project 10.47379/ICT22045. The research of Odysseas Sofikitis was supported by Common Prefix OÜ.
Proofs of Section 4
The safety proof rests on one timing fact, which we state as a lemma.
Lemma 2 (Delivery). Let an honest client relay a certificate at round , and let an honest client run a confirmation at round . Then holds the certificate when the confirmation runs.
Proof. The relay reaches by round . Let be the round at which first receives the certificate. By Algorithm 1, relays it at round . Let be the round at which last woke before round , or if has been awake since the first round. A client that falls asleep discards its pending confirmations, so scheduled the confirmation at a round and is awake from round to round . By Algorithm 2, .
Case 1: . Then is awake from round to round , and the relay of reaches it by round .
Case 2: . At round , multicasts a request (Algorithm 2). The request reaches by round . holds the certificate from round , so the reply of Algorithm 1 carries it and reaches by round .
In both cases receives the certificate by round and keeps it in , since it does not sleep between rounds and . A client processes the messages of a round before its confirmations, so holds the certificate when the confirmation runs.
Proof of Theorem 1. Suppose towards a contradiction that honest clients and output ledgers and with . By Algorithm 2 the output of a client only grows by extension, so confirmed at some round and confirmed at some round . By symmetry we may assume .
Let be the round at which the witness for became complete at . By Algorithm 2, . By Algorithm 2, relayed every certificate of the witness by round . By Lemma 2, holds all of them when its confirmation at round runs. The consumer is deterministic, so by Algorithm 2 has added to by then. Then Algorithm 2 stops from confirming at round . Contradiction.
Proof of Lemma 1. Let and certify conflicting blocks and . Each carries signatures of distinct validators out of , so
Every validator in the intersection equivocates. At most validators are Byzantine, so the intersection contains a rational validator.
Let be a rational validator that loses its stake for an equivocation. By Theorems 1 and 4, no two honest clients confirm conflicting ledgers. So receives at most one block reward from the equivocation, which is at most , and gains nothing from a double-spend. Had not equivocated, its utility would be non-negative. A rational validator deviates only for strictly greater utility, and a side payment is made before the action it buys. So the adversary pays more than before signs. Let be the height to which this payment is charged; a payment for a signature on is charged to the height of the block that names. The adversary receives from height , since the block rewarded at height is on a ledger that an honest client confirms, whose committees satisfy the bound on Byzantine members, in the dynamic setting by item 2 of Lemma 3. Hence , which is positive since .
By accountability, the rational validator in the intersection loses its stake, so the adversary draws more than from . If , this contradicts
so no two conflicting blocks are certified. A client freezes only when holds two conflicting ledgers (Algorithm 2). These contain conflicting blocks at the first position where they differ, and a witness certifies every block of its ledger, so no honest client freezes.
Proof of Theorem 2. Let be the block certified at height , proposed at round , and let be the set of rational signers of . Write and . Then and .
Upper bound. Let . By adversarial participation, compares signing with signing . By Definition 6, every transaction of that is not in is held by , so the second block carries at least more fees and pays at least more. Fees on the adversary’s own transactions appear in both blocks, so they do not change this difference. Neither alternative involves slashing or a double-spend. Since , signs only if the adversary pays it more than before it signs. The side payments charged to height therefore exceed . His validators receive from . By the definition of ,
and adding to both sides gives .
Tightness. Let every hold the same set of pending transactions, and let have total fee . The adversary has proposed, by one of his validators or by a paid rational signer, signs it with of his validators, and pays each rational signer . A rational signer receives by signing and by signing , so it strictly prefers to sign . The block is certified with and . The adversary pays and receives once is confirmed, so .
Proof of Corollary 1. Suppose towards a contradiction that . Then , so , and Theorem 2 gives . Substituting and rearranging gives , which contradicts the hypothesis. For the second form, the maps and are increasing on , so the right-hand side is largest at , where it equals .
Proof of Theorem 3. By Lemma 1, no two conflicting blocks are certified and no honest client freezes.
Item 1. Let be awake throughout and let be the round at which it last woke. Consider a certificate of and let be the round at which first received it. If , the relay of at round (Algorithm 1) reaches by round . If , the request of at round (Algorithm 2) reaches by round , and the reply of Algorithm 1 carries the certificate and reaches by round . So the witness for is complete at by round , and by Algorithm 2 its confirmation runs by round . Every ledger in and the output consist of certified blocks, and no two conflicting blocks are certified. So Algorithm 2 passes, and is consistent with . If , then Algorithm 2 outputs . Otherwise . In both cases the output extends .
Item 2. The submitting client sends to every validator, and validators are always awake, so from round every validator holds until it is included. Let be a height whose block is proposed after round and certified with bandwidth , and let . Then . By Corollary 1,
Since , the bracket is at least . Since , we get . As , there are at most such heights before is included.
Proofs of Section 5
Proof of Theorem 4. The proof is by a minimal counterexample over the confirmations of honest clients, ordered by round with ties broken arbitrarily. It uses two facts about a ledger that an honest client confirms at round . First, every certificate of was relayed by an honest client by round . Second, the rounds of the blocks of increase, and every block of is valid and carries a quorum certificate of the committee that designates for its epoch. Every handover certificate in is a quorum of the committee of the epoch it ends. Both facts hold by induction on . Let be the ledger from which the client took the anchor that it used for . The blocks, certificates and handover certificates of from height onward form the witness, which the client relayed at Algorithm 2 by the round at which it became complete. By Algorithm 2, . bootstrap checked them at Algorithm 3. The output of the client starts at and grows by extension (Algorithm 2), so , and the blocks and handover certificates of up to the last block of belong to . This covers , which lies in the first block above height . Either is empty, or the client confirmed at an earlier round and the induction hypothesis applies.
Towards a contradiction, let the confirmation of by at round be the first that conflicts with an earlier one, and let have confirmed earlier, at round . By the first fact, every certificate of was relayed by an honest client by round . By Lemma 2, holds all of them when its confirmation at round runs. Let be the ledger from which took the anchor it holds when it receives the last of them. Either is empty or confirmed it before round , so by the choice of . The output of grows only by extension (Algorithm 2) and outputs at round , so . If , then , which contradicts . Hence .
The blocks, certificates and handover certificates of from height onward form a witness. It passes Algorithm 3 because : the rounds of increase by the second fact, and its block after the anchor block is that of , which is of epoch . The ledgers and agree up to height , so they designate the same committee , and by the second fact the witness passes Algorithm 3. So bootstrap returns the blocks of above height , and adds to at Algorithm 2 before its confirmation runs. Then Algorithm 2 stops from confirming at round , which contradicts the choice of .
The next lemma shows that, for a fresh client, the bound on Byzantine members covers every committee that matters, and that a fork it accepts is an equivocation of one such committee.
Lemma 3 (Fork epoch). Assume client freshness. Let an honest client be awake at round with an anchor of epoch taken from a ledger , and call a ledger admissible if it agrees with up to height and passes the checks of bootstrap above that height.
Round is at most rounds after the end of epoch .
The bound on Byzantine members holds for every committee that an admissible ledger, or a ledger that an honest client confirms, designates.
If two admissible ledgers conflict, then there is an epoch such that at least members of equivocated on the blocks of epoch or on , and at least one of them is rational.
Proof. Item 1. The anchor of a client only moves forward. If comes at least rounds after the client woke, then by client freshness lies in an epoch at most . Otherwise the client woke fewer than rounds before , during an epoch with , so is less than rounds after the end of epoch .
Item 2. Let be admissible. By Algorithm 3, the blocks of above height are of epochs at least , and the client holds their certificates by round . By item 1, each was formed within the bonding window of its signers, which lasts until rounds after the end of an epoch at least . The blocks at or below height are those of . The client confirmed at an earlier round, while fresh, so the same argument applies to , and by induction over its confirmations down to the genesis block. The same induction applies to every ledger that an honest client confirms.
Item 3. Let and be the two ledgers. They agree up to height . Let be the first position at which they differ, and let and be their blocks at position . Both have the same parent . Let be the smaller of the epochs of and , say the epoch of . The rounds of the blocks of a ledger increase with height, so every block of an epoch before lies at or below in both ledgers. Hence both ledgers have the same state and designate the same committee , to which the bound applies by item 2.
Case 1: is also of epoch . By Algorithm 3, and carry quorum certificates of . They conflict, since they differ and have the same parent.
Case 2: is of a later epoch. Then is the block of height in , and has a block above it. By Algorithm 3, carries , a quorum of over . By Algorithm 3, carries a quorum certificate of , and is a block of epoch that extends .
In both cases two quorums of sign an equivocation. They share at least members, and at most members of are Byzantine.
Proof of Theorem 5. Suppose towards a contradiction that an honest client freezes. Then holds two conflicting ledgers and , and let be the later to enter , at round . Let be the ledger of the anchor of at round , of epoch . The ledger passed bootstrap under this anchor, so it is admissible. Either also passed bootstrap under it, or confirmed while was in , in which case by Algorithm 2. Since conflicts with , which agrees with up to height , also agrees with up to that height. Its blocks above it either belong to , which an honest client confirmed, or were checked by bootstrap with the committees that its own prefix designates, so is admissible as well.
By item 3 of Lemma 3, a rational member of some with equivocated on the blocks of epoch or on . The client relays both witnesses on receipt to the full nodes and the validators (Algorithm 2), so the committee of the current epoch holds the evidence by round . By item 1 of Lemma 3, this is at most rounds after the end of epoch , inside the bonding window of , so loses its stake . By Lemma 1, the adversary draws more than from , which contradicts . So no honest client freezes.
Item 1 of Theorem 3 concerns a ledger that an honest client has confirmed. holds its certificates and handover certificates. By Theorem 4, the ledger of the anchor of satisfies . If , the output of already extends . Otherwise , and the witness of from height passes bootstrap, since was confirmed by an honest client and its blocks above are of epochs at least . The timing of the static proof applies, does not freeze, and by Theorem 4, so the output of extends . Item 2 concerns the heights of ledgers that honest clients confirm. By item 2 of Lemma 3, their committees satisfy the bound on Byzantine members, so at each such height, and Theorem 2 and Corollary 1 apply as in the static case.
Proof of Theorem 6. Suppose the protocol guarantees safety and that every always-on honest client eventually outputs a ledger that contains a block of epoch . We show that outputs no such ledger in two executions A and B.
Execution A. The adversary runs the long-range attack. By the second guarantee, an always-on honest client outputs a ledger that contains a block of epoch by the end of epoch . The bonding window of ends rounds after the end of epoch , and buying the signatures of step 2 takes at most rounds more. Since , steps 1 and 2 end within epoch , and can wake in epoch after them. Let be the last block of epoch in and let be the prefix of below . In step 2, the bonding window of has ended, and the keys designated after are fresh, so a member of holds no stake and no seat that signing and its handover certificate could affect. Refusing gains it nothing, so a rational member strictly prefers the payment and signs. The Byzantine members sign as well. The adversary pays at most . The branch through is certified after the bonding window of , so the bound on Byzantine members does not apply to the committees it designates, and the adversary may hold their keys. After step 3, every block and handover certificate on the branch through carries a quorum of the committee that its own prefix designates, as on the branch through .
Execution B. By the property of committee, some valid block of epoch with the parent of , which may output, designates a set of fresh keys. Let B agree with A until is proposed. In B the protocol outputs as the last block of epoch , and the keys that the branch through designates belong to validators, Byzantine and rational in every committee. The adversary runs steps 1 to 4 with in place of : he buys the signatures of on and its handover certificate, and holds the fresh keys that the branch through designates, to which the bound again does not apply. By the second guarantee, the always-on honest client of B outputs a ledger that contains a block of epoch by the end of epoch , before step 2 of B. Honest clients output only ledgers of certified blocks, and until that step the only certified block with the parent and height of is . So extends by .
Fix the random coins of to be the same in A and B. The two executions agree until is proposed, and sleeps from then until it wakes in epoch , so has the same local state in both. After waking, receives messages from full nodes and validators only. In A, the adversary sends to , from his full node and from the keys of the branch through , exactly the messages that and the validators of the branch through send to in B. In B he does the same with and swapped. He delivers every message to exactly rounds after it is sent. So receives the same messages at the same rounds in A and B, and outputs the same ledgers.
Suppose towards a contradiction that outputs a ledger that contains a block of epoch . In A, safety gives . The blocks of are of epoch at most , so is not a prefix of , and agrees with at the position of . The block of at that position is therefore . In B, the same argument with gives . This contradicts . So if safety holds in A and in B, then outputs no ledger that contains a block of epoch , in either execution. ∎
References
- [1]Abraham, I., Dolev, D., Gonen, R., Halpern, J.Y.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing. pp. 53–62. PODC ’06 (2006)
- [2]Abraham, I., Dolev, D., Halpern, J.Y.: Lower bounds on implementing robust and resilient mediators. In: Theory of Cryptography Conference (TCC 2008). pp. 302–319. Springer (2008)arxiv.org/abs/0704.3646
- [3]Aiyer, A.S., Alvisi, L., Clement, A., Dahlin, M., Martin, J.P., Porth, C.: BAR fault tolerance for cooperative services. In: Proceedings of the Twentieth ACM Symposium on Operating Systems Principles. pp. 45–58. SOSP ’05 (2005)
- [4]Amoussou-Guenou, Y., Biais, B., Potop-Butucaru, M., Tucci-Piergiovanni, S.: Rational vs Byzantine players in consensus-based blockchains. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. pp. 43–51. AAMAS ’20 (2020)
- [5]Amoussou-Guenou, Y., Biais, B., Potop-Butucaru, M., Tucci-Piergiovanni, S.: Rational behaviors in committee-based blockchains. In: 24th International Conference on Principles of Distributed Systems (OPODIS 2020). LIPIcs, vol. 184, pp. 12:1–12:16 (2021). https://doi.org/10.4230/LIPIcs.OPODIS.2020.12
- [6]Avarikioti, Z., Kogias, E.K., Neiher, R., Stefo, C.: CoBRA: A universal strategyproof confirmation protocol for quorum-based proof-of-stake blockchains (2025), https://arxiv.org/abs/2503.16783
- [7]Azouvi, S., Danezis, G., Nikolaenko, V.: Winkle: Foiling long-range attacks in proof-of-stake systems. In: Proceedings of the 2nd ACM Conference on Advances in Financial Technologies. pp. 189–201. AFT ’20 (2020)DOI
- [8]Badertscher, C., Gaži, P., Kiayias, A., Russell, A., Zikas, V.: Ouroboros Genesis: Composable proof-of-stake blockchains with dynamic availability. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. pp. 913–930. CCS ’18 (2018). https://doi.org/10.1145/3243734.3243848
- [9]Braithwaite, S., Buchman, E., Khoffi, I., Konnov, I., Milosevic, Z., Ruetschi, R., Widder, J.: A Tendermint light client (2020), https://arxiv.org/abs/2010.07031
- [10]Buchman, E., Kwon, J., Milosevic, Z.: The latest gossip on BFT consensus (2018), https://arxiv.org/abs/1807.04938
- [11]Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Proceedings of the Third Symposium on Operating Systems Design and Implementation. pp. 173–186. OSDI ’99, USENIX Association, USA (1999)
- [12]Chung, H., Shi, E.: Foundations of transaction fee mechanism design. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms. pp. 3856–3899. SODA ’23 (2023)
- [13]Civit, P., Gilbert, S., Gramoli, V.: Polygraph: Accountable Byzantine agreement. In: Proceedings of the 41st IEEE International Conference on Distributed Computing Systems. pp. 403–413. ICDCS ’21 (2021)DOI
- [14]Civit, P., Gilbert, S., Gramoli, V., Guerraoui, R., Komatovic, J.: As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy! Journal of Parallel and Distributed Computing 181, 104743 (2023). https://doi.org/10.1016/j.jpdc.2023.104743
- [15]Daian, P., Pass, R., Shi, E.: Snow White: Robustly reconfigurable consensus and applications to provably secure proof of stake. Cryptology ePrint Archive, Paper 2016/919, full version (2016), https://eprint.iacr.org/2016/919
- [16]Fox, E., Pai, M.M., Resnick, M.: Censorship resistance in on-chain auctions. In: 5th Conference on Advances in Financial Technologies (AFT 2023). LIPIcs, vol. 282, pp. 19:1–19:20 (2023). https://doi.org/10.4230/LIPIcs.AFT.2023.19
- [17]Gong, T., Camilo, G.F., Nayak, K., Lewis-Pye, A., Kate, A.: Recover from excessive faults in partially-synchronous BFT SMR. In: 34th USENIX Security Symposium, pp. 4147–4166 (2025)
- [18]Lev-Ari, K., Spiegelman, A., Keidar, I., Malkhi, D.: FairLedger: A fair blockchain protocol for financial institutions. In: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). LIPIcs, vol. 153 (2019). https://doi.org/10.4230/LIPIcs.OPODIS.2019.4
- [19]Lewis-Pye, A., Roughgarden, T.: Permissionless consensus (2023), https://arxiv.org/abs/2304.14701
- [20]Lewis-Pye, A., Roughgarden, T.: Beyond optimal fault-tolerance. In: 7th Conference on Advances in Financial Technologies (AFT 2025). LIPIcs, vol. 354, pp. 15:1–15:23 (2025). https://doi.org/10.4230/LIPIcs.AFT.2025.15
- [21]Malkhi, D., Nayak, K., Ren, L.: Flexible Byzantine fault tolerance. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. pp. 1041–1053. CCS ’19 (2019)arxiv.org/abs/1904.10067
- [22]McMenamin, C., Daza, V., Pontecorvi, M.: Achieving state machine replication without honest players. In: Proceedings of the 3rd ACM Conference on Advances in Financial Technologies. pp. 1–14. AFT ’21 (2021). https://doi.org/10.1145/3479722.3480986
- [23]Neu, J., Sridhar, S., Yang, L., Tse, D.: Optimal flexible consensus and its application to Ethereum. In: 2024 IEEE Symposium on Security and Privacy (SP). pp. 3885–3903 (2024)arxiv.org/abs/2308.05096
- [24]Neu, J., Tas, E.N., Tse, D.: The availability-accountability dilemma and its resolution via accountability gadgets. In: Financial Cryptography and Data Security. LNCS, vol. 13411, pp. 541–559. Springer (2022)arxiv.org/abs/2105.06075
- [25]Ranchal-Pedrosa, A., Gramoli, V.: TRAP: The bait of rational players to solve Byzantine consensus. In: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security. pp. 168–181. ASIA CCS ’22 (2022). https://doi.org/10.1145/3488932.3513786
- [26]Ranchal-Pedrosa, A., Gramoli, V.: ZLB: A blockchain to tolerate colluding majorities. In: 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). pp. 209–222 (2024). https://doi.org/10.1109/DSN58291.2024.00032
- [27]Roughgarden, T.: Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559 (2020), https://arxiv.org/abs/2012.00854
- [28]Roughgarden, T.: Transaction fee mechanism design. In: Proceedings of the 22nd ACM Conference on Economics and Computation. EC ’21 (2021). https://doi.org/10.1145/3465456.3467591
- [29]Saraf, A., Kaklamanis, I., Wadhwa, S., Elsheimy, F.: Price of censorship: Censorship resistance and throughput under rational concurrent proposers (2026), https://arxiv.org/abs/2607.16995
- [30]Sheng, P., Wang, G., Nayak, K., Kannan, S., Viswanath, P.: BFT protocol forensics. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. pp. 1722–1743. CCS ’21 (2021)DOI
- [31]Sridhar, S., Tas, E.N., Neu, J., Zindros, D., Tse, D.: Consensus under adversary majority done right. In: Financial Cryptography and Data Security. pp. 108–126. FC ’25 (2025). https://doi.org/10.1007/978-3-032-07035-7_7
- [32]Sridhar, S., Zindros, D., Tse, D.: Better safe than sorry: Recovering after adversarial majority (2023), https://arxiv.org/abs/2310.06338
- [33]Stouka, A.P., Ma, J., Thiery, T.: Multiple proposer transaction fee mechanism design: Robust incentives against censorship and bribery (2025), https://arxiv.org/abs/2505.13751
- [34]Tas, E.N., Tse, D., Gai, F., Kannan, S., Maddah-Ali, M.A., Yu, F.: Bitcoin-enhanced proof-of-stake security: Possibilities and impossibilities. In: IEEE Symposium on Security and Privacy. S&P ’23 (2023)arxiv.org/abs/2207.08392
- [35]Thiery, T., D’Amato, F., Ma, J., Monnot, B., Tsao, T., Kaufmann, J., Song, J.: EIP-7805: Fork-choice enforced inclusion lists (FOCIL). Ethereum Improvement Proposals (2024), https://eips.ethereum.org/EIPS/eip-7805
- [36]Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: HotStuff: BFT consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. pp. 347–356. PODC ’19, Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3293611.3331591