Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance

The COOL protocol of [13] is tailored for Byzantine agreement, and its core was later adopted for reliable broadcast [6] and gradecast by [30]. We show that this core of COOL is essentially a new variant of dispersal (a part of a Verifiable Information Dispersal protocol [12]). We call this new variant graded dispersal. We note that dispersal typically needs a designated sender; in our abstraction, we assume the parties have already received the message from some “virtual sender” and wish to verify that they have enough information to retrieve and agree on it later. Defining this graded dispersal variant allows us to distill the novelty of COOL’s protocol consistency check and build applications that are based on COOL in a more modular fashion.

The analysis in [13] is rather involved and relies on various tools; citing [13] “the proof borrows tools from coding theory, together with graph theory and linear algebra”. As mentioned above, this also makes the result hard to verify. We provide a new analysis of our graded dispersal protocol. Notably, our analysis is significantly more concise, much shorter than the original COOL analysis, and uses only simple counting. Given the centrality of the result and its simple analysis, we believe that this protocol will be a good candidate for being part of a curriculum in distributed computing classes as a prime example of the centrality of polynomials in obtaining efficient perfect security.

We show how to apply graded dispersal to achieve the following (1) gradecast (synchrony); (2) multi-valued Byzantine agreement; (3) broadcast; and (4) reliable broadcast (asynchrony).

Gradecast introduced by Feldman and Micali [17] (“graded-broadcast”) is a fundamental primitive used for various consensus algorithms.

Bracha’s Reliable Broadcast [11] is a useful building block in asynchronous protocols. The recent paper of Das, Xiang, and Ren [15] has a detailed survey of the usefulness of communication-efficient Reliable Broadcast. In particular, it implies Asynchronous Verifiable Secret Sharing and Asynchronous Distributed Key Generation [4].

Our new protocol reaches agreement faster than the COOL protocol. Specifically, while COOL requires three rounds of reporting agreements to one another (see more in-depth in Section 2), we show that two rounds suffice. This improvement becomes particularly significant when utilizing the COOL technique in constant round protocols such as reliable broadcast and gradecast - and improves the state-of-the-art for those primitives.

Our new protocol improves the communication complexity by 40%. Specifically, the protocol of COOL divides the messages into blocks of polynomials of degree $d=t/5$. Our protocol works when dividing the messages into blocks of degree $d=t/3$. Changing the degree enhances the state-of-the-art in all our applications – multi-valued byzantine agreement, broadcast, gradecast, and reliable broadcast.

We consolidate the costs of gradecast and reliable broadcast in Table 1.

The protocol of COOL divides the value $v_i$ of size $L$ into blocks, where each block is a polynomial of degree-$d$ over a finite field $𝔽$. For simplicity of exposition, assume that $L=(d+1)\log |𝔽|$ (i.e., we have a single block – one polynomial).

Two parties $P_i$ and $P_j$ that wish to check whether their polynomials $f_i(x),f_j(x)$ are identical can do so efficiently using randomization and with a statistical error based on the Schwartz-Zippel lemma [29, 31]. Each pair evaluates its respective polynomials on a random point $r\in 𝔽$ and verify that $f_i(r)=f_j(r)$. This approach was taken in [1] for gradecast and reliable broadcast. The novelty of COOL protocol is that it achieves a similar effect of equality check of polynomials, deterministically, and error free. Each pair of parties exchange just $O(1)$ points, as in the statistical case. Specifically, $P_i$ sends to $P_j$ the points $f_i(i)$ and $f_i(j)$ only, and $P_j$ verifies that those two points agree with its polynomial $f_j(x)$. If a party agrees with $n-t$ parties - then the party is happy. The protocol proceeds in a few rounds, during which each party reports to others whether it is happy. A party remains happy if at least $n-t$ parties in its agreement set report they are happy. Interestingly, the proof of COOL shows that after three rounds of repeating this process, all parties that report that they are happy must hold the same polynomial.

We formalize a variant of dispersal, which, as mentioned, distills the consistency property achieved by COOL. We require the following properties from a graded dispersal protocol. Each party holds some polynomial $f_i(x)$ as input (of degree-$d$). The parties output $(f_i^{\prime }(x),g_i)$ where $f_i^{\prime }(x)$ is a polynomial of degree-$d$ (might be $\perp$), and $g_i$ is a grade in $\{0,1,2\}$. The guarantees are: (1) Validity: If all honest parties start with the same polynomial $f(x)$, then they all must output $(f(x),2)$; (2) Graded agreement: If some honest party outputs $(f(x),2)$ then at least $t+1$ honest party output $f(x)$ with a grade at least $1$, and all other honest parties output $(\perp ,0)$. Note that we have no guarantee in the case where no honest party outputs grade 2, i.e., in that case, different honest parties might have different polynomials as output (with grade 1). Furthermore, our formalization of graded dispersal allows two honest parties to output grades of $2$ and $0$, respectively. This is different from the typical definition of graded primitives (such as gradecast), where if an honest party outputs grade $2$, then all honest parties output a grade at least $1$. However, looking ahead, we show that this weak formalization of graded dispersal suffices for all the applications we consider, including reaching a full byzantine agreement.

We implement graded-dispersal based on the COOL protocol. The crux of our contribution is in providing a simple proof for this construction. Moreover, we show we can achieve it in one round of reporting happiness less than COOL. Specifically, we show that:

1. 1.

   Initially, only two sets of parties, $A$ and $B$, holding polynomials $f_A(x)$ and $f_B(x)$, respectively, can report that they are happy after the initial pairwise checks. Since two polynomials might agree on only $d$ common points, three parties holding distinct polynomials cannot have enough agreements and cannot all be happy. See Claim 3.4.

2. 2.

   We show that if there is one set of parties $A$, all holding the same polynomial $f_A(x)$ and $|A|\ge t+1$, then only parties from $A$ can output grade at least $1$, and all other parties output $(\perp ,0)$. Intuitively, if another set of parties $B$ with $|B|\le t$ holds polynomial $f_B(x)$, then those parties cannot remain happy due to inconsistencies with the larger set $A$. See Claim 3.5. Importantly, a party outputs grade 2 if it is happy and it received at least $2t+1$ reports from its agreement set in the last round. This implies that it received at least $t+1$ reports from honest parties. In that case, a party can output grade $2$, and the other happy parties must also hold $f_A(x)$, and we have at least $t+1$ parties with the same (and only) output polynomial, $f_A(x)$.

3. 3.

   If no large set exists, no party outputs grade 2 (no party is happy and received $2t+1$ reports of happiness from its agreed set in the last round). See Claim 3.6.

Our graded dispersal works in three rounds and requires $O(nL+n^2\log n)$ for inputs of size $L$.

In Section 3.2, we show a protocol that allows parties to reconstruct the output $f(x)$ once there are at least $t+1$ honest parties that hold the same input $f(x)$ (and other honest parties hold $\perp$). Essentially, this is precisely the guarantee we have once one party outputs 2 in the graded dispersal protocol. Simply, each party that has an input $f(x)$ sends to each party $P_i$ its point $f(i)$. $P_i$ then takes as its point the majority value that it received, and since $t+1$ honest parties that hold $f(x)$ and there are at most $t$ corrupted parties, we are guaranteed that the majority of $P_i$ is $f(i)$. Once each party $P_i$ has a point $f(i)$, the parties reconstruct $f$ by sending their points to one another and using Reed-Solomon decoding.
Given graded dispersal and data dissemination, we provide three applications in synchrony.

Gradecast is a relaxation of broadcast and involves a sender that holds a message $M$, and all parties output $(M_i,g_i)$ with $g_i\in \{0,1,2\}$. If the sender is honest, all parties must output $(M,2)$. The guarantee is that if one honest party outputs $(M,2)$, all honest parties must output $(M,g_i)$ with $g_i\ge 1$. We remark that the definition that we provide is a relaxation of Gradecast that was formalized by Katz and Koo [21], which allows the parties to output different messages when there is no honest party with grade $2$ (just as in our graded dispersal). We are unaware of any application of gradecast in which the relaxed definition does not suffice.

We show how to implement gradecast using graded dispersal and data dissemination. Specifically, the sender sends its message to all parties, and the parties then run graded-dispersal. After that, they run data dissemination and output the message they received in the data dissemination with their grade in the graded dispersal. It is easy to see that the requirements for gradecast are met.

The last round of graded dispersal can be run parallel to the first round of data dissemination, so we can get a protocol that runs in a total of $5$ rounds. This results in an improvement of 3 rounds compared to the state-of-the-art [30]; yet, our guarantee is slightly weaker. We also show how to satisfy the [17] definition at the expense of adding one more round. We then get a strict improvement of 2 rounds with the same security definition (and reduce communication by 40%). The improvement of 2 rounds is due to some redundancy in the protocol of [30].

We emphasize that the “relaxed” gradecast suffice for all the applications we are aware of, specifically to achieve broadcast with an expected constant number of rounds (see Section 2.3). We therefore advocate using the relaxed version.

We compose graded-dispersal, with binary agreement (on whether a party has grade 2), and data dissemination to achieve multi-valued byzantine agreement. As mentioned, our protocol has one less round than the state-of-the-art and $40\%$ less communication. The protocol runs in $O(nL+n^2\log n)$ with $\mathrm{\Theta }(n)$ rounds (due to the binary agreement).

Again, by composing graded-dispersal, binary agreement, and data dissemination, we obtain a broadcast protocol that runs in $O(nL+n^2\log n)$ communication and $\mathrm{\Theta }(n)$ rounds.

For gradecast and broadcast, we also show a variant where the protocol is balanced: each party sends or receives $O(L+n\log n)$, and there is no party whose communication load is higher than the others. This comes at the expense of adding an extra round.

As mentioned, broadcast and byzantine agreement in that setting must incur $\mathrm{\Omega }(n)$ rounds [18]. The broadcast and byzantine agreement presented in our paper achieves $O(n)$ rounds in the worst case. Rabin [28] and Ben-Or [8] studied the effect of randomization on round complexity, and Feldman and Micali [17] gave the first protocol with an expected constant round protocol for byzantine agreement with optimal resilience. Many works have improved the communication complexity of expected constant round Byzantine agreement protocols with optimal resilience [20, 25, 2, 7] where the current state of the art is $O(nL+n^3{\log }^{2}n)$ with expected constant number of rounds. We remark that in all those protocols, the sender first gradecasts its message, and therefore using our improved gradecast (whose relaxed notion suffices for this application) improves the constant in the “expected constant” of these works.

Gradecast is an important primitive used for various consensus algorithms, e.g., multi-consensus, approximate agreement [9], or Phase-King [5]. Our round complexity is the most efficient in the perfect setting. However, the protocol of Abraham and Asharov [1] is one round better at the expense of introducing some error (i.e., statistical security).

In the computational setting, the protocol of Cachin and Tessaro [12] achieves $O(nL+\kappa n^2\log n)$ where $\kappa$ is the computational security parameter. This is improved by Alhaddad et al.[6] to $O(nL+n^2\kappa )$ with $4$ rounds of communication. The recent work by Locher and Shoup looks into the constants and obtains $1.5nL+O(\kappa n^2\log n)$.

We now show that all the properties hold as in Definition 3.1.

Assume that all honest parties have the same input $f(x)$. For each party $P_i$, the set ${𝖠}_i^1$ will contain the set of all honest parties and therefore $|{𝖠}_i^1|\ge n-t$ and $P_i$ sends ${\mathrm{𝖮𝖪}}_1$. Moreover, it will receive ${\mathrm{𝖮𝖪}}_1$ from all honest parties; therefore, $P_i$ also sends ${\mathrm{𝖮𝖪}}_2$. We get that all honest parties send ${\mathrm{𝖮𝖪}}_2$, and consequently, all receive at least $2t+1$ ${\mathrm{𝖮𝖪}}_2$, so all output $(f(x),2)$.

If one party outputs $(f(x),2)$, then there are at least $t+1$ honest parties that output $(f(x),g)$ with $g\ge 1$, and all the others output $(\perp ,0)$. This is done in 3 steps:

• $\mathrm{■}$

  Claim 3.4 proves that there cannot be three honest parties that hold different inputs, that all send ${\mathrm{𝖮𝖪}}_1$. Hence there exists at most two inputs $f_a,f_b$ such that each honest party that sends ${\mathrm{𝖮𝖪}}_1$ must hold one of these two inputs.

• $\mathrm{■}$

  Given this, Claim 3.5 proves that if there is a set of at least $t+1$ honest parties that all have the same input, then no honest party holding a different input will send ${\mathrm{𝖮𝖪}}_2$.

• $\mathrm{■}$

  Claim 3.6 shows that if there is no set with at least $t+1$ honest parties that have the same input, then no honest party outputs grade 2.

If an honest party outputs grade 2, then from Claim 3.6 we must be in the case where there are at least $t+1$ honest parties as in Claim 3.5 and from that all honest parties that send ${\mathrm{𝖮𝖪}}_2$ (hence output grade 1) must output the same value.

Proving Claims 3.4, 3.5, 3.6 concludes the proof of the Theorem.

Seeking a contradiction, assume there exist honest parties $P_a,P_b,P_c$ that hold distinct input polynomials $f_a,f_b$, and $f_c$, such that $P_a,P_b,P_c$ all send ${\mathrm{𝖮𝖪}}_1$ messages.

Let $H$ be the set of all honest parties and let $I=[n]\setminus H$ be the malicious parties.

For any $x\in \{a,b,c\}$ define $S_x$ as the set of all the honest parties that agree with $P_x$:

Observe that:

• $\mathrm{■}$

  For any $x\in \{a,b,c\},|S_x|\ge n-t-|I|$. Because if $P_x$ sent ${\mathrm{𝖮𝖪}}_1$, it must agree with at least $n-t$ parties, and thus with at least $n-t-|I|$ honest parties.

• $\mathrm{■}$

  For any $x,y\in \{a,b,c\},|S_x\cap S_y|\le d$. Because for any $j\in S_x\cap S_y$ then $f_x(j)=f_j(j)=f_y(j)$. So if $|S_x\cap S_y|\ge d+1$ then $f_x$ and $f_y$ agree on at least $d+1$ points, and therefore, must be identical.

So from inclusion-exclusion:

Since $d=\lfloor t/3\rfloor$ so $3d\le t$:

On the other hand, $(S_a\cup S_b\cup S_c)\subseteq H$, and therefore $|S_a\cup S_b\cup S_c|\le |H|=n-|I|$:

Using $n\ge 3t+1$ and $|I|\le t$:

which is a contradiction. $\mathrm{⊲}$

So let $T_a$ and $T_b$ be the at most two sets of honest parties with inputs $f_a$ and $f_b$ respectively such that only members in those sets send ${\mathrm{𝖮𝖪}}_1$. Since ${𝖠}_j^2\subseteq {𝖠}_j^1$ for each honest party $P_j$ then only parties in $T_a$ or $T_b$ may send ${\mathrm{𝖮𝖪}}_2$.

Assume wlog that $|T_a|\ge |T_b|$.

Define:

From Claim 3.4, honest parties not in $T_a\cup T_b$ do not send ${\mathrm{𝖮𝖪}}_1$.

Observe that parties in $T_{b-}$ do not send ${\mathrm{𝖮𝖪}}_1$. This is because $|T_a|\ge t+1$, all $j\in T_{b-}$ have $f_a(j)\ne f_b(j)$ by definition. Therefore, any $j\in T_{b-}$ cannot receive support from $T_a$ and thus

Given this, parties in in $T_{b+}$ do not send ${\mathrm{𝖮𝖪}}_2$. This is because the only honest parties that can send ${\mathrm{𝖮𝖪}}_1$ that will be accepted by $T_{b+}$ are from $T_{a+}\cup T_{b+}$, but $|T_{a+}\cup T_{b+}|\le d$ because otherwise $f_a=f_b$. So for any party $j\in T_{b+}$ must have

$\mathrm{⊲}$

Observe that the parties in $T_{a-}$ and $T_{b-}$ do not send ${\mathrm{𝖮𝖪}}_2$. This is because all parties not in $T_a,T_b$ do not send ${\mathrm{𝖮𝖪}}_1$, and for $x\in \{a,b\}$, a party in $T_{x^{-}}$ can receive ${\mathrm{𝖮𝖪}}_1$ only from $T_x$ and the corrupted parties. Thus,

Given this, only parties in $T_{a+},T_{b+}$ might send ${\mathrm{𝖮𝖪}}_2$. However, no party can receive $2t+1$ ${\mathrm{𝖮𝖪}}_2$ messages. This is because $|T_{a+}\cup T_{b+}|\le d$ so

$\mathrm{⊲}$

This concludes the proof of Theorem 3.3. $◀$

We are unaware of an application that actually requires this a property, where grade 2 implies that all parties output the same value with grade $>2$ (so graded agreement not just weak graded agreement as in Definition 3.1 ). Nevertheless, we comment here that can be obtained by one more round.

To achieve this, parties that receive $n-t$ ${\mathrm{𝖮𝖪}}_2$s send ${\mathrm{𝖮𝖪}}_3$, and then: (1) if $P_i$ sent ${\mathrm{𝖮𝖪}}_3$ and received $2t+1$ ${\mathrm{𝖮𝖪}}_3$ it outputs $(f(x),2)$; (2) otherwise, if it sent ${\mathrm{𝖮𝖪}}_3$ it outputs $(f(x),1)$; (3) otherwise, (it did not send ${\mathrm{𝖮𝖪}}_3$) it outputs $(\perp ,0)$.

If all parties start with the same input $f(x)$ then they all send and receive $n-t$ ${\mathrm{𝖮𝖪}}_3$s and all output $(f(x),2)$. In addition, if there is no set $|T_a|\ge t+1$, then all honest parties must output $(\perp ,0)$. In this case, Claim 3.6 shows that no party receives $2t+1$ ${\mathrm{𝖮𝖪}}_2$; therefore, no honest party sends ${\mathrm{𝖮𝖪}}_3$.

Assume that $t+1$ honest parties start with the same input $f(x)$. Each honest party $P_j$ receives $f(j)$ at least $t+1$ times. All other honest parties that hold $\perp$ send nothing in the first message. As such, the majority value of $P_j$ must be $f(j)$, and it sends it to all other parties in the second round. Therefore, all honest parties must receive $(y_1,\mathrm{\dots },y_n)$ that is of distance at most $t$ from $(f(1),\mathrm{\dots },f(n))$. Since $n>2t+d$, the Reed Solomon decoding guarantees that all output $f(x)$.

Protocol 3.8 as described above incurs a total communication of $O(n^2\log n)$ bits and this corresponds to the case when each party starts with an input of size $(d+1)\log |𝔽|$ bits. Hence, the communication complexity of Protocol 3.8, where each party starts with inputs of size $L$ bits, is $O(nL+n^2\log n)$ bits. $◀$

We prove the case of an honest sender and a corrupted sender.

We first show that if the sender is honest and has an input $f(x)$, then all honest parties output $(f(x),2)$. Specifically, all honest parties start the graded dispersal with the same input $f(x)$. Therefore, from the validity of graded-dispersal, all honest parties output $(f(x),2)$. Moreover, since more than $t+1$ honest parties hold the same input $f(x)$ in the data-dissemination protocol, all honest parties output $f(x)$ in that protocol, and output $(f(x),2)$ in the gradecast protocol.

We next consider the case where there exists an honest party $P_j$ with an output grade $2$. In that case, $P_j$ must have grade $2$ in the graded-dispersal protocol. As such, from the graded agreement, there are at least $t+1$ honest parties that output the same polynomial $f(x)$ with grade $g_i\ge 1$ from graded dispersal. Moreover, from the properties of graded-dispersal, parties with output that is not $f(x)$ use $\perp$ as their input in the data dissemination protocol. Thus, there are at least $t+1$ honest parties with input $f(x)$ in the data dissemination protocol, and therefore all honest parties must output $f(x)$ in the data dissemination. All honest parties output $f(x)$ with a grade of at least $1$. $◀$

We can reduce one round of interaction by sending the first round of the data-dissemination protocol together with the last round of the graded dispersal protocol. Specifically, each party that sends ${\mathrm{𝖮𝖪}}_2$ message to $P_j$ (the last round of the weak dispersal) sends together with it the point $f_i(j)$ to party $P_j$ (the first message of the data dissemination).

We, therefore, get that the total round complexity of the protocol is five rounds (Theorem 3.12 is reported in that light).

In the protocol as described, the communication complexity of the sender is $O(n(d+1)\log n)$ while the communication complexity of every other party is just $O(n\log n)$. To reduce the communication complexity for the sender, the sender can first send to each party $P_i$ its point $f(i)$. Each party forwards the point it received to all others, and the parties use Reed Solomon decoding to reconstruct the polynomial $f(x)$.

As mentioned, we use the relaxed definition of gradecast as defined in [20]. The definition by [17] requires that in the absence of a party with grade $2$, all parties with grade $1$ must agree on their message as well. This can be achieved at the expense of adding one round to the graded-dispersal, as discussed in Section 3.1.

We first show validity, then agreement.

If all honest parties have the same input $f(x)$, then from the graded agreement property of graded dispersal (Definition 3.1), we get that all honest parties output $(f(x),2)$. All honest parties then input $1$ to the Binary Byzantine agreement, and then all honest parties receive $1$ as output. The parties then invoke the data-dissemination protocol, and since there are more than $t+1$ honest parties with the input $f(x)$, all honest parties receive $f(x)$ as output and output it.

The output of the parties is determined by the output of the binary byzantine agreement, $b$, which is the same for all parties. There are two cases to consider:

• $\mathrm{■}$

  If $b=0$, then all honest parties output $\perp$, and agreement holds.

• $\mathrm{■}$

  If $b=1$, then there must exists an honest party $P_j$ with an input $b_j=1$ to the Binary Byzantine Agreement. By the properties of weak-dispersal (Definition 3.1), this implies that at least $t+1$ honest parties have the same output $f(x)$ from the weak-dispersal protocol, i.e., the input of each honest party to the data-dissemination protocol (Protocol 3.8) is either $\perp$ or $f(x)$, and there are at least $t+1$ honest parties with input $f(x)$. The data-dissemination protocol then guarantees that all parties output $f(x)$. The parties output that value in our Byzantine Agreement protocol, and we again have an agreement.

The only case that is interesting is when $b=1$. The graded dispersal guarantees that output was also an input of some honest party. $◀$

We show agreement and validity.

By the binary byzantine agreement, all parties receive the same bit $b$. If $b=0$, then all honest parties output $\perp$ and agreement holds; If $b=1$, then it must be that some honest party received grade $2$ in the graded dispersal. As follows from the guarantees of graded dispersal, this implies that there are at least $t+1$ honest parties with the same output $f(x)$. Those honest parties input $f(x)$ to the data dissemination, and the output of all honest parties is then $f(x)$. Agreement again holds.

If the sender is honest and starts with input $f(x)$ of degree-$d$ over $𝔽$, then from the guarantees of graded-dispersal, all honest parties output $(f(x),2)$. As such, all honest parties input $1$ to the binary byzantine agremeent, and must agree on $b=1$. Therefore, all run the data-dissemination protocol, and all output $f(x)$. $◀$

In the broadcast protocol as described in Protocol 3.17, the communication complexity of the sender is $n(d+1)\log n$ bits, whereas the communication complexity of every other party is just $O(n\log n)$ bits. As before, to reduce the communication complexity for the sender, the sender can first send to each party $P_i$ its point $f(i)$. The parties then forward the received point to all others and use Reed Solomon decoding to reconstruct the polynomial $f(x)$.

We show each one of the properties separately.

An honest party terminates only after it receives $2t+1$ $\mathrm{𝙳𝚘𝚗𝚎}$ messages. This implies that it received at least $t+1$ messages $\mathrm{𝙳𝚘𝚗𝚎}$ from honest parties (and in particular, it also sent the $\mathrm{𝙳𝚘𝚗𝚎}$ message). Eventually, all honest parties will receive those $t+1$ $\mathrm{𝙳𝚘𝚗𝚎}$ messages and, in response, will also send a $\mathrm{𝙳𝚘𝚗𝚎}$ message. We obtain that eventually, all honest parties send $\mathrm{𝙳𝚘𝚗𝚎}$ message, and therefore each honest party will eventually receive $2t+1$ $\mathrm{𝙳𝚘𝚗𝚎}$ messages, regardless of the messages of the adversary. Therefore, all honest parties must terminate.

An honest party that terminates with an output $f^{\ast }(x)\ne \perp$ must have sent an ${\mathrm{𝖮𝖪}}_2$ message. Moreover, since it terminated, it must have received at least $2t+1$ $\mathrm{𝙳𝚘𝚗𝚎}$ messages, i.e., it received $\mathrm{𝙳𝚘𝚗𝚎}$ messages from at least $t+1$ honest parties. An honest party sends a $\mathrm{𝙳𝚘𝚗𝚎}$ message if it either received $2t+1$ ${\mathrm{𝖮𝖪}}_2$ messages or received $t+1$ $\mathrm{𝙳𝚘𝚗𝚎}$ messages. The latter implies that at least one honest party sent a $\mathrm{𝙳𝚘𝚗𝚎}$ message due to receiving $2t+1$ ${\mathrm{𝖮𝖪}}_2$ messages, and at least $t+1$ honest parties sent ${\mathrm{𝖮𝖪}}_2$ message. As follows from Claim 3.4, there are at most two sets of parties (with the same polynomial) that could have sent ${\mathrm{𝖮𝖪}}_1$. We have two cases to consider:

• $\mathrm{■}$

  As follows from Claim 3.6, if there is no large set of $t+1$ parties with the same polynomial, then no party receives $2t+1$ ${\mathrm{𝖮𝖪}}_2$. This implies that no honest party would have sent the $\mathrm{𝙳𝚘𝚗𝚎}$ message, and no party terminates.

• $\mathrm{■}$

  If there is a large set of $t+1$ parties with the same polynomial $f^{\ast }(x)$, then no other party sends ${\mathrm{𝖮𝖪}}_2$.

This implies that if some honest party terminates, then we must have a large set of $t+1$ parties with the same polynomial $f^{\ast }(x)$. This implies that at least $t+1$ honest parties terminate with that polynomial $f^{\ast }(x)$. Any other honest party that terminates with non-$\perp$ must also output $f^{\ast }(x)$.

If all honest parties start with the same polynomial $f^{\ast }(x)$, then eventually, all honest parties will appear in the agreed sets of one another. As such, eventually, all honest parties will send the ${\mathrm{𝖮𝖪}}_2$ message, send $\mathrm{𝙳𝚘𝚗𝚎}$ messages, and terminate. Parties might terminate earlier; as mentioned, if one honest party terminates, it outputs its polynomial, and we are also guaranteed that at least $t+1$ other honest parties terminate with their input polynomials. Therefore, weak validity holds. $◀$