[2302.11326.pdf](https://arxiv.org/pdf/2302.11326.pdf) ## Introduction ### Balancing dynamic availability and asynchrony resilience A *dynamically available* protocol preserves liveness and safety during events involving portions of the participants going offline Formalized my Pass and Shi through the [[sleepy model]] of consensus Limitation of [[dynamic participation]]/availability is that no consensus protocol can satisfy liveness under dynamic participation and safety under temporary network partitions [[availability-finality dilemma]] Consequently, dynamically available protocols assumed to be synchronous LMD GHOST is not secure even when all validators are online due to the [[balancing attacks]] [[Goldfish]] was presented as a solution to these challenges Synchronous Dynamically available Uses view-merge, enabling coordination between honest voters and an honest proposer Vote expiry only considers the most recent slot's votes Impractical for Ethereum because of its lack of resilience to temporary asynchrony The strict vote expiry period means that even short asynchrony can jeopardize the safety of any previously confirmed block This paper proposes [[RLMD-GHOST]], analyzed by introducing generalized [[sleepy model]], and formally define the concept of [[asynchrony resilience]] ### Technical Outline #### LMD-GHOST and its security Ethereum's Gasper has two components: - LMD-GHOST: synchronous consensus protocol - Casper: partially synchronous protocol that finalized blocks on the chain output by LMD-GHOST and keeps finalized blocks safe during periods of asynchrony [[LMD-GHOST]] is a fork choice function that takes the sequence of blocks and votes from each validator $v_{i}$ (so the local view of $v_{i}$) and outputs a canonical chain Starts from genesis block and walks down the sequence of blocks, choosing the next one as the child of B with the heaviest subtree - the ones with most (stake-weighted) latest votes on its descendants Can be thought of as propose-vote protocol Votes for a proposed block are cast by a randomly selected subset of the validator set called a *committee*, so a subsampling of validators are used Both proposer and voters use output of LMD-GHOST FC to decide what block to extend and vote for **Balancing Attack** Validators can have different local views leading to conflicting votes An adversarial proposer of slot t could produce two conflicting blocks which it reveals to two chosen equal-sized subsets of the committee. It then releases withheld votes from the committee of slot t to split validators of slot t + 1 into two equal-sized subsets, each seeing one of the two chains as leading and voting for that one Can be repeated indefinitely and break the liveness of LMD-GHOST [[Proposer Boost]] technique introduced as a mitigation to help coordinate the voters in slots with an honest proposer Honest voters temporarily grant extra weight to current proposal **[[Ex-ante reorgs]]** LMD-GHOST still prone to these even under full participation Consider an adversary controlling a fraction $\beta$ of the validators, among which the proposer for slot t + 1 This proposer privately creates a block B' on top of the block for slot t, B Say the adversary controls roughly a fraction $\beta$ of the validators sampled to vote at slot t+1, and they privately vote for B' Honest voters who don't see this block will vote for B In the next slot, t+2, an honest proposer publishes B'' building on B, which is the current tip of the canonical chain in their local view All honest validators in the committee of slot t + 2 vote for it, so B'' accrues 1 - $\beta$ of one committee's weight, (1-$\beta)W_{c}$ After, the adversary published B' and its votes from slot t+1 and t+2 for it. At this point B has weight about 2$\beta W_{c}$. If $\beta > \frac{1}{3}$, B' becomes canonical, reorging B'' because B' If an adversary controls k slots in a row, which is probability $\beta^k$, can withhold votes from these slots and release them after one honest slot This results in (k+1)$\beta W_{c}$ weight for a withheld adversarial block If $\beta > \frac{1}{k+2}$ this results in a reorg of the honestly proposed block Subsampling crucial in the success of the attack since the adversary is able to accumulate the votes of the validators it controls across the k committees. Without subsampling, the adversarial votes from the last slot would simply replace the ones from the previous slots, due to the latest message rule *Without subsampling there is no way for the adversary to overcome the weight of all honest validators voting together in one slot*, as they are a majority over the entire validator set **Dynamic availability failure due to stale votes** LMD-GHOST is insecure under dynamic participation Consider a validator set of |V1| = |V2| >> |V3| and V3 is adversarial Let t-1 and t be slots with adversarial proposers In t, adversary publishes conflicting blocks B and B', one as a proposal for t-1 and the other for t This is done in such a way that validators in V1 only receive B before voting, and V2 only see B', and both vote respectively B will become canonical, since V1 is slightly greater than V2. Next, V2 validators go offline Adversary can now wait arbitrarily long and then release the votes for B' This results in a reorg from B to B' since the latest votes of V2 are those for B', from slot t, and are still counted. If no decision is made, liveness under dynamic participation has failed. If one is made, it's for a descendant of B, and there's a safety failure #### Goldfish Synchronous consensus protocol with liveness and safety *under fully variable participation* -> dynamically available It's also *[[reorg resilient]]*: blocks proposed by honest validators are guaranteed inclusion in the chain Based on two techniques: *[[view-merge]]* and *vote expiry* Inherits propose-vote structure of LMD-GHOST and adds a third round for view-merge Structure can be generalized by the family of [[propose-vote-merge]] protocols View-merge is an improvement over proposer boost and serves the same purpose: coordinating honest voters in slots with an honest proposer Lets an honest proposer synchronize the local views of honest voters with its own, and *ensures* they cast votes for the proposed block With vote expiry, only votes from the latest slot influence the fork-choice Thus, adversary has no weight to accumulate weight across committees, and no way to overpower the coordinated voting of honest voters in a committee Thus it solves two problems at once: 1. Ex-ante reorgs caused by subsampling 2. Lack of dynamic availability due to adversary exploiting votes of offline validators, as they now expire View-merge and vote expiry together make for a reorg-resilient protocol View-merge ensures than an honest proposal B from slot t receives all votes from honest and online validators in the sampled committee of slot t By vote expiry, only votes from the committee of slot t are counted in slot t+1 (voters in slot t+1 use them as input to their fork-choice function when determining what to vote for) Reorg resilience immediately implies that the $\kappa$-deep confirmation rule is both safe and live, implying dynamic availability for Goldfish Goldfish's strict vote expiry can cause the weight supporting a block to drop to zero at any time if no new votes supporting it are received within one slot. Thus, it is *not* asynchrony resilient, and can not replace LMD-GHOST in Ethereum #### RLMD-GHOST Strict vote expiry does not seem compatible with any reasonable notion of resilience to asynchrony Neither is not expiring votes, where honest but offline validators can be exploited to conclude long reorgs Relaxing vote expiry is a natural approach RLMD-GHOST is in the family of propose-vote-merge consensus protocol parameterized by the *vote expiry period $\eta$* Only votes from the most recent $\eta$ slots are utilized in the protocol Relaxing vote expiry forces the removal of subsampling to avoid reintroducing ex-ante reorgs through accumulating votes from multiple committees. So every validator votes in every slot of RLMD-GHOST This would break reorg resilience When $\eta=1$, RLMD-GHOST reduces to a variant of Goldfish without subsampling of validators When $\eta=\infty,$ RLMD-GHOST reduces to LMD-GHOST (not as implemented in Ethereum but without subsampling and implementing view-merge instead of proposer boost, so also a propose-vote-merge protocol) Considering votes from a longer period ($\eta>1$) results in a more asynchrony-tolerant protocol, since a correspondingly longer period of asynchrony is needed for all votes to expire On the other hand, relaxing vote expiry should weaken dynamic availability. Because the fork choice can now be impacted by the (still unexpired) votes of offline validators, as in LMD-GHOST In the reorg resilience argument for Goldfish, after an honest slot t with proposal B, honest voters at slot t+1 still vote for B because the honest votes from slot t outnumber adversarial votes and there are no further votes to consider. With a longer expiry period $\eta>1$ this is no longer the case, because at slot t+1 all votes from slots \[t+1-$\eta$,t] have to be considered. **REMARK:** This seems like it finally makes sense to me. When you increase $\eta$, you have to consider votes from previous slots in determining which chain to follow. When it equals 1, you only look at the previous slot and what block is there to see where to extend. When it equals 2, you look at the last two slots, see which chain has the heavier weight and go from there. I think? #### Generalized Sleepy Model Allows us to capture a weaker notion of dynamic availability and precisely define a notion of *asynchrony resilience* Computing the fork-choice at slot t now requires considering all votes from slots \[t − η, t − 1] If there has been an honest proposal in slot t-1, the only votes which are guaranteed to vote in support of it are those from honest validators which were online in slot t-1, defined as $H_{t-1}$ All other votes are either from adversarial or offline validators, and potentially dangerous in both cases Let $H_{s,t}$ be the honest validators online in slots \[s,t] and $A_{t}$ be the validators corrupted up to slot t. Require $|H_{t-1}|>|A_{t}| \cup (H_{t-\eta,t-2} \setminus H_{t_-1})$ The number of validators that were active at some point between two slots but not at the last slot must be less than or equal to $\eta$ times the number of adversarial validators in the current slot When $\eta=1$, we recover standard majority assumption $|H_{t-1}|>|A_{t}|$ The more general condition is the key assumption of the generalized sleepy model, allowing us to describe a spectrum of dynamic participation regimes by varying the parameter If the assumption holds for a certain $\eta$, then the corresponding RLMD-GHOST protocol is reorg resilient and consequently secure Extending the generalized sleepy model further allows for bounded periods of asynchrony ## Model and Preliminary Notions ### System Model Validators, Byzantine faults considered Best-effort gossip primitive that will reach all validators is available Time divided into discrete rounds of $\Delta$ and a slot as a collection of k rounds, where k = $3\Delta$ Honest validators that become awake at round r must first execute and terminate a joining protocol, after which they become active In each slot t, a validator $v_{p}$ is selected to be the proposer, extending teh chain with a new block. Assume the existence of a proposer selection mechanism that's unique, unpredictable, and fair. The identity of $v_{p}$ is only known to other validators once $v_{p}$ reveals itself A view at a given round r is a subset of all the messages that a process has received until r. Notion of view is local for the validators A view is valid if all messages within it are verifiably valid, meaning all messages they reference are also contained in the vie wand themselves valid In particular, a block contains reference to its parent block, and verifying its validity requires also being able to verify the parent's validity. Implicitly, we only consider valid messages and views For two chains ch1 and ch2, we say ch1 <= ch2 if ch1 is a prefix of ch2. If block B is the tip of chain ch, we say that it is the head of ch, and we identify the whole chain with B. Accordingly, if ch′ <= ch and A is the head of ch′ , we also say ch′ <= B and A <= B. A fork-choice function is a deterministic function FC, which takes as input a view V and a slot t and outputs a block B, satisfying the following consistency property: if B is a block extending FC(V, t), then FC(V ∪ {B}, t) = B. We refer to the output of FC as the head of the canonical chain in V, and to the chain whose head is B as the canonical chain in V. Each validator keeps track of its canonical chain, which it updates using FC, based on its local view. We refer to the canonical chain of validator vi at round r as $ch_{i}^r$ Pivot slot refers to a slot in which the proposer is active at proposal time, a slot in which an honest proposal is made ### Generalized sleepy model We'll now formulate a one-parameter family of adversarial restrictions to generalize the usual sleepy model, then a two-param family which generalizes it further by introducing and accounting for bounded periods of asynchrony #### $\tau$-sleepy model $h_{r}$ = number of honest validators active at round r $f_{r}$ = number of adversarial validators at round r In sleepy model, adversary is constrained by the requirement that awake validators outnumber adversarial validators in every round by a constant factor c > 1 In this model, the requirement is **$h_{r} > cf_{r}$** D'Amato, Neu, Tas, and Tse introduce the notion of an active validator - validators that have completed the joining protocol - and assume the modified condition $h_{r-3\Delta} > f_{r}$ tailored to Goldfish. This is used because in Goldfish, validators corrupted after voting round r can still retroactively broadcast votes for that round, and these votes are relevant until 3$\Delta$ rounds later Use $H_{t},A_{t}$ to refer to active and adversarial validators at round $3\Delta t+\Delta$ $H_{s,t}$ = set of validators active at some point in slots \[s,t] **We require that the following condition, *$\tau$-sleepiness at slot t*, holds for any slot t:** $|H_{t-1}| > |A_{t} \cup (H_{t-\tau,t-2} \setminus H_{t-1})|$ Number of active validators at slot t-1 must exceed the number of adversarial validators together with all the other validators that have been active at some point in \[t-$\tau$, t-2] and that are not active in slot t-1 Tailored to a protocol implementing vote expiry (where $\eta=\tau$) because the votes which are considered at slot t are those from slots \[t-$\tau$, t-1]. Out of these, the only honest votes which we can rely on are those from $H_{t-1}$, whereas unexpired votes from honest validators that were not active in t-1 might help the adversary. When $\tau$=1, we get the sleepy model from Goldfish An execution is **$\tau$-compliant** if it satisfies $\tau$-sleepiness. $E_{\tau}$ is the set of such protocol executions $\tau$-sleepy model restricts the allowable set of executions to $\tau$-compliant executions, constraining the adversarial sleepiness and corruption power accordingly **Hierarchy of $\tau$-sleepy models** As $\tau$ increases, so do the restrictions that $\tau$-sleepy models put on the adversary Increasing $\tau$ makes it harder for $\tau$-sleepiness to be satisfied, as it constrains the adversarial corruption and sleepiness power more For $\tau=\infty$, all honest validators not active at round $3\Delta(t-1) + \Delta$ and which have voted at least once in the past are counted together with the adversarial ones. Requires honest validators to be greater than n/2 for all slots #### ($\tau,\pi$)-sleepy model Introducing the notion of a *temporary period of asynchrony of less than $\pi$ slots*, abbreviated by $\pi$-tpa **Definition (Temporary period of asynchrony):** We say that an interval ($t_{1},t_{2}$) of consecutive slots is a *temporary period of asynchrony*, tpa, if synchrony does not hold in the interval. If $t_{2}-t_{1} \leq \pi$, we refer to it as $\pi$-tpa We consider a system where synchrony holds except for one such $\pi$-tpa We refer to this network model as a *synchronous network with a temporary period of asynchrony* ta. Since a 1-tpa is empty, this is a generalization of the usual synchronous network model **Definition (($\tau,\pi$)-compliant execution):** For $\tau>\pi$ or both equal infinity, an execution in the synchronous network model with tpa is ($\tau,\pi$)-compliant if the tpa is in particular a $\pi$-tpa ($t_{1},t_{2}$) and the following conditions hold: - $\tau$-sleepiness at slot t holds for t's not in ($t_{1},t_{2}$] - $|H_{t_{1}} \setminus A_{t}| > |A_{t} \cup (H_{t-\tau,t-1} \setminus H_{t_{1}})|$ for t in ($t_{1},t_{2}+1$] - $H_{t_{1}}$ are awake at round $3\Delta t_{1}+2\Delta$ Call the set of ($\tau,\pi$)-compliant executions $E_{\tau,\pi}$ During $\pi$-tpa, the network is asynchronous and all honest validators can be asleep On the other hand, there are more restrictions on the adversary corruption schedule - it cannot corrupt too many validators in $H_{t_{1}}$, because we rely on that set to preserve the canonical chain throughout this period. This is why we have the third condition, as it guarantees that validators $H_{t_{1}}$ are able to observe votes cast at round $3\Delta t_{1}+\Delta$ which inform any votes they might cast during the period of asynchrony Not too many honest validators can be woken up during this period since waking up during asynchrony allows the adversary to manipulate their votes. ![[Pasted image 20230802105857.png]] Given a $\pi$-tpa $(t_{1},t_{2})$, we say that a validator $v_{i}$ in $H_{t_{1}}$ is **aware at round r** for r in slots $(t_{1},t_{2}]$ if $v_{i}$ is active at round r. For r not in those slots, we say that $v_{i}$ is aware at round r if it as active at round r. ### Security Consider $\lambda, \kappa$ to be the security parameter associated with the cryptographic components of the protocol and the security parameter of the protocol itself. Validators keep track of a *confirmed chain*, which is the output of the protocol according to a confirmation rule. Refer to the confirmed chain of validator $v_{i}$ at round r as $Ch_{i}^r$ ($ch_{i}^r$ for the canonical chain) **Definition 4 (Secure protocol):** We say a protocol outputting a confirmed chain Ch is secure and has confirmation time T_conf if Ch satisfies: Safety: For any two rounds r,r', and any two honest validators $v_{i},v_{j}$ at rounds r and r', either $Ch_{i}^r \leq Ch_{j}^{r'}$ or $Ch_{j}^{r'} \leq Ch_{i}^{r}$ Liveness: For any rounds r and r' >= r + Tconf, and any honest validator $v_{i}$ active at round r', $Ch_{i}^{r'}$ contains a block proposed by an honest validator at round > r A protocol satisfies τ-safety and τ-liveness if it satisfies safety and liveness, respectively, in the τ-sleepy model, i.e., in τ-compliant executions Eτ . If $\tau_{1} > \tau_{2}$, then $\tau_{1}$-sleepy model is weaker than 2 because of weaker assumptions **Definition 5 (Dynamic Availability):** $\tau$-dynamically-available iff it satisfies $\tau$-security **Definition 6 (Reorg Resilience):** An execution satisfies [[reorg resilient]] if any honest proposal B from a slot t is always in the canonical chain of all active validators at rounds >= $3\Delta t+\Delta$. A protocol is *$\tau$-reorg-resilient if all $\tau$-compliant executions satisfy reorg resilience* **Definition 7 (Asynchrony Resilience):** An execution in the synchronous network model with tpa ($t_{1},t_{2}$) satisfies asynchrony resilience if any honest proposal for a slot t <= $t_{1}$ is always in the canonical chain of all *aware* validators at rounds >= $3\Delta t+\Delta$. A protocol is ($\tau,\pi$)-asynchrony-resilient if all ($\tau,\pi$)-compliant executions satisfy asynchrony resilience Reorg resilience of proposals made before the tpa in the views of aware validators ## [[Propose-vote-merge]] protocols A fork-choice function uniquely identifies a protocol of this family See above notes for more ### View-merge Merge phase, along with all other ops involving views and buffers, are implementing the view-merge technique Ensures [[reorg resilience]] Works as follows: 1. Validator's buffer is merged into its view only at one specific time, i.e. $\Delta$ rounds preceding the start of a new slot. Therefore, no new messages enter its view before voting in the next slot 2. The one exception to the above is the proposer of the next slot, which merges the buffer right before propovsing, $\Delta$ rounds after all other validators. It then proposes its resulting view $V_{p}$ and a block extending the canonical chain as determined by FC, according to $V_{p}$ 3. Validators merge the proposed view into their local view, execute FC based on this merged view, and vote Observe that if network delay is less than $\Delta$ rounds, the view of the proposer is a superset of the views of other validators. Then, the final merged view of all validators before voting is equal to the view of the proposer. Since output of fork choice is a function of the view of a validator, every honest validator will have the same fork choice output, agreeing with the proposed block *view-merge property:* active validators vote for honest proposals under synchrony **Lemma 1:** Suppose that t is a pivot slot. THEN, all honest voters of slot t vote for the honest proposal B of slot t. ### Joining Protocol When a validator wakes up at round round between ($3\Delta(t-1)+2\Delta$, $3\Delta t+2\Delta$), it receives all the messages that were sent while it was asleep and add them to its buffer without participating in the protocol yet. The validator then waits for the next view-merge opportunity, at $3\Delta t+2\Delta$, to merge its buffer into its view. At this point, it starts executing the protocol ### Confirmation Rule In propose-vote-merge protocols, the confirmed chain Ch is the $\kappa$-deep prefix in terms of slots of the canonical chain, i.e. its prefix corresponding to blocks proposed at slots <= t - $\kappa$, which we denote $ch^\kappa$. A validator updates its confirmed chain whenever it updates its canonical chain by computing the fork choice (at round $3\Delta t+\Delta$), and possibly also $3\Delta t$ if they are the proposer to slot t. With overwhelming probability, all intervals \[t-$\kappa$,t) of $\kappa$ consecutive slots contain a pivot slot - a slot with an honest proposer that is active at proposal time In any slot there is at least a probability $\frac{h_{0}}{n}$ of an honest proposal being made **Lemma 2:** With overwhelming probability, all slot intervals of length $\kappa$ contain at least a pivot slot ### Properties Properties that propose-vote-merge protocols with a generic fork choice function satisfy **Proposition 1:** Suppose that all honest voters of slot t-1 vote for a descendant of block B. Then, B is in the canonical chain of all active validators in rounds {$3\Delta t,3\Delta t+\Delta$}. In particular, all honest voters of slot t vote for descendants of B. **Theorem 1 (Reorg Resilience):** Let us consider an execution of a propose-vote-merge protocol in which Proposition 1 holds. Then, this execution satisfies reorg resilience **Theorem 2 (Dynamic Availability):** An execution of a propose-vote-merge protocol satisfying reorg resilience also satisfies security with overwhelming probability with $T_{conf}=2\kappa$ slots. In particular $\tau$-reorg-resilience implies $\tau$-dynamic-availability ## Propose-vote-merge protocols based on GHOST #### GHOST fork-choice function based on a greedy algorithm that grows a blockchain on sub-branches with the most activity. Vote-based rather than block-based. Given a set of votes M, we define the weight function w(B,M) to output the number of votes in M for B or descendants of B. The following property will be used whenever wanting to prove that a block is in the canonical chain in some view. **Lemma 3:** Let V be a view in which over a majority of the votes are for a descendant of a block B. Then, GHOST (V,t) is a descendant of B, i.e. B is in the canonical chain output by the GHOST fork-choice #### Filtered GHOST Family of GHOST-based fork-choice functions defined as $G_{f}$. They are characterized by a view filter FIL, which takes as input a view B and a slot t and outputs ($V',t$), where V' is another view such that $V' \subset V$. Then, FC(V,t) = GHOST(FIL(V,t)) All fork choice functions considered from now on implement *equivocation discounting* to reduce spam and deal with equivocations. Excludes votes from equivocating validators from one's view before running fork-choice function. Done using view filters and checks for validators for which V contains multiple, equivocating votes for some slot t. #### LMD-GHOST GHOST but only considering the validator's most recent vote, assumed to be the most meaningful. $FIL_{lmd}$ removes all but the latest votes of every validator from V and outputs the resulting view - implementing latest message rule ![[Pasted image 20230803090423.png]] ### LMD-GHOST with view-merge and no subsampling With no subsampling we are able to prevent [[Ex-ante reorgs]] $\tilde{H}_{t}$ = the set of honest voters of slot t that are never corrupted. *Permanently honest* In the following theorem we analyze reorg resilience of LMD-GHOST. In particular, given $|\tilde{H}_{t}| > \frac{n}{2}$ and an honest proposal B from a slot t, then B is always canonical in all honest views that contain all slot t votes from $\tilde{H}_{t}$ without requiring synchrony at any future slot. In other words, honest proposals made during synchrony immediately become asynchronously safe. Much stronger than the usual notion of reorg resilience, which requires continued synchrony **Theorem 3 (Strong Reorg Resilience):** Consider an honest proposal B from a slot t in which network synchrony hold and $|\tilde{H}_{t}| > \frac{n}{2}$. Suppose that validators in $\tilde{H}_{t}$ do not fall asleep in rounds \[$3\Delta t + \Delta, 3\Delta t + 2\Delta$]. THEN B is always canonical in all honest views which contain all slot t votes from $\tilde{H}_{t}$ Proof: By Lemma 1, all honest voters of slot t broadcast a vote for B at round $3\Delta t+\Delta$. Synchrony in the subsequent $\Delta$ rounds means that all such votes are received by those same validators before they merge their buffers, since by assumption they do not fall asleep. Those votes are then in all of their views by the end of slot t and the result follows. On the other hand, LMD-GHOST is significantly limited in its support of dynamic participation, as shown in the following theorem. It presents a scenario in which the adversary is able to cause a reorg of a confirmed block, compromising t-safety and thus t-dynamic-availability while never violating t-sleepiness. Possible because t-sleepiness only considers votes from the last $\tau$ slots, but LMD-GHOST does not have vote expiry, so all votes are relevant to the fork-choice. Since $\infty$-sleepy model only allows a restrictive form of dynamic participation, almost requiring $|\tilde{H}_{t}| > \frac{n}{2}$ at all times. **Theorem 4:** LMD-GHOST is not $\tau$-dynamically-available for any finite $\tau$ and any confirmation rule with finite confirmation time $T_{conf}$ ### Goldfish Simplified variant of LMD-GHOST, very nearly belongs to propose-vote-merge family Tolerates dynamic participation, subsampling of validators, and is 1-reorg-resilient and 1-dynamically0available in synchronous networks with dynamic participation. Only votes from previous slot influence protocol's behavior. In following analysis, consider a version of Goldfish that fulfills propose-vote-merge specification. Doesn't use subsampling and replaces VRF lottery considered in original protocol with SSLE proposer selection mechanism. Characterized by GHOST-EPH, $G_{f}$ fork choice function that takes a view V and a slot t as inputs and finds the canonical chain determined by the votes within V that were broadcast for slot t-1. #### Vote Expiry All but the most recent votes are discarded. Generalized by introducing an expiration period $\eta$. In particular, given a slot t and a constant $\eta \in N$ with $\eta \geq 0$, the expiration period for a slot t is the interval \[t-$\eta$,t) and only votes broadcast within this period influence the protocol's behavior at slot t. GHOST fork-choice function with expiry period $\eta$ is a fork choice function in $G_{f}$ characterized by the filter function $FIL_{\eta_-\exp}(V,t)$ which removes all votes from slots < t- $\eta$ from V and outputs the resulting view. For n = $\infty$, we get back the regular GHOST fork-choice function, whereas for $\eta=1$ we get GHOST-EPH. ![[Pasted image 20230803094152.png]] #### Properties and limitations Goldfish is 1-reorg-resilient and 1-dynamically-available Brittle to temporary asynchrony, as even a single violation of the bound of $\Delta$ rounds on the network delay can lead to a catastrophic failure. All honest votes will not be delivered, and the votes will not be in any honest view after merging buffer. If there's a malicious proposer that proposes extending a block that's not in the canonical chain then the view of an honest validator will only have two votes: its own and the malicious. If A wins the tiebraker, all honest validators vote for it making it canonical and reorging lal previously confirmed blocks. **Theorem 5:** Goldfish is not $(\tau,\pi)$-asynchrony-resilient for any $\tau>\pi\geq 2$ ## Recent Latest Message Driven (RLMD) GHOST Generalizes LMD-GHOST with view-merge and no subsampling and Goldfish with no subsampling RLMD's filter function $FIL_{rlmd}(V,t)$ removes all but the latest message within the expiry period \[t-$\eta$,t) for slot t, FILrlmd = FILlmd ◦ FILη-exp ◦ FILeq. ### Tradeoff between dynamic availability and resilience to asynchrony Expiry parameter $\eta$ allows exploration of this tradeoff space $\eta$-dynamic availability and ($\eta,\eta-1$)-asynchrony-resilience (it can tolerate < $\eta$-1 slots of asynchrony but it is only secure with the stronger assumptions of the $\eta$-sleepy model) Even temporary violations of $\eta$-sleepiness assumptions (temporary adversarial majority) can be tolerated. The longer expiry period prevents the set of honest validators whose votes are unexpired, and thus relevant to FC, from suddently shrinking or disappearing altogether. On the other hand, taking into account votes of validators which might be asleep weakens dynamic availability, motivating why the $\eta$-sleepiness assumption is required. ### Properties **Lemma 4:** Proposition 1 holds for RLMD-GHOST in $\eta$-compliant executions RLMD-GHOST is $\eta$-reorg resistant, $\eta$-dynamically-available, and ($\eta$,$\eta$-1)-asynchrony-resilient By the hierarchy of sleepy models, these results also satisfied for $\tau\geq \eta$ ## Related Works Longest chain protocols are resilient to temp asynch and dynamically available, but not reorg resilient. Only two other types of dynamically available protocols have been designed so far: Goldfish [[Momose-Ren]] and [[Malkhi, Momose, Ren]] MR is a quorum-based atomic broadcast protocol in the sleepy model that supports dynamic participation and constant latency Requires stable participation for liveness Extends BFT to dynamic quorum size, according to the current participation level, using a graded agreement protocol MMR presents a synchronous protocol that is live under fully fluctuating participation Byzantine atomic broadcast protocol in the sleepy model with 3 round latency, but only tolerates 1/3 Byzantine nodes rather than 1/2. Has recently improved to achieve the 1/2 corruption threshold ## Conclusion and Future Work Reserve for future research the development of a secure ebb-and-flow protocol that incorporates RLMD-GHOST as a dynamically available component, along with a partially synchronous finality component **Open question whether the techniques of this work can be applied to the family of quorum-based dynamically available protocols to strengthen their resilience of asynchrony at the cost of weakened tolerance to dynamic participation** ## Limitations of RLMD-GHOST Not $\tau$-reorg-resilient for any $1\leq \tau<\eta$ Nor dynamically available ## Fast confirmations Requires small modification to the generic propose-vote-merge protocol, changing the vote behavior so that validators vote as soon as they see a proposal or at $3\Delta t+\Delta$, whichever comes first. This is the attestation behavior already specified by Ethereum consensus protocol ### Protocol with fast confirmation As opposed to Algorithm 1, we update the confirmed chain explicitly **PROPOSE:** Unchanged from section 3.2 (propopser merges its view with its buffer, runs fork choice to get head of chain, extends this wit ha new block and updates its canonical chain, broadcasts result) **VOTE:** In rounds \[$3\Delta t,3\Delta t+\Delta$], a validator $v_{i}$, upon receiving the proposal message, merges its view with the proposed view. After this, or at round $3\Delta t+\Delta$ if no proposal is received, it updates its canonical chain by setting $ch_{i} <- FC(V_{i},t)$ and braodcasts the vote message \[VOTE, FC($V_{i},t$), t, vi] **CONFIRM:** At round $3\Delta+\Delta$, validator merges its view with tis buffer It selects for fast confirmation the highest canonical block $B_{fast} < ch_{i}$ such that the buffer contains $\geq \frac{2n}{3}$ votes from slot t for descendants of $B_{fast}$ Then updates its confirmed chain $Ch_{i}$ to the highest of $B_{fast}, ch_{i}^k$ (k-deep prefix of canonical chain) as long as this does not result in updating $Ch_{i}$ to a prefix of itself **MERGE:** At round $3\Delta t+2\Delta,$ every validator $v_{i}$ merges its view with its buffer and sets the buffer to the empty set ### Safety and liveness tradeoff Fast confirmations protocol is safe when both fast confirmations and standard (k-deep) confirmations are safe, and live whenever at least one is live. Safety resilience can be worse than n/2, which is what the original protocol tolerates when all honest validators are awake, since $\eta$-sleepiness reduces to $|H_{t-1}| > |A_{t}|$ Previously section saw fast confirmations require a quorum of 2/3 \* n, which results in both liveness and safety resilience of fast confirmations of n/3. Safety resilience is reduced to n/3 as well Done so that RLMD-GHOST can be used in combination with a finality gadget to preserve dynamic availability. Violating the safety of a fast confirmation with quorum 2n/3 requires n/3 equivocations, thus making n/3 validators slashable Thus, the security guarantee of the resulting protocol under network synchrony is that a safety violation requires either safety of standard confirmations to be violated, implying a violation of $\eta$-sleepiness, and in particular $f\geq \frac{n}{2}$ if all honest validators are awake, or n/3 adversarial validators have to be slashable for equivocation ### Properties Fast confirmations are live when there are at least 2n/3 honest validators awake and the real network latency is $\leq \frac{\Delta}{2}$. **Lemma 5**. Suppose network synchrony holds for rounds \[3∆t + ∆, 3∆t + 2∆], and that an honest validator fast confirms block B at slot t. Suppose also that, in the view of any active validator at slot t + 1, < n 3 validators are seen as equivocators. Then, all honest voters of slot t + 1 vote for descendants of B. **Theorem 12 (Reorg resilience of fast confirmations)**. Consider an η-compliant execution of RLMD-GHOST. A block fast confirmed by an honest validator at a slot t is always in the canonical chain of all active validators at rounds ≥ 3∆(t + 1) + ∆. **Theorem 14 (Liveness of fast confirmations)**. An honest proposal B from a slot t in which |Ht| ≥ 2n/3 and network latency is ≤ ∆ 2 is fast confirmed by all active validators at round 3∆t + ∆ ## Finality in LMD-GHOST Special case of a confirmation rule, in particular one which is asynchronously safe, unlike the k-deep rule A **Certificate with Quorum Q** is the basis for a notion of finality in LMD-GHOST. Gasper chose to pair it with Casper FFG as a finality gadhet **Definition 8 (Certificate)** Given a slot t, we define an *m-quorum certificate* for slot t for a block B as a set Q of at least m votes broadcast in t, all (votes) for some descendant B, and all from distinct validators To create a notion of finality with a quorum Q of at least m votes, we require blocks to be allowed to contain votes, so that a vote for a block is also an acknowledgment of the votes it contains. The honest proposer behavior is to include all possible votes from the previous slot **Definition 9 (Finality):** A block B is m-finalized, with m > n/2, if for some slot t there exist: 1. An m-quorum certificate Q for slot t 2. a block A from slot t+1 containing Q 3. an m-quorum certificate Q' for slot t+1 for A from the same set of validators that Q is from (called an m-clique) If these conditions hold we say B is finalized at slot t+1. **QUESTION:** Has the design space of RLMD + certificates been explored? What are the problems or outstanding questions preventing RLMD-GHOST from being implemented?