Ring Proof Specification

22-08-2024-draft-6

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=P{K}_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.

1. Notation

1.1. Basics

Basic Sets

• ${\mathbb{N}}_k=\{0,\dots ,k-1\}$
• $\mathbb{B}={\mathbb{N}}_2$

Vectors Operations

• $\bar{x}=(x_0,\dots ,x_{n-1}),{\bar{x}}_i=x_i,0\le i<n$
• $\bar{a}\Vert \bar{b}=(a_0,\dots ,a_{n-1},b_0,\dots ,b_{m-1})$
• $x^{\Vert n}=(x,\dots ,x)\in X^n$

Kronecker Delta

• ${\delta }_{ij}=\{\begin{array}{ll}1& i=j\\ 0& i\ne j\end{array}$

Lagrange Basis Polynomials

• $L_i=L_{\mathbb{D},i}\in \mathbb{F}[X{]}^{<N},i\in {\mathbb{N}}_N,L_i({\omega }^j)={\delta }_{ij}$

1.2. Curves and Fields

• $⟨\omega ⟩=\mathbb{D}\subseteq {\mathbb{F}}^{\ast },|\mathbb{D}|=N\in \mathbb{N}$
  • Cyclic subgroup generated by
    $\omega$ in the multiplicative group
    ${\mathbb{F}}^{\ast }$.

Elliptic Curves

• $J=J/\mathbb{F}$ – Elliptic curve
  $J$ defined over the field
  $\mathbb{F}$.
• $\tilde{\mathbb{J}}=J(\mathbb{F})$ – Group of
  $\mathbb{F}$-rational points on
  $J$.
• $\mathbb{J}\subset \tilde{\mathbb{J}}$ – Prime order subgroup of
  $\tilde{\mathbb{J}}$.

Scalar Field

• ${\mathbb{F}}_{\mathbb{J}}$ – Field associated with the elliptic curve
  $\mathbb{J}$, with
  $|{\mathbb{F}}_{\mathbb{J}}|=|\mathbb{J}|$.
• $N_J=\lceil {\log }_2|{\mathbb{F}}_{\mathbb{J}}|\rceil$ – Number of bits to represent an element of
  ${\mathbb{F}}_{\mathbb{J}}$.
• $N_K=N-N_J-4$ – Maximum size of the ring handled with a domain of size
  $N$.

1.3. Support Functions

Unzip

• $\text{unzip}:{\mathbb{J}}^k\to ({\mathbb{F}}^k,{\mathbb{F}}^k);\bar{p}\to ({\bar{p}}_x,{\bar{p}}_y)$
  • Given a vector
    $\bar{p}$ of
    $k$ elliptic curve points,
    $\text{unzip}$ separates
    $\bar{p}$ into two vectors:
    ${\bar{p}}_x$ and
    ${\bar{p}}_y$, containing the
    $x$ and
    $y$ coordinates of each point, respectively.

Polynomial Interpolation

• $\text{Interpolate}:{\mathbb{F}}^k\to \mathbb{F}[x{]}^{<k};\bar{x}\to f$
  • Construct a polynomial by interpolating the vector values over
    $\mathbb{D}$

Polynomial Commitment Scheme

• $\text{PCS.Commit}:\mathbb{F}[x]\to \mathbb{G};f\to C_f$
  • Commits to a polynomial
    $f$ over
    $\mathbb{F}$, with commitment in group
    $\mathbb{G}$.

• $\text{PCS.Open}:(\mathbb{G},\mathbb{F})\to (\mathbb{F},\mathrm{\Pi });(C_f,x)\to (y,\pi )$
  • Evaluates the committed polynomial
    $f$ at point
    $x$, returning evaluation
    $y$ and proof
    $\pi$. The proof domain
    $\mathrm{\Pi }$ depends on the PCS.

• $\text{PCS.Verify}:(\mathbb{G},\mathbb{F},\mathbb{F},\mathrm{\Pi })\to \mathbb{B};(C_f,x,y,\pi )\to (0|1)$
  • Verifies whether
    $y=f(x)$ given the commitment
    $C_f$ and proof
    $\pi$.

Fiat-Shamir Transform

• $\text{FS}:\mathbb{S}\to \mathbb{F};\mathbf{\text{s}}\to x$
  • Maps a serializable object
    $\mathbf{\text{s}}\in \mathbb{S}$ to
    $\mathbb{F}$, typically via some cryptographically secure hash function.

---

2. Parameters

2.1. Scheme Specific

• $◻\in \mathbb{J}$ – Padding element, a point on
  $\mathbb{J}$ with unknown discrete logarithm.
• $H\in \mathbb{J}$ – Pedersen blinding base point.
• $\bar{H}=(H,2H,4H,\dots ,2^{N_{J-1}}H)\in {\mathbb{J}}^{N_J}$ – Vector of scaled multiples of
  $H$.
• $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.

2.2. Public Data

• $\overline{PK}\in {\mathbb{J}}^{N_K}$ – Vector of public keys in the ring, padded with
  $◻$ to length
  $N_K$ if needed.

2.3. Witness Data

• $t\in {\mathbb{F}}_{\mathbb{J}}$ – Prover's one-time secret.
• $k\in {\mathbb{N}}_{N_K}$ – Prover's index within the ring, identifying which public key in
  $\overline{PK}$ belongs to the prover.

2.4. Preprocessing

2.4.1. Public Input Preprocessing

Concatenate ring points with scaled multiples of

$H$:

$$\bar{P}=\overline{PK}\Vert \bar{H}=(P_0,\dots ,P_{N-5})\in {\mathbb{J}}^{N-4}$$

$${\bar{p}}_x=(P_{x,0},\dots ,P_{x,N-5},0,0,0,0)\in {\mathbb{F}}^N$$

$${\bar{p}}_y=(P_{y,0},\dots ,P_{y,N-5},0,0,0,0)\in {\mathbb{F}}^N$$

Ring items selector:

$$\bar{s}=1^{\Vert N_K}\Vert 0^{\Vert N-N_K}\in {\mathbb{F}}^N$$

2.4.1 Interpolation

The resulting vectors are interpolated over

$\mathbb{D}$:

$$p_x=\text{Interpolate}({\bar{p}}_x)$$

$$p_y=\text{Interpolate}({\bar{p}}_y)$$

$$s=\text{Interpolate}(\bar{s})$$

2.4.2. 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)$$

2.5. Relation to Prove

Knowledge of

$k$ and

$t$ such that

$R=P{K}_k+tH$.

$${\mathfrak{R}}_H=\{(R,\overline{PK};k,t)\mid R=P{K}_k+tH;R\in \mathbb{J},\overline{PK}\in {\mathbb{J}}^{N_K},k\in {\mathbb{N}}_{N_K},t\in {\mathbb{F}}_{\mathbb{J}}\}$$

---

3. Prover

3.1. Witness Polynomials

3.1.1. Bits Vector

• $\bar{k}\in {\mathbb{B}}^{N_K}$ – Binary vector representing the index
  $k$ in the ring.
  $\bar{k}$ has
  $N_K$ elements where
  $k_i={\delta }_{ik}$

• $\bar{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}$

The bits vector

$\bar{b}$ is constructed by concatenating

$\bar{k}$ and

$\bar{t}$, followed by a single 0.

$$\bar{b}=\bar{k}\Vert \bar{t}\Vert (0)$$

3.1.2. Conditional Sum Accumulator Vectors

$$AC{C}_0=S,AC{C}_i=AC{C}_{i-1}+b_{i-1}{P}_{i-1},i=1,\dots ,N-4$$

• The accumulator is initialized with the seed point
  $S$.
• The accumulator is updated at each index
  $i$ based on the previous value and the product of
  $b_{i-1}$ and
  $P_{i-1}$.

The resulting accumulator points are finally separated into

$x$ and

$y$ coordinates:

$$({\overline{acc}}_x,{\overline{acc}}_y)=\text{unzip}(\overline{ACC})$$

3.1.3. Inner Product Accumulator Vector

$$ac{c}_{i{p}_0}=0,ac{c}_{i{p}_i}=ac{c}_{i{p}_{i-1}}+b_{i-1}{s}_{i-1},i=1,\dots ,N-4$$

• The accumulator is initialized with
  $0$.
• The accumulator is updated at each index
  $i$ based on the previous value and the product of
  $b_{i-1}$ and
  $s_{i-1}$

3.1.4. 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}(\bar{b}\Vert (r_1,r_2,r_3))$$

$$ac{c}_x=\text{Interpolate}({\overline{acc}}_x\Vert (r_4,r_5,r_6))$$

$$ac{c}_y=\text{Interpolate}({\overline{acc}}_y\Vert (r_7,r_8,r_9))$$

$$ac{c}_{ip}=\text{Interpolate}({\overline{acc}}_{ip}\Vert (r_{10},r_{11},r_{12}))$$

Commit to the witness derived polynomials:

$$C_b=\text{PCS.Commit}(b)$$

$$C_{ac{c}_{ip}}=\text{PCS.Commit}(ac{c}_{ip})$$

$$C_{ac{c}_x}=\text{PCS.Commit}(ac{c}_x)$$

$$C_{ac{c}_y}=\text{PCS.Commit}(ac{c}_y)$$

3.2. 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}$).

3.2.1. Inner Product

$$c_1(x)=(ac{c}_{ip}(\omega x)-ac{c}_{ip}(x)-b(x)s(x))(x-{\omega }^{N-4})$$

This constraint ensures the inner product accumulator

$ac{c}_{ip}(x)$ is correctly updated, satisfying

$ac{c}_{ip}(\omega x)=ac{c}_{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.

3.2.2. Conditional Addition

$$\begin{array}{rl}{c}_2(x)=& (b(x)((ac{c}_x(x)-p_x(x){)}^2(ac{c}_x(x)+p_x(x)+ac{c}_x(\omega x))\\ & -(p_y(x)-ac{c}_y(x){)}^2)\\ & +(1-b(x))(ac{c}_x(\omega x)-ac{c}_x(x)))\times (x-{\omega }^{N-4})\end{array}$$

$$\begin{array}{rl}{c}_3(x)=& (b(x)((ac{c}_x(x)-p_x(x))(ac{c}_y(\omega x)+ac{c}_y(x))\\ & -(p_y(x)-ac{c}_y(x))(ac{c}_x(\omega x)-ac{c}_x(x)))\\ & +(1-b(x))(ac{c}_x(\omega x)-ac{c}_x(x)))\times (x-{\omega }^{N-4})\end{array}$$

These constraints enforce correct elliptic curve addition for the

$x$ and

$y$ components, respectively, controlled by the Boolean variable

$b(x)$:

• When
  $b(x)=1$:
  $c_2(x)$ and
  $c_3(x)$ enforce the correct elliptic curve addition for the
  $x$ and
  $y$ components, respectively.
• When
  $b(x)=0$: both constraints ensure the accumulator remains unchanged.

The factor

$(x-{\omega }^{N-4})$ nullifies the constraint at

$x={\omega }^{N-4}$, where it does not apply.

3.2.3. Booleanity

$$c_3(x)=b(x)(1-b(x))$$

Ensures that the polynomial

$b(x)$ acts as a Boolean variable, taking only values 0 or 1.

• If
  $b(x)=0$ or
  $b(x)=1$, then
  $c_3(x)=0$.
• If
  $b(x)$ takes any value other than 0 or 1,
  $c_3(x)$ will be non-zero, violating the constraint.

3.2.4. 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)=(ac{c}_x(x)-s_x)L_0(x)+(ac{c}_x(x)-r_x-s_x)L_{N-4}(x)$$

$$c_6(x)=(ac{c}_y(x)-s_y)L_0(x)+(ac{c}_y(x)-r_y-s_y)L_{N-4}(x)$$

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

• At
  $x={\omega }^0$:
  $L_0(x)=1$ and
  $L_{N-4}(x)=0$, enforcing
  $ac{c}_x({\omega }^0)=s_x$ and
  $ac{c}_y({\omega }^0)=s_y$.
• At
  $x={\omega }^{N-4}$:
  $L_0(x)=0$ and
  $L_{N-4}(x)=1$, enforcing
  $ac{c}_x({\omega }^{N-4})=r_x+s_x$ and
  $ac{c}_y({\omega }^{N-4})=r_y+s_y$.

3.2.5. Inner Product Boundary

$$c_7(x)=ac{c}_{ip}(x)L_0(x)+(ac{c}_{ip}(x)-1)L_{N-4}(x)$$

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

• At
  $x={\omega }^0$:
  $L_0(x)=1$ and
  $L_{N-4}(x)=0$, enforcing
  $ac{c}_{ip}({\omega }^0)=0$.
• At
  $x={\omega }^{N-4}$:
  $L_0(x)=0$ and
  $L_{N-4}(x)=1$, enforcing
  $ac{c}_{ip}({\omega }^{N-4})=1$.

3.3. Constraints Aggregation

3.3.1. 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_{ac{c}_{ip}},C_{ac{c}_x},C_{ac{c}_y})$$

Construct the aggregated polynomial:

$$c(x)=(\sum _{i=1}^7{\alpha }_i{c}_i(x))\cdot \prod _{k=1}^3(x-{\omega }^{N-k})$$

The factor

$\prod _{k=1}^3(x-{\omega }^{N-k})$ 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.

3.3.2. 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.

3.3.3. 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)$$

3.3.4. 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 )$$

$$ac{c}_{ip,\zeta }=ac{c}_{ip}(\zeta )$$

$$ac{c}_{x,\zeta }=ac{c}_x(\zeta )$$

$$ac{c}_{y,\zeta }=ac{c}_y(\zeta )$$

3.3.5. 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})ac{c}_{ip}(x)$$

Conditional addition accumulators (

$c_{2,3}$) contributions:

$$l_2(x)=(\zeta -{\omega }^{N-4})(b_{\zeta }(ac{c}_{x,\zeta }-p_{x,\zeta }{)}^{2}ac{c}_x(x)+(1-b_{\zeta })ac{c}_y(x))$$

$$l_3(x)=(\zeta -{\omega }^{N-4})((b_{\zeta }(ac{c}_{y,\zeta }-p_{y,\zeta })+1-b_{\zeta })ac{c}_x(x)+b_{\zeta }(ac{c}_{x,\zeta }-p_{x,\zeta })ac{c}_y(x))$$

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 )$$

3.3.6. 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 },ac{c}_{ip,\zeta },ac{c}_{x,\zeta },ac{c}_{y,\zeta },l_{\zeta \omega })$$

Construct the aggregate polynomial:

$$agg(x)={\nu }_1{p}_x(x)+{\nu }_2{p}_y(x)+{\nu }_{3}s(x)+{\nu }_{4}b(x)+{\nu }_{5}ac{c}_{ip}(x)+{\nu }_{6}ac{c}_x(x)+{\nu }_{7}ac{c}_y(x)+{\nu }_{8}q(x)$$

3.3.7. Proof Construction

Open the aggregate polynomial

$agg$ at

$\zeta$ and the linearization polynomial

$l$ at

$\zeta \omega$:

$${\mathrm{\Pi }}_{\zeta }=\text{PCS.Open}(agg,\zeta )$$

$${\mathrm{\Pi }}_{\zeta \omega }=\text{PCS.Open}(l,\zeta \omega )$$

Construct the proof as follows:

$$\mathrm{\Pi }=(C_b,C_{ac{c}_{ip}},C_{ac{c}_x},C_{ac{c}_y},p_{x,\zeta },p_{y,\zeta },s_{\zeta },b_{\zeta },ac{c}_{ip,\zeta },ac{c}_{x,\zeta },ac{c}_{y,\zeta },C_q,l_{\zeta \omega },{\mathrm{\Pi }}_{\zeta },{\mathrm{\Pi }}_{\zeta \omega })$$

---

4. Verifier

4.1. 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

$P{K}_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:

$$\mathrm{\Pi }=(C_b,C_{ac{c}_{ip}},C_{ac{c}_x},C_{ac{c}_y},p_{x,\zeta },p_{y,\zeta },s_{\zeta },b_{\zeta },i{p}_{\zeta },a{c}_{x,\zeta },a{c}_{y,\zeta },C_q,l_{\zeta \omega },{\mathrm{\Pi }}_{\zeta },{\mathrm{\Pi }}_{\zeta \omega })$$

4.2. Verification

4.2.1. Fiat-Shamir Challenges

Recovery of aggregation coefficients and evaluation point:

$$\{{\alpha }_i{\}}_{i=1}^7\leftarrow \text{FS}(C_b,C_{ip},C_{ac{c}_x},C_{ac{c}_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 },ac{c}_{ip,\zeta },ac{c}_{x,\zeta },ac{c}_{y,\zeta },l_{\zeta \omega })$$

4.2.2. 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 }=-(ac{c}_{ip,\zeta }+b_{\zeta }{s}_{\zeta })(\zeta -{\omega }^{N-4})$$

$${\tilde{c}}_{2,\zeta }=\{b_{\zeta }[(ac{c}_{x,\zeta }-p_{x,\zeta }{)}^2(ac{c}_{x,\zeta }+p_{x,\zeta })-(p_{y,\zeta }-ac{c}_{y,\zeta }{)}^2]-(1-b_{\zeta })ac{c}_{y,\zeta }\}(\zeta -{\omega }^{N-4})$$

$${\tilde{c}}_{3,\zeta }=\{b_{\zeta }[(ac{c}_{x,\zeta }-p_{x,\zeta })ac{c}_{y,\zeta }+(p_{y,\zeta }-ac{c}_{y,\zeta })ac{c}_{x,\zeta }]-(1-b_{\zeta })ac{c}_{x,\zeta }\}(\zeta -{\omega }^{N-4})$$

$$c_4=b_{\zeta }(1-b_{\zeta })$$

$$c_5=(ac{c}_{x,\zeta }-s_x)L_0(\zeta )+(ac{c}_{x,\zeta }-r_x-s_x)L_{N-4}(\zeta )$$

$$c_6=(ac{c}_{y,\zeta }-s_y)L_0(\zeta )+(ac{c}_{y,\zeta }-r_y-s_y)L_{N-4}(\zeta )$$

$$c_7=ac{c}_{ip,\zeta }{L}_0(\zeta )+(ac{c}_{ip,\zeta }-1)L_{N-4}(\zeta )$$

Note: The tilde (

$\stackrel{~}{}$ ) 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 }$).

4.2.3. 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 }_i{c}_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}_{ac{c}_{ip}}+{\nu }_6{C}_{ac{c}_x}+{\nu }_7{C}_{ac{c}_y}+{\nu }_8{C}_q$$

Compute the aggregate evaluation

$ag{g}_{\zeta }$ using the same coefficients:

$$ag{g}_{\zeta }={\nu }_1{p}_{x,\zeta }+{\nu }_2{p}_{y,\zeta }+{\nu }_3{s}_{\zeta }+{\nu }_4{b}_{\zeta }+{\nu }_{5}ac{c}_{ip,\zeta }+{\nu }_{6}ac{c}_{x,\zeta }+{\nu }_{7}ac{c}_{y,\zeta }+{\nu }_8{q}_{\zeta }$$

Verify the aggregate polynomial opening at

$\zeta$ using

${\mathrm{\Pi }}_{\zeta }$:

$$\text{PCS.Verify}(C_{agg},\zeta ,ag{g}_{\zeta },{\mathrm{\Pi }}_{\zeta })$$

4.2.4. Evaluation of the Linearization Polynomial at

$\zeta \omega$

Compute the individual linearization polynomial commitments:

$$C_{l_1}=(\zeta -{\omega }^{N-4})C_{ac{c}_{ip}}$$

$$C_{l_2}=(\zeta -{\omega }^{N-4})(b_{\zeta }(ac{c}_{x,\zeta }-p_{x,\zeta }{)}^2{C}_{ac{c}_x}+(1-b_{\zeta })C_{ac{c}_y})$$

$$C_{l_3}=(\zeta -{\omega }^{N-4})((b_{\zeta }(ac{c}_{y,\zeta }-p_{y,\zeta })+1-b_{\zeta })C_{ac{c}_x}+b_{\zeta }(ac{c}_{x,\zeta }-p_{x,\zeta })C_{ac{c}_y})$$

Aggregate the linearization polynomial commitments using

$\{{\alpha }_i\}$ coefficients.

$$C_l=\sum _{i=1}^3{\alpha }_i{C}_{l_i}$$

Verify the aggregate linearization polynomial opening at

$\zeta \omega$ using

${\mathrm{\Pi }}_{\zeta \omega }$:

$$\text{PCS.Verify}(C_l,\zeta \omega ,l_{\zeta \omega },{\mathrm{\Pi }}_{\zeta \omega })$$

5. Acknowledgements

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

6. References

• These notes on hackmd: https://hackmd.io/@davxy/r1SVPqQc0.
• Sergey Vasilyev original writeup: https://hackmd.io/ulW5nFFpTwClHsD0kusJAA
• W3F reference implementation: https://github.com/w3f/ring-proof