no_witness_relations.tex

\label{sec:snarks}

In the following, we construct two related SNARKS, each of them allowing a prover to convince an 
efficient verifier that an alleged aggregated public key has indeed been computed correctly as an aggregate 
of a vector of public keys for which two succinct commitments (one to the vector of x affine coordinates and the other 
to the vector of y affine coordinates, respectively) are publicly known. The differences between the two  
constructions stem from how a \emph{bitmask} (also called a \emph{bitvector}) with one bit associated to each public key 
(necessary to signal the inclusion or omission of the respective public key w.r.t. the aggregate key) 
is used as part of the verifier's public input. We describe a 
\emph{basic accountable SNARK} (the bitmask is represented as a sequence of $0/1$ field elements) and a \emph{packed accountable SNARK} (the bitmask is 
partitioned into equal blocks of consecutive binary bits, and, in turn, each block is represented as a field element). 
%Each of our SNARKs implements a conditional NP relation bearing the 
%same name as the SNARK it implements. Note that the names ``basic accountable" (for short, ``basic'') and 
%``packed accountable" (for short, ``packed'') do not refer to the security of the respective SNARK but they summarise properties 
%of the underlying sets of constraints that define the SNARKs, and, hence their use case. 
We finally transform basic and packed accountable SNARKs into SNARKs for building accountable light client systems. \\

\noindent In order to compile our desired SNARKs we proceed as follows:
\begin{itemize}
\item In Sections \ref{sec_la} and \ref{sec_a} we define vector-based conditional NP relations $\Rla$ (i.e., basic accountable) and $\Ra$ (packed accountable).  
\item Correspondingly, we design two ranged polynomial protocols for the above relations. The ranged polynomial protocol notion originates in~\cite{plonk}; 
for convenience, we remind it to the reader (including a refinement) in Section~\ref{supplementary_poly_protocols_appendix};  
\item In Section~\ref{sec_two_step_compiler} we define a two-steps PLONK-inspired compiler which we use to compile the two ranged polynomial protocols into 
SNARKs for two novel mixed vector and trusted polynomial commitments conditional NP relations which we denote by 
$\Rlacom$ and $\Racom$, respectively. 
\item In Section~\ref{sec:inst_committee_key} we give an instantiation for committee key scheme for aggregatable signatures which uses, in turn, our SNARKS 
compiled in Section~\ref{sec_two_step_compiler} and our instantiation for BLS aggregatable signatures from Section~\ref{sec:bls}. 
\item We include in Section~\ref{suplementary_plonk_comparison} a comparison between PLONK~\cite{plonk} and our custom SNARKs. 
\end{itemize}

\noindent In more detail, we define our conditional NP relations over $\mathbb{F}$, i.e., the base field of $\einn$. 
Our SNARKs provers' circuits are defined as well over $\mathbb{F}$ as the scalar field of $\eout$. The vector of public keys, which is part of the public input for both of our 
relations $\Rla$ and $\Ra$, and is denoted by $\mathbf{pk} = (\mathit{pk_0}, \ldots, \mathit{pk_{n-2}})$, is a vector of pairs with each component 
in $\mathbb{F}$. This vector has size $n-1$ ($n$ defined in 
Section~\ref{sec:lagrange}). For $\Rla$ we denote 
the $n$ components bitmask by $\mathbf{bit} = (\mathit{bit_0}, \ldots, \mathit{bit_{n-1}})$ 
(meaning that each component belongs to the set $\{0,1\} \subset \mathbb{F}$), 
while the $\Ra$ relation is defined using the \emph{compacted bitmask} 
$\mathbf{b'} = (\mathit{b'_{0}}, \ldots, \mathit{b'_{\frac{n}{\block}-1}})$ of $\frac{n}{\block}$ field elements, 
each of which is $\block$ binary bits long ($\block$ has been defined in Section~\ref{sec:lagrange}). 
Each of the bits in the bit representation of these field elements signals the 
inclusion (or exclusion) of the index-wise corresponding public keys into the aggregated public key $\mathit{apk}$. In fact, 
the last bit of field element $\mathit{b'_{\frac{n}{\block}-1}}$ as well as the $n$-th component $\mathit{bit_{n-1}}$ do not correspond to any public key, 
but, as will become clear in the following, they have been included for easier design of constraints. \\ 

\noindent We denote by $H$ the multiplicative subgroup of $\mathbb{F}$ generated 
by $\omega$ as defined in Section~\ref{sec:lagrange}. We denote by  $\mathit{incl}(a_0, \ldots, a_{n-2})$ the inclusion 
predicate that checks if $(a_0, \ldots, a_{n-2}) \in \ginn{1}^{n-1}$. Moreover let $h = (\mathit{h_x}, \mathit{h_y})$ 
be some fixed, publicly known element in $\einn \setminus \ginn{1}$. We denote by $(a_x, a_y)$ the affine representation in 
$x$ and $y$ coordinates of $a \in \einn$ and by $\oplus$ the point addition in affine coordinates on the elliptic curve $\einn$. 
We denote by $\mathbb{B} = \{0,1\} \subset \mathbb{F}$. \\

%\noindent Finally, as mentioned in section~\ref{sec:conditional_relations}, the interpretation of adding explicit domains to public 
%inputs in the definition of conditional NP relations is that the honest parties (in our case, both the polynomial protocol verifiers and the SNARKs verifiers 
%as defined in this section below) parse the public inputs according to the specified domains without any further checks. Any checks or 
%computations that the honest parties perform regarding the public inputs are explicitly described as part of the protocols followed by 
%the honest parties.
%\vspace{-0.17in}
\subsection{Basic Accountable Ranged Polynomial Protocol}
\label{sec_la}
%\vspace{0in}
%\noindent We start by describing our conditional basic accountable relation $\Rla$ and the 
%corresponding $H$-ranged polynomial protocol $\Pla$. %For brevity, we omit the security parameter 
%$\lambda$ whenever we refer to any conditional NP relations for which we build SNARKs. \\

\noindent \textsf{Conditional Basic Accountable Relation $\Rla$}  
%\vspace{-0.05in}
\begin{equation*}
\begin{split}
\Rla = & \{(\mathbf{pk} \in ({\mathbb{F}^2})^{n-1}, \mathbf{bit} \in \mathbb{B}^n,
\mathit{apk} \in \mathbb{F}^2; \_) : \mathit{apk} = \sum_{i=0}^{n-2} [\mathit{bit_i}] \cdot \mathit{pk_i} \ | \ \mathbf{pk} \in \ginn{1}^{n-1} \} 
\end{split}
\end{equation*}
\noindent where $\mathbf{pk} = (\mathit{pk_0}, \ldots, \mathit{pk_{n-2}})$ and $\mathbf{bit} = (\mathit{bit_0}, \ldots, \mathit{bit_{n-1}})$. 
\noindent In this section we use the following polynomials and polynomial identities: \\

\noindent \textsf{Polynomials as Computed by Honest Parties} 
\begin{align*}
&\mathsf{b(X)} = \sum_{i=0}^{n-1} \mathit{bit_i} \cdot \mathsf{L_i(X)}; \mathsf{pkx(X)} =  \sum_{i=0}^{n-2} \mathit{pkx_i} \cdot \mathsf{L_i(X)}; \mathsf{pky(X)} =  \sum_{i=0}^{n-2} \mathit{pky_i} \cdot \mathsf{L_i(X)} \\
&\mathsf{kaccx(X)}  =  \sum_{i=0}^{n-1} \mathit{kaccx_i} \cdot \mathsf{L_i(X)}; \mathsf{kaccy(X)}  = \sum_{i=0}^{n-1} \mathit{kaccy_i} \cdot \mathsf{L_i(X)}, 
\end{align*}
\noindent where $(\mathit{pkx_0}, \ldots, \mathit{pkx_{n-2}})$ 
and $(\mathit{pky_0}, \ldots, \mathit{pky_{n-2}})$ are computed such that $\forall i \in \{0, \ldots, n-2\}$, $\mathit{pk_i}$ 
is interpreted as a pair $(\mathit{pkx_i}, \mathit{pky_i})$ with its components in $\mathbb{F}$; we also have 
$(\mathit{kaccx_{0}}, \mathit{kaccy_{0}}) = (\mathit{h_x}, \mathit{h_y})$ and 
$(\mathit{kaccx_{i+1}}, \mathit{kaccy_{i+1}}) =  (\mathit{kaccx_{i}}, \mathit{kaccy_{i}}) \oplus \mathit{bit_i}(\mathit{pkx_{i}}, \mathit{pky_{i}})$, 
$\forall i < n-1$. Note that in the last relation $\mathit{bit_i}$ is not interpreted as a field element anymore but as a binary bit.\\

\noindent \textsf{Polynomial Identities} 
\begin{align*}
& id_1(X) = (X-\omega^{n-1}) \cdot [b(X) \cdot ((kaccx(X)-pkx(X))^2 \cdot (kaccx(X)+ pkx(X) + \\ 
& + kaccx(\omega\cdot X)) - (pky(X) - kaccy(X))^2) +  (1-b(X))\cdot (kaccy(\omega\cdot X) - kaccy(X))] \\
& id_2(X)  =  (X-\omega^{n-1})\cdot [b(X) \cdot ((kaccx(X) - pkx(X)) \cdot (kaccy(\omega \cdot X) + kaccy(X)) - \\
& - (pky(X) - kaccy(X)) \cdot (kaccx(\omega \cdot X) - kaccx(X))) +  (1-b(X)) \cdot \\ 
& \cdot(kaccx(\omega \cdot X) - kaccx(X))] \\
& id_3(X)  =  (kaccx(X) - h_x)\cdot L_0(X) + (kaccx(X) - (h\oplus apk)_{x}) \cdot L_{n-1}(X)  \\
& id_4(X) =  (kaccy(X) - h_y)\cdot L_0(X) + (kaccy(X) - (h\oplus apk)_{y}) \cdot L_{n-1}(X) \\
& id_5(X) =  b(X)(1-b(X)).
\end{align*}

\noindent Polynomial identity $id_5(X)$ is not needed for defining ranged polynomial protocols for $\Rla$, however it is included 
here to ease presentation and for proofs consistency for the following section. \\

\noindent \textsf{$H$-ranged Polynomial Protocol $\Pla$ for Relation $\Rla$} \\

\noindent $H$-ranged polynomial protocol $\Pla$ for conditional relation $\Rla$ describes the interaction of the prover 
$\mathcal{P}_{poly}$, the verifier $\mathcal{V}_{poly}$ and the trusted third party $\mathcal{I}$ in accordance to 
Definition~\ref{def_ranged_poly_protocol} from Section~\ref{supplementary_poly_protocols_appendix}. \\

%\noindent \textsf{Protocol $\Pla$} \\

\noindent $\mathcal{P}_{poly}$ and $\mathcal{V}_{poly}$ know public input 
$\mathbf{bit} \in \mathbb{B}^n$, $\mathbf{pk} \in (\mathbb{F}^2)^{n-1}$ and $\mathit{apk} \in (\mathbb{F})^2$ 
which are interpreted as per their respective domains.
\begin{enumerate}
\item $\mathcal{V}_{poly}$ computes $b(X)$, $pkx(X)$, $pky(X)$.
\item $\mathcal{P}_{poly}$ sends polynomials $kaccx(X)$ and $kaccy(X)$ to $\mathcal{I}$. 
\item $\mathcal{V}_{poly}$ asks $\mathcal{I}$ to check whether the following polynomial relations hold over range $H$ 
$$id_i(X) = 0, \forall i \in [4].$$
\item $\mathcal{V}_{poly}$  accepts if $\mathcal{I}$'s checks verify. 
\end{enumerate}

\noindent We show that protocol $\Pla$ is an $H$-ranged polynomial protocol for 
conditional NP relation $\Rla$. For this, we first prove that:
\begin{test_claim} Assume that $\forall i < n-1$ such that $\mathit{bit}_i = 1$, $pk_i = (pkx_i, pky_i) \in \ginn{1}$. 
If polynomial identities $id_i(X) = 0, \forall i \in [5],$ hold over range 
$H$ and and the polynomial $b(X)$ has been constructed via interpolation on $H$ such that $b(\omega^i) = \mathit{bit}_i, \forall i <n$ then $\mathit{bit}_i \in \mathbb{B} = \{0,1\} \subset \mathbb{F}, \forall i <n$ \\
$(kaccx_{0}, kaccy_{0}) = (h_x, h_y)$, $(kaccx_{n-1}, kaccy_{n-1}) = (h_x, h_y) \oplus (apk_x, apk_y)$, \\
$(kaccx_{i+1}, kaccy_{i+1}) =  (kaccx_{i}, kaccy_{i}) \oplus \mathit{bit}_i(pkx_{i}, pky_{i})$, $\forall i < n-1$, 
where in the last relation $\mathit{bit_i}$ should not be interpreted as a field element but as a binary bit.
\label{claim:keys_affine_comm}
\end{test_claim}

\begin{proof} Everything but the last property in the claim is easy to derive from polynomial identities 
$id_3(X) =0, id_4(X )= 0, id_5(X) = 0$ holding over $H$. In order to prove the remaining property, we remind 
the incomplete addition formulae for curve points in affine coordinates, over elliptic curve in short Weierstrasse form and state:\\ 

\begin{observation}  
\label{obs:incomplete_addition} 
Suppose that $\mathit{bit} \in \{0,1\}$, $(x_1,y_1)$ is a point on an elliptic curve in short Weierstrasse form, and, if 
$\mathit{bit} = 1$, so is $(x_2,y_2)$. We claim that the following equations: 
\begin{align*}
&\mathit{bit}((x_1 - x_2)^2 (x_1 + x_2 + x_3) - (y_2 - y_1)^2 ) + (1 - \mathit{bit})(y_3 - y_1) =0 \ (\ast)\\
&\mathit{bit}((x_1 - x_2)(y_3 + y_1) - (y_2 - y_1)(x_3 - x_1)) + (1 - \mathit{bit})(x_3 - x_1) =0 \ (\ast\ast)
\end{align*}
\end{observation}

\noindent hold if and only if one of the following three conditions hold 

\begin{enumerate}
\item \label{cond1} $\mathit{bit}=1$ and $(x_1,y_1)\oplus(x_2,y_2)=(x_3,y_3)$ and $x_1 \neq x_2$
\item \label{cond2} $\mathit{bit}=0$ and $(x_3,y_3)=(x_1,y_1)$ 
\item  \label{cond3} $\mathit{bit}=1$ and $(x_1,y_1)=(x_2,y_2)$\footnote{Note that under condition~\ref{cond3}, $(x_3,y_3)$ 
can be any point whatsoever, maybe not even on the curve. The same holds true for $(x_2, y_2)$ under the condition~\ref{cond2}.}.
\end{enumerate}

\noindent It is easy to see that each of the conditions~\ref{cond1},\ref{cond2},\ref{cond3} above implies equations $(\ast)$ and $(\ast \ast)$.
\noindent For the implication in the opposite direction, if we assume that $(\ast)$ and $(\ast \ast)$ hold, then \\

\noindent \textit{Case a:} For $\mathit{bit}=0$, the first term of each equation $(\ast)$ and $(\ast \ast)$ vanishes, 
leaving us with $y_3-y_1=0$ and $x_3-x_1=0$ which are equivalent to condition~\ref{cond2}. \\

\noindent \textit{Case b:} For $\mathit{bit}=1$ and $x_1=x_2$, by simple substitution in $(\ast)$ and $(\ast \ast)$, 
we obtain $y_1 = y_2$, i.e., condition~\ref{cond3}.  \\

\noindent \textit{Case c:} For $\mathit{bit}=1$ and $x_1 \neq x_2$, then we can substitute
$\beta=\frac{y_2-y_1}{x_2-x_1}$ into equations $(\ast)$ and $(\ast \ast)$, leaving us with
$$x_1+x_2+x_3=\beta^2 \textrm{ and } y_3+y_1=\beta(x_3-x_1).$$
which are the usual formulae for short Weierstrass form addition of affine coordinate points when $x_1 \neq x_2$ 
so this is equivalent to condition~\ref{cond1}. \\

\noindent We apply the Observation~\ref{obs:incomplete_addition} by noticing that if $id_1(X)$ and $id_2(X)$ hold over $H$, 
then $(\ast)$ and $(\ast \ast)$ hold with $(x_1, y_1)$ substituted by $(kaccx_i,kaccy_i)$, $(x_2, y_2)$ 
substituted by $(pkx_i, pky_i)$, $(x_3, y_3)$ substituted by $(kaccx_{i+1},kaccy_{i+1})$ and $\mathit{bit}$ 
substituted by $\mathit{bit}_i$ for $0 \leq i \leq n-2$, where $\mathit{bit_i}$ should not be interpreted as a field element but as binary 
bit. Moreover, since $(kaccx_{0}, kaccy_{0}) = (h_x, h_y) \in \einn \setminus \ginn{1}$ 
and if $(pkx_i, pky_i) \in \ginn{1}$ whenever $\mathit{bit}_i = 1$, then $\forall i < n-1$ 
equations $(\ast)$ and $(\ast \ast)$ obtained after the substitution defined above are equivalent to either 
condition~\ref{cond1} or condition~\ref{cond2}, but never condition~\ref{cond3}, so the result of the sum (i.e., $(kaccx_{i+1}, kaccy_{i+1})$, $0\leq i \leq n-2$) is, 
by induction, at each step a well-defined point on the curve and this concludes our proof.
\end{proof}

\begin{corollary} Assume $\forall i < n-1$ 
such that $\mathit{bit}_i = 1$, $pk_i = (pkx_i, pky_i) \in \ginn{1}$. 
If the polynomial identities $id_i(X) = 0, \forall i \in [4],$ hold over range $H$ and 
$\mathit{bit_i} \in \mathbb{B}$, $\forall i < n-1$ and $b(X) = \sum_{i=0}^{n-1} \mathit{bit_i} \cdot L_i(X)$
then:  \\
$(kaccx_{0}, kaccy_{0}) = (h_x, h_y)$, \\
$(kaccx_{n-1}, kaccy_{n-1}) = (h_x, h_y) \oplus (apk_x, apk_y)$, \\
$(kaccx_{i+1}, kaccy_{i+1}) =  (kaccx_{i}, kaccy_{i}) \oplus \mathit{bit_i}(pkx_{i}, pky_{i})$, $\forall i < n-1$, where in the last relation 
$\mathit{bit_i}$ should not be interpreted as a field element but as a binary bit.
\label{corollary:keys_affine_comm}
\end{corollary}

\begin{proof}The proof follows trivially from the general result stated by Claim~\ref{claim:keys_affine_comm}. 
\end{proof}

\begin{lemma} 
\label{le:ba}
$\Pla$ as described above is an $H$-ranged polynomial 
protocol for conditional NP relation $\Rla$.
\end{lemma}

\begin{proof}
If $(\mathbf{bit},\mathbf{pk}, \mathit{apk}) \in \Rla$ holds, 
meaning that $\mathbf{bit} \in \mathbb{B}^n$ and $\mathbf{pk} \in \ginn{1}^{n-1}$ and $\mathit{apk} = \sum_{i=0}^{n-2} [\mathit{bit_i}] \cdot \mathit{pk_i}$ hold, 
then it is easy to see that the honest prover $\mathcal{P}_{poly}$ in $\Pla$ will convince the honest verifier $\mathcal{V}_{poly}$ in 
$\Pla$ to accept with probability $1$ so perfect completeness holds. \\
Regarding knowledge-soundness, if the verifier $\mathcal{V}_{poly}$ in $\Pla$ accepts, 
then the extractor $\mathcal{E}$ does not have to do anything as the relation $\Rla$ does not have a witness.  
However, we have to prove that if $\mathbf{pk} \in \ginn{1}^{n-1}$ and the verifier in $\Pla$ accepts, 
then $(\mathbf{bit},\mathbf{pk}, \mathit{apk}) \in \Rla$ holds, which given our definition for conditional relation is 
equivalent to proving that $\mathit{apk} = \sum_{i=0}^{n-2} [\mathit{bit_i}] \cdot \mathit{pk_i}$ holds. This is indeed the case due to 
corollary~\ref{corollary:keys_affine_comm}.

\end{proof}
%\vspace{-0.15in}
\subsection{Packed Accountable Ranged Polynomial Protocol}
\label{sec_a}
Let $\mathbb{F}_{|\block|}$ be the subset of field elements in $\mathbb{F}$ that can be represented using at 
most $\block$ bits, i.e., the set $\{0, \ldots, 2^{\block -1} \}$, where $\block$ has been defined in Section ~\ref{sec:lagrange}. 
Our conditional packed accountable relation $\Ra$ and the corresponding $H$-ranged polynomial protocol 
$\Pa$ are defined as follows:\\
 
\noindent \textsf{Conditional Packed Accountable Relation $\Ra$} 
\begin{equation*}
\begin{split}
\Ra = & \{(\mathbf{pk} \in (\mathbb{F}^2)^{n-1},\mathbf{b'} \in \mathbb{F}_{|\block|}^{\frac{n}{\block}},
\mathit{apk} \in \mathbb{F}^2; \mathbf{bit}) : \\ 
 & \mathit{apk} = \sum_{i=0}^{n-2} [\mathit{bit_i}] \cdot \mathit{pk_i} \ | \ \mathbf{pk} \in \ginn{1}^{n-1} \ \wedge \\
 & \wedge \mathbf{bit} \in \mathbb{B}^n  \wedge b'_{j} = \sum_{i=0}^{\block -1}2^i \cdot \mathit{bit_{\block \cdot j + i}}, \forall j < \frac{n}{\block} \} 
\end{split}
\end{equation*}
where $\mathbf{b'} = (b'_{0}, \ldots, b'_{{\frac{n}{\block}} -1})$. We define new polynomials and polynomial identities: \\

\noindent \textsf{New Polynomials as Computed by Honest Parties} 
$$ aux(X) = \sum_{i=0}^{n-1}aux_i \cdot L_i(X); c_{a}(X) = \sum_{i=0}^{n-1} c_{a,i} \cdot L_i(X); acc_{a}(X)  =  \sum_{i=0}^{n-1} acc_{a,i}  \cdot L_i(X)$$
\noindent where $aux_{i} = 1 \in \mathbb{F}$ if $i$ is divisible with $\block$ and $aux_{i} = 0 \in \mathbb{F}$ otherwise, $\forall i < n$ 
and $c_{a,i} = 2^k \cdot r^j$, $k = i \mod \block$, $j = i \div \block$, $\forall i < n$ ($r \in \mathbb{F}$ is introduced in protocol $\Pa$) and $acc_{a,i}$ are components of the vector $(0, \mathit{bit}_0 \cdot c_{a,0}, \mathit{bit}_0 \cdot c_{a,0}+ \mathit{bit}_1  \cdot c_{a,1}, \ldots, \sum_{i=0}^{n-2}\mathit{bit}_i \cdot c_{a,i})$, where $\mathit{bit_{0}}, \ldots, \mathit{bit_{n-1}}$ represent the first $n$ 
bits (however, we interpret them as elements in $\mathbb{B}$) of the concatenation of the binary representation of 
$\mathit{b'_{0}}, \ldots, \mathit{b'_{\frac{n}{\block}-1}}$.\footnote{As 
part of a correct public input for relation $\Ra$, each field element in the set 
$\{\mathit{b'_{0}}, \ldots, \mathit{b'_{\frac{n}{\block}-1}} \}$ is at most $\block$ binary bits long. If any such field element has fewer than $\block$ bits, 
then the honest prover will pad it with $0$s starting from the most significant bit up to a total individual length of $\block$ bits.} 
With this definition of $(\mathit{bit_{0}}, \ldots, \mathit{bit_{n-1}})$, 
the definition of $b(X)$ remains the same as in Section \ref{sec_la}.\\

\noindent \textsf{New Polynomial Identities} 
\begin{align*}
id_6(X) & =  c_{a}(\omega \cdot X) - c_{a}(X)\cdot (2+ (\frac{r}{2^{\block -1}} -2) \cdot aux(\omega \cdot X)) - (1 - r^{\frac{n}{\block}}) \cdot L_{n-1}(X).\\
id_7(X) & =  acc_{a}(\omega \cdot X) - acc_{a}(X) - b(X)\cdot c_{a}(X) + \mathsf{sum} \cdot L_{n-1}(X),
\end{align*}

\noindent where $\mathsf{sum}$ is a field element known to both $\mathcal{P}_{poly}$ and $\mathcal{V}_{poly}$ and will be defined below. \\ 

\noindent \textsf{$H$-ranged Polynomial Protocol $\Pa$ for Relation $\Ra$} \\

%\noindent In the following, we describe $H$-ranged polynomial protocol $\Pa$ for conditional relation 
%$\Ra$. \\

%\noindent \textsf{Protocol $\Pa$} \\

\noindent $\mathcal{P}_{poly}$ and $\mathcal{V}_{poly}$ know public inputs 
$\mathbf{b'} \in \mathbb{F}_{|\block|}^{\frac{n}{\block}}$ and 
$\mathbf{pk} \in (\mathbb{F}^2)^{n-1} $ and $\mathit{apk} \in \mathbf{F}^2$ which are interpreted as per their respective domains. \\

\begin{enumerate}
\item $\mathcal{V}_{poly}$ computes $pkx(X)$, $pky(X)$ and $aux(X)$.
\item $\mathcal{P}_{poly}$ sends polynomials $b(X)$, $kaccx(X)$ and $kaccy(X)$ to $\mathcal{I}$. 
\item $\mathcal{V}_{poly}$ replies with a random value $r$ chosen from $\mathbb{F}$. 
\item $\mathcal{V}_{poly}$ computes $\mathsf{sum}$ as $\sum_{j=0}^{\frac{n}{\block}-1} \mathit{b'_{j}} \cdot r^j$.\footnote{Note that if 
$b'_{j} = \sum_{k=0}^{\block -1}2^k \cdot \mathit{bit_{\block \cdot j + k }}$, $\forall j < \frac{n}{\block}$ and $\mathit{bit_i} \in \mathbb{B}, \forall i <n$, 
then $\sum_{i=0}^{n-1} 2^{i \mod \block} \cdot r^{i \div \block} \cdot \mathit{bit}_{i} = \sum_{j=0}^{\frac{n}{\block}-1}(\sum_{i=0}^{\block -1}2^k \cdot \mathit{bit_{\block \cdot j + k }}) \cdot r^j= \sum_{j=0}^{\frac{n}{\block}-1} \mathit{b'_{j}} \cdot r^j$.}
\item $\mathcal{P}_{poly}$ sends polynomials $c_{a}(X)$ and $acc_{a}(X)$ to $\mathcal{I}$. 
\item $\mathcal{V}_{poly}$ asks $\mathcal{I}$ to check whether the following polynomial relations hold over range $H$: 
$$id_i(X) = 0, \forall i \in [7].$$
\item $\mathcal{V}_{poly}$ accepts if $\mathcal{I}$'s checks verify. 
\end{enumerate}

\noindent We show $\Pa$ is an $H$-ranged polynomial protocol 
for relation $\Ra$. First, we prove the following:

\begin{test_claim}
\label{claim:bitvector_comm}
If the polynomial identities $id_6(X) = 0, id_7(X) = 0$ hold over range $H$, then, 
\ewnp, 
we have $c_{a,i} =  2^{i \mod \block} \cdot r^{i \div \block}$, $\forall i < n$ and $\mathsf{sum} = \sum_{i=0}^{n-1}b_i \cdot c_{a,i}$, 
where $b_i = b(\omega^i), \forall i <n$. If, additionally, identity $id_5(X) = 0$ holds over $H$, 
$r$ has been randomly chosen in $\mathbb{F}$, $\mathsf{sum} = \sum_{j=0}^{\frac{n}{\block}-1} b'_{j}r^j$ 
(as computed by $\mathcal{V}_{poly}$) and $\mathit{bit_{i}} \in \mathbb{B}, \forall i < n$ and 
$b'_{j} = \sum_{k=0}^{\block -1}2^k \cdot \mathit{bit_{\block \cdot j + k}}, \forall 0 \leq j \leq \frac{n}{\block} -1$ 
(due to the input $(b'_{0}, \ldots, b'^{\frac{n}{\block} -1})$ 
being interpreted by the verifier $\mathcal{V}_{poly}$ as in $\mathbb{F}_{|\block|}^{\frac{n}{\block}}$), then \ewnp, 
$b_i = \mathit{bit_{i}}, \forall i <n$.
\end{test_claim}

\begin{proof}
We show the first part of the claim by proving by contradiction that $c_{a,0} =1$ using the Schwartz-Zippel Lemma, the fact that $r$ has been 
randomly chosen, and, also the fact that $n$ is negligibly smaller compared to the size of $\mathbb{F}$. Finally, we appropriately expand $\mathit{id_7}(X) = 0$ 
over $H$, sum the LHS on one hand and the RHS on the other hand, equate and obtain the desired property of $\mathsf{sum}$. We show the second part of 
the claim by expressing $\mathsf{sum}$ in two ways as $\sum_{j=0}^{\frac{n}{\block}-1} b'_{j}r^j $ and as $\sum_{i=0}^{n-1} b_i \cdot c_{a,i}$ and re-writing the 
latter as an inner product of a vector of field elements with the vector $(1, r, \ldots, r^{\frac{n}{\mathsf{block}}-1})$ and using the small exponents test~\cite{small_exponents}. 
Full proof can be found in Section~\ref{sec:missing_snark_proofs}.
\end{proof}

\begin{lemma} 
$\Pa$ is an $H$-ranged polynomial protocol for conditional NP relation $\Ra$.
\end{lemma}

\begin{proof} 
The proof follows an analogous logic as used for proving Lemma~\ref{le:ba}. We additionally use 
claim~\ref{claim:bitvector_comm} and corollary~\ref{corollary:keys_affine_comm}. Full proof can be found in Section~\ref{sec:missing_snark_proofs}.
\end{proof}
%\vspace{-0.1in}

\subsection{Compiler for Hybrid Model SNARKs with Mixed Inputs}
\label{sec_two_step_compiler}
%\vspace{-0.05in}

\noindent We present a two-steps PLONK-based compilation technique from 
ranged polynomial protocols for conditional NP relations (formal definition in Section~\ref{supplementary_poly_protocols_appendix}) to hybrid 
model SNARKs (Definition~\ref{dfn_snark}) such that the conditional NP relations that define the SNARKs we compile in the 
second step contain both polynomial commitments and vectors of field elements as public inputs. By using just the first step of our 
compiler which is equivalent to the original PLONK compiler~\cite{plonk}, one would 
not be able to obtain SNARKs with mixed public inputs consisting of both vectors of field elements and also poly commitments. 
In turn, this type of NP relations with mixed inputs is crucial for designing accountable light clients via the use of committee key schemes 
(see Section~\ref{sec:inst_committee_key}).\\
\vspace{-0.2in}
\subsubsection{Our Compiler: Step 1} 
\label{compiler_step_1}
\vspace{-0.05in}
%\input{short_step_1_compiler.tex}
\input{full_step_1_compiler.tex}
\vspace{-0.2in}
\subsubsection{Our Compiler: Step 2}
\label{compiler_step_2}
\vspace{-0.05in}
\input{full_step_2_compiler.tex}

\noindent It is straightforward to apply the technique described above to our SNARKs $\Plah$ and $\Pah$ 
compiled in Step 2 and obtain relations $\Rlacom$ and $\Racom$ as described below such that they fulfil Lemma~\ref{sergey_type_relations}.\footnote{Due to our specific application to proof-of-stake blockchain context in which we make use of our custom SNARKs, 
the assumption/requirement that  $\mathit{State}_{\mathcal{R}_{\mathit{vec}, \mathit{com}}} \neq \emptyset$ for 
$\mathcal{R}_{\mathit{vec}, \mathit{com}} \in \{\Rlacom, \Racom \}$ is fulfilled.}
%\vspace{-0.1in}
\begin{align*}
& {\Rlacom} = \{(\mathbf{C} \in \mathcal{C}, \mathbf{bit} \in \mathbb{B}^n, \mathit{apk} \in \mathbb{F}^2; \mathbf{pk}) : 
\mathit{apk} = \sum_{i=0}^{n-2} [\mathit{bit_i}] \cdot \mathit{pk_i} \ | \\ & | \ \mathbf{pk} \in \ginn{1}^{n-1} \ \wedge \  \mathbf{C} = \mathbf{Com}(\mathbf{pk}) \} 
\end{align*}
%\vspace*{-0.75cm}
\begin{align*}
& {\Racom}  = \{(\mathbf{C} \in \mathcal{C}, \mathbf{b'} \in \mathbb{F}_{|\block|}^{\frac{n}{\block}}, \mathit{apk} \in \mathbb{F}^2;\mathbf{pk}, \mathbf{bit}) : 
\mathit{apk} = \sum_{i=0}^{n-2} [\mathit{bit_i}] \cdot \mathit{pk_i} \ | \\ & | \ \mathbf{pk} \in \ginn{1}^{n-1} \ \wedge \ \mathbf{bit} \in \mathbb{B}^n  \wedge b'_{j} = \sum_{i=0}^{\block -1}2^i \cdot \mathit{bit_{\block \cdot j + i}}, \forall j < \frac{n}{\block}  \wedge \  \mathbf{C} = \mathbf{Com}(\mathbf{pk}) \} 
\end{align*}
For completeness, we also include the full rolled out SNARK $\Pah$ for relation $\Racom$ in Section~\ref{sec:rolled_out} and we provide a comparison between PLONK universal 
SNARK and our custom SNARKs in Section~\ref{suplementary_plonk_comparison}.  
%\vspace*{-0.75cm}
\subsection{Our Instantiation for Committee Key Scheme}
\label{sec:inst_committee_key}
\noindent Given relations $\Rlacom$ and $\Racom$ described in Section~\ref{sec_two_step_compiler}, 
we are ready to present an instantiation for committee key scheme for aggregatable signatures 
(see definition in Section~\ref{sec:committee_key}); this, in turn, can be used to build an accountable light client. 
We instantiate $u$ and $v$ introduced in Section~\ref{sec:committee_key} as follows: let $u = n-1$, where $n$ was defined in 
Section~\ref{sec:lagrange} and we let $v \in \mathbb{N}, n-1 \leq v$, $v = \mathsf{poly}(\lambda)$, where by $v$ we denote the 
maximum number of validators that the system allows.

\begin{construction}(Committee Key Scheme for Aggregatable Signatures)
\label{inst:cks} In our implementation we call committee key scheme for 
aggregatable signatures the following instantiation of Definition~\ref{def: committee_key}, where $\mathcal{R} \in \{\Rlacom, \Racom\}$ 
as defined in the end of Section~\ref{sec_two_step_compiler}:
\begin{itemize}
\item $\mathit{CKS_{\mathcal{R}}.Setup}(v)$ calls the following algorithms: 
\begin{enumerate}
\item $\mathit{pp} \leftarrow \mathit{AS.Setup}(\mathit{aux_{\mathit{AS}}}= v+1)$ with  $\mathit{AS.Setup}$ part of Instantiation~\ref{insta:bls} where \\
$\ginn{1}$ is part of $\mathit{pp}$ (see notation in Section~\ref{sec:bls});
\item $\mathit{srs} \leftarrow \mathit{SNARK.Setup}(\mathit{aux_{\mathit{SNARK}}} = (v, 3v))$ with \\
$\mathit{srs}=([1]_{\indexoneout}, [\tau]_{\indexoneout}, \ldots, [\tau^{3v}]_{\indexoneout}, [1]_{\indextwoout}, [\tau]_{\indextwoout})$ ;
\item $(\mathit{rs}_{\mathit{pk}}, \mathit{rs}_{\mathit{vk}}) \leftarrow \mathit{SNARK.KeyGen}(\mathit{srs}, \mathcal{R})$ with \\ 
$(\mathit{rs}_{\mathit{pk}}, \mathit{rs}_{\mathit{vk}}) =  (([1]_{\indexoneout}, [\tau]_{\indexoneout}, \ldots, [\tau^{3v}]_{\indexoneout}),([1]_{\indexoneout}, [1]_{\indextwoout}, [\tau]_{\indextwoout}))$ \\
where %$\mathcal{R} \in \{\Rlacom, \Racom \}$ is one of the accountable relations defined in the end of section~\ref{sec_two_step_compiler} and 
the notation $[\ldots]_{\indexoneout}$ and $[\ldots]_{\indextwoout}$ was defined in Section~\ref{sec:pairings}.
\end{enumerate}

\item $\mathit{ck} \leftarrow \mathit{CKS_{\mathcal{R}}.GenerateCommitteeKey}(\mathit{rs_{pk}}, (\mathit{pk_i})_{i=1}^{n-1})$, where 
$\mathit{CKS_{\mathcal{R}}.GenerateCommitteeKey}$ first checks whether $(\mathit{pk_i})_{i=1}^{n-1} \in \ginn{1}^{n-1}$; 
if this does not hold, it outputs $\bot$; otherwise, the algorithm \\ $\mathit{CKS_{\mathcal{R}}.GenerateCommitteeKey}$ continues with the 
computations described below: \\
\noindent Let $\mathbf{pkx} = (\mathit{pkx_{1}}, \ldots, \mathit{pkx_{n-1}})$, $\mathbf{pky} = (\mathit{pky_{1}}, \ldots, \mathit{pky_{n-1}})$, $\forall i \in [n-1]$, $\mathit{pk_i} = (\mathit{pkx_i}, \mathit{pky_i}) \in \mathbb{F}^{2}$. \\
\noindent Let $pkx(X) = \sum_{i=0}^{n-2} \mathit{pkx_{i+1}} \cdot L_i(X)$, $pky(X) = \sum_{i=0}^{n-2} \mathit{pky_{i+1}} \cdot L_i(X)$.\\ 
\noindent Let $[pkx]_{\indexoneout} = pkx(\tau) \cdot [1]_{\indexoneout}$, $[pky]_{\indexoneout} = pky(\tau) \cdot [1]_{\indexoneout}$.\\ 
\noindent Let $\mathit{ck} = ([pkx]_{\indexoneout}, [pky]_{\indexoneout})$.\\
\noindent Note that $\mathbb{F}$ and $\{L_i(X)\}_{i=1}^{n-2}$ are as defined in Section~\ref{sec:lagrange}. 

\item $\pi = (\pi_{SNARK}, \mathit{apk}) \leftarrow \mathit{CKS_{\mathcal{R}}.Prove}
(\mathit{rs}_{\mathit{pk}}, \mathit{ck}, (\mathit{pk_i})_{i=1}^{n-1}, (\mathit{bit_i})_{i=1}^{n-1})$ 
where $\mathit{CKS_{\mathcal{R}}.Prove}$ calls \\ 
$\mathit{apk} = \sum_{i=1}^{n-1} \mathit{bit_i} \cdot \mathit{pk_i} \leftarrow \mathit{AS.AggregateKeys}(\mathit{pp}, (\mathit{pk_i})_{i:\mathit{bit_i = 1}})$ 
as defined in Instantiation~\ref{insta:bls} and $\pi_{SNARK} \leftarrow \mathit{SNARK.Prove}(\mathit{rs_{pk}}, (x,w), \mathcal{R})$, 
for $\mathcal{R} \in \{\Rlacom, \Racom \}$ where 
\begin{equation*}
\begin{cases}
 (x = (\mathit{ck}, (\mathit{bit_i})_{i=1}^{n-1}||0, \mathit{apk}), w = ((\mathit{pk}_i)_{i=1}^{n-1}) & \text{ if } \mathcal{R} = \Rlacom,\\
 (x = (\mathit{ck}, \mathbf{b'}, \mathit{apk}), w = ((\mathit{pk}_i)_{i=1}^{n-1}, (\mathit{bit_i})_{i=1}^{n-1}||0) & \text{ if } \mathcal{R} = \Racom, \\
\end{cases}       
\end{equation*}
where $\mathbf{b'}$ is the vector of field elements formed from blocks of size $\mathsf{block}$ of bits from vector 
$(\mathit{bit_i})_{i=1}^{n-1}||0$ and $\mathsf{block}$ is the highest power of 2 smaller than the size of a field element in $\mathbb{F}$. 

\item $0/1 \leftarrow \mathit{CKS_{\mathcal{R}}.Verify}(\mathit{pp}, \mathit{rs}_{\mathit{vk}}, \mathit{ck}, m, \mathit{asig}, \pi, \mathbf{bitvector})$ 
parses $\pi$ to retrieve $\pi_{\mathit{SNARK}}$ and $\mathit{apk}$ and it calls $\mathit{AS.Verify(\mathit{pp}, \mathit{apk}, m, \mathit{asig})}$ 
as defined in Instantiation~\ref{insta:bls} and it also calls \\ $\mathit{SNARK.Verify}(\mathit{rs_{vk}}, x, \pi_{\mathit{SNARK}}, \mathcal{R})$ 
(where $\pi_{\mathit{SNARK}}$, $x$ and $\mathcal{R}$ are as defined in the paragraph above with the only difference that $(\mathit{bit_i})_{i=1}^{n-1}$ 
represents the first $n-1$ bits of $\mathbf{bitvector}$, padded with $0$s, if not sufficiently many exist in $\mathbf{bitvector}$); 
it outputs $1$ if both algorithms output $1$ and it outputs $0$ otherwise.
\end{itemize}
\end{construction}

\begin{theorem}Given the hybrid model SNARK scheme secure for relation $\mathcal{R} \in \{ \Rlacom, \Racom\}$ as 
obtained using our two-step compiler in Section~\ref{sec_two_step_compiler} and the aggregatable signature scheme $\mathit{AS}$ 
                     as per Instantiation~\ref{insta:bls} (which fulfils Definition~\ref{def:aggregate_signatures}) with the additional 
                     specification that $\mathit{aux}_{\mathit{AS}} = v+1$ and choosing $v = n-1$, 
if we assume that an efficient adversary (against the soundness of) $\mathit{CKS}_{\mathcal{R}}$ outputs public keys only from the source group $\ginn{1}$,  
then the committee key scheme $\mathit{CKS}_{\mathcal{R}}$ as per Instantiation~\ref{inst:cks} is secure with respect to Definition~\ref{def: committee_key}.
\end{theorem}
\begin{proof} We give a full proof in Section~\ref{supplementary_proof_sec_cks}. 
\end{proof}