%% Theory of Computing
%% File: v018a013.tex
%% Publication date: June 7, 2022
%% Authors: Maya Leshkowitz
%
%
%
%

%

%
%

%
%

\documentclass{toc}

\tocdetails{%
volume=18, number=13, year=2022, firstpage=1,
specissue={\randomBI},           %
received={September 19, 2018},
revised={January 15, 2022},
published={June 7, 2022},
	%
	%
doi={10.4086/toc.2022.v018a013}
}
	%

\runningtitle{Round Complexity Versus Randomness Complexity in Interactive Proofs}
\tocpdftitle{Round Complexity Versus Randomness Complexity in Interactive Proofs}
\runningauthor{Maya Leshkowitz}
\copyrightauthor{Maya Leshkowitz}
\tocpdfauthor{Maya Leshkowitz}

\usepackage{microtype}%

%
%
%
%
%
%
%
\usepackage{amsmath}
\usepackage[titletoc,title]{appendix} %
\usepackage{graphicx}
%
%
%
%
%
%
%
%
%
%
\usepackage{enumitem}
\hypersetup{colorlinks=true,linkcolor=blue,citecolor=blue}
%
\usepackage{mathtools}

%
%
\newcommand{\mmm}[1]{\begin{align*}#1\end{align*}}
\newcommand{\etal}{\emph{et al.}}
\newcommand{\aka}{a.\,k.\,a.}  %

%
\newcounter{tag}[section]
\newcommand{\eqtag}[1]{\stepcounter{tag}\tag{\thesection.\thetag} \label{#1}}
\newcommand{\mathdot}{\ensuremath{\;\text{.}}}



%

 \DeclareMathOperator{\poly}{poly}     %

%
\newcommand{\ccNP}{\cclass{NP}} \newcommand{\np}{\ccNP}
\newcommand{\ccp}{\cclass{P}}
\newcommand{\BPP}{\cclass{BPP}}  \newcommand{\bpp}{\BPP}
\newcommand{\ccMA}{{\cclass {MA}}}
\newcommand{\coNP}{\cclass{coNP}} %
\newcommand{\ccAM}{{\cclass {AM}}}
\newcommand{\ccIP}{{\cclass {IP}}}
\newcommand{\coAM}{\cclass{coAM}}    %
\newcommand{\coAMTIME}{\cclass{coAM-TIME}}    %
\newcommand{\NTIME}{\cclass{NTIME}}    %
\newcommand{\AMTIME}{\cclass{AM-TIME}}    %
\newcommand{\COAMTIME}{\cclass{coAM-TIME}}    %
\newcommand{\TIME}{\cclass{TIME}}    %
%
\newcommand{\ccpspace}{\cclass{PSPACE}}
%

%
\newcommand{\STOC}{ACM Symposium on the Theory of Computing}
\newcommand{\FOCS}{IEEE Symposium on Foundations of Computer Science}
\newcommand{\JCSS}{Journal of Computer and System Science}
\newcommand{\JACM}{Journal of the ACM}
\newcommand{\CACM}{Communications of the ACM}
\newcommand{\SICOMP}{SIAM Journal on Computing}
\newcommand{\JofC}{Journal of Cryptology}
\newcommand{\ccIPL}{Information Processing Letters}
\newcommand{\LNCS}[1]{Lecture Notes in Computer Science (Vol.~{#1})} %
\newcommand{\Crypto}{Crypto} %
\newcommand{\CRYPTO}[1]{\Crypto{#1}}
\newcommand{\PODC}{ACM Symposium on Principles of Distributed Computing}

\newcommand{\Cnote}[1]{\begin{center}\fbox{\begin{minipage}{35em}
				{ {#1}} \end{minipage}}\end{center}}
%
\newtheorem{construction}[theorem]{Construction} 
\newtheorem*{claim*}{Claim}
\newtheorem{innercustomthm}{Theorem}
\newenvironment{customthm}[1]
{\renewcommand\theinnercustomthm{#1}\innercustomthm} %
{\endinnercustomthm}  %



%
\newcommand{\prolen}{$O\left(r(n)/{\log r(n)}\right)$}
\newcommand{\wgt}[1]{w(#1)}
\newcommand{\wgtc}[1]{w'(#1)}
\newcommand{\orgP}{$P_{0}$}
\newcommand{\newP}{$P$}
\newcommand{\clP}{$\widetilde{P}$}
\newcommand{\clPo}{$\widetilde{P_0}$}
\newcommand{\orgV}{$V_0$}
\newcommand{\newV}{$V$}
\newcommand{\rw}[1]{W^{\widetilde{P}}(#1)}
\newcommand{\PTree}{$T_{P,V}$}
\newcommand{\oPT}{$T_{P_0,V_0}$}
%
\newcommand{\oPTi}[1]{T_{P_0,V_0}^{#1}} %
%
\newcommand{\oET}{E_{P_0,V_0}} %

%
\newcommand{\cET}{E_{\widetilde{P}}} %
%
\newcommand{\clPT}{T_{\widetilde{P_0},V_0}} %
%
\newcommand{\clPTn}{T_{\widetilde{P},V}} %
\newcommand{\LPr}[1]{L^{\widetilde{P}}(#1)}
\newcommand{\gfunc}[1]{g(#1)}
%
\newcommand{\comp}{9/10} %
%
\newcommand{\sound}{1/10} %
\newcommand{\Leaf}[1]{L^{1}(#1)}
\newcommand{\rand}{r(n)}



%

\begin{document}
	
\begin{frontmatter}
		%
  \title{Round Complexity Versus Randomness Complexity in Interactive Proofs\titlefootnote{An extended abstract of this paper appeared in the Proceedings of \href{https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.49}{%
Proceedings of the 22nd International Conference on Randomization
and Computation (RANDOM'18)} ~\cite{conf-version}.}}
\author[leshkowitz]{Maya Leshkowitz\thanks{Work done while the author was at Weizmann Institute of Science}}

%
\begin{abstract}
Consider an interactive proof system for some set $S$ 
that has randomness complexity $r(n)$ for instances of length $n$, and arbitrary round complexity.  We show 
a public coin interactive proof system for $S$
of round complexity $O(r(n)/\log r(n))$. Furthermore, the randomness complexity is preserved up to a constant factor, and the resulting interactive proof system has perfect completeness.	
\end{abstract}

\tockeywords{complexity theory, interactive proofs}
\tocacm{F.1.3}
\tocams{68Q10, 68Q15, 68Q87}


\iffalse %
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\tocarxivcategory{cs.CC}

\fi %

\end{frontmatter}

\newpage
\tableofcontents
\newpage

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

%
%
%
%
%

The notion of interactive proof systems,
put forward by Goldwasser, Micali, Rackoff~\cite{GMR} and Babai~\cite{B},
and the demonstration of their power by 
Lund, Fortnow, Karloff, Nisan~\cite{LFKN} and Shamir~\cite{S90}
are among the most celebrated achievements of complexity theory. %

Loosely speaking, interactive proof systems capture the most general
way in which one party can efficiently verify claims made by another,
more powerful, party. The definition of interactive proof systems
generalizes the traditional notion of a proof system
(indeed, an $\ccNP$-proof system),
by allowing both \emph{interaction} and \emph{randomness}. 

It is well known that both interaction and randomness are inherent 
to the power of interactive proof systems, where here we mean
the extra power above that of $\ccNP$-proof systems.
Interactive proofs with no randomness can be easily
transformed into $\ccNP$-proof systems, 
whereas randomized non-interactive proofs, 
captured by the class $\ccMA$ (defined by Babai~\cite{B}),
are essentially the randomized version of $\ccNP$.
%
%
%

Both \emph{interaction} and \emph{randomness} are quantitative notions;
that is, one talks of the ``amount of interaction,''
which is commonly associated with the (total) number 
of messages exchanged (\aka\ number of \emph{rounds}), 
and of the amount of randomness (\aka\ \emph{randomness complexity}). 
While the previous paragraph refers to the qualitative question
and asserts that both interaction and randomness are essential,
a finer study of the quantitative question is called for;
that is, it is natural to ask about the necessary amount 
of interaction and randomness in various interactive proof systems.

The study of round complexity in interactive proof systems has some 
%
well-known   %
results:
%
Babai introduced public coin interactive proofs (\aka\ Arthur--Merlin proofs) in~\cite{B}, and showed that the round complexity of any
%
bounded-round  %
Arthur--Merlin proof can be reduced to $\ccAM$ (a
%
two-message  %
Arthur--Merlin proof). Babai and Moran extended this result in~\cite{BM} and showed that the round complexity of Arthur--Merlin proofs 
for instances of length $n$
can be reduced by %
any  %
constant factor~\cite{BM}, %
assuming we keep at least one $\ccAM$ alternation. %
The public coin transformation of Goldwasser and Sipser~\cite{GS}
(which essentially preserves the number of rounds)
extends this result to %
private-coin   %
interactive proof systems. 
It is also known that a stronger round reduction is quite unlikely.
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
This is the case due to a combination of results reviewed below
in the paragraph titled ``conditional tightness.''

In contrast, we are only aware of one study that focuses
on the randomness complexity of interactive proof systems.\footnote{We refer to unconditional results and not to the 
long line of research %
on  %
randomness versus hardness %
trade-offs  %
that 
%
relies  %
on uniform or non-uniform assumptions,
%
%
see, \eg, \cite{KM},\cite{SU}.}
Specifically, Bellare \etal~\cite{BGG} studied the randomness complexity 
of \emph{error reduction} in the context of interactive proof systems.
(We mention that the randomness complexity is also of interest
in~\cite{GL}, which provides an alternative transformation
of general interactive proof systems to public coin ones.) 

Regarding the completeness in interactive proofs, the fact that every interactive proof system can be transformed into one with perfect completeness was shown in ~\cite{FGMSZ}.  
%
%
%
%
%
%
%
%
%
\subsection{Round complexity versus randomness complexity}
A natural question, which to the best of our knowledge
%
has not been  %
considered before, is what is the relation between
the two foregoing complexity measures. We do suspect that 
there are cases when the randomness complexity cannot be made smaller than the round complexity without trivially increasing the number of rounds. 
This is because constant-round interactive proof
systems seem more powerful than $\ccNP$-proof systems
(see, \eg, the Graph Non-Isomorphism proof of~\cite{GMW}), 
whereas a logarithmic amount of randomness is clearly useless 
(since this reduces to $\ccp$). 
But \emph{can the round complexity be %
greater  %
than the randomness complexity?}

The answer is definitely negative if we consider 
\emph{public coin} interactive proof systems. 
Recall that in these proof systems,
in each round, the verifier sends the outcome of fresh coins 
that it has tossed at the beginning of the current round,
and so by definition, the number of coin tosses is at least
as large as the number of rounds.\footnote{This presumes that the definition requires the
	verifier to send a non-empty message in each round. 
	But otherwise (\ie, if the definition allows empty messages), 
	rounds in which the verifier sends nothing can be collapsed.}
%
However, it is not clear what happens in the case of general
interactive proofs. (In particular, the transformation
of~\cite{GS} significantly increases the randomness complexity
by a factor depending on the number of rounds.) 

Recall that in a general interactive proof system,
the verifier may toss all coins at the very beginning,
but its message in each round may be a complex function
of the outcome of these coins 
(and the messages it has received from the prover).
In particular, the verifier's messages may have very little
information %
content  %
(from the prover's point of view), 
and so %
%
%
in principle we could %
have many more rounds than the number of coins tossed. 
Furthermore, it is not clear how to collapse rounds 
that yield verifier messages of low information
%
content.  %
These are the issues we deal with when showing that even in general interactive proof systems, randomness complexity $r(n)$ yields round complexity $O\left (r(n)/\log r(n)\right )$. Hence, in interactive proof systems, \emph{the round complexity is smaller than the randomness complexity}.

%
%
\begin{theorem}[Main Theorem] \label{thm:main}  %
  %
  %
Suppose that $S$ has an interactive proof system of randomness
complexity $r(n)$ for instances of length $n$. Then, $S$
has a \textsf{public coin} interactive proof system of 
round complexity $O(r(n)/\log r(n))$ and randomness complexity $O(r(n))$.
Furthermore, the resulting interactive proof system has perfect completeness.
\end{theorem}
Note that, in addition to obtaining the public coin feature,
we obtain perfect completeness for free. 
That is, even if the original system does not have 
perfect completeness, the new one has this feature. 
%
%
%
%

\subsubsection{Conditional tightness} 
The round complexity obtained by \expref{Theorem}{thm:main}
is the best one may hope for at this time,
since a result asserting round complexity $o(r(n)/\log r(n))$ 
for any set that has  an interactive proof system 
of randomness complexity $r(n)$ would yield an unexpected result
that seems currently out of reach. 
Specifically, it would place {\tt SAT} in
%
%
$\coAMTIME(2^{o(n)})$, %
which %
contradicts   %
%
%
common beliefs. 
The full reasoning is as follows: 
\begin{enumerate}
\item 
A variant of the celebrated interactive proof system 
for ${\overline{\tt SAT}}$
%
%
\cite{S90} %
%
%
yields an interactive proof system of 
randomness complexity $O(n)$ for unsatisfiable CNFs with 
$n$ variables.  
(This interactive proof consists of $n/\log n$ rounds such
that in each round we strip a single variable in the
sum-check that sums over $n/\log n$ variables with values in $[n]$, 
while using a finite field of 
%
order %
	 $\poly(n)$. %
%
%
See ~\cite[Sec 8]{GVW}.)%
\footnote{This is done by packing a sequence of $\log n$ bits of the boolean variables into a symbol of $H=[n]\subseteq F$ where $F$ is some field. For $i\in \ell$, where $\ell=\log n$, denote by $f_i(x):F\rightarrow F$ the polynomial of degree $n-1$ that maps each element in $H$ to the value of its $i$th boolean variable. Now, take the standard  arithmetization of the CNF and replace each occurrence of the   variable indexed $j\cdot \ell   +i$ by the polynomial $f_i(x_j)$, where $x_j$ is the $F$ variable that represents the $j$th block of boolean variables. The resulting polynomial is a
%
%
polynomial in $n/\ell$ variables, 
of total degree $O(m\cdot n)$, where $m$ is the number of clauses. Finally, 
the number of satisfying assignments is given by the
sum over all $(y_1,....,y_{n/\ell })\in H^{n/ \ell }$
of the polynomial derived above. Furthermore, we do not execute
the sum-check protocol over an exponentially large finite field
but rather over a finite field of prime cardinality $p=\poly(n)$,
where $p$ is selected by the verifier at random among such primes.} 

	\item 
On the other hand, any set having an $m$-round interactive proof
system is in 
 %
 $\AMTIME(n^{O(m)})$, %
see~\cite[Apdx B]{GVW}. 
Hence, if unsatisfiable CNFs have an interactive proof  
of round complexity $o(n/\log n)$, then such instances
can be refuted in
%
  $\AMTIME(2^{o(n)})$, %
whereas $\AMTIME(T)$  
may equal $\NTIME(\poly(T))$. 
\end{enumerate}


%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\subsection[On the proof]{On the proof of \expref{Theorem}{thm:main}}\label{intro:proof}
We start by giving an overview of a proof of a weaker result, in which we show how to transform any interactive proof, of randomness complexity $r(n)$, to a \emph{private coin} interactive proof for the same set that uses $O(r(n)/\log r(n))$ rounds, while maintaining the randomness complexity of $r(n)$. This proof gives a flavor of the proof of the main theorem, but is significantly simpler.

\subsubsection{Private coin emulation protocol} 

We describe the strategies of the new prover \newP~ and verifier \newV~ in iterations, where each iteration may correspond to several rounds of the original protocol of prover \orgP~ and verifier \orgV. The idea of the emulation protocol is that, in every iteration, we would like \newP~ to send possible continuations of the current transcript (each possibly describing execution segments of several rounds) that reveal much information about the verifier's random coins. Hence, \newP~ sends  %
maximal transcripts
 such that each account for a noticeable fraction of the residual probability mass.\footnote{Note that in the eyes of an observer, a verifier that samples its random coins at the beginning of the interaction and proceeds accordingly, is equivalent to a verifier that on each round samples a message with probability proportional to its residual probability mass.}
The verifier \newV~ then checks if one of these transcripts is consistent with the strategy of \orgV~ determined by the values of its random coins, which were tossed upfront. (That is, does the transcript contain the messages that \orgV~ would send using the private coin tosses of \newV~ and the previous messages.)
If so, \newV~ picks %
%
a  %
%
maximum transcript %
%
consistent with the strategy of \orgV, and they 
%
continue   %
their interaction from that point. Otherwise, \newV~ sends its next message (based on the aforementioned coins) without using the continuations suggested by \newP. We stress that the only source of \newV's randomness is its private coins tossed upfront, which are used to determine the continuation of the transcript in each subsequent iteration.

We %
elaborate on how the prover \newP~ determines the continuations of the transcripts. Fixing an iteration, we denote the current transcript by $\gamma$ and its residual probability  mass by $p(\gamma)$. Each transcript the prover sends on this iteration is a %
maximal 
continuation of $\gamma$ %
that is a ``heavy continuation.'' By a  heavy continuation $\gamma '$, we mean that $\gamma '$ has probability mass  greater than $p(\gamma)/r(n)$, when subtracting from it the probability mass of the  continuations of $\gamma$ that were either sent by \newP~ in previous iterations, or previously in this iteration. %
A heavy continuation is maximal in the sense that all its continuations are not heavy (probability mass not greater than $p(\gamma)/r(n)$). %
Note that there are at most $r(n)$ heavy continuations of $\gamma$, so the prover can send them to the verifier (who is computationally bounded).

This conditioning allows \newP~ to send several continuations of the transcript, some of which may also be continuations of the others. Consider for example the case that the prover sends $\gamma\alpha_1 \beta_1 \alpha_2 \beta_2$ and  $\gamma \alpha_1 \beta_1$. In this case if the verifier chooses $\gamma \alpha_1 \beta_1$ it means that in the next iteration the continuation of this transcript cannot begin with $\alpha_2 \beta_2$.  

The benefit of this method of determining transcript-continuations is that we guarantee that in the \emph{next} iteration the probability mass of the new transcript is \emph{lower} than 
$p(\gamma)/r(n)$. The reasoning is as follows. If the verifier \newV~ chooses one of the transcripts suggested by the prover \newP, then on the \emph{next} iteration the residual probability mass of each of its continuations is lower than $p(\gamma)/r(n)$. Otherwise, this continuation should have  been suggested by the prover on the previous iteration.
If \newV~ did not choose any of the transcripts, and instead continued the transcript with its own message $\widetilde{\alpha_1}$, then it follows that the residual probability mass of the transcript $\gamma \widetilde{\alpha_1}$ (under the conditioning of the appropriate events) is also lower than $p(\gamma)/r(n)$, otherwise the continuation $\gamma\widetilde{\alpha_1}$ should have been suggested by \newP.

It follows that after $O(r(n)/\log r(n))$ iterations the probability of the transcript generated is at most $\left(1/r(n)\right)^{r(n)/\log r(n)}=1/2^{r(n)}$, which means that there is a unique value of the coin tosses consistent with the transcript. Hence, a complete transcript is generated and \newV~ can reject or accept at this point.
It is easy to show that if \newP~ follows the prescribed emulation, then the verifier \newV~ accepts with the same probability as in the original interactive proof system, and hence completeness is maintained.   

Note that the above emulation per se does not suffice for proving soundness. It is essential to include validation checks that guarantee that the transcripts provided by \newP~ are consistent with some legal prover \orgP~ strategy for the original protocol.\footnote{Otherwise \newP~ can 
provide different transcripts tailored to the verifier's private coin tosses, whereas the original prover could not have employed such a strategy since it is not exposed to the private coin tosses.} This means that if \newP~ provides two transcripts that share a prefix, this common prefix must end with a prover's message and diverge only
%
depending on  %
the verifier's response. This implies that the prover \orgP~ answers in the same way to the same verifier %
\orgV's  %
messages, which means that \newP's strategy is consistent with some prover \orgP~ of the original %
%
proof system
and so the soundness of the original proof system is maintained. 

\subsubsection{Public coin emulation protocol}
The simplified private coin emulation protocol captures one of the key ideas of our public coin emulation protocol. The difficulty that we face when seeking a public coin emulation is that we cannot rely on hidden coins tossed upfront by the verifier. Thus, when presented with a list of heavy continuations, it is unclear how the verifier should select one at random, since the selection probability should be determined by the residual probability masses that are unknown to it. Our solution is to have the prover provide these probabilities, but this raises the need to verify these claimed values
(and have the verifier %
reject right away  %
if the sum of these probabilities does not match the claimed probability
of the transcript as determined before the current iteration). In the last iteration of the emulation, a complete transcript is sampled, containing the verifier's private coins, hence the validity of the transcript and the claim can be checked.

The foregoing description raises a few issues.  
Firstly, the prover should find a way to communicate all the transcripts to the verifier, and not only the ones with high residual probability mass as before. Second, it is not clear what happens to the soundness when the prover provides wrong values for the residual probabilities. 
As for the second issue, note that maliciously raising the claimed probability
of a transcript does contribute towards having the sum of
probabilities meet the prior claim, but it makes the probability
that this transcript is selected higher, and so puts the prover
in greater difficulties in the next iteration. Indeed, a careful analysis
shows that actually, the prover gains nothing by such behaviour,
since when the transcript is complete, false claims about its 
residual probability are easily detected. 

Turning back to the first issue, we note that the issue is that there may be too many short transcripts, that each account for a small fraction of the residual probability mass. To deal with this case, we have the prover pack many transcripts 
into a single auxiliary message. We use a succinct
representation of a sequence that contains many of the transcripts but not all of them
(since otherwise, we would have made no progress at the current iteration). 
The succinct representation should support the verification that
the corresponding sequences are disjoint. Now, each such ``pack''
of transcripts will be assigned the corresponding probability mass, 
and will be treated as if it were an actual transcript. 

Needless to say, the foregoing is but a very rough sketch
of the structure of the derived proof system.
The actual proof system uses a carefully designed verification
procedure that ensures that its executions can be mapped to executions 
in the original proof system (in order to guarantee soundness). 

We note that while the above description of the public coin emulation refers to the
probability that various transcripts appear in the original proof system 
(when the prover uses an optimal strategy),
our actual construction refers only to accepting transcripts
(\ie, transcripts that lead the original verifier to accept). 
Consequently, we obtain a proof system of perfect completeness,
even if the original proof system had two-sided error probability. 


%
\subsection{Relation to previous public coin emulation protocols}  \label{subsub: relation}
The basic idea used in emulating a private coin interactive proof by a public coin one is having the prover assist the verifier in generating its next message using public coins, instead of relying on private coins to generate the messages. 
Goldwasser and Sipser, who first suggested this emulation strategy \cite{GS}, cluster the potential messages that the original verifier could have sent on the next round into clusters according to the (approximate) number of coin sequences that support each
message. A constant-round, public-coin sampling protocol is utilized in order to sample from the
cluster of messages that have the largest number of coin sequences. This emulation succeeds assuming a sufficiently large initial gap between completeness and soundness, which is obtained at a cost of blowup of $\poly (n)$ factor in randomness complexity. Thus, the original public coin emulation preserves the round complexity of the private coin interactive proof but not the randomness complexity. 

An alternative public coin emulation, suggested by Goldreich and Leshkowitz \cite{GL}, is similar to the original emulation but differs in the way the chosen cluster of messages (from which the sampling is performed) is determined. Whereas in the original emulation the chosen cluster is deterministically determined as the one with the largest number of coins, in the alternative emulation the chosen cluster is selected probabilistically according to its weight (\ie, the number of coin tosses in the cluster). Therefore, the alternative emulation gets closer to sampling from the
%
actual  %
distribution of prover verifier transcripts. Consequently, it requires a smaller initial gap between completeness and soundness. Similarly to the original emulation, the alternative emulation preserves the round complexity but not the randomness complexity, although the blowup in randomness complexity is slightly reduced due to the decrease in the
%
completeness/soundness gap.  %

Our emulation protocol was designed with the goal of 
%
giving an upper bound on  %
the round complexity in terms of the randomness complexity, while preserving the randomness complexity. To this end, the way the prover assists the verifier in generating its next message is different from the method used in the aforementioned emulations. The prover %
supplies %
 the verifier with heavy continuations, %
%
%
%
which may correspond to multiple interaction rounds, that account for a noticeable fraction of the residual weight. In addition to the heavy continuations, the prover clusters the messages that each account for a small fraction of the residual weight using a succinct representation that supports the verification that messages in each cluster are disjoint. The method from the alternative emulation is then used to probabilistically select from the joint set of clusters and heavy continuations. When a cluster is selected, instead of using a sampling protocol to sample a message from the cluster, the emulation protocol is executed iteratively until reaching a heavy continuation (which corresponds to a message of the original interactive proof system). For this reason, the emulation protocol does not preserve the round complexity, which may increase by a $\poly (n)$ factor. However,
%
addressing our initial concern,  %
the combination of message generation and selection methods ensure that the randomness complexity $r(n)$ is preserved up to a constant factor and the new round complexity is at most $O(r(n)/\log r(n))$. 
 
The original and alternative public coin emulations did not obtain perfect completeness since they used a sampling protocol for sampling a message from a cluster, which may fail even when the prover is honest. Since our emulation does not utilize such a protocol, we obtain perfect completeness for free.
 %
 
 %
An additional known public coin emulation is obtained using the LFKN--Shamir protocol \cite{LFKN, S90}  to derive a public coin interactive proof system with perfect completeness to any set in $\ccpspace$, and applying the protocol on the trivial $\ccpspace$ emulation of the private coin interactive proof system. This 
%
public coin emulation with perfect completeness  %
is derived at a cost of polynomial round complexity and randomness 
complexity. 
  %
  
  
\subsection{Organization} \label{subsec:intro_org}
Towards proving the main theorem we shall show how to emulate an existing interactive proof system with a public coin emulation protocol that has $O\left (r(n)/\log r(n)\right )$ rounds. We begin by introducing the notion of ``protocol trees'' in \expref{Section}{sec:tree}, which we use to describe the interaction of the verifier and prover of the original interactive proof system. In \expref{Section} {sec:emu_tree}, we shall show how to transform the protocol tree into an ``emulation tree,'' that contains the continuations of the transcripts that the prover sends on each iteration along with their probability masses. Using this emulation tree, we then turn to
%
describing  %
the public coin emulation protocol for the new prover and verifier, in \expref{Section}{sec:emu}. The analysis of the emulation, which is given in \expref{Section}{sec:anal}, is partitioned into completeness (\expref{Subsection}{subsec:anal_comp}) and soundness (\expref{Subsection}{subsec:anal_soundness}).

In \expref{Appendix}{sec:private_tree}, we %
show how to emulate the existing interactive proof system with a private coin emulation protocol that has \prolen~ rounds. The organization of this section is similar to the organization of the main part of the paper, although most sections of it are less involved. \expref{Appendix}{sec:private_tree} is written so it can be read independently of the rest of the paper, and the decision if to read it before or after the other parts of the paper is left to the reader. 
\Cnote{We provide notes that point out the main differences and similarities between the private and public coin emulation protocols. These notes are typeset as this one.}

In \expref{Appendix}{sec:public_tree}, we %
show an additional way to emulate the existing proof system with a public coin one that has perfect completeness. We stress that this is emulation is weaker than the one in the main theorem since it does not reduce the round complexity. 

The two emulations in \expref{Appendix}{sec:private_tree} and \expref{Appendix}{sec:public_tree} together can be used to derive an alternative proof of the main theorem. This alternative proof of the main theorem is more modular, splitting the transformation into two simpler independent steps. We show how this can be done in \expref{Appendix}{sec:public_tree}. 




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

Let us start by formally defining interactive proof systems, where the completeness and soundness bounds are parameters.
%
\begin{definition} [Interactive Proof Systems]\label{def:ip} %
Let $c,s:\mathbb{N}\to[0,1]$ such that
%
$c(|x|)\geq s(|x|)+1/\poly(|x|)$.   %
An interactive proof system for a set $S$ is a
%
two-party game,    %
%
%
%
between a verifier, denoted $V$, executing a probabilistic
polynomial-time strategy,  %
%
%
%
and a prover, denoted $P$, executing a {\em(computationally unbounded)}
strategy,   %
satisfying the following two conditions:
\begin{itemize}
\item Completeness with bound $c$: 
For every $x\in S$, the verifier $V$ accepts
%
with probability at least $c(|x|)$  %
after interacting with the prover $P$ on common input $x$.
%
\item Soundness with bound $s$: 
For every $x\notin S$ and every prover $\widetilde{P}$ strategy,
the verifier $V$ accepts
%
with probability at most $s(|x|)$   %
after interacting with $\widetilde{P}$ on common input $x$.
%
\end{itemize}
	When $c$ and $s$ are not specified, we mean $c\equiv {2}/{3}$ and $s\equiv {1}/{3}$.
	We denote by $\ccIP$ the class of sets having interactive
	proof systems. When  $c\equiv1$, we say that the system has \textsf{perfect  completeness}. 
\end{definition}


\section[The protocol tree]{The protocol tree of the original proof system} \label{sec:tree}


\Cnote{Note that the protocol tree for the private coin emulation described in \expref{Section} {p_sec:tree} is similar to the one described here, except for the definition of weights.  }

Fixing an interactive proof between a prover \newP~ and a verifier \newV, and an instance $x$ of length $n$, we describe the possible prover-verifier
interactions on common input $x$ using a tree \PTree~
whose height corresponds to the number of rounds of interaction.  For some
$\ell=\ell(n)$,
we assume without loss of generality that in %
%
%
%
%
%
%
%
%
round $i$ the verifier sends a message 
$\alpha_i\in\left\{ 0,1\right\} ^{\ell}$,
and the 
%
prover  %
responds with a message $\beta_i\in\left\{ 0,1\right\} ^{\ell}$. 
%
%
We can also assume, without loss of generality, that the prover's strategy
is deterministic and fixed. Each node $v$
%
on  %
level $j$ represents a possible prover-verifier transcript
for the first $j$ rounds of the interaction. The branching 
of \PTree~ represents
the possible ways to extend the transcript to the next round. The
number of ways to extend the transcript
%
is the number of possible messages of the verifier
in the next round %
%
%
since the prover is deterministic.  %
Hence, each node has
\emph{at most} $D\coloneqq2^{\ell}$ children, corresponding to the 
$2^{\ell}$
possible verifier messages for the next round. The prover's response
to each such message is included in the \textbf{description} of the 
corresponding node. 

The description of a node $u$ on level $j$ contains the partial \textbf{transcript}
$\gamma\left(u\right)=\alpha_{1}\beta_{1},\dots,\alpha_{j}\beta_{j}$
of the interaction up to the $j$'th round. The root (at level zero) has an empty transcript, whereas a leaf in \PTree~ represents
a complete prover-verifier interaction. We can assume, without loss
of generality, that the verifier sends its private coins on the last
round, and hence every leaf is associated with a sequence of coin
tosses which %
leads the verifier
either   %
to accept or to reject. Hence,
we can represent the possible interactions generated by the interactive
proof system using a tree of height $m$ which has $2^{r(n)}$ leaves,
where $m$ is the number of rounds and $r(n)$ is the number of coin tosses. Using a constant number of
repetitions of an interactive proof system with standard completeness and soundness parameters, we can assume that the interactive proof system
has completeness parameter $\comp$ and soundness parameter
$\sound$.\footnote{The new interactive proof system will work by performing multiple invocations of the original interactive proof system. The verifier will accept
%
%
if %
the majority  %
of the original runs are accepting.} Note that this blows up the randomness complexity
only by a constant factor (as compared to our interactive proof for the standard 
%
$1/3$, $2/3$ %
parameters). Therefore, if $x$ is a yes-instance then at
least $\comp\cdot2^{r(n)}$ of its leaves represent accepting runs,
and if $x$ is a no-instance then at most $\sound\cdot2^{r(n)}$
of its leaves represent accepting runs. 

The description of a node also contains its \textbf{weight}, denoted $\wgt{u}$. The weight of the node is the number of coin sequences that
are consistent with the node and lead the verifier to accept at the
end of the interaction. That is,

\begin{definition}
%
[Weight of a leaf] \label{def:weight_leaf} %
	Let $u$ be a leaf in \PTree~ with transcript $\gamma(u)$
	which corresponds to the full transcript of the interaction of $P$
	and $V$ on input $x$, when $V$ uses %
coin sequence   %
$\rho$; that is, 
	\begin{equation}
	\gamma\left(u\right)=\left(\alpha_{1},\beta_{1},\dots,\alpha_{m},\beta_{m},\left(\rho,\sigma\right)\right)\label{eq:transcript-1-1}
	\end{equation}
	where $\sigma=V\left(x,\rho,\beta_{1},\dots,\beta_{m}\right)\in\left\{ 0,1\right\} $
	is $V$'s final verdict and for every $i=1,\dots,m$ it holds that
	$\alpha_{i}=V\left(x,\rho,\beta_{1},\dots,\beta_{i-1}\right)$ and
	$\beta_{i}=P\left(x,\alpha_{1},\dots,\alpha_{i}\right)$. We define
	the weight $\wgt{u}$ of $u$ to be $V$'s final verdict $\sigma$. 
\end{definition}

\begin{definition}
%
[Weight of a node] \label{def:weight_node}
	The weight $w(u)$ of a node $u$ in \PTree~
	 is the sum of the weights of the leaves that are descendants
	of $u$. 
\end{definition}

Note that $\wgt{u}$ is proportional to the probability that $\gamma (u)$ is generated  and the verifier accepts at the end of the interaction.
\Cnote{In the private coin emulation the weight of all the leaves is defined as $1$. Hence, in the private coin emulation the weight of a node is the number of coin sequences that are consistent with the corresponding transcript.}
\section{The emulation tree} \label{sec:emu_tree}
\subsection{Overview} \label{subsec:emu_overview}

So far we  %
have  %
explained how to represent the possible executions of an $m$-round 
interactive proof
system between prover \orgP~ and verifier \orgV~ on some instance $x$, where the protocol utilizes $r(n)$ coins. This %
results   %
in a protocol tree \oPT~ of height $m$ with $2^{r(n)}$ leaves.
Our goal is to transform this protocol tree to an emulation tree, denoted by $\oET$, that
defines a prover strategy for a \prolen -round public coin emulation protocol. This transformation is done using the
{\tt Build\_Tree} procedure. First, we describe how the emulation tree is used in the very restricted case where
the protocol tree is already suitable for our proposed public coin protocol and the {\tt Build\_Tree} procedure is not required. Next, we explain
how the transformation works in a restricted case when the degree
of the protocol tree is bounded by %
$\poly(n)$, and
finally in the case of a general protocol tree. 

\Cnote{The procedure for constructing the private coin emulation tree described in \expref{Section}{p_sec:emu_tree} is similar to the one described here for the restricted case that the degree of the protocol tree is bounded by $\poly(n)$.  Those familiar with the construction of the emulation tree for the private coin protocol can skip to the ``general case'' paragraph. }

%
\subsubsection %
{The protocol tree is of height \prolen~
	and degree $\text{poly}(n)$}

In order to convince the verifier that $x$ is a yes-instance the prover makes an initial claim that the weight of the root of the protocol tree \oPT~ is at least $c\cdot 2^{r(n)}$ (where $c$ is the completeness bound). The emulation is initiated at the root of \oPT~ and on each round of
the emulation the prover assists the verifier at progressing one step
down the \oPT. (This assistance is required because the verifier
does not have access to \oPT.) Each round consists of the
prover providing the verifier with the descriptions of the children of the current node $u$ that was sampled on the previous round, where these descriptions contain the weights of the various children. The verifier performs validations to check that according to the descriptions these are legal children of $u$, and that their claimed weights sum up to $\wgt{u}$. Then, the verifier samples a child with probability that is approximately proportional to its weight,
up to a multiplicative factor of %
$1+1/r(n)$ %
 using $O\left(\log r(n)\right)$
public coins. On the last round, a leaf is sampled, whose description contains
the complete prover-verifier interaction along with the coins tossed
by the verifier. The new verifier accepts if and only if the transcript
sampled is consistent with the original verifier's strategy according to the coin tosses revealed, and leads
the original verifier to accept.

To see why this is indeed an interactive proof system for the original language, note that an
honest prover can always convince the verifier of the correctness
of a true claim using this emulation. Hence, the interactive proof system
we described has perfect completeness. On the other hand, for no-instances,
a prover that wants to make the verifier accept must make an initial
claim that the weight of the empty transcript is much larger than its %
actual weight. %
%
%
%
Namely, the actual weight of the empty transcript is at
most $s\cdot2^{r(n)}$, whereas the prover claims that the weight is
at least $c\cdot2^{r(n)}$, where $c>s$ are the completeness and soundness
bounds of the original interactive proof system. Thus, there is
a multiplicative gap of %
$s/c$ %
between the actual weight and the one claimed. 
We can show that, in expectation, this gap is maintained throughout
the emulation, up to a factor of 
$\left(1+1/{r(n)}\right)^{r(n)} < \eee$ %
that comes from the approximation factor. Therefore, the probability that
a leaf that corresponds
to an accepting run is sampled on the last round (and hence the verifier
accepts) is at most 
%
%
%
$\eee s/c$
which is smaller than $1/3$
for a suitable choice of $s$ and $c$. 

%
\subsubsection %
{The degree of the protocol tree is bounded by $\poly(n)$}

In this case the height of the protocol tree \oPT~ may be asymptotically
larger than %
$r(n)/ \log r(n)$. 
We create a new tree of height \prolen  ~to guide
the prover's strategy, which we use in a way similar to how we used
the protocol tree in the previous paragraph. We call this tree the \textbf{emulation tree}, which we denote by $\oET$. The nodes in the $\oET$~ are nodes in \oPT. However, the children of a node $u$ in $\oET$~ may
be non-immediate descendants of $u$ in \oPT.

We start with a protocol tree \oPT~ rooted at $r$ whose weight
is $\wgt{r}$, and on each step we modify this tree towards creating
an emulation tree $\oET$. We define a \textbf{heavy descendant} of node $r$  to
be a node whose weight is at least %
$\wgt{r}/r(n)$ %
and the weight of each of its children is smaller than %
 $\wgt{r}/{r(n)}$. %
Note that there are at most $r(n)$ heavy descendants for each node in the tree. 

We modify \oPT~ so that the children of $r$ in the emulation tree
are its original children as well as the heavy descendants that
we lift upwards to make them new children of $r$. This modification
is performed using the {\tt Build\_Tree(r)} procedure, which
when invoked on a node $r$ identifies the nodes that will be  children of $r$ in the new tree, sets them as children of $r$, and then initiates recursive invocations on the (original and new) children of $r$, creating the new
emulation tree rooted at $r$. Details follow. 

The {\tt Build\_Tree(r)} begins by  identifying the heavy descendants of $r$ (they can also be children of $r$ in $\oPTi{r}$), which will become \textbf{heavy children} of $r$. Denote by $\oPTi{u}$ the intermediate tree after we identify and set $u$ as a heavy descendant of $r$. This way we have a notation for every transformation of the tree in which we set an additional child in the tree. That is, if the next tree after $\oPTi{u}$ is $\oPTi{w}$ then in $\oPTi{w}$ both $u$ and $w$ are heavy children of $r$.
After we identified the children of $r$ in the new emulation tree, we call the {\tt Build\_Tree}  procedure recursively on each
child of $r$, which creates an emulation tree rooted at that node. 

Observe that in the final emulation tree $\oET$, for each node $u$, 
the weight of each grandchild of $u$ is at most %
 ${w(u)}/{r(n)}$. %
 This is because if $v$ is a heavy child of $u$ in $\oET$, then the weight of each descendant of $v$ in $\oPTi{u}$ is at most %
 ${w(u)}/{r(n)}$. %
 Since the children of $v$ in the emulation tree are descendants of $v$ in $\oPTi{u}$ the claim holds. Otherwise, $v$ is a non-heavy child of $u$, so its weight is smaller than %
  ${w(u)}/{r(n)}$ %
 and hence the weight of each child of $v$ is also smaller than %
  ${w(u)}/{r(n)}$. %

It follows that the height of $\oET$~ is \prolen.
The number of children of each node is at most $\poly(n)$, because we add
at most $r(n)$ heavy children to the original children of each node, and $r(n)$ is at most polynomial in $n$.
Hence, the emulation tree has properties similar to the protocol tree
in the previous paragraph, so it is suitable for our public coin emulation described in the previous subsection. 

\subsubsection{The general case}

In general, the degree of the protocol tree \oPT~ may be exponential in $n$. Lifting the heavy children
as we did in the case of unbounded height guarantees that the height of the
new emulation tree $\oET$~ is \prolen,
but its degree may be super-polynomial in $n$ (due to the original children). Hence,  we will not be able
to perform the emulation by having the prover provide the verifier with the descriptions of the children of the current node.
Thus, we also need to make sure we create $\oET$~ so that its  degree is %
$\poly(n)$. %

In order to reduce the degree when it is too large, we group the non-heavy children of $r$ under new children, which we call \textbf{interval children}.  This is done in addition to handling the heavy children of $r$ as before. 
In general, children of $r$ in \oPT~ may become non-immediate
descendants in the next intermediate tree, and non-immediate descendants of
$r$ may become immediate children of $r$ in the next intermediate tree (due to lifting).


Determining the children of $r$  is done in two steps, as part of the  {\tt Build\_Tree(r)}  procedure. The first
step is identifying the heavy descendants $v_1,\dots,v_k$ of $r$ and lifting them
to be children of $r$, creating heavy children. This is done by creating intermediate trees $\oPTi{v_1}$,\dots ,$\oPTi{v_k}$, through a sequence of editing steps. On each step, we create a new intermediate tree and edit it on the next step, by identifying and moving the next heavy descendant.
Next, we unite the non-heavy children of $r$ into groups. We unite the children by lexicographic order of their transcript field, such that the weight of each group is larger than %
$\wgt{r}/r(n)$ %
and at most %
${2\wgt{r}}/{r(n)}$ %
(except for, possibly, the last group which is only required to have weight smaller than %
${2\wgt{r}}/{r(n)}$). %
We create
a new \textbf{interval child} $v$ for each such
group, where the children of $v$ are the nodes
in the group. 


After creating all the interval children of $r$, the children of $r$ in the final emulation tree $\oET$~ are exactly the children of $r$ in $\oPTi{z}$, where $z$ is the last interval child of $r$ created. The number of children $r$ has is at most $r(n)$, since the weight of each child of $r$ (except for possibly the last interval child) is at least %
${w(r)}/{r(n)}$.
 Next, the procedure is called recursively on the children of $r$ in $\oPTi{z}$ in order to create the final emulation tree. 


The description of a node $u$ in the emulation tree is composed of the
\textbf{transcript }field $\gamma\left(u\right)=\alpha_{1}\beta_{1}\dots\alpha_{i}\beta_{i}$
and a \textbf{weight }field $\wgt{u}$ as in the original
protocol tree, with an additional \textbf{range} field $R(u)$.
The range of a node represents the possible range of its children's transcripts.

After determining the heavy children of $u$, and before grouping the non-heavy children under interval children, the non-heavy children of $u$ are all children of $u$ in \oPT.

Hence, the transcripts of the children of each interval child are the same up to the last verifier's message on which they differ, which corresponds to the branching of the intermediate tree for the next round. Thus, we can label the range $R(u)=\left[s,e\right]$
where $s<e\in\left\{ 0,1\right\} ^{\ell}$ according to the range of the last verifier message in the transcript field of the children of $u$.  
Heavy children
have full range $\left[0^{\ell},1^{\ell}\right]$, whereas the range
of interval children is a subinterval of $\left [0^{\ell},1^{\ell}\right]$ such that this subinterval corresponds to the transcripts of the descendants that are grouped under this node.

We show in the analysis that the height of $\oET$~ is \prolen. The degree of nodes in $\oET$~ is at most $r(n)$,  hence it is suitable for public coin emulation like in the previous subsection. 


(The running time of this algorithm is at least the size of the protocol
tree, which is exponential in $r(n)$, and thus it may be exponential in
$\left|x\right|$. However, the prover is the one that runs this algorithm
and the prover is computationally unbounded. Therefore, the running
time is not an issue.) 

\subsection{The {\tt Build\_Tree} procedure} \label{sec:emu_tree:proc}

Denote the designated prover and verifier of the original interactive proof system by \orgP~ and \orgV~ respectively, and the protocol tree of \orgP~ and \orgV~ for a yes-instance $x$ by \oPT. The {\tt Build\_Tree} procedure is a recursive procedure that reads and updates a tree $T$, which is initially set to equal the protocol tree \oPT ~until obtaining the final emulation tree, denoted by $\oET$. When invoked on a node $u$ in $T$, the procedure determines the children of $u$, updates the global tree and invokes the procedure recursively on the children of $u$. 
\\We denote by $T(u)$ the subtree of $T$ rooted at $u$. 
\paragraph*{Initialization.}
The tree $T$ is initialized to be the original protocol tree, where each node has a description that contains the weight and transcript like in the original tree, and an additional range field which is initially left empty. We set the range of the root, denoted $r$, to be full range $R(r)=[0^{\ell},1^{\ell}]$. If the weight of $r$ is zero we terminate the process. Otherwise, we invoke the  {\tt Build\_Tree}  procedure on $r$.

\paragraph*{The main procedure:  {\tt Build\_Tree} .}
If $u$ is a leaf, the procedure returns without updating the global tree $T$. Otherwise, the  {\tt Build\_Tree}  procedure invokes two sub-procedures,  {\tt Build\_Heavy(u)} and {\tt Build\_Interval(u)}, in order to identify and update the children of $u$ in $T$ and place them as children of $u$. Finally, the Build\_Tree procedure is invoked recursively on all the children of $u$ in $T$.


\paragraph*{{\tt Build\_Heavy}.}


The {\tt Build\_Heavy} procedure identifies the \textbf{heavy descendants} of $u$ in $T(u)$, which are descendants of large weight that have no children of large weight, and modifies the tree by lifting them to become \textbf{heavy children} of $u$. 
\begin{definition} 
	%
	[Heavy descendants] \label{def:heavy_desc}   %
	We call $v$ a heavy descendant of $u$ if $v$ is a descendant of $u$ in $T$ and the following conditions hold:
	\begin{enumerate} 
	%
		\item $\wgt{v}\geq\ \wgt{u}/ r(n)$ %
		\item Either $v$ is a leaf, or for each child $z$ of $v$ it holds that %
		$\wgt{z}<\wgt{u}/{r(n)}$.
	\end{enumerate}
\end{definition}

\noindent For each heavy descendant $v$ of $u$ we perform the following process: 

\begin{enumerate}  
	\item Update $v$'s description: Set the range field of $v$ to be full range $R(v)=[0^{\ell},1^{\ell}]$.
	\item Modify the protocol tree if $v$ is not already a child of $u$: 
	\begin{enumerate}
		\item Subtract $\wgt{v}$ from the weight of the ancestors of $v$ in $T(u)$, except for $u$ whose weight stays the same. 
		\item Move $v$ (along with the subtree rooted at $v$) so it is placed directly under $u$. 
	\end{enumerate}
\end{enumerate}
\noindent See \expref{Figure}{fig:build_heavy}.
%
\begin{figure}	[h]
	\begin{centering}
		
		\includegraphics[scale=0.5]{drawio/build_heavy_nodes.pdf}\protect
		\caption{{\tt Build\_Heavy}: In the first step, $v$ is identified as a heavy descendant of $u$ and moved to be a heavy child of $u$. In the second step, $z$ is identified and moved to be a heavy child of $u$. The triangles represent subtrees of the original tree.}
		\label{fig:build_heavy}
		\par\end{centering}
	
\end{figure}

\noindent After we finish identifying and moving the heavy children of $u$ we perform a clean up stage where we erase all the nodes in $T$ with weight zero. 


\paragraph*{{\tt Build\_Interval(u)}.}
This procedure groups the non-heavy children of $u$ under \textbf{interval children}. 
Denote the range field of $u$ by $R(u)=[s(u),e(u)]$.  (Note that $s(u)=0^\ell$ and $e(u)=1^\ell$ unless $u$ is an interval node, in which case its range is partial.) We partition the range of $u$ into a sequence of consecutive intervals, each one representing the range of a new child of $u$. As long as we have not partitioned all of the range $[s(u),e(u)]$ we perform the following procedure.

\begin{enumerate}
	\item Determine $s'$, the starting point of the interval child's range: Initially, for the first interval child of $u$ we set $s'=s(u)$. For the next interval children, if the end of the range of the previously created interval child is $\tilde{e}$, then we set $s'=\tilde{e}+1$. 
	\item 
	Determine $e'$, the ending point of the interval child's range: 
	For each $e\in \{0,1\}^\ell$, denote by $non\_heavy(s',e)$ the set of children of $u$ in $T(u)$ whose weights are smaller than %
	$\wgt{u}/r(n)$ %
	and their last verifier message $\alpha$ (in the transcript field) is in the range $[s',e]$. Note that when $[s',e]\neq[s(u),e(u)]$ the set $non\_heavy(s',e)$ can be a proper subset of the non-heavy children of $u$. We define the weight of the set $non\_heavy(s',e)$, which we denote by $W(s',e)$, as the sum of the weights of nodes in $non\_heavy(s',e)$. 
	\\We set $e'$, to be the minimal $e\in \{0,1\}^\ell$ that satisfies %
	$W(s',e)\geq \wgt{u}/{r(n)}$ %
	If no such $e$ exists and $W(s',e(u))>0$, we set $e'=e(u)$. If $W(s',e(u))=0$ there is no need to create another interval child so we return to the  {\tt Build\_Tree}  procedure. (This guarantees that the weight of an interval child is at least $1$). 
	\item Create a new node $v$: We set the transcript of $v$ to be like the transcript of $u$, $\gamma(v)=\gamma(u)$, its range to be $R(v)=[s',e']$ and its weight to be $w(v)=W(s',e')$. 
	\item Place $v$ in the tree: disconnect $u$ from the nodes in $non\_heavy(s',e')$. Set $u$ as a parent of $v$ and let $v$ be the parent of all nodes that are in $non\_heavy(s',e')$.  
\end{enumerate}

\noindent See \expref{Figure}{fig:build_interval}. Note that the weight of an interval child of $u$ is at most %
$2\wgt{u}/r(n)$ %
and at least  %
$\wgt{u}/r(n)$, %
 except possibly for the last interval child, whose weight is at least $1$.

\begin{figure}	[h]
	\begin{centering}
		
		\includegraphics[scale=0.5]{drawio/build_interval.pdf}\protect
		\caption{{\tt Build\_Interval}: The left diagram represents the tree before the {\tt Build\_Interval} procedure. The nodes to the left of the dashed line are heavy children of $u$. The group of nodes inside each dashed circle are united under an interval node. The tree on the right is the result of applying the {\tt Build\_Interval} procedure.}
		\label{fig:build_interval}
		\par\end{centering}
	
\end{figure}

%
\subsection{Properties of the emulation tree } \label{sec:emu_tree:prop}

Recall that in the original protocol tree, $v$ was a child of $u$
if and only if $\gamma(v)=\gamma(u)\alpha\beta$, where $\alpha,\beta \in \{0,1\}^\ell$ denote the next verifier message and the prover's response to it.
However, in the new emulation tree, $\oET$, this is not the case.
Namely, if $v$ is a child of $u$ in $\oET$, then it could be that $v$
is a heavy child of $u$ and hence $\gamma(v)=\gamma(u)\alpha_{1}\beta_{1},\dots,\alpha_{k}\beta_{k}$ for some $\alpha_1,\beta_1,\dots ,\alpha_k,\beta_k\in \{0,1\}^\ell$,
or $v$ is an interval child hence $\gamma(v)=\gamma(u)$
and $R(v)\subseteq R(u)$.  Nevertheless, the following
properties of the final emulation tree $\oET$~ are readily verified. 
%
\begin{claim} 
%
[Node degree] \label{emu_tree:prop:deg}
	Each node $u$ in the final emulation tree $\oET$~ has at most $r(n)$ children.
\end{claim}
\begin{proof}
	Note that we call  {\tt Build\_Tree}  on every node in $\oET$.
	By definition, the weight of each heavy child of $u$ is at least %
	$\wgt{u}/r(n)$. %
	The weight of each interval child is also at least %
	$\wgt{u}/r(n)$ %
	except for possibly the last interval child whose weight is non zero. Therefore, the number of children is at most $r(n)$. (If there were $r(n)+1$ children or more, then the $r(n)$ first children would have weight of at least %
	$\wgt{u}/r(n)$, %
	 and the last child has positive weight, which means that in total the sum of the weights of the children is greater than $\wgt{u}$, in contradiction.) 
\end{proof}
\begin{claim} 
%
[Weight reduction] \label{emu_tree:prop:weight}
	For every node $u$ in the final emulation tree $\oET$~ the weight
	of each grandchild of $u$ in $\oET$~ is at most %
	$2\wgt{u}/r(n)$.
\end{claim}
\begin{proof}
	
	Let $v$ be a child of $u$ in the emulation tree. First, consider the case that $v$ is a heavy child of $u$. Denote by $T_{u}$ the intermediate tree in the process of construction, after we determine the new children of $u$ and before the recursive invocations of the procedure on the children of $u$. By the definition of heavy children, the weight of each child of $v$ in $T_{u}$ is at most %
	$\wgt{u}/r(n)$. %
	Thus, the weights of the children of $v$ in $T_{u}$ is also at most %
	$\wgt{u}/r(n)$. %
	Now, if $z$ is a heavy child of $v$ (\ie, heavy with respect to $\wgt{v}$) in the final emulation tree $\oET$, then it is a descendant of $v$ in $T_{u}$, so its weight is at most %
	$\wgt{u}/r(n)$. %
	Otherwise, $z$ is an interval child of $v$ so its weight is at most %
		$2\wgt{v}/r(n)$, %
	  which is at most %
	$2\wgt{u}/r(n)$. %
	
	In case $v$ is an interval child of $u$, its weight is at most %
		$2\wgt{u}/r(n)$. %
	Hence, the weight of each grandchild of $u$ which is a child of $v$, is also at most %
			$2\wgt{u}/r(n)$. %
\end{proof}

\begin{corollary} 
%
[Corollary to \expref{Claim}{emu_tree:prop:weight})] \label{emu_tree:prop:height}  %
	The height of the final emulation tree $\oET$ is \prolen.
\end{corollary}
\begin{proof}
	The weight of the root of the protocol tree is at most the number of leaves in the tree, which is $2^{r(n)}$. When we start constructing the emulation tree, the weight of the root is the same as in the protocol tree. Moreover, the weight of a node does not
	change from the point that we call  {\tt Build\_Tree}  on it. Hence, the weight of the root
	in $\oET$~ is also at most $2^{r(n)}$. By \expref{Claim}{emu_tree:prop:weight}, the weight of a node in level $2i$ of the emulation tree is at most %
	${2^{r(n)}}/{\left(\frac{r(n)}{2}\right)^i}$. %
	Taking %

%
	$i=\left \lceil {r(n)}/{\log \left({r(n)}/{2}\right)}\right \rceil$ 
	we get that the weight of a node in level $2i$ of the emulation tree is at most $1$. Lastly note that a node with weight $1$ cannot have grandchildren, else by \expref{Claim}{emu_tree:prop:weight} their weight is smaller than $1$. This cannot happen since the
	weights of nodes in the emulation tree are positive integers. We
	conclude that the height of the emulation tree is at most %
	$2\cdot\lceil {r(n)}/{(\log(r(n))-1)}\rceil+1$. 
\end{proof}

\begin{claim}
	%
	[Leaves] \label{emu_tree:prop:leaves}
	The leaves of  $\oET$~ are exactly the leaves of protocol tree \oPT~ whose weights are $1$.
\end{claim}
\begin{proof}
	The construction does not create nodes whose weights are zero. Hence, all the leaves in $\oET$~  have positive weight. Following the construction of the emulation tree we can see that, during each step, the weight of a leaf from the original protocol tree stays the same, whereas the weight of a non-leaf is the sum of the weights of the leaves that are descendants of it. Hence, a leaf in $\oET$~ must be a leaf in \oPT whose weight is $1$.
	

	
	On the other hand, if $v$ is a leaf whose weight is $1$ in \oPT, then $v$ appears in the emulation tree. This is because the only way nodes from the protocol tree are erased throughout the construction is if their weight is $0$ (possibly after truncations in the middle of the construction). A leaf from \oPT~ that appears in $\oET$~ must appear as a leaf. This is because the only way we add descendants to a node is when we add interval children, but we do not invoke {\tt Build\_Interval} on a leaf.
\end{proof}



\section{Public coin emulation} \label{sec:emu}
\subsection{Emulation preliminaries}
Next, we describe the strategy of the designated prover \newP~ and verifier \newV~ in the new protocol (``emulation''). The strategy of the designated prover \newP~ for a yes-instance $x$ uses the emulation tree $\oET$~ of $x$ constructed in the previous section. The prover assists the verifier \newV~ in progressing down the emulation tree. On each
iteration, the prover provides the descriptions of the children $v_{1},\dots,v_{d}$
of the current node $u$, which was sampled in the previous iteration. The verifier performs
validations on the list supplied by the prover (to be detailed below), and then samples one
of the children for the next iteration according to its weight. The verifier does not
have access to the emulation tree, and its validations consist of
structural requirements on the part of the emulation tree seen so far. On the last iteration, the verifier checks that the full transcript, along with the sequence of coin tosses, leads the original verifier \orgV~ to accept. 


\Cnote{The main difference between the public coin emulation and the private coin one is in the way a child of a node is chosen in each iteration. In the private coin  emulation, the values of the verifier's private coin tosses determine which child is chosen. In contrast, in the public coin emulation, \newV~ does not have private coins. Hence, it must choose a continuation based on the transcripts and the probability distributions suggested by \newP.   }

One of the structural validations that the verifier makes is
that the nodes provided by the prover are possibly children of $u$ in the emulation tree.  For nodes in the original protocol tree, $v$ is possibly a child of $u$ if and only if the transcript of $v$ extends the transcript of $u$ by one pair of messages, and thus $v$ is possibly a descendant of $u$ if and only if the transcript of $u$ is a proper prefix of the transcript
of $v$. For nodes in the emulation tree the situation is more complex. If the transcript of $v$ equals the transcript of $u$ and the range of $v$ is a partial range of the range of $u$, then $v$ is possibly a child of $u$ which the verifier regards as an \textbf{interval child}. If the transcript of $u$ is a proper prefix of the transcript of $v$ and if  $\gamma(u)=\alpha_{1}^u\beta_{1}^u,\dots,\alpha_{i}^u\beta_{i}^u$, and $\alpha _{i+1}^v$ (the $i+1$ verifier's message in the transcript of $v$) is in the range of $u$ then $v$ is possibly a child of $u$, which the verifier regards as a \textbf{heavy child}.



With these two cases in mind, we define the conditions required of the descriptions of two nodes $u$ and $v$ in order for $v$ to be a descendant (not necessarily a child) of $u$ in the emulation tree. We say that $v$ is a \textbf{transcript descendant} of $u$ if these required conditions hold. 


%
\begin{definition}
	%
	[Transcript Descendant] \label{def:tran_desc} %
	Denote by $u$ and $v$ nodes in the emulation tree with transcripts
	$\gamma\left(u\right)=\alpha_{1}^{u}\beta_{1}^{u},\dots,\alpha_{i}^{u}\beta_{i}^{u}$
	and $\gamma\left(v\right)=\alpha_{1}^{v}\beta_{1}^{v}\dots\alpha_{j}^{v}\beta_{j}^{v}$
	and with range field $R\left(u\right)$ and $R\left(v\right)$, respectively.
	We say that $v$ is a transcript descendant of $u$ if one of the
	following conditions hold:
	\begin{enumerate}[label=\roman*]
		\item \label{def:td_1}$\gamma(v)=\gamma(u)$ and $R(v)\subseteq R(u)$
		\item \label{def:td_2}$\gamma\left(u\right)$ is a proper prefix of $\gamma\left(v\right)$
		and $\alpha_{i+1}^{v}\in R(u)$
	\end{enumerate}
\end{definition}


\begin{figure}	[h]
	\begin{centering}
		
		\includegraphics[scale=0.4]{drawio/truncation.pdf}\protect
		\caption{Truncation during  {\tt Build\_Tree}. The node $v$ is identified as a heavy descendant of $z$, so it is moved (along with the subtree that is rooted at it) to be a heavy child of $z$.}
		\label{fig:tranc}
		\par\end{centering}
	
\end{figure}


It is easy to show that for every node $u$ in $\oET$, every descendant  of $u$ is a transcript descendant of $u$. The proof is similar to the proof  of \expref{validation}{comp:td} in the completeness part of the analysis.
\\We state the following claim regarding the transitivity property of transcript descendancy, which we use in the analysis of the emulation.
\begin{claim}
%
[Transitivity] \label{anal:trans} %
	For nodes $u$, $v$ and $z$ in the emulation tree such that $z$ is a transcript descendant of $v$ and $v$ is a transcript descendant of $u$, $z$ is a transcript descendant
	of $u$. 
\end{claim} 
\begin{proof}
Denote the length of $\gamma\left(u\right)$
by $i$. Recall that if $v$ is a transcript descendant of $u$ then one of the following conditions hold: \begin{enumerate}
	\item $\gamma(v)=\gamma(u)$ and $R(v)\subseteq R(u)$, in this case, we say that $v$ is a transcript descendant of $u$ of type (\ref{def:td_1}).
	\item $\gamma\left(u\right)$ is a proper prefix of $\gamma\left(v\right)$
	and $\alpha_{i+1}^{v}\in R(u)$, in this case, we say that $v$ is a transcript descendant of $u$ of type (\ref{def:td_2}). 
\end{enumerate}
We proceed by case analysis according to the descendancy types between $u$, $v$ and $z$ and show that in each case $z$ is a transcript descendant of $u$.
\begin{itemize}
	\item If $z$ is a transcript descendant of $v$ of type (\ref{def:td_1}) and $v$ is a transcript descendant of $u$ of
	type (\ref{def:td_1}) then $\gamma\left(u\right)=\gamma\left(v\right)=\gamma\left(z\right)$,
	and $R\left(z\right)\subseteq R\left(v\right)\subseteq R\left(u\right)$,
	so $z$ is a transcript descendant of $u$ of type (\ref{def:td_1}). 
	\item If $z$ is a transcript descendant of $v$ of type (\ref{def:td_1}) and $v$ is a transcript descendant of $u$ of
	type (\ref{def:td_2}) then $\gamma(u)$ is a proper prefix of $\gamma(v)=\gamma(z)$. Since the transcripts of $v$ and $z$ are equal it follows that $\alpha_{i+1}^z=\alpha_{i+1}^v$. Because $\alpha_{i+1}^v\in R(u)$ we get that $\alpha_{i+1}^z\in R(u)$, so $z$ is a transcript descendant of $u$ of type (\ref{def:td_2}).
	\item If $z$ is a transcript descendant of $v$ of type (\ref{def:td_2}) and $v$ is a transcript descendant of $u$ of
	type (\ref{def:td_1}) then $\gamma(v)$ is a proper prefix of $\gamma(z)$ and $\gamma(u)=\gamma(v)$, so $\gamma(u)$ is a proper prefix of $\gamma(z)$. Furthermore, $\alpha_{i+1}^z\in R(v)\subseteq R(u)$ so $z$
	is a transcript descendant of $u$ of type (\ref{def:td_2}).
	
	\item If $z$ is a transcript descendant of $v$ of type (\ref{def:td_2}) and $v$ is a transcript descendant of $u$ of
	type (\ref{def:td_2}) then $\gamma(u)$ is a proper prefix of $\gamma(z)$. Furthermore, because the transcript of $v$ is a prefix of the transcript of $z$ then $\alpha_{i+1}^{z}=\alpha_{i+1}^{v}$. Since $v$ is a transcript descendant of $u$ of type (\ref{def:td_2}), we know that $\alpha_{i+1}^{v}\in R\left(u\right)$  and so $\alpha_{i+1}^{z}\in R(u)$. Hence, $z$
	is a transcript descendant of $u$ of type (\ref{def:td_2}).
	
\end{itemize}	
\end{proof}


The condition of $v$ being a
transcript descendant of $u$ is not sufficient to guarantee that $v$
is possibly a descendant of $u$ in the emulation tree $\oET$. For example, suppose that $v$ was a child of $u$ in \oPT, and is a heavy descendant of a node $z$ that is an ancestor of $u$ in $\oET$. Then, $v$ becomes a heavy child of $z$ in $\oET$, which means that the subtree rooted at $v$  was truncated and moved up to be a direct descendant of $z$. Therefore, in order to check if $v$ is possibly a legal
descendant of $u$ in the emulation tree, the verifier needs to check that $v$ does not belong to a part of the tree that was truncated and moved to a different part of the emulation tree (such as nodes $v$ and $w$ in \expref{Figure}{fig:tranc}). 
For this reason, the verifier keeps a \textbf{seen-list} $S$ of nodes that were seen during the emulation, and updates the list at every iteration with the new nodes seen. 
Note that the nodes in $S(u)$, which the verifier sees up to the iteration that the input node is $u$, are a subtree of the emulation tree that is composed of a path from the root of the tree to $u$, augmented with the children of the nodes in the path. See \expref{Figure}{fig:seen}.
\begin{figure}	[h]
	\begin{centering}
		
		\includegraphics[scale=0.5]{drawio/seen.pdf}\protect
		\caption{The nodes in the seen-list, $S$, in the iteration that the input node is $u$. }
		\label{fig:seen}
		\par\end{centering}
	
\end{figure}

Another structural validation requires the transcripts that the verifier sees during the execution to be consistent with a deterministic prover strategy.

\begin{definition} 
	%
	[Prover consistent] \label{def:prover_consistent} %
	We say that two transcripts $\gamma(u)$ and $\gamma(v)$ are \textbf{prover consistent} if the maximal prefix they agree on is either empty or ends with a prover's message. That is, the prover should respond in the same way on the same prefix of the transcripts (\ie, for every $j$ smaller or equal to the length of the shorter transcript, if $(\alpha_1^u\beta_1^u,\dots ,\alpha_j^u)=(\alpha_1^v\beta_1^v,\dots,\alpha_j^v)$ then $\beta_j^u= \beta_j^v$). 
\end{definition}

This condition will allow for extracting a prover's strategy for the original protocol from the transcripts in $\oET$, and then to claim that since the original prover cannot fool the verifier with high probability, the new prover cannot either.

We stress that we give an honest-prover centric description of the emulation protocol. This means that \expref{Step}{emu:provide} describes the intended behaviour from an honest prover to provide the descriptions of the heavy children.
A %
dishonest   %
prover may deviate from this step, and the purpose of the verifier's checks to see that even if there was a deviation the prover can not succeed in claiming that a no-instance is a yes-instance with high probability. 
%
%
%
%
\subsection{Emulation construction}
Initially, for the first iteration, the transcript of the root $r$ is the empty transcript and the range is full, $[0^\ell,1^\ell]$. The prover provides the weight of the root $r$ and the verifier checks that the claimed weight is at least $\comp\cdot2^{r(n)}$. The verifier adds the description of $r$ to the seen-list $S$ (which is initially empty). The rest of the first iteration, as well as subsequent iterations, proceed as follows. 

\begin{construction} (the $i$th iteration) \label{emu:const}
	On input a non-leaf node $u$ and seen-list $S$.
\end{construction}	


\begin{enumerate}
	\item The prover provides the descriptions of the children $v_{1},\dots,v_{d}$ 
	of $u$: \mmm{\left(\gamma\left(v_{1}\right),R\left(v_{1}\right),\wgt{v_{1}}\right),\dots,\left(\gamma\left(v_{d}\right),R\left(v_{d}\right),\wgt{v_{d}}\right)} \label{emu:provide}
	\item The verifier performs the following validations and rejects
	if any of them fails: \label{emu:val}
	
	\begin{enumerate}
		\item \label{emu:val:diff} The verifier checks that all nodes are different (according to their
		descriptions). That is, for each distinct $i,j\in [d]$, if $\gamma (v_{i})=\gamma(v_{j})$,
		then $R(v_{i})\neq R(v_{j})$. 
		\item \label{emu:val:sum}The verifier checks that the weights of the children of $u$ sum up
		to $\wgt{u}$; that is, 
		\begin{equation}
		\wgt{u}=\sum_{j=1}^{d}\wgt{v_{j}} \label{eq:sum}
		\end{equation}
		\item \label{emu:val:td} For each $j\in\left[d\right]$, the verifier checks
		that $v_{j}$ is a transcript descendant of $u$.
		\item \label{emu:val:parint}For each interval child $v_{j}$, the verifier checks that $\gamma\left(v_{j}\right)=\gamma(u)$; that is, if $R\left(v_{j}\right)\neq[0^{\ell},1^{\ell}]$, then $\gamma\left(v_{j}\right)=\gamma(u)$ must hold.
		\item \label{emu:val:trunc}For each  $j\in [d]$, the verifier checks
		that $v_{j}$ is not in a part of the emulation tree that was truncated. (See discussion following \expref{Definition}{def:tran_desc}.) Specifically, for  $v\in S$ then if $v$ is a transcript descendant of $u$, then $v_{j}$ should not be a transcript descendant of $v$. \\
		For illustration consider \expref{Figure}{fig:tranc}, where $u,t,z,v\in S$. In that case, the verifier checks that $v_j$ is not a transcript descendant of $v$, where $v$ is a transcript descendant of $u$ since it was a descendant of $u$ in the original protocol tree. (In particular, $v_j$ should not be equal to $w$ shown in the figure.)\\
		(Note that it can be that $v_{j}$ is a transcript descendant of some node in $S$ that is not a transcript descendant of $u$, and this is not considered a violation. For example, all the nodes are transcript descendants of the root $r$, which is in $S$.)  
		
		%
		
		\item \label{emu:val:disj}The verifier checks that the ranges of all the interval children are disjoint; that is, for every two interval children $v_j$ and $v_k$, the verifier checks
		that $R\left(v_{j}\right)\cap R\left(v_{k}\right)=\emptyset$.
		\item \label{emu:val:pc} For each $j\in [d]$ the verifier checks that $\gamma(v_j)$ is \textbf{prover consistent} (see \expref{Definition}{def:prover_consistent}) with respect to the other transcripts of nodes in $S$ and with regarding to the transcripts of the other children $\gamma(v_{k})$, where $k\neq j$.  

	\end{enumerate}
	\item \label{emu:const:prob}The verifier chooses a child according to the probability distribution
	$J$ that assigns each $j\in\left[d\right]$ probability approximately
	proportional to $\wgt{v_{j}}$ using $O(\log r(n))$ coin tosses. That is, $J$ is such that
	\mmm
	{\eqtag{emu:const:approx_sampling}
		\textbf{Pr}\left[J=j\right]\leq\frac{\wgt{v_{j}}}{\sum_{i=1}^{d}\wgt{v_{i}}}\cdot \left(1+\frac{1}{r(n)}\right)
	}
	We can only afford to use $O(\log r(n))$ public coins per iteration since the height of the emulation tree, and hence the number of iterations of the emulation, is \prolen~ and we want the total number of public coins to be $O(r(n))$. Hence, we compromise on sampling each child with probability proportional to $\wgt{v_j}$, and instead sample with approximate probability.
	See the explanation for approximate sampling in \expref{Subsection}{app:approx}.
	\item \label{emu:const:last_step}The verifier adds all the children of $u$ to the seen-list $S$; that is $S\leftarrow S\cup \{v_1,\dots ,v_d\}$. Denote by $j$ the index the verifier choose in \ref{emu:const:prob}. Unless $\gamma (v_j)$ is the complete transcript (which contains the last message), the next iteration will start with node $v_j$ and the set $S$. Otherwise, we proceed to the final checks.  
\end{enumerate}


By our conventions, the last message the verifier \orgV~ sends, denoted $\alpha_{m}$, contains the
outcomes $\rho\in\left\{ 0,1\right\} ^{r(n)}$ of the $r(n)$ coins tossed.
Thus, if the last node chosen is $v$, then $\rho$ can be easily extracted
from $\gamma\left(v\right)=\alpha_{1}\beta_{1},\dots,\alpha_{m}\beta_{m}$.
After the last iteration, the verifier performs final checks and accepts
if all of them hold:



\begin{enumerate}[label=(\roman*)]
	\item Check that $\rho$  is accepting for $\gamma\left(v\right)$ and consistent with it: It checks that $V_0\left(x,\rho,\beta_{1},\dots,\beta_{m}\right)=1$,
	and that for every $i=1,\dots,m$ it holds that $\alpha_{i}=V_0\left(x,\rho,\beta_{1},\dots,\beta_{i-1}\right)$.
	Note that the verifier needs $\rho$ in order to verify these conditions,
	so this check can only be done after the last iteration. 
	\item Check that $\wgt{v}=1$; in other words the prover's last claim should be that the weight of the last node chosen is $1$ (and not more than $1$).
\end{enumerate}
%
\subsection{The number of rounds and randomness complexity}
Clearly, the number of iterations (and hence rounds) of the emulation is \prolen~ because the height of the emulation tree is \prolen,  and the prover and verifier proceed one step down the tree in each iteration. Since the verifier uses $O(\log r(n))$ public coins in each iteration, the randomness complexity of the emulation is $O(r(n))$.


	\subsection{Approximate sampling} \label{app:approx}

Let $D=(p_1,\dots ,p_d)$ be the probability distribution that assigns each $j\in [d]$ probability proportional to $\wgt{v_j}$; that is, $p_{j}={\wgt{v_j}}/{\sum_{i=1}^{d}\wgt{v_i}}$.
Our goal is to approximate the probability distribution $D$ with a probability distribution $J=(p_1',\dots ,p_d')$ in the sense that for each $j\in[d]$ it holds that $p_j'\leq p_j\cdot (1+{1}/{r(n)})$. Moreover, the probability distribution $J$ should be one that the verifier can sample from using $k=O\left(\log r(n)\right)$ coin tosses. Note that our method of approximation also satisfies $p_j'> p_j-1/(r(n))^{3}$~ for every $j\in [d]$, although the lower bound is not used in our work.

Let $k\in \N$ such that $2^{k-1}<(r(n))^{3}\leq2^{k}$. Assume, without loss
of generality, that $p_d$ is the largest probability and thus $p_d\geq {1}/{d}\geq {1}/{r(n)}$. For $j<d$ define $p_j'$ by rounding down $p_j$ to the closest integer multiple  of $2^{-k}$, whereas we add the residual probability mass to $p_d'$. That is,

\mmm{
	p_j' = 
	\begin{cases}
		\frac{\lfloor p_{j}\cdot2^{k}\rfloor}{2^{k}} & \text{for } j<d \\
		1-\sum_{i=1}^{d-1}\frac{\lfloor p_{i}\cdot2^{k}\rfloor}{2^{k}} & \text{for } j=d 
	\end{cases}
}

Clearly for $j<d$ it holds that $p'_{j}\leq p_{j}$. 
For $j=d$, 
\mmm{
	p'_{d} & =1-\sum_{i=1}^{d-1}\frac{\lfloor p_{i}\cdot2^{k}\rfloor}{2^{k}}\\
	& \leq1-\sum_{i=1}^{d-1}\frac{p_{i}\cdot2^{k}-1}{2^{k}}\\
	& =1-\sum_{i=1}^{d-1}p_{i}+\left(d-1\right)\cdot2^{-k}\mathdot  \eqtag{approx_pd}
}

Recall that the number of children the prover supplies, $d$, is upper
bounded by $r(n)$, and that
$2^{-k}\leq (r(n))^{-3}$. Thus, 
\mmm{(d-1)\cdot 2^{-k}\leq r(n)\cdot (r(n))^{-3}=(r(n))^{-2}\eqtag{approx_b}\mathdot}

Because $D$ is a probability distribution we get that $p_d=1-\sum_{i=1}^{d-1}p_{i}$ and so plugging \expeqref{Eq.}{approx_b} in \expeqref{Eq.}{approx_pd} we get that $p_d'\leq p_d+{1}/{\left(r(n)\right)^2}$.


Using the fact that $p_d\geq {1}/{r(n)}$ it follows that ${1}/{\left(r(n)\right)^2}\leq {p_d}/{r(n)}$ and hence \mmm{p_d'\leq p_d\cdot \left(1+{1}/{r(n)}\right)}  



\section{Analysis of the emulation}\label{sec:anal}

We show that the interactive proof system is transformed by the emulation protocol of \expref{Construction}{emu:const}, which uses the emulation tree $\oET$~ constructed in \expref{Section}{sec:emu_tree:proc}, into
a public coin interactive proof system with perfect completeness and soundness ${1}/{3}$. 

\subsection{Completeness} \label{subsec:anal_comp}
We claim that the emulation protocol of \expref{Construction}{emu:const} has perfect completeness. That is, if $x$ is a yes-instance, then \newV~ will accept at the end of the interaction with \newP.

Recall that \newP~ builds an emulation tree $\oET$~ from the protocol tree \oPT.  Since $x$ is a yes-instance at least $\comp\cdot 2^{r(n)}$ of the coin tosses lead the verifier to accept and hence the weight of the root of \oPT~ is at least $\comp\cdot 2^{r(n)}$. The weight of the root does not change during the construction of the emulation tree. Thus, the weight of the root of $\oET$~ is  at least $\comp\cdot 2^{r(n)}$ as well. Hence, \newP~ can make a valid initial claim of weight at least $\comp \cdot 2^{r(n)}$

Next, we wish to show that the validations on \expref{Step}{emu:val}  are satisfied for every iteration. This is equivalent to showing that validations are satisfied for every node in the final emulation tree $\oET$. The general framework of the proof consists of going over every validation performed and showing that the property being checked holds for every node in the original protocol tree \oPT, and continues to hold with every modification of the tree as part of the  {\tt Build\_Tree}  procedure. 
\\We denote by $\oPTi{v}$ the tree during construction, after the step that $v$ is identified either as a heavy child, or created as an interval child in the tree.  We can list the intermediate trees according to the order the nodes are placed starting from the root $r$ and until the protocol tree is transformed to an emulation tree: $L=$\oPT$=\oPTi{r},\oPTi{u_1},\dots,\oPTi{u_m}=\oET$. For every tree in this list, we show that for every node $u$ in the tree the validations when $u$ is the input node of the iteration pass. Therefore, it will follow that the validations also pass for every node in the final emulation tree $\oET$.

When we say that a validation passes relative to a (possibly intermediate) tree $\oPTi{z}$ and node $u$ in $\oPTi{z}$, we mean that if the tree $\oPTi{z}$ had been used as an emulation tree then in the iteration which $u$ is the input node, the validation would have passed. Note that possibly the degree of $u$ in $\oPTi{z}$~ is not polynomial in $n$, and hence we can not use $\oPTi{z}$~ to define the emulation protocol, since the verifier should run in polynomial time. However, we can still prove that each validation passes for the intermediate trees assuming that the verifier was not polynomially bounded.  Recall that the nodes in $\oPTi{z}$, on which we did not invoke the  {\tt Build\_Tree}  procedure yet, do not have a range field. We regard the nodes that do not have a range field as having a full range $[0^\ell,1^\ell]$.  

Let $\oPTi{z}$~ be an intermediate tree from the list above, created when assigning the node $z$ (either as an interval child or heavy child) as part of the  {\tt Build\_Tree}  procedure. We assume that the validation we are currently checking holds for every node in $\oPTi{z}$, and show that it also holds in the next step of the construction, that is the next tree in the list $L$. Recall that the next step can either be identifying a heavy child for $z$ as part of the {\tt Build\_Heavy} procedure, or creating an interval child for $z$ as part of the {\tt Build\_Interval} procedure. Denote the child being created or identified by $v$, and the intermediate tree after this modification by $\oPTi{v}$.

Note that, it is not sufficient to show that after the creation or identification of $v$,  the property being checked is maintained for $v$. This is because the procedure might affect the descendants and ancestors of $v$ in $\oPTi{v}$, as well as nodes whose seen-list changes. Exactly which nodes are affected depends on the validation. 


\begin{remark}
	\label{note:children}Let $v$ be a node in some tree $\oPTi{z}$~ that the  {\tt Build\_Tree}  procedure has not been invoked on yet. Recall that the children of $v$ in $\oPTi{z}$~ are children of the node $v'$ in \oPT~ that satisfies $\gamma(v')=\gamma(v)$. Hence, like in the tree \oPT, the transcripts of the children of $v$ in $\oPTi{z}$~ extend the transcript of $v$ by one pair of messages. Furthermore, if we did not invoke  {\tt Build\_Tree}  on $v$ yet, then we also did not invoke it on the descendants of $v$ in $\oPTi{z}$. Thus, the subtree of $\oPTi{z}$~ rooted at $v$, denoted by $\oPTi{z}(v)$, is a subtree of \oPT. (This is true up to the point that $v$ might be an interval node and thus not in \oPT. In this case changing just the node $v$ to the node $v'$ defined above we get a subtree of \oPT.)    
\end{remark} 
Now, we go over the validations in \expref{Step}{emu:val} , which are  stated for a node $u$ and its children $v_1,\dots ,v_d$ provided by the prover as part of the emulation. The validations are numbered as in \expref{Construction}{emu:const}. Assuming that the validations hold for every node in $\oPTi{z}$, we shall prove that these validations hold for every node in $\oPTi{v}$ (the next intermediate tree in the list).  


\Cnote{Showing that the validations in \expref{Step}{emu:val} of the public coin emulation are satisfied is similar in spirit to the proof that the validations in \expref{Step}{p_emu:vald} of the private coin emulation are satisfied, which is given in \expref{Subsection}{p_subsec:comp}. }
\begin{enumerate}[label=(\alph*)]
	\item In this validation, the verifier checks that the descriptions of all the children of $u$ are distinct, \ie, if $v_i$ and $v_j$ are two children of $u$ provided by the prover and $\gamma\left(v_{i}\right)=\gamma\left(v_{j}\right)$
	then $R\left(v_{i}\right)\neq R\left(v_{j}\right)$. \\
	First, note that in \oPT~ all the nodes have distinct transcripts, and in particular for every node all of its children have distinct descriptions. Let $\oPTi{v}$ be an intermediate tree in the list. We assume that this validation passes for all the trees prior to $\oPTi{v}$ in the list and we show it also holds in $\oPTi{v}$. Denote the parent of $v$ in $\oPTi{v}$ by $z$. The only node in $\oPTi{v}$ that may have new children relative to the ones in the proceeding tree in the list $L$ is $z$, and hence from the assumption, it sufficed to show that the validation holds for $z$.  If $v$ is an interval child of $z$ then its description is distinct from the other children of $z$ since the ranges of the interval children are distinct. If $v$ is determined as a heavy child of $z$, then it is a descendant of $z$ in $\oPTi{z}$.  By \expref{Remark} {note:children},  $\oPTi{z}(z)$ is a subtree of \oPT. Hence, each node in $\oPTi{z}(z)$ has a different description. All the heavy children of $z$ in $\oPTi{v}$ are in $\oPTi{z}(z)$, and hence they have distinct descriptions. To conclude note that the heavy children have full range, and interval children have partial range, and hence in particular the heavy and interval children of $z$ are distinct from each other. 
	
	
 
	
	\item In this validation the verifier checks that the weights of the children $v_1,\dots ,v_d$ of $u$ sum up
	to $\wgt{u}$; that is, 
	\mmm{\eqtag{anal:sum_weight}
		\wgt{u}=\sum_{j=1}^{d}\wgt{v_j}
	}
	
	We shall show that this property holds in every step of the construction of the emulation tree $\oET$, for every node in the tree. Starting from the protocol tree \oPT, we know that by definition it satisfies the property that the weight
	of each node is the sum of the weights of its children. (Recall that $z$ is a node that we are invoking the  {\tt Build\_Tree}  procedure on, and $v$ is a node that we determine as a child for $z$.) Assuming that \expeqref{Eq.} {anal:sum_weight} holds for every node in $\oPTi{z}$, we shall show that it holds for every node in $\oPTi{v}$ as well. We consider  two cases, according to if $v$ is a heavy child or interval child of $z$. (Recall that these are the only cases since after invoking  {\tt Build\_Tree(z)} every child of $z$ is either a heavy or interval child.)
	\begin{itemize}
		\item If $v$ is a new heavy child determined for $z$, denote by $z,z_1,\dots,z_k=v$  the path from $z$ to $v$
		in $\oPTi{z}(z)$ before $v$ is moved to be a child of $z$. In this case, after moving $v$ we subtract $\wgt{v}$
		off the weight of $z_{1},\dots,z_{k-1}$. Hence, \expeqref{Eq.}{anal:sum_weight} holds
		for these nodes (we subtract $\wgt{v}$ both from their weight and from the weight of one of their children). \expeqref{Eq.}{anal:sum_weight} also holds for $z$,
		since its weight stays the same because we subtract
		$\wgt{v}$ off the weight of $z_{1}$, and we add an additional
		child $v$ with weight $\wgt{v}$. For the other nodes in $\oPTi{v}$ we neither change their weight nor the weights of their children.
		\item If $v$ is a new interval child of $z$, then the weight of $v$ is the sum of the weights of its children.  \expeqref{Eq.} {anal:sum_weight} also holds for $z$ since its weight stays the same and the sum of the weights of its children also stays the same, this is also true of all the other nodes in $\oPTi{v}$.
		
	\end{itemize}
	Lastly, we note that the clean-up stage, in which we remove nodes whose weights are $0$, does not affect this validation.
	\item \label{comp:td}In this validation, for each $j\in [d]$, the verifier checks
	that the child $v_{j}$ provided by the prover is a transcript descendant of $u$.\\
	Recall that we consider nodes in the protocol tree that do not have a range field (yet) as having a full range. In the protocol tree \oPT~ the transcript of each node is a proper prefix of the transcript of its children. Hence, every node in the protocol tree is a transcript descendant of \expref{type}{def:td_2} (see \expref{Definition}{def:tran_desc}) of its parent.  
	As before, we shall assume that every node in $\oPTi{z}$ maintains the property that it is a transcript descendant of its parent, and show that this property is maintained in the tree $\oPTi{v}$, after the assignment of $v$ as a child of $z$. We only need to show this validation holds for $z$, which possibly has a new child $v$, and for $v$ itself, which might not have been a node in $\oPTi{z}$. The property holds for all the other nodes in $\oPTi{v}$ from our assumption on $\oPTi{z}$. We consider two cases: 
	\begin{itemize}
		\item If $v$ is a heavy child of $z$, then $v$ was a descendant of $z$ in $\oPTi{z}$ that we move to be a child of $z$ (along with its descendants) and set its range to be full range. By our assumption, each node in the path from $z$ to $v$ in $\oPTi{z}$ is a transcript descendant of its parent, so by transitivity (see \expref{Claim}{anal:trans}), $v$ is a transcript descendant of $z$.  
		\item If $v$ is an interval child of $z$ then after the creation of $v$ the transcript of $v$ is equal to the transcript of $z$, and by the construction we know that $R(u)\subseteq R(z)$. Thus, $v$ is a transcript descendant of $z$ of \expref{type}{def:td_1}. 
		\\In addition, the children of $v$ in $\oPTi{v}$ are transcript descendants of $v$. This is because the children of $v$ are all children of $z$ in $\oPTi{z}$, such that their next verifier message is in the range of $v$. Hence, the children of $v$ are transcript descendants of \expref{type}{def:td_2} of $v$ . 
	\end{itemize}
	
	\item In this validation the verifier checks, for each interval child $v_{j}$ of $u$, that the transcript of $v_j$ is equal to the transcript of $u$; that is, if $R\left(v_{j}\right)\neq[0^{\ell},1^{\ell}]$ then $\gamma\left(v_{j}\right)=\gamma\left(u\right)$ must hold.\\
	This holds because the only case where $R\left(v_{j}\right)\neq[0^{\ell},1^{\ell}]$ is if $v_j$ is an interval child of $u$, and in this case $\gamma\left(v_{j}\right)=\gamma\left(u\right)$ because of how we create interval children. Note that once we create an interval child in some intermediate tree it stays a child of its parent throughout the subsequent tree transformations, and hence also in the final emulation tree.
	
	\item In this validation the verifier checks, for each  child $v_j$ of $u$,	that $v_{j}$ is not in a part of the emulation tree that was truncated.  For every $y\in S$, the verifier  checks  that if $y$ is a transcript descendant of $u$, then $v_{j}$ should not be a transcript descendant of $y$. Note that if $y$ is a transcript descendant of $u$ then by validation \ref{comp:td} we know that $y$ is not an ancestor of $u$.
	\\In order to show that the validation is satisfied, we shall first define the notation of seen-list of a node, and then prove that the following claim holds for every node in the emulation tree $\oET$.
		\begin{definition}
			%
			[Seen-list of a node.] \label{seen} %
		When we consider a tree $T$ that is not the final emulation tree, and a node  $v\in T$, then we regard the seen-list of $v$, denoted by $S(v)$, as the list containing the nodes that are ancestors of $v$, augmented with their children.  \end{definition}
	%
	\begin{claim} %
		Let $u\in \oET$~ and $y\in S(u)$ that is not an ancestor of $u$ in $\oET$. If $y$ is a transcript descendant of $u$,  then each descendant $v_j$ of $u$ in $\oET$~ is not a transcript descendant of $y$.
%
\end{claim} %
	Note this is a stronger claim then what we need to show because we only need to show it for the children of $u$ in $\oET$~ and not for each descendant of $u$. 
	
	First, we shall show that the claim holds in the initial protocol tree \oPT. Each node in \oPT~ is a transcript descendant only of its ancestors in the tree. However, each node $u$ is not an ancestor of any node in $S(u)$, so the nodes in $S(u)$  cannot be transcript descendants of $u$. Thus, the claim holds vacuously.
	Next, we shall assume that the claim holds in the tree $\oPTi{z}$ before creating a child $v$ of $z$, and we show that it holds in the tree $\oPTi{v}$ after the identification $v$ as a heavy child of $z$, or creation of $v$ as an interval child. 
	\begin{itemize}
		\item  If  $v$ is identified as a heavy descendant of $z$, then $v$ is moved to be a child of $z$ along with the subtree under it. In order to show that the claim holds in $\oPTi{v}$, it is enough to consider the nodes $c\in\oPTi{v}$ who have new descendants or new nodes in $S(c)$ relative to the ones they had in $\oPTi{z}$. The descendants of the nodes in $\oPTi{v}$ are descendants of it in $\oPTi{z}$. 
		The only nodes in $\oPTi{v}$ that have new nodes in their seen-list are the descendants of $z$, since now $v$ is in their seen-list, whereas $v$ may not have been in their seen-list before the move. Determining the heavy descendants of $z$ is done by searching the tree from bottom to top (this is implied by the definition of heavy descendants, \ref{def:heavy_desc}). It follows that the ancestors of $v$ in $\oPTi{z}$ which are transcript descendants of $z$  have not been identified as heavy descendants of $z$ (or any other node) at this point yet, and so in $\oPTi{z}$ the node $v$ is only a transcript descendant of its ancestors. Thus, if $c$ is a node in $\oPTi{v}$ such that $v\in S(c)$ and $v$ is a transcript descendant of $c$, then $c$ is an ancestor of $v$ in $\oPTi{z}$. It is left to check that the descendants of $c$ in $\oPTi{v}$ are not transcript descendants of $v$. From \expref{Note}{note:children}, it follows that the subtree of $\oPTi{v}$ rooted at $c$, denoted by $\oPTi{v}(c)$, is a subtree of \oPT. Thus, because $v\notin\oPTi{v}(c)$ (recall that $v$ was lifted to be a heavy child of $z$, and $c$ is a descendant of $z$) it follows that the descendants of $c$ are not transcript descendants of $v$. (See \expref{Figure} {fig:comp_trunc_heavy}.)
		\begin{figure}	[h]
			\begin{centering}
				
				\includegraphics[scale=0.5]{drawio/comp_trunc_heavy.pdf}\protect
				\caption{$v$ is identified as a heavy child of $z$, and $c$ is a descendant of $z$.}
				\label{fig:comp_trunc_heavy}
				\par\end{centering}
			
		\end{figure}
		\item Let $v$ be an interval child created for $z$. We shall assume that the claim holds in the tree $\oPTi{z}$ before the assignment of $v$, and show that it holds in $\oPTi{v}$. It is enough to show that the claim holds when the node $u$  is one of the following: either a new interval child $v$ or a node in $\oPTi{v}$ that has new descendants  or a node in $\oPTi{v}$ that has new nodes in their seen-list (relative to the ones in $\oPTi{z}$). (For the other nodes in $\oPTi{v}$ the claim follows from our assumption regarding $\oPTi{z}$.) 
		\\The only nodes in $\oPTi{v}$ that have new descendants that they did not have in $\oPTi{z}$ are the ancestors of $v$ in $\oPTi{v}$, which now have $v$ as their descendant. Let $d$ be some ancestor of $v$ in $\oPTi{v}$,  and let $c\in S(d)$ be a transcript descendant of $d$. We need to show that $v$ is not a transcript descendant of $c$. We know that $v$ has children in $\oPTi{v}$ otherwise it would not been created as an interval node, so let $t$ be a child of $v$ in $\oPTi{v}$ (see \expref{Figure} {fig:comp_trunc_heavy2}). It follows that $t$ is a transcript descendant of $v$. Assume by contradiction that  $v$ is a transcript descendant of $c$. Hence, by transitivity, $t$ is also transcript descendants of $c$. In addition, $t$ is a descendant of $d$ in $\oPTi{z}$. This is in contradiction to our hypothesis that the claim holds in $\oPTi{z}$.
		\begin{figure}	[h]
			\begin{centering}
				
				\includegraphics[scale=0.5]{drawio/comp_trunc_heavy2.pdf}\protect
				\caption{$v$ is an interval child created by uniting 3 children of $z$.}
				\label{fig:comp_trunc_heavy2}
				\par\end{centering}
			
		\end{figure} 
		
		The nodes whose seen-list $S$ increases in $\oPTi{v}$ relative to $\oPTi{z}$ are the descendants of $z$, because $v$ is added to their list. However, $v$ cannot be a transcript descendant of any descendant of $z$. This is because the heavy children of $z$ have longer transcripts than $v$, so $v$ cannot be a transcript descendant of them, or of their descendants (this follows from validation \ref{emu:val:td} and transitivity). The other interval children of $z$ have a range that is disjoint from the range of $v$. Thus, they and their descendants cannot be transcript descendants of $v$.
		\\Lastly, we show that the claim holds for $v$ as well. Let there be a some node $b\in S(v)$  which is a transcript descendant of $v$. We need to show that the descendants of $v$ in $\oPTi{v}$ are not transcript descendants of $b$. There are two different options. 
		\begin{itemize}
			\item Either $b\in S(z)$ in $\oPTi{z}$, like node $c$ in \expref{Figure} {fig:comp_trunc_heavy2}. The node $b$ is a transcript descendant of $v$ which  is a transcript descendant of $z$, so by transitivity $b$ is a transcript descendant of $z$. Every descendant of $v$ in $\oPTi{v}$ is a descendant of $z$ in \oPT{z}. Hence, from the fact that the claim is true for $z$ in $\oPTi{z}$ we know that the descendants of $v$ in $\oPTi{v}$ are not transcript descendants of $b$.
			\item If $b\in S(v)$ but $b\notin S(z)$  then $b$ must be a child of $z$, like node $y$ in \expref{Figure}{fig:comp_trunc_heavy2}. Since $b$ is a transcript descendant of $v$ then $b$ must be a heavy child of $z$. (If $b$ is an interval child of $z$, like $v$ is, then $b$ cannot be a transcript descendant of $v$ since their ranges are disjoint.) We did not invoke  {\tt Build\_Tree}  on $v$  yet, so by \expref{Note}{note:children}, it follows that $\oPTi{v}(v)$ is a subtree of \oPT. Hence, from the fact that $b$ is not in $\oPTi{v}(v)$ it follows that the transcript descendants of $b$ are not in $\oPTi{v}(v)$ either. In other words, the descendants of $v$ in $\oPTi{v}$ are not transcript descendants of $b$.  
		\end{itemize} 
		
	\end{itemize}
	
	\item In this validation, the verifier checks that the ranges of all the interval children of $u$ are disjoint; that is, for every two interval children $v_{j}$ and $v_{k}$ of $u$, the verifier checks that $R\left(v_{j}\right)\cap R\left(v_{k}\right)=\emptyset$.\\
	By the way we create the interval children it holds that the start of the range of each interval child is after the end of the range of the previous child created.
	\item In this validation, the verifier checks, for each child $v_j$ of $u$, that $\gamma(v_j)$ is \emph{prover consistent} (see \expref{Definition} {def:prover_consistent}) with respect to the other transcripts of nodes in $S(u)$ and with regarding to the transcripts of the other children of $u$.
	\\In the original protocol tree, \oPT, every two nodes are prover consistent since \orgP~ is deterministic. (If there were two partial transcripts in \oPT~ whose maximal common prefix ends with a verifier message it would mean that the prover can responds in different ways to the same partial transcripts.) The transcripts of the nodes in $\oET$~ all appear in \oPT, so every two transcripts in $\oET$~ are prover consistent as well.  
	
\end{enumerate}
The final checks are satisfied because according to \expref{Claim} {emu_tree:prop:leaves} the leaves of the emulation tree $\oET$~ are the leaves of the protocol tree whose weights are 1. Hence, $V_0\left(x,\rho,\alpha_1,\dots, \alpha_m\right)=1$, 
and for every $i=1,\dots,m$ it holds that $\alpha_{i}=V_0\left(x,\rho,\beta_{1},\dots,\beta_{i-1}\right)$. In addition $\wgt{v}=1$.
\subsection{Soundness} \label{subsec:anal_soundness}



We show that if $x$ is a no-instance, then when interacting with any prover \clP~ for the public coin emulation protocol, the new public coin verifier \newV~ accepts with probability at most {1}/{3}.
We do so by showing that on each iteration  there is a gap (in expectation) between
the weight of the node claimed by
the prover, and the actual weight %
of the node. Starting from the root,
if $x$ is a no-instance, then the initial prover's claim is that
the weight of the node sampled should be at least $\comp\cdot2^{r(n)}$ (or else the verifier rejects upfront),
but the number of coin sequences that lead the verifier to accept at the end of the interaction, and hence the actual weight of the
node, is at most $\sound\cdot2^{r(n)}$. 
We want to show that this gap is approximately maintained
with high probability at least  until the last iteration, and hence the verifier
rejects.

In order to proceed with this analysis, we need to define the notion
of ``actual weight of a node'' 
in the emulation tree. We do this by considering the weight relative
to the protocol tree of the original interactive proof
system. The verifier of the original protocol system which we refer to is
of course \orgV,  the verifier of the original proof system being emulated. However, choosing the prover of the original system is less straightforward. We shall show that a prover's strategy for the emulation protocol yields a prover strategy for the original protocol.

\Cnote{\expref{Subsection}{subsub:anal_derive} is a more involved version of the private coin proof of soundness in \expref{Section}{p_subsec:soundness}. The other two components of the soundness analysis of the public coin system (which
%
define   %
the notion of actual weight of a node, and bound the gap between the claimed and actual weight) 
are not required for the private coin soundness analysis. }

\subsubsection[Deriving a prover strategy]{Deriving a prover strategy for the original proof system}\label{subsub:anal_derive}

We can assume without loss of generality that \clP~  is deterministic since for every probabilistic prover there is a deterministic prover for which the verifier's acceptance probability is at least as high. (Recall that we want to show that the verifier rejects with high probability. Hence, it suffices to take a deterministic prover which the verifier rejects with lower probability when interacting with, and showing that this probability is still high enough). 

We can also assume, without loss of generality, that the strategy of  \clP~ is such that the verifier does not abort until the final checks. This is because every prover strategy in which the verifier aborts in one of the intermediate checks can be modified to a prover strategy such that the verifier does not abort until the final checks and the verifier's acceptance probability is at least as large. (The prover can compute the transcripts of the children such that they are different continuations of their parent and prover consistent with the list $S$ instead of every node where the verifier would have aborted in the intermediate checks.)
Since \clP~ is deterministic and the verifier doesn't abort until the final checks, the prover's strategy can be represented using an emulation tree which we denote by $\cET$. 

 We show that we can extract a deterministic strategy  \clPo~ for the original prover using the strategy of \clP. We define a strategy for \clPo~ by using the transcripts in $\cET$. That is, for each $u\in \cET$~ with transcript $\gamma\left(u\right)=\alpha_{1}\beta_{1}\dots,\alpha_{j}\beta_{j}$
we define \clPo$\left(x,\alpha_{1},\dots,\alpha_{i}\right)\coloneqq\beta_{i}$
for all $i\leq j$. We extend \clPo's strategy to transcripts that do not appear in $\cET$~ in an arbitrary way.

In order to show that the strategy of \clPo~ is well defined we need to show that no two nodes  $u,v\in \cET$~ share the prefix of prover-verifier interaction but differ on the prover's response. That is, we show that every two nodes $u,v\in \cET$~ are \textbf
{prover consistent} (see \expref{Definition}{def:prover_consistent}). 

For a node $u\in \cET$~ provided during the emulation, recall that we denote by $S\left(u\right)$ the seen-list (see \expref{Definition}{seen})  the list of nodes from $\cET$~ at the beginning of the iteration in which $u$ was the input node (\ie, was the node handled on that iteration). That is, the nodes in $S(u)$ are the ancestors of $u$ in $\cET$~  and their children. 

To show that every two nodes $u,v\in \cET$~ are prover consistent, as well as for other parts of the soundness proof, we rely on the following claim.


\begin{claim}
%
[Transcript descendancy forms a tree] 	\label{anal:prop2}
	Let $w\in \cET$~ and $u,z\in S(w)$. Assume that the strategy of \clP~ is such that the verifier does not abort until the final checks. Let $\ell$ be a node with a range and a transcript field that is a transcript descendant of both
	$z$ and $u$. Then either $u$ is a transcript descendant of $z$
	or $z$ is a transcript descendant of $u$.
\end{claim}	

\begin{proof}
	First, note that this claim is not true if the prover's strategy is not one in which the verifier does not abort until the final checks. For example, if $\ell$ is a transcript descendant 	of type (\ref{def:td_1}) of both $u$ and $z$, then $\gamma\left(u\right)=\gamma\left(z\right)=\gamma\left(\ell\right)$,
	and $R\left(\ell\right)$ is contained in both $R\left(u\right)$
	and in $R\left(z\right)$. However, $R\left(u\right)$ and $R\left(z\right)$ may not be contained one in the other, and hence $u$ is not a transcript descendant of $z$ and $z$ is not a transcript descendant of $u$. 
	
	Since $\ell$ is a transcript descendant of $u$ and of $z$, then both
	$\gamma\left(u\right)$ and $\gamma\left(z\right)$ are prefixes of $\gamma\left(\ell\right)$.
	Assume, without loss of generality, that $\left|\gamma\left(z\right)\right|\geq\left|\gamma\left(u\right)\right|$. It follows that $\gamma\left(u\right)$ is a prefix of $\gamma\left(z\right)$. (See \expref{Figure}{fig:claim14_1}.)
	
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/claim14_1.pdf}\protect
			\caption{The transcripts of $u$,$z$ and $\ell$ when $\left|\gamma\left(z\right)\right|\geq\left|\gamma\left(u\right)\right|$  }
			\label{fig:claim14_1}
			\par\end{centering}
		
	\end{figure}
	
	The first case is that $\gamma\left(u\right)$ is a strict prefix
	of $\gamma\left(z\right)$. In this case $\gamma\left(u\right)$ is
	also a strict prefix of $\gamma\left(\ell\right)$ and hence $\ell$
	is a transcript descendant of type (\ref{def:td_2}) of $u$ . Denote the transcripts of $u$ and $z$ by $\gamma\left(u\right)=\alpha_{1}\beta_{1}\dots\alpha_{i}\beta_{i}$
	and $\gamma\left(z\right)=\alpha_{1}\beta_{1}\dots\alpha_{j}\beta_{j}$,
	for $j>i$. For an index $i$ and a node $u$ denote by $\alpha_i^u$ the $i$th verifier's message in the transcript of $u$. Because $\gamma\left(z\right)$ is a prefix of $\gamma\left(\ell\right)$
	it follows that $\alpha_{i+1}^{z}=\alpha_{i+1}^{\ell}$. From the
	fact that $\ell$ is a transcript descendant of type (\ref{def:td_2}) of $u$ we know that
	$\alpha_{i+1}^{\ell}\in R\left(u\right)$. Thus, $\alpha_{i+1}^{z}\in R\left(u\right)$
	and $\gamma\left(u\right)$ is a strict prefix of $\gamma(z)$, so $z$
	is a transcript descendant of $u$ (of type (\ref{def:td_2})). 
	\\The second case is that the transcripts of $u$ and $z$ are equal; that is,
	$\gamma\left(u\right)=\gamma\left(z\right)=\alpha_{1}\beta_{1}\dots\alpha_{i}\beta_{i}$.
	In this case we need to show that $R\left(u\right)\subseteq R\left(z\right)$
	or $R\left(z\right)\subseteq R\left(u\right)$. If $R\left(u\right)=\left[0^{\ell},1^{\ell}\right]$
	then $R\left(z\right)\subseteq R\left(u\right)$,
	so $z$ is a transcript descendant of $u$ of type (\ref{def:td_1}). Similarly, if $R\left(z\right)=\left[0^{\ell},1^{\ell}\right]$ then $u$ is a transcript descendant of $z$ of type (\ref{def:td_1}).
	
	We are left with the case that $\gamma(u)=\gamma(z)$ and both $u$ and $z$ do not have a full range. In this part we consider the relation between $u$ and $z$ in $\cET$. Recall that $S(w)$ contains the nodes in the path from the root to $w$, augmented with their children. 

	Denote the least common ancestor of $u$ and $z$ in $\cET$~ by
	$v$. If $v=u$ then there is a path from $v$ to $z$.
	Since validation \ref{emu:val:td} passes for every node in $\cET$, each node in the path is a transcript descendant
	of its predecessor, so from transitivity $z$ is a transcript descendant
	of $v$. Similarly, if $v=z$ then $u$ is a transcript descendant of $z$. 
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/claim14_2.pdf}\protect
			\caption{$z$ and $u$ are two nodes in $S(w)$ whose least common ancestor is $v$.  }
			\label{fig:claim14_2}
			\par\end{centering}
		
	\end{figure}
	
	Otherwise, $v$ is neither equal to $u$ nor to $z$. However, at least one of the nodes $u$ or $z$ is a child of $v$ in $\cET$~ (because of the structure of $S(w)$, see \expref{Figure}{fig:claim14_2} for illustration). Assume, without loss of generality, that $z$ is a child of $v$. The range of $z$ is not full so $z$ must be an interval child of $v$ and $\gamma(v)=\gamma(z)$. It follows that $\gamma(u)=\gamma(v)$ so $u$ is either another interval child of $v$ or a descendant of an interval child of $v$. Thus, the ranges of $u$ and $z$ are disjoint because they belong
	to different branches of interval children of $v$, and the ranges of the interval children are disjoint from \expref{validation}{emu:val:disj}. This is in contradiction to the assumption in the claim that $\gamma(\ell)$ is a transcript descendant of both $\gamma(u)$ and $\gamma(z)$. To see why this is a contradiction consider two cases. If $\gamma(\ell)=\gamma(u)=\gamma(z)$ then $\ell$ is a transcript descendant of type (\ref{def:td_1}) of both $u$ and $z$ and hence $R(\ell)\subseteq R(u)$  and $R(\ell)\subseteq R(z)$, and so $R(u)$ and $R(z)$ cannot be disjoint. If $\gamma(u)=\gamma(z)$ are strict prefixes of $\gamma(\ell)$ then $\ell$ is a transcript descendant of $u$ and $z$ of type (\ref{def:td_2}). Hence, $\alpha_{i+1}^\ell \in R(u)$ and $\alpha_{i+1}^\ell \in R(z)$, so also in this case $R(u)$ and $R(z)$ cannot be disjoint.
\end{proof}
%

We are ready to prove the prover consistency property of the emulation tree.
\Cnote{Note that the following proof is a more involved version of the proof of \expref{Lemma}{private:consis} in \expref{Section}{p_sec:anal}.}

\begin{lemma} 
	%
	[Prover consistency of the emulation tree] \label{anal:consis} %
	
	%
	If the strategy of the prover \clP~
	for the new emulation is such that the verifier \newV~ does not abort until the final checks then every two transcripts of nodes in the emulation tree $\cET$~ are prover consistent.
\end{lemma}
\begin{proof}
 Let $u$ and $v$ be two nodes in the emulation tree $\cET$, we wish to show that their transcripts $\gamma(u)$ and $\gamma(v)$ are prover-consistent. If one of the nodes is a descendant of the other node in the emulation tree, with out loss of generality, we assume that $v$ is a descendant of $u$. We denote by $S'(v)$ the seen-list of the parent of $v$. That is, if $u$ is the parent of $v$ in $\cET$~ then $S'(v)=S(u)$.  In the general case that $v$ is a descendant of $u$ then $u\in S'(v)$ and \expref{validation}{emu:val:pc} is satisfied so $\gamma(u)$ and $\gamma(v)$ are prover-consistent. Otherwise, denote by $z$ the least common ancestor of $u$ and $v$, and $a$ and $b$ the children of $z$ that are ancestors of $u$ and $v$ respectively. (It is possible that $a=u$ or $b=v$.) See \expref{Figure}{fig:PC} for illustration.
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/PC.pdf}\protect
			\caption{The subtree of $\cET$~ that contains $u$ and $v$}
			\label{fig:PC}
			\par\end{centering}
		
	\end{figure}
	
	Consider the case that at least one of the transcripts of $u$ and $v$ equals the transcript of $a$ or $b$, respectively (this also covers the case that $u$ or $v$ are children of $z$). Assume, without loss of generality, that $\gamma(a)=\gamma(u)$. We know that $\gamma(v)$ and $\gamma(a)$ are prover consistent, because $a\in S'(v)$ and \expref{validation}{emu:val:pc} is satisfied. (If $v=b$ then $a\notin S'(v)$ but then $\gamma(v)$ and $\gamma(a)$ are prover consistent also from \expref{validation}{emu:val:pc} because they are both children of $z$.) Hence, $\gamma(v)$ and $\gamma(u)$ are also prover consistent. 
	
	Otherwise, $\gamma(a)$ is a proper prefix of $\gamma(u)$, and $\gamma(b)$ is a proper prefix of $\gamma(v)$. We consider three cases according to the relation between $\gamma(a)$ and $\gamma(b)$. 
	
	First, consider the case that  $\gamma(a)$ is not a prefix of $\gamma(b) $ and $\gamma(b)$  is not a prefix of $\gamma(a)$.
	It follows that the maximal prefix on which $\gamma(a)$ and $\gamma(b)$ agree upon is a proper prefix of both. This common prefix equals the maximal prefix on which  $\gamma(u)$ and $\gamma(v)$ agree. We know that $\gamma(a)$ and $\gamma(b)$ are prover-consistent because the prover provides $a$ along with $b$ as children of $z$ and we assume that \expref{validation} {emu:val:pc} is satisfied. Since the maximal prefix that $\gamma(u)$ and $\gamma(v)$ agree on is equal to the maximal prefix that $\gamma(a)$ and $\gamma(b)$  agree on, it follows that $\gamma(v)$ and $\gamma(u)$ are also prover-consistent. See \expref{Figure}{fig:PC2} for illustration.
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/PC2.pdf}\protect
			\caption{ $\gamma(a)$ and $\gamma(b)$ agree on the prefix in white, while $\gamma(a)$ is a prefix of $\gamma(u)$ and $\gamma(b)$ is a prefix of $\gamma(v)$.   }
			\label{fig:PC2}
			\par\end{centering}
		
	\end{figure}
	
	
	
	Next, consider the case when $\gamma(a)=\gamma(b)$, and assume that the transcript of $a$ and $b$ contain messages from $i$ rounds. In this case both $a$ and $b$ are interval children of $z$. This is because at least one of them needs to have a partial transcript, otherwise \expref{validation}{emu:val:diff} would be violated. Assume without loss of generality that $a$ has a partial transcript. Because $a$ has a partial transcript, from \expref{validation}{emu:val:parint} the transcript of $z$ is equal to the transcript of $a$ and $b$, and the range of $z$ is full. Hence, if the range of $b$ is full then the description of $b$ and $z$ are the same, and in particular $b$ is not a transcript descendant of $z$, which violates \expref{validation}{emu:val:td}.  We have established that $a$ and $b$ are interval children of $z$ and from \expref{validation} {emu:val:disj} it follows that $R(a)\cap R(b)=\emptyset$. Note that $u$ is a transcript descendant of $a$, and $v$ is a transcript descendant of $b$ of \expref{type} {def:td_2}, since the transcripts $\gamma(a)$ and $\gamma(b)$ are  proper prefixes of $\gamma(u)$ and $\gamma(v)$ respectively. As a result, $\alpha_{i+1}^v\in R(b)$ and $\alpha_{i+1}^u\in R(a)$. It follows that $\alpha_{i+1}^v\neq\alpha_{i+1}^u$, which means that the maximal prefix that $\gamma(u)$ and $\gamma(v)$ agree on is equal to $\gamma(a)=\gamma(b)$. Hence, the maximal prefix ends with a prover message and so $\gamma(u)$ and $\gamma(v)$ are prover consistent.
	
	We are left with the case that one of the transcripts $\gamma(a)$ and $\gamma(b)$  is a proper prefix of the other, and assume, without loss of generality, that $\gamma(a)$ is a proper prefix of $\gamma(b)$. Denote the transcript of $b$ by $\gamma(b)=\alpha_1\beta_1,\dots,\alpha_k\beta_k$. Since $\gamma(a)$ is a proper prefix of $\gamma(b)$, and $\gamma(z)$ is a prefix of both $\gamma(b)$ and $\gamma(a)$ (since they are transcript descendants of $z$) it follows that $\gamma(b)\neq \gamma(z)$ and so $b$ is not an interval child of $z$ by \expref{validation}{emu:val:parint} and hence $R(b)=[0^\ell,1^\ell]$. 
	
	We claim that $u$ is not a transcript descendant of $b$. Assume, by contradiction, that $u$ is a transcript descendant of $b$.  Note that $a$ is not a transcript descendant of $b$, since we assumed that $\gamma(a)$ is a proper prefix of $\gamma(b)$. Denote the nodes in the path from $a$ to $u$ in $\cET$~ by $a=a_0,a_1,\dots ,a_k=u$ and by $a_{j}$ the first node in the path such that $a_{j}$ is not a transcript descendant of $b$ and $a_{j+1}$ is a transcript descendant of $b$. Since $a_{j+1}$ is a transcript descendant of both $a_{j}$ and $b$, which are in $S(a_{j+1})$, and since $a_j$ is not a transcript descendant of $b$, it follows by \expref{Claim}{anal:prop2} that $b$ is a transcript descendant of $a_{j}$ (see \expref{Figure}{fig:PC3}). Hence, in the iteration where the prover provides node $a_{j+1}$ as a child of $a_{j}$ there is a violation to \expref{validation}{emu:val:trunc}, because $a_{j+1}$ is a transcript descendant of $b\in S(a_{j})$ and $b$ is a transcript descendant of $a_{j}$. Put differently, $a_{j+1}$ is part of a truncation from $a_{j}$. Hence, we reached a contradiction to the hypothesis that \newV~ does not abort in the intermediate validations, and so $u$ cannot be a transcript descendant of $b$. 
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/PC3.pdf}\protect
			\caption{The dashed arrow pointing from $b$ to $a_{j+1}$ represent the fact that $a_{j+1}$ is a transcript descendant of $b$, and similarly that $b$ is a transcript descendant of $a_j$.   }
			\label{fig:PC3}
			\par\end{centering}
		
	\end{figure}
	
	We showed that $u$ is not a transcript descendant of $b$ and $R(b)=[0^\ell,1^\ell]$, so  $\gamma(b)$ is not a prefix of $\gamma(u)$. (If $\gamma(b)$ is a proper prefix of $\gamma(u)$ then $u$ is a transcript descendant of $b$ of \expref{type}{def:td_2} since $R(b)=[0^\ell,1^\ell]$, whereas if $\gamma(b)=\gamma(u)$ then $R(u)\subseteq [0^\ell,1^\ell]=R(b)$, which means that $u$ is a transcript descendant of \expref{type} {def:td_1} of $b$.) Let $u'$ be the parent of $u$ in $\cET$. We know that $b\in S(u')$  because $b$ is a child of $z$, which is an ancestor of $u'$. Hence, by \expref{validation} {emu:val:pc} the transcript of $u$, which is a child of $u'$ and the transcript of $b\in S(u')$ are prover consistent. It follows that the maximal common prefix of $\gamma(u)$ and $\gamma(b)$ is a proper prefix of $\gamma(b)$ that ends with a prover message. 
	
	Lastly, note that from \expref{validation}{emu:val:td} each node in the path from $b$ to $v$ is a transcript descendant of its parent, so from transitivity $v$ is a transcript descendant of $b$. Thus, $\gamma(b)$ is a prefix of $\gamma(v)$. It follows that the maximal common prefix of $\gamma(v)$ and $\gamma(u)$ is contained in the maximal common prefix of $\gamma(u)$ and $\gamma(b)$, so it ends with a prover message (See \expref{Figure}{fig:PC4}). 
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/PC4.pdf}\protect
			\caption{The maximal common prefix between $\gamma(u)$ and $\gamma(b)$ appears in white. Since $\gamma(b)$ is a prefix of $\gamma(v)$ the maximal common prefix of $\gamma(u)$ and $\gamma(v)$ is the same as the former.  }
			\label{fig:PC4}
			\par\end{centering}		
	\end{figure}	
\end{proof}

\subsubsection[Actual weight of a node]{Actual weight of a node in $\cET$}\label{subsub:anal_real}
We want to introduce the notion of the ``actual weight''
of a node in $\cET$. This ``actual weight'' 
should be proportional to the probability that the node represents a partial interaction of the verifier \orgV~ with the prover \clPo, which was extracted in the previous subsection, and that this partial interaction leads \orgV~ to accept. Hence, it is natural to use the weights in $\clPT$ for this value. However, the weights in $\clPT$ do not reflect the truncations the prover \clP makes, and so they are not specific to the emulation tree and the way which it was constructed. Thus, we also need to use the tree $\cET$, which contains the information about the truncations. Another difficulty that arises is that the nodes in $\clPT$ are only heavy nodes. Hence, instead of using the weight of a node in $\clPT$ we consider the number of leaves whose weights are $1$ and are transcript descendants of it.    

\begin{definition}
 %
[Actual weight of $u\in \cET$~ relative to protocol tree $\clPT$] %
	For a node $u\in \cET$~  denote by $\Leaf{u}$ the set
	of leaves in $\clPT$ that are transcript descendants of $u$ and
	whose weight is $1$. (The definition of transcript descendants relates to nodes that have a transcript and range field, so we consider the nodes in $\clPT$  as if they have full range $[0^\ell,1^\ell]$.) 
	\\Denote by $Trunc\left(u\right)$
	the non-ancestors of $u$ in $S\left(u\right)$ (relative to the emulation tree $\oET$) that are transcript descendants
	of $u$. (In particular, $u\notin Trunc(u)$.) 
	\\We define $\LPr{u}$  as
	\mmm{
		\LPr{u}=\left\{ L^{1}\left(u\right)\bigg \backslash\bigcup_{z\in Trunc\left(u\right)}L^{1}\left(z\right)\right\} 
	}
We define the actual weight of $u$,  denoted by $\rw{u}$, to be the size of the set $\LPr{u}$. That is, 
	\mmm{
		\rw{u}=\left|\LPr{u}\right|
	}
\end{definition}
For the soundness proof, we use the following claim regarding the actual weight of a node in the emulation tree $\cET$, which asserts that the actual weight of a node is at least as large as the sum of the weights of its children. 

\begin{claim} \label{anal:whole_is_larger}
	Assume that the strategy of the prover \clP~  is such that the verifier does not abort until the final checks. Let $u\in \cET$~ and $v_1,\dots ,v_d$ children of $u$ in $\cET$.	Then
	\mmm{
		\sum_{i=1}^{d}\rw{v_i}\leq \rw{u}\mathdot
	}	
\end{claim}	
\begin{proof}
	The proof follows from the following two facts: 
	\begin{fact}\label{anal:disjoint_leaves}
		For each distinct $i,j\in [d]$, it holds that $\LPr{v_j}\cap \LPr{v_i}=\emptyset$.
	\end{fact}
	\begin{fact}\label{anal:contain_leaves}
		For each $j\in [d]$, it holds that $\LPr{v_j}\subseteq \LPr{u}$.
	\end{fact}
	
	
	We start with the proof of \expref{Fact}{anal:disjoint_leaves}. Consider two different cases. The first case is if $v_{i}$ and
	$v_{j}$ are not transcript descendants of each other ($v_{i}$ is
	not a transcript descendant of $v_{j}$ and vice versa). If $\ell\in \LPr{v_j}$, then $\ell$ is a transcript
	descendant of $v_{j}$. Assume by contradiction that  $\ell\in \LPr{v_i}$. Hence, $\ell$ is also a transcript
	descendant of $v_{i}$, and $v_{i}$ and
	$v_{j}$ are in $S(v_{j})$. From \expref{Claim}{anal:prop2} one of $v_i$ and $v_j$ is a transcript descendant of the other, in
	contradiction to the our assumption for this case. 
	
	The second case is that $v_{j}$ (respectively $v_i$) is a transcript descendant of
	$v_{i}$ (respectively $v_j$). Without loss
	of generality, assume that $v_{j}$ is a transcript descendant of $v_{i}$.
	In this case $v_{j}\in Trunc\left(v_{i}\right)$, since $v_{j}\in S(v_i)$ and $v_j$ is not an ancestor of $v_i$. From the fact that $\ell\in \LPr{v_j}$
	it follows that $\ell\in L^{1}\left(v_{j}\right)$. By the definition of $L^{\widetilde{P}}$ the leaves in $L^1(v_j)$ are removed from the set $\LPr{v_i}$, and hence $\ell\notin \LPr{v_i}$. This completes the proof of \expref{Fact} {anal:disjoint_leaves}. 
	
	Turning to the proof of \expref{Fact}{anal:contain_leaves}, let $\ell\in \LPr{v_j}$. Therefore, the leaf $\ell$
	is a transcript descendant of $v_{j}$. From \expref{validation}{emu:val:td} it follows that 
	$v_{j}$ is a transcript descendant of $u$. Therefore, by transitivity,
	$\ell$ is a transcript descendant of $u$ so $\ell\in L^{1}\left(u\right)$.
	Assume by contradiction that there exists $z\in Trunc\left(u\right)$
	such that $\ell\in L^{1}\left(z\right)$ and hence $\ell\notin \LPr{u}$. Recall that $z\in Trunc(u)$ means that  $z$ is a transcript descendant of $u$ and $z\in S(u)$ (See \expref{Figure}{fig:weight_sum}). This also means that $z\in S(v_j)$ since $S(u)\subseteq S(v_j)$. It follows that $\ell$ is a transcript
	descendant of both $z$ and $v_{j}$ which are in $S(v_j)$. Hence, from \expref{Claim}{anal:prop2} there are two options:
	\begin{itemize}
		\item The first option is that $v_{j}$ is a transcript descendant of $z$.
		However, this cannot happen since in the iteration where $u$ is the input node, by \expref{validation}{emu:val:trunc} it cannot
		be that $v_{j}$ is a transcript descendant of $z\in S(u)$
		and $z$ is a transcript descendant of $u$.
		\item The second option is that $z$ is a transcript descendant of $v_{j}$.
		This cannot be the case because $z\in S(u)$ implies that $z\in S\left(v_{j}\right)$ and so
		$z\in Trunc\left(v_{j}\right)$. But because $\ell\in L^{1}\left(z\right)$
		we get that $\ell\notin \LPr{v_j}$, in contradiction to our hypothesis. 
	\end{itemize}
	
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/weight_sum.pdf}\protect
			\caption{The emulation tree after $z$ has been truncated and moved to be a chid of $r$.}
			\label{fig:weight_sum}
			\par\end{centering}
		
	\end{figure}
	Thus, we reach a contradiction in both options, so in particular there does not exist $z\in Trunc(u)$ such that $\ell\in L^1(z)$. Hence, $\ell\in \LPr{u}$. 
\end{proof}

\subsubsection{Bounding the gap} \label{subsub:anal_actual}

Next, we define the gap between the actual weight and the claimed weight, which we use for the analysis.

\begin{definition}
%
[Gaps] \label{anal:def:gaps} %
	The gap for node $u \in \cET$~ denoted by
	$\gfunc{u}$, is the ratio between $\rw{u}$,
	the actual weight of node $u$ according to the strategy of $\widetilde{P}$, and the
	claimed weight $\wgtc{u}$. 
	\mmm{
		g\left(u\right)={\rw{u}}/{\wgtc{u}}
	}
	
	
	Note that we can assume without loss of generality
	that $\wgtc{u}>0$ since the prover can omit the nodes with claimed weight equal to $0$. 
\end{definition}
Let $v$ be a node chosen on the $i$th iteration of a random execution of the emulation protocol by $\widetilde{P}$ and $V$. We denote the value of the gap on the $i$th iteration by $g_{i}=g\left(v\right)$, and by $g_{0}$ the value of the gap of the
root $r$. 

We consider the $m'$ iteration emulation protocol defined in \expref{Construction} {emu:const}, and
fix an iteration  $i\in\left[m'\right]$ as well as the values
of the coin tosses, denoted by $r_{1},\dots,r_{i-1}$, obtained during the emulation of the first $i-1$
iterations. Denote by $u$ the node sampled
on iteration $i-1$. If $i=1$ then $u$ is the root of the emulation tree. The description of the node $u$ and $g_{i-1}=g\left(u\right)$
are fixed. Denote by $G_{i}$ the random variable that represents
$g_{i}$ at the end of the $i$th iteration, which depends on the child of $u$ chosen on the $i$th iteration. Towards proving \expref{Claim}{anal:gap_change} below, we analyze the change in the
gap on the $i$th iteration, and show that it does not increase too
much in expectation. 
\begin{claim} \label{anal:gap_change}
	Consider a prover strategy for the proposed public coin emulation in which the verifier does not abort until the final checks. For any sequence of values of the coin tosses  $r_{1},\dots,r_{i-1}$, it holds that 
	\mmm{
		\mathbb{E}_{r_{i}}\left[G_{i}|\,r_{1},\dots,r_{i-1}\right]\leq g_{i-1} \cdot \left (1+{1}/{r(n)}\right)
	}
\end{claim}

\begin{proof}
	Let $v_{1},\dots,v_{d}$ be the children of $u$, that were provided
	by the prover in the emulation. Since $G_{i}$ is the gap after the $i$th
	iteration, its value dependents on the child of $u$ that was chosen
	\mmm{
		\mathbb{E}\left[G_{i}|\,r_{1},\dots,r_{i-1}\right] & =  \sum_{j=1}^{d}\textbf{Pr}\left[v_{j}\,\text{chosen}\right]\cdot g\left(v_{j}\right)\mathdot \eqtag{eq:expec}
	}
	By the definition of the gap for node $v_{j}$,
	\mmm{
		g\left(v_{j}\right)=\frac{\rw{v_j}}{\wgtc{v_j}}\mathdot  \eqtag{eq:1}
	}
	According to \expref{Step} {emu:const:prob} of the emulation protocol, 
	\mmm{
		\textbf{Pr}\left[v_{j}\,\text{chosen}\right]\leq\frac{\wgtc{v_j}}{\sum_{i=1}^{d}\wgtc{v_i}}\cdot \left (1+{1}/{r(n)}\right )\eqtag{eq:chosen} \mathdot 
	}
	Plugging in \expeqref{Eq.} {eq:1} and \expeqref{Eq.}{eq:chosen} in \expeqref{Eq.} {eq:expec}
	we have
	\mmm{
		\mathbb{E}\left[G_{i}|\,r_{1},\dots,r_{i-1}\right] & \leq  \sum_{j=1}^{d}\frac{\wgtc{v_j}}{\sum_{i=1}^{d}\wgtc{v_i}}\cdot \left (1+{1}/{r(n)}\right)\cdot\frac{\rw{v_j}}{\wgtc{v_j}}\\
		& =  \sum_{j=1}^{d}\frac{\rw{v_j}}{\sum_{i=1}^{d}\wgtc{v_i}}\cdot\left  (1+{1}/{r(n)}\right)\mathdot \eqtag{eq:expec2}
	}
	From \expref{validation}{emu:val:sum} it holds that
	\mmm{
		\wgtc{u}=\sum_{i=1}^{d}\wgtc{v_i}\eqtag{eq:sum claimed weights}\mathdot
	}
	Hence, combining \expeqref{Eq.}{eq:sum claimed weights} and \expref{Claim} {anal:whole_is_larger}
	in \expeqref{Eq.}{eq:expec2} we get
	\mmm{
		\mathbb{E}\left[G_{i}|\,r_{1},\dots,r_{i-1}\right] & \leq  \frac{\rw{u}}{\wgtc{u}}\cdot \left (1+{1}/{r(n)}\right)\\
		& =  g\left(u\right)\cdot \left (1+{1}/{r(n)}\right)=g_{i-1}\cdot \left (1+{1}/{r(n)}\right)\mathdot
	}
	The claim follows.
\end{proof}
\subsubsection{Concluding the soundness proof}

Denote by $r$ the root of the protocol tree. Recall that $\rw{u}$
is defined based on the protocol tree $\clPT$ of a prover \clPo~ and verifier \orgV~ for the original interactive proof of $x$. Hence, for the root of the protocol tree $r$ we know that $\rw{r}$ is bounded above by the number of leaves with weight $1$ in $\clPT$, which is the number of sequences of coin tosses that lead
the verifier to accept $x$. Thus, if $x$ is a no-instance, then $\rw{r}\leq{1}/{10}\cdot2^{r(n)}$.
Hence, if the prover claims that some no-instance is a yes-instance,
then at the beginning of the emulation $\wgtc{r}\geq{9}/{10}\cdot2^{r(n)}$
whereas $\rw{r}\leq{1}/{10}\cdot2^{r(n)}$, thus $g_{0}\leq{1}/{9}$.
Denote by $v$ the leaf sampled at the end of the emulation. If the
verifier accepts the complete emulation, then (in particular) the
final checks pass and so $\rw{v}=\wgtc{v}=1$
and so $g_{m'}=g\left(v\right)={\rw{v}}/{\wgtc{v}}=1$. 

Therefore, in order to upper bound the probability that the verifier accepts,
it suffices to upper bound the probability that the gap after the
last iteration, $G_{m'}$, is greater than or equal to 1. Clearly,
\mmm{
	\textbf{Pr}\left[G_{m'}\geq1\right]  \leq  \mathbb{E}\left[G_{m'}\right]\mathdot
}
From \expref{Claim}{anal:gap_change} we know that for every sequence of coin tosses $r_{1},\dots,r_{i-1}$ that
determine $g_{i-1}$ 
\mmm{
	\mathbb{E}_{r_{i}}\left[G_{i}|\,r_{1},\dots,r_{i-1}\right]\leq g_{i-1}\cdot \left (1+{1}/{r(n)}\right)\mathdot
}
Hence,
\mmm{
	\mathbb{E}_{r_{1},\dots,r_{i}}\left[G_{i}\right] 
	&\leq  \left (1+{1}/{r(n)}\right)\cdot \mathbb{E}_{r_{1},\dots,r_{i-1}}\left[G_{i-1}\right] 
	\eqtag{eq:Expec by round}\mathdot }
Applying the bound from \expeqref{Eq.}{eq:Expec by round} iteratively
it follows that
\mmm{
	\mathbb{E}_{r_{1},\dots,r_{m'}}\left[G_{m'}\right]\leq  \left (1+{1}/{r(n)}\right)^{m'}\cdot g_{0}\mathdot }
From \expref{property}{emu_tree:prop:height}, the height of the emulation tree and hence the number of iterations of the new emulation is at most $m'=2\cdot\lceil{r(n)}/{\log r(n)}\rceil+1$.
For  $n\geq8$ the value of $m'$ is at most $r(n)$ and thus,
\mmm{
	\mathbb{E}_{r_{1},\dots,r_{m'}}\left[G_{m'}\right]&\leq\left(1+{1}/{r(n)}\right)^{r(n)}\cdot g_{0}\\&\leq \eee \cdot {g_{0}}<{1}/{3}\mathdot 
}
where the last equality follows from the fact that $g_{0}\leq{1}/{9}$. Hence, the verifier accepts
with probability of at most ${1}/{3}$. 
\newpage 
%

\begin{appendices}


	
	\section{Private coin emulation}\label{sec:private_tree}
	In the following appendix, we prove a weaker version of the main theorem, which gives an upper-bound on the round complexity in terms of the randomness complexity, for \emph{private coin} interactive proof systems. The point in doing so is that the proof is significantly simpler. Moreover, we can use this weaker version as a component of an alternative proof of the main theorem, which we show in \expref{Appendix}{sec:public_tree}. 
	\begin{theorem}
		\label{theorem:weak}
		Suppose that $S$ has an interactive proof system of randomness
		complexity $r(n)$ for instances of length $n$. Then, $S$
		has a \textsf{private coin} interactive proof system of round complexity $O(r(n)/\log r(n))$  
		~and randomness complexity $r(n)$. Furthermore, the soundness and completeness of the original interactive proof system are preserved.
	\end{theorem}
	
	This appendix can also be read independently from the proof of the main theorem. The general structure of the proof is similar to the one of the main theorem. In \expref{Section}{p_sec:tree} we describe the protocol tree of the original proof system. The protocol tree is used to construct an emulation tree in \expref{Section}{p_sec:emu_tree}. In \expref{Section}{p_sec:emu} we describe the private coin emulation, which uses the emulation tree constructed in the previous section. The analysis of the private coin emulation is performed in \expeqref{Section}{p_sec:anal}. 
	\Cnote{We provide notes that point out the main differences and similarities between the private and public coin emulation protocols. These notes are typeset as this one.} 
	\subsection[The protocol tree]{The protocol tree of the original proof system} \label{p_sec:tree}
	
	
	\Cnote{Note that the protocol tree for the public coin emulation described in \expref{Section}{sec:tree} is similar to the one described here, except for the definition of weights. }
	
	Fixing an interactive proof between prover \newP~ and verifier \newV~ and an instance $x$ of length $n$, we describe the possible prover-verifier
	interactions of the system on common input $x$ using a tree \PTree~
	whose height corresponds to the number of rounds of interaction. For some $\ell=\ell(n)$,
	we assume without loss of generality that in each iteration the verifier
	sends a message $\alpha\in\left\{ 0,1\right\} ^{\ell}$, and the prover's
	responds with a message $\beta\in\left\{ 0,1\right\} ^{\ell}$. We
	can also assume, without loss of generality, that the prover's strategy
	is deterministic and fixed. Each
	node $v$ in level $j$ represents a possible prover-verifier transcript
	for the first $j$ rounds of the interaction. The branching of \PTree~ represents
	the possible ways to extend the transcript to the next round. The
	number of ways to extend the transcript depends only on the verifier's
	message, since we fixed the prover's strategy. Hence, each node has
	\emph{at most} $D\coloneqq2^{\ell}$ children, corresponding to the $2^{\ell}$
	possible verifier messages for the next round. The prover's response
	to each such message is included in the \textbf{description} of the corresponding node. 
	
	The description of a node $u$ on level $j$ contains the partial \textbf{transcript}
	$\gamma\left(u\right)=\alpha_{1}\beta_{1},\dots,\alpha_{j}\beta_{j}$
	of the interaction up to the $j$'th round. The root (at level zero) has an empty transcript, whereas a leaf of \PTree~ represents
	a complete prover-verifier interaction. We can assume, without loss
	of generality, that the verifier sends its private coins on the last
	round, and hence every leaf is associated with a sequence of coin
	tosses which either leads the verifier to accept or to reject. Hence,
	we can represent the possible interactions generated by the interactive
	proof system using a tree \PTree~ of height $m$ that has $2^{r(n)}$ leaves,
	where $m$ is the number of rounds and $r(n)$ is the number of coin tosses.
	
	The description of a node also contains its \textbf{weight}, denoted $\wgt{u}$. The weight of the node is the number of coin sequences that
	are consistent with the node and lead the verifier to accept at the
	end of the interaction. That is,
	
	\begin{definition}
	%
	[Weight of a leaf] \label{p_def:weight_leaf} %
		The weight of a leaf is defined to be $1$. Recall that a leaf $u$  corresponds to a full transcript of the interaction of $P$
		and $V$ on input $x$, when $V$ uses a sequence of coin tosses $\rho$. 
	\end{definition}
	
	\begin{definition}
	%
	[Weight of a node] \label{p_def:weight_node}
		The weight of a node $u$ in the protocol
		tree \PTree~ is the sum of the weights of the leaves that are descendants
		of $u$. 
	\end{definition}
	Note that the weight of node in \PTree, which corresponds to a possibly partial transcript, is proportional to the probability that a sequence of coin tosses is consistent with that transcript.
	\Cnote{In the public coin emulation, the weight of a leaf is defined as $1$ if the verifier accepts at the end of the interaction, otherwise the weight is $0$. Hence, in the public coin emulation the weight of the node is the number of coin sequences that
		are consistent with the corresponding transcript \emph{and} lead the verifier to accept at the
		end of the interaction.}
	\subsection{The emulation tree} \label{p_sec:emu_tree}
	Using the protocol tree \oPT, we create a new tree of height \prolen  ~to guide
	the prover's strategy. We call this tree the \textbf{emulation tree} and we denote it by $\oET$. The nodes in $\oET$~ are nodes from \oPT, however the children of a node $u$ in $\oET$~ may
	be non-immediate descendants of $u$ in \oPT.
	
	\Cnote{The procedure for constructing the private coin emulation tree $\oET$~ is similar to the one described for the the main public coin emulation, provided that the degree of \oPT~ is $poly(n)$. In the foregoing private coin emulation we only care about the height of $\oET$, and we do not mind if the degree of the tree is not polynomially bounded. Hence, unlike in the public coin emulation, we do not group the nodes under interval children in order to reduce the degree. }
	The  {\tt Build\_Tree}  procedure is a recursive procedure that reads and updates a tree $T$, which is initially set to equal the protocol tree \oPT, until obtaining the final emulation tree $\oET$. We start with a protocol tree \oPT~ rooted at $u$ whose weight
	is $\wgt{u}=2^{\rand}$, and on each step we modify this tree towards creating
	$\oET$. We define a \textbf{heavy descendant} of $u$ in $T$ to
	be a node in $T$ whose weight is at least $\frac{\wgt{u}}{r(n)}$, such that this descendant is either a leaf,
	or the weight of each of its children is smaller than $\frac{\wgt{u}}{r(n)}$.
	Note that there are at most $r(n)$ such nodes. 
	
	We modify $T$ so that the children of $u$ in the emulation tree
	are its original children as well as the heavy descendants that
	we lift upwards to make them new children of $u$. This modification
	is performed using the  {\tt Build\_Tree(u)}  procedure, which
	when invoked on a node $u$ identifies the nodes that will be  children of $u$ in the new tree, sets them as children of $u$, and then initiates recursive invocations on the (original and new) children of $u$, creating the new
	emulation tree rooted at $u$. Details follow. 
	
	Let $T_{u}$ denote the intermediate tree after the stage that we identify the heavy descendants of $u$ and raise them to be children of $u$. The {\tt Build\_Tree(u)} procedure begins  by identifying
	a heavy descendant $v$ of $u$ ($v$ can also be a child of $u$ in $T$), which will become a \textbf{heavy child} of $u$
	in $T_{u}$. We move $v$ to be a direct child of $u$, along with the subtree rooted at $v$ (see \expref{Figure}{fig:p_build_heavy}). We update the weights of the ancestors of $v$ that are descendants of $u$ by subtracting $\wgt{v}$ off their weight. We then proceed to the next heavy descendant of $u$. When we finish identifying all the heavy children, the children of $u$ in $T_{u}$ consist of the heavy children of $u$ along with the original children of $u$ in $T$. Next, we erase any nodes whose weights are $0$ from the tree. The weight of a descendant of $u$ may become zero, for example, if all its children were identified as heavy descendants of $u$. 
	
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/build_heavy_nodes.pdf}\protect
			\caption{In the first step, $v$ is identified as a heavy descendant of $u$ and moved to be a heavy child of $u$. In the second step, $z$ is identified and moved to be a heavy child of $u$. The triangles represent subtrees of the original tree.}
			\label{fig:p_build_heavy}
			\par\end{centering}
		
	\end{figure}
	
	Lastly, we invoke the  {\tt Build\_Tree}  procedure on each
	child of $u$ in $T_u$, which creates an emulation tree rooted at that node. 
	
	Observe that in the final emulation tree, for each node $u$, 
	the weight of each grandchild of $u$ is at most $\frac{w(u)}{r(n)}$. If $v$ is a heavy child of $u$ in the emulation tree, then the weight of each descendants of $v$ in $T_{u}$ is at most $\frac{w(u)}{r(n)}$. Since the children of $v$ in the emulation tree are descendants of $v$ in $T_{u}$ the claim holds. Otherwise, $v$ is a non-heavy child of $u$, so its weight is smaller than $\frac{w(u)}{r(n)}$ and hence the weight of the children of $v$ is also smaller than $\frac{w(u)}{r(n)}$.
	
	It follows that the weight of a node in level $2\rand/ \log r(n) $ is at most $\frac{2^{\rand}}{(r(n))^{\rand/ \log r(n) }}=1$. Recall that we perform a clean up stage to delete nodes with weight equal to zero, and hence we guarantee that the weights of all the nodes in the emulation tree are positive integers. It follows that the height of the final emulation tree is \prolen. 
	We note that the number of heavy children of each node is at most $r(n)$, whereas the number of non-heavy children may be exponential in $n$.
	
	\subsection{Emulation protocol} \label{p_sec:emu}
\subsubsection{Protocol preliminaries}	
	
	Next, we describe the strategy of the designated prover \newP~ and verifier \newV~ in the new protocol (``emulation''). Denote the designated prover and verifier of the original proof system by \orgP~ and \orgV~ respectively, and by $\oET$~ the emulation tree constructed in the previous subsection. The verifier \newV~ does not have access to the emulation tree, but it has access to the original verifier \orgV~ strategy. The emulation starts with the verifier sampling private coins $\rho\in\{0,1\}^{\rand}$. Starting from the root of the emulation tree, in each iteration, the prover and the verifier progress one step down the emulation tree, until reaching a leaf that represents a possible complete transcript of the original interaction. 
	
	
	\Cnote{The main difference between the public coin emulation and the private coin one is in the way a child of a node is chosen in each iteration.  In the public coin emulation \newV~ does not have private coins, hence it must choose a continuation based on the transcripts and the probability distributions suggested by \newP. In contrast, in the foregoing  emulation the values of the verifier's private coin tosses determine which child is chosen.  }
	
	In each
	iteration, the prover should provide the transcripts of the \emph{heavy children} $v_{1},\dots,v_{d}$
	of the current node $u$, which was reached in the previous iteration. The verifier performs
	validations on the list supplied by the prover (to be detailed below), and aborts if any of these validations fail. If one of the transcripts provided by the prover is consistent with the verifier's private coins, then the verifier chooses this transcript, and the next iteration proceeds from this heavy child. Otherwise, the verifier sends its next message, according to the strategy of \orgV~ and to the values of its private coins $\rho$. The prover then answers with its response to the verifier's message. In this case, the continuation of the transcript corresponds to one of the non-heavy children of $u$ in the emulation tree. Towards the next iteration, the prover and verifier proceed from the new node. On the last iteration, the verifier checks that the full transcript, along with the sequence of coin tosses, leads the original verifier \orgV~ to accept. 
	
	The validations that the verifier performs are meant to ensure that the transcripts that the prover provides for the new emulation are consistent with a deterministic prover strategy for the original interactive proof system. In such a case, we can claim that, since the original prover cannot fool the verifier with high probability, the new prover cannot do so either. 
	
	\begin{definition} 
		%
		[Prover consistent] \label{p_def:prover_consistent}
		We say that two transcripts $\gamma(u)$ and $\gamma(v)$ are \textbf{prover consistent} if the maximal prefix they agree on is either empty or ends with a prover's message. That is, the prover should respond in the same way on the same prefix of the transcripts.
	\end{definition}
	
	
	The verifier is able to check prover consistency only between previous transcripts seen so far in the emulation. For this reason, the verifier keeps a \textbf{seen-list} $S$ of the nodes that were seen during the emulation, and at each iteration, it checks prover consistency between the new transcripts and the transcripts of the nodes in $S$. 
	
	Note that the nodes in $S$, which the verifier has seen up to some iteration, are a subtree of the emulation tree that consists of a path from the root of the tree to the current input node, augmented with the children of the nodes on the path. See \expref{Figure}{p_fig:seen}.
	\begin{figure}	[h]
		\begin{centering}
			
			\includegraphics[scale=0.5]{drawio/seen.pdf}\protect
			\caption{The nodes in the seen-list, $S$, in the iteration that the input node is $u$. }
			\label{p_fig:seen}
			\par\end{centering}
		
	\end{figure}

	
	We want to claim that all the transcripts in the emulation tree of an untrusted prover are prover consistent, whereas the verifier can only check the prover consistency between the transcripts of the seen nodes, which consist of a very partial portion of the emulation tree. In order to guarantee that consistency between the nodes in $S$ is enough to ensure that all the transcripts in the emulation tree are prover consistent, we add additional validations that check the structure of the emulation tree. The goal of these checks is to make sure that the emulation tree was constructed using a protocol tree where the only changes done to the protocol tree are "raising" parts of the tree (as done with the heavy children in the designated construction).
	
	\subsubsection{Protocol construction}	
	We stress that we give an honest prover centric description of the emulation protocol. This means that \expref{Step}{p_emu:provide} describes the intended behaviour from an honest prover to provide the transcripts of the heavy children. A %
dishonest   %
prover may deviate from this description, and the purpose of the verifier's checks to see that even if there was a deviation the prover can not succeed in claiming that a no-instance is a yes-instance with high probability. 
	
	Initially, for the first iteration, the verifier samples its private coins $\rho\in \{0,1\}^{\rand}$. The input node is the root. The verifier sets the seen-list $S$  to contain the transcript of the root, which is the empty string. The rest of the first iteration, as well as subsequent iterations, proceed as follows. 
	
	\begin{construction} (the $i$th iteration) \label{private:const}
		On input a node $u$ and seen-list $S$. 
	\end{construction}	
	
	\begin{enumerate} 
		\item \label{p_emu:provide}The prover provides the transcripts of the heavy children $v_1,\dots ,v_d$ of $u$: $\gamma(v_1),\dots, \gamma(v_d)$.
		\item \label{p_emu:vald}The verifier performs the following validations and rejects
		if any of them fails:
		\begin{enumerate}
			\item \label{private:val_prefix}For each $j\in [d]$ the verifier checks that $\gamma(u)$ is a proper prefix of $\gamma(v_j)$. 
			\item \label{private:val_pc} For each $j\in [d]$ the verifier checks that the transcript $\gamma(v_j)$ is prover consistent with the other transcripts in $S$ and with the other transcripts $\gamma(v_k)$. 
			\item \label{private:val_trunc}For each $j\in [d]$ the verifier checks that $\gamma(v_j)$ is not part of the emulation tree that was truncated from $\gamma(u)$; that is, if $\gamma(u)$ is a proper prefix of a transcript $\widetilde{\gamma}\in S$, then  $\widetilde{\gamma}$ should not be a prefix of $\gamma(v_j)$. (Note that this also implies that $\gamma(v_j)$ is different from the other transcripts in $S$.) 
			\item \label{private:val_diff} The verifier checks that all the nodes are different (according to their transcripts), that is, for each distinct $i,j\in [d]$ the verifier checks that $\gamma(v_i)\neq \gamma(v_j)$.
			
		\end{enumerate}
		\item \label{p_emu:choose} The verifier checks if any of the transcripts the prover provided are consistent with the values of its private coins $\rho$, where a transcript $\gamma_j=\alpha_1\beta_1,\dots, \alpha_k\beta_k$ is consistent with a sequence of private coins $\rho$, if for every $i\in [k]$ it holds that $V_0(x,\rho,\beta_1,\dots,\beta_{i-1})=\alpha_i$. There are two options according to whether or not there exists a suggested transcript that is consistent with $\rho$. 
		\begin{enumerate}
			\item \label{p_emu:choose_h}If there exists a transcript that is consistent with $\rho$, the verifier sends the prover the maximal transcript $\gamma(v_j)$  that is consistent with its coins. The prover and the verifier update the input node $u$ for the next iteration to be $v_j$. The verifier updates the set $S$ of seen transcripts $S\leftarrow S\cup\left \{\gamma(v_1) ,\dots ,\gamma(v_d) \right \}$.
			\item \label{p_emu:choose_l}Otherwise, the verifier sends its next message $\alpha$ according to the value of its private coins $\rho$. That is, if the current transcript is $\gamma(u)=\alpha_1\beta_1,\dots ,\alpha_k\beta_k$, then the verifier sends $\alpha$ such that $V_0(x,\rho,\beta_1,\dots,\beta_{k})=\alpha$. The prover answers with a message $\beta$ such that $\gamma(u)\alpha\beta$ is a transcript of a child of $u$ in the emulation tree. (The assumption that there exists such a child in the emulation tree is justified in the completeness part of the analysis.)  The verifier updates the set $S$ of seen transcripts; that is, $S\leftarrow S\cup\left \{\gamma(v_1) ,\dots ,\gamma(v_d),\gamma(u)\alpha\beta \right \}$. Towards the next iteration the prover and the verifier update the input node for the next iteration to be the node in the emulation tree whose transcript is $\gamma(u)\alpha \beta$.  
		\end{enumerate}
	\end{enumerate}
	Unless $\gamma(u)$ is the complete transcript (which contains the last message), the next iteration will start with transcript $\gamma(u)$ and the set $S$. Otherwise, we proceed to the final checks. 
	
	
	
	\paragraph{Final check.} After the complete transcript $\gamma=\alpha_1\beta_1,\dots ,\alpha_m\beta_m$ has been determined, the verifier \newV~ accepts if and only if $\rho$ is accepting for $\gamma$; that is, if $V_0(x,\rho,\beta_1,\dots,\beta_m)=1$.
	
	\subsubsection{Number of rounds}In the proposed emulation each iteration consists of a prover message in \expref{Step}{p_emu:provide},  followed by a verifier message in \expref{Step}{p_emu:choose}, and then possibly another prover message in \expref{Step}{p_emu:choose_l}. Hence, each iteration takes two rounds of communication. However, we can augment the last prover message in \expref{Step}{p_emu:choose_l} with the prover message in \expref{Step}{p_emu:provide} of the next iteration. Thus, the number of rounds of communication is the number of iterations of the emulation protocol plus one. The number of iterations is equal to the height of the emulation tree, which is equal to \prolen. 
	
	\subsection{Proof of correctness}\label{p_sec:anal}
	\subsubsection{Completeness} \label{p_subsec:comp}
	
	We claim that if $x$ is a yes-instance, then the new verifier \newV~ accepts with probability at least $c(n)$, the completeness parameter of the original interactive proof system. The proof of completeness is partitioned into three parts. First, we shall show that the strategy of honest prover \newP, as specified in \expref{Subsection}{p_sec:emu}, is indeed well defined; specifically, we shall show that if the verifier does not choose one of the continuations suggested by the prover, but rather sends its next message according to the value of its coin tosses, then there is an unique node in the emulation tree that corresponds to the new transcript.  Next, we show that the strategy of \newP~ is such that \newV~ does not abort until the final check. Finally, we show that this implies that the probability that \newV~ accepts at the end of the interaction with \newP~ is equal to the probability that \orgV~ accepts at the end of the interaction with \orgP, which is at least $c(n)$. 
	
	\paragraph{The prover's strategy is well defined.}
	We begin by showing that the strategy of \newP~ in \expref{Step} {p_emu:choose_l} is well defined. That is, we have to show that if the verifier does not choose one of the suggested continuations of $u$  provided by the prover, but rather sends its next message $\alpha$ in \expref{Step} {p_emu:choose_l} according to the value of its coin tosses $\rho$, then $u$ has an unique child in the emulation tree $\oET$~ whose  transcript is $\gamma(u)\alpha\beta$ for some $\beta\in \{0,1\}^\ell$. 
	
	Let $\beta$ be the message \orgP~ sends in response to the transcript $\gamma(u)\alpha$.  All the nodes in $\oET$~ appear in \oPT, and thus all the transcripts must be consistent with the strategy of \orgP. Thus, every transcript in $\oET$~ whose prefix is $\gamma(u)\alpha$ must proceed with $\beta$. Note that  $u$ cannot have two children whose transcripts are $\gamma(u)\alpha\beta$ since all the transcripts in \oPT~ are distinct, and the same must hold in $\oET$. The reason that $u$ has a child whose transcript is $\gamma(u)\alpha\beta$ is as follows. We know that continuations of $\gamma(u)$ that are consistent with the values of \newV's private coin tosses were not suggested by the prover \newP~ in this iteration or a previous one, otherwise \newV~ would have chosen this continuation and not have reached $u$. Hence, $\gamma(u)\alpha\beta$ was not raised to be a heavy child of an ancestor of $u$, and hence it is a child of $u$ in $\oET$. Similarly, the leaf whose transcript is the complete interaction with private coins $\rho$ was not not raised to be a heavy child of $u$ or of its ancestors, and hence it is a descendant of $\gamma(u)\alpha\beta$ in $\oET$. Thus, the weight of the node whose transcript is  $\gamma(u)\alpha\beta$ is non-zero, so it was not erased from the tree, and it is a child of $u$. 

	\paragraph{The validations in  \expref{Step}{p_emu:vald} are satisfied.}
	We shall show that the validations in \expref{Step}{p_emu:vald} are satisfied in every iteration. This is equivalent to showing that validations are satisfied for every non-leaf node $u$ in the final emulation tree $\oET$, in the iteration that $u$ was the input node (\ie, the node handled on that iteration).     
	
	\Cnote{Showing that the validations in \expref{Step}{p_emu:vald} are satisfied is a simplified version of the completeness proof of the public coin protocol, which is given in \expref{Subsection}{subsec:anal_comp}. }
	
	The general framework of the proof consists of going over every validation performed, and showing that the property being checked holds for every node in the original protocol tree \oPT, and continues to hold with every modification of the tree as part of the  {\tt Build\_Tree}  procedure. 
	\\We denote by $\oPTi{v}$ the tree during construction, after $v$ is identified as a heavy child and placed as a child of $z$ in the tree.  We can list the intermediate trees according to the order the nodes are identified starting from the root $r$ and until the protocol tree is transformed to an emulation tree: $L=$\oPT$=\oPTi{r},\oPTi{u_1},\dots,\oPTi{u_m}=\oET$. For every tree in this list, we show that for every node $u$ in the tree the validations when $u$ is the input node of the iteration pass. Therefore, it will follow that the validations also pass for every node in the final emulation tree $\oET$.
	
	Let $T$ be an intermediate tree, and $u$ a node in $T$. When we say that a validation passes relative to $T$ and $u$, we mean that if the tree $T$ had been used as an emulation tree, then in the iteration on which $u$ is the input node, the validation would have passed. The children of $u$ that are considered in the validation are the children of $u$ in $T$, and the seen-list $S$ consists of the ancestors of $u$ and their children in $T$. Recall that the emulation protocol does not use $T$ as an emulation tree, since it is an intermediate tree so its height has not been reduced enough to satisfy the bound required by the theorem. However, if $T$ had been used the validations would have passed.   
	
	
	Let $\oPTi{z}$~ be an intermediate tree from the list above, created when identifying the node $z$ as a heavy child of some other node. We assume that the validation we are currently checking holds for every node in $\oPTi{z}$, and show that it also holds in the next step of the construction, that is the next tree in the list $L$. Recall that the next step is identifying a heavy child for $z$ (or if $z$ doesn't have heavy children then identifying the next heavy child for the next node in the traversal of the intermediate tree $\oPTi{z}$). Denote the next heavy child being identified by $v$, and the intermediate tree after this modification by $\oPTi{v}$.
	
	Note that it is not sufficient to show that after the creation or identification of $v$  the property being checked is maintained for $v$. This is because the procedure might affect the descendants and ancestors of $v$ in $\oPTi{v}$, as well as nodes whose seen-list changes. Exactly which nodes are affected depends on the validation. 
	
\begin{remark}	
		\label{p_note:children}Let $v$ be a node in $\oPTi{z}$ that the  {\tt Build\_Tree}  procedure has not been invoked on yet. Recall that the children of $v$ in $\oPTi{z}$ are children of the node $v$ in \oPT. Hence, like in the tree \oPT, the transcripts of the children of $v$ in $\oPTi{z}$ extend the transcript of $v$ by one pair of messages. Furthermore, if we did not invoke  {\tt Build\_Tree}  on $v$ yet, then we also did not invoke it on the descendants of $v$ in $\oPTi{z}$. Thus, the subtree of $\oPTi{z}$ rooted at $v$, denoted by $\oPTi{z}(v)$, is a subtree of \oPT.    
	\end{remark} 
	Now, we go over the validations, which are  stated for a node $u$ and its children $v_1,\dots ,v_d$ provided by the prover as part of the emulation. The validations are numbered as in \expref{Construction}{private:const}. Assuming that the validations hold for every node in $\oPTi{z}$, we shall prove that these validations hold for every node in $\oPTi{v}$ (the next intermediate tree in the list).  
	
	
	\begin{enumerate}[label=(\alph*)]
		\item \label{vala} In this validation, for each $j\in [d]$ the verifier checks that $\gamma(u)$ is a proper prefix of $\gamma(v_j)$. In the original protocol tree \oPT~ the transcript of each node extends the transcript of its parent by a pair of messages and thus the property holds. Assume that every node in $\oPTi{z}$ maintains the property that its parent's transcript is a proper prefix of its transcript. Let $v$ be a heavy descendant identified for $z$ and moved to be a child of $z$ along with the subtree under it. The only node in $\oPTi{v}$ that has a child it did not have in $\oPTi{z}$ is $z$, which now has $v$ as a child. Since $v$ is a descendant of $z$ in $T$, and the transcript of every node in $\oPTi{z}$ is a proper prefix of the transcripts of its children, then the transcript of $z$ is a proper prefix of the transcript of $v$.  Hence, in the new tree $\oPTi{v}$, the transcript of each node is a proper prefix of the transcript of its children as well.
		\item In this validation, the verifier checks, for each child $v_j$ of $u$, that $\gamma(v_j)$ is prover consistent with respect to the other transcripts of nodes in $S$ and with respect to the transcripts of the other children of $u$.
		\\In the original protocol tree, \oPT, every two nodes are prover consistent since \orgP~ is deterministic. (If there were two partial transcripts in \oPT~ whose maximal common prefix ends with a verifier message it would mean that that the prover can respond in different ways to the same partial transcript). The transcripts of the nodes in $\oET$~ all appear in \oPT, so every two transcripts in $\oET$~ are prover consistent as well.  
		\item In this validation the verifier checks, for each child $v_j$ of $u$, that $v_j$ is not part of the emulation tree that was truncated from $\gamma(u)$; that is, if $\gamma(u)$ is a prefix of a transcript $\widetilde{\gamma}\in S$, then  $\widetilde{\gamma}$ should not be a prefix of $\gamma(v_j)$. (Note that this also implies together with validation \ref{vala} that for each transcript $\widetilde{\gamma}\in S$ that  $\widetilde{\gamma}\neq \gamma(v_j)$.)
		
		The main idea is that the changes we make to the emulation tree in every step of the construction are identifying a heavy descendant and moving it to be a direct child along with the subtree under it. Hence, if some node $v$ whose transcript is $\widetilde{\gamma}=\gamma(v)$ and is a descendant of $u$, is identified as a heavy child of an ancestor of $u$, denoted by $z$, then $v$ is moved, along with the subtree rooted at $v$, to be a descendant of  $z$. Hence, all the nodes that $\gamma(v)$ is a prefix of \emph{and} are descendants of $v$ cannot be descendants of $u$, and in particular they cannot be children of $u$ after the move. However, it is not clear that after moving $v$ to be a heavy child of $z$ the only potential nodes that we need to check that the claim holds for are the ancestors of $v$ (note that above we assumed that $u$ is an ancestor of $v$). Moreover, it is not true that all the nodes that $\gamma(v)$ is a prefix of are descendants of $v$ in the emulation tree, since some of these nodes might have been lifted to be heavy children of ancestors of $v$ in a previous iteration.  Hence, a detailed proof follows.
		\begin{definition}
			%
			[Seen-list of a node] \label{private_seen} %
				When we consider an intermediate tree $\oPTi{z}$, which may not be the final emulation tree, and some node  $v\in T$, then we denote by $S(v)$ the seen-list $S$ in the beginning of the iteration where $v$ is the input node handled. That is, $S(v)$ is the list containing the nodes that are ancestors of $v$ in $\oPTi{z}$, augmented with their children.
			\end{definition}
		
		Let $u\in\oET$~ and $\widetilde{\gamma}\in S(u)$ such that $\gamma(u)$ is a prefix of $\widetilde{\gamma}$. We prove that for each \emph{descendant} $b$ of $u$ in $\oET$~ the transcript $\widetilde{\gamma}$ is not a prefix of $\gamma(b)$.
		
		Note this is a stronger claim than what we need to show, because we only need to show it for the children of $u$ in $\oET$~ and not for each descendant of $u$. 
		
		First, we shall show that the claim holds in the initial protocol tree \oPT. The transcript of each node is \oPT~ is a prefix only of its descendants in the tree. However, $u$ is not an ancestor of any node in $S(u)$, so $\gamma(u)$ cannot be a prefix of any  $\widetilde{\gamma}\in S(u)$.
		Next, we shall assume that the claim holds in the intermediate tree $\oPTi{z}$ before identifying and moving the child $v$ of $z$, and we show that it holds in the tree $\oPTi{v}$ after the identification of $v$ as a heavy child of $z$. 
		
		When  $v$ is identified as a heavy descendant of $z$, node $v$ is moved to be a child of $z$ along with the subtree under it. In order to show that the claim holds in $\oPTi{v}$, it is enough to consider the nodes $u\in \oPTi{v}$ that have new descendants or new nodes in $S(u)$ relative to the ones they had in $\oPTi{z}$. The descendants of every node in $\oPTi{v}$ are all descendants of it in $\oPTi{z}$. 
		
		The only nodes in $\oPTi{v}$ that have new nodes in their seen-list are the descendants of $z$, since now $\gamma(v)$ is in their seen-list (recall definition in \expref{Remark}{p_note:children} ), whereas $\gamma(v)$ may not have been in their seen-list before the move. By \expref{Remark}{p_note:children}, before the invocation of  {\tt Build\_Tree(z)}  the subtree rooted at $z$ is a subtree of \oPT. Let $u$ be a descendant of $z$ in $\oPTi{v}$. Since determining the heavy descendants of $z$ is done bottom up (this is implied by the definition of heavy descendants in \expref{Subsection}{p_sec:emu_tree}), if $\gamma(u)$ is a prefix of $\gamma(v)$ then $u$ is an ancestor of $v$ in $\oPTi{z}$. It is left to check that $\gamma(v)$ is not a prefix of the transcripts of the descendants of $u$ in $\oPTi{v}$. By \expref{Remark}{p_note:children}, it follows that the subtree of $\oPTi{v}$ rooted at $u$, denoted by $\oPTi{v}(u)$, is a subtree of \oPT. Thus, because $v\notin \oPTi{v}(u)$ (recall that $v$ was lifted to be a heavy child of $z$, and $u$ is a descendant of $z$) it follows that $\gamma(v)$ is not a prefix of the transcripts of the nodes in $\oPTi{v}(u)$, which are the descendants of $u$ in $\oPTi{v}$. (See \expref{Figure} {fig:p_comp_trunc_heavy}.)
		\begin{figure}	[h]
			\begin{centering}
				
				\includegraphics[scale=0.5]{drawio/p_comp_trunc_heavy.pdf}\protect
				\caption{$v$ is identified as a heavy child of $z$, and $u$ is a descendant of $z$, which was an ancestor of $v$ in $\oPTi{z}$.}
				\label{fig:p_comp_trunc_heavy}
				\par\end{centering}
			
		\end{figure}
		
		\item In this check the verifier checks that all the children of $u$ have different transcripts; that is, for every two distinct children $v_i$ and $v_j$ of $u$, the verifier checks that $\gamma(v_i)\neq \gamma(v_j)$.
		\\In the original protocol tree \oPT~ every two nodes have different transcripts. The nodes in $\oET$~ all appear in \oPT, so every two nodes in $\oET$~ also have different transcripts, and in particular every two children of $u$ have different transcripts.  
	\end{enumerate}
	
	\paragraph{Concluding the proof of completeness.}In order to conclude the proof of completeness we use the following claim, which shows that the probability that \newV~ accepts at the end of the interaction with \newP~ is equal to the probability that \orgV~ accepts at the end of the interaction with \orgP. The claim is stated in a more general way than needed for the proof of completeness, so that we shall also be able to use it in the soundness part of the analysis.   
	
%
\begin{claim}[Relating leaves in the two trees]\label{p_claim:mapping_comp}  %
		%
		Let \clP~ be a prover for the emulation of input $x$ with emulation tree $\cET$, using a strategy
		such that the verifier \newV~ does not abort until the final checks. Let \clPo~ be a prover strategy for the original interactive proof system that is consistent with all the transcripts in $\cET$; that is, for every $u\in \cET$~ with transcript $\gamma(u)=\alpha_1\beta_1,\dots ,\alpha_j\beta_j$, the strategy of \clPo~  satisfies  \clPo$(x,\alpha_1,\dots ,\alpha_i)=\beta_i$ for every $i\leq j$. Then, the transcript $\gamma$ created by the end of the emulation of \clP~ and \newV~ when using coins $\rho$ is equal to the transcript interacted between \clPo~ and \orgV~ when using coins $\rho$. Thus, the probability that \newV~ accepts at the end of the interaction with \clP~ is equal to the probability that \orgV~ accepts at the end of the interaction with \clPo.  
	\end{claim}
	
	The proof of completeness follows by using in \expref{Claim} {p_claim:mapping_comp}, \newP~ as \clP~  and \orgP~ as \clPo. Indeed, we can do so because as showed previously it holds that \newV~ does not abort until the final checks when interacting with \newP. In addition, since the emulation tree was constructed using the protocol tree \oPT, for every node $u$ in the emulation tree with transcript $\gamma(u)=\alpha_1\beta_1,\dots,\alpha_j\beta_j$ it holds that \orgP$(x,\alpha_1,\dots ,\alpha_i)=\beta_i$ for every $i\leq j$. Applying \expref{Claim}{p_claim:mapping_comp}, the probability that \newV~ accepts at the end of the interaction with \newP~ is equal to the probability that \orgV~ accepts at the end of the interaction with \orgP. Thus, the completeness of the original interactive proof system is maintained. 
	\begin{proof}
		Let $\rho$ be the value of the coins of \newV. By the assumption, all the transcripts in the emulation tree $\cET$~ are consistent with the strategy of \clPo. Recall that, in each iteration of the emulation of \newV~ and \clP,  a new node in $\cET$~ is chosen, and the continuation of the transcript is according to the transcript of the new node. Hence, in each iteration the continuation of the transcript  must be consistent with the transcript of \clPo. The proof follows by noting that the continuations of the transcript are also consistent with the strategy of \orgV~ with coins $\rho$. That is, if the verifier \newV~ chooses a continuation of the transcript suggested by \newP, then this transcript must be consistent with the strategy of \orgV~ with coins $\rho$. Otherwise, the verifier sends its next message based on the strategy of \orgV~ with coin tosses $\rho$. It follows that in every iteration the current transcript is consistent with the strategy of \clPo~ and \orgV~ with coins $\rho$. 
		
		From the assumption that \newV~ does not abort until the final checks, we know that after the last iteration the complete transcript  had been interacted. Hence, this complete transcript is equal to the transcript of the interaction between \clPo~ and \orgV~ with coins $\rho$.
		
		
		The final check of the emulation of \clP~ and \newV~ with random coin $\rho$ pass if and only if \orgV~ with coins $\rho$ accepts the complete transcript that has been interacted.  Recall that the private coins in the original and new emulation are sampled using the same probability distribution. Thus, the probability that \newV~ accepts at the end of the interaction with \clP~ is equal to the probability that \orgV~ accepts at the end of the interaction with \clPo. 
		\end{proof}
	\subsubsection{Soundness} \label{p_subsec:soundness}
	
	Let $x$ be a no-instance. We shall show that \newV~ rejects $x$ with probability at least $s(n)$, the original soundness parameter. 
	\Cnote{The main part of the soundness proof here is \expref{Lemma} {private:consis}, which is a slightly simplified version of \expref{Lemma} {anal:consis} in \expref{Section}{subsub:anal_derive}. The other two components of the soundness analysis of the public coin system (which are defining the notion of actual weight of a node, and bounding the gap between the claimed and actual weight) are not required for the private coin soundness analysis. }	
	The crux of the proof is extracting a deterministic strategy  for the original prover \clPo~  using the strategy of \clP. We can assume, without loss of generality, that \clP~  is deterministic since for every probabilistic prover there is a deterministic prover for which the verifier's acceptance probability is at least as high. Hence, if we show soundness holds with deterministic provers it implies soundness is maintained also with non-deterministic provers.  Because the prover is deterministic we know that there is an emulation tree underlying the strategy of prover \clP.  In an emulation tree every node contains a transcript that extends the transcript of its parent. Hence, the protocol tree of \clPo~ and \newV~ can be used to define an emulation tree, which we denote by  $\cET$. We define a strategy for \clPo~ by using the transcripts in $\cET$. That is, for each $u\in \cET$~ with transcript $\gamma\left(u\right)=\alpha_{1}\beta_{1}\dots,\alpha_{j}\beta_{j}$,
	we define \clPo$\left(x,\alpha_{1},\dots,\alpha_{i}\right)\coloneqq\beta_{i}$
	for all $i\leq j$. We extend \clPo's strategy to transcripts that do not appear in $\cET$~ in an arbitrary way. The main part of the analysis consists of showing that the transcripts of every two nodes in $\cET$~ are prover consistent, \ie, that their maximal common prefix ends with a prover message, and thus the strategy of \clPo~ is well defined.  
	
	We can assume, without loss of generality, that the strategy of  \clP~ is such that the verifier does not abort until the final checks. This is because every prover strategy in which the verifier aborts in one of the intermediate checks can be modified to a prover strategy in which the verifier does not abort until the final check and the verifier's acceptance probability is at least as large. (The prover can compute the transcripts of the children such that they are different continuations of their parent and prover consistent with the list $S$ instead of every node where the verifier would have aborted in the intermediate checks.)  In \expref{Lemma} {private:consis} we show that this implies that all the transcripts in $\cET$~ are prover consistent, and thus the strategy of \clPo~ is well defined. The proof of soundness then follows by applying \expref{Claim} {p_claim:mapping_comp} (provided in \expref{Subsection} {p_subsec:comp}), that implies that the probability that \newV~ accepts when interacting with \clP~ is equal to the probability that \orgV~ accepts when interacting with \clPo, which is at most the soundness parameter $s(n)$. 
	
	It is left to  show that the strategy of \clPo~ is well defined, \ie, that no two nodes  $u,v\in \cET$~ share the prefix of prover-verifier interaction but differ on the prover's response. That is, we show that every two nodes $u,v\in \cET$~ are \textbf
	{prover consistent} (see \expref{Definition}{p_def:prover_consistent}). 
	
	For a node $u\in \cET$~ provided during the emulation, denote by $S\left(u\right)$ the seen-list from $\cET$~ at the beginning of the iteration in which $u$ was the input node (\ie, was the node handled on that iteration). That is, the nodes in $S(u)$ are the ancestors of $u$ in $\cET$~  and their children. \expref{Validation} {private:val_pc} implies that each node $u$ in the emulation tree is prover consistent with the transcripts of the nodes in $S(u)$. We show that using \expref{validations} {private:val_prefix},\ref{private:val_trunc} and \ref{private:val_diff} it follows that \emph{every} two transcripts in the emulation tree are prover consistent. 
	
	\begin{lemma} 
		%
		[Prover consistency of the emulation tree] \label{private:consis} %
		%
		If \clP~ is a prover for the new emulation protocol using a strategy
		 such that the verifier \newV~ does not abort until the final checks (for every verifier randomness), then every two transcripts of nodes in the emulation tree $\cET$~ are prover consistent.
	\end{lemma}
	
	\Cnote{Note that the following proof is a slightly simplified version of the proof of \expref{Lemma}{anal:consis} in \expref{Section}{sec:anal}.}
	\begin{proof}
		
		Let $u$ and $v$ be two nodes in the emulation tree $\cET$, we wish to show that their transcripts $\gamma(u)$ and $\gamma(v)$ are prover-consistent. If one of the nodes is in the seen-list $S$ of the other node (that is, if $u\in S(v)$ or $v\in S(u)$) then the transcripts of $u$ and $v$ must be prover consistent by \expref{validation}{private:val_pc}. Otherwise,  the intersection between the seen-list of nodes of $u$ and $v$ is non-empty, and particular it contains the least common ancestor of $u$ and $v$, denoted by $z$, as well as the children of $z$ that are ancestors of $u$ and $v$, denoted by $a$ and $b$ respectively, see \expref{Figure}{fig:PC_private} for illustration. (Note that $z$ is not equal to $u$  or to $v$, otherwise $u\in S(v)$ or $v\in S(u)$. Similarly $a\neq u$ and $b\neq v$.) Hence, by using the prover consistency between the transcripts of $a,b,z$ and the transcript of $u$, as well as between the transcript of $v$, and by using structural validations between the nodes in the emulation tree (\expref{validations} {private:val_prefix}, \ref{private:val_trunc} and \ref{private:val_diff}) we are able to show that the transcripts of $u$ and $v$ are also prover consistent. Details follow.      
		\begin{figure}	[h]
			\begin{centering}
				
				\includegraphics[scale=0.5]{drawio/PC.pdf}\protect
				\caption{The subtree of $\cET$~ that contains $u$ and $v$}
				\label{fig:PC_private}
				\par\end{centering}
			
		\end{figure}
		
	
		Since $a$ is an ancestor of $u$ and $b$ is an ancestor of $v$, then  $\gamma(a)$ is a proper prefix of $\gamma(u)$, and $\gamma(b)$ is a proper prefix of $\gamma(v)$. We consider two cases according to the relation between $\gamma(a)$ and $\gamma(b)$. 
		
		First, consider the case that  $\gamma(a)$ is not a prefix of $\gamma(b) $ and $\gamma(b)$  is not a prefix of $\gamma(a)$. By \expref{validation} {private:val_prefix} we know that each node in this path from $u$ to $a$ is a prefix of its children. Thus, $\gamma(a)$ is a prefix of $\gamma(u)$. Similarly, $\gamma(b)$ is a prefix of $\gamma(v)$. Recall that we are in the case that  $\gamma(a)$ is not a prefix of $\gamma(b) $ and $\gamma(b)$  is not a prefix of $\gamma(a)$, and so the maximal prefix on which $\gamma(a)$ and $\gamma(b)$ agree upon is a proper prefix of both. This common prefix equals the maximal prefix on which  $\gamma(u)$ and $\gamma(v)$ agree. We know that $\gamma(a)$ and $\gamma(b)$ are prover-consistent because the prover provides $a$ along with $b$ as children of $z$ and we assume that \expref{validation}{private:val_pc} is satisfied. Since the maximal prefix that $\gamma(u)$ and $\gamma(v)$ agree on is equal to the maximal prefix that $\gamma(a)$ and $\gamma(b)$  agree on, it follows that $\gamma(v)$ and $\gamma(u)$ are also prover-consistent. See \expref{Figure} {fig:private_PC2} for illustration.
		\begin{figure}	[h]
			\begin{centering}
				
				\includegraphics[scale=0.5]{drawio/PC2.pdf}\protect
				\caption{ $\gamma(a)$ and $\gamma(b)$ agree on the prefix in white, while $\gamma(a)$ is a prefix of $\gamma(u)$ and $\gamma(b)$ is a prefix of $\gamma(v)$.   }
				\label{fig:private_PC2}
				\par\end{centering}
			
		\end{figure}
		
		Note that $\gamma(a)$ cannot be equal to $\gamma(b)$ since that would be a violation of \expref{validation}{private:val_diff}. We are left with the case that one of the transcripts $\gamma(a)$ and $\gamma(b)$  is a proper prefix of the other, and assume, without loss of generality, that $\gamma(a)$ is a proper prefix of $\gamma(b)$. Denote the transcript of $b$ by $\gamma(b)=\alpha_1\beta_1,\dots,\alpha_k\beta_k$. 
		
		We claim that $\gamma(b)$ is not a prefix of $\gamma(u)$. Assume by contradiction that $\gamma(b)$ is a prefix of $\gamma(u)$. Note that $b\in S(u)$, so by \expref{validation}{private:val_trunc} (which passed for the parent of $u$)  $\gamma(b)\neq \gamma(u)$, so $\gamma(b)$ must be a proper prefix of $\gamma(u)$. Denote the nodes in the path from $a$ to $u$ in $\cET$~ by $a=a_0,a_1,\dots ,a_n=u$ and by $a_{j}$ the first node in the path such that $\gamma(a_{j})$ is a prefix of $\gamma(b)$ and $\gamma(a_{j+1})$ is not a prefix of $\gamma(b)$. There must exist such node $a_j$ since $\gamma(a)$ is a prefix of $\gamma(b)$, and $\gamma(u)$ is not a prefix of $\gamma(b)$. Note that since $a_{j+1}$ is an ancestor of $u$ in $\cET$, then by \expref{validation}{private:val_prefix} it follows that $\gamma(a_{j+1})$ is a proper prefix of $\gamma(u)$. Hence, $\gamma(b)$ and $\gamma(a_{j+1})$ are both prefixes of $\gamma(u)$. Thus, one of them must be a prefix of the other, and so in this case $\gamma(b)$ is a prefix of $\gamma(a_{j+1})$. It follows that we have a violation to \expref{validation}{private:val_trunc}, since $b\in S(a_j)$ where $\gamma(a_{j})$ is a prefix of $\gamma(b)$ and $\gamma(b)$ is a prefix of $\gamma(a_{j+1})$ (see \expref{Figure}{fig:private_PC3}). Hence, we reached a contradiction to the hypothesis that \newV~ does not abort in the intermediate validations, and so $\gamma(b)$ cannot be a prefix of $\gamma(u)$.
		
		Because $\gamma(b)$ is not a prefix of $\gamma(u)$, the maximal common prefix of $\gamma(u)$ and $\gamma(b)$ is a proper prefix of $\gamma(b)$. We know that $b\in S(u)$  because $b$ is a child of $z$, which is an ancestor of $u$. Hence, by \expref{validation}{private:val_pc}, the transcript of $u$ and the transcript of $b\in S(u)$ are prover consistent. It follows that the maximal common prefix of $\gamma(u)$ and $\gamma(b)$, which is a proper prefix of $\gamma(b)$, ends with a prover message. 
		
		\begin{figure}	[h]
			\begin{centering}
				
				\includegraphics[scale=0.5]{drawio/PC3.pdf}\protect
				\caption{The dashed arrow pointing from $b$ to $a_{j+1}$ represent the fact that $\gamma(b)$ is a prefix of  $\gamma(a_{j+1})$, and similarly that $\gamma(a_j)$ is a prefix of $\gamma(b)$.   }
				\label{fig:private_PC3}
				\par\end{centering}
			
		\end{figure}
				\begin{figure}	[h]
			\begin{centering}
				
				\includegraphics[scale=0.5]{drawio/PC4.pdf}\protect
				\caption{The maximal common prefix between $\gamma(u)$ and $\gamma(b)$ appears in white. Since $\gamma(b)$ is a prefix of $\gamma(v)$ the maximal common prefix of $\gamma(u)$ and $\gamma(v)$ is the same as the former.  }
				\label{fig:private_PC4}
				\par\end{centering}		
		\end{figure}
		Lastly, note that from \expref{validation}{private:val_prefix} the transcript of each node in the path from $b$ to $v$ is a prefix of the transcript of its parent. Thus, $\gamma(b)$ is a prefix of $\gamma(v)$. It follows that the maximal common prefix of $\gamma(v)$ and $\gamma(u)$ is contained in the maximal common prefix of $\gamma(u)$ and $\gamma(b)$, so it ends with a prover message (See \expref{Figure}{fig:private_PC4}). 
	
	\end{proof}
\section{Alternative public coin emulation}\label{sec:public_tree}
In this Appendix we sketch a proof for an additional weaker version of the main theorem, one which transforms a private coin interactive proof system to a public coin interactive proof system. This transformation does not reduce the round complexity, and it does not preserve the randomness complexity, but it also does not blow up the randomness complexity by much.  Recall that this is indeed weaker than the main theorem, because this transformation does not yield a public coin interactive proof where the round complexity is bounded by the randomness complexity. Moreover, the randomness complexity is not preserved.

The contribution of this theorem is also due to the fact that we can derive the main  \expref{Theorem}{thm:main} from  \expref{Theorem}{thm:randeff} and \expref{Theorem}{theorem:weak}. In this way, we obtain a modular proof of the main theorem in which the creation of the protocol tree and its emulation are separated into two stages. We would like to thank an anonymous reviewer for suggesting the idea of proving theorem \expref{Theorem}{thm:randeff}. 

\begin{theorem}	
%
[Randomness Efficient Public Coin Emulation] \label{thm:randeff} %
	Suppose that $S$ has an interactive proof system of randomness
	complexity $r(n)$ and round complexity $m(n)$ for instances of length $n$. Then, $S$
	has a \textsf{public coin} interactive proof system of round complexity $O(m'(n))$, where $m'(n)=$\text{max}$\{r(n)/\log r(n),m(n)\}$,  
	~and randomness complexity $O(\log r(n)\cdot m')$. Furthermore, the resulting interactive proof system has perfect completeness.
\end{theorem}

 
The section is organized as follows, first we show how to conclude the main theorem from the two weaker theorems. Next, we sketch a proof for \expref{Theorem}{thm:randeff}.  

\subsection{Concluding the main \expref{Theorem}{thm:main} using the alternative emulation} 
For clarity, we begin by restating the main Theorem.

\begin{customthm}{1.1}
%
[Main Theorem]
	Suppose that $S$ has an interactive proof system of randomness
	complexity $r(n)$ for instances of length $n$. Then, $S$
	has a \textsf{public coin} interactive proof system of round complexity $O(r(n)/\log r(n))$  
	~and randomness complexity $O(r(n))$. Furthermore, the resulting interactive proof system has perfect completeness.
\end{customthm}
Next, we give an alternative proof of the main theorem. See the main sections of the paper for the standard proof.
\begin{proof}
		  Fix an interactive proof  for the set $S$, that has randomness
	complexity $r(n)$ for instances of length $n$. From \expref{Theorem}{theorem:weak}, it follows that $S$ has a private coin interactive proof system of round complexity $O(r(n)/\log r(n))$  
	~and randomness complexity $r(n)$. Applying \expref{Theorem}{thm:randeff} on the new interactive proof system for $S$, if follows that $S$ has a public coin interactive proof system of round complexity $O(r(n)/\log r(n))$, and randomness complexity $O\big(\log r(n)\cdot \left(r(n)/\log r(n)\right) \big)=O(r(n))$. Furthermore, the resulting interactive proof system has perfect completeness. 
\end{proof}
\textbf{Reflection.} In this alternative proof, we first use  \expref{Theorem}{theorem:weak} to reduce the number of rounds of the private coin interactive proof system to \prolen. We then apply \expref{Theorem}{thm:randeff} on the new interactive proof system and convert it to a public coin interactive proof system that does not increase the round complexity to above \prolen, and has randomness complexity of  $O(\log r(n))$ times the number of rounds, so randomness complexity is $O(r(n))$. In particular, using other known transformations of private coin to public coin interactive proofs, instead of \expref{Theorem}{thm:randeff},  would not have worked in deriving the main theorem since these transformations blow up the randomness complexity by too much.

The main difference between the standard proof in the main section of this paper and the alternative proof, is that in the standard proof the transformation is done in one shoot. That is, there is one transformation of the protocol tree of the original interactive proof system to an emulation tree that \emph{both} has degree bounded polynomially and height bounded by \prolen. Then this emulation tree is used to perform a public coin emulation and the verifer has to perform on every round both validations concerning the degree reduction and validations concerning the height reduction. In contrast, in the alternative proof the transformation of the protocol tree is separated to two parts: first, reduce the height of the tree (which will reduce the number of rounds to \prolen), and then reduce the degree of the tree (which will enable emulating with public coins). The emulation itself is also separated into two parts. Since we are using the private coin transformation we derived with \expref{Theorem}{theorem:weak}, and then emulating it using the emulation of \expref{Theorem}{thm:randeff}, it follows that all the validations defined in the private coin emulation protocol are postponed to after the last iteration of public coin emulation \expref{Construction}{pub:emu:const} (see the protocol in the following sections).
\subsection{Proof Sketch of \expref{Theorem}{thm:randeff}}\label{pub}
We sketch the proof of \expref{Theorem}{thm:randeff}, beginning by giving an overview  in \expref{Section}{pub:tree}. Next, we describe the construction of the emulation tree and its properties in \expref{Section}{pub:build} and \expref{Section}{pub:sec:emu_tree:prop}, and finally describe the emulation protocol in \expref{Section}{pub:emulation} . We omit the analysis of the emulation protocol. We refer the interested reader to the analysis in \expref{Section}{sec:anal}, which includes the ideas required for the analysis of this theorem. 
\subsubsection{Overview}\label{pub:tree}
Fixing an interactive proof between a prover \newP~ and a verifier \newV, and an instance $x$ of length $n$, we describe the possible prover-verifier
interactions on common input $x$ using the protocol tree \PTree~ defined in \expref{Section} {sec:tree}.
The height of \PTree~ corresponds to the number of rounds $m(n)$ of interaction, and the number of leaves is $2^{r(n)}$, where $r(n)$ is the randomness complexity.
As in the proof of the main theorem, our goal is to transform the protocol tree to an emulation tree, denoted by $\oET$, that defines a prover strategy for a public coin emulation. Recall that the way we use the emulation tree to define a prover strategy for the public coin emulation is by initiating the emulation at the tree root, and on each round having the prover assist the verifier at progressing one step down the emulation tree. (This assistance is required because the verifier does not have access to $\oET$.) Each round consists of the prover providing the verifier with the descriptions of the children of the current node $u$ that was sampled on the previous round, where these descriptions contain the weights of the various children. Hence, in order to apply this emulation strategy, the prover should use an emulation tree with a degree that is bounded by $\poly(n)$, whereas the degree of \PTree~ can be exponential in $n$. Thus, our goal is to transform the protocol tree \PTree~ to an emulation tree $\oET$, with a degree bounded by $\poly(n)$, and  the height of the tree (which corresponds to the number of rounds) should be $O(m')$, for  $m'(n)=$\text{max}$\{r(n)/\log r(n),m(n)\}$. This is done using the {\tt Build\_Tree(r)} procedure.

In order to reduce the degree when it is too large, we group the children of $r$ under new children, which we call \textbf{interval children}.  (Note that here we don't need to first lift the heavy descendants of $r$ as we did in the proofs of the other theorems, because we are not trying to reduce the number of rounds, unlike in the other theorems.) 
In general, children of $r$ in \oPT~ may become non-immediate
descendants during the procedure.


The  {\tt Build\_Tree(r)}  procedure unites the  children of $r$ into groups. We unite the children of $r$ by lexicographic order of their transcript field, such that the weight of each group is larger than ${\wgt{r}}/{r(n)}$ and at most ${2\wgt{r}}/{r(n)}$ (except for, possibly, the last group which is only required to have weight smaller than ${2\wgt{r}}/{r(n)}$). We create
a new \textbf{interval child} $v$ for each such
group, where the children of $v$ are the nodes
in the group. If $r$ has only one child $u$, then instead of creating an interval child for $r$, we leave $u$ as an original child of $r$.   

Denote by $\oPTi{u}$ the intermediate tree after we identify and set $u$ as an interval or original child  of $r$. This way we have a notation for every transformation of the tree in which we create an additional child. 

After creating all the interval children of $r$ (or identifying the original child), the children of $r$ in the final emulation tree $\oET$~ are exactly the children of $r$ in $\oPTi{z}$, where $z$ is the last interval child of $r$ created. The number of children $r$ has is at most $r(n)$, since the weight of each interval child of $r$ (except for possibly the last interval child) is at least ${w(r)}/{r(n)}$. Next, the procedure is called recursively on the children of $r$ in $\oPTi{z}$ in order to create the final emulation tree. 


The description of a node $u$ in the emulation tree is composed of the
\textbf{transcript }field $\gamma\left(u\right)=\alpha_{1}\beta_{1}\dots\alpha_{i}\beta_{i}$
and a \textbf{weight }field $\wgt{u}$ as in the original
protocol tree, with an additional \textbf{range} field $R(u)$.
The range of a node represents the possible range of its children's transcripts.
Hence, the transcripts of the children of each interval child are the same up to the last verifier's message on which they differ, which corresponds to the branching of the intermediate tree for the next round. Thus, we can label the range $R(u)=\left[s,e\right]$
where $s<e\in\left\{ 0,1\right\} ^{\ell}$ according to the range of the last verifier message in the transcript field of the children of $u$.  
Original children
have full range $\left[0^{\ell},1^{\ell}\right]$, whereas the range
of interval children is a subinterval of $\left [0^{\ell},1^{\ell}\right]$ such that this subinterval corresponds to the transcripts of the descendants that are grouped under this node.

We show in the analysis that the height of $\oET$~ is  $O(m'(n))$, where \\$m'(n)=$\text{max}$\{r(n)/\log r(n),m(n)\}$. The degree of nodes in $\oET$~ is at most $r(n)$,  hence it is suitable for public coin emulation. 


(The running time of this algorithm is at least the size of the protocol
tree, which is exponential in $r(n)$, and thus it may be exponential in
$\left|x\right|$. However, the prover is the one that runs this algorithm
and the prover is computationally unbounded. Therefore the running
time is not an issue.) 

\subsubsection{The {\tt Build\_Tree} procedure} \label{pub:build}

Denote the designated prover and verifier of the original interactive proof system by \orgP~ and \orgV~ respectively, and the protocol tree of \orgP~ and \orgV~ for a yes-instance $x$ by \oPT. The {\tt Build\_Tree} procedure is a recursive procedure that reads and updates a tree $T$, which is initially set to equal the protocol tree \oPT ~until obtaining the final emulation tree, denoted by $\oET$. When invoked on a node $u$ in $T$, the procedure determines the children of $u$, updates the global tree and invokes the procedure recursively on the children of $u$. 
\\We denote by $T(u)$ the subtree of $T$ rooted at $u$. 
\paragraph*{Initialization.}
The tree $T$ is initialized to be the original protocol tree, where each node has a description that contains the weight and transcript like in the original tree, and an additional range field which is initially left empty. We set the range of the root, denoted $r$, to be full range $R(r)=[0^{\ell},1^{\ell}]$. If the weight of $r$ is zero we terminate the process. Otherwise, we invoke the  {\tt Build\_Tree}  procedure on $r$.

\paragraph*{The main procedure:  {\tt Build\_Tree} .}
If $u$ is a leaf, the procedure returns without updating the global tree $T$. If $u$ has only one child $v$ with non zero weight, then the procedure deletes the children of $u$ whose weights are equal to zero, identifies $v$ as an \textbf{original child} of $u$, and sets the range of $v$  to be full range $R(r)=[0^{\ell},1^{\ell}]$.  Otherwise, the  {\tt Build\_Tree}  procedure invokes the {\tt Build\_Interval(u)} procedure, in order to create and update the children of $u$ in $T$. Finally, the Build\_Tree procedure is invoked recursively on all the children of $u$ in $T$.

\paragraph*{{\tt Build\_Interval(u)}.}
This procedure groups the children of $u$ under \textbf{interval children}. 
Denote the range field of $u$ by $R(u)=[s(u),e(u)]$.  (Note that $s(u)=0^\ell$ and $e(u)=1^\ell$ unless $u$ is an interval node, in which case its range is partial.) We partition the range of $u$ into a sequence of consecutive intervals, each one representing the range of a new child of $u$. As long as we have not partitioned all of the range $[s(u),e(u)]$ we perform the following procedure.

\begin{enumerate}
	\item Determine $s'$, the starting point of the interval child's range: Initially, for the first interval child of $u$ we set $s'=s(u)$. For the next interval children, if the end of the range of the previously created interval child is $\tilde{e}$, then we set $s'=\tilde{e}+1$. 
	\item 
	Determine $e'$, the ending point of the interval child's range: 
	For each $e\in \{0,1\}^\ell$, denote by $Interval(s',e)$ the set of children of $u$ in $T(u)$ whose last verifier message $\alpha$ (in the transcript field) is in the range $[s',e]$. Note that when $[s',e]\neq[s(u),e(u)]$ the set $Interval(s',e)$ can be a proper subset of the non-heavy children of $u$. We define the weight of the set $Interval(s',e)$, which we denote by $W(s',e)$, as the sum of the weights of nodes in $Interval(s',e)$. 
	\\We set $e'$, to be the minimal $e\in \{0,1\}^\ell$ that satisfies $W(s',e)\geq{\wgt{u}}/{r(n)}$. If no such $e$ exists and $W(s',e(u))>0$, we set $e'=e(u)$. If $W(s',e(u))=0$ there is no need to create another interval child so we return to the  {\tt Build\_Tree}  procedure. (This guarantees that the weight of an interval child is at least $1$). 
	\item Create a new node $v$: We set the transcript of $v$ to be like the transcript of $u$, $\gamma(v)=\gamma(u)$, its range to be $R(v)=[s',e']$ and its weight to be $w(v)=W(s',e')$. 
	\item Place $v$ in the tree: disconnect $u$ from the nodes in $Interval(s',e')$. Set $u$ as a parent of $v$ and let $v$ be the parent of all nodes that are in $Interval(s',e')$.  
\end{enumerate}

\noindent  Note that the weight of an interval child of $u$ is at most ${2\wgt{u}}/{r(n)}$ and at least ${\wgt{u}}/{r(n)}$, except possibly for the last interval child, whose weight is at least $1$.


%
\subsubsection{Properties of the emulation tree } \label{pub:sec:emu_tree:prop}

Recall that in the original protocol tree, $v$ was a child of $u$
if and only if $\gamma(v)=\gamma(u)\alpha\beta$ where $\alpha,\beta \in \{0,1\}^\ell$ denote the next verifier message and the prover's response to it.
However, in the new emulation tree, $\oET$, this is not the case.
Namely, if $v$ is a child of $u$ in $\oET$, then it could be that $v$
is an original child of $u$ and hence $\gamma(v)=\gamma(u)\alpha\beta$ for some $\alpha,\beta\in \{0,1\}^\ell$,
or $v$ is an interval child hence $\gamma(v)=\gamma(u)$
and $R(v)\subseteq R(u)$.  Nevertheless, the following
properties of the final emulation tree $\oET$~ are readily verified. We omit the proofs for most of these properties and we refer the reader to the proofs in \expref{Section}{sec:emu_tree:prop}, which are a slightly more complex version of the corresponding claims here. We only include the proof of \expref{Corollary}{pub:emu_tree:prop:height} since it is different from the one in \expref{Section}{sec:emu_tree:prop}. 
%
\begin{claim} 
	%
	[Node degree] \label{pub:emu_tree:prop:deg} %
	Each node $u$ in the final emulation tree $\oET$~ has at most $r(n)$ children.
\end{claim}
\begin{claim} 
	%
	[Weight reduction] \label{pub:emu_tree:prop:weight}
	For every node $u$ in the final emulation tree $\oET$, and each grandchild $z$ of $u$, either $z$ is a child of an interval child of $u$, and the weight of $z$ is at most ${2\wgt{u}}/{r(n)}$, or $z$ is an original child of $u$.
\end{claim}
\begin{corollary} 
	%
	[Corollary to \expref{Claim}{pub:emu_tree:prop:weight}] \label{pub:emu_tree:prop:height}
	The height of the final emulation tree $\oET$~ is $O(m'(n))$, where $m'(n)=$\text{max}$\{r(n)/\log r(n),m(n)\}$.
\end{corollary}
\begin{proof}
	 Fixing an iteration that begins with input node $u$, the prover helps the verifier go one step down  $\oET$. Hence, two iterations later the chosen node $z$ is a grandchild of $u$, so from \expref{Claim}{pub:emu_tree:prop:weight} either $z$ is a child of an interval child of $u$  and the weight of $z$ is at most ${2\wgt{u}}/{r(n)}$, or $z$ is a child of  an original child of $u$. Note that after visiting $m$ original children while going down the tree  we have reached a leaf of $\oET$. In addition, after visiting $3r(n)/\log r(n) $ interval children the weight of the node we reached is at most ${2^{r(n)}}/{\left({r(n)}/{2}\right)^{3(r(n)/\log r(n))}}<1$, so we have reached a leaf.  It follows that after $2(m+ 3r(n)/\log r(n))$  iterations we have reached a leaf (either by visiting $m$ original children or having the weight reduced with interval children). The multiplication by two comes from the fact that we have a guarantee of visiting an original child or reducing the weight only after two iterations.
\end{proof}
\begin{claim}
	%
	[Leaves]  \label{pub:emu_tree:prop:leaves} %
	 The leaves of  $\oET$~ are exactly the leaves of protocol tree \oPT~ whose weights are $1$.
\end{claim}
\subsubsection{Public Coin Emulation}\label{pub:emulation}
 
Next, we describe the strategy of the designated prover \newP~ and verifier \newV~ in the new protocol (``emulation''). The strategy of the designated prover \newP~ for a yes-instance $x$ uses the emulation tree $\oET$~ of $x$ constructed in the previous section. The prover assists the verifier \newV~ in progressing down the emulation tree. On each
iteration, the prover provides the descriptions of the children $v_{1},\dots,v_{d}$
of the current node $u$, which was sampled in the previous iteration. The verifier performs
validations on the list supplied by the prover (to be detailed below), and then samples one
of the children for the next iteration according to its weight. The verifier does not
have access to the emulation tree, and its validations consist of
structural requirements on the part of the emulation tree seen so far. On the last iteration, the verifier checks that the full transcript, along with the sequence of coin tosses, leads the original verifier \orgV~ to accept. 

\Cnote{The exposition and definitions for this section are identical to the ones in \expref{Section}{sec:emu}, with the minor change of having original children in this emulation, instead of the heavy children in the other Section. Hence, we will not repeat the exposition here, and the reader is referred to read the exposition in \expref{Section}{sec:emu}, which includes  transcript descendant \expref{Definition}{def:tran_desc}, transitivity \expref{Definition}{anal:trans} and prover consistency \expref{Definition}{def:prover_consistent}. Note that what is stated about heavy children in \expref{Section}{sec:emu} holds for original children in this emulation (although the creation of the two types of children is different, the claims we make about them in this section are identical). }

\begin{construction} (the $i$th iteration) \label{pub:emu:const}
	On input a non-leaf node $u$.
\end{construction}	


\begin{enumerate}
	\item The prover provides the descriptions of the children $v_{1},\dots,v_{d}$ 
	of $u$: \mmm{\left(\gamma\left(v_{1}\right),R\left(v_{1}\right),\wgt{v_{1}}\right),\dots,\left(\gamma\left(v_{d}\right),R\left(v_{d}\right),\wgt{v_{d}}\right)} 
	\item If $d=1$, then $u$ has a single child $v_1$, and the verifier performs the following validations and rejects if any of them fails:
	\begin{enumerate}
		\item The verifier checks that the weight of $v_1$ is equal to the weight of $u$.
		\item The verifier checks that $v_1$ is a transcript descendant of $u$.
	\end{enumerate}
	\item Otherwise, if $d>1$ the verifier performs the following validations and rejects
	if any of them fails: 
	
	\begin{enumerate}
		\item The verifier checks that all nodes are different (according to their
		descriptions). That is, for each distinct $i,j\in [d]$, if $\gamma (v_{i})=\gamma(v_{j})$,
		then $R(v_{i})\neq R(v_{j})$. 
		\item The verifier checks that the weights of the children of $u$ sum up
		to $\wgt{u}$; that is, 
		\begin{equation}
		\wgt{u}=\sum_{j=1}^{d}\wgt{v_{j}} \label{p_eq:sum}
		\end{equation}
		\item  For each $j\in\left[d\right]$, the verifier checks
		that $v_{j}$ is a transcript descendant of $u$.
		\item For each child $v_{j}$, the verifier checks that $\gamma\left(v_{j}\right)=\gamma(u)$.
		%
		
		\item The verifier checks that the ranges of all the children are disjoint; that is, for every two children $v_j$ and $v_k$, the verifier checks
		that $R\left(v_{j}\right)\cap R\left(v_{k}\right)=\emptyset$.
	
	\end{enumerate}
	\item \label{pub:emu:const:prob}The verifier chooses a child according to the probability distribution
	$J$ that assigns each $j\in\left[d\right]$ probability approximately
	proportional to $\wgt{v_{j}}$ using $O(\log r(n))$ coin tosses. That is, $J$ is such that
	\mmm
	{\eqtag{p_emu:const:approx_sampling}
		\textbf{Pr}\left[J=j\right]\leq\frac{\wgt{v_{j}}}{\sum_{i=1}^{d}\wgt{v_{i}}}\cdot \left(1+{1}/{r(n)}\right)
	}
	We only utilize $O(\log r(n))$ public coins per iteration since we want this emulation to be as efficient as possible in terms of randomness complexity, without sacrificing soundness by more than a constant factor in total. Hence, we compromise on sampling each child with probability proportional to $\wgt{v_j}$, and instead sample with approximate probability.
	See the explanation for approximate sampling in \expref{Appendix}{app:approx}. 
\end{enumerate}


By our conventions, the last message the verifier \orgV~ sends, denoted $\alpha_{m}$, contains the
outcomes $\rho\in\left\{ 0,1\right\} ^{r(n)}$ of the $r(n)$ coins tossed.
Thus, if the last node chosen is $v$, then $\rho$ can be easily extracted
from $\gamma\left(v\right)=\alpha_{1}\beta_{1},\dots,\alpha_{m}\beta_{m}$.
After the last iteration, the verifier performs final checks and accepts
if all of them hold:


\begin{enumerate}[label=(\roman*)]
	\item \label{last_valid}Check that $\rho$  is accepting for $\gamma\left(v\right)$ and consistent with it: It checks that $V_0\left(x,\rho,\beta_{1},\dots,\beta_{m}\right)=1$,
	and that for every $i=1,\dots,m$ it holds that $\alpha_{i}=V_0\left(x,\rho,\beta_{1},\dots,\beta_{i-1}\right)$.
	Note that the verifier needs $\rho$ in order to verify these conditions,
	so this check can only be done after the last iteration. Also note that if
	these checks pass then $\wgt{v}=1$ (rather than $\wgt{v}=0$).
	\item Check that $\wgt{v}=1$; in other words the prover's last claim should be that the weight of the last node chosen is $1$ (and not more than $1$).
\end{enumerate}


\end{appendices}

\subsection*{Acknowledgments.} 
I would like to thank my advisor, Prof. Oded Goldreich, for his encouragement to approach the problem studied in this paper, and for his guidance, support and contribution in the research and the writing process. I thank Dr. Guy Rothblum for useful discussions. I also thank the anonymous reviewers for providing useful comments and suggestions.


\bibliographystyle{tocplain}   
%
\bibliography{bibstrings,v018a013,bibtail}

%
%
%
%
\begin{tocauthors}
\begin{tocinfo}[leshkowitz]
	Maya Leshkowitz\\
        \phd\ student\\
	The Hebrew University of Jerusalem\\
        Jerusalem, Israel\\
	mleshkowitz\tocat{}gmail\tocdot{}com \\
\end{tocinfo}
\end{tocauthors}



%
%
%
%
%
%
%
%
%
%
%
%
%
%

\begin{tocaboutauthors}
\begin{tocabout}[leshkowitz]
\textsc{Maya Leshkowitz} received her M.\,Sc. from Weizmann Institute of Science, under the supervision of \href{http://www.wisdom.weizmann.ac.il/~/oded/}{Oded Goldreich}. 

\noindent Maya discovered her love for solving mathematical questions as a child when she played and solved riddles together with her grandfather, \href{https://www.wisdom.weizmann.ac.il/~oded/s_even.html}{Shimon Even}. In graduate school, although she was interested in Cognitive Science and human behavior, the Math and Computer Science courses at the Hebrew University sparked her old passion and %
led  %
her to pursue a M.\,Sc. in Computer Science. Currently, she is a Ph.\,D student in the Cognitive Science department at the Hebrew University, under the supervision of \href{http://labconscious.huji.ac.il/members/principal-investigator/ran-hassin}{Ran R. Hassin}. She is interested in how people group information into chunks (such as by event or category) and how these chunks later influence attitudes and evaluations.     
 
\noindent When she is not doing research, she enjoys drawing,
dancing, and traveling.

\end{tocabout}
\end{tocaboutauthors}

\end{document}
