appendix_step_1_compiler.tex

\section{PLONK Compiler for SNARKs}
\label{first_step_compiler}

\noindent We summarise and exemplify below the PLONK-based compilation technique~\cite{plonk} from 
ranged polynomial protocols for conditional NP relations (formal definition in Section~\ref{supplementary_poly_protocols_appendix}) to 
SNARKs for pure vector-based NP relations. This is a more detailed version of the first step of our two-step PLONK based compiler as 
defined in Section~\ref{sec_two_step_compiler}. Concretely, our first step applies the PLONK compiler~\cite{plonk} (Lemma 4.7): 
we compile the information theoretical ranged polynomial protocols $\Pla$ and $\Pa$ for relations $\Rla$ and $\Ra$, respectively (see Sections~\ref{sec_la,sec_a}) 
into SNARKs $\Plastar$, and $\Pastar$, respectively. We can define this compilation step for any ranged polynomial protocols for relations 
(as per Definition~\ref{supplementary_poly_protocols_appendix} in Section~\ref{def_ranged_poly_protocol}). In order to do that we need: 
\begin{itemize}
\item  The batched version of KZG polynomial commitments~\cite{KZG_10} described in Section 3 of PLONK~\cite{plonk}.\footnote{In fact, 
one can replace the use of KZG polynomial commitments with any binding polynomial commitment that has knowledge-soundness, including non-homomorphic polynomial commitments, 
such as FRI-based polynomial commitments (e.g., RedShift~\cite{redshift}). If the optimisation gained from PLONK linearisation technique is a goal, 
then, with minimal changes one can use any homomorphic polynomial commitment, e.g., the discrete logarithm based polynomial commitment 
from Halo~\cite{halo}.}
\item A general compilation technique: such a technique has been already defined in Lemma 4.7 of PLONK; combined with Lemma 4.5 
from PLONK this technique can be applied with minor adaptations (this includes the corresponding technical measures) to the notion of ranged 
polynomial protocols.  
\item So far, both the ranged polynomial protocols for relations and the protocols resulted after the first compilation step have been explicitly defined as interactive 
protocols. In order to obtain the non-interactive version of the latter (essentially the N in SNARK) one has to apply the Fiat-Shamir 
transform~\cite{FS_transform}, \cite{FS_transform_with_proof}, \cite{SE_plonk}.
\end{itemize}

\noindent Let $\mathcal{R}$ be a (conditional) NP relation, let $\mathscr{P}_{\mathcal{R}}$ be a ranged polynomial protocol for 
relation $\mathcal{R}$ and let $\mathscr{P}^*_{\mathcal{R}}$ be the SNARK compiled from $\mathscr{P}_{\mathcal{R}}$ using the PLONK compiler.  
The compilation technique requires the SNARK prover of  $\mathscr{P}^*_{\mathcal{R}}$ to compute 
polynomial commitments to all polynomials that the prover $\mathcal{P}_{poly}$ in $\mathscr{P}_{\mathcal{R}}$ sent to the ideal party $\mathcal{I}$. Analogously, 
it requires the SNARK verifier of $\mathscr{P}^*_{\mathcal{R}}$ to compute polynomial commitments to all pre-processed polynomials\footnote{This is a one-time computation that is 
reused by the SNARK verifier for all SNARK proofs over the same circuit.} as well polynomial commitments to polynomials the verifier $\mathcal{V}_{poly}$ 
in $\mathscr{P}_{\mathcal{R}}$ sent to the ideal party $\mathcal{I}$. Then, the SNARK prover sends the SNARK verifier openings to 
all the polynomial commitments computed by him as well as the polynomial commitments computed by the SNARK verifier. The SNARK 
prover additionally sends the corresponding batched proofs for polynomial commitment openings. In turn, the SNARK verifier accepts or rejects based 
on the result of the verification of the batched polynomial commitment scheme. \\

\noindent A more efficient compilation technique exists which reduces the number of polynomial commitments and alleged polynomial commitments openings 
(i.e., both group elements and field elements) sent by the SNARK prover to the SNARK verifier; this, in turn, reduces the size of the SNARK proof. 
This technique is called linearisation and is described, at a high level, after Lemma 4.7 in PLONK. The existing description however covers only the 
SNARK prover side and it does not detail the SNARK verifier side so in the following we cover that. \\

\noindent By functionality, the vectors that are handled by the the verifier $\mathcal{V}_{poly}$ are 
of two types: pre-processed vectors and public input vectors. These two types of vectors are used by $\mathcal{V}_{poly}$ 
to obtain, via interpolation over the range on which the respective range polynomial protocol is defined, pre-processed polynomials 
(as used in the Definition~\ref{supplementary_poly_protocols_appendix} in Section~\ref{def_ranged_poly_protocol}, e.g., polynomial $aux(X)$ used in Section~\ref{sec_la}) and 
public-inputs-derived polynomials (e.g., polynomials $pkx(X)$ and $pky(X)$ used in Sections~\ref{sec_la,sec_a})
and polynomial $b(X)$ used in Section~\ref{sec_la}). The efficient linearisation technique allows the SNARK verifier to reduce the 
number of polynomial commitments it has to compute compared to the general PLONK compiler in the following way. Instead of 
having to compute polynomial commitments to all polynomials $\mathcal{V}_{poly}$ sends to $\mathcal{I}$ (including any corresponding 
pre-processed polynomials), the SNARK verifier computes polynomial evaluations at one or multiple random points (as per the linearisation 
step specific requirements) for all the polynomials that are either easy to evaluate (e.g., polynomial $aux(X)$ used in Section~\ref{sec_a}) or 
all the polynomials that are obtained from vectors that do not take up a large amount of memory (e.g., polynomial $b(X)$ used in Section~\ref{sec_la}). 
For the rest of the polynomials (e.g., $\mathit{pkx}(X)$ and $\mathit{pky}(X)$), the SNARK verifier computes polynomial commitments as before.\\

\noindent We note we can apply all the techniques mentioned above, including the combined prover-and-verifier-side linearisation 
to compile our ranged polynomial protocols $\Pla$ and $\Pa$ into the corresponding SNARKs $\Plastar$ and $\Pastar$, respectively. 
To conclude this step, we formally state in Section~\ref{def_ranged_poly_protocol}, Lemma~\ref{le:compilation_step_1} under which conditions and how efficiently 
one can compile ranged polynomial protocols for conditional NP relations (where the public inputs are interpreted as vector of field elements) 
into hybrid model SNARKs by using only the original PLONK compiler. \\