specification.tex

% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{amsmath,amssymb}
\usepackage{lmodern}
\usepackage{iftex}
\ifPDFTeX
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  hidelinks,
  pdfcreator={LaTeX via pandoc}}
\urlstyle{same} % disable monospaced font for URLs
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\ifLuaTeX
  \usepackage{selnolig}  % disable illegal ligatures
\fi

\author{}
\date{}

\begin{document}

\hypertarget{ring-proof-specification}{%
\section{Ring Proof Specification}\label{ring-proof-specification}}

26-08-2024-draft-7

\hypertarget{abstract}{%
\subsection{\texorpdfstring{\emph{Abstract}}{Abstract}}\label{abstract}}

This document describes a cryptographic scheme based on SNARKs (Succinct
Non-Interactive Arguments of Knowledge) that enables a prover to
demonstrate knowledge of a secret scalar \(t\) and a secret index \(k\)
within a group of public keys, where each public key is a point on an
elliptic curve. The scheme ensures that, when combined with a public
elliptic curve point \(H\), the relation \(R = PK_k + t·H\) is
satisfied. It leverages elliptic curve operations, a polynomial
commitment scheme, and the Fiat-Shamir heuristic to achieve
non-interactivity and zero-knowledge properties.

\hypertarget{notation}{%
\subsection{1. Notation}\label{notation}}

\hypertarget{basics}{%
\subsubsection{1.1. Basics}\label{basics}}

\hypertarget{basic-sets}{%
\paragraph{Basic Sets}\label{basic-sets}}

\begin{itemize}
\tightlist
\item
  \(\mathbb{N}_k = \{0, \dots, k-1\}\)
\item
  \(\mathbb{B} = \mathbb{N}_2\)
\end{itemize}

\hypertarget{vectors-operations}{%
\paragraph{Vectors Operations}\label{vectors-operations}}

\begin{itemize}
\tightlist
\item
  \(\overline{x} = (x_0, \dots, x_{n-1}),\ \overline{x}_i = x_i,\ 0 \leq i < n\)
\item
  \(\overline{a} \| \overline{b} = (a_0, \ldots, a_{n-1}, b_0, \ldots, b_{m-1})\)
\item
  \(x^{\|n} = (x, \ldots, x) \in X^n\)
\end{itemize}

\hypertarget{kronecker-delta}{%
\paragraph{Kronecker Delta}\label{kronecker-delta}}

\begin{itemize}
\tightlist
\item
  \(\delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases}\)
\end{itemize}

\hypertarget{lagrange-basis-polynomials}{%
\paragraph{Lagrange Basis
Polynomials}\label{lagrange-basis-polynomials}}

\begin{itemize}
\tightlist
\item
  \(L_i = L_{\mathbb{D}, i} \in \mathbb{F}[X]^{<N},\ \ i \in \mathbb{N}_N,\ \ L_i(\omega^j) = \delta_{ij}\)
\end{itemize}

\hypertarget{curves-and-fields}{%
\subsubsection{1.2. Curves and Fields}\label{curves-and-fields}}

\begin{itemize}
\tightlist
\item
  \(\langle \omega \rangle = \mathbb{D} \subseteq \mathbb{F}^*,\ \ |\mathbb{D}| = N \in \mathbb{N}\)

  \begin{itemize}
  \tightlist
  \item
    Cyclic subgroup generated by \(\omega\) in the multiplicative group
    \(\mathbb{F}^*\).
  \end{itemize}
\end{itemize}

\hypertarget{elliptic-curves}{%
\paragraph{Elliptic Curves}\label{elliptic-curves}}

\begin{itemize}
\tightlist
\item
  \(J = J / \mathbb{F}\) -- Elliptic curve \(J\) defined over the field
  \(\mathbb{F}\).
\item
  \(\tilde{\mathbb{J}} = J(\mathbb{F})\) -- Group of
  \(\mathbb{F}\)-rational points on \(J\).
\item
  \(\mathbb{J} \subset \tilde{\mathbb{J}}\) -- Prime order subgroup of
  \(\tilde{\mathbb{J}}\).
\end{itemize}

\hypertarget{scalar-field}{%
\paragraph{Scalar Field}\label{scalar-field}}

\begin{itemize}
\tightlist
\item
  \(\mathbb{F_J}\) -- Field associated with the elliptic curve
  \(\mathbb{J}\), with \(|\mathbb{F_J}| = |\mathbb{J}|\).
\item
  \(N_J = \lceil \log_2 |\mathbb{F_J}| \rceil\) -- Number of bits to
  represent an element of \(\mathbb{F_J}\).
\item
  \(N_K = N - N_J - 4\) -- Maximum size of the ring handled with a
  domain of size \(N\).
\end{itemize}

\hypertarget{support-functions}{%
\subsubsection{1.3. Support Functions}\label{support-functions}}

\hypertarget{unzip}{%
\paragraph{Unzip}\label{unzip}}

\begin{itemize}
\tightlist
\item
  \(\text{unzip}: \mathbb{J}^k \to (\mathbb{F}^k, \mathbb{F}^k);\ \ \overline{p} \mapsto (\overline{p}_x, \overline{p}_y)\)

  \begin{itemize}
  \tightlist
  \item
    Given a vector \(\overline{p}\) of \(k\) elliptic curve points,
    \(\text{unzip}\) separates \(\overline{p}\) into two vectors:
    \(\overline{p}_x\) and \(\overline{p}_y\), containing the \(x\) and
    \(y\) coordinates of each point, respectively.
  \end{itemize}
\end{itemize}

\hypertarget{polynomial-interpolation}{%
\paragraph{Polynomial Interpolation}\label{polynomial-interpolation}}

\begin{itemize}
\tightlist
\item
  \(\text{Interpolate}: \mathbb{F}^k \to \mathbb{F}[x]^{< k};\ \ \overline{x} \mapsto f\)

  \begin{itemize}
  \tightlist
  \item
    Construct a polynomial by interpolating the vector values over
    \(\mathbb{D}\)
  \end{itemize}
\end{itemize}

\hypertarget{polynomial-commitment-scheme}{%
\paragraph{Polynomial Commitment
Scheme}\label{polynomial-commitment-scheme}}

\begin{itemize}
\tightlist
\item
  \(\text{PCS.Commit}: \mathbb{F}[x] \to \mathbb{G};\ \ f \mapsto C_f\)

  \begin{itemize}
  \tightlist
  \item
    Commits to a polynomial \(f\) over \(\mathbb{F}\), with commitment
    in group \(\mathbb{G}\).
  \end{itemize}
\item
  \(\text{PCS.Open}: (\mathbb{G}, \mathbb{F}) \to (\mathbb{F}, \Pi);\ \ (C_f, x) \mapsto (y,\pi)\)

  \begin{itemize}
  \tightlist
  \item
    Evaluates the committed polynomial \(f\) at point \(x\), returning
    evaluation \(y\) and proof \(\pi\). The proof domain \(\Pi\) depends
    on the PCS.
  \end{itemize}
\item
  \(\text{PCS.Verify}: (\mathbb{G}, \mathbb{F}, \mathbb{F}, \Pi) \to \mathbb{B};\ \ (C_f,x,y ,\pi) \mapsto (0|1)\)

  \begin{itemize}
  \tightlist
  \item
    Verifies whether \(y = f(x)\) given the commitment \(C_f\) and proof
    \(\pi\).
  \end{itemize}
\end{itemize}

\hypertarget{fiat-shamir-transform}{%
\paragraph{Fiat-Shamir Transform}\label{fiat-shamir-transform}}

\begin{itemize}
\tightlist
\item
  \(\text{FS}: \mathbb{S} \to \mathbb{F};\ \textbf{s} \mapsto x\)

  \begin{itemize}
  \tightlist
  \item
    Maps a serializable object \(\textbf{s} \in \mathbb{S}\) to
    \(\mathbb{F}\), typically via some cryptographically secure hash
    function.
  \end{itemize}
\end{itemize}

\begin{center}\rule{0.5\linewidth}{0.5pt}\end{center}

\hypertarget{parameters}{%
\subsection{2. Parameters}\label{parameters}}

\hypertarget{scheme-specific}{%
\subsubsection{2.1. Scheme Specific}\label{scheme-specific}}

\begin{itemize}
\tightlist
\item
  \(\square \in \mathbb{J}\) -- Padding element, a point on
  \(\mathbb{J}\) with unknown discrete logarithm.
\item
  \(H \in \mathbb{J}\) -- Pedersen blinding base point.
\item
  \(\overline{H} = (H, 2H, 4H, \ldots, 2^{N_{J-1}}H) \in \mathbb{J}^{N_J}\)
  -- Vector of scaled multiples of \(H\).
\item
  \(S \in \tilde{\mathbb{J}} \setminus \mathbb{J}\) -- Point in
  \(\tilde{\mathbb{J}}\) used as seed for accumulation, ensuring the
  result is never the identity.
\end{itemize}

\hypertarget{public-data}{%
\subsubsection{2.2. Public Data}\label{public-data}}

\begin{itemize}
\tightlist
\item
  \(\overline{PK} \in \mathbb{J}^{N_K}\) -- Vector of public keys in the
  ring, padded with \(\square\) to length \(N_K\) if needed.
\end{itemize}

\hypertarget{witness-data}{%
\subsubsection{2.3. Witness Data}\label{witness-data}}

\begin{itemize}
\tightlist
\item
  \(t \in \mathbb{F_J}\) -- Prover's one-time secret.
\item
  \(k \in \mathbb{N}_{N_K}\) -- Prover's index within the ring,
  identifying which public key in \(\overline{PK}\) belongs to the
  prover.
\end{itemize}

\hypertarget{preprocessing}{%
\subsubsection{2.4. Preprocessing}\label{preprocessing}}

\hypertarget{public-input-preprocessing}{%
\paragraph{2.4.1. Public Input
Preprocessing}\label{public-input-preprocessing}}

Concatenate ring points with scaled multiples of \(H\):
\[\overline{P} = \overline{PK} \| \overline{H} = (P_0, \ldots, P_{N-5}) \in \mathbb{J}^{N-4}\]
\[\overline{p}_x = (P_{x,0}, \ldots, P_{x,N-5}, 0, 0, 0, 0) \in \mathbb{F}^N\]
\[\overline{p}_y = (P_{y,0}, \ldots, P_{y,N-5}, 0, 0, 0, 0) \in \mathbb{F}^N\]

Ring items selector:
\[\overline{s} = 1^{\|N_K}\ \|\ 0^{\|N-N_K} \in \mathbb{F}^N\]

\hypertarget{interpolation}{%
\paragraph{2.4.1 Interpolation}\label{interpolation}}

The resulting vectors are interpolated over \(\mathbb{D}\):
\[p_x = \text{Interpolate}(\overline{p}_x)\]
\[p_y = \text{Interpolate}(\overline{p}_y)\]
\[s = \text{Interpolate}(\overline{s})\]

\hypertarget{commit-to-the-constructed-vectors}{%
\paragraph{2.4.2. Commit to the constructed
vectors}\label{commit-to-the-constructed-vectors}}

\[C_{p_x} = \text{PCS.Commit}(p_x)\]
\[C_{p_y} = \text{PCS.Commit}(p_y)\] \[C_s = \text{PCS.Commit}(s)\]

\hypertarget{relation-to-prove}{%
\subsubsection{2.5. Relation to Prove}\label{relation-to-prove}}

Knowledge of \(k\) and \(t\) such that \(R = PK_k + tH\).
\[\mathfrak{R}_H = \{ (R, \overline{PK}; k, t) \mid R = PK_k + tH \,;\, R \in \mathbb{J}, \, \overline{PK} \in \mathbb{J}^{N_K}, \, k \in \mathbb{N}_{N_K}, \, t \in \mathbb{F_J} \}\]

\begin{center}\rule{0.5\linewidth}{0.5pt}\end{center}

\hypertarget{prover}{%
\subsection{3. Prover}\label{prover}}

\hypertarget{witness-polynomials}{%
\subsubsection{3.1. Witness Polynomials}\label{witness-polynomials}}

\hypertarget{bits-vector}{%
\paragraph{3.1.1. Bits Vector}\label{bits-vector}}

\begin{itemize}
\item
  \(\overline{k} \in \mathbb{B}^{N_K}\) -- Binary vector representing
  the index \(k\) in the ring. \(\overline{k}\) has \(N_K\) elements
  where \(k_i = \delta_{ik}\)
\item
  \(\overline{t} \in \mathbb{B}^{N_J}\) -- Binary representation of the
  secret scalar \(t\), with \(t_i\) representing the \(i\)-th bit of
  \(t\) in little-endian order, i.e., \(t = \sum t_i 2^i\), for
  \(i \in \mathbb{N}_{N_J}\)
\end{itemize}

The bits vector \(\overline{b}\) is constructed by concatenating
\(\overline{k}\) and \(\overline{t}\), followed by a single 0.

\[\overline{b} = \overline{k} \| \overline{t} \| (0)\]

\hypertarget{conditional-sum-accumulator-vectors}{%
\paragraph{3.1.2. Conditional Sum Accumulator
Vectors}\label{conditional-sum-accumulator-vectors}}

\[
ACC_0 = S, \quad ACC_i = ACC_{i-1} + b_{i-1}P_{i-1}, \quad i = 1, \ldots, N-4
\]

\begin{itemize}
\tightlist
\item
  The accumulator is initialized with the seed point \(S\).
\item
  The accumulator is updated at each index \(i\) based on the previous
  value and the product of \(b_{i-1}\) and \(P_{i-1}\).
\end{itemize}

The resulting accumulator points are finally separated into \(x\) and
\(y\) coordinates: \[
(\overline{acc}_x, \overline{acc}_y) = \text{unzip}(\overline{ACC})
\]

\hypertarget{inner-product-accumulator-vector}{%
\paragraph{3.1.3. Inner Product Accumulator
Vector}\label{inner-product-accumulator-vector}}

\[
acc_{ip_0} = 0, \quad acc_{ip_i} = acc_{ip_{i-1}} + b_{i-1}s_{i-1}, \quad i = 1, \ldots, N-4
\]

\begin{itemize}
\tightlist
\item
  The accumulator is initialized with \(0\).
\item
  The accumulator is updated at each index \(i\) based on the previous
  value and the product of \(b_{i-1}\) and \(s_{i-1}\)
\end{itemize}

\hypertarget{interpolation-and-commitments}{%
\paragraph{3.1.4. Interpolation and
Commitments}\label{interpolation-and-commitments}}

The resulting vectors are interpolated over \(\mathbb{D}\) with random
values \(\{r_i\}\) appended as padding for the final entries. This
padding helps obscure the resulting polynomial, even when committing to
identical witness values.
\[b = \text{Interpolate}(\overline{b} \| (r_1, r_2, r_3))\]
\[acc_x = \text{Interpolate}(\overline{acc}_x \| (r_4, r_5, r_6))\]
\[acc_y = \text{Interpolate}(\overline{acc}_y \| (r_7, r_8, r_9))\]
\[acc_{ip} = \text{Interpolate}(\overline{acc}_{ip} \| (r_{10}, r_{11}, r_{12}))\]

Commit to the witness derived polynomials:
\[C_b = \text{PCS.Commit}(b)\]
\[C_{acc_{ip}} = \text{PCS.Commit}(acc_{ip})\]
\[C_{acc_x} = \text{PCS.Commit}(acc_x)\]
\[C_{acc_y} = \text{PCS.Commit}(acc_y)\]

\hypertarget{constraints}{%
\subsubsection{3.2. Constraints}\label{constraints}}

Constraints are polynomials constructed to evaluate to zero when
satisfied; a non-zero evaluation indicates a violation.

Note. When evaluating a polynomial \(f\) at
\(x = \omega^k \in \mathbb{D}\) for some \(k \in \mathbb{N}\),
\(f(\omega x)\) gives the value of the polynomial at the next position
in the evaluation domain (\(\omega x = \omega^{k+1}\)).

\hypertarget{inner-product}{%
\paragraph{3.2.1. Inner Product}\label{inner-product}}

\[
c_1(x) = \bigl(acc_{ip}(\omega x) - acc_{ip}(x) - b(x)s(x)\bigr)(x - \omega^{N-4})
\]

This constraint ensures the inner product accumulator \(acc_{ip}(x)\) is
correctly updated, satisfying
\(acc_{ip}(\omega x) = acc_{ip}(x) + b(x)s(x)\).

The factor \((x - \omega^{N-4})\) ensures the constraint holds at all
points including \(x = \omega^{N-4}\), where \(c_1(x)\) automatically
vanishes.

\hypertarget{conditional-addition}{%
\paragraph{3.2.2. Conditional Addition}\label{conditional-addition}}

\[\begin{aligned}
c_2(x) = & \biggl( b(x) \Bigl( \bigl(acc_x(x) - p_x(x)\bigr)^2 \bigl(acc_x(x) + p_x(x) + acc_x(\omega x)\bigr) \\
         & \quad - \bigl(p_y(x) - acc_y(x)\bigr)^2 \Bigr) \\
         & + \bigl(1 - b(x)\bigr) \bigl(acc_x(\omega x) - acc_x(x)\bigr) \biggr) \times (x - \omega^{N-4}) \\
\end{aligned}\] \[\begin{aligned}
c_3(x) = & \biggl( b(x) \Bigl( \bigl(acc_x(x) - p_x(x)\bigr)\bigl(acc_y(\omega x) + acc_y(x)\bigr) \\
         & \quad - \bigl(p_y(x) - acc_y(x)\bigr)\bigl(acc_x(\omega x) - acc_x(x)\bigr) \Bigr) \\
         & + \bigl(1 - b(x)\bigr) \bigl(acc_x(\omega x) - acc_x(x)\bigr) \biggr) \times (x - \omega^{N-4})
\end{aligned}\]

These constraints enforce correct elliptic curve addition for the \(x\)
and \(y\) components, respectively, controlled by the Boolean variable
\(b(x)\):

\begin{itemize}
\tightlist
\item
  \textbf{When} \(b(x) = 1\): \(c_2(x)\) and \(c_3(x)\) enforce the
  correct elliptic curve addition for the \(x\) and \(y\) components,
  respectively.
\item
  \textbf{When} \(b(x) = 0\): both constraints ensure the accumulator
  remains unchanged.
\end{itemize}

The factor \((x - \omega^{N-4})\) nullifies the constraint at
\(x = \omega^{N-4}\), where it does not apply.

\hypertarget{booleanity}{%
\paragraph{3.2.3. Booleanity}\label{booleanity}}

\[c_3(x) = b(x)\bigl(1 - b(x)\bigr)\]

Ensures that the polynomial \(b(x)\) acts as a Boolean variable, taking
only values 0 or 1.

\begin{itemize}
\tightlist
\item
  \textbf{If} \(b(x) = 0\) or \(b(x) = 1\), then \(c_3(x) = 0\).
\item
  \textbf{If} \(b(x)\) takes any value other than 0 or 1, \(c_3(x)\)
  will be non-zero, violating the constraint.
\end{itemize}

\hypertarget{conditional-addition-boundary}{%
\paragraph{3.2.4. Conditional Addition
Boundary}\label{conditional-addition-boundary}}

Given the seed point \(S = (s_x, s_y)\) and the expected result delta
from the seed point \(R = (r_x, r_y)\), the constraints are:
\[c_5(x) = \bigl(acc_x(x) - s_x\bigr)L_0(x) + \bigl(acc_x(x) - r_x - s_x\bigr)L_{N-4}(x)\]
\[c_6(x) = \bigl(acc_y(x) - s_y\bigr)L_0(x) + \bigl(acc_y(x) - r_y - s_y\bigr)L_{N-4}(x)\]

These constraints ensure the accumulator components take specific values
at the conditional addition boundaries:

\begin{itemize}
\tightlist
\item
  \textbf{At} \(x = \omega^0\): \(L_0(x) = 1\) and \(L_{N-4}(x) = 0\),
  enforcing \(acc_x(\omega^0) = s_x\) and \(acc_y(\omega^0) = s_y\).
\item
  \textbf{At} \(x = \omega^{N-4}\): \(L_0(x) = 0\) and
  \(L_{N-4}(x) = 1\), enforcing \(acc_x(\omega^{N-4}) = r_x + s_x\) and
  \(acc_y(\omega^{N-4}) = r_y + s_y\).
\end{itemize}

\hypertarget{inner-product-boundary}{%
\paragraph{3.2.5. Inner Product Boundary}\label{inner-product-boundary}}

\[c_7(x) = acc_{ip}(x)L_0(x) + \bigl(acc_{ip}(x) - 1\bigr)L_{N-4}(x)\]

This constraint ensure the accumulator components take specific values
at the conditional addition boundaries:

\begin{itemize}
\tightlist
\item
  \textbf{At} \(x = \omega^0\): \(L_0(x) = 1\) and \(L_{N-4}(x) = 0\),
  enforcing \(acc_{ip}(\omega^0) = 0\).
\item
  \textbf{At} \(x = \omega^{N-4}\): \(L_0(x) = 0\) and
  \(L_{N-4}(x) = 1\), enforcing \(acc_{ip}(\omega^{N-4}) =1\).
\end{itemize}

\hypertarget{constraints-aggregation}{%
\subsubsection{3.3. Constraints
Aggregation}\label{constraints-aggregation}}

\hypertarget{aggregation-polynomial}{%
\paragraph{3.3.1. Aggregation Polynomial}\label{aggregation-polynomial}}

The protocol aggregates all constraints into a single polynomial for
efficiency.

Using the Fiat-Shamir heuristic, sample the aggregation coefficients:
\[\{\alpha_i\}_{i=1}^7 \leftarrow \text{FS}(C_b, C_{acc_{ip}}, C_{acc_x}, C_{acc_y})\]

Construct the aggregated polynomial:
\[c(x) = \left(\sum_{i=1}^7 \alpha_i c_i(x)\right) \cdot \prod_{k=1}^3 \left(x - \omega^{N-k}\right)\]

The factor \(\prod_{k=1}^3 \left(x - \omega^{N-k}\right)\) ensures that
\(c(x)\) vanishes at the last three points of the domain, thereby
enforcing the constraints across the entire evaluation domain, including
the last three points where random evaluation values were used during
the witness polynomials interpolation phase.

\hypertarget{quotient-polynomial}{%
\paragraph{3.3.2. Quotient Polynomial}\label{quotient-polynomial}}

The quotient polynomial is computed as: \[q(x) = \frac{c(x)}{x^N - 1}\]

Dividing by \(X^N - 1\) ensures that the aggregated constraints encoded
in \(c(x)\) are enforced consistently across the entire evaluation
domain \(\mathbb{D}\) while reducing the degree of the polynomial.

\hypertarget{quotient-polynomial-commitment-and-challenge}{%
\paragraph{3.3.3. Quotient Polynomial Commitment and
Challenge}\label{quotient-polynomial-commitment-and-challenge}}

The prover commits to the quotient polynomial \(q\):
\[C_q = \text{PCS.Commit}(q)\]

The prover receives the evaluation point \(\zeta\) in response:
\[\zeta \leftarrow \text{FS}(C_q)\]

\hypertarget{relevant-polynomials-evaluation}{%
\paragraph{3.3.4. Relevant Polynomials
Evaluation}\label{relevant-polynomials-evaluation}}

Evaluate the relevant polynomials at the sampled evaluation point
\(\zeta\): \[p_{x,\zeta} = p_x(\zeta)\] \[p_{y,\zeta} = p_y(\zeta)\]
\[s_\zeta = s(\zeta)\] \[b_\zeta = b(\zeta)\]
\[acc_{ip,\zeta} = acc_{ip}(\zeta)\] \[acc_{x,\zeta} = acc_x(\zeta)\]
\[acc_{y,\zeta} = acc_y(\zeta)\]

\hypertarget{linearization-polynomial}{%
\paragraph{3.3.5. Linearization
Polynomial}\label{linearization-polynomial}}

The linearization polynomials are constructed to enable the verifier to
evaluate certain parts of the constraint polynomials at \(\zeta \omega\)
while independently reconstructing the evaluation of \(q\) at \(\zeta\)
using the ``relevant polynomial evaluations'' provided by the prover as
part of the proof.

In particular we require these contributions just for the accumulators
contraints.

Accumulator inner product (\(c_1\)) contribution:
\[l_1(x)=(\zeta - \omega^{N-4})acc_{ip}(x)\]

Conditional addition accumulators (\(c_{2,3}\)) contributions:
\[l_2(x)=(\zeta-\omega^{N-4})\bigl(b_\zeta(acc_{x,\zeta}-p_{x,\zeta})^2acc_x(x)+(1-b_\zeta)acc_y(x)\bigr)\]
\[l_3(x)=(\zeta-\omega^{N-4})\Bigl(\bigl(b_\zeta(acc_{y,\zeta}-p_{y,\zeta})+1-b_\zeta\bigr)acc_x(x)+b_\zeta(acc_{x,\zeta}-p_{x,\zeta})acc_y(x)\Bigr)\]

Linearized constraints are aggregated using \(\{\alpha_i\}\)
coefficients and evaluated at \(\zeta \omega\):
\[l(x)=\sum_{i=1}^3\alpha_i l_i(x)\] \[l_{\zeta\omega}=l(\zeta\omega)\]

\hypertarget{sample-aggregation-coefficients}{%
\paragraph{3.3.6. Sample Aggregation
Coefficients}\label{sample-aggregation-coefficients}}

Sample the aggregation coefficients \(\{\nu_i\}\) using the Fiat-Shamir
heuristic and compute the aggregate polynomial \(agg\):
\[\{\nu_i\}_{i=1}^8 \leftarrow \text{FS}(p_{x,\zeta}, p_{y,\zeta}, s_\zeta, b_\zeta, acc_{ip,\zeta}, acc_{x,\zeta}, acc_{y,\zeta}, l_{\zeta\omega})\]

Construct the aggregate polynomial:
\[agg(x)=\nu_1p_x(x)+\nu_2p_y(x)+\nu_3s(x)+\nu_4b(x)+\nu_5acc_{ip}(x)+\nu_6acc_x(x)+\nu_7acc_y(x)+\nu_8q(x)\]

\hypertarget{proof-construction}{%
\paragraph{3.3.7. Proof Construction}\label{proof-construction}}

Open the aggregate polynomial \(agg\) at \(\zeta\) and the linearization
polynomial \(l\) at \(\zeta\omega\):
\[\Pi_\zeta = \text{PCS.Open}(agg,\zeta)\]
\[\Pi_{\zeta\omega} = \text{PCS.Open}(l,\zeta\omega)\]

Construct the proof as follows:
\[\Pi=(C_b,C_{acc_{ip}},C_{acc_x},C_{acc_y},p_{x,\zeta},p_{y,\zeta},s_\zeta,b_\zeta,acc_{ip,\zeta},acc_{x,\zeta},acc_{y,\zeta},C_q,l_{\zeta\omega},\Pi_\zeta,\Pi_{\zeta\omega})\]

\begin{center}\rule{0.5\linewidth}{0.5pt}\end{center}

\hypertarget{verifier}{%
\subsection{4. Verifier}\label{verifier}}

\hypertarget{inputs}{%
\subsubsection{4.1. Inputs}\label{inputs}}

Commitments to the ring public keys and the selector, prepared during
the pre-processing phase: \[(C_{p_x}, C_{p_y}, C_s)\]

The claimed accumulation result, allegedly \(PK_k + tH\) for some \(k\)
and \(t\) known to the prover. This is the primary element to be
assessed: \[R = (r_x, r_y)\]

Proof which contains all the necessary commitments, evaluations, and
openings needed for the verifier to perform the validation checks: \[
\Pi = (C_b, C_{acc_{ip}}, C_{acc_x}, C_{acc_y}, p_{x,\zeta}, p_{y,\zeta}, s_\zeta, b_\zeta, ip_{\zeta}, ac_{x,\zeta}, ac_{y,\zeta}, C_q, l_{\zeta\omega}, \Pi_\zeta, \Pi_{\zeta\omega})
\]

\hypertarget{verification}{%
\subsubsection{4.2. Verification}\label{verification}}

\hypertarget{fiat-shamir-challenges}{%
\paragraph{4.2.1. Fiat-Shamir Challenges}\label{fiat-shamir-challenges}}

Recovery of aggregation coefficients and evaluation point:
\[\{\alpha_i\}_{i=1}^7 \leftarrow \text{FS}(C_b, C_{ip}, C_{acc_x}, C_{acc_y})\]
\[\zeta \leftarrow \text{FS}(C_q)\]
\[\{\nu_i\}_{i=1}^8 \leftarrow \text{FS}(p_{x,\zeta}, p_{y,\zeta}, s_\zeta, b_\zeta, acc_{ip,\zeta}, acc_{x,\zeta}, acc_{y,\zeta}, l_{\zeta\omega})\]

\hypertarget{contributions-to-the-constraints-evaluated-at-zeta}{%
\paragraph{\texorpdfstring{4.2.2. Contributions to the Constraints
Evaluated at
\(\zeta\)}{4.2.2. Contributions to the Constraints Evaluated at \textbackslash zeta}}\label{contributions-to-the-constraints-evaluated-at-zeta}}

The following expressions represent the contributions to the constraint
polynomials evaluated at the point \(\zeta\):
\[\tilde{c}_{1,\zeta}=-(acc_{ip,\zeta}+b_\zeta s_\zeta)(\zeta-\omega^{N-4})\]
\[\tilde{c}_{2,\zeta}=\left\{b_\zeta\left[(acc_{x,\zeta}-p_{x,\zeta})^2(acc_{x,\zeta}+p_{x,\zeta})-(p_{y,\zeta}-acc_{y,\zeta})^2\right]-(1-b_\zeta)acc_{y,\zeta}\right\}(\zeta-\omega^{N-4})\]
\[\tilde{c}_{3,\zeta}=\left\{b_\zeta\left[(acc_{x,\zeta}-p_{x,\zeta})acc_{y,\zeta}+(p_{y,\zeta}-acc_{y,\zeta})acc_{x,\zeta}\right]-(1-b_\zeta)acc_{x,\zeta}\right\}(\zeta-\omega^{N-4})\]
\[c_4=b_{\zeta}(1-b_{\zeta})\]
\[c_5=(acc_{x,\zeta}-s_x)L_0(\zeta)+(acc_{x,\zeta}-r_x-s_x)L_{N-4}(\zeta)\]
\[c_6=(acc_{y,\zeta}-s_y)L_0(\zeta)+(acc_{y,\zeta}-r_y-s_y)L_{N-4}(\zeta)\]
\[c_7=acc_{ip,\zeta}L_0(\zeta)+(acc_{ip,\zeta}-1)L_{N-4}(\zeta)\]

\textbf{Note:} The tilde ( \(\tilde{}\) ) above the first three
polynomials indicates that these are only partial contributions,
representing the components evaluated at \(\zeta\). The components
evaluated at \(\zeta \omega\) are added later by the linearization
aggregated polynomial found within the proof (\(l_{\zeta\omega}\)).

\hypertarget{evaluation-of-the-quotient-polynomial-at-zeta}{%
\paragraph{\texorpdfstring{4.2.3. Evaluation of the Quotient Polynomial
at
\(\zeta\)}{4.2.3. Evaluation of the Quotient Polynomial at \textbackslash zeta}}\label{evaluation-of-the-quotient-polynomial-at-zeta}}

Aggregate the contributions along with the linearization polynomial
evaluated at \(\zeta \omega\) to compute the evaluation of the quotient
polynomial at \(\zeta\):
\[q_{\zeta}=\frac{(\sum_{i=1}^7\alpha_ic_i+l_{\zeta\omega})\prod_{k=1}^3(\zeta-\omega^{N-k})}{\zeta^N-1}\]

Compute the aggregate commitment \(C_{agg}\) using the aggregation
coefficients \(\nu_i\):
\[C_{agg} = \nu_1 C_{p_x} + \nu_2 C_{p_y} + \nu_3 C_s + \nu_4 C_b + \nu_5 C_{acc_{ip}} + \nu_6 C_{acc_x} + \nu_7 C_{acc_y} + \nu_8 C_q\]

Compute the aggregate evaluation \(agg_\zeta\) using the same
coefficients:
\[agg_\zeta = \nu_1 p_{x,\zeta} + \nu_2 p_{y,\zeta} + \nu_3 s_\zeta + \nu_4 b_\zeta + \nu_5 acc_{ip,\zeta} + \nu_6 acc_{x,\zeta} + \nu_7 acc_{y,\zeta} + \nu_8 q_\zeta\]

Verify the aggregate polynomial opening at \(\zeta\) using
\(\Pi_\zeta\):
\[\text{PCS.Verify}(C_{agg}, \zeta, agg_\zeta, \Pi_\zeta)\]

\hypertarget{evaluation-of-the-linearization-polynomial-at-zeta-omega}{%
\paragraph{\texorpdfstring{4.2.4. Evaluation of the Linearization
Polynomial at
\(\zeta \omega\)}{4.2.4. Evaluation of the Linearization Polynomial at \textbackslash zeta \textbackslash omega}}\label{evaluation-of-the-linearization-polynomial-at-zeta-omega}}

Compute the individual linearization polynomial commitments:
\[C_{l_1}=(\zeta-\omega^{N-4})C_{acc_{ip}}\]
\[C_{l_2}=(\zeta-\omega^{N-4})\left(b_\zeta(acc_{x,\zeta}-p_{x,\zeta})^2C_{acc_x}+(1-b_\zeta)C_{acc_y}\right)\]
\[C_{l_3}=(\zeta-\omega^{N-4})\left(\left(b_\zeta(acc_{y,\zeta}-p_{y,\zeta})+1-b_\zeta\right)C_{acc_x}+b_\zeta(acc_{x,\zeta}-p_{x,\zeta}) C_{acc_y}\right)\]

Aggregate the linearization polynomial commitments using
\(\{\alpha_i\}\) coefficients. \[C_l=\sum_{i=1}^3\alpha_iC_{l_i}\]

Verify the aggregate linearization polynomial opening at
\(\zeta \omega\) using \(\Pi_{\zeta\omega}\):
\[\text{PCS.Verify}(C_{l},\zeta\omega,l_{\zeta\omega},\Pi_{\zeta\omega})\]

\hypertarget{acknowledgements}{%
\subsection{5. Acknowledgements}\label{acknowledgements}}

This specification is primarily derived from Sergey Vasilyev's original
writeup and reference implementation, as cited in the references.

\hypertarget{references}{%
\subsection{6. References}\label{references}}

\begin{itemize}
\tightlist
\item
  These notes on hackmd: \texttt{https://hackmd.io/@davxy/r1SVPqQc0}.
\item
  Sergey Vasilyev original writeup:
  \texttt{https://hackmd.io/ulW5nFFpTwClHsD0kusJAA}
\item
  W3F reference implementation:
  \texttt{https://github.com/w3f/ring-proof}
\end{itemize}

\end{document}