
\section{More Technical Proof of \theoremref{gap-main}}
\label{app:geometric-proof-l1}

\begin{claim}
	For each $d\geq 1$, let $C_d$ denote a curve over $X\in[0,1]$ that includes all points $(x,\mathrm{opt}_d(x,1))$. Let $T$ be the transformation defined in \figureref{transform-def}.
	Then, $C_{d}=T^{d-1}(C_1)$ where $T^{0}$ denotes the identity transformation and $T^{k}$ denotes the transformation achieved by composing $T$ with itself $k$ times. Moreover, for every depth $d$, there exists a martingale of bias $x$ whose $\mathrm{max\textnormal{-}score}$ in $L_1$-norm is equal to $\mathrm{opt}_d(x,1)$ and for each $i=1,\dots,n$, $\abs{\Omega_i}=2$.  
\end{claim}
\begin{proof}
	Let $C_1$ be the curve defined by
	the zeros of the equation $Y=2X(1-X)$ such that 
	$Y\geq 0$. Let $C_{d+1}$ be the curve obtained by 
	applying the transformation $T$ on $C_d$.\\
	Let $X'=\{X'=\{X'_i\}_{i=0}^{n},E'=\{E'_i\}_{i=1}^
	{n}\}$ be a martingale over the sample space 
	$\Omega'=\Omega'_1\times\dots\times\Omega'_n$ such
	that for each $i\in[n]$, $\Omega'_i=\{0,1\}, 
	E'_i(0)=l, E'_i(1)=r, X'_0=x$, for each 
	$(e_1,e_2,\dots,e_{n-1})\in \{l,r\}^{n-1}$, 
	$X'_n(e_1,\dots,e_{n-1},l)=0$ and 
	$X'_n(e_1,\dots,e_{n-1},r)=1$, for each $i\in 
	\{1,\dotsc,n-1\}$, $X'_i(e_1,e_2,\dots,e_{i-1},l)$ is the $X$
	coordinate of the interception of the line 
	$Y=-X+X'_{i-1}(e_1,\dots,e_{i-1})$ and the curve 
	$C_{n-i}$, and $X'_i(e_1,e_2,\dots,e_{i-1},r)$ is 
	the $X$ coordinate of the interception of the line
	$Y=X-X'_{i-1}(e_1,\dots,e_{i-1})$ and the curve 
	$C_{n-i}$.\\ Moreover, for each 
	$(e_1,e_2,\dots,e_{i-1})\in \{l,r\}^{i-1}$,  
	$$\Pr[l|E'_1=e_1,\dots,E'_{i-1}=e_{i-1}]=\frac{X'_
		{i}(e_1,\dots,e_{i-1},r)-X'_{i-1}(e_1,\dots,e_{i-1
		})}{X'_{i}(e_1,\dots,e_{i-1},r)-X'_{i}(e_1,\dots,e
		_{i-1},l)}$$ and
	$$\Pr[r|E'_1=e_1,\dots,E'_{i-1}=e_{i-1}]=\frac{X'_
		{i-1}(e_1,\dots,e_{i-1})-X'_{i}(e_1,\dots,e_{i-1},
		l)}{X'_{i}(e_1,\dots,e_{i-1},r)-X'_{i}(e_1,\dots,e
		_{i-1},l)}$$
	We claim that for each martingale 
	$\{X=\{X_i\}_{i=1}^n,E=\{E_i\}_{i=1}^n\}$ with 
	respect to the sample space 
	$\Omega=\Omega_1\times\dots\times\Omega_n$, we 
	have $\mathrm{max\textnormal{-}score}_1(X,E)\geq 
	\mathrm{max\textnormal{-}score}_1(X',E')$ and so 
	$\mathrm{opt}_d(x,1)=\mathrm{max\textnormal{-}sc
		ore}_1(X',E')$.\\ We prove our claim by induction on
	the depth of the martingale i.e. $n$. \\For the base
	case $n=1$, suppose $\Omega_1=\{1,\dots,t\}$, 
	$E_1(j)=e_1^{(j)}$. Without loss of generality, we 
	assume that $X_1(e_1^{(1)})\leq X_1(e_1^{(2)})\dots\leq 
	X_1(e_1^{(t)})$. Then there exist $p^{(1)},\dots,p^{(n)}$ such 
	that $x=\sum_{j=1}^{t}p^{(j)}X_1(e_1^{(j)})$ and 
	$\sum_{j=1}^{t}p^{(j)}=1$. In this case, since 
	$X_1(e_1^{(j)})$ is $0$ or $1$, there exists some $s$ 
	such that $x=\sum_{j=s+1}^{t}p^{(j)}$ and 
	$$\mathrm{max\textnormal{-}score}_1(X,E)=(p^{(1)}+\dots+
	p^{(s)})x+(p^{(s+1)}+\dots+p^{(t)})(1-x)=2x(1-x)$$ 
	But, the maximum score of a martingale $(X,E)$ 
	with respect to $\Omega_1=\{0,1\}$ such that 
	$\Pr[0]=x$ and $\Pr[1]=1-x$ is also 
	$2x(1-x)$.\\ Suppose that the claim is true for 
	depth $d$, and we want to prove it for the depth 
	$d+1$. \\
	Suppose that the martingale $\{ 
	X=\{X_i\}_{i=0}^{d+1},E=\{E_i\}^{d+1}_{i=1} \}$ 
	over $\Omega=\Omega_1\times 
	\Omega_2\times\dots\times\Omega_{d+1}$ is given such that $\Omega_1=\{1,\dots,t\}$ and for each $j\in \Omega_1$,
	$E_1(j)=e_1^{(j)}$.
	

	
	
	Note that for each $j\in \{1,2,\dotsc,t\}$, we define the 
	martingale 
	$\{V^{(j)}=\{V^{(j)}_i\}_{i=0}^{d}, 
	E^{(j)}=\{E^{(j)}_i\}_{i=2}^{d+1}\}$ over 
	$\Omega_2\times\dots\times\Omega_{d+1}$ where 
	$V^{(j)}_{i}(e_2,\dots,e_{d+1}):=X_{i+1}(e_1^{(j)},e_2,
	\dots,e_{d+1})$ is a martingale of depth $d$. Observe that
	for 
	any $j$
	and any value of $V_0=X_1(e_1^{(j)})$, there exists an 
	stopping time 
	$\tau^{(j)}_{max}(V^{(j)},E^{(j)}):\Omega_2\times
	\dots\times\Omega_{d+1}\rightarrow\{2,\dots,n\}$ 
	that maximizes the score of the martingale 
	$(V^{(j)},E^{(j)})$. Now, note that 
	$\tau_{max}(X,E)(e_1^{(j)},e_2,\dots,e_{d+1})$ equals $1$ 
	(which means that the martingale stops at time 
	$1$) when 
	$$|X_0-X_1(e_1^{(j)})|\geq 
	\mathrm{max\textnormal{-}score}_1(V^{(j)},E^{(j)})$$ 
	or equals $\tau^{(j)}_{max}(V^{(j)},E^{(j)})(e_2,
	\dots,e_{d+1})$ when $$|X_0-X_1(e_1^{(j)})|\leq 
	\mathrm{max\textnormal{-}score}_1(V^{(j)},E^{(j)})$$
	Let us define 
	$B_j\defeq\mathrm{max}(\mathrm{max\textnormal{-}score}_1(
	V^{(j)},E^{(j)}),|X_0-X_1(e_1^{(j)})|)$.
	We represent each point $Z^{(j)}\eqdef(X_1(e_1^{(j)}),B_j)$ in a 
	plane, see \figureref{induct}. In this plane, for each point $(x,y)$, 
	the value $y$ represents the score of a stopping time in a martingale 
	whose average is $x$ (the first value that the martingale takes).
	Since $X$ is a martingale, we have $X_0=\sum_{j=1}^{t}p^{(j)}X_1(e_1^{(j)})$.
	It also follows from the definition of $B_j$ that
	$$\mathrm{max\textnormal{-}score}_1(X,E)=\sum_{j=1}^{t}\Pr[E_1=j]B_j=\sum_{j=1}^{t}p^{(j)}B_j.$$
	Therefore, we have $$(X_0,\mathrm{max\textnormal{-}score}_1(X,E
	))=\sum_{j=1}^{t}p^{(j)}(X_1(e_1^{(j)}),B_j)=\sum_{j=1}^{t}p^{(j)}Z^{(j)}.$$
	Consequently, the point $(X_0,\mathrm{max\textnormal{-}score}_1(X,E
	))$ lies on the intersection of the line $X=X_0$ and the 
	convex hull of the points $Z^{(1)},\dotsc, Z^{(t)}$ 
	(Note that the argument is true even if we assume that $t$ is not finite).     
	
	It follows from the inductive hypothesis that for each 
	$j$, there exists a martingale of depth
	$d$, $\{X'^{(j)}=\{X'^{(j)}_i\}_{i=1}^{d+1}, 
	E'^{(j)}=\{E'^{(j)}_i\}_{i=2}^{d+1}\}$ over 
	$\Omega_2^{'}\times\dots\times\Omega_{d+1}^{'}$ such that $X'^{(j)}_1=X_1(e_1^{(j)})$ and for each $i\in \{2,\dots,d+1\}$, $\vert \Omega_i^{'}\vert=2$ and
	$\mathrm{max\textnormal{-}score}_1(X',E')=\mathrm{opt}_d(X'^{(j)}_1,1)=\mathrm{opt}_d(X_1(e_1^{(j)}))$. Therefore, $\mathrm{max\textnormal{-}score}_1(V^{(j)},E^{(j)})\geq \mathrm{opt}_d(X_1(e_1^{(j)}),1)$. This implies that
	$$ B_j\geq \mathrm{max}(\mathrm{opt}_d(X_1(e_1^{(j)}),1),|X_0-X_1(e_1^{(j)})|) $$
	that means the points $Z^{(1)},\dotsc, Z^{(t)}$ lie above 
	the curve defined by the zeros of the 
	equation $Y=\mathrm{max}(\mathrm{opt}_{d}(X,1),|X_0-
	X|)=\mathrm{max}(C_d(X),
	|X-X_0|)$. 

	Note that according to the inductive hypothesis, $C_d$ (the zeros of the equation 
	$Y=\mathrm{opt}_{d}(X,1)$) is equal to the curve $T^{d-1}(C_1)$ which is concave downward as a consequence of \claimref{preserve-concavity}. Thus, the intersection of the line $X=X_0$ and the 
	convex hull of the points $Z^{(1)},\dotsc, Z^{(t)}$ is above the point $Q=(x,C_{d+1}(x))$, see \figureref{induct}. Moreover, by choosing $t=2$ and $Z^{(1)}=P_1$ and $Z^{(2)}=P_2$, the score $T(C_d)(x)$ (point $Q$) can be achieved. But, note that according to the inductive hypothesis, the points $P_1$ and $P_2$ can be achieved by the martingale $\{X'^{(j)}=\{X'^{(j)}_i\}_{i=1}^{d+1}, E'^{(j)}=\{E'^{(j)}_i\}_{i=2}^{d+1}\}$. This shows
	that the martingale of depth $d+1$ with optimal score is achieved
	when for each $i\in \{1,\dotsc,d+1\}$, $|\Omega_i|=2$. Also as mentioned earlier, the height of the point $Q$ is $T(C_d)(x)$ and according to induction hypothesis, $C_d(x)=T^{d-1}(C_1)(x)$, so $\mathrm{opt}_{d+1}(x,1)=T^{d}(C_1)(x)$.    
























   
   













	

\end{proof}

\section{Applications}
\label{sec:applications} 



This section discusses various consequences of \theoremref{gap-main} and other related results. 

\input{fair}
\input{unfair} 
\input{control} 
\input{l2-gap} 
\subsection{Our Contributions}
\label{sec:contrib} 

We prove the following general martingale theorem.
\begin{theorem}
	\label{thm:gap-main} 
	Let $(X_0,X_1,\dotsc,X_n)$ be a discrete-time martingale such that $X_i\in[0,1]$, for all $i\in\{1,\dotsc,n\}$, and
	$X_n\in\{0,1\}$.
	Then, the following bound holds.
	$$\sup_{\text{stopping time }\tau} \EX{\abs{X_\tau-X_{\tau-1}}} \geq C_n(X_0),$$
	where $C_1(X) = 2X(1-X)$, and, for $n>1$, we obtain $C_n$ from $C_{n-1}$ recursively using the geometric transformation defined in \figureref{transform-def}.
	
	Furthermore, for all $n\geq1$ and $X_0\in[0,1]$, there exists a martingale $(X_0,\dotsc,X_n)$ (\wrt to the coordinate exposure filtration for $\zo^n$) such that for any stopping time $\tau$, it has $\EX{\abs{X_\tau-X_{\tau-1}}} = C_n(X_0)$. 
\end{theorem} 

Intuitively, given a martingale, an adversary can identify a stopping time where the expected gap in the martingale is at least $C_n(X_0)$.
Moreover, there exists a martingale that realizes the lower-bound in the tightest manner, \ie, all stopping times $\tau$ have identical susceptibility. 

Next, we estimate the value of the function $C_n(X)$. 
\begin{lemma}
	\label{lem:gap-lower-upper}
	For $n\geq 1$ and $X\in[0,1]$, we have 
	$$\frac2{\sqrt{2n-1}}X(1-X) \eqdef L_n(X) \leq C_n(X) \leq U_n(X)\defeq \frac1{\sqrt{n}}\sqrt{X(1-X)}$$
\end{lemma}
As a representative example, consider the case of $n=3$ and $X_0=1/2$. 
\figureref{3-majority} presents the martingale corresponding to the 3-round majority protocol and highlights the stopping time witnessing the susceptibility of 0.3750. 
\figureref{3-opt} presents the optimal 3-round coin-tossing protocol's martingale that has susceptibility of 0.2407. 

\input{fig-3-majority}
\input{fig-3-opt} 

In the sequel, we highlight applications of \theoremref{gap-main} to protocol constructions and hardness of computation results using these estimates. 

\begin{remark}[Protocol Constructions]
	The optimal martingales naturally translate into $n$-bit distributed coin-tossing and multi-faceted dice rolling protocols. 
	\begin{enumerate}
		\item \corollaryref{fair}: 
		For all $X_0\in[0,1]$, there exists an $n$-bit distributed bias-$X_0$ coin-tossing protocol for $n$ processors with the following security guarantee. 
		Any (computationally unbounded) adversary who follows the protocol honestly and resets at most one of the processors during the execution of the protocol can change the probability of an outcome by at most $\frac1{2\sqrt n}\sqrt{X_0(1-X_0)}$. 
	\end{enumerate}
\end{remark}

\begin{remark}[Hardness of Computation Results]
	The lower-bound on the maximum susceptibility helps demonstrate hardness of computation results. 
	For $X_0=1/2$, Cleve and Impagliazzo~\cite{Cleve93martingales} proved that one encounters $\abs{X_\tau-X_{\tau-1}}\geq \frac1{32\sqrt n}$ with probability $\frac15$. 
	In other words, their bound guarantees that the expected gap in the martingale is at least $\frac1{160\sqrt n}$, which is significantly smaller than our bound $\frac1{2\sqrt{2 n}}$. 
	Hardness of computation results relying on \cite{Cleve93martingales} (and its extensions) work only for constant $0<X_0<1$.%
	\footnote{%
		Cleve and Impagliazzo set their problem as an optimization problem that trades off two conflicting objective functions. 
		These objective functions have exponential dependence on $X_0(1-X_0)$. 
		Consequently, if $X_0=1/\poly(n)$ or $X_0=1-1/\poly(n)$, then their lower bounds are extremely weak.
		%
	}
	However, our lower-bound holds for all $X_0\in[0,1]$; for example, even when $1/\poly(n) \leq X_0  \leq 1-1/\poly(n)$. 
	Consequently, we extend existing hardness of computation results using our more general lower-bound. 
	\begin{enumerate}
		\item \theoremref{unfairness} extends the fail-stop attack of \cite{Cleve93martingales} on 2-party bias-$X_0$ coin-tossing protocols (in the information-theoretic commitment hybrid). 
		For any $X_0\in[0,1]$, a fail-stop adversary can change the probability of the final outcome of any 2-party bias-$X_0$ coin-tossing protocol by $\geq \frac{\sqrt 2}{12\sqrt{n+1}}X_0(1-X_0)$. 
		This result is useful to demonstrate black-box separations results. 
		\item \corollaryref{bb-sep} extends the black-box separation results of \cite{TCC:DLMM11,TCC:HaiOmrZar13,TCC:DacMahMal14} separating (appropriate restrictions of) 2-party bias-$X_0$ coin tossing protocols from one-way functions. 
		We illustrate a representative new result that follows as a consequence of \corollaryref{bb-sep}.  
		For constant $X_0\in(0,1)$, \cite{TCC:DLMM11,TCC:HaiOmrZar13,TCC:DacMahMal14} rely on (the extensions of) \cite{Cleve93martingales} to show that it is highly unlikely that there exist 2-party bias-$X_0$ coin tossing protocols using one-way functions in a black-box manner achieving  $o(1/\sqrt n)$ {\em unfairness}~\cite{EC:GorKat10}. 
		Note that when $X_0=1/n$, there are secure 2-party coin tossing protocols with  $1/2n$ unfairness (based on \corollaryref{fair}) even in the information-theoretic setting. 
		Previous results cannot determine the limits to the unfairness of 2-party bias-$1/n$ fair coin-tossing protocols that use one-way functions in a black-box manner. 
		Our black-box separation result (refer to \corollaryref{bb-sep}) implies that it is highly unlikely to construct bias-$1/n$ coin using one-way functions in a black-box manner with $< \frac{\sqrt2}{12\cdot n^{3/2}}$ unfairness. 
		\item \corollaryref{control} and \corollaryref{control2} extend Cleve and Impagliazzo's~\cite{Cleve93martingales} result on influencing discrete control processes to arbitrary $X_0\in[0,1]$. 
	\end{enumerate}
\end{remark}



\subsection{Influencing Discrete Control Processes} 
\label{sec:control} 


Lichtenstein~\etal~\cite{LLS1989} considered the problem of an adversary influencing the outcome of a stochastic process through mild interventions. 
For example, an adversary attempts to bias the outcome of a distributed $n$-processor coin-tossing protocol, where, in the $i$-th round, the processor $i$ broadcasts her message. 
This model is also used to characterize randomness sources that are adversarially influenced, for example,~\cite{FOCS:SriZuc94,SODA:KenRabSin96,zuckerman1996simulating,nisan1996extracting,nisan1999extracting,FOCS:TreVad00,FOCS:DodSpe02,FOCS:DOPS04,TCC:DodPiePrz06,TCC:BosDod07}.

Consider the sample space $\Omega=\Omega_1\times\Omega_2\times\dotsi\times\Omega_n$ and a joint distribution $(E_1,\dotsc,E_n)$ over the sample space. 
We have a function $f\colon\Omega\to\zo$ such that $\EX{f(E_1,\dotsc,E_n)}=X_0$. 
This function represents the protocol that determines the final outcome from the public transcript. 
The filtration, at time-step $i$, reveals the value of the random variable $E_i$ to the adversary. 
We consider the corresponding Doob's martingale $(X_0,X_1,\dotsc,X_n)$. 
Intuitively, $X_i$ represents the probability of $f(E_1,\dotsc,E_n)=1$ conditioned on the revealed values $(E_1=e_1,\dotsc,E_i=e_i)$. 
The adversary is allowed to intervene only once. 
She can choose to intervene at time-step $i$, reject the current sample $E_i=e_i$, and substitute it with a fresh sample from $E_i$. 
This intervention is identical to {\em restarting} the $i$-th processor if the adversary does not like her message. 
Note that this intervention changes the final outcome by 
  $$(X_{i-1}|E_1=e_1,\dotsc,E_{i-1}=e_{i-1}) - (X_i|E_1=e_1,\dotsc,E_i=e_i)$$


We shall use a stopping time $\tau$ to represent the time-step where an adversary decides to intervene. 
However, for some $(E_1=e_1,\dotsc,E_n=e_n)$ the adversary may not choose to intervene. 
Consequently, we consider stopping times $\tau\colon\Omega\to\{1,\dotsc,n,\infty\}$, where the stopping time being $\infty$ corresponds to the event that the adversary did not choose to intervene. 
In the Doob martingale discussed above, as a direct consequence of \theoremref{gap-main}, there exists a stopping time $\tau^*$ with susceptibility $\geq C_n(X_0)$. 
Note that susceptibility measures the expected (unsigned) magnitude of the deviation, if an adversary intervenes at $\tau^*$.  
Some of these contributions to susceptibility shall increase the probability of the final outcome being 1, and the remaining shall decrease the probability of the final outcome being 1. 
By an averaging argument, there exists a stopping time $\tau\colon\Omega\to\{1,\dotsc,n,\infty\}$ that biases the outcome of $f$ by at least $\geq\frac12 C_n(X_0)$, whence the following corollary. 
\begin{corollary}[Influencing Discrete Control Processes]
\label{corol:control}
Let $\Omega_1,\dotsc,\Omega_n$ be arbitrary sets, and $(E_1,\dotsc,E_n)$ be a joint distribution over the set $\Omega\defeq\Omega_1\times\dotsi\times\Omega_n$. 
Let $f\colon\Omega\to\zo$ be a function such that $\probX{f(E_1,\dotsc,E_n)=1}=X_0$. 
Then, there exists an adversarial strategy of intervening once to bias the probability of the outcome away from $X_0$ by $\geq \frac12C_n(X_0) \geq \frac12L_n(X_0) =\frac{1}{\sqrt{2n-1}}X_0(1-X_0)$. 
\end{corollary}
The previous result of \cite{Cleve93martingales} applies only to $X_0=1/2$ and they ensure a deviation of $1/320\sqrt n$. 
For $X_0=1/2$, our result ensures a deviation of (roughly) $1/4\sqrt{2n} \approx 1/5.66\sqrt n$. 







\subsubsection{Influencing Multi-faceted Dice-rolls} 

\corollaryref{control} generalizes to the setting where $f\colon\Omega\to\{0,1,\dotsc,\omega-1\}$, \ie, the function $f$ outputs an arbitrary $\omega$-faceted dice roll. 
In fact, we quantify the deviation in the probability of any subset $S\subseteq\{0,1,\dotsc,\omega-1\}$ of outcomes caused by an adversary intervening once.  
\begin{corollary}[Influencing Multi-faceted Dice-Rolls]
\label{corol:control2}
Let $\Omega_1,\dotsc,\Omega_n$ be arbitrary sets, and $(E_1,\dotsc,E_n)$ be a joint distribution over the set $\Omega\defeq\Omega_1\times\dotsi\times\Omega_n$. 
Let $f\colon\Omega\to\{0,1,\dotsc,\omega-1\}$ be a function with $\omega\geq 2$ outcomes, $S\subseteq\{0,1,\dotsc,\omega-1\}$ be any subset of outcomes, and  $\probX{f(E_1,\dotsc,E_n)\in S}=X_0$. 
Then, there exists an adversarial strategy of intervening once to bias the probability of the outcome being in $S$ away from $X_0$ by $\geq \frac12C_n(X_0) \geq \frac12L_n(X_0) =\frac{1}{\sqrt{2n-1}}X_0(1-X_0)$. 
\end{corollary}
\corollaryref{control} and \corollaryref{control2} are equivalent to each other. 
Clearly \corollaryref{control} is a special case of \corollaryref{control2}. 
\corollaryref{control2}, in turn, follows from \corollaryref{control} by considering ``$f(E_1,\dotsc,E_n)\in S$'' as the interesting event for the martingale. 
We state these two results separately for conceptual clarity and ease of comparison with the prior work. 











\subsection{Distributed Coin-Tossing Protocol} 
\label{sec:fair} 

We consider constructing distributed $n$-processor coin-tossing protocols where the $i$-th processor broadcasts her message in the $i$-th round. 
We shall study this problem in the information-theoretic setting.  
Our objective is to design $n$-party distributed coin-tossing protocols where an adversary cannot bias the distribution of the final outcome significantly. 


For $X_0=1/2$, one can consider the incredibly elegant ``majority protocol''~\cite{STOC:Blum83,ABCGM85,STOC:Cleve86}.
The $i$-th processor broadcasts a uniformly random bit in round $i$. 
The final outcome of the protocol is the majority of the $n$ outcomes, and an adversary can bias the final outcome by $\frac1{\sqrt{2\pi n}}$ by restarting a processor once~\cite{STOC:Cleve86}.



We construct distributed $n$-party bias-$X_0$ coin-tossing protocols, for any $X_0\in[0,1]$, and our new protocol for $X_0=1/2$ is more robust to restarting attacks than this majority protocol. 
Fix $X_0\in[0,1]$ and $n\geq 1$. 
Consider the optimal martingale $(X_0,X_1,\dotsc,X_n)$ guaranteed by \theoremref{gap-main}.
The susceptibility corresponding to any stopping time is $=C_n(X_0) \leq U_n(X_0) = \frac1{\sqrt n}\sqrt{X_0(1-X_0)}$.  
Note that one can construct an $n$-party coin-tossing protocol where the $i$-th processor broadcasts the $i$-th message, and the corresponding Doob's martingale is identical to this optimal martingale. 
An adversary who can restart a processor once biases the outcome of this protocol by at most $\frac12 C_n(X_0)$, this is discussed in \sectionref{control}. 
\begin{corollary}[Distributed Coin-tossing Protocols]
\label{corol:fair} 
For every $X_0\in[0,1]$ and $n\geq 1$ there exists an $n$-party bias-$X_0$ coin-tossing protocol such that any adversary who can restart a processor once causes the final outcome probability to deviate by $\leq \frac12C_n(X_0) \leq \frac12U_n(X_0) = \frac1{2\sqrt n} \sqrt{X_0(1-X_0)}$. 
\end{corollary}
For $X_0=1/2$, our new protocol's outcome can be changed by $\frac1{4\sqrt n}$, which is less than the $\frac1{\sqrt{2\pi n}}$ deviation of the majority protocol. 
However, we do not know whether there exists a {\em computationally efficient} algorithm implementing the coin-tossing protocols corresponding to the optimal martingales. 























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

{\bfseries A Representative Motivating Application. }
Consider a distributed protocol for $n$ processors to toss a coin, where a processor $i$ broadcasts her message in round $i$. 
At the end of the protocol, all processors reconstruct the common outcome from the public transcript. 
When all processors are honest, the probability of the final outcome being 1 is $X_0$ and the probability of the final outcome being 0 is $1-X_0$, \ie, the final outcome is a {\em bias-$X_0$ coin}. 
Suppose there is an adversary who can (adaptively) choose to {\em restart} one of the processors after seeing her message (\ie, the {\em strong adaptive} corruptions model introduced by Goldwasser, Kalai, and Park~\cite{ICALP:GolKalPar15}); otherwise her presence is innocuous. 
Our objective is to design bias-$X_0$ coin-tossing protocols such that the adversary cannot change the distribution of the final outcomes significantly. 

{\em The Majority Protocol.} 
Against computationally unbounded adversaries, (essentially) the only known protocol is the well-known majority protocol~\cite{STOC:Blum83,ABCGM85,STOC:Cleve86} for $X_0=1/2$.
The majority protocol requests one uniformly random bit from each processor and the final outcome is the majority of these $n$ bits. 
An adversary can alter the probability of the final outcome being 1 by $\frac1{\sqrt{2\pi n}}$, \ie, the majority protocol is $\frac1{\sqrt{2\pi n}}$ insecure. 

{\em Our New Protocol.}
We shall prove a general martingale result in this paper that yields the following result as a corollary. 
For any $X_0\in[0,1]$, there exists an $n$-bit bias-$X_0$ coin-tossing protocol in the information-theoretic setting that is $\frac12\sqrt{\frac{X_0(1-X_0)}{n}}$ insecure.
In particular, for $X_0=1/2$, our protocol uses only 625 processors to reduce the insecurity to, say,  1\%; while the majority protocol requires 1592 processors.  


{\bfseries General Formal Framework: Martingales.} 
Martingales are natural models for several stochastic processes. 
Intuitively, martingales correspond to a gradual release of information about an event. 
A priori, we know that the probability of the event is $X_0$. 
For instance, in a distributed $n$-party coin-tossing protocol the outcome being $1$ is the event of interest.   

A discrete-time martingale $(X_0,X_1,\dotsc,X_n)$ represents the gradual release of information about the event over $n$ time-steps.\footnote{%
  For the introduction, we do not explicitly mention the underlying filtration for brevity. 
  The proofs, however, clearly mention the associated filtrations.%
}
For intuition, we can assume that $X_i$ represents the probability that the outcome of the coin-tossing protocol is $1$ after the first $i$ parties have broadcast their messages. 
Martingales have the unique property that if one computes the expected value of $X_j$, for $j>i$, at the end of time-step $i$, it is identical to the value of $X_i$. 
In this paper we shall consider martingales where, at the end of time-step $n$, we know for sure whether the event of interest has occurred or not.
That is, we have $X_n\in\zo$. 

A {\em stopping time} $\tau$ represents a time step $\in \{1,2,\dotsc,n\}$ where we stop the evolution of the martingale. 
The test of whether to stop the martingale at time-step $i$ is a function only of the information revealed so far. 
Furthermore, this stopping time need {\em not} be a constant. 
That is, for example, different transcripts of the coin-tossing protocol potentially have different stopping times. 


{\bfseries Our Martingale Problem Statement.} 
The inspiration of our approach is best motivated using a two-player game between, namely, the {\em martingale designer} and the {\em adversary}. 
Fix $n$ and $X_0$. 
The martingale designer presents a martingale $\ensuremath{{\mathcal X}}\xspace = (X_0,X_1,\dotsc,X_n)$ to the adversary and the adversary finds a stopping time $\tau$ that maximizes the following quantity. 
  $$\EX{\abs{X_\tau-X_{\tau-1}}}$$
Intuitively, the adversary demonstrates the most severe {\em susceptibility} of the martingale by presenting the corresponding stopping time $\tau$ as a witness. 
The martingale designer's objective is to design martingales that have less susceptibility. 
Our paper uses a geometric approach to inductively provide tight bounds on the least susceptibility of martingales for all $n\geq 1$ and $X_0\in[0,1]$, that is, the following quantity.
$$C_n(X_0) \defeq \inf_{\ensuremath{{\mathcal X}}\xspace} \; \sup_\tau \; \EX{\abs{X_\tau-X_{\tau-1}}}$$
This precise study of $C_n(X_0)$, for general $X_0\in[0,1]$, is motivated by natural applications in discrete process control as illustrated by the representative motivating problem. 
This paper, for representative applications of our results, considers $n$-processor distributed protocols and 2-party $n$-round protocols.
The stopping time witnessing the highest susceptibility shall translate into appropriate adversarial strategies. 
These adversarial strategies shall imply hardness of computation results. 

\input{contribution}
\input{prior}
\subsection{$L_2$ Gaps and their Tightness}
\label{sec:l2-gap} 

Finally, to demonstrate the versatility of our geometric approach, we measure large $L_2$-norm gaps in martingales.  
\begin{figure}[H]
	\begin{boxedminipage}{\linewidth}
	
		\begin{minipage}{0.5\linewidth}
			\input{fig-transform-def-l2} 
		\end{minipage}
	
		\begin{minipage}{0.5\linewidth}
			\input{fig-transform-intuit-l2}
		\end{minipage}
	\end{boxedminipage}
	\caption{Definition of transform of a curve $D$, represented by $T'(D)$. 
		The locus of the point $Q$ (in the right figure) defines the curve $T'(D)$.
	}
	\label{fig:transform-def-l2}
\end{figure}
\begin{theorem}
\label{thm:gap-main-2} 
Let $(X_0,X_1,\dotsc,X_n)$ be a discrete-time martingale such that
  $X_n\in\{0,1\}$. 
Then, the following bound holds.
    $$\sup_{\text{stopping time }\tau} \EX{\left({X_\tau-X_{\tau-1}}\right)^2} \geq D_n(X_0)\defeq \frac1n X_0(1-X_0)$$
Furthermore, for all $n\geq1$ and $X_0\in[0,1]$, there exists a martingale $(X_0,\dotsc,X_n)$ such that for any stopping time $\tau$, it has $\EX{\left({X_\tau-X_{\tau-1}}\right)^2} = D_n(X_0)$. 
\end{theorem}


\begin{proof}
    
We shall proceed by induction on $n$. 

\noindent{\bfseries Base Case $n=1$.} 
Note that in this case (see \figureref{transform-induct-bc}) the optimal stopping time is $\tau=1$. 
  $$\mathrm{opt}_1(X_0,2) = D_1(X_0) = (1-X_0)X_0^2 + X_0(1-X_0)^2 = X_0(1-X_0) \; .$$

\noindent{\bfseries General Inductive Step.} 
Let us fix $X_0=x$ and $n=d\geq 2$. 
We proceed analogous to the argument in \sectionref{large-gap-l1}. 
The adversary can either decide to stop at the child $j$ (see \figureref{jump2-induct} for reference) or continue to the subtree rooted at it to find a better stopping time.
 
\input{fig-induct-l2}

Overall, the adversary gets the following contribution from the $j$-th child 
  $$\max\left\{(x\p j-x)^2 , D_{d-1}(x\p j)\right\}$$
The adversary obtains a score that is at least the height of $Q$ in \figureref{induct-l2}. 
Further, a martingale designer can choose $t=2$, and $Z\p 1=P_1$ and $Z\p 2=P_2$ to define the optimal martingale. 
Similar to \theoremref{gap-main}, the scores corresponding to all possible stopping times in the optimal martingale are identical. 

We can argue that the height of $Q$ is the geometric-mean of the heights of $P_1$ and $P_2$. 
This observation defines the geometric transformation $T'$ in \figureref{transform-def-l2}.
For this transformation, we demonstrate that $D_n(X_0)=\frac1nX_0(1-X_0)$ is the solution to the recursion $D_n = {T'}^{n-1}(D_1)$ in \claimref{Characterising-Second-Norm}. 
\end{proof}

\begin{claim}
	\label{clm:Characterising-Second-Norm}
	Let $D_1$ be the curve defined as the zeros of the equation $Y=X(1-X)$ and for $n>1$, $D_n$ is obtained as applying the transformation $T'$, defined in \figureref{transform-def-l2}, to the curve $D_{n-1}$. We claim that for each $x\in [0,1]$, $D_n(x)=d_nx(1-x)$ where $d_n=\frac1n$. 
	\end{claim}

\begin{proof}
	We use induction on $n$ to prove that for each $x\in [0,1]$, we have $D_n(x)=d_nx(1-x)$ where $d_n=\frac1n$. Base case $n=1$, is obvious. Now, assuming that $D_n(x)=d_nx(1-x)$ where $d_n=\frac1n$, we will prove that $D_{n+1}(x)=d_{n+1}x(1-x)$ where $d_{n+1}=\frac1{n+1}$.
	Let's fix $x\in [0,1]$ and let $x_0$ and $x_1$ be respectively the smaller and larger root of the equation $d_nx^*(1-x^*)=(x-x^*)^2$. Then we have
	
	$$
	x_0=\frac{(2x+d_n)-\sqrt{d_n^2+4d_nx(1-x)}}{2(1+d_n)} \; ,
	$$
	$$
	x_1=\frac{(2x+d_n)+\sqrt{d_n^2+4d_nx(1-x)}}{2(1+d_n)} \; .
	$$
	Let $y_0=d_nx_0(1-x_0)$ and $y_1=d_nx_1(1-x_1)$, then we have the following relations: $$y_0=d_n\cdot\frac{(2x+d_n)-\sqrt{d_n^2+4d_nx(1-x)}}{2(1+d_n)}\cdot \frac{(2(1-x)+d_n)+\sqrt{d_n^2+4d_nx(1-x)}}{2(1+d_n)}$$
	
	$$y_1=d_n\cdot\frac{(2x+d_n)+\sqrt{d_n^2+4d_nx(1-x)}}{2(1+d_n)}\cdot\frac{(2(1-x)+d_n)-\sqrt{d_n^2+4d_nx(1-x)}}{2(1+d_n)}$$
	
	Now, according to the definition of transformation $T'$ in \figureref{transform-def-l2}, we have $D_{n+1}(x)=\sqrt{y_0y_1}$ and:
	
	\begin{align*}
		\sqrt{y_0y_1}&=\frac{d_n}{4(1+d_n)^2}\cdot\sqrt{\left(\left(2x+d_n\right)^2-\left(d_n^2+4d_nx(1-x)\right)\right)\left(\left(2(1-x)+d_n\right)^2-\left(d_n^2+4d_nx(1-x)\right)\right)} \\
		&=\frac{d_n}{4(1+d_n)^2}\cdot \sqrt{\left(4x^2(1+d_n)\right)\left(4(1-x)^2(1+d_n)\right)}\\
		&=\frac{d_n}{1+d_n}x(1-x)=\frac{\frac{1}{n}}{1+\frac{1}{n}}x(1-x)
		\\&=\frac{1}{n+1}x(1-x)
	\end{align*}
	\end{proof}  

Note that, for any martingale $(X_0,\dotsc,X_n)$ with $X_n\in\zo$, we have $\EX{\sum_{i=1}^n (X_i-X_{i-1})^2} = \EX{X_n^2-X_0^2} = X_0(1-X_0)$. 
Therefore, by an averaging argument, there exists a round $i$ such that $\EX{(X_i-X_{i-1})^2} \geq \frac1nX_0(1-X_0)$. 
\theoremref{gap-main-2} proves the existence of a martingale that achieves the lower-bound even for non-constant stopping times. 
This result provides a technique to obtain the upper-bound to $C_n(X)$ in \lemmaref{gap-lower-upper}.
 
\subsection{Alternate Proof for $U_{n+1} \succcurlyeq T(U_{n})$ }
\label{app:alt-proof}
\begin{proof}
	Recall that we defined $D_n$ as the zeros of the curve $Y = \frac{1}{n}X(1-X)$. 
	Since $U_n$ is defined by the zeros of the curve $Y = \sqrt{\frac{1}{n}X(1-X)}$, by squaring the $Y$-values for $U_n$, we can obtain the curve $D_n$. 
	This is illustrated in \figureref{un-dn-transform}. 
	Denote points on curve $U_n$ as $P_1 := (x_0,y_0)$, $P_2 := (x_1,y_1)$ and points on curve $D_n$ as $P'_1 := (x_0,y'_0)$, $P'_2 := (x_1,y'_1)$. 
	In the left-hand figure, let $\alpha := x - x_0$ and $\beta := x_1-x$, then $y_0 = \alpha $ and $y_1 = \beta$ and $Q = H.M. (\alpha,\beta)$. After squaring, in the right-hand figure $Q = (H.M.(\alpha,\beta))^2$. Note by definition of the transformation $T'$, we have that $Q' =G.M.(\alpha^2,\beta^2)$. We show that $G.M.(\alpha^2,\beta^2) \geq (H.M.(\alpha,\beta))^2$ as follows 
	\begin{align*}
	&& G.M.(\alpha^2,\beta^2) &\geq \left(H.M.(\alpha,\beta)\right)^2\\
	&& \left(G.M.(\alpha^2,\beta^2)\right)^{1/2} &\geq H.M.(\alpha,\beta)\\
	&& G.M.(\alpha,\beta) &\geq H.M.(\alpha,\beta),
	\end{align*}
	which is true by the standard $G.M. \geq H.M.$ inequality. 
	Now recall that the locus of the point $Q'$ defines the curve $T'(D_n) = D_{n+1}$ (From \claimref{Characterising-Second-Norm})
	and we know that $D_{n+1} = U^2_{n+1}$. Also, after squaring the $Y$-axis, the locus of the point $Q$ defines the curve $T^2(U_n)$, therefore we have just shown that $U^2_{n+1} \succcurlyeq T^2(U_{n})$, which means that $U_{n+1} \succcurlyeq T(U_{n})$.  
\end{proof}



Note that, for any martingale $(X_0,\dotsc,X_n)$ with $X_n\in\zo$, we have $\EX{\sum_{i=1}^n (X_i-X_{i-1})^2} = \EX{X_n^2-X_0^2} = X_0(1-X_0)$. 
Therefore, by an averaging argument, there exists a round $i$ such that $\EX{(X_i-X_{i-1})^2} \geq \frac1nX_0(1-X_0)$. 
\theoremref{gap-main-2} proves the existence of a martingale that achieves the lower-bound even for non-constant stopping times. 

This result provides an alternate technique to obtain the upper-bound to $C_n(X)$ in \lemmaref{gap-lower-upper}.   


\begin{figure}[H]
	\begin{boxedminipage}{\linewidth}
	
		\begin{minipage}{0.5\linewidth}
			\input{fig-un-l1} 
		\end{minipage}
	
		\begin{minipage}{0.5\linewidth}
			\input{fig-un-dn-l2}
		\end{minipage}
	\end{boxedminipage}
	\caption{Intuitive summary of the Proof of \claimref{our-induct-upper}. In the left-hand figure, we have $U_n$ and the locus of the point $Q$ defines the curve $T(U_n)$. Recall that $D_n$ is defined by the zeros of the curve $Y = \frac{1}{n}X(1-X)$.
		Intuitively we can say that $D_n = (U_n)^2$. By squaring the $Y$-axis in the left-hand figure, we get the right-hand figure. Since $D_{n+1}=T^{'}(D_n)$ (From \claimref{Characterising-Second-Norm})
	
		, and the locus of the point $Q'$ defines this curve, we only need to show that $Q'$ is always above $Q$ in the right-hand figure in order to prove our original claim. 
	}
	\label{fig:un-dn-transform}
\end{figure}


\section{Large Gaps in Martingales: A Geometric Approach}
\label{sec:large-gap-l1}


This section presents a high-level overview of our proof strategy. 
In the sequel, we shall assume that we are working with discrete-time martingales $(X_0,X_1,\dotsc,X_n)$ such that $X_n\in\zo$. 


Given a martingale $(X_0,\dotsc,X_n)$, its {\em susceptibility} is represented by the following quantity
  $$\sup_{\text{stopping time }\tau} \EX{\abs{X_\tau-X_{\tau-1}}}$$
Intuitively, if a martingale has high susceptibility, then it has a stopping time such that the gap in the martingale while encountering the stopping time is large. 
Our objective is to characterize the {\em least susceptibility} that a martingale $(X_0,\dotsc,X_n)$ can achieve. 
More formally, given $n$ and $X_0$, characterize
  $$C_n(X_0) \defeq \inf_{(X_0,\dotsc,X_n)} \sup_{\text{stopping time }\tau} \EX{\abs{X_\tau-X_{\tau-1}}}$$
Our approach is to proceed by induction on $n$ to exactly characterize the curve $C_n(X)$, and our argument naturally constructs the best martingale that achieves $C_n(X_0)$. 
\begin{enumerate}
\item We know that the base case is $C_1(X) = 2X(1-X)$ (see~\figureref{transform-induct-bc} for this argument). 
\item Given the curve $C_{n-1}(X)$, we identify a geometric transformation $T$ (see~\figureref{transform-def}) that defines the curve $C_n(X)$ from the curve $C_{n-1}(X)$. 
  \sectionref{gap-main} summarizes the proof of this inductive step that crucially relies on the geometric interpretation of the problem, which is one of our primary technical contributions. 
  Furthermore, for any $n\geq 1$, there exist martingales such that its susceptibility is $C_n(X_0)$. 
\item Finally, \sectionref{gap-lower-upper-proof}
proves that the curve $C_n(X)$  lies above the curve $L_n(X) \defeq \frac2{\sqrt{2n-1}}X(1-X)$ and below the curve $U_n(X) \defeq \frac1{\sqrt n} \sqrt{X(1-X)}$. 
\end{enumerate}



\subsection{Proof of \theoremref{gap-main}}
\label{sec:gap-main} 

Our objective is the following. 
\begin{enumerate}
\item Given an arbitrary martingale $(X,E)$, find the maximum stopping time in this martingale, \ie, the stopping time $\tau_{\max}(X,E,1)$. 
\item For any depth $n$ and bias $X_0$, construct a martingale that achieves the max-score. 
  We refer to this martingale as the {\em optimal} martingale. 
  A priori, this martingale need not be unique. 
  However, we shall see that for each $X_0$, it is (essentially) a unique martingale. 
\end{enumerate} 
We emphasize that even if we are only interested in the exact value of $C_n(X_0)$ for $X_0=1/2$, it is unavoidable to characterize $C_{n-1}(X)$, for all values of $X\in[0,1]$. 
Because, in a martingale $(X_0=1/2,X_1,\dotsc,X_n)$, the value of $X_1$ can be arbitrary. 
So, without a precise characterization of the value $C_{n-1}(X_1)$, it is not evident how to calculate the value of $C_n(X_0=1/2)$. 
Furthermore, understanding $C_n(X_0)$, for all $X_0\in[0,1]$, yields entirely new applications for our result. 


{\bfseries Base Case of $n=1$.} 
For a martingale $(X_0,X_1)$ of depth $n=1$, we have $X_1\in\zo$. 
Thus, without loss of generality, we assume that $E_1$ takes only two values (see~\figureref{transform-induct-bc}). 
Then, it is easy to verify that the max-score is always equal to $2X_0(1-X_0)$. 
This score is witnessed by the stopping time $\tau=1$. 
So, we conclude that 
  $\mathrm{opt}_1(X_0,1) = C_1(X_0) = 2X_0(1-X_0) $
\input{fig-transform-induct-bc}


{\bfseries Inductive Step. $n=2$ (For Intuition).}
For simplicity, let us consider finite martingales, \ie, the sample space $\Omega_i$ of the random variable $E_i$ is finite. 
Suppose that the root $X_0=x$ in the corresponding martingale tree has $t$ children with values $x\p1, x\p2, \dotsc,x\p t$, and the probability of choosing the $j$-th child is $p\p j$, where $j\in\{1,\dotsc,t\}$ (see~\figureref{jump2-induct}). 
\input{fig-jump2-induct}

Given a martingale $(X_0,X_1,X_2)$, the adversary's objective is to find the stopping time $\tau$ that maximizes the score $\EX{\abs{X_\tau - X_{\tau-1}}}$. 
If the adversary chooses to stop at $\tau=0$, then the score $\EX{\abs{X_\tau - X_{\tau-1}}}=0$, which is not a good strategy. 
So, for each $j$, the adversary chooses whether to stop at the child $x\p j$, or continue to a stopping time in the sub-tree rooted at $x\p j$. 
The adversary chooses the stopping time based on which of these two strategies yield a better score. 
If the adversary stops the martingale at child $j$, then the contribution of this decision to the score is $p\p j\abs{x\p j-x}$. 
On the other hand, if she does not stop at child $j$, then the contribution from the sub-tree is guaranteed to be $p\p jC_1(x\p j)$. 
Overall, from the $j$-th child, an adversary obtains a score that is at least $p\p j\max\left\{\abs{x\p j-x},C_1(x\p j)\right\}$. 
\input{fig-induct-c1c2} 



Let $h\p j\defeq \max\left\{\abs{x\p j-x},C_1(x\p j)\right\}$. 
We represent the points $Z\p j=(x\p j,h\p j)$ in a two dimensional plane. 
Then, clearly all these points lie on the solid curve defined by $\max\left\{\abs{X-x},C_1(X)\right\}$, see~\figureref{induct-c1c2}.

Since $(X,E)$ is a martingale, we have $x=\sum_{j=1}^t p\p jx\p j$ and the adversary's strategy for finding $\tau_{\max}$ gives us $\mathrm{max\textnormal{-}score}_1(X,E)= \sum_{j=1}^tp\p jh\p j$. 
This observation implies that the coordinate $(x,\mathrm{max\textnormal{-}score}_1(X,E)) = \sum_{j=1}^tp\p jZ\p j$. 
So, the point in the plane giving the adversary the maximum score for a tree of depth $n=2$ with bias $X_0=x$ lies in the {\em intersection} of the convex hull of the points $Z\p1,\dotsc,Z\p t$, and the line $X=x$. 
Let us consider the martingale defined in \figureref{induct-c1c2} as a concrete example. 
Here $t=4$, and the points $Z\p1, Z\p2, Z\p3, Z\p4$ lie on $\max\left\{\abs{X-x},C_1(X)\right\}$.
The martingale designer specifies the probabilities $p^{(1)}, p^{(2)}, p^{(3)}$, and $p^{(4)}$, such that $p^{(1)}x^{(1)} + \dotsi + p^{(4)}x^{(4)}=x$. 
These probabilities are not represented in \figureref{induct-c1c2}. 
Note that the point $\left( p^{(1)}x^{(1)} + \dots + p^{(4)}x^{(4)}, p^{(1)}h^{(1)} +\dots + p^{(4)}h^{(4)} \right)$ representing the score of the adversary is the point $p^{(1)}Z^{(1)}+\dots+p^{(4)}Z^{(4)}$. 
This point lies inside the convex hull of the points $Z^{(1)}, \dots ,Z^{(4)}$ and on the line $X = p^{(1)}x^{(1)} + \dots + p^{(4)}x^{(4)}=x$. 
The exact location depends on $p^{(1)},\dots,p^{(4)}$.

The point $Q'$ is the point with minimum height. 
Observe that the height of the point $Q'$ is at least the height of the point $Q$. 
So, in any martingale, the adversary shall find a stopping time that scores more than (the height of) the point $Q$. 

On the other hand, the martingale designer's objective is to reduce the score that an adversary can achieve. 
So, the martingale designer chooses $t=2$, and the two points $Z\p1=P_1$ and $Z\p2=P_2$ to construct the optimum martingale. 
We apply this method for each $x\in[0,1]$ to find the corresponding point $Q$. 
That is, the {\em locus of the point} $Q$, for $x\in[0,1]$, yields the curve $C_2(X)$. 

We claim that the height of the point $Q$ is the {\em harmonic-mean} of the heights of the points $P_1$ and $P_2$. 
This claim follows from elementary geometric facts. 
Let $h_1$ represent the height of the point $P_1$, and $h_2$ represent the height of the point $P_2$. 
Observe that the distance of $x - x_S(x) = h_1$ (because the line $\ell_1$ has slope $\pi - \pi/4$). 
Similarly, the distance of $x_L(x)-x=h_2$ (because the line $\ell_2$ has slope $\pi/4$). 
So, using properties of similar triangles, the height of $Q$ turns out to be
  $$ h_1 + \frac{h_1}{h_1+h_2}\cdot(h_2-h_1) = \frac{2h_1h_2}{h_1+h_2}.$$

This property inspires the definition of the geometric transformation $T$, see~\figureref{transform-def}.
Applying $T$ on the curve $C_1(X)$ yields the curve $C_2(X)$ for which we have $C_2(x) = \mathrm{opt}_2(x,1)$. 
\begin{figure}%
\begin{boxedminipage}{\linewidth}
\input{fig-transform-def} 
\input{fig-transform-intuit}
\end{boxedminipage}
\caption{Definition of transform of a curve $C$, represented by $T(C)$. 
  The locus of the point $Q$ (in the right figure) defines the curve $T(C)$.}
\label{fig:transform-def}
\end{figure}


{\bfseries General Inductive Step.} 
Note that a similar approach works for general $n=d\geq 2$. 
Fix $X_0$ and $n=d\geq 2$. 
We assume that the adversary can compute $C_{d-1}(X_1)$, for any $X_1\in[0,1]$. 

Suppose the root in the corresponding martingale tree has $t$ children with values $x\p1, x\p2,\dotsc,x\p t$, and the probability of choosing the $j$-th child is $p\p j$ (see~\figureref{jump2-induct}).
Let $(X\p j,E\p j)$ represent the martingale associated with the sub-tree rooted at $x\p j$. 

\input{fig-induct}


For any $j\in\{1,\dotsc,t\}$, the adversary can choose to stop at the child $j$. 
This decision will contribute $\abs{x\p j-x}$ to the score with weight $p\p j$. 
On the other hand, if she continues to the subtree rooted at $x\p j$, she will get at least a contribution of $\mathrm{max\text{-}score}_1(X\p j,E\p j)$ with weight $p\p j$. 
Therefore, the adversary can obtain the following contribution to her score
  $$p\p j\max\left\{\abs{x\p j-x},C_{d-1}(x\p j)\right\}$$

Similar to the case of $n=2$, we define the points $Z\p1,\dotsc,Z\p t$. 
For $n> 2$, however, there is one difference from the $n=2$ case. 
The point $Z\p j$ need not {\em lie on the solid curve}, but it can lie on or above it, \ie, they lie in the gray area of \figureref{induct}. 
This phenomenon is attributable to a suboptimal martingale designer producing martingales with suboptimal scores, \ie, {\em strictly above} the solid curve. 
For $n=1$, it happens to be the case that, there is (effectively) only one martingale that the martingale designer can design (the optimal tree).  
The adversary obtains a score that is at least the height of the point $Q'$, which is at least the height of $Q$.
On the other hand, the martingale designer can choose $t=2$, and $Z\p 1=P_1$ and $Z\p2=P_2$ to define the optimum martingale. 
Again, the locus of the point $Q$ is defined by the curve $T(C_{d-1})$. 


{\bfseries Conclusion.} 
So, by induction, we have proved that $C_n(X) = T^{n-1}(C_1(X))$. 
Additionally, note that, during induction, in the optimum martingale, we always have $\abs{x\p0-x}=C_{n-1}(x\p0)$ and $\abs{x\p1-x}=C_{n-1}(x\p1)$. 
Intuitively, the decision to stop at $x\p j$ or continue to the subtree rooted at $x\p j$ has identical consequence. 
So, by induction, {\em all stopping times} in the optimum martingale have score $C_n(x)$. 



\section{Preliminaries}
\label{sec:prelim}


We denote the {\em arithmetic mean} of two numbers $x$ and $y$ as $\mathrm{A.M.}(x,y)\defeq (x+y)/{2}$. 
The {\em geometric mean} of these two numbers is denoted by $\mathrm{G.M.}(x,y)\defeq \sqrt{x\cdot y}$ and their {\em harmonic mean} is denoted by $\mathrm{H.M.}(x,y)\defeq \left(\left(x^{-1}+y^{-1}\right)/2\right)^{-1}=2xy/(x+y)$. 

{\bfseries Martingales and Related Definitions.}
The {\em conditional expectation} of a random variable $X$ with respect to an event $\mathcal{E}$ denoted by  $\EX{X|\mathcal{E}}$, is defined as $\EX{X\cdot\1{\mathcal E}}/\probX{\mathcal{E}}$. 
For a discrete random variable $Y$, the conditional expectation of $X$ with respect to $Y$, denoted by $\EX{X|Y}$, is a random variable that takes value $\EX{X|Y=y}$ with probability $\probX{Y=y}$, where $\EX{X|Y=y}$ denotes the conditional expectation of $X$ with respect to the event $\{\omega\in \Omega|Y(\omega)=y\}$. 

Let $\Omega=\Omega_1\times\Omega_2\times\dotsi\times\Omega_n$ denote a sample space and $(E_1,E_2,\dotsc,E_n)$ be a joint distribution defined over $\Omega$ such that 
for each $i\in\{1,\dotsc,n\}$, $E_i$ is a random variable over $\Omega_i$. 
Let $X=\{X_i\}_{i=0}^{n}$ be a sequence of random variables defined over $\Omega$. 
We say that $X_j$ is $E_1,\dotsc,E_j$ measurable if there exists a function $g_j\colon \Omega_1\times\Omega_2\times\dotsi\times\Omega_j\to\mathbb{R} $ such that $X_j=g_j(E_1,\dotsc,E_j)$.
Let $X=\{X_i\}_{i=0}^{n}$ be a discrete-time martingale sequence with respect to the sequence $E=\{E_i\}_{i=1}^{n}$.
This statement implies that for each $i\in\{0,1,\dotsc,n\}$, we have 
$$\EX{X_{i+1}|E_1,E_2,\dotsc,E_i}=X_i$$
Note that the definition of martingale implies $X_i$ to be $E_1,\dotsc,E_i$ measurable for each $i\in\{1,\dotsc,n\}$ and $X_0$ to be constant.  
In the sequel, we shall use $\{ X=\{X_i\}_{i=0}^{n},E=\{E_i\}^n_{i=1} \}$ to denote a martingale sequence where for each $i=1,\dotsc,n$, $X_i\in [0,1]$, and $X_n\in \{0,1\}$. 
However, for brevity, we use $\left(X_0,X_1,\dotsc,X_n\right)$ to denote a martingale. 
Given a function $f\colon\Omega_1\times\Omega_2\times\dotsi\times\Omega_n\to\mathbb{R}$, if we define the random variable $Z_i\defeq \EX{f(E_1,\dotsc,E_n)|E_1,\dotsc,E_i}$, for each $i\in \{0,1,\dotsc,n\}$, then the sequence $Z=\{Z_i\}_{i=0}^{n}$ is a martingale with respect to $\{E_i\}_{i=1}^{n}$. 
This martingale is called the {\em Doob's martingale}. 


The random variable $\tau\colon\Omega \rightarrow \{0,1,\dotsc, n\}$ is called a stopping time if for each $k\in\{1,2,\dotsc,n\}$, the occurrence or non-occurrence of the event $\{\tau\leq k\} \defeq \{\omega\in \Omega| \tau(\omega)\leq k\}$ depends only on the values of random variables $E_1,E_2,\dotsc,E_k$.
Equivalently, the random variable $\1{\tau \leq k}$ is $E_1,\dotsc, E_k$ measurable. 
Let $\mathcal{S}(X,E)$ denote the set of all stopping time random variables over the  martingale sequence  $\{ X=\{X_i\}_{i=0}^{n},E=\{E_i\}^n_{i=1} \}$. 
For $ \ell \in \{1,2\}$, we define the {\em score} of a martingale sequence $(X,E)$ with respect to a stopping time $\tau$ in the $L_\ell$-norm as the following quantity.
$$\mathrm{score}_\ell(X,E,\tau) \defeq \EX{ \abs{X_\tau - X_{\tau-1}}^\ell }$$
We define the {\em max stopping time} as the stopping time that maximizes the score 
$$\tau_{\max}(X,E,\ell) \defeq \argmax_{\tau\in \mathcal{S}(X,E)} \mathrm{score}_\ell(X,E,\tau),$$ 
and the (corresponding) {\em $\mathrm{max\textnormal{-}score}$} as 
$$\mathrm{max\text{-}score}_\ell(X,E)\defeq\EX{|X_{\tau_{\max}}-X_{\tau_{\max-1}}|^\ell}$$



Let $A_n(x^{*})$ denote the set of all discrete time martingales $\{X=\{X_i\}_{i=0}^n,E=\{E_i\}_{i=1}^n\}$ such that $X_0=x^{*}$ and $X_n \in \{0,1\}$. 
We define {\em optimal score} as 
$$\mathrm{opt}_n(x^{*},\ell) \defeq \inf_{(X,E)\in A_n(x^{*})}\mathrm{max\textnormal{-}score}_\ell(X,E)$$
\input{fig-prelim-mart-tree}


{\bfseries Representing a Martingale as a Tree.}	
We interpret a discrete time martingale sequence $X=\{X_i\}_{i=0}^{n}$ defined over a sample space $\Omega=\Omega_1\times\dotsi\times\Omega_n$ as a tree of depth $n$ (see \figureref{prelim-mart-tree}). 
For $i=0,\dotsc,n$, any node at depth $i$ has $\abs{\Omega_{i+1}}$ children. 
In fact, for each $i$, the edge between a node at depth $i$ and a child at depth $(i+1)$ corresponds to a possible outcome that $E_{i+1}$ can take from the set $\Omega_{i+1}=\{x\p1,\dotsc,x\p t\}$. 



Each node $v$ at depth $i$ is represented by a unique path from root to $v$ like $(e_1,e_2,\dots,e_{i})$, which corresponds to the event $\{\omega\in \Omega|E_1(\omega)=e_1,\dots,E_{i}(\omega)=e_{i}\}$. 
Specifically, each path from root to a leaf in this tree, represents a unique outcome in the sample space $\Omega$. 


Any subset of nodes in a tree that has the property that none of them is an ancestor of any other, is called an {\em anti-chain}. 
If we use our tree-based notation to represent a node $v$, \ie,  the sequence of edges $e_1,\dots,e_i$ corresponding to the path from root to $v$, then any prefix-free subset of nodes is an anti-chain. 
Any anti-chain that is not a proper subset of another anti-chain is called a {\em maximal anti-chain}. 
A stopping time in a martingale corresponds to a {\em unique} maximal anti-chain in the martingale tree.%


\noindent{\bfseries Geometric Definitions and Relations.}
Consider curves $C$  and $D$ defined by the zeroes of $Y=f(X)$ and $Y=g(X)$, respectively, where $X\in[0,1]$. 
We restrict to curves $C$ and $D$ such that each one of them have exactly one intersection with $X=x$, for any $x\in [0,1]$.
Refer to \figureref{prelim-good-ex} for intuition. 
Then, we say $C$ is \emph{above} $D$, represented by $C \succcurlyeq D $, if,  for each $x\in [0,1]$, we have $f(x) \geq g(x)$.
\input{fig-prelim-good-ex}






\subsection{Prior Approaches to the General Martingale Problem} 
\label{sec:prior} 

Azuma-Hoeffding inequality~\cite{Azuma1967,Hoeffding63} states that if $\abs{X_i-X_{i-1}} = o(1/\sqrt n)$, for all $i\in\{1,\dotsc,n\}$, then, essentially, $\abs{X_n-X_0}=o(1)$ with probability 1.
That is, the final information $X_n$ remains close to the a priori information $X_0$. 
However, in our problem statement, we have $X_n\in\zo$. 
In particular, this constraint implies that the final information $X_n$ is significantly different from the a priori information $X_0$.
So, the initial constraint ``for all $i\in\{1,\dotsc,n\}$ we have $\abs{X_i-X_{i-1}} = o(1/\sqrt n)$'' must be violated. 
What is the probability of this violation? 

For $X_0=1/2$, Cleve and Impagliazzo~\cite{Cleve93martingales} proved that there exists a  round $i$ such that $\abs{X_i-X_{i-1}}\geq \frac1{32\sqrt n}$ with probability $1/5$. 
We emphasize that the round $i$ is a random variable and not a constant. 
However, the definition of the ``big jump'' and the ``probability to encounter big jumps'' both are exponentially small function of $X_0$.
So, the approach of Cleve and Impagliazzo is only applicable to constant $X_0\in(0,1)$.
Recently, in an independent work, Beimel~\etal~\cite{BeimelHMO17} demonstrate an identical bound for {\em weak martingales} (that have some additional properties), which is used to model multi-party coin-tossing protocols. 

For the upper-bound, on the other hand, Doob's martingale corresponding to the majority protocol is the only known martingale for $X_0=1/2$ with a small {\em maximum susceptibility}. 
In general, to achieve arbitrary $X_0\in[0,1]$, one considers coin tossing protocols where the outcome is $1$ if the total number of heads in $n$ uniformly random coins surpasses an appropriate threshold. 





\subsubsection{Detailed Discussion of Our Fail-stop Attack and Proofs}
\label{sec:attack-coin-toss}

Given a stopping time $\tau$ we shall associate the following score with it 
$$S'(\tau) \defeq  \sum^{n+1}_{i=1} \E_{x \in \Omega} \bigg\vert \E[ (X_i-D_{i-1}) \mathbbm{1}_{\tau = i} \vert E_1(x),E_2(x),\ldots, E_{i-1}(x)] \bigg\vert   
$$

Intuitively, this score correctly accounts for the increase and decrease in the probability of heads in every round $i$. \footnote{
	The score is slightly pessimistic, which, we argue, is also necessary. 
	Note that our expression is of the form $\abs{\EX{(X_i-D_{i-1}) \mathbbm{1}_{\tau = i} \vert\dotsc}}$. 
	One might \text{na\"ive}\xspace{}ly consider using the expression $\EX{\abs{X_i-D_{i-1}} \mathbbm{1}_{\tau = i} \vert\dotsc}$ instead. 
	However, there is an issue.   
	Suppose the stopping time stops the martingale for all children of $X_i$. 
	This strategy causes the outcome to deviate by $\abs{X_i-D_i}$, and our expression correctly accounts for it (because $\EX{X_{i+1}}=X_i$). 
	However, the alternative expression accounts for it incorrectly. 
	Basically, the alternative expression might not be translatable into a deviation of outcome by a fail-stop attacker. %
}

\begin{claim}
	\label{clm:D_abort_parent_cond}
	We prove the following two statements
	\begin{itemize}
		\item If $0\leq x^{(\ell)}\leq x_0\leq x\leq 1$, (where $x_0$ is the solution of equation $x-x_0=C^{'}_d(x_0)$ in $[0,1]$), $x-D \geq \frac{2}{3} \left(x-x^{(\ell)}\right) \geq 0$, and $ x-x^{(\ell)} \geq C^{'}_d(x^{(l)})$, then, 
		$$ x-D \geq \frac{1}{3}C^{'}_{d+1}(x) \; .$$
		\item If $0\leq x\leq x_1\leq x^{(r)}\leq 1$, (where $x_1$ is the solution of equation $x_1-x=C^{'}_d(x_1)$ in $[0,1]$), $D-x\geq \frac{2}{3}\left(x^{(r)}-x\right) \geq 0$, and $\left(x^{(r)}-x\right) \geq C^{'}_d(x^{(r)})$, then $$D-x\geq \frac{1}{3}C^{'}_{d+1}(x) \; .$$
	\end{itemize}
\end{claim}
\begin{proof}
We prove the first statement. Since for each $n$, $C^{'}_n(x)=C^{'}_n(1-x)$, the second part is implied by the first part by replacing $x,D,x^{(\ell)}$ with $1-x,1-D,x^{(r)}=1-x^{(\ell)}$.


In order to show the first part, it is sufficient to show that $\frac{2}{3}(x-x^{(\ell)}) \geq \frac{1}{3} C^{'}_{d+1}(x)$. 


We know that 
\begin{align*}
\frac{C^{'}_{d+1}(x)}{3} = \frac{2}{3}\cdot \frac{y_0y_1}{y_0+y_1} = \frac{2}{3}\cdot \frac{(x-x_0)(x_1-x)}{(x_1-x_0)} \; .
\end{align*}
We also know that 
\begin{align*}
&x-x^{(\ell)} \geq x-x_0 \; ,
\end{align*}
and, 
\begin{align*}
& x_1 - x_0 \geq x_1-x \; .
\end{align*}
Combining the above two relations we have 
\begin{align*}
(x-x^{(\ell)})(x_1 - x_0) &\geq (x-x_0)(x_1-x) 
\\(x-x^{(\ell)}) &\geq \frac{(x-x_0)(x_1-x)}{(x_1 - x_0)}
\\\frac{2}{3}(x-x^{(\ell)}) &\geq \frac{1}{3}\cdot \frac{2(x-x_0)(x_1-x)}{(x_1 - x_0)}
\\\frac{2}{3}(x-x^{(\ell)}) &\geq \frac{1}{3}C^{'}_{d+1}(x)
\\ \frac{2}{3}(x-x^{(\ell)}) &\geq \frac{1}{3}C^{'}_{d+1}(x)
\end{align*}
The proof follows from observing that $x-D\geq \frac{2}{3}(x-x^{(\ell)})$ from our assumption. 
\end{proof}

We will use specialized stopping time defined in \sectionref{unfair} to construct a stopping time for our fail-stop adversary. More formally, given a stopping time $\tau_1$ from \theoremref{specialized-stopping} such that $\sup_{\tau_1} \EX{\abs{X_{\tau_1}-X_{{\tau_1}-1}}} \geq C^{'}_n(X_0)$, there exists a stopping time $\tau_2$ such that $ S'(\tau_2) \geq \frac{1}{3}C^{'}_n(X_0)$. 

\begin{proof}
	The proof will proceed by induction on $n$. 
	\begin{enumerate}
		\item Base Case: For $n=1$, see \figureref{def-induct-bc}. 
		\input{fig-def-induct-bc}
		Recall that $C^{'}_1(x)=x(1-x)$. We have two cases 
		\begin{itemize}
			\item If $D \geq x$, we define $\tau_2$ as the stopping time that stops only at $0$. Then, $D(1-x) \geq x(1-x) \geq \frac{1}{3}x(1-x) \geq \frac{1}{3}C^{'}_1(x)$.
			\item If $D < x$, we define $\tau_2$ as the stopping time that stops only at $1$. Then $(1-D)x \geq x(1-x) \geq \frac{1}{3}x(1-x) \geq \frac{1}{3}C^{'}_1(x)$.
		\end{itemize}
	
		\item Assume the claim is true for $n=d$, see \figureref{def-induct-indhyp}. 
		\input{fig-def-induct-indhyp}
		For each edge $\left(x,x^{(j)}\right)$, if $\vert x-x^{(j)} \vert \geq C^{'}_d\left(x^{(j)}\right)$, then mark the edge. Let $$\mathtt{Marked}\defeq\{j: |x-x^{(j)}|\geq C^{'}_d(x^{(j)} \} \; .$$
		\\Without loss of generality, we assume that the nodes are \emph{in-order}. 
		
		Denote $\mathtt{Left}:=\{j:\ x^{(j)} \leq x \} \bigcap \mathtt{Marked}$ and $\mathtt{Right}:=\{j:\ x^{(j)} \geq x \}\bigcap \mathtt{Marked}$. 
		We analyze three possible cases 
		\begin{itemize}
		
			\item \textit{Case 1.} No edges are marked. This means that for all $j$, $\vert x-x^{(j)} \vert \leq C^{'}_d\left(x^{(j)}\right)$. 
			The adversarial strategy is to recurse on the underlying subtrees. 
			The overall deviation in this case is given by 
			$$\sum_j p^{(j)} C^{'}_d \left(x^{(j)}\right) \geq C^{'}_{d+1}\left(\sum_j p^{(j)} x^{(j)} \right) = C^{'}_{d+1}(x) \geq \frac{C^{'}_{d+1}(x)}{3} \; .$$
			
			\item  \textit{Case 2.} There exists a marked edge $j$ such that $D \leq \frac{x+2x^{(j)}}{3}$, and $x \geq x^{(j)}$, or $D \geq \frac{x+2x^{(j)}}{3}$, and $x^{(j)} \geq x$. The adversarial strategy is to abort at the parent.\\
			Suppose $D \leq \frac{x+2x^{(j)}}{3}$ and $x \geq x^{(j)}$, then $x-D \geq \frac{2}{3}(x-x^{(j)})$, the rest follows from \claimref{D_abort_parent_cond}. If $D \geq \frac{x+2x^{(j)}}{3}$ and $x^{(j)} \geq x$, then $D-x \geq \frac{2}{3}(x^{(j)}-x)$ and the rest again follows from \claimref{D_abort_parent_cond}. 
			\item  If \textit{Case 1} and \textit{Case 2} are not satisfied, then $\mathtt{Marked}$ is not empty but for any marked edge $j$ that $x\geq x^{(j)}$, we have $D>\frac{x+2x^{(j)}}{3}$ and for any marked edge $j$ that $x\leq x^{(j)}$, we have $D<\frac{x+2x^{(j)}}{3}$. Note that since $\mathtt{Marked}$ is not empty, at least one of the two sets $\mathtt{Left}$ and $\mathtt{Right}$ is not empty. Two cases can happen: 
			\begin{itemize}
				\item \textit{Case 3.1} Both $\mathtt{Left}$ and $\mathtt{Right}$ are non-empty. \\
				Then there exist $\ell^*$ and $r^*$ such that $\frac{x+2x^{(\ell^*)}}{3} < D < \frac{x+2x^{(r^*)}}{3}$ where $\ell^*:=\max_\ell \mathtt{Left}$ and $r^*:=\min_r \mathtt{Right}$. There are two sub-cases in this scenario : 
				\begin{itemize}
					\item \textit{Case 3.1.1} $\frac{x+2x^{(\ell^*)}}{3} < D \leq x$. \\
					The adversarial strategy is to follow the strategy of $\tau_1$. If the strategy of $\tau_1$ is to abort on left marked edges and recurse on the rest, then we have the following analysis: 

					For any $\ell \in \mathtt{Left}$, $\ell \leq \ell^*$, and we have 
					$$D-x^{(\ell)} > \frac{x+2x^{(\ell^*)}}{3} - x^{(\ell)} = \frac{x-x^{(\ell)} + 2(x^{(\ell^*)}-x^{(\ell)})}{3} \geq \frac{x-x^{(\ell)}}{3} > \frac{C^{'}_d(x^{(\ell)})}{3}  \; .$$

					The total deviation from aborting on the left marked edges is given by 
					\begin{align*}
					&\sum_{\ell \in \mathtt{Left}} p^{(\ell)} (D-x^{(\ell)}) \geq \sum_{\ell \in \mathtt{Left}} p^{(\ell)} \frac{x-x^{(\ell)}}{3} \geq  \sum_{\ell \in \mathtt{Left}} p^{(\ell)} \frac{C^{'}_d(x^{(\ell)})}{3} \; .
					\end{align*}
					The total deviation from recursing on the right edges and unmarked edges is given by 
				$$ \sum_{k \not\in \mathtt{Marked}} p^{(k)} \frac{C^{'}_d(x^{(k)})}{3} + \sum_{r \in \mathtt{Right}}p^{(r)}\frac{C^{'}_{d}(x^{(r)})}{3} \; , $$
				The overall deviation is 
				\begin{align*}
				&\sum_{\ell \in \mathtt{Left}} p^{(\ell)} (D-x^{(\ell)})+\sum_{r \in \mathtt{Right}}p^{(r)}\frac{C^{'}_{d}(x^{(r)})}{3} + \sum_{k \not\in \mathtt{Marked}} p^{(k)} \frac{C^{'}_d(x^{(k)})}{3} \\
				&\geq  \sum_{\ell \in \mathtt{Left}} p^{(\ell)} \frac{x-x^{(\ell)}}{3} +\sum_{r \in \mathtt{Right}}p^{(r)}\frac{C^{'}_{d}(x^{(r)})}{3} + \sum_{k \not\in \mathtt{Marked}} p^{(k)} \frac{C^{'}_d(x^{(k)})}{3} \\
				&\geq \frac{C^{'}_{d+1}(x)}{3}
				\end{align*}
			    In above, the last inequality holds due to the fact that $\tau_1$ is a specialized stopping time and martingale aborts on left marked edges and recurses on the rest which is exactly what $\tau_1$ suggests.
				\\If the strategy of $\tau_1$ is to abort on the right marked edges and recurse on the rest, then we have the following analysis.

				For any $r \in \mathtt{Right}$ such that $r \geq r^*$, we have 
				$$x^{(r)}-D>x^{(r)}-x > C^{'}_d(x^{(r)}) >\frac{C^{'}_d(x^{(r)})}{3} \; .$$
				The total deviation from aborting on the right marked edges is given by 
				\begin{align*}
				&\sum_{r \in \mathtt{Right}} p^{(r)} (x^{(r)}-D) \geq \sum_{r \in \mathtt{Right}} p^{(r)} \frac{x^{(r)}-x }{3} \geq \sum_{r \in \mathtt{Right}} p^{(r)} \frac{C^{'}_d(x^{(r)})}{3}
				\end{align*}
					The total deviation from recursing on the left edges and unmarked edges is given by 
				$$ \sum_{k \not\in \mathtt{Marked}} p^{(k)} \frac{C^{'}_d(x^{(k)})}{3} + \sum_{l \in \mathtt{Left}}p^{(l)}\frac{C^{'}_{d}(x^{(l)})}{3} \; .$$
				The overall deviation is 
				\begin{align*}
				&\sum_{r \in \mathtt{Right}} p^{(r)} (x^{(r)} -D )+\sum_{\ell \in \mathtt{Left}}p^{(l)}\frac{C^{'}_{d}(x^{(l)})}{3} + \sum_{k \not\in \mathtt{Marked}} p^{(k)} \frac{C^{'}_d(x^{(k)})}{3} \\
				&\geq  \sum_{r \in \mathtt{Right}} p^{(r)} \frac{x^{(r)} - x}{3} +\sum_{\ell \in \mathtt{Left}}p^{(\ell)}\frac{C^{'}_{d}(x^{(\ell)})}{3} + \sum_{k \not\in \mathtt{Marked}} p^{(k)} \frac{C^{'}_d(x^{(k)})}{3} \\
				&\geq \frac{C^{'}_{d+1}(x)}{3}
				\end{align*}
			    In above, the last inequality holds due to the fact that $\tau_1$ is a specialized stopping time and martingale aborts on right marked edges and recurses on the rest which is exactly what $\tau_1$ suggests.
			    
				\item \textit{Case 3.1.2.}  $x < D < \frac{x+2x^{(r^*)}}{3}$. 
					\\The adversarial strategy is the same as above : Follow the strategy of $\tau_1$. The analysis is almost identical to the one above due to symmetry. 				
				\end{itemize}
				\item \textit{Case 3.2.} Either $\mathtt{Left}$ or $\mathtt{Right}$ is empty. \\The adversarial strategy is to abort at all marked edges and recurse on all unmarked edges. \\Suppose $\mathtt{Right}$ is empty, then $\frac{x+2x^{(\ell^*)}}{3} < D < x$, where $\ell^*:=\max_\ell \mathtt{Left}$. The analysis is the same as in \textit{Case 3.1.1}. If $\mathtt{Left}$ is empty then the analysis is the same as \textit{Case 3.1.2}. \qedhere
			\end{itemize}
			
		\end{itemize}
	
	\end{enumerate}
\end{proof}

The above proof shows that $S'(\tau_2) \geq \frac{1}{3} C'_n(X_0)$. In order to estimate $C'_n(X_0)$, we define $L'_n(X)=\sqrt{\frac{2}{n+1}} X(1-X)$ and claim that $C'_n(X) \succcurlyeq L_n'(X)$. 

To prove our claim, we define the curve $G'_n(X)\defeq a'_nX(1-X)$ such that $a'_1=1$ and 
$a'_{n+1}= 2\left(\frac{\sqrt{a'^2_n+1}-1}{a'_n}\right)$ for $n\geq 1$ and we prove by induction that $C'_n \succcurlyeq G'_n$ for all $n$ as below: (analogous to the one shown for \lemmaref{gap-lower-upper}) 

{\bfseries Base Case of $n=1$.} 
Since, $C'_1(X)=G'_1(X) = X(1-X)$, it is obvious that $C'_1\succcurlyeq G'_1$. 

{\bfseries Inductive Argument.} 
Suppose we have $C'_n\succcurlyeq G'_n$. 
Then, we have $T(C'_n)\succcurlyeq T(G'_n)$ (by~\claimref{above-to-above}).
Note that $C'_{n+1}=T(C'_n)$. 
We know that $T(G'_n)\succcurlyeq G'_{n+1}$ (refer to \claimref{our-induct} ). 
Consequently, it follows that $C'_{n+1}\succcurlyeq G'_{n+1}$. 

So far, we have proved that $C'_n \succcurlyeq G'_n$ for all $n$. Recall that $G'_n(X)\defeq a'_nX(1-X)$ such that $a'_1=1$ and 
$a'_{n+1}= 2\left(\frac{\sqrt{a'^2_n+1}-1}{a'_n}\right)$. Now, by using \lemmaref{lowerbound-an}, we conclude that $a'_n\geq \sqrt{\frac{2}{n+1}}$. Thus, $C'_{n} \succcurlyeq L'_{n}$.
Now we can say that $S'(\tau_2) \geq \frac{1}{3} C'_n(X_0) \geq \frac{1}{3} L'_n(X_0)$. Further, any contribution to this score is attributable to one of the following four interactions: (1) \tuple{A^+,B} (\ie, adversarial Alice increasing the probability of heads by aborting), 
(2) \tuple{A^-,B}, 
(3) \tuple{A,B^+}, and 
(4) \tuple{A,B^-}. By an averaging argument, this implies that one of the parties can deviate the outcome of the other party by at least $\frac{1}{12}L'_n(X_0)$. This concludes our proof of \theoremref{unfairness}.


Similar to the previous section, \theoremref{unfairness} extends to $\omega$-faceted dice-rolling protocols by considering any subset $S\subseteq\{0,1,\dotsc,\omega-1\}$ of outcomes, and considering the final outcome being in $S$ as the interesting event for the martingale. 
 
\subsubsection{Discussion of Specialized Stopping Time - Proof of \theoremref{specialized-stopping}}
\label{sec:special-stopping-proof}

Before proving the theorem, we define the sequence of functions $\{g_n\}_{n=1}^\infty$ recursively. 
Let $A_n(X_0)$ 
be the set of 
all martingales $X=\left(X_0,X_1,\dotsc,X_{n}\right)$ 
such that for each $0\leq i\leq n-1$, $X_i\in[0,1]$ and $X_n\in\{0,1\}$. We define $$g_1(X_0):=\inf_{X\in A_1(X_0)}\sup_{\tau\in \mathcal{F}_1(X_0,X_1)}\E\vert X_{\tau}-X_{\tau-1} \vert$$ where $\mathcal{F}_1(X_0,X_1):=\{\tau_1, \tau_2\}$ and $\tau_1$ is an stopping time defined on martingale $(X_0,X_1)$ such that $\tau_1(X_0,X_1)=1$ if $X_1=0$ and $\tau_1(X_0,X_1)=\infty$ if $X_1=1$; and $\tau_2(X_0,X_1)=1$ if $X_1=1$ and $\tau_2(X_0,X_1)=\infty$ if $X_1=0$. Note that $\mathcal{F}_1(X_0,X_1)$ represents the set of all specialized stopping times in martingale $(X_0,X_1)$.
$A_1(X_0)$ consists of only one martingale and $\E\vert X_{\tau_1}-X_{\tau_1-1}\vert=\E\vert X_{\tau_2}-X_{\tau_2-1}\vert=X_0(1-X_0)$ which implies that $g_1(X_0)=X_0(1-X_0)$. 
We define 
$$g_n(X_0):=\inf_{X\in A_n(X_0)}\sup_{\tau\in \mathcal{F}_n(X_0,X_1,\dots,X_n)}\E\vert X_{\tau}-X_{\tau-1} \vert$$
where $\mathcal{F}_n(X_0,X_1,\dots,X_n)$ denotes the set of all specialized stopping times like $\tau$ defined on martingale $X=(X_0,X_1,\dots,X_n)$ which could be one of the following two cases:


Suppose $X_0=x$ and $X_1=x^{*}$. Then, let $x_0\in[0,1]$ be the solution of equation $x-x_0= g_{n-1}(x_0)$ and $x_1\in[0,1]$ be the solution of equation $x_1-x= g_{n-1}(x_1)$. 

\begin{enumerate}
	\item For all $x^{*}\leq x_0$, $\tau(x,x^{*},X_2,\dots,X_n)=1$ and for all $x^{*}> x_0$, $\tau(x,x^{*},X_2,\dots,X_n)=1+\tau^{'}(x^{*},X_2,\dots,X_n)$ for some $\tau^{'}\in \mathcal{F}_{n-1}(x^{*},X_2,\dots,X_n)$. This corresponds to
	the case that the specialized stopping time stops for all $x^{*}\leq x_0$ and recursively stops for all $x^{*}\geq x_0$ later.
	\item For all $x^{*}\geq x_1$, $\tau(x,x^{*},X_2,\dots,X_n)=1$ and for all $x^{*}< x_1$, $\tau(x,x^{*},X_2,\dots,X_n)=1+\tau^{'}(x^{*},X_2,\dots,X_n)$ for some $\tau^{'}\in \mathcal{F}_{n-1}(x^{*},X_2,\dots,X_n)$. This corresponds to
	the case that the specialized stopping time stops for all $x^{*}\geq x_1$ and recursively stops for all $x^{*}\leq x_1$ later.
\end{enumerate}      

To prove \theoremref{specialized-stopping}, it suffices to prove the following claim. 
\begin{claim}
	\label{clm:specialized-main-claim}
	Let $C'_1(x)=x(1-x)$ and the 
	curve $C'_n$ is achieved by applying 
	transformation $T$ on the curve $C'_{n-1}$ i.e. $C'_n=T\left(C'_{n-1}\right)$. Then, we have $g_n(x)=C'_n(x)$ for any $x\in[0,1]$.
\end{claim}
We first describe the intuitive idea behind the proof and then give a technical proof afterwards. \newline 
{\bfseries Proof Sketch.}
We use induction on $n$ to prove the claim. For $n=1$ and for each $x\in [0,1]$, we have $g_1(x)=x(1-x)=C'_1(x)$. 
Now, we assume that for each $x\in [0,1]$, $g_n(x)=C'_n(x)$.
Since $C'_{n+1}(X)=T\left(C'_n(X)\right)$, it suffices to prove that $g_{n+1}(X)=T\left(g_n(X)\right)$ because it implies that $g_{n+1}(X)= T\left(g_n(X)\right)=T\left(C'_n(X)\right)=C'_{n+1}(X)$. 
Let us consider martingale $(X_0,X_1,\dots,X_n, X_{n+1})$ where $X_0=x$ and $X_1\in \{x^{(1)},\dots,x^{(t)}\}$. According to the induction hypothesis, the adversary is guaranteed to get $g_n(x^{(j)})=C'_n(x^{(j)})$ as the score in any martingale of depth $n$ if she chooses an appropriate stopping time in $\mathcal{F}_n(x^{(j)},X_2,\dots,X_{n+1})$. 

We define left marked edges as the set $\{j: x^{(j)} \leq x, \text{ and, } |x-x^{(j)}|\geq C^{'}_{n}(x^{(j)}) \}$ and right marked edges as the set $\{j: x^{(j)} \geq x, \text{ and, } |x-x^{(j)}|\geq C^{'}_{n}(x^{(j)}) \}$.
Now, to prove that $g_{n+1}(X) = T\left(g_n(X)\right)$ it suffices to show that in any arbitrary martingale in $A_{n+1}(x)$, the maximum score that could be achieved by either stopping the martingale at only left marked edges at time $1$ or stopping the martingale at only right marked edges at time $1$, is always guaranteed to be greater than or equal to $T(g_n(x))=T(C'_n(x))=C'_{n+1}(x)$.   
In \figureref{special-intuit}, we are considering a martingale $(x,X_1,\dots,X_n,X_{n+1})$ such that $X_1$ can take only two values either $x_{l}$ or $x_{r}$ with probabilities $p_l$ and $p_r$ respectively. Note that $x_{l} \leq x_S(x)$ and $x_L(x) \leq x_{r}$. Any specialized stopping time $\tau$ either stops at $x_l$ and continues at $x_r$ or stops at $x_r$ and continues at $x_l$. Here, the curve $C'_{n}$ represents the points $(x,g_n(x))$ for $0\leq x\leq 1$.
According to the induction hypothesis, in martingale $(x_l, X_2, \dots, X_n)$, the score $g_n(x_l)$ is guaranteed to be achieved (so the contribution of score when martingale doesn't stop at this edge is $p_lg_n(x_l)$) but if martingale stops at time $1$ at edge $(x,x_l)$, then the contribution of score for this edge is $p_l|x-x_l|$. A similar thing can be said about $x_r$. 
We can observe that while the point $Q^{''}$ (which is the intersection of line $D_lU_r$ with line $X=x$ and its height corresponds to the score achieved when martingale stops at $x_r$ and continues at $x_l$) lies below the point $Q=(x,g_{n+1}(x))$ (which is the intersection of line $P_1P_2$ with line $X=x$ and its height corresponds to $T(g_n(x))$), the point $Q^{'}$ (which is the intersection of line $U_lD_r$ with line $X=x$ and its height corresponds to the score achieved by stopping martingale at $x_l$ and allowing it to continue at $x_r$) is above the point $Q$. Observe that the maximum of the two scores achieved in these two strategies is always greater than or equal to $T(g_n(x))$. Moreover, if $x_S$ is chosen as $x_l$
and $x_L$ is chosen as $x_r$, then $Q=Q^{'}=Q^{''}$ and the value $T(C'_{n})(x)$ can be achieved for some martingale. This means that $g_{n+1}(x)=T(g_n(x))=T(C'_n(x))=C'_{n+1}(x)$ for any $x\in [0,1]$.           



\subsection{Fail-stop Attacks on Coin-tossing/Dice-rolling Protocols}
\label{sec:unfair}

A {\em two-party $n$-round bias-$X_0$ coin-tossing protocol} is an interactive protocol between two parties who send messages in alternate rounds, and $X_0$ is the probability of the coin-tossing protocol's outcome being heads. 
{\em Fair computation} ensures that even if one of the parties aborts during the execution of the protocol, the other party outputs a (randomized) heads/tails outcome. 
This requirement of guaranteed output delivery is significantly stringent, and Cleve~\cite{STOC:Cleve86} demonstrated a computationally efficient attack strategy that alters the output-distribution by $O(1/n)$, \ie, any protocol is $O(1/n)$ unfair. 
Defining fairness and constructing fair protocols for general functionalities has been a field of highly influential research~\cite{STOC:GHKL08,EC:GorKat10,C:BLOO11,TCC:AshLinRab13,TCC:Asharov14,makriyannis2014classification,TCC:ABMO15}. 
This interest stems primarily from the fact that fairness is a desirable attribute for secure-computation protocols in real-world applications. 
However, designing fair protocol even for simple functionalities like (bias-$1/2$) coin-tossing is challenging both in the two-party and the multi-party setting. 
In the multi-party setting, several works~\cite{ABCGM85,C:BeiOmrOrl10,TCC:AloOmr16} explore fair coin-tossing where the number of adversarial parties is a constant fraction of the total number of parties. 
For a small number of parties, like the two-party and the three-party setting, constructing such protocols have been extremely challenging even against computationally bounded adversaries~\cite{TCC:MorNaoSeg09,STOC:HaiTsf14,SODA:BHLT17}. 
These constructions (roughly) match Cleve's $O(1/n)$ lower-bound in the computational setting.


In the information-theoretic setting, Cleve and Impagliazzo~\cite{Cleve93martingales} exhibited that any two-party $n$-round bias-$1/2$ coin-tossing protocol are $\frac1{2560\sqrt n}$ unfair. 
In particular, their adversary is a fail-stop adversary who follows the protocol honestly except aborting prematurely. 
In the information-theoretic commitment-hybrid, there are two-party $n$-round bias-1/2 coin-tossing protocols that have $\approx 1/\sqrt n$ unfairness~\cite{STOC:Blum83,ABCGM85,STOC:Cleve86}. 
This bound matches the lower-bound of $\Omega(1/\sqrt n)$ by Cleve and Impagliazzo~\cite{Cleve93martingales}. 
It seems that it is necessary to rely on strong computational hardness assumptions or use these primitives in a non-black box manner to beat the $1/\sqrt n$ bound~\cite{TCC:DLMM11,TCC:HaiOmrZar13,TCC:DacMahMal14,BeimelHMO17}. 

We generalize the result of Cleve and Impagliazzo~\cite{Cleve93martingales} to all 2-party $n$-round bias-$X_0$ coin-tossing protocols (and improve the constants by two orders of magnitude). 
For $X_0=1/2$, our fail-stop adversary changes the final outcome probability by $\geq \frac1{24\sqrt2}\cdot \frac1{\sqrt{n+1}}$.
\begin{theorem}[Fail-stop Attacks on Coin-tossing Protocols]
\label{thm:unfairness} 
For any two-party $n$-round bias-$X_0$ coin-tossing protocol, there exists a fail-stop adversary that changes the final outcome probability of the honest party by at least $\frac1{12}C'_n(X_0)\geq \frac1{12} L'_n(X_0) \defeq\frac1{12} \sqrt{\frac2{n+1}} X_0(1-X_0)$, where $C'_1(X)\defeq X(1-X)$ and $C'_n(X)\defeq {T}^{n-1}(C'_1(X))$. 
\end{theorem}
This theorem is {\em not} a direct consequence of \theoremref{gap-main}. 
The proof relies on an entirely new inductive argument; however, the geometric technique for this recursion is similar to the proof strategy for \theoremref{gap-main}. 

Before proving the above theorem, we provide some insight into our approach. Let $\Pi = \left\langle A,B\right\rangle$ be an $n$-round bias-$X_0$ coin-tossing protocol between Alice and Bob. 
Without loss of generality, assume that Alice sends messages in rounds $1,3,\dotsc$, and Bob sends messages in rounds $2,4,\dotsc$. 
The random variable $(E_1,\dotsc,E_i)$ represents the partial transcript of the protocol at the end of round $i$. 
The random variable $X_i$ represents the expected probability of heads at the end of the protocol execution conditioned on the current partial transcript at the end of round $i$. 
Note that $(X=(X_i)_{i=0}^n,E=(E_i)_{i=1}^n )$ is a Doob's martingale. 

We construct fail-stop adversaries only. 
Suppose Alice has to send the message in round $(i+1)$ (\ie, $i$ is even), but she aborts. 
Then, the {\em defense} $D_i$ is the probability of Bob outputting heads. 
Similarly, suppose Bob is supposed to send the message in round $(i+1)$ (\ie, $i$ is odd), but he aborts. 
Then, we define $D_i$ as the probability of Alice outputting heads. 
Note that $D_i$ is $(E_1,\dotsc,E_i)$ measurable. 
In other words, the defense of round $i$ is a function only of the partial transcript at the end of that round.

The high-level idea of our construction of a good fail-stop attack is the following. 
We shall use a stopping time $\tau$ to identify appropriate partial transcripts of $\Pi$ to abort. 
Suppose we have already generated a partial transcript $(e_1,\dotsc,e_i)$ (refer~\figureref{prelim-mart-tree}), and the next messages that are possible are $e_{i+1}\in\Omega_{i+1}$. 
Suppose $\tau$ stops the martingale at $e_{i+1} = e\p j$. 
Note that $X_{i+1}=x\p j$ is the probability of heads conditioned on the transcript $\Pi$ being $(e_1,\dotsc,e_i,e_{i+1}=e\p j)$. 
Further, the defense of the other party is $D_i$. 

If $i$ is even, then Alice is supposed to send the $(i+1)$-th message. 
So, the stopping time $\tau$ is indicating Alice to abort if the message in the next round she plans to send is $e\p j$. 
Suppose $x\p j\leq D_i$. 
Then, if Alice aborts when her next message is $e\p j$, then she is increasing the probability of heads by $p\p j\abs{x\p j-D_i}$. 

So, the conclusion is the following. 
If $i$ is even and $x\p j\leq D_i$ then the advice of $\tau$ will be {\em helpful} to an adversarial Alice who is interested in increasing the probability of heads, say $A^+$. 
If $x\p j>D_i$, then the advice of $\tau$ will be helpful to an adversarial Alice who is interested in reducing the probability of heads, say $A^-$. 
Similarly, when $i$ is odd, the advice of $\tau$ is useful to either $B^+$ or $B^-$.



{\bfseries Specialized Stopping Time.} 
For this discussion, let us consider \figureref{transform-def}. 
Note that if $X_1$ is very small (that is, $X_1 < x_S(x)$) or $X_1$ is very large (that is, $X_1> x_L(x)$), then the adversary aborts. 
Furthermore, if $X_1$ is close to $X_0$  (that is, $X_1 \in [x_S(x),x_L(x)]$), then the adversary does not abort and recursively constructs the optimum stopping time. 
In particular (refer to \figureref{jump2-induct} and \figureref{induct-c1c2}) if there exists $x\p j$ and $x\p{j'}$ such that $x\p j< x_S(x)$ and $x\p{j'}>x_L(x)$ then the adversary aborts in both these two cases. 
This step is crucial to arguing that the point $Q'$ is higher than the point $Q$ in \figureref{induct-c1c2}, which, in turn, is key to the transformation definition. 


However, if a stopping time stops the martingale at high as well as low values of $X_i$ then it is not evident how to to translate the susceptibility corresponding to this stopping time into output-bias achieved by a fail-stop adversary. 
So, we restrict to {\em specialized stopping times} with the following property (we use \figureref{transform-def} for reference in the following definition). 
\begin{boxedalgo}
	\label{def:special-def}
Fix $n$ and $X_0$. 
Pick any $i=n-d$ and fix $E_1=e_1,\dotsc,E_i=e_i$. 
Let $x=(X_i|E_1=e_1,\dotsc,E_i=e_i)$. 
\begin{itemize}
\item Either, the specialized stopping time stops for all $X_{i+1}< x_S(x)$ and recursively stops $X_{i+1}\geq x_S(x)$ later, or 
\item The specialized stopping time stops all $X_{i+1}>x_L(x)$ and recursively stops $X_{i+1}\leq x_L(x)$ later. 
\end{itemize}
\end{boxedalgo} 
Now, it is not evident whether specialized stopping times also have high susceptibility. 


\input{fig-special-intuit}

\begin{theorem}
	\label{thm:specialized-stopping}
	Let $(X_0,X_1,\dotsc,X_n)$ be a discrete-time martingale such that $X_i\in[0,1]$, for all $i\in\{1,\dotsc,n\}$, and $X_n\in\{0,1\}$. 
	Then, the following bound holds.
	$$\sup_{\text{specialized stopping time }\tau} \EX{\abs{X_\tau-X_{\tau-1}}} \geq C^{'}_n(X_0),$$

	where $C'_1(X)\defeq X(1-X)$ and $C'_n(X)\defeq {T}^{n-1}(C'_1(X))$.
\end{theorem}
Let us start with the base case $n=1$. 
Note that a specialized stopping time cannot stop the martingale at both low and high $X_1$. 
So, we consider stopping times $\tau\colon\Omega\to\{1,\dotsc,n,\infty\}$, where $\tau=\infty$ for a full transcript indicates that the adversary did not abort. 
Note that a specialized stopping time can either stop the martingale when $X_1=0$ or $X_1=1$.
In either of these two cases, the susceptibility is $C'_1(X_0) = X_0(1-X_0)$. 

For $n\geq 2$, we show that the recursive definition of the transform $T$ continues to hold even for specialized stopping time (refer \figureref{special-intuit} for intuition). 
Note that the adversary chooses the stopping time that achieves the highest susceptibility. 
So, the maximum height of $Q'$ and $Q''$ in \figureref{special-intuit} is greater than the height of $Q$. 
We emphasize that this proof crucially relies on the fact that $C'_{n-1}(X)$ lies below the curve $Y =\min\{X,1-X\}$. 
So, our result holds because $C'_1(X)$ lies below the curve $Y =\min\{X,1-X\}$.
\sectionref{special-stopping-proof} presents the full proof. 

Finally, we translate the susceptibility of a specialized stopping time into output-bias that a fail-stop adversary can enforce. 
\sectionref{attack-coin-toss} provides the full proof of \theoremref{unfairness}.



\subsubsection{Black-box Separation Results}
Gordon and Katz~\cite{EC:GorKat10} introduced the notion of {\em $1/p$-unfair secure computation} for a fine-grained study of fair computation of functionalities. 
In this terminology, \theoremref{unfairness} states that $\frac{c}{\sqrt{n+1}}X_0(1-X_0)$-unfair computation of a bias-$X_0$ coin is impossible for any positive constant $c< \frac{\sqrt 2}{12}$ and $X_0\in[0,1]$. 

Cleve and Impagliazzo's result~\cite{Cleve93martingales} states that $\frac{c}{\sqrt n}$-unfair secure computation of the bias-$1/2$ coin is impossible for any positive constant $c< \frac1{2560}$. 
This result on the hardness of computation of fair coin-tossing was translated into black-box separations results. 
These results~\cite{TCC:DLMM11,TCC:HaiOmrZar13,TCC:DacMahMal14}, intuitively, indicate that it is unlikely that $\frac{c}{\sqrt n}$-unfair secure computation of the bias-$1/2$ coin exists, for $c< \frac1{2560}$, relying solely on the black-box use of one-way functions. 
We emphasize that there are several restrictions imposed on the protocols that these works~\cite{TCC:DLMM11,TCC:HaiOmrZar13,TCC:DacMahMal14} consider; detailing all of which is beyond the scope of this draft. 
Substituting the result of \cite{Cleve93martingales} by \theoremref{unfairness}, extends the results of \cite{TCC:DLMM11,TCC:HaiOmrZar13,TCC:DacMahMal14} to general bias-$X_0$ coin-tossing protocols. 
\begin{corollary}[Informal: Black-box Separation]
\label{corol:bb-sep} 
For any $X_0\in[0,1]$ and positive constant $c< \frac{\sqrt 2}{12}$, the existence of $\frac{c}{\sqrt{n+1}}X_0(1-X_0)$-unfair computation protocol for a bias-$X_0$ coin is black-box separated from the existence of one-way functions (restricted to the classes of protocols considered by \cite{TCC:DLMM11,TCC:HaiOmrZar13,TCC:DacMahMal14}).
\end{corollary}

\input{subsec-attack-coin-toss.tex}
\input{subsec-stoppingtime.tex}





