You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
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.
Maps a serializable object $\textbf{s} \in \mathbb{S}$ to $\mathbb{F}$, typically via some cryptographically secure hash function.
2. Parameters
2.1. Scheme Specific
$\square \in \mathbb{J}$ -- Padding element, a point on $\mathbb{J}$ with unknown discrete logarithm.
$H \in \mathbb{J}$ -- Pedersen blinding base point.
$\overline{H} = (H, 2H, 4H, \ldots, 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 $\square$ to length $N_K$ if needed.
2.3. Witness Data
$t \in \mathbb{F_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.
Ring items selector:
$$\overline{s} = 1^{|N_K}\ |\ 0^{|N-N_K} \in \mathbb{F}^N$$
2.4.1 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})$$
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} }$$
3. Prover
3.1. Witness Polynomials
3.1.1. Bits Vector
$\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}$
$\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}$
The bits vector $\overline{b}$ is constructed by concatenating $\overline{k}$ and $\overline{t}$, followed by a single 0.
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})
$$
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}(\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)$$
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}$).
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)\bigl(1 - b(x)\bigr)$$
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) = \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:
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$.
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})$$
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.
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)$$$$acc_{ip,\zeta} = acc_{ip}(\zeta)$$$$acc_{x,\zeta} = acc_x(\zeta)$$$$acc_{y,\zeta} = acc_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.
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, 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)$$
3.3.7. 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})$$
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 $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})
$$
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}=-(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)$$
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}$).
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_ic_i+l_{\zeta\omega})\prod_{k=1}^3(\zeta-\omega^{N-k})}{\zeta^N-1}$$
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)$$
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_{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})$$
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