# ePBS-compliant Fast Confirmation Rule for RLMD $$ \newcommand{\betan}{\beta_\mathsf{n}} \newcommand{\newfconf}[1]{{\mathsf{nfconf}(#1)}} \newcommand{\fconf}[1]{{\mathsf{fconf}(#1)}} \newcommand{\vote}[1]{{\mathsf{vote}(#1)}} \newcommand{\rinclude}{{r_\mathsf{include}}} $$ Let us import any notation already defined in the [3SF paper v1 on arxiv](http://arxiv.org/abs/2411.00558v1). ## 1. GAT-reliant Fast Confirmation Rule with Adversary ratio $<\frac{1}{3}$ > **Objective 1** > Design a Fast Confirmation Rule parametrized by the ratio $\betan$ of total (both awake and asleep) adversary nodes vs the total number of nodes (both awake and asleep) > **Assumptions** > 1. RLMD > 2. Synchrony > 2. Every node has the same weight > 3. $f < \betan n$ > **Additional Notation** > - $S_{r}^{v,B}$: senders or RLMD votes for $\succeq B$ that are received by validator $v$ at time $r$ and that are not expired at the vote time in the next slot, i.e., at time $vote(t+1)$. > - $E_{r}^v$: validators that have equivocated according to the view of validator $v$ at time $r$. > **Result** > If > 1. we assume $\betan < 20\%$ > 2. We set the threshold used by the builder to decide whether to reveal or not to 60% > 3. The builder decides before $\fconf{t}$ > 3. We set the threshold used to decide whether the proposer needs to paid when no payload has been revealed to 80% > > then, the following properties are satisfied > > 1. Proposer Safety > 2. Builder Reveal Safety (assuming that the PTC sees the payload in time and all attesters agree with the PTC) > 3. Builder Withhold Safety > **Disclaimer** > As hinted above, in this work, we do not take the PTC into account. Essentially, assume that if an honest builder reveals, then the PTC sees they payload and all attesters in the next slot agree with the PTC. Future work will need to also consider the possible adverse effect of the PTC check. ### Safety Given the properties of RLMD, to confirm a block $B$ in slot $t$, we need to identify a condition that ensures that all honest validator in $H_\vote{t+1}$ vote for $\succeq B$. Let $v'$ be any (honest) validator in $H_\vote{t+1}$. The weight in support of $\succeq B$ is $|S_\vote{t+1}^{v',B} \setminus E_\vote{t+1}^{v'}|$. The maximum weight in support of any conflicting block is correspond to the total number of nodes, minus the equivocating nodes, minus the non-equivocating nodes that have cast a vote in support of $\succeq B$, that is, $n - |E_\vote{t+1}^{v'}| - |S_\vote{t+1}^{v',B} \setminus E_\vote{t+1}^{v'}|$. If $|S_\vote{t+1}^{v',B} \setminus E_\vote{t+1}^{v'}| > n - |E_\vote{t+1}^{v'}| - |S_\vote{t+1}^{v',B} \setminus E_\vote{t+1}^{v'}|$, then $v'$ votes for $\succeq B$ in slot $t+1$. By adding $|S_\vote{t+1}^{v',B} \setminus E_\vote{t+1}^{v'}|$ to both sides, we get the following condition: $$\frac{|S_\vote{t+1}^{v',B} \setminus E_\vote{t+1}^{v'}|}{n - |E_\vote{t+1}^{v'}|} > \frac{1}{2}$$ Let $\newfconf{t} \leq \fconf{t}$ be the time when this "new" fast confirmation rule is evaluated. Note that $\frac{|S_\vote{t+1}^{v',B} \setminus E_\vote{t+1}^{v'}|}{n - |E_\vote{t+1}^{v'}|} \geq \frac{|S_\newfconf{t}^{v,B}| - |E_\vote{t+1}^{v'}|}{n - |E_\vote{t+1}^{v'}|}$ as 1. $S_{\newfconf{t}}^{v,B} \subseteq S_{\vote{t+1}}^{v',B}$ due to the synchrony assumption 2. $|S_\newfconf{t}^{v,B} \setminus E_\vote{t+1}^{v'}| \geq |S_\newfconf{t}^{v,B}| - |E_\vote{t+1}^{v'}|$ Then, let us know work out under which conditions $\frac{|S_\newfconf{t}^{v,B}| - |E_\vote{t+1}^{v'}|}{n - |E_\vote{t+1}^{v'}|} \geq \frac{1}{2}$. Given that (1) $|S_\newfconf{t}^{v,B}| \leq n$, only the adversary can equivocate, and $|E_\vote{t+1}^{v'}| < \betan n$, we have $\frac{|S_\newfconf{t}^{v,B}| - |E_\vote{t+1}^{v'}|}{n - |E_\vote{t+1}^{v'}|} \geq \frac{|S_\newfconf{t}^{v,B}| - \betan n}{n - \betan n}$ Then, $\frac{|S_\newfconf{t}^{v,B}| - \betan n}{n - \betan n} > \frac{1}{2}$ is implied by $$ \frac{|S_\newfconf{t}^{v,B}|}{n} \geq \frac{1+\betan}{2} $$ > **Note** > 1. If $\betan = \frac{1}{3}$, then $\frac{1+\betan}{2} = \frac{2}{3}$ which corresponds to the rule used in both the 3SF and "Simple SSF" paper under the same assumption ### ePBS Compatibility > **Notation** > $R^T$ is the builder release threshold. That is, if the builder sees $\frac{|S_\newfconf{t}^{v,B}|}{n} \geq R^T$, then it releases the payload. Otherwise, it doesn't. > $P^T$ is the proposer payment threshold in the case that the payload is not revealed. That is, assume that the payload is not present. If at some time $\rinclude$ $\frac{|S_\rinclude^{v,B}|}{n} \geq P^T$, then the proposer is paid by the builder. Otherwise, the proposer is not paid. > **Additional Assumptions** > 3. After GAT > **Properties to ensure:** > 1. **Proposer safety.** If the proposer is honest, then the proposer gets paid. > 2. **Builder reveal safety (assuming that the PTC sees the payload in time and all attesters agree with the PTC).** If the builder decides to reveal, then the block that includes the commitment to the builder's payload is not going to be reorged out. > 3. **Builder withhold safety.** If the builder decides to withhold, then the builder is not penalized. #### Proposer Safety Given that we are after GAT, we have that $\frac{|S_\newfconf{t}^{v,B}|}{n} \geq 1-\betan$. Therefore > **Constraint 1**: > $P^T \leq 1 - \betan$ #### Builder Reveal Safety This is given by using the confirmation rule defined above: > **Constraint 2**: > $R^T \geq \frac{1+\betan}{2}$ #### Builder Withhold Safety Here we need to ensure that if the builder rightfully decides not to reveal, then the payment threshold is never met. Worst that can happen from this perspective for the builder is that all adversary nodes vote in support of the block carrying a commitment for the payload they decided to withhold. This means that if $\frac{|S_\newfconf{t}^{v,B}|}{n} < R^T$, then $\frac{|S_\newfconf{t}^{v,B}| + \betan n}{n} < P^T$ Simplifying: > **Constraint 3**: > $R^T + \betan \leq P^T$ as 1. $\frac{|S_\newfconf{t}^{v,B}| + \betan n}{n} = \frac{|S_\newfconf{t}^{v,B}|}{n} + \betan$ 2. $\frac{|S_\newfconf{t}^{v,B}|}{n} + \betan < R^T + \betan$ #### Putting all together For Constraint 1 & 3, we get $R^T \leq 1 - 2\betan$ From Constraint 2, then we get $\frac{1+\betan}{2} \leq 1 - 2\betan$ By solving for $\betan$, we get $\beta \leq \frac{1}{5}$