betaFeedback

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 Δ\Delta, 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 Δ\Delta 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 2Δ2\Delta, 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 Π\Pi to maintain an ordered ledger of transactions. In Section 3, we consider a static setting, in which there is a fixed set V\mathcal{V} of nn 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 ee by Ce\mathcal{C}_e. 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 DD coins as stake. We model an entity that locks α⋅D\alpha\cdot D coins as controlling α\alpha 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 Π\Pi. 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 FhF_h, 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 FhF_h. 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 Δ\Delta: a message sent at round rr to a party pp reaches pp by round r+Δr+\Delta, provided pp is awake from round rr to round r+Δr+\Delta. 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 GG, available to every party, specifies the initial validators, their public keys, and their stake.

Adversarial model. In the static setting, ∣V∣=3f+1|\mathcal{V}| = 3f + 1; in the dynamic setting, every committee satisfies ∣Ce∣=3f+1|\mathcal{C}_e| = 3f + 1. In either case, ff validators are Byzantine and the remaining k=2f+1k = 2f + 1 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 A\mathcal{A} controls all Byzantine validators and may corrupt any number of clients and of full nodes other than FhF_h. He controls message delivery subject to the synchronous bound Δ\Delta 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 B\mathcal{B} coins that are not staked. He also receives the rewards of his validators, and we write ghg_h for the reward he receives from the block of height hh. 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 hh against ghg_h. Any excess is drawn from B\mathcal{B}. We write Bh≥0B_h \ge0 for the amount drawn at height hh, so that ∑hBh≤B\sum_h B_h \le\mathcal{B}. Fees that the adversary pays on his own transactions count as side payments.

Definition 1 (Repeatable attack). An adversarial strategy is repeatable at height hh if Bh=0B_h = 0, that is, if the side payments it makes at height hh are at most ghg_h.

A repeatable strategy can run at every height. A strategy that is not repeatable draws on B\mathcal{B}, 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, f∗≤ff^{*} \le f, sign the certificate of a block, and their signatures are included. A rational signer of a block bb compares signing bb with signing bb extended by the transactions it holds. The k=qk = q rational validators can certify the second block without the adversary, and it pays each signer 1/q1/q 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 b=(h,H(b′),T)b = (h, H(b'), T) has height hh, the hash H(b′)H(b') of its parent b′b', and an ordered sequence TT of transactions. Two blocks conflict if neither extends the other. A ledger L\mathcal{L} is a sequence of blocks. We write Lrc\mathcal{L}^{c}_{r} for the ledger output by client cc by round rr. We write L⪯L′\mathcal{L} \preceq\mathcal{L}' if L\mathcal{L} is a prefix of L′\mathcal{L}'. Two ledgers are consistent, written L∼L′\mathcal{L} \sim\mathcal{L}', if one is a prefix of the other, and conflicting, written L≁L′\mathcal{L} \not\sim\mathcal{L}', otherwise. Two conflicting ledgers contain conflicting blocks at the first position where they differ.

Certifiable protocols. Our transformation applies to any protocol Π\Pi 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 Π\Pi is certifiable if it comes with a witness producer W and a deterministic non-interactive witness consumer C: a party invoking W at round rr obtains a witness ww with C(w)=L(w) = \mathcal{L}, the ledger Π\Pi has output at that party by round rr, and C(w)=⊥(w) = \perp for every ww that is not a valid witness.

Quorum-based protocols. We focus on protocols in which a block bb is finalized after a set of q=2f+1q = 2f + 1 signatures on bb by distinct members of the committee, such as PBFT [11], HotStuff [36] and Tendermint [10]. Validators that follow Π\Pi certify at most one block per height. We call the certificate that finalizes bb a valid quorum certificate, denote it by QCb\mathrm{QC}_b, and write signers⁡(QCb)\operatorname{signers}(\mathrm{QC}_b) for the members whose signature is on QCb\mathrm{QC}_b. A witness for a ledger L=(b0,…,bh)\mathcal{L}=(b_0,\ldots,b_h) consists of the ledger together with a quorum certificate for each block: w=(G,(b0,QCb0),…,(bh,QCbh))w=(G,(b_0,\mathrm{QC}_{b_0}),\ldots,(b_h,\mathrm{QC}_{b_h})). The consumer CC checks every certificate and every parent hash, and executes the ledger from GG. It returns ⊥\bot 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 Π\Pi is accountable: the quorum certificates QCb\mathrm{QC}_b and QCb′\mathrm{QC}_{b'} for any two conflicting blocks bb and b′b' prove that every validator in their intersection v∈signers⁡(QCb)∩signers⁡(QCb′)v \in\operatorname{signers}(\mathrm{QC}_b)\cap\operatorname{signers}(\mathrm{QC}_{b'}) has deviated from the protocol specification. The pair (QCb,QCb′)(\mathrm{QC}_b,\mathrm{QC}_{b'}) is the evidence of the equivocation. A validator that equivocates loses its stake DD. 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 tx\mathrm{tx} submitted by clients carries a fee tx.fee≥0\mathrm{tx.fee} \ge0. We write MprM_p^r for the set of transactions pending in the view of validator pp during the round rr, and F(X)=∑tx∈Xtx.feeF(X)=\sum_{\mathrm{tx}\in X}\mathrm{tx.fee} for the total fee value of a set XX of transactions, such as a block bb or the set MprM_p^r. A block may contain any number of transactions, and including a transaction in a block costs its proposer nothing. We write F‾\overline{F} for an upper bound on the fee value of a block and assume D>F‾D > \overline{F}.

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 c1,c2c_1,c_2 and all rounds r1,r2r_1,r_2, the ledgers of c1,c2c_1,c_2 are consistent, i.e., Lr1c1∼Lr2c2\mathcal{L}_{r_1}^{c_1}\sim\mathcal{L}_{r_2}^{c_2}.

Definition 4 (Liveness). A protocol satisfies liveness if, for every transaction tx\mathrm{tx} submitted by an honest client at round rr, there exists a round r′>rr' > r such that every honest client that outputs a ledger at a round r′′≥r′r'' \ge r' outputs a ledger containing tx\mathrm{tx}.

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 γ\gamma-censorship resistance, which ensures that the value of transactions that can be censored at any height is bounded by a γ\gamma-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 QCb\mathrm{QC}_b be a quorum certificate and let f∗f^* be the number of Byzantine validators among its signers. The adversarial bandwidth of QCb\mathrm{QC}_b is ρ=f∗/q\rho= f^*/q.

Definition 6 (Censored value). Let bb be the block certified at height hh, proposed at round rr, and let RR be the set of rational signers of QCb\mathrm{QC}_b. Let Mh=b∪⋂p∈RMpp\mathcal{M}_h = b \cup\bigcap_{p\in R}\mathcal{M}^p_p be the transactions of bb together with the transactions held by every rational signer. The censored value at height hh is censh=F(Mh)−F(b)\mathrm{cens}_h = \mathcal{F}(\mathcal{M}_h) - \mathcal{F}(b).

Definition 7 (γ\gamma-censorship resistance). Fix γ∈[0,1)\gamma\in[0,1). A protocol is γ\gamma-censorship resistant if censh≤γ⋅F(Mh)+Bh\mathrm{cens}_h \leq\gamma\cdot\mathcal{F}(\mathcal{M}_h) + B_h at every height hh at which a block is certified.

Utilities

The game. An execution of Π\Pi 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 II of that execution, the utility of a rational validator pp is upI=rewpI+bribepI+gainpI−penpIu^I_p = \mathrm{rew}^I_p + \mathrm{bribe}^I_p + \mathrm{gain}^I_p - \mathrm{pen}^I_p, where rewpI\mathrm{rew}^I_p is the protocol reward received by pp during II, bribepI\mathrm{bribe}^I_p is the side payment received by pp from the adversary, gainpI\mathrm{gain}^I_p is its share of any double-spent value (if any such attack is successful), and penpI\mathrm{pen}^I_p 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 Π\Pi. Validators run Π\Pi 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 RR that starts at genesis is a witness. For every witness with a ledger not yet in SS, the client adds the ledger to SS (Algorithm 2) and schedules confirm for round t+2Δt + 2\Delta, where tt is the current round (Algorithm 2). confirm outputs the ledger if SS holds no conflicting ledger and the ledger extends L^\hat{\mathcal{L}} (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 L^\hat{L} and discards RR, SS and its pending confirmations.

The client waits 2Δ2\Delta, one Δ\Delta more than in [32], because clients reach each other only through full nodes: a relayed certificate reaches FhF_h within Δ\Delta, and its relay reaches every awake client within another Δ\Delta. The same 2Δ2\Delta covers the request round trip of a client that has just woken. Here FhF_h 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 CC 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 qq 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, FhF_h 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 f+1f+1 signers, so at least one rational validator signs both and loses its stake DD. The adversary must pay it more than his reward from one height, which only BB 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 ρ\rho 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 tt reaches, through FhF_h, every honest client that confirms at a round s≥t+2Δs \ge t + 2\Delta, even one asleep at round tt. In particular, the term gain⁡pI\operatorname{gain}^{I}_{p} 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 f+1f + 1 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 D−Fˉ/qD-\bar{F}/q before it signs and draws more than D−FˉD-\bar{F} from BB, so the attack is never repeatable. In particular, if B≤D−FˉB\le D-\bar{F}, then no two conflicting blocks are certified and no honest client freezes.

Two quorums share f+1f+1 members, at least one rational, which loses DD and gains at most one block reward.

Theorem 2 (Censorship). Assume adversarial participation. At every height hh at which a block is certified with bandwidth ρ\rho and censh>0\mathrm{cens}_h>0,

censh<ρ⋅F(Mh)+Bh.\mathrm{cens}_h<\rho\cdot\mathcal{F}(\mathcal{M}_h)+B_h.

The bound is tight. Suppose the rational signers hold the same transactions. For every set of transactions in Mh\mathcal{M}_h of total fee c>0c>0 and every ε>0\varepsilon>0, the adversary can censor exactly this set at height hh with Bh≤max⁡(0,c−ρF(Mh)+ε)B_h\le\max(0,c-\rho\mathcal{F}(\mathcal{M}_h)+\varepsilon) 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 ρ\rho of the fees, so, when the rational signers hold the same transactions, censoring fee value cc at a height is repeatable if and only if c<ρF(Mh)c<\rho\mathcal{F}(\mathcal{M}_h). Since ρ≤f/q\rho\le f/q, the construction is f/qf/q-censorship resistant (Definition 7), and censoring all of Mh\mathcal{M}_h is never repeatable when F(Mh)>0\mathcal{F}(\mathcal{M}_h)>0. 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 bb be certified at height hh with bandwidth ρ\rho, and let tx∈Mh\mathrm{tx}\in\mathcal{M}_h with tx.fee>0\mathrm{tx.fee}>0. Then tx∈b\mathrm{tx}\in b whenever

tx.fee≥ρ1−ρF(Mh∖{tx})+Bh1−ρ.\mathrm{tx.fee}\ge\frac{\rho}{1-\rho}\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\})+\frac{B_h}{1-\rho}.

Since ρ≤f2f+1\rho\le\frac{f}{2f+1}, it suffices that

tx.fee≥ff+1F(Mh∖{tx})+2f+1f+1Bh.\mathrm{tx.fee}\ge\frac{f}{f+1}\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\})+\frac{2f+1}{f+1}B_h.

Theorem 3 (Liveness). Assume adversarial participation and B≤D−FˉB\le D-\bar{F}. Then no honest client freezes, and the following hold.

  1. If the certificates of a valid ledger L\mathcal{L} have reached FhF_h by round ss, then every honest client that is awake throughout [s′,s′+4Δ][s',s'+4\Delta] for some s′≥ss'\ge s outputs, by round s′+4Δs'+4\Delta, a ledger that extends L\mathcal{L}.

  2. Let tx\mathrm{tx} be submitted by an honest client at round rr, and let δ>0\delta>0 be such that tx.fee≥ff+1F(Mh∖{tx})+δ\mathrm{tx.fee}\ge\frac{f}{f+1}\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\})+\delta at every height hh whose block is proposed after round r+Δr+\Delta. Then at most 2B/δ2B/\delta such heights certify a block without tx\mathrm{tx} before tx\mathrm{tx} is included.

Remark 1. Theorem 3 is weaker than liveness (Definition 4). By Theorem 2, a transaction whose fee stays below ρ1−ρF(Mh∖{tx})\frac{\rho}{1-\rho}\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\}) 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 ff+1\frac{f}{f+1} of the other pending fees when ρ=f/q\rho=f/q. 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 uu 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 E∈NE \in\mathbb{N}. Epoch ee consists of the rounds [eE,(e+1)E)[eE,(e+1)E). 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 heh_e for the last height of epoch ee, that is, the height of the last block whose epoch is at most ee, and σe\sigma_e for the state after the block of height heh_e. The committee of epoch ee is Ce=committee⁡(σe−1)C_e=\operatorname{committee}(\sigma_{e-1}), where committee⁡\operatorname{committee} is a fixed public function, and C0C_0 is the genesis committee. We abstract how transactions determine the committee. During epoch ee the members of CeC_e run Π\Pi, and a quorum certificate for a block of epoch ee carries qq signatures of distinct members of CeC_e. How the members of CeC_e obtain the ledger at the start of the epoch is part of Π\Pi. Full nodes run the static construction and store every well-formed certificate, since they track no committees.

Handover certificates. The transition from epoch e−1e-1 to epoch ee is certified by the outgoing committee. Every member of Ce−1C_{e-1} signs the pair (e,H(b))(e,H(b)), where bb is the block of height he−1h_{e-1} (Algorithm 3). A quorum of qq such signatures forms the handover certificate HOe\mathrm{HO}_e (Algorithm 3), which the first block above height he−1h_{e-1} includes (Algorithm 3). A certificate for a block of epoch e−1e-1 that extends bb, together with HOe\mathrm{HO}_e, is evidence of an equivocation by every validator that signed both, as is a pair of certificates for conflicting blocks.

Slashing. Fix u∈Nu \in\mathbb{N}. The stake of every validator in CeC_e remains locked, and slashable on evidence of an equivocation on the blocks of epoch ee or on HOe+1\mathrm{HO}_{e+1}, until 5Δ5\Delta rounds after the end of epoch e+ue+u. We call this period the bonding window of CeC_e. 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 ee against CeC_e, which it learns only after validating epoch e−1e-1, 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 (e0,Ce0,η0)(e_0, C_{e_0}, \eta_0): an epoch e0e_0, its committee Ce0C_{e_0}, and the hash η0\eta_0 of the block of height he0−1h_{e_0-1}. The client takes its anchor from the last ledger aa it confirmed, and e0e_0 is the epoch of the last block of aa. A client that has never confirmed a ledger holds the genesis anchor (0,C0,⊥)(0, C_0, \bot). The hash η0\eta_0 fixes the block of height he0−1h_{e_0-1} and, through the parent hashes, every block below it. The committee Ce0C_{e_0} 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 CC of the certifiable protocol. Algorithm 3 gives the witness consumer bootstrap, which verifies the committee changes across epochs. The client initializes L^b\hat{L}_b to aa and keeps its anchor, the state after aa, and L^\hat{L} across sleeps. A witness carries the blocks, certificates and handover certificates from height he0−1h_{e_0-1} onward. bootstrap checks that the witness extends the block that η0\eta_0 fixes, with increasing rounds and no block of an epoch below e0e_0 above it (Algorithm 3). It then validates one epoch at a time from e0e_0: every block of epoch e′e' is valid and carries a quorum certificate of Ce′C_{e'} (Algorithm 3), the next committee is derived from the state (Algorithm 3), and HOe′+1HO_{e'+1} is a quorum of Ce′C_{e'} (Algorithm 3). The ledger of a witness is the prefix of aa that ends at height he0−1h_{e_0-1}, 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 ee holds an anchor of epoch e0≥e−ue_0 \ge e-u. While it stays awake, its anchor must stay equally recent, except during the first 4Δ4\Delta rounds after it wakes, which it needs to confirm a new ledger: at every round rr at least 4Δ4\Delta rounds after it woke, its anchor is of epoch e0≥e′−ue_0 \ge e'-u, where e′e' is the epoch of rr.

Analysis

The proofs of this subsection are in Section B.

Theorem 4 (Dynamic safety). The construction of § 3 with bootstrap in place of CC 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 B<D−F‾\mathcal{B} < \mathcal{D} - \overline{\mathcal{F}}. 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 (e0,Ce0,η0)(e_0, C_{e_0}, \eta_0).

  1. upon entering epoch ee ▷ Run by every member of Ce−1C_{e-1}

  2. b←b \leftarrow the block of height he−1h_{e-1}

  3. cast a signature over (e,H(b))(e, H(b))

  4. HOe←\mathrm{HO}_e \leftarrow a quorum of qq such signatures by Ce−1C_{e-1}

  5. include HOe\mathrm{HO}_e in the first block above height he−1h_{e-1}

  6. end upon

  1. function bootstrap(w)(w) ▷ ww carries blocks, certificates and handovers from height he0−1h_{e_0-1} on

  2. if ww is not a hash chain with increasing rounds, its block of height he0−1h_{e_0-1} does not hash to η0\eta_0, or a block above it is of an epoch below e0e_0 then

  3. return ⊥\perp ▷ Diverges before the anchor

  4. end if

  5. for e′←e0e' \leftarrow e_0 to the last epoch in ww do ▷ Ce′C_{e'} is known here

  6. if some block of epoch e′e' in ww has no quorum certificate of Ce′C_{e'} or is invalid then

  7. return ⊥\perp ▷ Uncertified or invalid

  8. end if

  9. Ce′+1←committee⁡(σe′)C_{e'+1} \leftarrow\operatorname{committee}(\sigma_{e'}) ▷ σe′\sigma_{e'} is the state after height he′h_{e'}

  10. b←b \leftarrow the block of height he′h_{e'} in ww

  11. if ww has a block above height he′h_{e'} and HOe′+1\mathrm{HO}_{e'+1} in ww is not a quorum of Ce′C_{e'} over (e′+1,H(b))(e' + 1, H(b)) then

  12. return ⊥\perp

  13. end if

  14. end for

  15. return the blocks of ww above height he0−1h_{e_0-1}

  16. end function

Two conflicting witnesses that pass bootstrap first differ in an epoch d≥e0d \ge e_0 whose committee both designate, and the handover certificate makes the fork an equivocation of CdC_d (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 KK of 3f+13f + 1 keys and every block pp, some valid block of epoch ee with parent pp, which Π\Pi may output, makes committee designate KK as Ce+1C_{e+1}.

The long-range attack. Fix epochs dd and e>d+ue > d + u and a budget B>0B > 0. Let the committees designated after the last block bb of epoch dd consist of keys that no earlier committee holds. Let an honest client cc be awake during epoch dd, fall asleep before bb is proposed, and wake during epoch ee, after step 2 below. The adversary acts as follows.

  1. He follows the protocol until an always-on honest client has output a ledger that contains a block of epoch d+1d+1 and the bonding window of CdC_d has ended.

  2. He pays B/(2q)B/(2q) to each rational member of CdC_d. In return, it signs a block b′b' of epoch dd with the parent and height of bb, after which committee designates keys he generated, and the handover certificate that names b′b'.

  3. He extends b′b' epoch by epoch up to epoch ee, certifying every block and handover with keys he holds.

  4. He answers the requests of cc from a full node he controls, exactly as FhF_h would answer them in the execution in which b′b' was certified in epoch dd and bb 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 uu epochs and a function committee with the property above, in which honest clients output only ledgers of certified blocks. Let E>7ΔE > 7\Delta, let the adversary hold any budget B>0B > 0, and let e>d+ue > d + u. 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 d+1d + 1 by the end of epoch e−1e - 1; and that the client cc above eventually does.

In the execution with the attack and in the one where bb and b′b' exchange roles, cc has the same local state and receives the same messages, so it outputs the same ledger. By safety, that ledger extends bb in one execution and b′b' in the other. FhF_h does not help, because cc 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 e0e_0 keeps the guarantees of the static case in epoch ee if e−e0≤ue - e_0 \le u, and not necessarily if e−e0>ue - e_0 > u. 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 f+1f + 1 validators, his own among them, and the adversary must pay a rational one more than D−Fˉ/qD - \bar{F}/q (Lemma 1), for instance from saved rewards.

Censorship. Transactions whose fee is below a ρ\rho 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 tt, and let an honest client cc run a confirmation at round s≥t+2Δs \ge t + 2\Delta. Then cc holds the certificate when the confirmation runs.

Proof. The relay reaches FhF_h by round t+Δt+\Delta. Let t′≤t+Δt' \le t+\Delta be the round at which FhF_h first receives the certificate. By Algorithm 1, FhF_h relays it at round t′t'. Let twt_w be the round at which cc last woke before round ss, or 00 if cc has been awake since the first round. A client that falls asleep discards its pending confirmations, so cc scheduled the confirmation at a round t′′≥twt'' \ge t_w and is awake from round twt_w to round ss. By Algorithm 2, s=t′′+2Δ≥tw+2Δs = t'' + 2\Delta\ge t_w + 2\Delta.

Case 1: tw≤t′t_w \le t'. Then cc is awake from round t′t' to round t′+Δ≤t+2Δ≤st' + \Delta\le t + 2\Delta\le s, and the relay of FhF_h reaches it by round t′+Δt' + \Delta.

Case 2: tw>t′t_w > t'. At round twt_w, cc multicasts a request (Algorithm 2). The request reaches FhF_h by round tw+Δt_w + \Delta. FhF_h holds the certificate from round t′<twt' < t_w, so the reply of Algorithm 1 carries it and reaches cc by round tw+2Δ≤st_w + 2\Delta\le s.

In both cases cc receives the certificate by round ss and keeps it in RR, since it does not sleep between rounds twt_w and ss. A client processes the messages of a round before its confirmations, so cc holds the certificate when the confirmation runs.

Proof of Theorem 1. Suppose towards a contradiction that honest clients c1c_1 and c2c_2 output ledgers L1=Lr1c1\mathcal{L}_1 = \mathcal{L}_{r_1}^{c_1} and L2=Lr2c2\mathcal{L}_2 = \mathcal{L}_{r_2}^{c_2} with L1≁L2\mathcal{L}_1 \not\sim\mathcal{L}_2. By Algorithm 2 the output of a client only grows by extension, so c1c_1 confirmed L1\mathcal{L}_1 at some round s1≤r1s_1 \le r_1 and c2c_2 confirmed L2\mathcal{L}_2 at some round s2≤r2s_2 \le r_2. By symmetry we may assume s1≤s2s_1 \le s_2.

Let t1t_1 be the round at which the witness for L1\mathcal{L}_1 became complete at c1c_1. By Algorithm 2, s1=t1+2Δs_1 = t_1 + 2\Delta. By Algorithm 2, c1c_1 relayed every certificate of the witness by round t1t_1. By Lemma 2, c2c_2 holds all of them when its confirmation at round s2≥t1+2Δs_2 \ge t_1 + 2\Delta runs. The consumer CC is deterministic, so by Algorithm 2 c2c_2 has added L1\mathcal{L}_1 to SS by then. Then Algorithm 2 stops c2c_2 from confirming L2\mathcal{L}_2 at round s2s_2. Contradiction. □\square

Proof of Lemma 1. Let QCb\mathrm{QC}_b and QCb′\mathrm{QC}_{b'} certify conflicting blocks bb and b′b'. Each carries q=2f+1q = 2f + 1 signatures of distinct validators out of n=3f+1n = 3f + 1, so

∣signers⁡(QCb)∩signers⁡(QCb′)∣≥2q−n=f+1.\lvert\operatorname{signers}(\mathrm{QC}_b) \cap\operatorname{signers}(\mathrm{QC}_{b'}) \rvert\ge2q - n = f + 1.

Every validator in the intersection equivocates. At most ff validators are Byzantine, so the intersection contains a rational validator.

Let vv be a rational validator that loses its stake DD for an equivocation. By Theorems 1 and 4, no two honest clients confirm conflicting ledgers. So vv receives at most one block reward from the equivocation, which is at most Fˉ/q\bar{F}/q, and gains nothing from a double-spend. Had vv not equivoc­ated, 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 vv more than D−Fˉ/qD - \bar{F}/q before vv signs. Let hh be the height to which this payment is charged; a payment for a signature on HOe\mathrm{HO}_e is charged to the height of the block that HOe\mathrm{HO}_e names. The adversary receives gh≤1qFˉg_h \le\frac{1}{q}\bar{F} from height hh, since the block rewarded at height hh 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 Bh>D−1qFˉ−1qFˉ≥D−FˉB_h > D - \frac{1}{q}\bar{F} - \frac{1}{q}\bar{F} \ge D - \bar{F}, which is positive since D>FˉD > \bar{F}.

By accountability, the rational validator in the intersection loses its stake, so the adversary draws more than D−FˉD - \bar{F} from B\mathcal{B}. If B≤D−Fˉ\mathcal{B} \le D - \bar{F}, this contradicts

∑hBh≤B,\sum_h B_h \le\mathcal{B},

so no two conflicting blocks are certified. A client freezes only when SS 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. □\square

Proof of Theorem 2. Let bb be the block certified at height hh, proposed at round rr, and let R\mathcal{R} be the set of rational signers of QCb\mathrm{QC}_b. Write V=F(Mh)V = \mathcal{F}(\mathcal{M}_h) and cens=censh\mathrm{cens} = \mathrm{cens}_h. Then ∣R∣=q−f∗=(1−ρ)q\lvert\mathcal{R} \rvert= q - f^* = (1 - \rho)q and F(b)=V−cens\mathcal{F}(b) = V - \mathrm{cens}.

Upper bound. Let v∈Rv \in\mathcal{R}. By adversarial participation, vv compares signing bb with signing b∪Mrvb \cup\mathcal{M}_r^v. By Definition 6, every transaction of Mh\mathcal{M}_h that is not in bb is held by vv, so the second block carries at least cens\mathrm{cens} more fees and pays vv at least cens/q\mathrm{cens}/q 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 cens>0\mathrm{cens} > 0, vv signs bb only if the adversary pays it more than cens/q\mathrm{cens}/q before it signs. The side payments charged to height hh therefore exceed (1−ρ)cens⁡(1-\rho)\operatorname{cens}. His validators receive gh≤ρF(b)=ρ(V−cens⁡)g_h \le\rho\mathcal{F}(b)=\rho(V-\operatorname{cens}) from bb. By the definition of BhB_h,

(1−ρ)cens⁡<ρ(V−cens⁡)+Bh,(1-\rho)\operatorname{cens}<\rho(V-\operatorname{cens})+B_h,

and adding ρcens⁡\rho\operatorname{cens} to both sides gives cens⁡<ρV+Bh\operatorname{cens}<\rho V+B_h.

Tightness. Let every v∈Rv\in\mathcal{R} hold the same set MM of pending transactions, and let X⊆MX\subseteq M have total fee c>0c>0. The adversary has b=M∖Xb=M\setminus X proposed, by one of his validators or by a paid rational signer, signs it with f∗=ρqf^*=\rho q of his validators, and pays each rational signer (c+ε)/q(c+\varepsilon)/q. A rational signer receives (V−c)/q+(c+ε)/q(V-c)/q+(c+\varepsilon)/q by signing bb and V/qV/q by signing b∪M=Mb\cup M=M, so it strictly prefers to sign bb. The block bb is certified with Mh=M\mathcal{M}_h=M and cens⁡h=c\operatorname{cens}_h=c. The adversary pays (1−ρ)(c+ε)(1-\rho)(c+\varepsilon) and receives gh=ρ(V−c)g_h=\rho(V-c) once bb is confirmed, so Bh=max⁡(0,c−ρV+(1−ρ)ε)≤max⁡(0,c−ρV+ε)B_h=\max(0,c-\rho V+(1-\rho)\varepsilon)\le\max(0,c-\rho V+\varepsilon). □\square

Proof of Corollary 1. Suppose towards a contradiction that tx∉b\mathrm{tx}\notin b. Then tx∈Mh∖b\mathrm{tx}\in\mathcal{M}_h\setminus b, so cens⁡h≥tx.fee>0\operatorname{cens}_h\ge\mathrm{tx.fee}>0, and Theorem 2 gives tx.fee≤cens⁡h<ρF(Mh)+Bh\mathrm{tx.fee}\le\operatorname{cens}_h<\rho\mathcal{F}(\mathcal{M}_h)+B_h. Substituting F(Mh)=tx.fee+F(Mh∖{tx})\mathcal{F}(\mathcal{M}_h)=\mathrm{tx.fee}+\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\}) and rearranging gives (1−ρ)tx.fee<ρF(Mh∖{tx})+Bh(1-\rho)\mathrm{tx.fee}<\rho\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\})+B_h, which contradicts the hypothesis. For the second form, the maps ρ↦ρ1−ρ\rho\mapsto\frac{\rho}{1-\rho} and ρ↦11−ρ\rho\mapsto\frac{1}{1-\rho} are increasing on [0,1)[0,1), so the right-hand side is largest at ρ=f2f+1\rho=\frac{f}{2f+1}, where it equals ff+1F(Mh∖{tx})+2f+1f+1Bh\frac{f}{f+1}\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\})+\frac{2f+1}{f+1}B_h. □\square

Proof of Theorem 3. By Lemma 1, no two conflicting blocks are certified and no honest client freezes.

Item 1. Let cc be awake throughout [s′,s′+4Δ][s',s'+4\Delta] and let tw≤s′t_w\le s' be the round at which it last woke. Consider a certificate of L\mathcal{L} and let t′≤st'\le s be the round at which FhF_h first received it. If t′≥twt'\ge t_w, the relay of FhF_h at round t′t' (Algorithm 1) reaches cc by round t′+Δ≤s′+Δt'+\Delta\le s'+\Delta. If t′<twt'<t_w, the request of cc at round twt_w (Algorithm 2) reaches FhF_h by round tw+Δt_w+\Delta, and the reply of Algorithm 1 carries the certificate and reaches cc by round tw+2Δ≤s′+2Δt_w+2\Delta\le s'+2\Delta. So the witness for L\mathcal{L} is complete at cc by round s′+2Δs'+2\Delta, and by Algorithm 2 its confirmation runs by round s′+4Δs'+4\Delta. Every ledger in S\mathcal{S} and the output L^\widehat{\mathcal{L}} consist of certified blocks, and no two conflicting blocks are certified. So Algorithm 2 passes, and L^\widehat{\mathcal{L}} is consistent with L\mathcal{L}. If L^⪯L\widehat{\mathcal{L}}\preceq\mathcal{L}, then Algorithm 2 outputs L\mathcal{L}. Otherwise L⪯L^\mathcal{L}\preceq\widehat{\mathcal{L}}. In both cases the output extends L\mathcal{L}.

Item 2. The submitting client sends tx\mathrm{tx} to every validator, and validators are always awake, so from round r+Δr+\Delta every validator holds tx\mathrm{tx} until it is included. Let hh be a height whose block bb is proposed after round r+Δr+\Delta and certified with bandwidth ρ\rho, and let tx∉b\mathrm{tx}\notin b. Then tx∈Mh\mathrm{tx}\in\mathcal{M}_h. By Corollary 1,

Bh>(1−ρ)tx.fee−ρF(Mh∖{tx})=(1−ρ)(tx.fee−ρ1−ρF(Mh∖{tx})).B_h>(1-\rho)\mathrm{tx.fee}-\rho\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\})=(1-\rho)\left(\mathrm{tx.fee}-\frac{\rho}{1-\rho}\mathcal{F}(\mathcal{M}_h\setminus\{\mathrm{tx}\})\right).

Since ρ1−ρ≤ff+1\frac{\rho}{1-\rho}\le\frac{f}{f+1}, the bracket is at least δ\delta. Since 1−ρ≥f+12f+1>121-\rho\ge\frac{f+1}{2f+1}>\frac{1}{2}, we get Bh>δ/2B_h>\delta/2. As ∑hBh≤B\sum_h B_h\le B, there are at most 2B/δ2B/\delta such heights before tx\mathrm{tx} is included. □\square

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 L\mathcal{L} that an honest client confirms at round ss. First, every certificate of L\mathcal{L} was relayed by an honest client by round s−2Δs - 2\Delta. Second, the rounds of the blocks of L\mathcal{L} increase, and every block of L\mathcal{L} is valid and carries a quorum certificate of the committee that L\mathcal{L} designates for its epoch. Every handover certificate in L\mathcal{L} is a quorum of the committee of the epoch it ends. Both facts hold by induction on ss. Let aa be the ledger from which the client took the anchor (e0,Ce0,η0)(e_0,C_{e_0},\eta_0) that it used for L\mathcal{L}. The blocks, certificates and handover certificates of L\mathcal{L} from height he0−1h_{e_0}-1 onward form the witness, which the client relayed at Algorithm 2 by the round tt at which it became complete. By Algorithm 2, s=t+2Δs = t + 2\Delta. bootstrap checked them at Algorithm 3. The output of the client starts at aa and grows by extension (Algorithm 2), so a⪯La \preceq\mathcal{L}, and the blocks and handover certificates of L\mathcal{L} up to the last block of aa belong to aa. This covers HOe0\mathrm{HO}_{e_0}, which lies in the first block above height he0−1h_{e_0}-1. Either aa is empty, or the client confirmed aa at an earlier round and the induction hypothesis applies.

Towards a contradiction, let the confirmation of L2\mathcal{L}_2 by c2c_2 at round s2s_2 be the first that conflicts with an earlier one, and let c1c_1 have confirmed L1≁L2\mathcal{L}_1 \not\sim\mathcal{L}_2 earlier, at round s1≤s2s_1 \le s_2. By the first fact, every certificate of L1\mathcal{L}_1 was relayed by an honest client by round s1−2Δ≤s2−2Δs_1 - 2\Delta\le s_2 - 2\Delta. By Lemma 2, c2c_2 holds all of them when its confirmation at round s2s_2 runs. Let aa be the ledger from which c2c_2 took the anchor it holds when it receives the last of them. Either aa is empty or c2c_2 confirmed it before round s2s_2, so a∼L1a \sim\mathcal{L}_1 by the choice of L2\mathcal{L}_2. The output of c2c_2 grows only by extension (Algorithm 2) and c2c_2 outputs L2\mathcal{L}_2 at round s2s_2, so a⪯L2a \preceq\mathcal{L}_2. If L1⪯a\mathcal{L}_1 \preceq a, then L1⪯L2\mathcal{L}_1 \preceq\mathcal{L}_2, which contradicts L1≁L2\mathcal{L}_1 \not\sim\mathcal{L}_2. Hence a⪯L1a \preceq\mathcal{L}_1.

The blocks, certificates and handover certificates of L1\mathcal{L}_1 from height he0−1h_{e_0}-1 onward form a witness. It passes Algorithm 3 because a⪯L1a \preceq\mathcal{L}_1: the rounds of L1\mathcal{L}_1 increase by the second fact, and its block after the anchor block is that of aa, which is of epoch e0e_0. The ledgers aa and L1\mathcal{L}_1 agree up to height he0−1h_{e_0}-1, so they designate the same committee Ce0C_{e_0}, and by the second fact the witness passes Algorithm 3. So bootstrap returns the blocks of L1\mathcal{L}_1 above height he0−1h_{e_0}-1, and c2c_2 adds L1\mathcal{L}_1 to SS at Algorithm 2 before its confirmation runs. Then Algorithm 2 stops c2c_2 from confirming L2\mathcal{L}_2 at round s2s_2, which contradicts the choice of L2\mathcal{L}_2. □\square

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 xx with an anchor of epoch e0e_0 taken from a ledger aa, and call a ledger admissible if it agrees with aa up to height he0−1h_{e_0}-1 and passes the checks of bootstrap above that height.

  1. Round xx is at most 4Δ4\Delta rounds after the end of epoch e0+ue_0 + u.

  1. The bound on Byzantine members holds for every committee that an admissible ledger, or a ledger that an honest client confirms, designates.

  1. If two admissible ledgers conflict, then there is an epoch d≥e0d \ge e_0 such that at least f+1f + 1 members of CdC_d equivocated on the blocks of epoch dd or on HOd+1\mathrm{HO}_{d+1}, and at least one of them is rational.

Proof. Item 1. The anchor of a client only moves forward. If xx comes at least 4Δ4\Delta rounds after the client woke, then by client freshness xx lies in an epoch at most e0+ue_0 + u. Otherwise the client woke fewer than 4Δ4\Delta rounds before xx, during an epoch ee with e−u≤e0e-u \le e_0, so xx is less than 4Δ4\Delta rounds after the end of epoch e0+ue_0 + u.

Item 2. Let L\mathcal{L} be admissible. By Algorithm 3, the blocks of L\mathcal{L} above height he0−1h_{e_0-1} are of epochs at least e0e_0, and the client holds their certificates by round xx. By item 1, each was formed within the bonding window of its signers, which lasts until 5Δ5\Delta rounds after the end of an epoch at least e0+ue_0 + u. The blocks at or below height he0−1h_{e_0-1} are those of aa. The client confirmed aa at an earlier round, while fresh, so the same argument applies to aa, 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 L\mathcal{L} and L′\mathcal{L}' be the two ledgers. They agree up to height he0−1h_{e_0-1}. Let ii be the first position at which they differ, and let yy and y′y' be their blocks at position ii. Both have the same parent pp. Let d≥e0d \ge e_0 be the smaller of the epochs of yy and y′y', say the epoch of yy. The rounds of the blocks of a ledger increase with height, so every block of an epoch before dd lies at or below pp in both ledgers. Hence both ledgers have the same state σd−1\sigma_{d-1} and designate the same committee CdC_d, to which the bound applies by item 2.

Case 1: y′y' is also of epoch dd. By Algorithm 3, yy and y′y' carry quorum certificates of CdC_d. They conflict, since they differ and have the same parent.

Case 2: y′y' is of a later epoch. Then pp is the block of height hdh_d in L′\mathcal{L}', and L′\mathcal{L}' has a block above it. By Algorithm 3, L′\mathcal{L}' carries HOd+1\mathrm{HO}_{d+1}, a quorum of CdC_d over (d+1,H(p))(d + 1, H(p)). By Algorithm 3, yy carries a quorum certificate of CdC_d, and yy is a block of epoch dd that extends pp.

In both cases two quorums of CdC_d sign an equivocation. They share at least 2q−n=f+12q - n = f + 1 members, and at most ff members of CdC_d are Byzantine. □\square

Proof of Theorem 5. Suppose towards a contradiction that an honest client cc freezes. Then S\mathcal{S} holds two conflicting ledgers L1L_1 and L2L_2, and let L2L_2 be the later to enter S\mathcal{S}, at round xx. Let aa be the ledger of the anchor of cc at round xx, of epoch e0e_0. The ledger L2L_2 passed bootstrap under this anchor, so it is admissible. Either L1L_1 also passed bootstrap under it, or cc confirmed aa while L1L_1 was in S\mathcal{S}, in which case L1∼aL_1 \sim a by Algorithm 2. Since L1L_1 conflicts with L2L_2, which agrees with aa up to height he0−1h_{e_0-1}, L1L_1 also agrees with aa up to that height. Its blocks above it either belong to aa, which an honest client confirmed, or were checked by bootstrap with the committees that its own prefix designates, so L1L_1 is admissible as well.

By item 3 of Lemma 3, a rational member vv of some CdC_d with d≥e0d \ge e_0 equivocated on the blocks of epoch dd or on HOd+1\mathrm{HO}_{d+1}. 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 x+Δx+\Delta. By item 1 of Lemma 3, this is at most 5Δ5\Delta rounds after the end of epoch e0+u≤d+ue_0+u\le d+u, inside the bonding window of CdC_d, so vv loses its stake DD. By Lemma 1, the adversary draws more than D−FˉD-\bar{F} from B\mathcal{B}, which contradicts B≤D−Fˉ\mathcal{B}\le D-\bar{F}. So no honest client freezes.

Item 1 of Theorem 3 concerns a ledger L\mathcal{L} that an honest client has confirmed. FhF_h holds its certificates and handover certificates. By Theorem 4, the ledger aa of the anchor of cc satisfies a∼La\sim\mathcal{L}. If L⪯a\mathcal{L}\preceq a, the output of cc already extends L\mathcal{L}. Otherwise a⪯La\preceq\mathcal{L}, and the witness of L\mathcal{L} from height he0−1h_{e_0-1} passes bootstrap, since L\mathcal{L} was confirmed by an honest client and its blocks above aa are of epochs at least e0e_0. The timing of the static proof applies, cc does not freeze, and L^∼L\widehat{\mathcal{L}}\sim\mathcal{L} by Theorem 4, so the output of cc extends L\mathcal{L}. 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 ρ≤f/q\rho\le f/q at each such height, and Theorem 2 and Corollary 1 apply as in the static case. □\square

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 d+1d+1. We show that cc 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 LA\mathcal{L}_A that contains a block of epoch d+1d+1 by the end of epoch e−1e-1. The bonding window of CdC_d ends 5Δ5\Delta rounds after the end of epoch d+u≤e−1d+u\le e-1, and buying the signatures of step 2 takes at most 2Δ2\Delta rounds more. Since E>7ΔE>7\Delta, steps 1 and 2 end within epoch ee, and cc can wake in epoch ee after them. Let bb be the last block of epoch dd in LA\mathcal{L}_A and let PP be the prefix of LA\mathcal{L}_A below bb. In step 2, the bonding window of CdC_d has ended, and the keys designated after bb are fresh, so a member of CdC_d holds no stake and no seat that signing b′b' 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 (2f+1)B/(2q)=B/2(2f+1)B/(2q)=B/2. The branch through b′b' is certified after the bonding window of CdC_d, 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 b′b' carries a quorum of the committee that its own prefix designates, as on the branch through bb.

Execution B. By the property of committee, some valid block b′b' of epoch dd with the parent of bb, which Π\Pi may output, designates a set of fresh keys. Let B agree with A until bb is proposed. In B the protocol outputs b′b' as the last block of epoch dd, and the keys that the branch through b′b' designates belong to validators, ff Byzantine and 2f+12f+1 rational in every committee. The adversary runs steps 1 to 4 with bb in place of b′b': he buys the signatures of CdC_d on bb and its handover certificate, and holds the fresh keys that the branch through bb designates, to which the bound again does not apply. By the second guarantee, the always-on honest client of B outputs a ledger LB\mathcal{L}_B that contains a block of epoch d+1d+1 by the end of epoch e−1e-1, 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 bb is b′b'. So LB\mathcal{L}_B extends PP by b′b'.

Fix the random coins of cc to be the same in A and B. The two executions agree until bb is proposed, and cc sleeps from then until it wakes in epoch ee, so cc has the same local state in both. After waking, cc receives messages from full nodes and validators only. In A, the adversary sends to cc, from his full node and from the keys of the branch through b′b', exactly the messages that FhF_h and the validators of the branch through b′b' send to cc in B. In B he does the same with bb and b′b' swapped. He delivers every message to cc exactly Δ\Delta rounds after it is sent. So cc receives the same messages at the same rounds in A and B, and outputs the same ledgers.

Suppose towards a contradiction that cc outputs a ledger Lc\mathcal{L}_c that contains a block of epoch d+1d+1. In A, safety gives Lc∼LA\mathcal{L}_c \sim\mathcal{L}_A. The blocks of PP are of epoch at most dd, so Lc\mathcal{L}_c is not a prefix of PP, and Lc\mathcal{L}_c agrees with LA\mathcal{L}_A at the position of bb. The block of Lc\mathcal{L}_c at that position is therefore bb. In B, the same argument with LB\mathcal{L}_B gives b′b'. This contradicts b≠b′b \ne b'. So if safety holds in A and in B, then cc outputs no ledger that contains a block of epoch d+1d+1, in either execution. ∎

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [10]Buchman, E., Kwon, J., Milosevic, Z.: The latest gossip on BFT consensus (2018), https://arxiv.org/abs/1807.04938
  11. [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. [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. [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. [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. [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. [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. [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. [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. [19]Lewis-Pye, A., Roughgarden, T.: Permissionless consensus (2023), https://arxiv.org/abs/2304.14701
  20. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [32]Sridhar, S., Zindros, D., Tse, D.: Better safe than sorry: Recovering after adversarial majority (2023), https://arxiv.org/abs/2310.06338
  33. [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. [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. [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. [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

Paper details

vlnc:W_bajw8766
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents