\section{Lower Bounds on First-Round Halting}\label{sec:FirstRound}

In this section, we present our lower bound for the probability of first-round halting in Byzantine agreement protocols.
\begin{theorem}[Bound on first-round halting. \cref{thm:FirstRound:Arb} restated]\label{thm:FirstRound:Arb:Res}
\ThmFirstRoundArb
\end{theorem}

Let $\Pi$ be as in \cref{thm:FirstRound:Arb:Res}. We assume for ease of notation that an honest party that runs more than one round outputs $\perp$ (it will be clear that the attack, described below, does not benefit from this change).
We also omit the security parameter from the parties' input list, it will be clear though that the adversaries we present are efficient \wrt the security parameter.

\begin{lemma}[Neighboring executions]\label{lemma:FirstRound:Arb}
	Let $\vect{v},\vect{v}' \in {\zo^n}$ be with $\mathrm{dist}(\vect{v},\vect{v}') \le t$. Then for both $\o\in \{0,1\}$:
	\[
	\pr{\Pi(\vect{v}') \in \set{\o,\bot}^n \setminus \set{\bot^n}} \ge	\pr{\Pi(\vect{v}) \in \set{\o,\bot}^n} - (1- \gamma) - 4\alpha - \mathsf{err}.
	\]
\end{lemma}
Namely, the lemma bounds from below the probability that in a random honest execution of the protocol on input $\vect{v}'$, at least one party halts in the first round while outputting $\o$.

We prove \cref{lemma:FirstRound:Arb} below, but first use it to prove \cref{thm:FirstRound:Arb:Res}. We also make use of the following immediate observation.
\begin{claim}[Almost pre-agreement]\label{claim:FirstRoundound:Arb:Validity}
Let $\vect{v} \in {\zo^n}$ and $\o \in \{0,1\}$ be such that $\mathrm{dist}(\vect{v},\o^n) \le t$. Then, $\pr{\Pi(\vect{v}) \in \set{\o,\bot}^n} \ge 1 - \alpha - \beta$.
\end{claim}
\begin{proof}
Let $\mathcal{A} \subset [n]$ be a subset of size $n-t$ such that $\vect{v}_\mathcal{A} = \o^{\size{\mathcal{A}}}$. The claimed validity of $\Pi$ yields that
\begin{align*}
\pr{\Pi(\vect{v})_\mathcal{A} \notin \set{\o,\bot}^{\size{\mathcal{A}}}} < \beta
\end{align*}
This follows from $\beta$-validity of $\Pi$ and the fact that an honest party cannot distinguish between an execution of $\Pi(\vect{v})$ and an execution of $\Pi(b^n)$ in which all parties not in $\mathcal{A}$ act as if their input bit is as in $\vect{v}$. Hence, by the claimed agreement of $\Pi$,

\begin{align*}
\pr{\Pi(\vect{v}) \notin \set{\o,\bot}^n} < \alpha + \beta
\end{align*}
\end{proof}

\begin{proof}[Proof of \cref{thm:FirstRound:Arb:Res}]~
We separately prove the theorem for $t \ge n/3$ and for $t \ge n/4$.

\paragraph{The case $t \ge n/3$.}
We assume for simplicity that $(n-t)/2\in {\mathbb{N}}$, let $\vect{v}_0= 0^t 1^{\ceil{(n-t)/2}} 0^{\floor{(n-t)/2}} $ and let $\vect{v}_1 = 1^t 1^{\ceil{(n-t)/2}} 0^{\floor{(n-t)/2}}$. Note that $\mathrm{dist}(\vect{v}_0,\vect{v}_1) = t$, and that for both $\o\in \{0,1\}$ it holds that $\mathrm{dist}(\vect{v}_\o,\o^n)\le t$. Hence, by \cref{claim:FirstRoundound:Arb:Validity},
for both $\o\in \{0,1\}$:
\begin{align*}
\pr{\Pi(\vect{v}_\o) \in \set{\o,\bot}^n} \ge 1 - \alpha - \beta.
\end{align*}
Applying \cref{lemma:FirstRound:Arb} to $\vect{v}= \vect{v}_0$ and $\vect{v}'= \vect{v}_1$ yields that
\begin{align*}
\pr{\Pi(\vect{v}_1) \in \set{0,\perp}^n \setminus \set{\bot^n}} \ge 1 - 5\alpha - \beta - (1- \gamma) - \mathsf{err},
\end{align*}
yielding that $5\alpha + 2\beta + (1-\gamma) + \mathsf{err}\ge 1$.

\paragraph{The case $t \ge n/4$.} In this case there are no two vectors that are $t$ apart in Hamming distance, and still each of them has $n-t$ entries of opposite values. Rather, we consider the two vectors $\vect{v}_0= 0^t 0^t 0^t 1^{n-3t}$ and $\vect{v}_1= 1^t 1^t 0^t 1^{n-3t}$ of distance $2t$. For both $\o\in \{0,1\}$, the vector $\vect{v}_\o$ has at least $n-t$ entries with $\o$ and is of distance $t$ from the vector $\mathbf{v}^{\star} =1^t 0^t 0^t 1^{n-3t}$.

As in the first part of the proof, Applying \cref{claim:FirstRoundound:Arb:Validity,lemma:FirstRound:Arb} on $\vect{v}_b$ and $\mathbf{v}^{\star}$, for both $b\in \{0,1\}$, yields that
\begin{align*}
\pr{\Pi(\mathbf{v}^{\star}) \in \set{\o,\bot}^n \setminus \set{\bot^n}} \ge 1 - 5\alpha - \beta - (1- \gamma) - \mathsf{err},
\end{align*}
yielding that $2(5\alpha + \beta + (1- \gamma) + \mathsf{err}) \ge 1$.
\end{proof}

\newcommand{\PPf}{\Pi^\mathcal{P}}
\subsection{Proving Lemma~\ref{lemma:FirstRound:Arb}}
\begin{proof}[Proof of \cref{lemma:FirstRound:Arb}]
Fix $b \in \{0,1\}$ and let $\delta = \pr{\Pi(\vect{v}) \in \set{\o,\bot}^n}$. Let $\mathcal{P}$ be the coordinates in which $\vect{v}$ and $\vect{v}'$ differ, and let ${\overline{\mathcal{P}}} = n \setminus \mathcal{P}$. Let $I$ be the index (a function of the parties' coins and setup parameters) of the smallest party in ${\overline{\mathcal{P}}}$ that halts in the first round and outputs the same value, both if the parties in $\mathcal{P}$ send their messages according to input $\vect{v}$ and if they do that according to $\vect{v}'$. We let $I=0$ if there is no such party, and (abusing notation) sometimes identify $I$ with the event that $I\neq 0$, \eg $\pr{I}$ stands for $\pr{I\ne 0}$. Clearly,

\begin{align*}
\delta \le \pr{\Pi(\vect{v}) \in \set{\o,\bot}^n \qand I}+ (1- \pr{I})
\end{align*}
and thus
\begin{align}\label{eq:FirstRound:Arb:1}
\pr{\Pi(\vect{v}) \in \set{\o,\bot}^n \qand I} \ge \delta - (1-\pr{I})
\end{align}

It follows that
\begin{align}\label{eq:FirstRound:Arb:2}
\pr{\Pi(\vect{v}') \in \set{\o,\bot}^n \setminus \set{\bot^n}} &\ge \pr{\Pi(\vect{v}') \in \set{\o,\bot}^n \qand I}\\
&=\pr{\Pi(\vect{v}') \in \set{\o,\bot}^n \qand \Pi(\vect{v}')_I= b}\nonumber\\
&\ge \pr{\Pi(\vect{v}')_I= b} - \alpha\nonumber\\
&= \pr{\Pi(\vect{v})_I = \o} - \alpha\nonumber\\
&\ge \pr{\Pi(\vect{v}) \in \set{\o,\bot}^n \qand \Pi(\vect{v})_I = \o} - 2\alpha\nonumber\\
&= \pr{\Pi(\vect{v}) \in \set{\o,\bot}^n \qand I} - 2\alpha\nonumber\\
&\ge \delta - (1-\pr{I}) - 2\alpha.\nonumber
\end{align}
The first inequality and the equalities hold by the definition of $I$. The second and third inequalities hold by agreement, and the last inequality holds by \cref{eq:FirstRound:Arb:1}. We conclude the proof showing that:
\begin{align}\label{claim:FirstRound:Arb}
	\pr{I} \ge \gamma - \mathsf{err} - 2\alpha
\end{align}

Let $E_h$ be the event that each party in ${\overline{\mathcal{P}}}$ either does not halt when the parties in $\mathcal{P}$ act according to $\vect{v}$ or does not halt when they act according to $\vect{v}'$. Let $E_a$ be the event that $E_h$ does not occur, but $I = 0$. Clearly $I = 0 \Longleftrightarrow E_h \lor E_a$.

Consider the adversary that in the first round acts toward a random subset of ${\overline{\mathcal{P}}}$ according to input $\vect{v}$ and towards the remaining parties according to $\vect{v}'$, and aborts at the end of this round. It is clear that if $E_a$ occurs, the above adversary violates agreement with probability $1/2$. Thus, $\pr{E_a} \le 2\alpha$.

It is also clear that when $E_h$ occurs, the above attacker fails to prevent an honest party
in ${\overline{\mathcal{P}}}$ from halting in the first round only if the following event happens: each party in ${\overline{\mathcal{P}}} $ does not halt in $\Pi(\vect{v}'')$ for some $\vect{v}'' \in \set{\vect{v},\vect{v}'}$, but the adversary acts towards each of these parties on the input in which it does halt. The latter event happens with probability at most $2^{-\size{{\overline{\mathcal{P}}}}} \le 2^{t-n} = \mathsf{err}$. Thus, $\pr{E_h} \le 1 - (\gamma - \mathsf{err})$. We conclude that
\begin{align}
	\pr{I} \ge 1 - \pr{E_h} - \pr{E_a} \ge \gamma - \mathsf{err} - 2\alpha
\end{align}
Finally, we note that if the protocol has public randomness, the (now rushing) attacker does not have to guess what input to act upon.
Rather, after seeing the first-round randomness, it \emph{finds} an input $\vect{v}'' \in\set{\vect{v},\vect{v}'}$ such that at least one party in ${\overline{\mathcal{P}}}$ does not halt in $\Pi(\vect{v}'')$ or violates agreement, and acts according to this input. Hence, the bound on $I$ changes to
\begin{align*}
\pr{I} \ge \gamma - \alpha,
\end{align*}
proving the theorem statement for such protocols.
\end{proof}

\section{Introduction}\label{sec:intro}

Byzantine agreement (BA)~\cite{PSL80,LSP82} is one of the most important problems in theoretical computer science. In a BA protocol, a set of $n$ parties wish to jointly agree on one of the honest parties' input bits.
The protocol is \emph{$t$-resilient} if no set of $t$ corrupted parties can collude and prevent the honest parties from completing this task.
In the closely related problem of \emph{broadcast}, all honest parties must agree on the message sent by a (potentially corrupted) sender.
Byzantine agreement and broadcast are fundamental building blocks in distributed computing and cryptography, with applications in fault-tolerant distributed systems~\cite{CL99,KBCCEGGRWWWZ00}, secure multiparty computation~\cite{Yao82,GMW87,BGW88,CCD88}, and more recently, blockchain protocols~\cite{SM16,GHMVZ17,PS18}.

In this work, we consider the \emph{synchronous} communication model, where the protocol proceeds in rounds. It is well known that in the plain model, without any trusted setup assumptions, BA and broadcast can be solved if and only if $t<n/3$~\cite{PSL80,LSP82,FLM85,GM93}. Assuming the existence of digital signatures and a public-key infrastructure (PKI), BA can be solved in the honest-majority setting $t<n/2$, and broadcast under any number of corruptions $t<n$~\cite{DS83}. Information-theoretic variants that remain secure against computationally unbounded adversaries exist using information-theoretic pseudo-signatures~\cite{PW92}.

An important aspect of BA and broadcast protocols is their \emph{round complexity}. For deterministic $t$-resilient protocols, $t+1$ rounds are known to be sufficient~\cite{DS83,GM93} and necessary~\cite{FL82,DS83}. The breakthrough results of \citet{Ben-Or83} and \citet{Rabin83} showed that this limitation can be circumvented using randomization. In particular, \citet{Rabin83} used \emph{random beacons} (common random coins that are secret-shared among the parties in a trusted setup phase) to construct a BA protocol resilient to $t<n/4$ corruptions. The failure probability of Rabin's protocol after $r$ rounds is $2^{-r}$, and the \emph{expected} number of rounds to reach agreement is constant. This line of research culminated with the work of \citet{FM97} who showed how to compute the common coins from scratch, yielding expected-constant-round BA protocol in the plain model, resilient to $t<n/3$ corruptions. \citet{KK06} gave an analogue result in the PKI-model for the honest-majority case. Recent results used trusted setup and cryptographic assumptions to establish a surprisingly small expected round complexity, namely $9$ for $t<n/3$~\cite{Micali17} and $10$ for $t<n/2$~\cite{MV17,ADDNR19}.

The expected-constant-round protocols mentioned above are guaranteed to terminate (with negligible error probability) within a poly-logarithmic number of rounds.
The lower bounds on the guaranteed termination from~\cite{FL82,DS83} were generalized by \cite{CMS89,KY84}, showing that any randomized $r$-round protocol must fail with probability at least $(c\cdot r)^{-r}$ for some constant $c$; in particular, randomized agreement with sub-constant failure probability cannot be achieved in \emph{strictly} constant rounds. However, to date there is no lower bound on the \emph{expected} round complexity of randomized BA.

In this work, we tackle this question and show new lower bounds for randomized BA. To make the discussion more informative, we consider a more explicit definition that bounds the halting probability within a specific number of rounds. A lower bound based on such a definition readily implies a lower bound on the expected round complexity of the BA protocol.

\subsection{The Model}\label{sec:intro:model}
We start with describing in more details the model in which our lower bounds are given. In the BA protocols considered in this work, the parties are communicating over a synchronous network of private and authenticated channels. Each party starts the protocol with an input bit and upon completion decides on an output bit. The protocol is $t$-resilient if when facing $t$ colluding parties that attack the protocol it holds that: (1) all honest parties agree on the same output bit (\emph{agreement}), and (2) if all honest parties start with the same input bit, then this is the common output bit (\emph{validity}). The protocols might have a \emph{trusted setup phase}: a trusted external party samples correlated values and distributes them between the parties. A setup phase is known to be essential for tolerating $t\geq n/3$ corruptions, and seems to be crucial for highly efficient protocols such as \cite{Micali17,SM16,MV17,ADDNR19,ACDNPRS19}. The trusted setup phase is typically implemented using (heavy) secure multiparty computation \cite{BCGTV15,BGG18}, via a public-key infrastructure, or with a random oracle (that can be used to model proof of work)~\cite{PS17}.

\paragraph{Locally consistent adversaries.}
The attacks presented in the paper require very limited capabilities from the corrupted parties (a limitation that makes our bounds stronger). Specifically, a corrupted party might (1) prematurely abort, and (2) send messages to different parties based on \emph{differing} input bits and/or incoming messages from other corrupted parties (see \cref{sec:OurResults:Adv} for a precise definition). We emphasize that corrupted parties sample their random coins honestly (and use the same coins for all messages sent). In addition, they do not lie about messages received from honest parties.

\paragraph{Public-randomness protocols.}
In many randomized protocols, including all those used in practice, cryptography is merely used to provide \emph{message authentication}---preventing a party from lying about the messages it received---and \emph{verifiable randomness}---forcing the parties to toss their coins correctly. The description of such protocols can be greatly simplified if only security against locally consistent adversaries is required (in which corrupted parties do not lie about their coin tosses and their incoming messages from honest parties). This motivates the definition of \emph{public-randomness} protocols, where each party publishes its local coin tosses for each round (the party's first message also contains its setup parameter, if such exists).
Although our attacks apply to arbitrary BA protocols, we show even stronger lower bounds for public-randomness protocols.

We illustrate the simplicity of the model by considering the BA protocol of \citet{Micali17}. In this protocol, the cryptographic tools, digital signatures and verifiable random functions (VRFs),\footnote{A pseudorandom function that provides a non-interactively verifiable proof for the correctness of its output.} are used to allow the parties elect leaders and toss coins with probability $2/3$ as follows: each party $\MathAlgX{P}_i$ in round $r$ evaluates the VRF on the pair $(i,r)$ and multicasts the result. The leader is set to be the party with the smallest VRF value, and the coin is set to be the least-significant bit of this value. Since these values are uniformly distributed $\kappa$-bit strings ($\kappa$ is the security parameter), and there are at least $2n/3$ honest parties, the success probability is $2/3$. (Indeed, with probability $1/3$, the leader is corrupted, and can send its value only to a subset of the parties, creating disagreement.)

When considering locally consistent adversaries, \citeauthor{Micali17}'s protocol can be significantly simplified by having each party randomly sample and multicast a uniformly distributed $\kappa$-bit string (cryptographic tools and setup phase are no longer needed). Corrupted parties can still send their values to a subset of honest parties as before, but they cannot send different random values to different honest parties.

A similar simplification applies to other BA protocols that are based on leader election and coin tosses such as \cite{FM97,FG03,KK06} (private channels are used for a leader-election sub-protocol), \cite{MV17,ADDNR19} (cryptography is used for coin-tossing and message-authentication), and \cite{SM16,ACDNPRS19} (cryptography is used to elect a small committee per round).\footnote{Unlike the aforementioned protocols that use ``simple'' preprocess and ``light-weight'' cryptographic tools, the protocol of \citet{Rabin83} uses a heavy, per execution, setup phase (consisting of Shamir sharing of a random coin for every potential round) that we do not know how to cast as a public-randomness protocol.}

\begin{proposition}[Malicious security to locally consistent public-randomness protocol, informal]\label{prop:mal_to_local}
Each of the BA protocols of \cite{FM97,FG03,KK06,Micali17,SM16,MV17,ADDNR19,ACDNPRS19} induces a public-randomness BA protocol secure against locally consistent adversaries, with the same parameters.
\end{proposition}

\paragraph{A useful abstraction for protocol design.}
To complete the picture, we remark that security against locally consistent adversaries, which may seem somewhat weak at first sight, can be compiled using standard cryptographic techniques into security against arbitrary adversaries. This reduction becomes lossless, efficiency-wise and security-wise, when applied to public-randomness protocols. Thus, building public-randomness protocols secure against locally consistent adversaries is a useful abstraction for protocol designers that want to use what cryptography has to offer, but without being bothered with the technical details.
See more details in \cref{sec:intro:LocalToFull}.

\paragraph{Connection to the full-information model.}
The public-randomness model can be viewed as a restricted form of the \emph{full-information model}~\cite{CC84,BL85,GGL98,BB98,BPV06,GPV06,KKKSS08,Lewko11,KS13,LL13}. In the latter model, the adversary is computationally unbounded and has complete access to all the information in the system, \ie it can listen to all transmitted messages and view the internal states of honest parties (such an adversary is also called \emph{intrusive}~\cite{CC84}). One of the motivations to study full-information protocols is to separate \emph{randomization} from \emph{cryptography} and see to what extent randomization alone can speed up Byzantine agreement. \citet{BB98} showed that any full-information BA protocol tolerating $t=\Theta(n)$ adaptive, fail-stop corruptions (\ie the adversary can dynamically choose which parties to crash) runs for $\tilde \Omega(\sqrt{n})$ rounds. \citet{GPV06} constructed an $O(\log{n})$-round BA protocol tolerating $t=(1/3-\varepsilon)n$ static, malicious corruptions, for an arbitrarily small constant $\varepsilon>0$.

We chose to state our results in the public-randomness model for two reasons. First, our lower bounds readily extend to lower bounds in the full-information model (since we consider weaker adversarial capabilities, \eg all our attacks are efficient). Second, when considering locally consistent adversaries, public-randomness captures essentially what efficient cryptography has to offer. Indeed, all protocol used in practice can be cast as public-randomness protocols tolerating locally consistent adversaries (\cref{prop:mal_to_local}) and every public-randomness protocol secure against locally consistent adversaries can be compiled, using cryptography, to malicious security in the standard model, where security relies on secret coins (see \cref{thm:local_to_malicious} below).

We note that it is known how to compile certain full-information protocols and ``boost'' their security from fail-stop into malicious; however, these compilers capture either deterministic protocols~\cite{Hadzilacos87,Bracha84,NT90} or protocols with a non-uniform source of randomness (namely, an SV-source~\cite{SV84})~\cite{GPV06}. It is unclear whether these compilers can be extended to capture arbitrary protocols (this is in fact stated as an open question in~\cite{Bracha84,GPV06}).
In addition, these compilers are designed to be information theoretic and not rely on cryptography; thus, they do not model highly efficient protocols used in practice.

\subsection{Our Results}\label{sec:intro:ourResult}
We present three lower bounds on the halting probability of randomized BA protocols.
To keep the following introductory discussion simple, we will assume that both validity and agreement properties hold perfectly, without error.

\paragraph{First-round halting.}
Our first result bounds the halting probability after a single communication round. This is the simplest case since parties cannot inform each other about inconsistencies they encounter. Indeed, the established lower bound is quite strong, showing an exponentially small bound on the halting probability when $t\geq n/3$, and exponentially close to $1/2$ when $t\geq n/4$.

\begin{theorem}[First-round halting, informal]\label{thm:intro:FirstRound}
Let $\Pi$ be an $n$-party BA protocol and let $\gamma$ denote the halting probability after a single communication round facing a locally consistent, static, adversary corrupting $t$ parties. Then,
\begin{itemize}
	\item $t \ge n/3$ implies $\gamma \le 2^{t-n}$ for arbitrary protocols, and $\gamma=0$ for public-randomness protocols.
	\item $t \ge n/4$ implies $\gamma \le 1/2+2^{t-n}$ for arbitrary protocols, and $\gamma \leq 1/2$ for public-randomness protocols.
\end{itemize}
\end{theorem}

Note that the deterministic $(t+1)$-round, $t$-resilient BA protocol of \citet{DS83} can be cast as a locally consistent public-randomness protocol (in the plain model).\footnote{When considering locally consistent adversaries, the impossibility of BA for $t\geq n/3$ does not apply.}
\cref{thm:intro:FirstRound} shows that for $n=3$ and $t=1$, this two-round BA protocol is essentially optimal and cannot be improved via randomization (at least without considering complex protocols that cannot be cast as public-randomness protocols).

\paragraph{Second-round halting for arbitrary protocols.}
Our second result considers the halting probability after two communication rounds.
This is a much more challenging regime, as honest parties have time to detect inconsistencies in first-round messages. Our bound for arbitrary protocols in this case is weaker, and shows that when $t>n/4$, the halting probability is bounded away from $1$.

\begin{theorem}[Second-round halting, arbitrary protocols, informal]\label{thm:intro:SecondRound:Arb}
Let $\Pi$ be an $n$-party BA protocol and let $\gamma$ denote the halting probability after two communication rounds facing a locally consistent, static, adversary corrupting $t=(1/4+\varepsilon)\cdot n$ parties.
Then, $\gamma \le 1 - (\varepsilon /5)^2$.
\end{theorem}

\paragraph{Second-round halting for public-randomness protocols.}
\cref{thm:intro:SecondRound:Arb} bounds the second-round halting probability of arbitrary BA protocols away from one. For public-randomness protocol we achieve a much stronger bound. The attack requires \emph{adaptive} corruptions (as opposed to \emph{static} corruptions in the previous case) and is based on a combinatorial conjecture that is stated below.\footnote{The attack holds even without assuming \cref{con:intro:IsoBot} when considering \emph{strongly adaptive} corruptions~\cite{GKP15}, in which an adversary sees all messages sent by honest parties in any given round and, based on the messages' content, decides whether to corrupt a party (and alter its message or sabotage its delivery) or not. Similarly, the conjecture is not required if each party is limited to tossing a single unbiased coin. These extensions are not formally proved in this paper.\label{footnote:no_conjecture}}

\begin{theorem}[Second-round halting, public-randomness protocols, informal]\label{thm:intro:SecondRound:PR}
Let $\Pi$ be an $n$-party public-randomness BA protocol and let $\gamma$ denote the halting probability after two communication rounds facing a locally consistent adversary adaptively corrupting $t$ parties.
Then, for sufficiently large $n$ and assuming \cref{con:intro:IsoBot} holds,
\begin{itemize}
\item $t > n/3$ implies $\gamma=0$.
\item $t > n/4$ implies $\gamma \leq 1/2$.
\end{itemize}
\end{theorem}

\cref{thm:intro:SecondRound:PR} shows that for sufficiently large $n$, any public-randomness protocol tolerating $t>n/3$ locally consistent corruptions cannot halt in less than three rounds (unless \cref{con:intro:IsoBot} is false). In particular, its expected round complexity must be at least three.

To understand the meaning of this result, recall the protocol of \citet{Micali17}. As discussed above, this protocol can be cast as a public-randomness protocol tolerating $t<n/3$ adaptive locally consistent corruptions. The protocol proceeds by continuously running a three-round sub-protocol until halting, where each sub-protocol consists of a coin-tossing round, a check-halting-on-$0$ round, and a check-halting-on-$1$ round. Executing a single instance of this sub-protocol demonstrates a halting probability of $1/3$ after three rounds.
By \cref{thm:intro:SecondRound:PR}, a protocol that tolerates slightly more corruptions, \ie $(1/3 +\varepsilon) \cdot n$, for arbitrarily small $\varepsilon>0$, cannot halt in fewer rounds.

\paragraph{Our techniques.}
Our attacks follow the spirit of many lower bounds on the round complexity on BA and broadcast~\cite{FL82,DS83,KY84,DRS90,GKKO07,AH10}. The underlying idea is to start with a configuration in which validity assures the common output is $0$, and gradually adjust it, while retaining the same output value, into a configuration in which validity assures the common output is $1$. (For the simple case of deterministic protocols, each step of the argument requires the corrupted parties to lie about their input bits and incoming messages from other corrupted parties, but otherwise behave honestly.) Our main contribution, which departs from the aforementioned paradigm, is adding another dimension to the attack by aborting a random subset of parties (rather than simply manipulating the input and incoming messages). This change allows us to bypass a seemingly inherent barrier for this approach. We refer the reader to \cref{sec:Technique} for a detailed overview of our attacks.

We remark that a similar approach was employed by \citet{AC08} for obtaining lower bounds on consensus protocols in the asynchronous shared-memory model, a flavor of BA in a communication model very different to the one considered in the present paper. Specifically, \cite{AC08} showed that in an asynchronous shared-memory system, $\Theta(n^2)$ steps are required for $n$ processors to reach agreement when facing $\Theta(n)$ \emph{computationally unbounded strongly adaptive} corruptions (see \cref{footnote:no_conjecture}). Their adversary also aborts a subset of the parties to prevent halting; however, the difference in communication model (synchronous in our work, vs.\ asynchronous in \cite{AC08}) and the adversary's power (efficient and adaptive in our work, vs.\ computationally unbounded and strongly adaptive in \cite{AC08}) yields a very different attack and analysis (though, interestingly, both attacks boil down to different variants of isoperimetric-type inequalities).

\paragraph{The combinatorial conjecture.}
We conclude the present section by motivating and stating the combinatorial conjecture assumed in \cref{thm:intro:SecondRound:PR}, and discussing its plausibility. We believe the conjecture to be of independent interest, as it relates to topics from Boolean functions analysis such as influences of subsets of variables \cite{Odonnel14} and isoperimetric-type inequalities \cite{MosselORSS2006,MosselOS2013}. The nature of our conjecture makes the following paragraphs somewhat technical, and reading them can be postponed until after going over the description of our attack in \cref{sec:Technique}.

The analysis of our attack naturally gives rise to an isoperimetric-type inequality. For limited types of protocols, we manage to prove it using Friedgut's theorem~\cite{Friedgut98} about approximate juntas and the KKL theorem~\cite{KKL88}. For arbitrary protocols, however, we can only
reduce our attack to the conjecture below.

We require the following notation before stating the conjecture. Let $\Sigma$ denote some finite set.
For $\vect{x}\in \Sigma^n$ and $\mathcal{S} \subseteq [n]$, define the vector $\bot_\mathcal{S}(\vect{x}) \in \set{\Sigma \cup \bot}^n$ by assigning all entries indexed by $\mathcal{S}$ with the value $\bot$, and all other entries according to $\vect{x}$. Finally, let $\mathbf{D}_{n,\sigma}$ denote the distribution induced over subsets of $[n]$ by choosing each element with probability $\sigma$ independently at random.

\def\MainConj{
For any $\sigma,\lambda >0$ there exists $\delta>0$ such that the following holds for large enough $n\in {\mathbb{N}}$: let $\Sigma$ be a finite alphabet, and let $\mathcal{A}_0,\mathcal{A}_1 \subseteq \sb^n$ be two sets such that for both $b\in \{0,1\}$:

\begin{align*}
\ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \Sigma^n}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}_b} \ge \lambda } \ge 1-\delta.
\end{align*}
Then,
\begin{align*}
\ppr{\substack{\mathcal{S} \gets \mathbf{D}_{n,\sigma} \vspace{.05in}\\ \vect{r}\gets \Sigma^n }}{\forall b\in \{0,1\}\colon \set{\vect{r},\bot_{\mathcal{S}}(\vect{r})} \cap \mathcal{A}_b \neq \emptyset} \ge \delta.
\end{align*}
}

\begin{conjecture}\label{con:intro:IsoBot}
\MainConj
\end{conjecture}

\noindent
Consider two large sets $\mathcal{A}_0$ and $\mathcal{A}_1$ which are ``stable'' in the following sense: for both $\o\in \{0,1\}$, with probability $1-\delta$ over $\mathcal{S}\gets \mathbf{D}_{n,\sigma}$, it holds that both $\vect{r}$ and $\bot_{\mathcal{S}}(\vect{r})$ belong to $\mathcal{A}_\o$, with probability at least $\lambda$ over $\vect{r}$. \cref{con:intro:IsoBot} stipulates that with high probability ($\ge \delta$), the vectors $\vect{r}$ and $\bot_{\mathcal{S}}(\vect{r})$ lie in opposite sets (\ie one is in $\mathcal{A}_0$ and the other $\mathcal{A}_{1-\o}$), for random $\vect{r}$ and $\mathcal{S}$. It is somewhat reminiscent of the following flavor of isoperimetric inequality: for any two large sets $\mathcal{B}_0$ and $\mathcal{B}_1$, taking a random element from $\mathcal{B}_0$ and resampling a few coordinates, yields an element in $\mathcal{B}_1$ with large probability. Less formally, one can ``move'' from one set to the other by manipulating a few coordinates~\cite{MosselORSS2006,MosselOS2013}.

A few remarks are in order. First, it suffices for our purposes to show that $\delta$ is a noticeable (\ie inverse polynomial) function of $n$, rather than independent of $n$.\footnote{We remark that it is rather easy to show that $\delta\ge 2^{-n}$, which is not good enough for our purposes.} We opted for the latter as it gives a stronger attack. Second, the conjecture holds for ``natural'' sets such as balls, \ie $\mathcal{A}_0$ and $\mathcal{A}_1$ are balls centered around $0^n$ and $1^n$ of constant radius,\footnote{The alphabet $\Sigma$ is not necessarily Boolean, and there are a couple of subtleties in defining balls.} and ``prefix'' sets, \ie sets of the form $\mathcal{A}_\o=\o^k \times \set{\Sigma \cup \bot}^{n-k}$. Furthermore, the claim can be proven when the probabilities over $\mathcal{S}$ and $\vect{r}$ are reversed, \ie ``with probability $\lambda$ over $\vect{r}$, it holds that both $\vect{r}$ and $\bot_{\mathcal{S}}(\vect{r})$ belong to $\mathcal{A}_\o$ with probability at least $1-\delta$ over $\mathcal{S}$'', instead of the above. Interestingly, this weaker statement boils down to the aforementioned isoperimetric-type inequality (cf.~\cite{MosselORSS2006} for the Boolean case and \cite{MosselOS2013} for the non Boolean case).

We conclude by pointing out that, as mentioned in \cref{footnote:no_conjecture}, the conjecture is not needed for certain limited cases that are not addressed in detail in the present paper. One such case is sketched out in \cref{sec:Technique}.

\subsection{Locally Consistent Security to Malicious Security}\label{sec:intro:LocalToFull}

As briefly mentioned in \cref{sec:intro:model}, protocols that are secure against locally consistent adversaries can be compiled to tolerate arbitrary malicious adversaries.
The compiler requires a PKI setup for digital signatures, verifiable random functions (VRFs)~\cite{MRV99}, and non-interactive zero-knowledge proofs (NIZK)~\cite{BFM88}. A VRF is a pseudorandom function with an additional property: using the secret key and an input $x$, the VRF outputs a pseudorandom value $y$ along with a proof string $\pi$; using the public key, everyone can use $\pi$ to verify whether $y$ is the output of $x$. We consider a trusted setup phase for establishing the PKI, where a trusted party generates VRF and signature keys for every party, securely gives the secret keys to each party, and publishes the public keys to all.

Given a protocol that is secure against locally consistent adversaries, the compiled protocol proceeds as follows, round by round.
Each party $\MathAlgX{P}_i$ sets its random coins for the \rth round $\rho_i^r$ (together with a proof $\pi_i^r$) by evaluating the VRF over the pair $(i,r)$.
Next, for every $j\in[n]$, party $\MathAlgX{P}_i$ uses these coins to compute the message $m^r_{i\to j}$ for $\MathAlgX{P}_j$, signs $m^r_{i\to j}$ as $\sigma^r_{i\to j}$, and sends $(m^r_{i\to j},\sigma^r_{i\to j},\pi_i^r)$ to $\MathAlgX{P}_j$.
Finally, $\MathAlgX{P}_i$ sends to $\MathAlgX{P}_j$ a NIZK proof that:
\begin{enumerate}
    \item
    There exist an input bit $b$, random coins $\rho_i^r$, as well as random coins $\rho^{r'}_i$ and incoming messages and $(m^{r'}_{1\to i},\ldots,m^{r'}_{n\to i})$ for every prior round $r'<r$, such that: (1) $\pi_i^r$ verifies that $\rho_i^r$ is the VRF output of $(i,r)$ (using the VRF public key of $\MathAlgX{P}_i$), (2) the message $m^r_{i\to j}$ was signed by $\MathAlgX{P}_i$, and (3) the message $m^r_{i\to j}$ is the output of the next-message function of $\MathAlgX{P}_i$ when applied to these values.
    \item
    For $r>1$, the messages $(m^{r'}_{k\to i},\sigma^{r'}_{k\to i},\pi_k^{r'})$ received by $\MathAlgX{P}_i$ from every $\MathAlgX{P}_k$ in prior rounds are proven to be properly generated. That is, $\MathAlgX{P}_k$ provided a NIZK proof that explains how $m^{r'}_{k\to i}$ was generated using random coins computed via the VRF on $(k,r')$ and on incoming messages that were signed by the senders.
\end{enumerate}

When considering public-randomness protocols, the above compilation can be made much more efficient. Instead of proving in zero knowledge the consistency of each message, each party $\MathAlgX{P}_i$ concatenates to each message all of its incoming messages from the previous round. A receiver can now locally verify the coins used by $\MathAlgX{P}_i$ are the VRF output of $(i,r)$ (as assured by the VRF), that the incoming messages are properly signed, and that the message is correctly generated from the internal state of $\MathAlgX{P}_i$ (which is now visible and verified).

\begin{theorem}[Locally consistent to malicious security, folklore, informal]\label{thm:local_to_malicious}
Assume PKI for digital signatures, VRF, and NIZK. Then, an expected-constant-round BA protocol secure against locally consistent adversaries can be compiled into a maliciously secure protocol with the same parameters.
\end{theorem}

The proof of \cref{thm:local_to_malicious} can be found in \cref{sec:LocalToFull}.

\subsection{Additional Related Work}\label{sec:relatedWork}

Following the work of \citet{FM97} in the two-thirds majority setting, \citet{KK06} improved the expected round complexity to $23$, and \citet{Micali17} to $9$. In the honest-majority setting, \citet{FG03} showed expected-constant-round protocol and \citet{KK06} expected $56$ rounds. \citet{MV17} adjusted the technique from \cite{Micali17} to the honest-majority case. \citet{ADDNR19} achieved expected $10$ rounds assuming static corruptions and expected $16$ rounds assuming adaptive corruptions. \citet{ACDNPRS19} constructed an expected-constant-round protocol tolerating $(1/2-\epsilon)\cdot n$ adaptive corruptions with sublinear communication complexity. In the dishonest-majority setting, \citet{GKKO07} constructed a broadcast protocol with expected $O(k^2)$ rounds, tolerating $t<n/2+k$ corruptions, that was improved by \citet{FN09} to expected $O(k)$ rounds.

\citet{AH10} extended the results of \citet{CMS89} and of \citet{KY84} on guaranteed termination of randomized BA protocols to the asynchronous setting, and provided a tight lower bound.

Randomized protocols with expected constant round complexity have \emph{probabilistic termination}, which requires delicate care \wrt composition (\ie their usage as subroutines by higher-level protocols). Parallel composition of randomized BA protocols was analyzed in \cite{Ben-Or83,FG03}, sequential composition in \cite{LLR06}, and universal composition in \cite{CCGZ16,CCGZ17}.

\subsection{Open Questions}\label{sec:OpenQuest}
Our attack on two-round halting of public-randomness protocols is based on \cref{con:intro:IsoBot}. In this work we prove special cases of this conjecture, but proving the general case remains an open challenge.

A different interesting direction is to bound the halting probability of protocols when $t<n/4$. It is not clear how to extend our attacks to this regime.

\subsection*{Paper Organization}

In \cref{sec:Technique} we present a technical overview of our attacks. The formal model and the exact bounds are stated in \cref{sec:OurResult}. The proof of the first-round halting is given in \cref{sec:FirstRound}, and for second-round halting in \cref{sec:SecondRound}.
The proof of \cref{thm:local_to_malicious} appears in \cref{sec:LocalToFull}.

\subsection{The Combinatorial Conjecture}\label{sec:Iso}
Next, we provide the formal statement for the combinatorial conjecture used in \cref{thm:SecondRound:PR}.
For $n\in {\mathbb{N}}$ and $\sigma \in [0,1]$, let $\mathbf{D}_{n,\sigma}$ be the distribution induced on the subsets of $[n]$ by sampling each element independently with probability $\sigma$.
For a finite alphabet $\Sigma$, a vector $\vect{x}\in \Sigma^n$, and a subset $\mathcal{S} \subseteq [n]$, define the vector $\bot_\mathcal{S}(\vect{x}) \in \Sigma^n$ by
\[
\bot_\mathcal{S}(\vect{x})_i=
\begin{cases}
\bot, & i\in {\cal{S}},\\
\vect{x}_i, & \text{otherwise}.
\end{cases}
\]

\begin{conjecture}[restating \cref{con:intro:IsoBot}]\label{con:IsoBot}
For any $\sigma,\lambda >0$ there exists $\delta>0$ such that the following holds for large enough $n\in {\mathbb{N}}$. Let  $\Sigma$ be a finite alphabet and let $\mathcal{A}_0,\mathcal{A}_1 \subseteq \sb^n$  be  two  sets such that for both $b\in \{0,1\}$:
\begin{align*
\ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \Sigma^n}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}_b} \ge  \lambda } \ge 1-\delta.
\end{align*}
Then,
\begin{align*
\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S} \gets \mathbf{D}_{n,\sigma}}}{\forall b\in \{0,1\}\colon  \set{\vect{r},\bot_{\mathcal{S}}(\vect{r})}  \cap \mathcal{A}_b \neq \emptyset} \ge  \delta.
\end{align*}
\end{conjecture}

\remove{
\begin{remark}\label{rem:IsoBot}
	We make the following observations.
	\begin{enumerate}

		\item The conjecture trivially holds then  the set $\mathcal{A}_0,\mathcal{A}_1$ are restricted to hamming balls and prefix sets

		\Inote{explain}

		\item  For our application, \cref{thm:SecondRound:PR}, we can weaken the conjecture allowing $\delta$ to be noticeable (\ie inverse polynomial) function of $n$ and $\size{\Sigma}$.

	\end{enumerate}
\end{remark}

\subsubsection{Towards Proving \cref{con:IsoBot}}
\Inote{the following theorem was proven by Alex}
\begin{notation}\label{not:Iso}
	For $n\in {\mathbb{N}}$, finite set $\Sigma$, $\vect{r}\in \Sigma^n$ and $\mathcal{S}\subseteq [n]$, let $F_\mathcal{S}(\vect{r})$ denote the random variable  defined by

	$F_\mathcal{S}(\vect{r})_i=\begin{cases} \vect{r}_i & \text{if } i\notin \mathcal{S} \\ \wt{r}_i\gets \Sigma &\text{ otherwise}.\end{cases}$.

\end{notation}

\begin{theorem}[Alex]\label{thm:Iso}
	For every $\sigma, \lambda>0$ there exists $\varepsilon>0$ such that the following holds for large enough $n\in {\mathbb{N}}$. Let  $\Sigma$ be a finite alphabet, and let $\mathcal{B}_0,\mathcal{B}_1 \subseteq \Sigma^n$ such that $\size{\mathcal{B}_b}\ge \lambda \cdot \size{\Sigma}^n $, for both $b\in \{0,1\}$. Then, $$\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{B}_0 \land F_\mathcal{S}(\vect{r})\in \mathcal{B}_1}\ge \varepsilon.$$
\end{theorem}

\Inote{I believe that the following variant of \cref{thm:Iso} should do for proving \cref{con:IsoBot}.}
\begin{conjecture}\label{con:Iso}
	For every $\sigma, \lambda,\delta>0$  the following holds for large enough $n\in {\mathbb{N}}$. Let  $\Sigma$ be a finite alphabet, and let $\mathcal{B}_0,\mathcal{B}_1 \subseteq \Sigma^n$ such that $\size{\mathcal{B}_b}\ge \lambda \cdot \size{\Sigma}^n $, for both $b\in \{0,1\}$.
	Then, there exists a distribution $\mathbf{D}_{n,\sigma}'$ with $\ppr{{\cal{S}} \gets  \mathbf{D}_{n,\sigma}'}{\size{{\cal{S}}} \ge 2\sigma n} \in o(1)$ such that
	$$\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}'}}{\vect{r}_{\overline{\cS}}\in (\mathcal{B}_0)_{\overline{\cS}} \cap (\mathcal{B}_1)_{\overline{\cS}}}\ge 1-\delta.$$
\end{conjecture}

}

\remove{

\cref{thmn:Iso} yields the following corollary.

\begin{corollary}\label{cor:IsoBot}
	For any $\sigma,\lambda >0$, there exists $\delta>0$ such that the following holds for large enough $n\in {\mathbb{N}}$. Let  $\Sigma$ be a finite alphabet, and let $\mathcal{A}_0,\mathcal{A}_1 \subseteq \sb^n$  be  two  sets such that for both $b\in \{0,1\}$:

	\begin{align*
	\ppr{\vect{r} \gets \Sigma^n}{\ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}_b} \ge  1-\delta } \ge \lambda.
	\end{align*}
	Then,
	\begin{align*
	\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S} \gets \mathbf{D}_{n,\sigma}}}{\forall b\in \{0,1\}\colon  \set{\vect{r},\bot_{\mathcal{S}}(\vect{r})}  \cap \mathcal{A}_b \neq \emptyset} \ge  \delta.
	\end{align*}
\end{corollary}

\begin{proof}
	For $\sigma, \lambda>0$, let $\varepsilon>0$ be the constant guaranteed by \cref{thmn:Iso} for the same $\sigma$, $\lambda$, and fix $\delta=\varepsilon/2$. We assume that $\ppr{\vect{r} \gets \Sigma^n}{\ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}_b} \ge  1-\delta } \ge \lambda$, for both $z\in \{0,1\}$, and we show that $\ppr{\vect{r},\mathcal{S}}{\vect{r}\in \mathcal{A}_0\land \bot_{\mathcal{S}}(\vect{r})\in \mathcal{A}_1 } \ge \delta$. For $z\in \{0,1\}$, we define $\mathcal{B}_z=\set{\vect{r}\in \Sigma^n \text{ s.t.\ } \ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}_z} \ge  1-\delta }$ and notice that $\size{\mathcal{B}_z}\ge \lambda \cdot \size{\Sigma}^n$, for both $z\in \{0,1\}$. Next, observe that

	\begin{align}
	&\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{A}_0\land \bot_{\mathcal{S}}(\vect{r})\in \mathcal{A}_1 } \ge  \ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{B}_0\land F_\mathcal{S}(\vect{r})\in \mathcal{B}_1 \land \bot_{\mathcal{S}}(\vect{r})\in \mathcal{A}_1 } =  \nonumber\\
	&\hspace*{2cm}\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{B}_0\land F_\mathcal{S}(\vect{r})\in \mathcal{B}_1 } - \ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{B}_0\land F_\mathcal{S}(\vect{r})\in \mathcal{B}_1 \land \bot_{\mathcal{S}}(\vect{r})\notin \mathcal{A}_1 }\nonumber
	\end{align}
	and, by \cref{thmn:Iso},
	\begin{align}
	&\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{A}_0\land \bot_{\mathcal{S}}(\vect{r})\in \mathcal{A}_1 } \ge     \label{eq:low2} \varepsilon - \ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{B}_0\land F_\mathcal{S}(\vect{r})\in \mathcal{B}_1 \land \bot_{\mathcal{S}}(\vect{r})\notin \mathcal{A}_1 }.
	\end{align}
	Finally, by the definition of $\mathcal{B}_z$, it holds that $\ppr{\mathcal{S}}{\bot_{\mathcal{S}}(\vect{r})\notin \mathcal{A}_1 \mid \vect{r}\in \mathcal{B}_1 }\le \delta $. Thus,
	\begin{align}\label{eq:bad} \ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{B}_0\land F_\mathcal{S}(\vect{r})\in \mathcal{B}_1 \land \bot_{\mathcal{S}}(\vect{r})\notin \mathcal{A}_1 } \le \ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{B}_1 \land \bot_{\mathcal{S}}(\vect{r})\notin \mathcal{A}_1 }\le \delta.
	\end{align}
	Given our choice of $\delta$, we combine \cref{eq:low2,eq:bad}, and we conclude that $$\ppr{\substack{\vect{r}\gets \Sigma^n\\ \mathcal{S}\gets \mathbf{D}_{n,\sigma}}}{\vect{r}\in \mathcal{A}_0\land \bot_{\mathcal{S}}(\vect{r})\in \mathcal{A}_1 } \ge \delta.$$
\end{proof}
\subsection{Proving \cref{thmn:Iso}}
}

\section{Locally Consistent Security to Malicious Security}\label{sec:LocalToFull}

\newcommand{\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace}{\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace}
\newcommand{\ensuremath{\mbox{\footnotesize{\textsf{DS}}}}\xspace}{\ensuremath{\mbox{\footnotesize{\textsf{DS}}}}\xspace}
\newcommand{\ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace}{\ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace}
\newcommand{\textsf{ZKPoK}\xspace}{\textsf{ZKPoK}\xspace}

\newcommand{\mathsf{VRF.Gen}}{\mathsf{VRF.Gen}}
\newcommand{\mathsf{VRF.Eval}}{\mathsf{VRF.Eval}}
\newcommand{\mathsf{VRF.Verify}}{\mathsf{VRF.Verify}}

\newcommand{\ensuremath{\mathsf{Expt}}\xspace}{\ensuremath{\mathsf{Expt}}\xspace}
\newcommand{\ensuremath{\Expt^\mathsf{VRF}}\xspace}{\ensuremath{\ensuremath{\mathsf{Expt}}\xspace^\mathsf{VRF}}\xspace}
\newcommand{\ensuremath{\Expt^\mathsf{Sig}}\xspace}{\ensuremath{\ensuremath{\mathsf{Expt}}\xspace^\mathsf{Sig}}\xspace}
\newcommand{\ensuremath{\mathcal{O}_\mathsf{eval}}\xspace}{\ensuremath{\mathcal{O}_\mathsf{eval}}\xspace}
\newcommand{\ensuremath{\mathcal{O}_\mathsf{sign}}\xspace}{\ensuremath{\mathcal{O}_\mathsf{sign}}\xspace}

\newcommand{\ensuremath{\mathcal{F}_\mathsf{zk}}\xspace}{\ensuremath{\mathcal{F}_\mathsf{zk}}\xspace}

\newcommand{\ensuremath{\mathcal{M}_\mathsf{in}}\xspace}{\ensuremath{\mathcal{M}_\mathsf{in}}\xspace}
\newcommand{\ensuremath{\tilde{\mathcal{M}}_\mathsf{in}}\xspace}{\ensuremath{\tilde{\mathcal{M}}_\mathsf{in}}\xspace}
\newcommand{\ensuremath{\mathcal{M}_\mathsf{out}}\xspace}{\ensuremath{\mathcal{M}_\mathsf{out}}\xspace}

\newcommand{\mathsf{NIZK.Gen}}{\mathsf{NIZK.Gen}}
\newcommand{\mathsf{NIZK.Prover}}{\mathsf{NIZK.Prover}}
\newcommand{\mathsf{NIZK.Verifier}}{\mathsf{NIZK.Verifier}}
\newcommand{\varphi}{\varphi}
\newcommand{\ensuremath{\mathsf{crs}}\xspace}{\ensuremath{\mathsf{crs}}\xspace}
\newcommand{\ensuremath{\mathcal{R}}\xspace}{\ensuremath{\mathcal{R}}\xspace}
\newcommand{\ensuremath{\mathcal{L}}\xspace}{\ensuremath{\mathcal{L}}\xspace}
\newcommand{\MathAlgX{S}_\mathsf{nizk}\xspace}{\MathAlgX{S}_\mathsf{nizk}\xspace}

\newcommand{\mathsf{DS.Gen}}{\mathsf{DS.Gen}}
\newcommand{\mathsf{DS.Sign}}{\mathsf{DS.Sign}}
\newcommand{\mathsf{DS.Verify}}{\mathsf{DS.Verify}}

\newcommand{\mathsf{sk}^{\mathsf{ds}}}{\mathsf{sk}^{\mathsf{ds}}}
\newcommand{\mathsf{vk}^{\mathsf{ds}}}{\mathsf{vk}^{\mathsf{ds}}}
\newcommand{\mathsf{sk}^{\mathsf{vrf}}}{\mathsf{sk}^{\mathsf{vrf}}}
\newcommand{\mathsf{vk}^{\mathsf{vrf}}}{\mathsf{vk}^{\mathsf{vrf}}}

\newcommand{\mathsf{setup}}{\mathsf{setup}}
\newcommand{\mathsf{Comp}}{\mathsf{Comp}}
\newcommand{\comp_\mathsf{PR}}{\mathsf{Comp}_\mathsf{PR}}

In this section, we formally state and prove \cref{thm:local_to_malicious} and show how to \emph{compile} any BA protocol that is secure against locally consistent adversaries into a protocol that is secure against malicious adversaries.
That is, we prove the following theorem:

\begin{theorem}[\cref{thm:local_to_malicious}, restated]\label{thm:local_to_malicious:Res}
Let $\Pi$ be a $(t,\alpha,\beta,q,\gamma)$-\MathAlgX{BA} against locally consistent adversaries for $q=O(\log{n})$ and assume the existence of verifiable random functions and existentially unforgeable digital signatures under an adaptive chosen-message attack.
Then,
\begin{enumerate}
    \item\label{thm:local_to_mal_generic}
    Assuming in addition the existence of non-interactive zero-knowledge proofs, there exist a {\sc ppt}\xspace protocol-compiler $\mathsf{Comp}(\cdot)$ such that $\Pi'=\mathsf{Comp}(\Pi)$ is a $(t,\alpha-\operatorname{neg}(\kappa),\beta-\operatorname{neg}(\kappa),q,\gamma-\operatorname{neg}(\kappa))$-\MathAlgX{BA} in the PKI model, resilient to malicious adversaries.
    \item\label{thm:local_to_mal_PC}
    There exists a {\sc ppt}\xspace protocol-compiler $\comp_\mathsf{PR}(\cdot)$ such that if $\Pi$ is a public-randomness protocol, then $\Pi'=\comp_\mathsf{PR}(\Pi)$ is a $(t,\alpha-\operatorname{neg}(\kappa),\beta-\operatorname{neg}(\kappa),q,\gamma-\operatorname{neg}(\kappa))$-\MathAlgX{BA} in the PKI model, resilient to malicious adversaries.
\end{enumerate}
\end{theorem}

In \cref{sec:ltf:prelim}, we define the cryptographic primitives used in the compiler, and in \cref{sec:ltf:compiler}, we construct the compiler and prove its security.

\subsection{Preliminaries}\label{sec:ltf:prelim}
The compiler makes use of  \emph{verifiable random functions} (VRF)~\cite{MRV99}, \emph{digital signatures}, and non-interactive zero-knowledge proofs, as defined below.

\subsubsection{Verifiable Random Functions}
We follow the definition of VRF from \cite{HJ16}.
\begin{definition}[VRF]\label{def:vrf}
A \textsf{verifiable random function} is a tuple of polynomial-time algorithms $\Pi=(\mathsf{VRF.Gen},\mathsf{VRF.Eval},\mathsf{VRF.Verify})$ of the following form.
\begin{itemize}
    \item
    $\mathsf{VRF.Gen}(1^\kappa)\to(\mathit{sk},\mathit{vk})$. On input the security parameter, the key-generation algorithm outputs a secret key $\mathit{sk}$ and a public verification key $\mathit{vk}$.
    \item
    $\mathsf{VRF.Eval}(\mathit{sk},x)\to(y,\pi)$. On input the secret key and an input $x\in\{0,1\}^\kappa$, the evaluation algorithm outputs a value $y\in \mathcal{S}$ (for a finite set $\mathcal{S}$) and a proof $\pi$.
    \item
    $\mathsf{VRF.Verify}(\mathit{vk},x,y,\pi)\to b$. On input the verification key, an input $x\in\{0,1\}^\kappa$, an output $y\in \mathcal{S}$, and a proof $\pi$, the deterministic verification algorithm outputs a bit $b\in\{0,1\}$.
\end{itemize}
\end{definition}
\noindent
We require the following properties:
\begin{itemize}
\item \textbf{Correctness.}
For $(\mathit{sk},\mathit{vk})\gets\mathsf{VRF.Gen}(1^\kappa)$ and $x\in\{0,1\}^\kappa$ it holds that if $(y,\pi)\gets\mathsf{VRF.Eval}(\mathit{sk},x)$ then $\mathsf{VRF.Verify}(\mathit{vk},x,y,\pi)=1$.

\item \textbf{Unique provability.}
For all strings $(\mathit{sk}, \mathit{vk})$ (not necessarily generated by $\mathsf{VRF.Gen}$) and all $x\in\{0,1\}^\kappa$, there  exists no $(y_0,\pi_0,y_1,\pi_1)$ such that $y_0\neq y_1$ and $\mathsf{VRF.Verify}(\mathit{vk},x,y_0,\pi_0)=\mathsf{VRF.Verify}(\mathit{vk},x,y_1,\pi_1)=1$.

\item \textbf{Pseudorandomness.}
For any {\sc ppt}\xspace adversary $\Ac} % {\Dc=(\Ac} % {\Dc_1,\Ac} % {\Dc_2)$ it holds that
\[
\size{\pr{\ensuremath{\Expt^\mathsf{VRF}}\xspace_{\Pi,\Ac} % {\Dc}(\kappa)=1}-\frac12}\leq \operatorname{neg}(\kappa),
\]
\noindent
for the experiment $\ensuremath{\Expt^\mathsf{VRF}}\xspace$ defined below:
\end{itemize}

\begin{small}
\begin{center}
\begin{tabular}{|l|l|}
    \hline
    \Centerstack{
    $\ensuremath{\Expt^\mathsf{VRF}}\xspace_{\Pi,\Ac} % {\Dc}(\kappa)$
    }
    &
    \Centerstack{
    $\ensuremath{\mathcal{O}_\mathsf{eval}}\xspace(x)$
    }\\
    \hline
    \Centerstack[l]{
    $(\mathit{sk},\mathit{vk})\gets\mathsf{VRF.Gen}(1^\kappa)$\\
    $(x^\ast,{\sf state})\gets\Ac} % {\Dc_1^{\ensuremath{\mathcal{O}_\mathsf{eval}}\xspace(\cdot)}(\mathit{vk})$\\
    $(y_0,\pi)\gets\mathsf{VRF.Eval}(\mathit{sk},x^\ast)$\\
    $y_1\gets_R \mathcal{S}$\\
    $b\gets_R \{0,1\}$\\
    $b'\gets\Ac} % {\Dc_2^{\ensuremath{\mathcal{O}_\mathsf{eval}}\xspace(\cdot)}({\sf state},y_b)$\\
    return $1$ if and only if $b=b'$\\
    \quad and $\Ac} % {\Dc$ didn't query $x^\ast$
    }
    &
    \shortstack[l]{
    $(y,\pi)\gets\mathsf{VRF.Eval}(\mathit{sk},x)$\\
    return $(y,\pi)$
    }\\
    \hline
\end{tabular}
\end{center}
\end{small}

\subsubsection{Digital Signatures}
We consider the standard notion of existentially unforgeable signatures under an adaptive chosen-message attack~\cite{GMR88}.
\begin{definition}[Digital signatures]
A \textsf{digital signatures} scheme is a tuple of polynomial-time algorithms $\Pi=(\mathsf{DS.Gen},\mathsf{DS.Sign},\mathsf{DS.Verify})$ of the following form.
\begin{itemize}
    \item
    $\mathsf{DS.Gen}(1^\kappa)\to(\mathit{sk},\mathit{vk})$. On input the security parameter, the key-generation algorithm outputs a secret signing key $\mathit{sk}$ and a public verification key $\mathit{vk}$.
    \item
    $\mathsf{DS.Sign}(\mathit{sk},m)\to\sigma$. On input the signing key and a message $m$, the signing algorithm outputs a signature $\sigma$.
    \item
    $\mathsf{DS.Verify}(\mathit{vk},m,\sigma)\to b$. On input the verification key, a message $m$, and a signature $\sigma$, the deterministic verification algorithm outputs a bit $b\in\{0,1\}$.
\end{itemize}
\end{definition}
\noindent
We require the following properties:
\begin{itemize}
\item \textbf{Correctness.}
For $(\mathit{sk},\mathit{vk})\gets\mathsf{DS.Gen}(1^\kappa)$ and a message $m$ it holds that if $\sigma\gets\mathsf{DS.Sign}(\mathit{sk},m)$ then $\mathsf{DS.Verify}(\mathit{vk},m,\sigma)=1$.

\item \textbf{Existentially unforgeable under an adaptive chosen-message attack.}
For any {\sc ppt}\xspace adversary $\Ac} % {\Dc$ it holds that
\[
\size{\pr{\ensuremath{\Expt^\mathsf{Sig}}\xspace_{\Pi,\Ac} % {\Dc}(\kappa)=1}}\leq \operatorname{neg}(\kappa),
\]
\noindent
for the experiment $\ensuremath{\Expt^\mathsf{Sig}}\xspace$ defined below:
\end{itemize}

\begin{small}
\begin{center}
\begin{tabular}{|l|l|}
    \hline
    \Centerstack{
    $\ensuremath{\Expt^\mathsf{Sig}}\xspace_{\Pi,\Ac} % {\Dc}(\kappa)$
    }
    &
    \Centerstack{
    $\ensuremath{\mathcal{O}_\mathsf{sign}}\xspace(m)$
    }\\
    \hline
    \Centerstack[l]{
    $(\mathit{sk},\mathit{vk})\gets\mathsf{DS.Gen}(1^\kappa)$\\
    $(m,\sigma)\gets\Ac} % {\Dc^{\ensuremath{\mathcal{O}_\mathsf{sign}}\xspace(\cdot)}(\mathit{vk})$\\
    return $1$ if and only if $\mathsf{DS.Verify}(\mathit{vk},m,\sigma)=1$\\
    \quad and $\Ac} % {\Dc$ didn't query $m$
    }
    &
    \shortstack[l]{
    $\sigma\gets\mathsf{DS.Sign}(\mathit{sk},m)$\\
    return $\sigma$
    }\\
    \hline
\end{tabular}
\end{center}
\end{small}

\subsubsection{Non-Interactive Zero-Knowledge Proofs}
A non-interactive zero-knowledge proof~\cite{BFM88} is a single-message protocol that allow a prover to convince a verifier the a certain common statement belongs to a language, without disclosing any additional information. We follow the definition from \cite{GOS12}.
\begin{definition}[NIZK]\label{def:nizk}
Let $\ensuremath{\mathcal{R}}\xspace$ be an $\class{NP}$-relation and let $\ensuremath{\mathcal{L}}\xspace_\ensuremath{\mathcal{R}}\xspace$ be the language consisting of the statements in $\ensuremath{\mathcal{R}}\xspace$.
A \textsf{non-interactive zero-knowledge proof} system for $\ensuremath{\mathcal{R}}\xspace$ is a tuple of polynomial-time algorithms $\Pi=(\mathsf{NIZK.Gen},\mathsf{NIZK.Prover},\mathsf{NIZK.Verifier})$ of the following form:
\begin{itemize}
    \item
    $\mathsf{NIZK.Gen}(1^\kappa)\to\ensuremath{\mathsf{crs}}\xspace$. On input the security parameter, the setup-generation algorithm outputs a common reference string $\ensuremath{\mathsf{crs}}\xspace$.
    \item
    $\mathsf{NIZK.Prover}(\ensuremath{\mathsf{crs}}\xspace,x,w)\to\varphi$. On input the $\ensuremath{\mathsf{crs}}\xspace$, a statement $x$, and a witness $w$ such that $(x,w)\in\ensuremath{\mathcal{R}}\xspace$, the prover algorithm outputs a proof string $\varphi$.
    \item
    $\mathsf{NIZK.Verifier}(\ensuremath{\mathsf{crs}}\xspace,x,\varphi)\to b$. On input the $\ensuremath{\mathsf{crs}}\xspace$, a statement $x$, and a proof $\varphi$, the verification algorithm outputs a bit $b\in\{0,1\}$.
\end{itemize}
\end{definition}
\noindent
We require the following properties:
\begin{itemize}
\item \textbf{Correctness.}
A proof system is complete if an honest prover with a valid witness can convince an honest verifier. For $(x,w)\in\ensuremath{\mathcal{R}}\xspace$ it holds that
\[
\pr{\mathsf{NIZK.Verifier}(\ensuremath{\mathsf{crs}}\xspace,x,\varphi)=1 \mid \ensuremath{\mathsf{crs}}\xspace\gets\mathsf{NIZK.Gen}(1^\kappa), \varphi\gets\mathsf{NIZK.Prover}(\ensuremath{\mathsf{crs}}\xspace,x,w)}=1.
\]
\item \textbf{Statistical soundness.}
A proof system is sound if it is infeasible to convince an honest verifier when the statement is false.
For all polynomial-size families $\sset{x_\kappa}$ of statements $x_\kappa\notin\ensuremath{\mathcal{L}}\xspace_\ensuremath{\mathcal{R}}\xspace$ and all adversaries $\Ac} % {\Dc$ it holds that
\[
\pr{\mathsf{NIZK.Verifier}(\ensuremath{\mathsf{crs}}\xspace,x_\kappa,\varphi)=1 \mid \ensuremath{\mathsf{crs}}\xspace\gets\mathsf{NIZK.Gen}(1^\kappa), \varphi\gets\Ac} % {\Dc(\ensuremath{\mathsf{crs}}\xspace,x_\kappa)}=1.
\]
\item \textbf{Computational (adaptive, multi-theorem) zero knowledge.}
A proof system is zero-knowledge if the proofs do not reveal any information about the witnesses. There exists a polynomial-time simulator $\MathAlgX{S}_\mathsf{nizk}\xspace=(\MathAlgX{S}_\mathsf{nizk}\xspace^1,\MathAlgX{S}_\mathsf{nizk}\xspace^2)$, where $\MathAlgX{S}_\mathsf{nizk}\xspace^1$ returns a simulated \ensuremath{\mathsf{crs}}\xspace together with a simulation trapdoor $\tau$ that enables $\MathAlgX{S}_\mathsf{nizk}\xspace^2$ to simulate proofs without having access to the witness. That is, for every non-uniform polynomial-time adversary $\Ac} % {\Dc$ it holds that
{\small{
\[
\abs{\pr{\Ac} % {\Dc^{\mathsf{P}_\ensuremath{\mathsf{crs}}\xspace(\cdot,\cdot)}(\ensuremath{\mathsf{crs}}\xspace)= 1 \mid \ensuremath{\mathsf{crs}}\xspace\gets\mathsf{NIZK.Gen}(1^\kappa)}
-\pr{\Ac} % {\Dc^{\MathAlgX{S}_{\ensuremath{\mathsf{crs}}\xspace,\tau}(\cdot,\cdot)}(\ensuremath{\mathsf{crs}}\xspace)= 1 \mid (\ensuremath{\mathsf{crs}}\xspace,\tau)\gets\MathAlgX{S}_\mathsf{nizk}\xspace^1(1^\kappa)}}\leq\operatorname{neg}(\kappa),
\]
}}
where $\MathAlgX{S}_{\ensuremath{\mathsf{crs}}\xspace,\tau}(x,w)=\MathAlgX{S}_\mathsf{nizk}\xspace^2(\ensuremath{\mathsf{crs}}\xspace,\tau,x)$ for $(x,w)\in\ensuremath{\mathcal{R}}\xspace$ and $\mathsf{P}_\ensuremath{\mathsf{crs}}\xspace(x,w)=\mathsf{NIZK.Prover}(\ensuremath{\mathsf{crs}}\xspace,x,w)$.
\end{itemize}

\subsubsection{Next-Message Functions}
An $n$-party protocol is represented by a set $\sset{\mathsf{next\mhyphen msg}_{i\to j}}_{i,j\in[n]}$ of next-message functions, a set $\sset{\mathsf{output}_i}_{i\in[n]}$ of output functions, and a distribution $D$ for generating setup information. Initially, the setup information is sampled as $(\mathsf{setup}_1,\ldots,\mathsf{setup}_n)\gets D$ and every party $\MathAlgX{P}_i$ receives $\mathsf{setup}_i$ before the protocol begins.
The view of a party $\MathAlgX{P}_i$ in the \rth round, denoted $\textsc{view}_i^r$, consists of: its input bit $x_i$, its setup information $\mathsf{setup}_i$, its random coin tosses $\rho_i=(\rho_i^1,\ldots,\rho_i^r)$ (where $\rho_i^{r'}$ are the tossed coins for round $r'$) and the incoming messages $(m^{r'}_{1\to i}, \ldots, m^{r'}_{n\to i})$ for every $r'<r$, where $m^{r'}_{j\to i}$ is the message received from $\MathAlgX{P}_j$ in round $r'$.
Given $\MathAlgX{P}_i$'s view in the \rth round, the function $\mathsf{next\mhyphen msg}_{i\to j}(\textsc{view}_i^r)$ outputs the message $m^r_{i\to j}$ to be sent by $\MathAlgX{P}_i$ to $\MathAlgX{P}_j$, except for the last round, where it outputs $\bot$; in that case the output function $\mathsf{output}(\textsc{view}_i^r)$ produces the output value $y$. \Wlg we assume that a message $m^r_{i\to j}$ is of the form $(r,i,j,m)$; looking ahead, this will ensure that two messages in the protocol will not have the same signature.

\subsubsection{The PKI Model}
The compiled protocol is designed to work in the \emph{public-key infrastructure} (PKI) model, where a trusted third party generates private/public keys for the parties before the protocol begins. In our setting, we will require a PKI for VRF, digital signatures, and \ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace, meaning that the trusted party operates as follows:
\begin{enumerate}
    \item
    For every $i\in[n]$, compute VRF keys $(\mathsf{sk}^{\mathsf{vrf}}_i,\mathsf{vk}^{\mathsf{vrf}}_i)\gets\mathsf{VRF.Gen}(1^\kappa)$.
    \item
    For every $i\in[n]$, compute signature keys $(\mathsf{sk}^{\mathsf{ds}}_i,\mathsf{vk}^{\mathsf{ds}}_i)\gets\mathsf{DS.Gen}(1^\kappa)$.
    \item
    Compute $\ensuremath{\mathsf{crs}}\xspace\gets\mathsf{NIZK.Gen}(1^\kappa)$.
    \item
    Send to every party $\MathAlgX{P}_i$ the secret keys $(\mathsf{sk}^{\mathsf{vrf}}_i,\mathsf{sk}^{\mathsf{ds}}_i)$ as well as all the public keys $\ensuremath{\mathsf{crs}}\xspace$, $(\mathsf{vk}^{\mathsf{vrf}}_1,\ldots,\mathsf{vk}^{\mathsf{vrf}}_n)$ and $(\mathsf{vk}^{\mathsf{ds}}_1,\ldots,\mathsf{vk}^{\mathsf{ds}}_n)$.
\end{enumerate}

\subsection{The Compiler}\label{sec:ltf:compiler}

Given a protocol that is secure against locally consistent adversaries, the main idea of the compiler is to limit the capabilities of a malicious adversary attacking the compiled protocol to those of a locally consistent one. This is achieved by proving an honest behavior via the cryptographic tools described above (VRF, digital signatures, and NIZK proofs) in a similar way to the GMW compiler~\cite{GMW87}. Unlike GMW, where all consistency proofs are carried out over a broadcast channel to ensure a consistent view between the honest parties, in our case the consistency proofs are done over pairwise channels, so they only guarantee local consistency.

\smallskip
We start by defining the NP relations that will be used for the zero-knowledge proofs. Each instance consists of a message between a pair of parties (say from $\MathAlgX{P}_i'$ to $\MathAlgX{P}_j'$) and the witness is the internal state of $\MathAlgX{P}_i'$ used to generate the message (the input, the random coins, and all incoming messages) along with a ``proof of correctness,'' \ie that the random coins were properly generated using the VRF, that the incoming messages that $\MathAlgX{P}_i'$ received from every $\MathAlgX{P}_k'$ were signed by $\MathAlgX{P}_k'$, and in turn were proven to be generated correctly (\ie that each $\MathAlgX{P}_k'$ used the correct random coins generated by the VRF and its incoming messages were signed by the senders). Note that this recursive step in the verification is required for proving locally consistent behaviour, since if both $\MathAlgX{P}_i'$ and $\MathAlgX{P}_k'$ are corrupt, then $\MathAlgX{P}_k'$ can send an arbitrary message to $\MathAlgX{P}_i'$ and sign it (in this case the NIZK proof from $\MathAlgX{P}_k'$ to $\MathAlgX{P}_i'$ will not verify). When $\MathAlgX{P}_i'$ sends its message to an honest $\MathAlgX{P}_j'$, it is not enough that $\MathAlgX{P}_i'$ proves that the messages from $\MathAlgX{P}_k'$ are properly signed, but $\MathAlgX{P}_i'$ must also prove that $\MathAlgX{P}_k'$ provided a NIZK proof asserting that its messages were generated by consistent random coins and correct incoming messages according to the next-message function.
For this reason we consider $q=O(\log{n})$

\paragraph{The Relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$.}
We will consider the following set of NP relations, where for $i,j\in[n]$ and an integer $r$, the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$ is parametrized by an $n$-party protocol $\Pi$ (represented by $\sset{\mathsf{next\mhyphen msg}_{i\to j}}_{i,j\in[n]}$ and $\sset{\mathsf{output}_i}_{i\in[n]}$), a $\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace$ scheme, a $\ensuremath{\mbox{\footnotesize{\textsf{DS}}}}\xspace$ scheme, and a \ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace scheme, as well as:
\begin{itemize}
	\item
	A vector of VRF verification keys $(\mathsf{vk}^{\mathsf{vrf}}_1,\ldots,\mathsf{vk}^{\mathsf{vrf}}_n)$.
	\item
	A vector of signature verification keys $(\mathsf{vk}^{\mathsf{ds}}_1,\ldots,\mathsf{vk}^{\mathsf{ds}}_n)$.
	\item
	A \ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace common reference string $\ensuremath{\mathsf{crs}}\xspace$.
\end{itemize}
The instance consists of a message $(m_{i\to j}^r,\sigma_{i\to j}^r,\pi_i^r)$ (the message from $\MathAlgX{P}_i$ to $\MathAlgX{P}_j$).
The witness consists of:
\begin{itemize}
	\item
	A bit $x_i\in\{0,1\}$ and a string $\mathsf{setup}_i$.
	\item
	A vector of random coins $(\rho_i^1,\ldots,\rho_i^r)$.
	\item
	For $r'\in[r-1]$ and $k\in[n]$, a message $\vect{m}^{r'}_{k\to i}=(m^{r'}_{k\to i},\sigma^{r'}_{k\to i},\pi^{r'}_k,\varphi_{k\to i}^{r'})$ ($\MathAlgX{P}_i$'s incoming messages).
\end{itemize}
The instance/witness pair is in the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$ if the following holds:
\begin{enumerate}
	\item
	For every $r'\in[r]$ it holds that $\mathsf{VRF.Verify}(\mathsf{vk}^{\mathsf{vrf}}_i,(i,r'),\rho_i^{r'},\pi_i^{r'})=1$.
	\item
	$\mathsf{DS.Verify}(\mathsf{vk}^{\mathsf{ds}}_i,m^r_{i\to j},\sigma^r_{i\to j})=1$.
	\item
	For $r'\in[r-1]$ and $k\in[n]$ it holds that $\mathsf{NIZK.Verifier}(\ensuremath{\mathsf{crs}}\xspace,(m^{r'}_{k\to i},\sigma^{r'}_{k\to i},\pi_k^{r'}),\varphi_{k\to i}^{r'})=1$ \wrt the relation $\ensuremath{\mathcal{R}}\xspace^{r'}_{k\to i}$.
	\item
	Set $\textsc{view}_i^1=(x_i,\mathsf{setup}_i,\rho_i^1)$ and for $1<r'\leq r$ set $\textsc{view}_i^{r'}=(\textsc{view}_i^{r'-1},m_{1\to i}^{r'-1},\ldots,m_{n\to i}^{r'-1},\rho_i^{r'})$. Then, it holds that $m_{i\to j}^r=\mathsf{next\mhyphen msg}_{i\to j}(\textsc{view}_i^r)$.
\end{enumerate}

\paragraph{The compiled protocol.}
Having defined the relations $\sset{\ensuremath{\mathcal{R}}\xspace^r_{i\to j}}$, we are ready to present the compiler for a protocol $\Pi$, secure against locally consistent adversaries to a maliciously secure one. Initially, in the setup phase, each party receives its setup information for $\Pi$ in addition to the PKI keys for $\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace$, digital signatures, and NIZK (as described above). To generate its coins for the \rth round (along with a proof), party $\MathAlgX{P}_i$ evaluates the $\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace$ over the pair $(i,r)$; next, $\MathAlgX{P}_i$ computes the \rth round messages for $\Pi$, signs each message, and sends to every other $\MathAlgX{P}_j$ the corresponding message, the signature, and the $\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace$ proof. In addition, $\MathAlgX{P}_i$ sends to $\MathAlgX{P}_j$ a $\ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace$ proof for $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$, proving that $\MathAlgX{P}_i$ behaves consistently towards $\MathAlgX{P}_j$.

Let $\Pi=(\MathAlgX{P}_1,\ldots,\MathAlgX{P}_n)$ be an $n$-party protocol represented by the set of next-message functions $\sset{\mathsf{next\mhyphen msg}_{i\to j}}_{i,j\in[n]}$, the set of output functions $\sset{\mathsf{output}_i}_{i\in[n]}$, and a distribution $D$ for generating setup information. Let $\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace$ be a verifiable random function, let $\ensuremath{\mbox{\footnotesize{\textsf{DS}}}}\xspace$ be a digital signatures scheme, and let $\ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace$ be a non-interactive zero-knowledge proof scheme.
Later on, we will simplify the compiler for the case of public-randomness protocols by removing the need for $\ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace$.

\begin{protocol}[Protocol $\Pi' = (\MathAlgX{P}'_1,\ldots, \MathAlgX{P}'_n)=\mathsf{Comp}(\Pi)$]\label{prot:generic}~
\begin{itemize}
\item[Setup:]
The setup-generation algorithm samples $(\mathsf{setup}_1,\ldots,\mathsf{setup}_n)\gets D$ for the protocol $\Pi$, computes $\ensuremath{\mathsf{crs}}\xspace\gets\mathsf{NIZK.Gen}(1^\kappa)$, and for every $i\in[n]$ computes $(\mathsf{sk}^{\mathsf{vrf}}_i,\mathsf{vk}^{\mathsf{vrf}}_i)\gets\mathsf{VRF.Gen}(1^\kappa)$ and $(\mathsf{sk}^{\mathsf{ds}}_i,\mathsf{vk}^{\mathsf{ds}}_i)\gets\mathsf{DS.Gen}(1^\kappa)$.
The setup string for party $\MathAlgX{P}'_i$ is set to be $\mathsf{setup}'_i=\left(\mathsf{setup}_i, \mathsf{sk}^{\mathsf{vrf}}_i,\mathsf{sk}^{\mathsf{ds}}_i, \ensuremath{\mathsf{crs}}\xspace,\mathsf{vk}^{\mathsf{vrf}}_1,\ldots,\mathsf{vk}^{\mathsf{vrf}}_n, \mathsf{vk}^{\mathsf{ds}}_1,\ldots,\mathsf{vk}^{\mathsf{ds}}_n\right)$.

\item[Input:] Party $\MathAlgX{P}_i'$  starts with an input bit $x_i\in\{0,1\}$.

\item[Round $r=1$:]~

\begin{enumerate}
	\item $\MathAlgX{P}_i'$ computes $(\rho_i^1,\pi_i^1)\gets\mathsf{VRF.Eval}(\mathsf{sk}^{\mathsf{vrf}}_i,(i,1))$ and sets $\textsc{view}_i^1=(x_i,\mathsf{setup}_i,\rho_i^1)$.
	\item $\MathAlgX{P}_i'$ computes for every $j\in[n]$ the message $m^1_{i\to j}=\mathsf{next\mhyphen msg}_{i\to j}(\textsc{view}_i^1)$ and signs $\sigma_{i\to j}^1\gets\mathsf{DS.Sign}(\mathsf{sk}^{\mathsf{ds}}_i,m_{i\to j}^1)$.

	\item $\MathAlgX{P}_i'$ computes for every $j\in[n]$ a proof for the relation $\ensuremath{\mathcal{R}}\xspace^1_{i\to j}$ on $\mathsf{stat}_{i\to j}^1=(m_{i\to j}^1,\sigma_{i\to j}^1,\pi_i^1)$ and witness $\mathsf{wit}_{i\to j}^1=(x_i,\mathsf{setup}_i,\rho^1_i)$ as $\varphi_{i\to j}^1\gets\mathsf{NIZK.Prover}(\ensuremath{\mathsf{crs}}\xspace, \mathsf{stat}_{i\to j}^1, \mathsf{wit}_{i\to j}^1)$.
	\item $\MathAlgX{P}_i'$ sends $\vect{m}_{i\to j}^1=(m_{i\to j}^1,\sigma_{i\to j}^1, \pi_i^1,\varphi_{i\to j}^1)$ to $\MathAlgX{P}'_j$.
\end{enumerate}

\item[Round $r>1$:]
Let $\vect{m}_{j\to i}^{r-1}=(m_{j\to i}^{r-1},\sigma_{j\to i}^{r-1}, \pi_j^{r-1},\varphi_{i\to j}^{r-1})$ be the message $\MathAlgX{P}_i'$ received from $\MathAlgX{P}_j'$ in round $r-1$. If $\MathAlgX{P}_j'$ did not send a message, or if $\mathsf{NIZK.Verifier}(\ensuremath{\mathsf{crs}}\xspace,(m_{j\to i}^{r-1},\sigma_{j\to i}^{r-1}, \pi_j^{r-1}), \varphi_{i\to j}^{r-1})=0$, set $m_{j\to i}^{r-1}=\bot$.

\begin{enumerate}
	\item $\MathAlgX{P}_i'$ computes $(\rho_i^r,\pi_i^r)\gets\mathsf{VRF.Eval}(\mathsf{sk}^{\mathsf{vrf}}_i,(i,r))$ and sets the internal view as $\textsc{view}_i^r=(\textsc{view}_i^{r-1},m_{1\to i}^{r-1},\ldots,m_{n\to i}^{r-1},\rho_i^r)$.
    \item
    $\MathAlgX{P}_i'$ computes for every $j\in[n]$ the message $m^r_{i\to j}=\mathsf{next\mhyphen msg}_{i\to j}(\textsc{view}_i^r)$ and signs $\sigma_{i\to j}^r\gets\mathsf{DS.Sign}(\mathsf{sk}^{\mathsf{ds}}_i,m_{i\to j}^r)$.

	\item $\MathAlgX{P}_i'$ computes for every $j\in[n]$ a proof for the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$ on the statement $\mathsf{stat}_{i\to j}^r=(m_{i\to j}^r,\sigma_{i\to j}^r,\pi_i^r)$ and witness $\mathsf{wit}_{i\to j}^r=(\mathsf{wit}_{i\to j}^{r-1}, \rho^r_i, \sset{\vect{m}_{k\to i}^{r-1}}_{k\in[n]})$ as $\varphi_{i\to j}^r\gets\mathsf{NIZK.Prover}(\ensuremath{\mathsf{crs}}\xspace, \mathsf{stat}_{i\to j}^r, \mathsf{wit}_{i\to j}^r)$.
	\item $\MathAlgX{P}_i'$ sends $\vect{m}_{i\to j}^r=(m_{i\to j}^r,\sigma_{i\to j}^r,\varphi_{i\to j}^r,\pi_i^r)$ to $\MathAlgX{P}'_j$.
\end{enumerate}

\item[Output:]
If in some round $r$, the output of $\mathsf{next\mhyphen msg}_{i\to j}(\textsc{view}_i^r)$ is $\bot$ for all $j\in[n]$, indicating it is the last round, $\MathAlgX{P}_i'$ outputs $y=\mathsf{output}(\textsc{view}_i^r)$ and halts.
\end{itemize}
\end{protocol}

\subsubsection{Security Proof}
We prove the security of \cref{prot:generic} using a sequence of arguments. Given a protocol $\Pi$ secure against locally consistent adversaries, we first adjust it to use pseudorandom coins computed using a VRF. The new protocol, denoted $\Pi_1$, remains secure against slightly weaker locally consistent adversaries by the pseudorandomness property of the VRF. Next, we show how to convert any malicious adversary against the compiled protocol $\Pi'=\mathsf{Comp}(\Pi)$ into a ``weak'' locally consistent attack against $\Pi_1$. The proof of the second part of the theorem, concerning public-randomness protocols, follows in similar lines.

\begin{proof}[Proof of \cref{thm:local_to_malicious:Res}]
We start by proving the first part of the theorem, considering generic protocols, and later focus on public-randomness protocols.

\paragraph{Proof of Item~\ref{thm:local_to_mal_generic} (generic protocols).}
We prove Item~\ref{thm:local_to_mal_generic} in two steps.
Initially, as an intermediate step, we consider a variant of $\Pi$, denoted $\Pi_1$, where the parties behave exactly as in $\Pi$ except that they use a $\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace$ to compute their random coins for each round. Formally, $\Pi_1$ is defined in the PKI model, where, in addition to the setup information for $\Pi$, every party $\MathAlgX{P}_i$ receives $\mathsf{sk}^{\mathsf{vrf}}_i$ and $(\mathsf{vk}^{\mathsf{vrf}}_1,\ldots,\mathsf{vk}^{\mathsf{vrf}}_n)$ for $(\mathsf{sk}^{\mathsf{vrf}}_i,\mathsf{vk}^{\mathsf{vrf}}_i)\gets\mathsf{VRF.Gen}(1^\kappa)$. During the execution of the protocol, each party $\MathAlgX{P}_i$ evaluates $(\rho_i^r,\pi_i^r)\gets\mathsf{VRF.Eval}(\mathsf{sk}^{\mathsf{vrf}}_i,(i,r))$, sets its coins for the \rth round to $\rho_i^r$ (instead of a uniformly distributed string), and appends $\pi_i^r$ to its \rth round messages.
Note that the strings $\rho_i^r$ are deterministic, so a locally consistent adversary has the power to use arbitrary values instead. To enable a reduction to the security of $\Pi$, we will explicitly assume that corrupted parties indeed use the honestly generated pseudorandom values $\rho_i^r$ by evaluating the \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace on $(i,r)$; we call such a locally consistent adversary \emph{\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant}.
\begin{claim}
If $\Pi$ is a $\left(t,\alpha,\beta,q,\gamma\right)$-\MathAlgX{BA} against locally consistent adversaries, then $\Pi_1$ is a $\left(t,\alpha-\operatorname{neg}(\kappa),\beta-\operatorname{neg}(\kappa),q,\gamma-\operatorname{neg}(\kappa)\right)$-\MathAlgX{BA} against locally consistent  \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries.
\end{claim}
\begin{proof}
By assumption, a corrupted $\MathAlgX{P}_i$ uses the value $\rho_i^r$ as its random coins for the \rth round. Therefore, the only difference between $\Pi_1$ and $\Pi$ are the use of pseudorandom string instead of uniformly distributed strings. The proof follows by the pseudorandomness of the $\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace$ scheme using a standard hybrid argument.
\end{proof}

Next, let $\Ac} % {\Dc'$ be an adversary attacking $\Pi'=(\MathAlgX{P}'_1,\ldots,\MathAlgX{P}'_n)$. We will construct an adversary $\Ac} % {\Dc$ for the protocol $\Pi_1=(\MathAlgX{P}_1,\ldots,\MathAlgX{P}_n)$. Let $\MathAlgX{S}_\mathsf{nizk}\xspace=(\MathAlgX{S}_\mathsf{nizk}\xspace^1,\MathAlgX{S}_\mathsf{nizk}\xspace^2)$ be the simulator that is guaranteed for the NIZK scheme. The adversary $\Ac} % {\Dc$ runs internally a copy of $\Ac} % {\Dc'$ and proceeds as follows:
\begin{itemize}
\item
In the setup phase of $\Pi_1$, $\Ac} % {\Dc$ receives the setup string $\left(\mathsf{setup}_i, \mathsf{sk}^{\mathsf{vrf}}_i,\mathsf{vk}^{\mathsf{vrf}}_1,\ldots,\mathsf{vk}^{\mathsf{vrf}}_n\right)$ (consisting of the setup for $\Pi$ and the \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace keys). Next, \Ac} % {\Dc samples $(\ensuremath{\mathsf{crs}}\xspace,\tau)\gets\MathAlgX{S}_\mathsf{nizk}\xspace^1(1^\kappa)$ and $(\mathsf{sk}^{\mathsf{ds}}_i,\mathsf{vk}^{\mathsf{ds}}_i)\gets\mathsf{DS.Gen}(1^\kappa)$ for every $i\in[n]$, and provides the setup string $\mathsf{setup}'_i=\left(\mathsf{setup}_i, \mathsf{sk}^{\mathsf{vrf}}_i,\mathsf{sk}^{\mathsf{ds}}_i, \ensuremath{\mathsf{crs}}\xspace,\mathsf{vk}^{\mathsf{vrf}}_1,\ldots,\mathsf{vk}^{\mathsf{vrf}}_n, \mathsf{vk}^{\mathsf{ds}}_1,\ldots,\mathsf{vk}^{\mathsf{ds}}_n\right)$ for every corrupted $\MathAlgX{P}'_i$.

\item
Upon receiving a message $(m^r_{i \to j},\pi_i^r)$ from an honest $\MathAlgX{P}_i$ to a corrupted $\MathAlgX{P}_j$ in the execution of $\Pi_1$, \Ac} % {\Dc sends $(m^r_{i \to j},\sigma^r_{i \to j},\pi_i^r, \varphi_{i\to j}^r)$ to $\Ac} % {\Dc'$ with $\sigma_{i\to j}^r\gets\mathsf{DS.Sign}(\mathsf{sk}^{\mathsf{ds}}_i,m^r_{i \to j})$ and $\varphi_{i\to j}^r\gets\MathAlgX{S}_\mathsf{nizk}\xspace^2(\ensuremath{\mathsf{crs}}\xspace,\tau,(m^r_{i \to j},\sigma^r_{i \to j},\pi_i^r))$.
\item
When $\Ac} % {\Dc$ receives $(m^r_{i \to j},\sigma^r_{i \to j},\pi_i^r,\varphi_{i\to j}^r)$ from $\Ac} % {\Dc'$ on behalf of a corrupted $\MathAlgX{P}_i'$ to an honest $\MathAlgX{P}_j'$ (in the simulated execution of $\Pi'$), \Ac} % {\Dc first verifies that $\mathsf{NIZK.Verifier}(\ensuremath{\mathsf{crs}}\xspace,(m^r_{i \to j},\sigma^r_{i \to j},\pi_i^r),\varphi_{i\to j}^r)=1$. If the proof is verified, \Ac} % {\Dc sends the message $(m^r_{i \to j},\pi_i^r)$ to $\MathAlgX{P}_j$ in the protocol $\Pi_1$; otherwise, \Ac} % {\Dc considers $\MathAlgX{P}_i$ as an aborting party towards $\MathAlgX{P}_j$.
\end{itemize}

We complete the proof in a series of steps, analyzing the attack under increasingly stronger power of the adversary $\Ac} % {\Dc'$, starting from a locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant attack until reaching a full blown malicious attack.
Initially, we will assume perfect security of the NIZK, and remove this restriction later on.
\begin{claim}
Consider a perfect NIZK scheme.
If $\Pi_1$ is a $\left(t,\alpha,\beta,q,\gamma\right)$-\MathAlgX{BA} against locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries, then $\Pi'$ is a $\left(t,\alpha,\beta,q,\gamma\right)$-\MathAlgX{BA} against locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries.
\end{claim}
\begin{proof}
If $\Ac} % {\Dc'$ is a locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversary, then in particular whenever $\Ac} % {\Dc'$ sends a message on behalf of a corrupted $\MathAlgX{P}_i'$, he knows a witness for the \ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace proof. Therefore, \wlg we can assume that either a corrupted $\MathAlgX{P}_i'$ does not send a message (\ie aborts) to an honest $\MathAlgX{P}_j'$ or that $\MathAlgX{P}_i'$ correctly generates the \ensuremath{\mbox{\footnotesize{\textsf{NIZK}}}}\xspace proof. In that case every locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant attack by $\Ac} % {\Dc'$ translates to a locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant attack by $\Ac} % {\Dc$.
\end{proof}

The next claim considers stronger adversaries that are allowed to use arbitrary random coins for computing the next-message function.
We will use the following notations: A message sent in $\Pi'$ is of the form $(m,\sigma,\pi,\varphi)$; we call $m$ the \emph{content of the message}. For a party $\MathAlgX{P}_i'$, let $\ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}$ denote the set of incoming messages' contents received from party $\MathAlgX{P}_k'$ in round $r'$ (as this is a locally consistent attack, there could be multiple incoming messages from each corrupted party, but at most one message from each honest party). Let $\ensuremath{\mathcal{M}_\mathsf{out}}\xspace^{r,i\to j}$ be the set of possible messages' contents that $\MathAlgX{P}_i'$ can send to $\MathAlgX{P}_j'$ at round $r$ under a \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant locally consistent attack when using a subset of the incoming messages' contents $\sset{\ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}}_{r'<r, k\in[n]}$ and randomness $\sset{\rho_i^{r'}}_{r'\in[r]}$ computed as $(\rho_i^{r'},\pi_i^{r'})\gets\mathsf{VRF.Eval}(\mathsf{sk}^{\mathsf{vrf}}_i,(i,r'))$.

\begin{claim}\label{claim:LC:rand}
Consider a perfect NIZK scheme.
If $\Pi_1$ is a $\left(t,\alpha,\beta,q,\gamma\right)$-\MathAlgX{BA} against locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries, then $\Pi'$ is a $\left(t,\alpha-\operatorname{neg}(\kappa),\beta-\operatorname{neg}(\kappa),q,\gamma-\operatorname{neg}(\kappa)\right)$-\MathAlgX{BA} against locally consistent adversaries.
\end{claim}
\begin{proof}
We prove the claim by showing that the additional power of the adversary only allows for a negligible cheating advantage.
Consider a locally consistent adversary $\Ac} % {\Dc'$ and assume that a corrupted party $\MathAlgX{P}_i'$ used arbitrary random coins to generate the message content for party $\MathAlgX{P}_j'$ in round $r$, denoted $\tilde{m}_{i\to j}^r$. There are two possible cases:
\begin{itemize}
    \item[\textbf{Case 1:}]
    If $\tilde{m}_{i\to j}^r\in\ensuremath{\mathcal{M}_\mathsf{out}}\xspace^{r,i\to j}$, then the adversary can compute a witness for the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$. That is, even if the actual coins used to generate $\tilde{m}_{i\to j}^r$ are different than $\sset{\rho_i^{r'}}_{r'\in[r]}$, the message $\tilde{m}_{i\to j}^r$ can be explained as if generated using $\sset{\rho_i^{r'}}_{r'\in[r]}$ consistently with a subset of the incoming messages in $\sset{\ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}}_{r'<r, k\in[n]}$. Therefore, \wlg this can be cast as a locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant attack.
    \item[\textbf{Case 2:}]
    If $\tilde{m}_{i\to j}^r\notin\ensuremath{\mathcal{M}_\mathsf{out}}\xspace^{r,i\to j}$, let $\sset{\tilde{\rho}_i^{r'}}_{r'\in[r]}$ be the coins used by $\Ac} % {\Dc'$ to generate $\tilde{m}_{i\to j}^r$. Then, $\tilde{\rho}_i^{r'}\neq \rho_i^{r'}$ for at least one $r'$. To provide a witness for the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$, $\Ac} % {\Dc'$ must generate $\tilde{\pi}_i^{r'}$ such that $\mathsf{VRF.Verify}(\mathsf{vk}^{\mathsf{vrf}}_i,(i,r'),\tilde{\rho}_i^{r'},\tilde{\pi}_i^{r'})=1$. By unique provability property of the VRF, such an attack can only succeed with negligible probability.
\end{itemize}
\end{proof}

The next claim considers stronger adversaries that are allowed to use arbitrary incoming messages for their next-message function.
\begin{claim}\label{claim:LC:messages}
Consider a perfect NIZK scheme.
If $\Pi_1$ is a $\left(t,\alpha,\beta,q,\gamma\right)$-\MathAlgX{BA} against locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries, then $\Pi'$ is a $\left(t,\alpha-\operatorname{neg}(\kappa),\beta-\operatorname{neg}(\kappa),q,\gamma-\operatorname{neg}(\kappa)\right)$-\MathAlgX{BA} against locally consistent adversaries that are allowed to use arbitrary messages' contents when computing the next-message function.
\end{claim}
\begin{proof}
Consider an adversary $\Ac} % {\Dc'$ that behaves locally consistent but can use arbitrary values as incoming messages. Assume that $\Ac} % {\Dc'$ is \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant and let $r$ be the first round in which $\Ac} % {\Dc'$ deviates from the protocol \wrt incoming messages. Let $\MathAlgX{P}_i'$ be a corrupted party that uses $\sset{\ensuremath{\tilde{\mathcal{M}}_\mathsf{in}}\xspace^{r',k\to i}}_{r'<r, k\in[n]}$ as its set of incoming messages to generate the message content for party $\MathAlgX{P}_j'$ in round $r$, denoted $\tilde{m}_{i\to j}^r$, and assume that $\bigcup \ensuremath{\tilde{\mathcal{M}}_\mathsf{in}}\xspace^{r',k\to i} \nsubseteq \bigcup \ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}$.
There are two possible cases:

\begin{itemize}
    \item[\textbf{Case 1:}]
    If $\tilde{m}_{i\to j}^r\in\ensuremath{\mathcal{M}_\mathsf{out}}\xspace^{r,i\to j}$, then the adversary can compute a witness for the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$. That is, even if $\bigcup \ensuremath{\tilde{\mathcal{M}}_\mathsf{in}}\xspace^{r',k\to i} \nsubseteq \bigcup \ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}$, the message $\tilde{m}_{i\to j}^r$ can be explained as if generated using a subset of $\bigcup \ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}$. Therefore, \wlg this can be cast as a locally consistent attack.
    \item[\textbf{Case 2:}]
    If $\tilde{m}_{i\to j}^r\notin\ensuremath{\mathcal{M}_\mathsf{out}}\xspace^{r,i\to j}$, then to find a witness for the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$, $\Ac} % {\Dc'$ must produce for every message $\tilde{m}_{k\to i}^{r'}\in\bigcup \ensuremath{\tilde{\mathcal{M}}_\mathsf{in}}\xspace^{r',k\to i} \setminus\bigcup \ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}$ a signature $\tilde{\sigma}_{k\to i}^{r'}$, a VRF proof $\pi_{k\to i}^{r'}$ and a NIZK proof $\tilde{\varphi}_{k\to i}^{r'}$ .
    \begin{itemize}
        \item
        If $\MathAlgX{P}_k$ is honest, $\Ac} % {\Dc'$ can find an accepting signature $\tilde{\sigma}_{k\to i}^{r'}$ for $\tilde{m}_{k\to i}^{r'}$ under $\mathsf{vk}^{\mathsf{ds}}_k$ only with negligible probability (recall that every message $\tilde{m}_{k\to i}^{r'}$ encodes the values $k,i,r'$; hence, $\Ac} % {\Dc'$ cannot reuse messages that were signed by $\MathAlgX{P}_k$ in other rounds).
        \item
        If $\MathAlgX{P}_k$ is corrupted, then in turn it must have provided a valid witness for the relation $\ensuremath{\mathcal{R}}\xspace_{k\to i}^{r'}$. By the minimality of $r$, it is guaranteed that $\tilde{m}_{k\to i}^{r'-1}$ was honestly generated \wrt the incoming messages of $\MathAlgX{P}_k'$ until round $r'-1$, $\sset{\bigcup \ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r'',k'\to k}}_{r''\in[r'-1], k'\in[n]}$. In this case, \wlg, the message $\tilde{m}_{k\to i}^{r'}$ could have been sent by the corrupted $\MathAlgX{P}_k'$ to the corrupted $\MathAlgX{P}_i'$, \ie be included in the set $\ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}$.
    \end{itemize}
\end{itemize}
The proof of the claim now reduces considering non-\ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries, which follows from \cref{claim:LC:rand}.
\end{proof}

The next claim considers stronger adversaries that are not required to compute their outgoing messages by the next-message function, but can send arbitrary messages instead.
\begin{claim}
Consider a perfect NIZK scheme.
If $\Pi_1$ is a $\left(t,\alpha,\beta,q,\gamma\right)$-\MathAlgX{BA} against locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries, then $\Pi'$ is a $\left(t,\alpha-\operatorname{neg}(\kappa),\beta-\operatorname{neg}(\kappa),q,\gamma-\operatorname{neg}(\kappa)\right)$-\MathAlgX{BA} against malicious adversaries.
\end{claim}
\begin{proof}
Consider a malicious adversary $\Ac} % {\Dc'$ and assume that $\Ac} % {\Dc'$ behaves locally consistent and \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant until round $r$, \ie round $r$ is the first round in which $\Ac} % {\Dc'$ does not compute a message according to the next-message function. Let $\MathAlgX{P}_i'$ be a corrupted party that generates the message content for party $\MathAlgX{P}_j'$ in round $r$, denoted $\tilde{m}_{i\to j}^r$, arbitrarily.
There are two possible cases:
\begin{itemize}
    \item[\textbf{Case 1:}]
    If $\tilde{m}_{i\to j}^r\in\ensuremath{\mathcal{M}_\mathsf{out}}\xspace^{r,i\to j}$, then the adversary can compute a witness for the relation $\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$. That is, the message $\tilde{m}_{i\to j}^r$ can be explained as if generated using $\sset{\rho_i^{r'}}_{r'\in[r]}$ consistently with a subset of the incoming messages in $\sset{\ensuremath{\mathcal{M}_\mathsf{in}}\xspace^{r',k\to i}}_{r'<r, k\in[n]}$ according to the next-message function. Therefore, \wlg this can be cast as a locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant attack.
    \item[\textbf{Case 2:}]
    If $\tilde{m}_{i\to j}^r\notin\ensuremath{\mathcal{M}_\mathsf{out}}\xspace^{r,i\to j}$, then $\Ac} % {\Dc'$ must provide $\tilde{\sigma}_{i\to j}^r$ and $\pi_i^r$ along with a witness $\mathsf{wit}_{i\to j}^r$ consisting of:
    \begin{itemize}
        \item
        An input bit $x_i$ an $\mathsf{setup}_i$.
        \item
        For every $r'\in[r]$ random coins $\rho_i^{r'}$.
        \item
        For every $r'\in[r-1]$ and $k\in[n]$ a message $\tilde{\vect{m}}_{k\to i}^{r'}=(\tilde{m}_{k\to i}^{r'},\tilde{\sigma}_{k\to i}^{r'},\pi_k^{r'},\tilde{\varphi}_{k\to i}^{r'})$.
    \end{itemize}
    In addition it holds that $((\tilde{m}_{i\to j}^r,\tilde{\sigma}_{i\to j}^r,\pi_i^r),\mathsf{wit}_{i\to j}^r)\in\ensuremath{\mathcal{R}}\xspace^r_{i\to j}$.
    As before, with all but negligible probability it is guaranteed that $\mathsf{VRF.Verify}(\mathsf{vk}^{\mathsf{vrf}}_i,(i,r),\rho_i^r,\pi_i^r)=1$ and for every honest party $\MathAlgX{P}_k'$, $((\tilde{m}_{k\to i}^{r'},\tilde{\sigma}_{k\to i}^{r'},\pi_k^{r'}),\tilde{\varphi}_{k\to i}^{r'})\in\ensuremath{\mathcal{R}}\xspace_{k\to i}^{r'}$. For a corrupted $\MathAlgX{P}_k'$, if $((\tilde{m}_{k\to i}^{r'},\tilde{\sigma}_{k\to i}^{r'},\pi_k^{r'}),\tilde{\varphi}_{k\to i}^{r'})\in\ensuremath{\mathcal{R}}\xspace_{k\to i}^{r'}$ then \wlg the message could have been sent by $\MathAlgX{P}_k'$ to $\MathAlgX{P}_i'$. We conclude that with all but negligible probability, the $\tilde{m}_{i\to j}^r$ can be explained by a locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant attack.
\end{itemize}
The proof of the claim now follows from \cref{claim:LC:messages}.
\end{proof}

Finally, we remove the assumption of a perfect NIZK scheme and consider a NIZK scheme that allows for negligible adversarial advantage, and obtain the following claim.
\begin{claim}
If $\Pi_1$ is a $\left(t,\alpha,\beta,q,\gamma\right)$-\MathAlgX{BA} against locally consistent \ensuremath{\mbox{\footnotesize{\textsf{VRF}}}}\xspace-compliant adversaries, then $\Pi'$ is a $\left(t,\alpha-\operatorname{neg}(\kappa),\beta-\operatorname{neg}(\kappa),q,\gamma-\operatorname{neg}(\kappa)\right)$-\MathAlgX{BA} against malicious adversaries.
\end{claim}
This concludes the proof of the first part of the theorem.

\paragraph{Proof of Item~\ref{thm:local_to_mal_PC} (public-randomness protocols).}
We prove Item~\ref{thm:local_to_mal_PC} of \cref{thm:local_to_malicious:Res} by adjusting the compiler $\mathsf{Comp}$ and removing the use of NIZK proofs. The new compiler $\comp_\mathsf{PR}$ is defined like $\mathsf{Comp}$ except that instead of computing a NIZK proof $\varphi_{i\to j}^r\gets\mathsf{NIZK.Prover}(\ensuremath{\mathsf{crs}}\xspace, \mathsf{stat}_{i\to j}^r, \mathsf{wit}_{i\to j}^r)$ for the relation $\ensuremath{\mathcal{R}}\xspace_{i\to j}^r$ and sending $\varphi_{i\to j}^r$, the sender $\MathAlgX{P}_i'$ simply sends the witness $\mathsf{wit}_{i\to j}^r$. The receiver $\MathAlgX{P}_j'$ can now directly verify that $\mathsf{wit}_{i\to j}^r$ is a valid witness. The proof follows immediately from Item~\ref{thm:local_to_mal_generic} of \cref{thm:local_to_malicious:Res}.
\end{proof}

\section{Our Lower Bounds}\label{sec:OurResult}

In this section, we formally state our lower bounds on the round complexity of Byzantine agreement protocols. The communication and adversarial models as well as the notion of Byzantine agreement protocols we consider are given in \cref{sec:OurResults:Model}, and our bounds are formally stated in \cref{sec:OurResult:Bounds}.

\subsection{The Model}\label{sec:OurResults:Model}

\subsubsection{Protocols}
All protocols considered in this paper are {\sc ppt}\xspace (probabilistic polynomial time): the running time of every party is polynomial in the (common) security parameter (given as a unary string). We only consider Boolean-input Boolean-output protocols: apart from the common security parameter, all parties have a single input bit, and each of the honest parties outputs a single bit. For an $n$-party protocol $\Pi$, an input vector $\vect{v}\in {\zo^n}$ and randomness $\vect{r}$, let $\Pi(\vect{v}; \vect{r})$ denote the output vector of the parties in an (honest) execution with party $\MathAlgX{P}_i$'s input being $\vect{v}_i$ and randomness $\vect{r}_i$.
For a set of parties $\mathcal{P} \subseteq [n]$, we denote by $\Pi(\vect{v}; \vect{r})_\mathcal{P}$ the output vector of the parties in $\mathcal{P}$.

The protocols we consider might have a \emph{setup phase} in which before interaction starts a trusted party distributes (correlated) values between the parties. We only require the security to hold for a \emph{single} use of the setup parameters (in reality, these parameters are set once and then used for many interactions). This, however, only makes our lower bound stronger.

The communication model is \emph{synchronous}, meaning that the protocols proceed in rounds. In each round every party can send a message to every other party over a private and authenticated channel. (Allowing the protocol to be executed over private channels makes our lower bounds stronger.) It is guaranteed that all of the messages that are sent in a round will arrive at their destinations by the end of that round.

\subsubsection{Adversarial Model}\label{sec:OurResults:Adv}

We consider both {\MathAlgX{adaptive}\xspace} and {\MathAlgX{non\mhyphen adaptive}\xspace} (\aka static) adversaries. An {\MathAlgX{adaptive}\xspace} adversary can choose which parties to corrupt for the next round immediately after the conclusion of the previous round but before seeing the next round's messages. If a party has been corrupted then it is considered corrupt for the rest of the execution. A {\MathAlgX{non\mhyphen adaptive}\xspace} (static) adversary chooses which parties to corrupt \emph{before} the execution of the protocol begins (\ie before the setup phase, if such exists). We measure the success probability of the latter adversaries as the expectation over their choice of corrupted parties.

We consider both \emph{rushing} and \emph{non-rushing} adversaries. A non-rushing adversary chooses the corrupted parties' messages in a given round based on the messages sent in the \emph{previous} rounds. In contrast, a rushing adversary can base the corrupted parties' messages on the messages sent in the previous rounds, and on those sent by the honest parties in the \emph{current} round.

\paragraph{Locally consistent adversaries.}
As discussed in \cref{sec:intro:model}, our attack requires very limited capabilities from each corrupted party: to prematurely abort, and to lie about its input bit and incoming messages from other corrupted parties. In particular, a corrupted party tosses its local coins honestly and does not lie about incoming messages from honest parties. We now present the formal definition.

\begin{definition}[locally consistent adversaries]\label{def:Semi-ConssitentParties}
Let $\Pi=(\mathsf{P}_1,\ldots,\mathsf{P}_n)$ be an $n$-party protocol and let $\sset{\alpha_{i,i'}^j}_{i,i' \in [n],j\in {\mathbb{N}}}$ be its set of next-message functions, \ie
\[
m^j_{i,i'}=\alpha_{i,i'}^j\left(b;r;(m^1_{1,i},\ldots,m^1_{n,i}),\ldots, (m^{j-1}_{1,i},\ldots,m^{j-1}_{n,i})\right)
\]
is the message party $\mathsf{P}_i$ sends to party $\mathsf{P}_{i'}$ in the \jth round, given that its input bit is $b$, the random coins it flipped till now are $r$, and in round $j' < j$, it got the message $m^{j'}_{i'',i}$ from party $\mathsf{P}_{i''}$. An adversary taking the role of $\mathsf{P}_i$ is said to be {\sf locally consistent} \wrt $\Pi$, if it \emph{flips its random coins honestly}, and the message it sends in the \jth round to party $\mathsf{P}_{i'}$ takes one of the following two forms:

\begin{description}
	\item[Abort:] the message $\perp$.

	\item[Input and message selection:] a set of messages $\set{m_\ell}_{\ell=1}^k$, for some $k$, such that for each $\ell \in [k]$:
\[
m_\ell = \alpha_{i,i'}^j\left(b_\ell;r;((m^1_{1})_\ell,\ldots,(m^1_{n})_\ell),\ldots, ((m^{j-1}_{1})_\ell,\ldots,(m^{j-1}_{n})_\ell)\right),
\]
where $b_\ell\in \{0,1\}$, $r$ are the coins $\mathsf{P}_i$ tossed (honestly) until now, and $(m^{j'}_{i''})_\ell$, for each $j'<j$ and $i''\neq i$, is one of the messages $\mathsf{P}_i$ received from party $\mathsf{P}_{i''}$ in the \iith{j} round (or the empty string).
\end{description}
\end{definition}
That is, a locally consistent party $\mathsf{P}_{i}$ might send party $\mathsf{P}_{i'}$ a sequence of messages
(and not just one as instructed), each consistent with a possible choice of its input bit, and some of the messages it received in the previous round. In turn, this will enable party $\mathsf{P}_{i'}$, if corrupted, the freedom to choose in the next rounds the message of $\mathsf{P}_{i}$ it would like to act according to. Note that \wlg, $\mathsf{P}_{i}$ will always send a single message to the honest parties, as otherwise they will discard the messages.

A few remarks are in place.
\begin{enumerate}
	\item While the above definition does not enforce between-rounds consistency (a party might send to another party a first-round message consistent with input $0$ and a second-round message consistent with input $1$), compiling a given protocol so that every message party $\mathsf{P}_{i}$ sends to $\mathsf{P}_{i'}$ contains the previous messages $\mathsf{P}_{i}$ sent to $\mathsf{P}_{i'}$, will enforce such between-rounds consistency on locally consistent parties.

	\item Although a locally consistent adversary tosses its random coins honestly, he may toss all random coins at the beginning of the protocol and choose its actions as a function of these coins. Our attacks in \cref{sec:FirstRound,sec:SecondRound} do not take advantage of this capability, and let the corrupted parties toss the random coins for a given round at the beginning of the round.

	\item Using standard cryptographic techniques, a protocol secure against locally consistent adversaries can be compiled into one secure against arbitrary malicious adversaries, without hurting the efficiency of the protocol ``too much,'' and in particular preserve the round complexity (see \cref{sec:intro:LocalToFull}).

	\item The locally consistent parties considered in \cref{sec:FirstRound,sec:SecondRound} do not take full advantage of the generality of \cref{def:Semi-ConssitentParties}. Rather, the parties considered either act honestly but abort at the conclusion of the first round, cheat in the first round and then abort, or cheat only in the second round and then abort.
\end{enumerate}

\subsubsection{Public-Randomness Protocols}\label{sec:OurResults:PR}
In \cref{sec:intro:model}, we showed that the description of many natural protocols can be simplified when security is required to hold only against locally consistent adversaries. In this relaxed description a trusted setup phase and cryptographic assumptions are not required, and every party can publish the coins it locally tossed in each round.

\begin{definition}[Public-randomness protocols]\label{def:PR}
A protocol has {\sf public randomness}, if every party's message consists of two parts: the randomness it sampled in that round, and an arbitrary message which is a function of its view (input, incoming messages, and coins tossed up to and including that point). The party's first message also contains its setup parameters, if such exist.
\end{definition}

\subsubsection{Byzantine Agreement}\label{sec:BA}

We now formally define the notion of Byzantine agreement. Since we focus on lower bounds we will consider only the case of a single input bit and a single output bit. A more general notion of Byzantine agreement will include string input and string outputs. A generic reduction shows that the cost of agreeing on strings rather than bits is two additional rounds~\cite{TC84}.

\begin{definition}[Byzantine Agreement]\label{def:BA}
We associate the following properties with a {\sc ppt}\xspace $n$-party Boolean input/output protocol $\Pi$.

\begin{description}
	\item[Agreement.] Protocol $\Pi$ has {\sf $(t,\alpha)$-\MathAlgX{agreement}}, if the following holds \wrt any {\sc ppt}\xspace adversary controlling at most $t$ parties in $\Pi$ and any value of the non-corrupted parties' input bits: in a random execution of $\Pi$ on sufficiently large security parameter, all non-corrupted parties output the \emph{same} bit with probability at least $1-\alpha$.\footnote{A more general definition would allow the parameter $\alpha$ (and the parameters $\beta,\gamma$ below) to depend on the protocol's security parameter. But in this paper we focus on the case that $\alpha$ is a fixed value.}

	\item[Validity.] Protocol $\Pi$ has {\sf $(t,\beta)$-\MathAlgX{validity}}, if the following holds \wrt any {\sc ppt}\xspace adversary controlling at most $t$ parties in $\Pi$ and an input bit $b$ given as input to all non-corrupted parties: in a random execution of $\Pi$ on sufficiently large security parameter, all non-corrupted parties output $b$ with probability at least $1-\beta$.

	\item[Halting.] Protocol $\Pi$ has {\sf $(t,q,\gamma)$-{\cal{S}}}, if the following holds \wrt any {\sc ppt}\xspace adversary controlling at most $t$ parties in $\Pi$ and any value of the non-corrupted parties' input bits: in a random execution of $\Pi$ on sufficiently large security parameter, all non-corrupted parties halt within $q$ rounds with probability at least $\gamma$.
\end{description}

\noindent
Protocol $\Pi$ is a $(t,\alpha,\beta,q,\gamma)$-\MathAlgX{BA}, if it has $(t,\alpha)$-\MathAlgX{agreement}, $(t,\beta)$-\MathAlgX{validity}, and $(t,q,\gamma)$-{\cal{S}}. If the protocol has a setup phase, then the above probabilities are taken \wrt this phase as well.
\end{definition}

\begin{remark}[Concrete security]
Since we care about fixed values of a protocol's characteristics (\ie agreement), the role of the security parameter in the above definition is to enable us to bound the running time of the parties and adversaries in consideration in a meaningful way, and to parametrize the cryptographic tools used by the parties (if there are any). Since the attacks we present are efficient assuming the protocol is efficient (in any reasonable sense), the bounds we present are applicable for a fixed protocol that might use a \emph{fixed} cryptographic primitive, \eg SHA-256.
\end{remark}

\subsection{The Bounds}\label{sec:OurResult:Bounds}
We proceed to present the formal statements of the three lower bounds.

\paragraph{First-round halting, arbitrary protocols.}
The first result bounds the halting probability of arbitrary protocols after a single round. Namely, for ``small'' values of $\alpha$ and $\beta$, the halting probability is ``small'' for $t\geq n/3$ and ``close to $1/2$'' for $t\geq n/4$.

\def\ThmFirstRoundArb
{
Let $\Pi$ be a {\sc ppt}\xspace $n$-party protocol that is $(t,\alpha,\beta,1,\gamma)$-\MathAlgX{BA} against locally consistent, static, non-rushing adversaries. Then,
\begin{itemize}
	\item $t \ge n/3$ implies $\gamma \le 5\alpha + 2\beta +\mathsf{err}$
	\item $t \ge n/4$ implies $\gamma \le 1/2 + 5\alpha + \beta + \mathsf{err}$,
\end{itemize}
for $\mathsf{err}= 2^{t-n}$ ($\mathsf{err}=0$ for public-randomness protocols whose security holds against rushing adversaries).
}
\begin{theorem}[restating \cref{thm:intro:FirstRound}]\label{thm:FirstRound:Arb}
	\ThmFirstRoundArb
\end{theorem}
\paragraph{Second-round halting, arbitrary protocols.}
The second result bounds the halting probability of arbitrary protocols after two rounds.

\def\ThmSecondRoundArb
{
Let $\Pi$ be a {\sc ppt}\xspace $n$-party protocol that is a $(t,\alpha,\beta,2,\gamma)$-\MathAlgX{BA} against locally consistent, static, non-rushing adversaries for $t > n/4$. Then $\gamma \le 1 + 2\alpha + \frac\beta{w^2} -\frac1{2w^2}$ for $w = \ceil{(n-\ceil{n/4})/\floor{t - n/4}}+1$.
}
\begin{theorem}[restating \cref{thm:intro:SecondRound:Arb}]\label{thm:SecondRound:Arb}
	\ThmSecondRoundArb
\end{theorem}

In particular, for $t = (1/4 + \varepsilon)\cdot n$ and ``small'' $\alpha$ and $\beta$, the protocol might not halt at the conclusion of the second round with probability $\approx 1/\varepsilon^2$.

\paragraph{Second-round halting, public-randomness protocols.}
The third result bounds the halting probability of public-randomness protocols after two rounds. The result requires adaptive and rushing adversaries, and is based on \cref{con:IsoBot} (stated in \cref{sec:Iso} below).

\newcommand{\eps_t}{\varepsilon_t}
\newcommand{\eps_\gamma}{\varepsilon_\gamma}

\def\ThmSeconRoundPR
{
Assume \cref{con:IsoBot} holds. Then, for any (constants) $\eps_t,\eps_\gamma>0$ there exists $\alpha> 0$ such that the following holds for large enough $n$: let $\Pi$ be a {\sc ppt}\xspace $n$-party, public-randomness protocol that is $(t,\alpha,\beta= \eps_\gamma^2/200,2,\gamma)$-\MathAlgX{BA} against locally consistent, rushing, adaptive adversaries. Then,
	\begin{itemize}
		\item $t \ge (1/3 + \eps_t)\cdot n$ implies $\gamma < \eps_\gamma$.
		\item $t \ge (1/4 + \eps_t)\cdot n$ implies $\gamma < \frac12 + \eps_\gamma$.
	\end{itemize}
}

\begin{theorem}[restating \cref{thm:intro:SecondRound:PR}] \label{thm:SecondRound:PR}
\ThmSeconRoundPR
\end{theorem}
In particular, assuming the protocol has perfect agreement and validity, the protocol never halts in two rounds if the fraction of corrupted parties is greater than $1/3$, and halts in two rounds with probability at most $1/2$ if the fraction of corrupted parties is greater than $1/4$.

The value of $\alpha$ in the theorem is (roughly) $\delta\cdot \eps_t\cdot \eps_\gamma^2$ where $\delta$ is the constant guaranteed by \cref{con:IsoBot}. We were not trying to optimize over the constants in the above statement, and in particular it seems that $\beta$ can be pushed to $\eps_\gamma^2$.

\section{Lower Bounds on Second-Round Halting}\label{sec:SecondRound}
In this section, we prove lower bounds for second-round halting of Byzantine agreement protocols. In \cref{sec:TwoRoundProtcol:Arbitrary}, we prove a bound for arbitrary protocols, and in \cref{sec:TwoRoundProtcol:PR}, we give a much stronger bound for public-randomness protocols (the natural extension of public-coin protocols to the 'with-input' setting).

\subsection{Arbitrary Protocols}\label{sec:TwoRoundProtcol:Arbitrary}
We start by proving our lower bound for second-round halting of arbitrary protocols.

\begin{theorem}[Bound on second-round halting, arbitrary protocols. \cref{thm:SecondRound:Arb} restated]\label{thm:SecondRound:Arb:Res}
\ThmSecondRoundArb
\end{theorem}

Let $\Pi$ be as in \cref{thm:SecondRound:Arb:Res}. We assume for ease of notation that an honest party that runs more than two rounds outputs $\perp$ (it will be clear that the attack, described below, does not benefit from this change). We also assume \wlg that the honest parties in an execution of $\Pi$ never halt in one round (by adding a dummy round if needed). Finally, we omit the security parameter from the parties' input list, it will be clear though that the adversaries we present are efficient \wrt the security parameter.

Let $k =\ceil{n/4}$ and let $h = \ceil{(n-k)/(t-k)}$. The theorem is easily implied by the next lemma.

\begin{lemma}[Neighboring executions]\label{lemma:SecondRound:Arb}
Let $\vect{v},\vect{v}' \in {\zo^n}$ be with $\mathrm{dist}(\vect{v},\vect{v}') \le k$. Then, for every $\o\in \{0,1\}$:
\[
\pr{\Pi(\vect{v}') = \o^n} \ge \pr{\Pi(\vect{v}) = \o^n} - h(h+1)(2\alpha + 1-\gamma) - \alpha.
\]
\end{lemma}
Namely, the lemma bounds from below the probability that in a random honest execution of the protocol on input $\vect{v}'$ all parties halt within two rounds while outputting $\o$.

We prove \cref{lemma:SecondRound:Arb} below, but first use it to prove \cref{thm:SecondRound:Arb:Res}. We also make use of the following immediate observation.
\begin{claim}[Almost pre-agreement]\label{claim:SecondRound:Arb:Validity}
Let $\vect{v} \in {\zo^n}$ and $\o \in \{0,1\}$ be such that $\mathrm{dist}(\vect{v},\o^n) \le t$. Then, $\pr{\Pi(\vect{v}) = \o^n } \ge 1 - \alpha - \beta - (1- \gamma)$.
\end{claim}
\begin{proof}
The same argument as in the proof of \cref{claim:FirstRoundound:Arb:Validity} yields that
\begin{align*}
\pr{\Pi(\vect{v}) \notin \set{\o,\bot}^n} < \alpha + \beta
\end{align*}
Thus, by $\gamma$-second-round halting
\begin{align*}
\pr{\Pi(\vect{v}) \ne \o^n} < \alpha + \beta + (1-\gamma)
\end{align*}
\end{proof}

\begin{proof}[Proof of \cref{thm:SecondRound:Arb:Res}]
Consider the vectors $\vect{v}_0= 0^k 0^k 0^k 1^{n-3k}$, $\vect{v}_1= 1^k 1^k 0^k 1^{n-3k}$ and $\mathbf{v}^{\star} =1^k 0^k 0^k 1^{n-3k}$. Note that for both $\o\in \{0,1\}$ it holds that $\mathrm{dist}(\vect{v}_b,\o^n)\le t$ since $n/4 \leq k\leq t$), and that $\mathrm{dist}(\vect{v}_b,\mathbf{v}^{\star})=k$. Applying \cref{lemma:SecondRound:Arb,claim:SecondRound:Arb:Validity} for each of these vectors, yields that for both $\o\in \{0,1\}$:
\begin{align*}
\pr{\Pi(\mathbf{v}^{\star}) = \o^n} &\ge 1- \alpha - \beta -(1- \gamma) - h(h+1)(2\alpha + 1-\gamma) -\alpha\\
&\ge 1- \beta - (h+1)^2(2\alpha + 1-\gamma).
\end{align*}
Note that $w=h+1$, which implies $\beta +w^2(2\alpha + 1-\gamma) \ge 1/2$, and the proof follows by a simple calculation.
\end{proof}

\subsubsection{Proving \cref{lemma:SecondRound:Arb}}
We assume for ease of notation that $\mathrm{dist}(\vect{v},\vect{v}')=k$ (rather than $\le k$) and let $\ell=t-k$. Assume for ease of notation that $h\cdot \ell = n-k $ (\ie no rounding), and for a $k$-size
subset of parties $\mathcal{P} \subset [n]$, let $ \mathcal{L}^\mathcal{P}_1,\dots,\mathcal{L}_h^\mathcal{P}$ be an arbitrary partition of ${\overline{\mathcal{P}}} = [n] \setminus \mathcal{P}$ into $\ell$-size
subsets. Consider the following family of protocols:

\newcommand{\Pi^\cP}{\Pi^\mathcal{P}}

{ \samepage
\begin{protocol}[$\Pi^\cP_{d}$]\label{prot:main:Arb} ~
\begin{description}
	\item [Parameters:] A subset $\mathcal{P}\subseteq [n]$ and an index $d\in (h)$.
	\item [Input:] Every party $\mathsf{P}_i$ has an input bit $v_i\in\{0,1\}$.

	\item [First round:] ~
	\begin{description}
		\item[Party $\mathsf{P}_i \in \mathcal{P}$.]
		If $d=0$ [resp.,\xspace $d=h$], act honestly according to $\Pi$ \wrt input bit~$v_i$ [resp.,\xspace $1-v_i$].
		Otherwise,
		\begin{enumerate}
			\item Choose random coins honestly (\ie uniformly at random).

			\item To each party in $\bigcup_{j \in \set{1,\ldots,d}} \mathcal{L}_j^\mathcal{P}$: send a message according to input $1-v_i$.

			\item To each party in $\bigcup_{j \in \set{d+1 ,\ldots, h}} \mathcal{L}_j^\mathcal{P}$: send a message according to input $v_i$ (real input).

			\item Send no messages to the other parties in $\mathcal{P}$.
		\end{enumerate}

		\item[Other parties.] Act according to $\Pi$.
	\end{description}

	\item [Second round:]~

	\begin{description}
		\item[Party $\mathsf{P}_i \in \mathcal{P}$.]
        If $d=0$ [resp.,\xspace $d=h$], act honestly according to $\Pi$ \wrt input bit~$v_i$ [resp.,\xspace $1-v_i$]; otherwise, abort.

		\item[Other parties.] Act honestly according to $\Pi$.
	\end{description}
\end{description}
\end{protocol}
}

Namely, the ``pivot'' parties in $\mathcal{P}$ gradually shift their inputs from their real input to its negation according to parameter $d$. Note that protocol $\Pi^\cP_{0}(\vect{v})$ is equivalent to an honest execution of protocol $\Pi(\vect{v})$, and $\Pi^\cP_{h}(\vect{v})$ is equivalent to an honest execution of $\Pi(\vect{v}')$, for $\vect{v}'$ being $\vect{v}$ with the coordinates in $\mathcal{P}$ negated. \cref{lemma:SecondRound:Arb} easily follows by the next claim about \cref{prot:main:Arb}. In the following we let $\delta = \pr{\Pi(\vect{v})_{\overline{\mathcal{P}}} = \o^{\size{{\overline{\mathcal{P}}}}}}$.

\newcommand{{d^\ast}}{{d^\ast}}
\begin{claim}\label{claim:SecondRound:Arb}
For any $k$-size
subset $\mathcal{P}\subset [n]$ and $d\in (h)$ it holds that
\[
\pr{\Pi^\cP_d(\vect{v})_{\overline{\mathcal{P}}} = \o^{\size{{\overline{\mathcal{P}}}}}} \ge \delta- d (h+1)(2\alpha + 1-\gamma)
\]
\end{claim}
We prove \cref{claim:SecondRound:Arb} below, but first use it to prove \cref{lemma:SecondRound:Arb}.
\begin{proof}[Proof of \cref{lemma:SecondRound:Arb}]
By \cref{claim:SecondRound:Arb},
\begin{align*}
\pr{\Pi^\cP_h(\vect{v})_{\overline{\mathcal{P}}} = \o^{\size{{\overline{\mathcal{P}}}}}} \ge \delta - h(h+1)(2\alpha + 1-\gamma)
\end{align*}
Since $\Pi^\cP_h(\vect{v})$ is just an honest execution of $\Pi(\vect{v}')$, by agreement
\begin{align*}
\pr{\Pi(\vect{v}') = \o^n} &\ge \delta - h(h+1)(2\alpha + 1-\gamma) - \alpha
\end{align*}
\end{proof}

\begin{proof}[Proof of \cref{claim:SecondRound:Arb}]
The proof is by induction on $d$. The base case $d=0$ holds by definition. Suppose for contradiction the claim does not hold, and let ${d^\ast}\in(h-1)$
be such that the claim holds for ${d^\ast}$ but not for ${d^\ast}+1$. Let $\gamma_d$ be the probability that all honest parties halt in the second round of a random execution of $\Pi^\cP_d(\vect{v})$. The assumption about ${d^\ast}$ yields that
\begin{align}\label{eq:main:Arb:01}
\pr{\Pi^\cP_{d^\ast}(\vect{v})_{\overline{\mathcal{P}}} = \o^{\size{{\overline{\mathcal{P}}}}}} \ge \delta- \beta- {d^\ast} (h+1)(2\alpha + 1-\gamma)
\end{align}
and
\begin{align}\label{eq:main:Arb:02}
\pr{\Pi^\cP_{{d^\ast}+1}(\vect{v})_{\overline{\mathcal{P}}} \in \{0,1\}^{\size{{\overline{\mathcal{P}}}}} \setminus \sset{\o^{\size{{\overline{\mathcal{P}}}}}}} > 1-\left(\delta - \beta - ({d^\ast}+1) (h+1)(2\alpha + 1-\gamma)\right)- (1-\gamma_d)
\end{align}

We note that for every $d\in (h)$
\begin{align}\label{eq:main:Arb:03}
\frac{1- \gamma_d}{h+1} \le 1-\gamma
\end{align}

Indeed, otherwise, the adversary that corrupts the parties in $\mathcal{P}$ and acts like $\Pi^\cP_d$ for a random $d\in (h)$, violates the $\gamma$-second-round-halting property of $\Pi$. We conclude that
\begin{align}\label{eq:main:Arb:1}
\lefteqn{\ppr{\vect{r}}{\Pi^\cP_{d^\ast}(\vect{v};\vect{r})_{\overline{\mathcal{P}}} = \o^{\size{{\overline{\mathcal{P}}}}} \qand \Pi^\cP_{{d^\ast}+1}(\vect{v};\vect{r})_{\overline{\mathcal{P}}} \in \{0,1\}^{\size{{\overline{\mathcal{P}}}}} \setminus \sset{\o^{\size{{\overline{\mathcal{P}}}}}}}}\\
& \ge 1 - \left(1- \ppr{\vect{r}}{\Pi^\cP_{d^\ast}(\vect{v};\vect{r})_{\overline{\mathcal{P}}} = \o^{\size{{\overline{\mathcal{P}}}}}} \right) - \left(1- \ppr{\vect{r}}{\Pi^\cP_{{d^\ast}+1}(\vect{v};\vect{r})_{\overline{\mathcal{P}}} \in (\{0,1\}^{\size{{\overline{\mathcal{P}}}}} \setminus \sset{\o^{\size{{\overline{\mathcal{P}}}}}}}\right)\nonumber\\
& > (h+1) (2\alpha + 1 - \gamma) - (1-\gamma_d) \nonumber\\
& \ge (h+1) 2\alpha,\nonumber
\end{align}
for $\vect{r}$ being the randomness of the parties. The first inequality is by \cref{eq:main:Arb:01,eq:main:Arb:02}, and the second one by \cref{eq:main:Arb:03}.

Consider the adversary that samples $d\gets (h)$, corrupts the parties in $\mathcal{P} \cup \mathcal{L}^\mathcal{P}_{d+1}$, and acts towards a uniform random subset of the honest parties according to $\Pi^\cP_d$ and to the remaining parties according to $\Pi^\cP_{d+1}$. \cref{eq:main:Arb:1} yields that the above adversary causes disagreement with probability larger than $(h+1) 2\alpha/2(h+1) = \alpha$. Since it corrupts at most $t$ parties, this contradicts the assumption about $\Pi$.
\end{proof}

\subsection{Public-Randomness Protocols}\label{sec:TwoRoundProtcol:PR}
We proceed to prove our lower bound for second-round halting of public-randomness protocols.

\begin{theorem}[Lower bound on second-round halting, public-randomness protocols. \cref{thm:SecondRound:PR} restated] \label{thm:SecondRound:PR:Res}
	\ThmSeconRoundPR
\end{theorem}

Assume \cref{con:IsoBot} holds. Let $\Pi$ be as in the theorem statement, and assume $\gamma= \eps_\gamma$ in the case $t \ge (1/3 +\eps_t)\cdot n$ and $\gamma= \tfrac{1}{2} + \eps_\gamma$ in the case $t \ge (1/4 +\eps_t)\cdot n$. Let $\lambda =\eps_\gamma /10$ and $\sigma= \eps_t/4$. Recall that $\bot_\mathcal{S}(\vect{x})$ is the string resulting by replacing all entries of $\vect{x}$ indexed by $\mathcal{S}$ with $\bot$.
\cref{con:IsoBot} yields that there exists $\delta>0$ such that the following holds for large enough $n$: let $\Sigma$ be a finite alphabet and let $\mathcal{A}_0,\mathcal{A}_1 \subset \sb^n$ be two sets such that for both $b\in \{0,1\}$:
\begin{align*
\ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \Sigma^n}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}_b} \ge \lambda} \ge 1-\delta.
\end{align*}

Then,
\begin{align}\label{eq:IsoBot}
\ppr{\vect{r}\gets \Sigma^n,\mathcal{S} \gets \mathbf{D}_{n,\sigma}}{\forall b\in \{0,1\}\colon \set{\vect{r},\bot_{\mathcal{S}}(\vect{r})} \cap \mathcal{A}_b \neq \emptyset} \ge \delta.
\end{align}

In the following we assume $\alpha = \min\set{\delta\lambda \eps_t/10, \beta}$ and derive a contradiction, yielding that the agreement error has to be larger than that.

Fix $n$ that is large enough for \cref{eq:IsoBot} to hold and that $\ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\size{{\cal{S}}} > 2\sigma n} = 2^{- \Theta(n\cdot \sigma^2)} \le \alpha$, \ie $n> \Theta((\log 1/\alpha)/\sigma^2)$. As in the proof of \cref{thm:SecondRound:Arb:Res}, we assume for ease of notation that an honest party that runs more than two round outputs $\perp$, and that the honest parties in $\Pi$ never halt in one round. We also omit the security parameter from the parties input list. We assume \wlg that in the first round, the parties flip
no coin, since such coins can be added to the setup parameter.

We use the following notation: the setup parameter and second-round randomness of the parties in $\Pi$ are identified with elements of $\mathcal{F}$ and $\mathcal{R}$, respectively. We denote by $f_i$ and $r_i$ the setup parameter and the second-round
randomness of party $\mathsf{P}_i$ in $\Pi$, and let $D_\F$ be the joint distribution of the parties' setup parameters (by definition, the joint distribution of the second-round randomness is the product distribution $\cR^n$). For $\vect{v} \in {\zo^n}$, $\vect{f}=(f_1,\ldots,f_n) \in \Supp(D_\F)$, and $\vect{r}=(r_1,\ldots,r_n) \in\cR^n$, let $\Pi(\vect{v};(\vect{f},\vect{r}))$ denote the execution of $\Pi$ in which party $\mathsf{P}_i$ gets input $v_i$, setup parameter $f_i$ and second-round randomness $r_i$. We naturally apply this notation for the variants of $\Pi$ considered in the proof.

For ${\cal{S}}\subseteq[n]$, let $\Pi^{\cal{S}}$ be the variant of $\Pi$ in which the parties in ${\cal{S}}$ halt at the end of the first round. Let $k = \ceil{{t-\eps_t \cdot n}}$ (\ie $k = \ceil{n/3}$ if $t\ge (1/3 + \eps_t)\cdot n$, and $k = \ceil{n/4}$ if $t\ge (1/4 + \eps_t)\cdot n$). The heart of the proof lies in the following lemma.

\begin{lemma}[Neighboring executions]\label{lemma:SecondRound:PR}
Let $\vect{v},\vect{v}' \in {\zo^n}$ be with $\mathrm{dist}(\vect{v},\vect{v}') \le k$, let $\o\in \{0,1\}$, and let ${\overline{\cS}} = [n] \setminus {\cal{S}}$.  Then, with probability at least $\gamma- 7\lambda- \frac{\alpha + \pr{\Pi(\vect{v}) \ne \o^n}}{\lambda}$ over $\vect{f} \gets D_\F$, it holds that
\begin{align*}
\ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \cR^n}{\Pi(\vect{v}';(\vect{f},\vect{r})) = \o^n \qand \Pi^{\cal{S}}(\vect{v}';(\vect{f},\vect{r}))_{\overline{\cS}} = \o^{\size{{\overline{\cS}}}} } \ge \lambda}\ge 1-\delta.
\end{align*}
\end{lemma}
Namely, in an execution of $\Pi(\vect{v}')$, all honest parties halt after two rounds and output $\o$, regardless of whether a random subset of parties aborts after the first round. \cref{lemma:SecondRound:PR} is proven in \cref{sec:lemma:SecondRound:PR}, but let us first use it to prove \cref{thm:SecondRound:PR}. We make use of the following immediate observation:
\begin{claim}[Almost pre-agreement]\label{claim:SecondRound:PR:Validity}
Let $\vect{v} \in {\zo^n}$ and $\o \in \{0,1\}$ be such that $\mathrm{dist}(\vect{v},\o^n) \le t$. Then, $\pr{\Pi(\vect{v}) \in \set{\o,\perp}^n } \ge 1 - \alpha - \beta $.
\end{claim}
\begin{proof}
The proof of this claim uses an identical argument as in the proof of \cref{claim:FirstRoundound:Arb:Validity}.
\remove{
Let $\mathcal{A} \subset [n]$ be a subset of size $n-t$ such that $\vect{v}_\mathcal{A} = \o^{\size{\mathcal{A}}}$. The claimed validity of $\Pi$ yields that
\begin{align*}
\ppr{\vect{r}}{\Pi(\vect{v};(\vect{f},\vect{r}))_\mathcal{A} \notin\set{\o,\bot}^{\size{\mathcal{A}}}} < \beta_\vect{f}(\vect{v}).
\end{align*}
Hence	by the claimed agreement,
\begin{align*}
\ppr{\vect{r}}{\Pi(\vect{v};(\vect{f},\vect{r})) \notin \set{\o,\bot}^n} < \alpha_\vect{f}(\vect{v}) + \beta_\vect{f}(\vect{v}).
\end{align*}
}
\end{proof}

\paragraph{Proving \cref{thm:SecondRound:PR}.}
\begin{proof}[Proof of \cref{thm:SecondRound:PR}]~
We separately prove the case $t \ge (1/3 + \eps_t)\cdot n$ and $t \ge (1/4 + \eps_t)\cdot n$.

\paragraph{The case $t \ge (1/3 + \eps_t)\cdot n$.}
Let $\vect{v}_0= 0^k 1^{\ceil{(n-k)/2}} 0^{\floor{(n-k)/2}} $ and let $\vect{v}_1= 1^k 1^{\ceil{(n-k)/2}} 0^{\floor{(n-k)/2}} $. Note that $\mathrm{dist}(\vect{v}_0,\vect{v}_1)=k$ and that for both $\o\in \{0,1\}$ it holds that $\mathrm{dist}(\vect{v}_b,\o^n) \le t$. We will use \cref{lemma:SecondRound:PR,claim:SecondRound:PR:Validity} to prove that $\Pi(\vect{v}_1) = 0^n$ with noticeable probability, contradicting the validity of the protocol.

Recall that, in this case, $\gamma = \eps_\gamma$, that $\lambda = \eps_\gamma/10$ and $\alpha,\beta \le \eps_\gamma^2/200 = \lambda^2/2$.  \cref{claim:SecondRound:PR:Validity} yields that for both $\o\in\{0,1\}$:
\begin{align}\label{eq:SecondRound:PR:1}
\pr{\Pi(\vect{v}_\o) \ne \overline{\o}^n }\ge \pr{\Pi(\vect{v}_\o) \in \set{\o,\perp}^n} \ge 1- \alpha - \beta \ge 1- \lambda^2
\end{align}
Applying \cref{lemma:SecondRound:PR} \wrt $\vect{v}_0$ and $\vect{v}_1$ and $b=0$, yields that with probability at least
\[
\gamma- 7\lambda- \frac{\alpha + \pr{\Pi(\vect{v}_0) \ne 0^n}}{\lambda} \geq 3\lambda- \lambda=2 \lambda
\]
over $\vect{f} \gets D_\F$, it holds that

\begin{align*}
\ppr{\vect{r}}{\Pi(\vect{v}_1;(\vect{f},\vect{r})) = 0^n}\ge \lambda
\end{align*}
and therefore
\begin{align*}
\pr{\Pi(\vect{v}_1) = 0^n}\ge 2 \lambda^2
\end{align*}
in contradiction to \cref{eq:SecondRound:PR:1}.

\paragraph{The case $t \ge (1/4 + \eps_t)\cdot n$.} Consider the vectors $\vect{v}_0= 0^k 0^k 0^k 1^{n-3k}$, $\vect{v}_1= 1^k 1^k 0^k 1^{n-3k}$ and $\mathbf{v}^{\star} =1^k 0^k 0^k 1^{n-3k}$. Note that for both $\o\in \{0,1\}$ it holds that $\mathrm{dist}(\vect{v}_\o,\o^n) \le t$ and that $\mathrm{dist}(\vect{v}_\o,\mathbf{v}^{\star})=k$. Applying \cref{lemma:SecondRound:PR,claim:SecondRound:PR:Validity} on $\vect{v}_b$ and $\mathbf{v}^{\star}$, for both $\o\in \{0,1\}$, yields that $\Pi^{\cal{S}}(\mathbf{v}^{\star}) = \o^n$ with noticeable probability over the choice of ${\cal{S}}$. This will allow us to use \cref{con:IsoBot} to lowerbound the protocol's agreement.

Recall that, in this case, $\gamma=1/2+\varepsilon_\gamma$. (Hence, $\lambda=20\gamma$.)
A similar calculation to the one in the previous case
yields that by \cref{lemma:SecondRound:PR,claim:SecondRound:PR:Validity}, for both $\o\in \{0,1\}$: with probability at least $\frac12 + 2\lambda$ over $\vect{f} \gets D_\F $ it holds that
\begin{align*}
\ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \cR^n}{\Pi(\mathbf{v}^{\star};(\vect{f},\vect{r})) = \o^n \qand \Pi^{\cal{S}}(\mathbf{v}^{\star};(\vect{f},\vect{r}))_{\overline{\cS}} = \o^{\size{{\overline{\cS}}}} } \ge \lambda}\ge 1-\delta.
\end{align*}
It follows that there exists a set $\mathcal{T} \subseteq \Supp(D_\F)$ with $\ppr{\vect{f} \gets D_\F}{\mathcal{T}}\ge 4\lambda$, such that for every $\vect{f}\in \mathcal{T}$, for \emph{both} $\o\in \{0,1\}$:
\begin{align}\label{eq:mainPR:4}
\ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \cR^n}{\Pi(\mathbf{v}^{\star};(\vect{f},\vect{r})) = \o^n \qand \Pi^{\cal{S}}(\mathbf{v}^{\star};(\vect{f},\vect{r}))_{\overline{\cS}} = \o^{\size{{\overline{\cS}}}} } \ge \lambda}\ge 1-\delta
\end{align}

We assume \wlg that if a party gets $\perp$ as its second-round random coins, it aborts after the first round. For $\vect{r} \in (\mathcal{R}\cup\sset{\bot})^n$ let $ \mathcal{E}(\vect{r})$ be the indices in $\vect{r}$ of the value $\bot$.
For $\vect{f} \in \Supp(D_\F)$ and $\o \in \{0,1\}$, let
\begin{align}
\mathcal{A}^\vect{f}_\o = \set{\vect{r} \in \set{\cR \cup \bot} \colon \Pi(\mathbf{v}^{\star};(\vect{f},\vect{r}))_{\overline{\mathcal{E}(\vect{r})}} = \o^{\size{\overline{\mathcal{E}(\vect{r})}}}}
\end{align}
By \cref{eq:mainPR:4}, for $\vect{f} \in \mathcal{T}$ and $\o\in \{0,1\}$, it holds that
\begin{align}
\ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \cR^n}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}^\vect{f}_\o} \ge\lambda} \ge 1-\delta
\end{align}
Hence by \cref{con:IsoBot}, see \cref{eq:IsoBot}, for $\vect{f} \in \mathcal{T}$ it holds that
\begin{align*}
\ppr{\vect{r}\gets \cR^n,\mathcal{S} \gets \mathbf{D}_{n,\sigma}}{\forall \o \in \{0,1\}\colon \set{\vect{r},\bot_{\mathcal{S}}(\vect{r})}\cap \mathcal{A}_b \neq \emptyset} > \delta.
\end{align*}
That is,
\begin{align}\label{eq:PR:3}
\ppr{\vect{r}\gets \mathcal{R}^n,\mathcal{S} \gets \mathbf{D}_{n,\sigma}}{\forall \o\in \{0,1\} \quad \exists {\cal{S}}_\o \in \set{{\cal{S}},\emptyset} \colon \Pi^{\mathcal{S}_\o}(\mathbf{v}^{\star};(\vect{f},\vect{r}))_{\overline{\mathcal{S}_\o}}= \o^{ \size{\overline{\mathcal{S}_\o}}}} >\delta
\end{align}

{\samepage
\noindent
Consider the following adversary:

\begin{algorithm}[$\MathAlgX{A}$]~
\begin{description}
	\item[Pre-interaction.]
	Corrupt a random subset $\mathcal{S} \gets \mathbf{D}_{n,\sigma} $ conditioned on $\size{{\cal{S}}} \le 2\sigma n$.

	\item[First round.] Act according to $\Pi$.
	\item[Second round.] Sample ${\cal{S}}_0,{\cal{S}}_1$ at random from $\set{\emptyset,{\cal{S}}}$, and act towards some honest parties according to $\Pi^{{\cal{S}}_0}$ and towards the others according to $\Pi^{{\cal{S}}_1}$ .
\end{description}
\end{algorithm}
}
Recall that $n$ is chosen so that $\ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\size{{\cal{S}}} >2\sigma n} \leq \alpha$ and that $\alpha < \delta/2$.
By \cref{eq:PR:3}, the above adversary violates the agreement of $\Pi$ on input $\mathbf{v}^{\star}$ with probability larger than $\delta - \ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\size{{\cal{S}}} >2\sigma n} \ge \delta - \alpha >\alpha$, in contradiction with the assumed agreement of $\Pi$.
\end{proof}

\newcommand{\cV^{\cP}}{\mathcal{V}^{\mathcal{P}}}
\renewcommand{\Pi^\cP}{\Pi^{\mathcal{P},\mathcal{S}}}
\newcommand{{\overline{\cP \cup \cS}}}{{\overline{\mathcal{P} \cup \mathcal{S}}}}

\subsubsection{Proving \cref{lemma:SecondRound:PR}}\label{sec:lemma:SecondRound:PR}
Fix $\vect{v},\vect{v} \in {\zo^n}$ and $b\in \{0,1\}$ as in the lemma statement. We assume for simplicity that $\mathrm{dist}(\vect{v},\vect{v}')=k$ (rather than $\le k$).
Let $\ell= \floor{(t -k)/2}$ and let $h = \ceil{(n-k)/\ell}$. Assume for ease of notation that $h\cdot \ell = n-k $ (\ie no rounding), and for a $k$-size subset of parties $\mathcal{P} \subset [n]$, let $ \mathcal{L}^\mathcal{P}_1,\dots,\mathcal{L}_h^\mathcal{P}$ be an arbitrary partition of ${\overline{\mathcal{P}}} = [n] \setminus \mathcal{P}$ into $\ell$-size subsets. Consider the following protocol family.

{ \samepage
\begin{protocol}[$\Pi^\cP_d$]\label{prot:main:2} ~
\begin{description}
    \item [Parameters:] subsets $\mathcal{P},\mathcal{S} \subseteq [n]$ and an index $d\in (h)$.
    \item [Input:] Party $\mathsf{P}_i$ has a setup parameter $f_i$ and an input bit $v_i$.

	\item [First round:] ~
	\begin{description}
		\item[Party $\mathsf{P}_i \in \mathcal{P}$.] ~
		If $d=0$ [resp.,\xspace $d=h$], act honestly according to  $\Pi$ \wrt input bit $v_i$ [resp.,\xspace $1-v_i$].
		Otherwise,
		\begin{enumerate}
			\item Choose random coins honestly (\ie uniformly at random).

			\item To each party in $\bigcup_{j \in \set{1,\ldots,d}} \mathcal{L}_j^\mathcal{P}$: send a message according to input $ 1-v_i$.

			\item To each party in $\bigcup_{j \in \set{d+1 ,\ldots, h}} \mathcal{L}_j^\mathcal{P}$: send a message according to input $v_i$ (real input).

			\item Send no messages to the other parties in $\mathcal{P}$.
		\end{enumerate}

		\item[Other parties.] Act according to $\Pi$.
	\end{description}

	\item [Second round:]~
	\begin{description}
		\item[Parties in $\mathcal{P} \setminus {\cal{S}}$.] If $d=0$ [resp.,\xspace $d=h$], act honestly according to $\Pi$ \wrt input bit $v_i$ [resp.,\xspace $1-v_i$]; otherwise, abort.

		\item[Parties in $\mathcal{S}$.] Abort.

		\item[Other parties.] Act according to $\Pi$.
	\end{description}
\end{description}
\end{protocol}
}
Namely, the ``pivot'' parties in $\mathcal{P}$ shift their inputs from their real input to the flipped one according to parameter $d$. The ``aborting'' parties in ${\cal{S}}$ abort at the end of the first round. Note that protocol $\Pi^\cP_{0}$ is the same as protocol $\Pi^{\cal{S}}$, and $\Pi^\cP_h(\vect{v})$ acts like $\Pi^{\cal{S}}(\vect{v}')$, for $\vect{v}'$ being $\vect{v}$ with the coordinates in $\mathcal{P}$ flipped.

For $\mathcal{P}, \mathcal{S} \subseteq [n]$, let ${\overline{\cP \cup \cS}} = [n] \setminus (\mathcal{P} \cup {\cal{S}})$, let $d\in (h)$, let $c\in \{0,1\}$, and let
\[
\cV^{\cP}_{d,c} = \set{(\vect{f},{\cal{S}},\vect{r}) \colon \quad \Pi^\cP_d(\vect{v};(\vect{f},\vect{r}))_{\overline{\cP \cup \cS}} = c^{\size{{\overline{\cP \cup \cS}}}}}
\]
Namely, $\cV^{\cP}_{d,c}$ are the sets, setup parameters and random strings on which honest parties in $\Pi^\cP_{d}$ halt in the second round and output $c$. Let $\chi = \pr{ \Pi(\vect{v}) \ne \o^n}$ and let
\[
\mathcal{T}_{d,c}^\mathcal{P} = \set{\vect{f} \colon \ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \cR^n}{(\vect{f},\mathcal{S},\vect{r}),(\vect{f},\emptyset,\vect{r}) \in \cV^{\cP}_{d,c} } \ge \lambda } \ge 1-\delta}
\]
The proof of  \cref{lemma:SecondRound:PR} immediately follows by the next lemma.
\begin{lemma}\label{lemma:SecondRound:PRR}
For every $k$-size subset $\mathcal{P} \subset [n]$ and $d\in [h]$,
it holds that
\begin{align*}
\ppr{ D_\F}{\mathcal{T}_{d,\o}^\mathcal{P}} \ge \gamma- 7\lambda- \frac{\chi + \alpha }{\lambda}
\end{align*}
\end{lemma}
\begin{proof}[Proof of \cref{lemma:SecondRound:PR}]
Immediate by \cref{lemma:SecondRound:PRR}.
\end{proof}
\newcommand{\widetilde{\cV}}{\widetilde{\mathcal{V}}}
\newcommand{{\widetilde{\cT}}}{{\widetilde{\mathcal{T}}}}

The rest of this subsection is devoted for proving \cref{lemma:SecondRound:PRR}. Fix a $k$-size subset $\mathcal{P} \subset [n]$ and omit it from the notation when clear from the context.
Let
\[
\widetilde{\cV}_{d,c} = \set{(\vect{f},{\cal{S}},\vect{r}) \colon \forall a\in \{0,1\} \quad \Pi^\cP_{d+a}(\vect{v};(\vect{f},\vect{r}))_{\overline{\cP \cup \cS}} = c^{\size{{\overline{\cP \cup \cS}}}}}
\]
Namely, $\widetilde{\cV}_{d,c} \subseteq \mathcal{V}_{d,c}$ are the sets, setup parameters and random strings, on which honest parties in $\Pi^\cP_{d+a}$ halt in the second round and output $c$, \emph{regardless} whether the parties in $\mathcal{S}$ abort \emph{and} whether the parties in $\mathcal{P}$ act toward those in $\mathcal{L}_{d+1}$ according to input $0$ or $1$.
Let
\[
{\widetilde{\cT}}_{d,c} = \set{\vect{f} \colon \ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \cR^n}{(\vect{f},\mathcal{S},\vect{r}),(\vect{f},\emptyset,\vect{r}) \in \widetilde{\cV}_{d,c} } \ge \lambda} \ge 1-\delta},
\]
let ${\widetilde{\cT}}_{d} = {\widetilde{\cT}}_{d,0}\cup {\widetilde{\cT}}_{d,1}$, and let ${\widetilde{\cT}} = \bigcap_{i \in (h-1)}{\widetilde{\cT}}_{d}$. \cref{lemma:SecondRound:PRR} is proved via the following claims (the following probabilities are taken over $\vect{f} \gets D_\F$).

\begin{claim}\label{claim:PR:0}
$\pr{\mathcal{T}_{d+1,\o} \mid {\widetilde{\cT}}} < \eta$ implies $\pr{\mathcal{T}_{d,\overline{\o}} \mid {\widetilde{\cT}}} \ge 1- \eta$.
\end{claim}
\begin{proof}[Proof of \cref{claim:PR:0}]
By definition, $\pr{{\widetilde{\cT}}_{d+1} \mid {\widetilde{\cT}}} =1$.	 Hence, $\pr{{\widetilde{\cT}}_{d+1,\o} \mid {\widetilde{\cT}}}< \eta$ implies $\pr{{\widetilde{\cT}}_{d+1,\overline{\o}} \mid {\widetilde{\cT}}}> 1 -\eta$, and the latter implies that $\pr{\mathcal{T}_{d,\overline{\o}} \mid {\widetilde{\cT}}}>  1 -\eta$.
\end{proof}

\begin{claim}\label{claim:PR:00}
$\pr{{\widetilde{\cT}}} \ge \gamma- 6\lambda$.
\end{claim}

\begin{claim}\label{claim:PR:01}
$\pr{\mathcal{T}_{1,\o} \mid {\widetilde{\cT}}} \ge 1- (\chi + \alpha)/(\Pr[{\widetilde{\cT}}]\cdot \lambda)$.
\end{claim}

\begin{claim}\label{claim:PR:1}
For every $d \in [h-1]$.
\[
\pr{\mathcal{T}_{d,0} \mid {\widetilde{\cT}}} + \pr{\mathcal{T}_{d,1} \mid {\widetilde{\cT}}} \le 1 + \frac{\lambda}{h\cdot\Pr[{\widetilde{\cT}}]}
\]
\end{claim}

We prove \cref{claim:PR:00,claim:PR:01,claim:PR:1} below, but first use the above claims for proving \cref{lemma:SecondRound:PR}.

\paragraph{Proving \cref{lemma:SecondRound:PRR}.}

\begin{proof}[Proof of \cref{lemma:SecondRound:PRR}.]
We first prove that for every $d\in [h]$:
\begin{align}\label{eq:SecondRound:PRR}
\pr{\mathcal{T}_{d,\o} \mid {\widetilde{\cT}}} \ge 1- \frac{ \chi + \alpha}{\Pr[{\widetilde{\cT}}]\cdot \lambda} - \frac{d\lambda}{h\cdot\Pr[{\widetilde{\cT}}]}
\end{align}
The proof is by induction on $d$. The base case, $d=1$, is by \cref{claim:PR:01}. The induction steps follows by the combination of \cref{claim:PR:0,claim:PR:1}. Applying \cref{eq:SecondRound:PRR} for $d=h$, yields that
\begin{align*}
\pr{\mathcal{T}_{h,\o} } \ge \Pr[{\widetilde{\cT}}]- \frac{ \chi +\alpha}{\lambda} - \lambda,
\end{align*}
and the proof follows by \cref{claim:PR:00}.
\end{proof}

\newcommand{\Pi^{\cS}}{\Pi^{\mathcal{S}}}

So it is left to prove \cref{claim:PR:00,claim:PR:01,claim:PR:1}. Note that the following adversaries corrupt at most $k + \ell + 2\sigma n \le t$ and thus they make a valid attack. Since our security model consider rushing adversaries, and $\Pi$ has
pubic randomness, we assume the adversary knows $\vect{f} = (f_1,\ldots,f_n)$ \emph{before} sending its first-round messages. In the following we let $\Pi^{\cS}_d = \Pi^\cP_d$ and $\Pi_d = \Pi^{\emptyset}_d$.
\paragraph{Proving \cref{claim:PR:00}.}
This is the only part in proof where we exploit the fact that the protocol is secure against \emph{adaptive} adversaries.
\begin{proof}[Proof of \cref{claim:PR:00}.]

Consider the following \emph{rushing adaptive} adversary.

{ \samepage
\begin{algorithm}[$\MathAlgX{A}$]\label{alg:PR:00}~

\begin{description}

\item[Pre interaction:]~
Corrupt the parties in $\mathcal{P}$.

\item[First round.] ~
Let $\vect{f}$ be the parties' setup parameters.

Do $1/\lambda\delta$ times:
\begin{enumerate}
	\item  Sample  $\mathcal{S} \gets \mathbf{D}_{n,\sigma} $ conditioned on $ \size{{\cal{S}}} \le 2\sigma n$.
	\item  	For each   $i\in (h-1)$: estimate $\xi_i =  \ppr{\vect{r} \gets \cR^n}{(\vect{f},{\cal{S}},\vect{r}),(\vect{f},\emptyset,\vect{r})  \in \widetilde{\cV}_{i}}$ by taking $\Theta( \log (h/ \lambda))$ samples of $\vect{r}$.

	\item Let $d = \operatorname*{argmin}_{i\in (h-1)} \set{\xi_i}$.

	\item If $\xi_d < 2\lambda$, break the loop.
\end{enumerate}

Corrupt the parties in ${\cal{S}} \cup \mathcal{L}_{d+1}$ (${\cal{S}}$ is the set sampled in the last loop), and act according to $\Pi_d$.

\item[Second round.]~

Let $\vect{r}$ be the parties' second-round randomness.

If $(\vect{f},\emptyset,\vect{r}) \notin \mathcal{V}_{d+a}$ for some $a\in \{0,1\}$,

\quad act according to $\Pi_{d+a}$.

Else,

\quad Let $a\in \{0,1\}$ be such that $(\vect{f},{\cal{S}},\vect{r}) \notin \mathcal{V}_{d+a}$, set to $0$ if no such value exists.

\quad Act according to $\Pi^{{\cal{S}}}_{d+a}$.
\end{description}
\end{algorithm}
}

Let $D$ be the value of $d$ chosen by the adversary $\MathAlgX{A}$ (at the first round of the protocol).
Since $\ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{ \size{{\cal{S}}} > 2\sigma n} \le \alpha < \delta/2$,
if $\vect{f} \notin {\widetilde{\cT}}$ then except with probability $\lambda$ it holds that $\xi_D \le 2\lambda$. Where if $\xi_D \le 2\lambda$, then in the interaction with $\MathAlgX{A}$ the honest parties both halt in the second round and output the same value with probability at most $5\lambda$. Where since $\alpha < \lambda$, the honest parties halt in the second round of such interaction with probability smaller than $6\lambda$. We conclude that the honest parties halt in the second round under the above attack with probability smaller than $\Pr[{\widetilde{\cT}}] + \Pr[\neg {\widetilde{\cT}}]\cdot 6\lambda \le \Pr[{\widetilde{\cT}}] + 6\lambda$, yielding that $\Pr[{\widetilde{\cT}}] > \gamma- 6\lambda$.
\end{proof}

\paragraph{Proving \cref{claim:PR:01}.}

\newcommand{{\overline{\cH}}}{{\overline{{\cal{H}}}}}

\begin{proof}[Proof of \cref{claim:PR:01}.]
By definition, for $\vect{f} \in \mathcal{T}_{1,\o}$ it holds that
\begin{align*}
\ppr{\vect{r} \gets \cR^n}{\Pi_1(\vect{v};(\vect{f},\vect{r}))_{\overline{\cH}} = \overline{\o}^{\size{{\overline{\cH}}}} } = \ppr{\vect{r} \gets \cR^n}{(\vect{f},\emptyset,\vect{r}) \in \mathcal{V}_{1,\overline{\o}} } \ge \lambda,
\end{align*}
letting ${\cal{H}} = \mathcal{P} \cup \mathcal{L}_1$ and ${\overline{\cH}} = [n] \setminus{\cal{H}}$. Let $\eta = \ppr{\vect{f}}{\mathcal{T}_{1,\overline{\o}} \mid {\widetilde{\cT}}}$, clearly,	$\ppr{\vect{f}}{\mathcal{T}_{1,\o} \mid {\widetilde{\cT}}} = 1 -\eta$. By the above
\begin{align}
 \pr{\Pi_1(\vect{v})_{\overline{\cH}} = \overline{\o}^{\size{{\overline{\cH}}}}} \ge \Pr[{\widetilde{\cT}}]\cdot \eta \cdot \lambda
\end{align}
(recall that $\Pi_1(\vect{v})$ stands for $\Pi_1(\vect{v};(\vect{f},\vect{r}))$, for a random choice of $(\vect{f},\vect{r}))$).
Finally, we notice that
\begin{align}
\pr{\Pi_1(\vect{v}) = \overline{\o}^{\size{{\cal{H}}}}} + \pr{\Pi(\vect{v}) = \o^n} \le 1+ \alpha
\end{align}

Otherwise, the adversary corrupting the parties in ${\cal{H}}$, and acting toward the first honest parties according to $\Pi$ and toward the rest according to $\Pi_1$ violates the $\alpha$-agreement of $\Pi$. We conclude that $\Pr[{\widetilde{\cT}}]\cdot \eta \cdot \lambda \le \chi + \alpha $, and therefore $\eta \le (\chi + \alpha)/(\Pr[{\widetilde{\cT}}]\cdot \lambda)$.
\end{proof}

\paragraph{Proving \cref{claim:PR:1}.}

The proof uses \cref{con:IsoBot} in a similar way to the second part of the proof of the theorem.

\begin{proof}[Proof of \cref{claim:PR:1}.]
For $\vect{r} \in (\mathcal{R}\cup\sset{\bot})^n$ let $ \mathcal{E}(\vect{r})$ be the indices in $\vect{r}$ of the value $\bot$.
We assume \wlg that a party aborts upon getting $\perp$ as its second round random coins. For $\vect{f} \in \Supp(D_\F)$, for $d\in [h-1]$, and for $\o \in \{0,1\}$, let
\begin{align}
\mathcal{A}^\vect{f}_\o = \set{\vect{r} \in \set{\cR \cup \bot} \colon \Pi_d(\vect{v};(\vect{f},\vect{r}))_{\overline{\mathcal{P} \cup \mathcal{L}_d \cup \mathcal{E}(\vect{r})}} = \o^{\size{\overline{\mathcal{P} \cup \mathcal{L}_d \cup \mathcal{E}(\vect{r})}}}}
\end{align}
By definition, for $\vect{f} \in \mathcal{T}_{d,0} \cap \mathcal{T}_{d,1}$ and $\o\in \{0,1\}$, it holds that
\begin{align}
\ppr{{\cal{S}}\gets \mathbf{D}_{n,\sigma}}{\ppr{\vect{r} \gets \cR^n}{\vect{r},\bot_{\mathcal{S}}(\vect{r}) \in \mathcal{A}^\vect{f}_\o} \ge \lambda} \ge 1-\delta
\end{align}
By \cref{con:IsoBot}, see \cref{eq:IsoBot}, for $\vect{f} \in \mathcal{T}_{d,0} \cap \mathcal{T}_{d,1}$ it holds that
\begin{align*
\ppr{\vect{r}\gets \cR^n,\mathcal{S} \gets \mathbf{D}_{n,\sigma}}{\forall \o \in \{0,1\} \colon \set{\vect{r},\bot_{\mathcal{S}}(\vect{r})}\cap \mathcal{A}^f_b \neq \emptyset} > \delta
\end{align*}
That is,
\begin{align}\label{eq:PR:1:4}
\ppr{\vect{r}\gets \mathcal{R}^n,\mathcal{S} \gets \mathbf{D}_{n,\sigma}}{\forall \o\in \{0,1\} \quad \exists {\cal{S}}_\o \in \set{{\cal{S}},\emptyset} \colon \Pi^{\mathcal{S}_\o}_{d}(\vect{v};(\vect{f},\vect{r}))_{ \overline{\mathcal{P} \cup \mathcal{L}_d \cup\mathcal{S}_\o} }= \o^{ \size{\overline{ \mathcal{P} \cup \mathcal{L}_d \cup\mathcal{S}_\o}}}} >\delta
\end{align}
In pursuit of contradiction, assume that $\pr{\mathcal{T}_{d,0} \mid {\widetilde{\cT}}} + \pr{\mathcal{T}_{d,1} \mid {\widetilde{\cT}}} \ge 1 + \lambda/(h\cdot \Pr[{\widetilde{\cT}}])$ for some $d \in [h-1]$. It follows that
\begin{align}\label{eq:PR:1:5}
\lefteqn{\ppr{\stackrel{\vect{f} \gets D_\F}{\vect{r}\gets \mathcal{R}^n,\mathcal{S} \gets \mathbf{D}_{n,\sigma}}}{\forall \o\in \{0,1\} \quad \exists {\cal{S}}_\o \in \set{{\cal{S}},\emptyset}\colon \Pi^{ {\cal{S}}_\o}_{d}(\vect{v};(\vect{f},\vect{r}))_{ \overline{\mathcal{P} \cup \mathcal{L}_d \cup {\cal{S}}_\o} }= \o^{ \size{\overline{ \mathcal{P} \cup \mathcal{L}_d \cup {\cal{S}}_\o}}}}}\\
&> \pr{\mathcal{T}_{d,0} \cap \mathcal{T}_{d,1}}\cdot \delta \hskip30em \nonumber\\
&\ge \Pr[{\widetilde{\cT}}]\cdot \Pr[\mathcal{T}_{d,0} \cap \mathcal{T}_{d,1} \mid {\widetilde{\cT}}] \cdot \delta \nonumber\\
&\ge \Pr[{\widetilde{\cT}}]\cdot \frac{\lambda}{h\cdot \Pr[{\widetilde{\cT}}]} \cdot \delta \nonumber\\
&= \lambda\delta /h \nonumber\\
&> 8\alpha.\nonumber
\end{align}
The first inequality is by \cref{eq:PR:1:4}, the second one by the assumption that $\Pr[\mathcal{T}_{d,0} \mid {\widetilde{\cT}}] + \Pr[\mathcal{T}_{d,1} \mid {\widetilde{\cT}}] \ge 1 + \lambda/(h\cdot \Pr[{\widetilde{\cT}}])$, and the last one by the definition of $\alpha$.

{\samepage
\noindent
Consider the following rushing adversary:

\begin{algorithm}[$\MathAlgX{A}$]~

\begin{description}
\item[Pre-interaction.] ~

	\begin{enumerate}
		\item For each $i\in [h-1]$, estimate

		\[
        \xi_i = \ppr{\vect{r}\gets \mathcal{R}^n,\mathcal{S} \gets \mathbf{D}_{n,\sigma}}{\forall \o\in \{0,1\} \quad \exists {\cal{S}}_\o \in \set{{\cal{S}},\emptyset} \colon \Pi^{{\cal{S}}_\o}_{d}(\vect{v};(\vect{f},\vect{r}))_{\overline{ \mathcal{P} \cup \mathcal{L}_d \cup {\cal{S}}_\o}}= \o^{ \size{\overline{ \mathcal{P} \cup \mathcal{L}_d \cup {\cal{S}}_\o}}}}
         \]
         by taking $\Theta(\log (h/\alpha)/\alpha$ samples. Let $d = \operatorname*{argmax}_{i\in [h-1]}\set{\xi_i}$.

		\item Sample a random $\mathcal{S} \gets \mathbf{D}_{n,\sigma} $ conditioned on $\size{{\cal{S}}} \le 2\sigma n$.
	\end{enumerate}

	 Corrupt the parties in $\mathcal{P} \cup \mathcal{S}\cup \mathcal{L}_d$.

	\item[First round.] Act according to $\Pi_d$.

	\item[Second round.] Sample ${\cal{S}}_0,{\cal{S}}_1$ at random from $\set{\emptyset,{\cal{S}}}$, and act towards some honest parties according to $\Pi^{{\cal{S}}_0}_{d,0}$ and towards the others according to $\Pi^{{\cal{S}}_1}_{d,1}$ .
\end{description}
\end{algorithm}
}
By \cref{eq:PR:1:5} and since $\ppr{{\cal{S}} \gets \mathbf{D}_{n,\sigma}}{{\cal{S}} \ge 2\sigma n} \le \alpha$, the above adversary violates the agreement of $\Pi$ on input $\vect{v}$ with probability larger than $\alpha$, contradicting the assumed agreement of $\Pi$.
\end{proof}

\section{Our Techniques}\label{sec:Technique}
In this section, we outline our techniques for proving our results. We start with explaining our bound for first-round halting of arbitrary protocols (\cref{thm:intro:FirstRound}). We then move to second-round halting, starting with the weaker bound for arbitrary protocols (\cref{thm:intro:SecondRound:Arb}), and then move to the much stronger bound for public-randomness protocols (\cref{thm:intro:SecondRound:PR}).

\paragraph{Notations.
We use calligraphic letters to denote sets, uppercase for random variables, lowercase for values, boldface for vectors, and sans-serif (\eg \MathAlgX{A}) for algorithms (\ie Turing Machines).
For $n\in{\mathbb{N}}$, let $[n]=\set{1,\cdots,n}$ and $(n)=\set{0,1,\cdots,n}$. Let $\mathrm{dist}(x, y)$ denote the hamming distance between $x$ and $y$. For a set $\mathcal{S} \subseteq [n]$ let ${\overline{\cS}} = [n]\setminus \mathcal{S}$. For a set $\mathcal{R}\subseteq \{0,1\}^n$, let $\mathcal{R}|_{\mathcal{S}}=\sset{\vect{x}_\mathcal{S} \in \{0,1\}^{\size{\mathcal{S}}}\text{ s.t.\ } \vect{x}\in \mathcal{R}}$, \ie $\mathcal{R}|_{\mathcal{S}}$ is the projection of $\mathcal{R}$ on the index-set $\mathcal{S}$.

Fix an $n$-party randomized BA protocol $\Pi = (\mathsf{P}_1,\ldots,\mathsf{P}_n)$. For presentation purposes, we assume that
validity and agreement
hold \emph{perfectly}, and consider no setup parameters (in the subsequent sections, we remove these assumptions). Furthermore, we only address here the case where the security threshold is $t>n/3$. The case $t>n/4$ requires an additional generic step that we defer to the technical sections of the paper. We denote by $\Pi(\vect{v};\vect{r})$ the output of an honest execution of $\Pi$ on input $\vect{v} \in {\zo^n}$ and randomness $\vect{r}$ (each party $\MathAlgX{P}_i$ holds input $v_i$ and randomness $r_i$). We let $\Pi(\vect{v})$ denote the resulting random variable determined by the parties' random coins, and we write $\Pi(\vect{v}) =\o$ to denote the event that the parties output $\o$ in an honest execution of $\Pi$ on input $\vect{v}$. All corrupt parties described below are locally consistent (see \cref{sec:intro:model}).

\subsection{First-Round Halting}\label{sec:technique:1}
Assume the honest parties of $\Pi$ halt at the end of the first round with probability $\gamma>0$ when facing $t$ corruptions (on every input).
Our goal is to upperbound the value of $\gamma$. Our approach is inspired by the analogous lower-bound for deterministic protocols (cf.,\xspace \cite{FL82,DS83}). Namely, we start with a configuration in which validity assures the common output is $0$, and, while maintaining the same output, we gradually adjust it into a configuration in which validity assures the common output is $1$, thus obtaining a contradiction. For randomized protocols, the challenge is to maintain the invariant of the output, even when the probability of halting is far from $1$. We make the following observations:

\begin{align} \label{eq:maj}
&\text{Almost pre-agreement:} \quad \mathrm{dist}(\vect{v},\o^n) \le t \implies \Pi(\vect{v})=\o.
\end{align}
That is, in an honest execution of $\Pi$, if the parties almost start with preagreement, \ie with at least $n-t$ of $\o$'s in the input vector,
then the parties output $\o$ with probability $1$. \cref{eq:maj} follows from \emph{agreement} and \emph{validity} by considering an adversary corrupting exactly those parties with input $v_i\neq b$, and otherwise not deviating from the protocol.

\begin{align}\label{eq:nei}
&\text{Neighboring executions (N1):} \quad \mathrm{dist}(\vect{v}_0,\vect{v}_1)\le t \implies \ppr{\vect{r}}{\Pi(\vect{v}_0;\vect{r})=\Pi(\vect{v}_1;\vect{r})}\ge \gamma.
\end{align}
That is, for two input vectors that are at most $t$-far (\ie the resiliency threshold), the probability that the executions on these vectors yield the same output when using the same randomness is bounded below by the halting probability. To see why \cref{eq:nei} holds, consider the following adversary corrupting subset $\mathcal{C}$, for $\mathcal{C}$ being the set of indices where $\vect{v}$ and $\vect{v}'$ disagree. For an arbitrary partition $\sset{\overline{\cC}_0,\overline{\cC}_1}$ of $\overline{\cC}$, the adversary instructs $\mathcal{C}$ to send messages according to $\vect{v}_0$ to $\overline{\cC}_0$ and according to $\vect{v}_1$ to $\overline{\cC}_1$, respectively. With probability at least $\gamma$, all parties halt at the first round, and, by perfect agreement, all parties compute the same output.\footnote{In the above, we have chosen to ignore a crucial subtlety. In an execution of the protocol, it may be the case that there is a suitable message (according to $\vect{v}_0$ or $\vect{v}_1$) to prevent halting, yet the adversary cannot determine which one to send. In further sections, we address this issue by taking a random partition of $\overline{\cC}$ (rather than an arbitrary one). By doing so, we introduce an error-term of $1/2^{n-t}$ when we upper bound the halting probability $\gamma$.} Since parties in $\overline{\cC}_\o$ cannot distinguish this execution from a halting execution of $\Pi(\vect{v}_\o;\vect{r})$, \cref{eq:nei} follows.

We deduce that if there are more than $n/3$ corrupt parties, then the halting probability is $0$; this follows by combining the two observations above for $\vect{v}_0=0^{n-t}1^{t}$ and $\vect{v}_1=0^{t}1^{n-t}$. Namely, by \cref{eq:maj}, it holds that $\ppr{\vect{r}}{\Pi(\vect{v}_0;\vect{r})=\Pi(\vect{v}_1;\vect{r})}=0$. Thus, by \cref{eq:nei}, $\gamma=0$.

\subsection{Second-Round Halting -- Arbitrary Protocols}\label{sec:technique:2}

We proceed to explain our bound for second-round halting of arbitrary protocols. Assume the honest parties of $\Pi$ halt at the end of the second round with probability $\gamma>0$ when facing $t$ corruptions (on every input). Let $t=(1/3+\varepsilon)\cdot n$, for an arbitrary small constant $\varepsilon>0$. In spirit, the attack follows the footsteps of the single-round case described above; we show that neighboring executions compute the same output with good enough probability (related to the halting probability), and lower-bound the latter using the \emph{almost pre-agreement}
observation. There is, however, a crucial difference between the first-round and second-round cases; the honest parties can use the second round to detect whether (some) parties are sending inconsistent messages. Thus, the second round of the protocol can be used to ``catch-and-discard'' parties that are pretending to have different inputs to different parties, and so our previous attack breaks down. (In the one-round case, we exploit the fact that the honest parties cannot verify the consistency of the messages they received.) Still, we show that there is a suitable variant of the attack that violates the agreement of any ``too-good'' scheme.

At a very high level, the idea for proving the \emph{neighboring} property is to \emph{gradually} increase the set of honest parties towards which the adversary behaves according to $\vect{v}_1$ (for the remainder it behaves according to $\vect{v}_0$, which is a decreasing set of parties). While the honest parties might identify the attacking parties and discard their messages, they should still agree on the output and halt at the conclusion of the second round with high probability. We exploit this fact to show that at the two extremes (where the adversary is merely playing honestly according to $\vect{v}_0$ and $\vect{v}_1$, respectively), the honest parties behave essentially the same. Therefore, if at one extreme (for $\vect{v}_0$) the honest parties output $\o$, it follows that they also output $\o$ at the other extreme (for $\vect{v}_1$), which proves the \emph{neighboring} property for the second-round case.

We implement the above by augmenting the one-round attack as follows. In addition to corrupting a set of parties that feign different inputs to different parties, the adversary corrupts an extra set of parties that is inconsistent with regards to the messages it received from the first set of corrupted parties. To distinguish between the two sets of corrupted parties, the former (first) will be referred to as ``pivot'' parties (since they pivot their input) and will be denoted $\mathcal{P}$, and the latter will be referred to as ``propagating'' parties (since they carefully choose what message to propagate at the second round) and will be denoted $\mathcal{L}$. We emphasize that the propagating parties deviate from the protocol only at the second round and only with regards to the messages received by the pivot parties (not with regards to their input -- as is the case for the pivot parties). In more detail, we partition ${\overline{\mathcal{P}}} = [n]\setminus \mathcal{P}$ into $\ell=\lceil 1/\varepsilon\rceil$ sets $\sset{\mathcal{L}_1,\ldots,\mathcal{L}_\ell}$, and we show that, unless there exists $i$ such that parties in $\mathcal{C}= \mathcal{P}\cup \mathcal{L}_i$ violate agreement (explained below), the following must hold for neighboring executions.

\begin{align} \label{eq:nei2}
&\text{Neighbouring executions (N2):} \quad \mathrm{dist}(\vect{v}_0,\vect{v}_1)\le n/3 \implies \\
& \pr{\Pi(\vect{v}_0)=\o\text{ in two rounds}} \ge \pr{ \Pi(\vect{v}_1)=\o\text{ in two rounds}} - 2 (\ell +1)^2 \cdot (1-\gamma). \nonumber
\end{align}
That is, for two input vectors that are at most $n/3$--far, the difference in probability that two distinct executions (for each input vector) yield the same output within two rounds is roughly upper-bounded by the quantity $(1-\gamma)/\varepsilon^2$ (\ie non-halting probability divided by $\varepsilon^2$). To see that \cref{eq:nei2} holds true, fix $\vect{v}_0,\vect{v}_1\in {\zo^n}$ of hamming distance at most $n/3$, and let $\mathcal{P}$ be the set of indices where $\vect{v}_0$ and $\vect{v}_1$ differ. Consider the following $\ell+1$ distinct variants of $\Pi$, denoted $\set{\Pi_0,\ldots, \Pi_\ell}$; in protocol $\Pi_i$, parties in $\mathcal{P}$ send messages to $\mathcal{L}_1,\ldots, \mathcal{L}_i$ according to the input prescribed by $\vect{v}_1$ and to $\mathcal{L}_{i+1},\ldots, \mathcal{L}_\ell$ according to the input prescribed by $\vect{v}_0$, respectively. All other parties follow the instructions of $\Pi$ for input $\vect{v}_0$. We write $\Pi_i=\o$ to denote the event that the parties not in $\mathcal{P}$ output $\o$. Notice that the endpoint executions $\Pi_0$ and $\Pi_{\ell}$ are identical to honest executions with input $\vect{v}_0$ and $\vect{v}_1$, respectively. Let $\mathsf{Halt}_i$ denote the event that the parties not in $\mathcal{P}$ halt at the second round in an execution of $\Pi_{i}$. We point out that $\pr{ \neg \mathsf{Halt}_i}\le (\ell+1)\cdot (1-\gamma)$, since otherwise the adversary corrupting $\mathcal{P}$ and running $\Pi_i$, for a random $i\in (\ell) \ensuremath{\mathrel{\vcenter{\baselineskip0.5ex \lineskiplimit0pt \hbox{\scriptsize.}\hbox{\scriptsize.}}}=} \set{0,\ldots,\ell}$, prevents halting with probability greater than $1-\gamma$. Next, we inductively show that
\begin{align}
\pr{\Pi_i=\o \land \mathsf{Halt}_i} \ge \pr{\Pi_{0} =\o \land \mathsf{Halt}_0} - 2i\cdot (\ell+1) \cdot (1-\gamma),\label{eq:teke}
\end{align}
for every $i\in (\ell)$, which yields the desired expression for $i=\ell$. In pursuit of contradiction, assume \cref{eq:teke} does not hold, and let $i$ denote the smallest index for which it does not hold (observe that $i\ne 0$, by definition). Notice that
\begin{align*}
& \hspace*{-2cm}\pr{(\Pi_{i-1}= \o \land \mathsf{Halt}_{i-1}) \land (\Pi_{i }\neq \o\land \mathsf{Halt}_i)}\\
&\ge \pr{\Pi_{i-1}=\o \land \mathsf{Halt}_{i-1}}-\pr{ \Pi_{i }= \o\vee \neg \mathsf{Halt}_i}\\
&\ge \pr{\Pi_{i-1}=\o \land \mathsf{Halt}_{i-1}}-\pr{ \Pi_{i }= \o\land \mathsf{Halt}_i} - \pr{ \neg \mathsf{Halt}_i}\\
&> 2\cdot (\ell+1) \cdot (1-\gamma) - \pr{ \neg \mathsf{Halt}_i} \\
&\ge (\ell+1) \cdot (1-\gamma) > 0.
\end{align*}
The second inequality follows from union bound and $A\lor \neg B\equiv (A\land B) \lor \neg B$, the third inequality is by induction hypothesis, and the last inequality by the bound $\pr{ \neg \mathsf{Halt}_i}\le (\ell+1)\cdot (1-\gamma)$.

It follows that an adversary corrupting $\mathcal{C}=\mathcal{P} \cup \mathcal{L}_i$ causes disagreement with non-zero probability by acting as follows: parties in $\mathcal{P}$ and $\mathcal{L}_i$ send messages according to $\Pi_i$ and $\Pi_{i-1}$ to $\overline{\cC}_0$ and $\overline{\cC}_1$, respectively, where $\sset{\overline{\cC}_0,\overline{\cC}_1}$ is an arbitrary partition of $\overline{\cC}= [n]\setminus \mathcal{P}\cup \mathcal{L}_i$. Since disagreement is ruled out by assumption, we deduce \cref{eq:teke,eq:nei2}. To conclude, we combine the \emph{almost pre-agreement}
property (\cref{eq:maj}) with the \emph{neighboring} property (\cref{eq:nei2}) with
$\vect{v}_0=0^{n-t}1^{t}$, $\vect{v}_1=0^{t}1^{n-t}$, and $\o=1$.
Namely, $\pr{\Pi(\vect{v}_0)=1\text{ in two rounds}}=0$, by \emph{almost pre-agreement} and $\pr{\Pi(\vect{v}_1)=1\text{ in two rounds}}\ge\gamma$, by \emph{almost pre-agreement} and \emph{halting}. It follows that $0 \ge \gamma - 2 (\ell +1)^2 \cdot (1-\gamma)$, by \cref{eq:nei2}, and thus $1-\frac{1}{2(\ell+1)^2+1} \ge \gamma$, which yields the desired expression.

\subsection{Second-Round Halting -- Public-Randomness Protocols}\label{sec:technique:3}

In \cref{sec:technique:2}, we ruled out ``very good'' second-round halting for arbitrary protocols via an efficient locally consistent attack. Recall that if the halting probability is too good (probability almost one), then there is a somewhat simple attack that violates agreement and/or validity. In this subsection, we discuss ruling out \emph{any} second-round halting, \ie halting probability bounded away from zero, for public-randomness protocols.

We first explain why the attack -- as is -- does not rule out second-round halting. Suppose that at the first round the parties of $\Pi$ send a deterministic function of their input, and at the second round they send the messages they received at the first round together with a uniform random bit. On input $\vect{v}$ and randomness $\vect{r}$, the parties are instructed \emph{not} to halt at the second round (\ie carry on beyond the second round until they reach agreement with validity) if a super-majority ($\ge n-t$) of the $v_i$'s are in agreement and $\operatorname*{maj}(r_1,\ldots, r_n)\neq \operatorname*{maj}(v_1,\ldots, v_n)$, \ie the majority of the random bits does not agree with the super-majority of the inputs. In all other cases, the parties are instructed to output $\operatorname*{maj}(r_1,\ldots, r_n)$.
It is not hard to see that this protocol will halt with probability $1/2$, even in the presence of the previous locally consistent adversary (regardless of the choice of propagating parties $\mathcal{L}_i$). More generally, if the randomness uniquely determines the output, the protocol designer can ensure that halting does not result in disagreement, by partitioning the randomness appropriately, and thus foiling the previous attack.\footnote{In \cref{sec:technique:2}, halting was close to $1$ and thus the randomness was necessarily ambiguous regarding the output.}

To overcome the above apparent obstacle, we introduce another dimension to our locally consistent attack; we instruct an extra set of corrupted parties to abort at the second round without sending their second-round messages. By utilizing aborting parties, the adversary can potentially decouple the output/halting from the parties' randomness and thus either prevent halting or cause disagreement.
In \cref{sec:technique:3:1}, we explain how to rule out second-round halting for a rather unrealistic class of public-randomness protocol. What makes the class of protocols unrealistic is that we assume security holds against unbounded locally consistent adversaries, and the protocol prescribes only a single bit of randomness per party per round. That being said, this case illustrates nicely our attack, and it also makes an interesting connection to Boolean functions analysis (namely, the KKL theorem~\cite{KKL88}). For general public-randomness protocols, we only know how to analyze the aforementioned attack assuming \cref{con:intro:IsoBot}, as explained in \cref{sec:technique:3:2}.

\subsubsection{``Superb'' Single-Coin Protocols}\label{sec:technique:3:1}
A BA protocol $\Pi$ is $t$-\emph{superb} if agreement and validity hold perfectly against an adaptive \emph{unbounded} locally consistent adversary corrupting at most $t$ parties, \ie the probability that such an adversary violates agreement or validity
is $0$. A public-randomness protocol is \emph{single-coin}, if, at any given round, each party samples a single unbiased bit.

\begin{theorem}[Second-round halting, superb single-coin protocols]\label{bound:KKL}
For every $\varepsilon> 0$ there exists $c>0$ such that the following holds for large enough $n$. For $t=(1/3+\varepsilon) \cdot n$, let $\Pi$ be a $t$-superb, single-coin, $n$-party public-randomness Byzantine agreement protocol and let $\gamma$ denote the probability that the protocol halts in the second round under a locally consistent attack. Then, $\gamma\le n^{-c}$.
\end{theorem}

We assume for simplicity that the parties do not sample any randomness at the first round, and write $\vect{r}\in {\zo^n}$ for the vector of bits sampled by the parties at the second round, \ie $r_i$ is a uniform random bit sampled by $\MathAlgX{P}_i$.

As discussed above, our attack uses an additional set of corrupted parties of size $\sigma\cdot n$, dubbed the ``aborting'' parties and denoted $\mathcal{S}$, that abort indiscriminately at the second round (the value of $\sigma$ is set to $\lfloor \varepsilon/4 \rfloor$ and $\ell=2\cdot \lceil1/\varepsilon\rceil$ to accommodate for the new set of corrupted parties, \ie $\size{\mathcal{L}_i}\le n\cdot \varepsilon /2$). In more detail, analogously to the previous analysis, we consider $(\ell+1)\cdot \binom{n}{\sigma n}$ distinct variants of $\Pi$, denoted $\sset{\Pi^{\mathcal{S}}_i}_{i,\mathcal{S}}$ and indexed by $i\in (\ell)$ and $\mathcal{S} \subseteq[n]$ of size $\sigma n$, as follows. In protocol $\Pi_i^\mathcal{S}$, parties in $\mathcal{P}$ send messages to $\mathcal{L}_1,\ldots, \mathcal{L}_i$ according to the input prescribed by $\vect{v}_1$, and to $\mathcal{L}_{i+1},\ldots, \mathcal{L}_\ell$ according to the input prescribed by $\vect{v}_0$ (recall that $\mathcal{P}$ is exactly those indices where $\vect{v}_0$ and $\vect{v}_1$ differ). Parties in $\mathcal{S}$ act according to $\mathcal{P}$ or $\mathcal{L}_j$, for the relevant $j$, except that they abort at the second round without sending their second-round messages. We write $\Pi^{\mathcal{S}}_i(\vect{r})=\o$ to denote the event that the parties not in $\mathcal{P}\cup \mathcal{S}$ output $\o$, where the parties' second-round randomness is equal to $\vect{r}$. Let $\mathsf{Halt}^{\mathcal{S}}_i$ denote the event that all parties not in $\mathcal{P}\cup \mathcal{S}$ halt at the second round in an execution of $\Pi^{\mathcal{S}}_i$, and define $\mathcal{R}_{i }^{\mathcal{S}}(\o)=\sset{\vect{r}\in {\zo^n}\text{ s.t.\ } \Pi^{\mathcal{S}}_i(\vect{r})=\o \land \mathsf{Halt}^{\mathcal{S}}_i}$. The following holds:

\begin{align}\label{eq:nei3}
&\text{Neighbouring executions (N2$\dagger$):}\\
&\quad \forall \vect{v}_0,\vect{v}_1 \in {\zo^n} \text{ with } \mathrm{dist}(\vect{v}_0,\vect{v}_1)\le n/3, \quad \forall \o\in \{0,1\},i\in [\ell] \ensuremath{\mathrel{\vcenter{\baselineskip0.5ex \lineskiplimit0pt \hbox{\scriptsize.}\hbox{\scriptsize.}}}=} \set{1,\ldots,\ell}\colon\nonumber\\
&\qquad\qquad \left (\forall \mathcal{S}\colon \pr{\Pi^\mathcal{S}_{i-1}=\o \land \mathsf{Halt}^{\mathcal{S}}_{i-1}} \ge \gamma/2 \right) \implies \left(\forall \mathcal{S}\colon\pr{\Pi^\mathcal{S}_{i}=\o \land \mathsf{Halt}^{\mathcal{S}}_{i}}\ge \gamma/2\right). \nonumber
\end{align}

\noindent
In words, for both $\o\in \{0,1\}$: if $\Pi_{i-1}^\mathcal{S}=\o$ and halts in two rounds with large probability ($\ge \gamma/2$), for every $\mathcal{S}$, then $\Pi_i^\mathcal{S}=\o$ and halts in two rounds with large probability, for every $\mathcal{S}$. Before proving \cref{eq:nei3}, we show how to use it to derive \cref{bound:KKL}. We apply \cref{eq:nei3} for
$\vect{v}_0=0^{n-t}1^{t}$, $\vect{v}_1=0^{t}1^{n-t}$, $\o=0$, and $i=\ell$, in combination with the properties of \emph{validity} and \emph{almost pre-agreement}
(\cref{eq:maj}). Namely, by these properties,
a random execution of $\Pi$ on input $\vect{v}_0$ where the parties in $\mathcal{S}$ abort at the second round yields output $0$ with probability at least $\gamma/2$, for every $\mathcal{S}\in {\binom{[n]}{\sigma n}}$.
Therefore, by \cref{eq:nei3},
we deduce that a random execution of $\Pi$ on input $\vect{v}_1$ where the parties in $\mathcal{S}$ abort at the second round yields output $0$ with probability at least $\gamma/2$, for every $\mathcal{S}\in {\binom{[n]}{\sigma n}}$. The latter violates either \emph{validity} or \emph{almost pre-agreement} -- contradiction.
To conclude the proof of \cref{bound:KKL}, we prove \cref{eq:nei3} by using the following corollary of the seminal KKL theorem \cite{KKL88} from \citet{BKK14}.
(Recall that $\mathcal{R}|_{\wb{\mathcal{S}}}$ is the projection of $\mathcal{R}$ on the index-set $\wb{\mathcal{S}}$.)

\begin{lemma}\label{lem:KKL} For every $\sigma, \delta\in (0,1)$, there exists $c>0$ s.t.\
the following holds for large enough~$n$. Let $\mathcal{R} \subseteq {\zo^n}$ be s.t.\
$\ssize{\mathcal{R}|_{\wb{\mathcal{S}}}}\le (1-\delta)\cdot 2^{(1-\sigma)n}$, for every $\mathcal{S}\subseteq [n]$ of size $\sigma n$. Then, $\size{\mathcal{R}}\le n^{-c}\cdot 2^n$.
\end{lemma}

Loosely speaking, \cref{lem:KKL} states that for a set $\mathcal{R}\subseteq {\zo^n}$, if the size of every projection on a constant fraction of indices is bounded away from one (in relative size), then the size of $\mathcal{R}$ is vanishingly small
(again, in relative size).\footnote{In the jargon of Boolean functions analysis, since every large set has a $o(n)$-size index-set of influence almost one, it follows that some projection on a constant fraction of indices is almost full.}

Going back to the proof, in pursuit of contradiction, let $i\ge 1$ denote the smallest index for which \cref{eq:nei3} does not hold, and without loss of generality suppose $b=0$, \ie there exists $\mathcal{S}$ such that $\ssize{\mathcal{R}_{i}^{\mathcal{S}}(0)}< \gamma/2 \cdot 2^{n}$, and $\ssize{\mathcal{R}_{i-1}^{\mathcal{S}'}(0)}\ge \gamma/2 \cdot 2^n$, for every relevant $\mathcal{S}'$. We prove \cref{eq:nei3} by proving \cref{eq:halt,eq:proj}, which result in contradiction via \cref{lem:KKL}.

\begin{align}
\text{Halting:}&\qquad \ssize{\mathcal{R}_{i }^{\mathcal{S}}(1)}\ge \gamma/2 \cdot 2^{n} \label{eq:halt} \\
\text{Perfect agreement:}&\qquad \forall \mathcal{S}' \colon \quad \ssize{\mathcal{R}_{i}^{\mathcal{S}}(1)|_{\wb{\mathcal{S}}'}}\le (1-\gamma/2)\cdot 2^{(1-\sigma) n} \label{eq:proj}
\end{align}
\noindent
\cref{eq:halt} follows by the \emph{halting} property of $\Pi_{i}^\mathcal{S}$, since the execution halts if and only if $\vect{r}\in \mathcal{R}_{i }^{\mathcal{S}}(1)\cup \mathcal{R}_{i }^{\mathcal{S}}(0)$, and, by assumption, $\ssize{\mathcal{R}_{i }^{\mathcal{S}}(0)}< \gamma/2 \cdot 2^{n}$.
To conclude, we prove \cref{eq:proj} by observing that for every $\mathcal{S}'$ and $b\in \{0,1\}$, and every $\vect{r}$ and $\vect{r}'$, if $\vect{r}\in \mathcal{R}_{i-1}^{\mathcal{S}'}(0)$ and $\vect{r}|_{\wb{\mathcal{S}}'}=\vect{r}'|_{\wb{\mathcal{S}}'}$, then $\vect{r}'\in \mathcal{R}_{i-1}^{\mathcal{S}'}(0)$ (by definition), \ie membership to $\mathcal{R}_{i-1}^{\mathcal{S}'}(0)$ does not depend on the indices of $\mathcal{S}'$.
It follows that $\ssize{\mathcal{R}_{i-1}^{\mathcal{S}}(0)|_{\wb{\mathcal{S}}'}}\ge \gamma/2 \cdot 2^{(1-\sigma) n}$, for every $\mathcal{S}'$, and therefore $\ssize{\mathcal{R}_{i}^{\mathcal{S}}(1)|_{\wb{\mathcal{S}}'}}\le (1-\gamma/2)\cdot 2^{(1-\sigma) n}$, since the sets $\mathcal{R}_{i}^{\mathcal{S}}(1)|_{\wb{\mathcal{S}}'}$ and $\mathcal{R}_{i-1}^{\mathcal{S}}(0)|_{\wb{\mathcal{S}}'}$ are non-intersecting for every $\mathcal{S}'$.
Otherwise, if $\mathcal{R}_{i}^{\mathcal{S}}(1)|_{\wb{\mathcal{S}}'}\cap \mathcal{R}_{i-1}^{\mathcal{S}}(0)|_{\wb{\mathcal{S}}'}\neq \emptyset$, then the following attack violates the superb quality of the protocol. Fix $\mathcal{S}'$ and $\vect{r}$ such that $\vect{r}\in \mathcal{R}_{i}^{\mathcal{S}}(1)$ and $\vect{r}|_{\wb{\mathcal{S}}'}\in \mathcal{R}_{i}^{\mathcal{S}}(1)|_{\wb{\mathcal{S}}'}\cap \mathcal{R}_{i-1}^{\mathcal{S}}(0)|_{\wb{\mathcal{S}}'}$, and consider the attacker controlling $\mathcal{P}$, $\mathcal{L}_{i}$, $\mathcal{S}$, and $\mathcal{S}'$ that sends
messages according to $\Pi_{i}^{\mathcal{S}}$ and $\Pi_{i-1}^{\mathcal{S}'}$ to $\overline{\cC}_0$ and $\overline{\cC}_1$, respectively, where $\sset{\overline{\cC}_0,\overline{\cC}_1}$ is an arbitrary partition of $\overline{\cC}=[n]\setminus \mathcal{P}\cup \mathcal{L}_{i} \cup \mathcal{S}\cup \mathcal{S}'$. It is not hard to see the attacker violates agreement, whenever the randomness lands on $\vect{r}$.

\begin{remark}
For superb, single-coin, public-randomness protocol, repeated application of \cref{eq:nei,lem:KKL} rules out second-round halting for arbitrary (constant) fraction of corrupted parties (and not only $n/3$ fraction).
\end{remark}

\subsubsection{General (Public-Randomness) Protocols}\label{sec:technique:3:2}
The analysis above crucially relies on the superb properties of the protocol. While it can be generalized for protocols with near-perfect statistical security and constant-bit randomness, we only manage to analyze the most general case (\ie protocols with non-perfect computational security and arbitrary-size randomness) assuming \cref{con:intro:IsoBot}. Very roughly (and somewhat inaccurately), when applying the above attack on general public-randomness protocols, the following happens for some $\delta>0$ and both values of $\o\in \{0,1\}$: for $(1-\delta)$-fraction of possible aborting subsets $\mathcal{S}$, the probability that the honest parties halt in two rounds and output the same value $\o$, whether parties in $\mathcal{S}$ all abort or not, is bounded below by the halting probability. Assuming \cref{con:intro:IsoBot}, it follows that with probability $\delta$ over the randomness and $\mathcal{S}$, the honest parties under the attack output opposite values depending whether the parties in ${\cal{S}}$ abort or not. We conclude that the agreement of the protocol is at most $\delta$. We refer the reader to \cref{sec:TwoRoundProtcol:PR} for the full details.