# Jet KZG ring VRFs
We define a ring VRF in which users amortize a groth16 with $O(\log \texttt{max_ring_size})$ constraints. We maintain the ring in a Merkle mountian range (MMR), instead of a single Merkle tree. As our ring grows users reprove this groth16 $O(\log \texttt{max_ring_size})$ times ever.
We have an inner [groth16](https://eprint.iacr.org/2016/260) proof for usage in a [specialized groth16 zero-knowledge continuation](https://eprint.iacr.org/archive/2023/002/20230101:143437), meaning its public input term $Z_1 = z_i [\zeta_i]_1$ has terms which must be hidden and really public inputs $Z_{\mathsf{pub}}$. $\def\sk{\mathtt{sk}} \def\Gsk{[\zeta_{\mathsf{sk}}]_1} \def\bsk{b_{\mathsf{sk}}} \def\fkvg{c_{kvg}} \def\Gx{[\zeta_x]_1} \def\Gxz{[\xi\epsilon/\gamma]_1} \def\Gz{[\tau\xi\epsilon/\gamma]_1}$ <!-- G_{xz} -->
$$ \begin{aligned}
e(A_1,B_1)
&= e([\alpha_1]_1, [\beta_1]_2)
\cdot e( Z_1, [\gamma]) \cdot e(C_1, [\delta]_2) \\
Z_{\mathsf{sec}} &= Z - Z_{\mathsf{pub}} + b_{\mathsf{zkc}} [\theta]_1 \\
C_1' &= C_1 + b_{\mathsf{zkc}} [\theta\gamma/\delta]_1 \\
e(A_1,B_1)
&= e([\alpha_1]_1, [\beta_1]_2)
\cdot e( Z_{\mathsf{sec}} + Z_{\mathsf{pub}}, [\gamma]) \cdot e(C_1', [\delta]_2)
\end{aligned} $$
We form a polynomial $\aleph$ whose designated evaluations give the current MMR roots for the ring.
We let $\tau$ denotes toxic waste used in powers, but independent from that used in the inner groth16. We compute a [KZG commitment](https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html) $\def\kzgcom{\mathtt{com}} \kzgcom$ for $\aleph$ using the modified SRS $[ \tau^i \epsilon / \gamma ]_1$, insted of the usual $[ \tau^i ]_1$. We also compute a KZG openning proof $\pi$ for the evaluation $y = \aleph(x)$ using the modified SRS $[ \tau^i ]_1$. We thus have the modified KZG opening proof:
$$ \begin{aligned}
e(\pi, [\tau \epsilon]_2 - x [\epsilon]_2)
&= e(\kzgcom, [\gamma]_2) \cdot e(- y [\epsilon/\delta]_1, [\delta]_2) \\
&\textrm{or} \\
e(A_2', B_2) &= e(\kzgcom + D_x + D_\tau, [\gamma]_2) \cdot e(C_2, [\delta]_2) \\
A_2 &= \color{green}{b_\pi^{-1}} \pi \color{orange}{+ b_p [\xi/\gamma]_1} \\
A_2' &= A_2 \color{red}{+ \fkvg [\xi/\gamma]_1} \\
B_2 &= \color{green}{b_\pi} [\tau \epsilon]_2 - \color{green}{b_\pi} x [\epsilon]_2 \\
C_2 &= - y [\epsilon/\delta]_1 \\
z &= \color{green}{b_\pi} (\color{orange}{b_p} + \color{red}{\fkvg}) \\
D_x &= x z \Gxz \\
D_\tau &= z \Gz \\
\end{aligned} $$
We should control $x$ from the inner groth16 via some $X = x \Gx$ term, so we prove the division of $D_x$ by $D_\tau$, roughly via $\textrm{DLEQ}\left( D_x / D_\tau = X / [\tau\zeta_x]_1 \right)$. We have a double multiplication here because of the $D_\tau$ denominator, for which two approaches look viable:
---
In principle, we could do two DLEQ proofs involving an intermediate bridge value $D' = b_\pi(b_p + \fkvg) [\epsilon/\gamma]_1$. Also our VRF needs another DLEQ proof between $\mathtt{apk} = \sk \Gsk + \bsk [\theta]_1$ and $\mathtt{h} = H_{\mathtt{sis}}(\mathtt{msg})$ and $\mathtt{preout} = \sk \, \mathtt{h}$, so all told this resembles
$$ \textrm{DLEQ}\left( \begin{aligned}
D_x/D' &= X/[\zeta_x]_1 \\
D'/[\epsilon/\gamma]_1 &= D_\tau/[\tau\epsilon/\gamma ]_1 \\
\mathtt{apk} / \Gsk &= \mathtt{preout} / \mathtt{h} \\
\end{aligned} \right) $$
Aside from $\mathtt{preout}$, all variable points here need blingind by $[\theta]_1$ terms, including $D'$. We need four scalar multiplications in each DLEQ proof, so after optimizations verifiers need 15 scalar multiplications. (TODO: Is 15 correct?)
In other words, the $U/V$ term in the $i$th row yields one verification equation like $t_i [\theta]_1 + s_i V = K_{U/V} + c \, U$, except for $\mathtt{preout}$ which looks like $s_3 \mathtt{h} = K_{U/V} + c \, \mathtt{preout}$ and lives on the sister curve.
---
Instead of doing two DLEQ proofs, we avoid the intermediate $D'$ terms by cancelling out the cross term directly, like a one layer inner product argument. In this, our preliminary witnesseses look like
$$ \def\Rcross{R_{\mathtt{cross}}} \begin{aligned}
R_x &\leftarrow r_x \Gx \\
R_z &\leftarrow r_z \Gz \\
R_{xz} &\leftarrow r_x r_y \Gxz \\
\Rcross &\leftarrow (r_x y + r_y x) \Gxz \\
R_{\mathsf{sk}} &\leftarrow r_{\mathsf{sk}} \Gsk \\
R_{\mathtt{h}} &\leftarrow r_{\mathsf{sk}} \mathtt{h}
\end{aligned} $$
In signing below, we'll produce a challenge $c = H(\cdots)$ and some proof components
$$ \begin{aligned}
s_x &\leftarrow r_x + c x \\
s_z &\leftarrow r_z + c z \\
s_{\mathsf{sk}} &\leftarrow r_{\mathsf{sk}} + c \sk \\
\end{aligned} $$
while verification should imply the equations
$$ \begin{aligned}
s_x \Gx &= R_x + c P_x \\
s_z \Gz &= R_z + c P_z \\
s_x s_z \Gxz &= c^2 P_{xz}+ c \Rcross + R_{xz} \\
s_{\mathsf{sk}} \Gx &= R_{\mathsf{sk}} + c \, [\sk \Gsk] \\
s_{\mathsf{sk}} \mathtt{h} &= R_{\mathtt{h}} + c \, \mathtt{preout} \\
\end{aligned} $$
An initial round merges the verification equations:
$$ \begin{aligned}
t_0 &\leftarrow (\Gx,\Gxz,\Gz) \\
t &\leftarrow (P_x,P_{xz},P_z,\Rcross,\mathtt{h},\mathtt{apk}) \\
(c_x,c_z,c_{\mathsf{sk}}) &\leftarrow H(t_0,t) \\
R &\leftarrow c_x R_x + c_z R_z + R_{xy} + c_{\mathsf{sk}} R_{\mathsf{sk}}
\end{aligned} $$
At this point, our signature consists of $\sigma = (P_x, P_z, P_{xz}, \Rcross, R, s_x, s_z, s_{\mathsf{sk}})$. We need zero-knowledge so our signer select a random $b_J$ and adds $b_J [\theta]_1$ to each curve point $J$ in $\sigma$, so then we need one more proof component
$$
s_\theta \leftarrow b_R + c (c_x b_{P_x} + c_y b_{P_z} + b_{\Rcross} + \bsk) + c^2 b_{P_{xz}} $$
Now our verifier recomputes $t$ and checks
$$ \begin{aligned}
(c_x,c_z,c_{\mathsf{sk}}) &\leftarrow H(t_0,t) \\
P &\leftarrow c_x P_x + c_y P_y + \Rcross + c_{\mathsf{sk}} \mathtt{apk} \\
c &\leftarrow H(t_0,t,R) \\
s_{\mathsf{sk}} \mathtt{h} &= R_{\mathtt{h}} + c \, \mathtt{preout} \\[5pt]
c_x s_x \Gx + c_y &s_z \Gz + s_x s_z \Gxz + s_{\mathsf{sk}} \Gsk + s_\theta [\theta]_1 \\
&\quad= R + c P + c^2 P_{xz}
\end{aligned} $$
In total, five fixed base and five variable base scalar multiplications, plus one of each on the faster Edwards curve.
---
We connected $x$ from the Groth16 output to the KZG input above. We should connect $y$ from the KZG output to the Groth16 input too.
We therefore want $C_2 = - y [\epsilon/\delta]_1$ wired directly into $C_1$ too, for which we could choose $\epsilon$ so that $[-\epsilon/\delta]_1$ becomes the wire $[\epsilon'/\delta]_1$ from our inner Groth16. As $\epsilon$ shows up as $[\epsilon]_2$, $[\tau\epsilon]_2$, and elsewhere, we instead the wire in $C_1$ be given by $[{\epsilon'-\epsilon \over \delta}]_1$. We remark the bare groth16 could be verified by using $[\epsilon'/\gamma]_1$, which never appears normally.
As this subsumes $C_2$ into $C_1$, we now define
$$ C = C_1 + (b_{P_x} + b_{P_z} + \bsk) [\theta\gamma/\delta]_1 $$
so then our verification equation becomes
$$ \begin{aligned}
e(A_1,B_1) e(A_2, B_2)
&= e([\alpha_1]_1, [\beta_1]_2) \cdot e(I, [\gamma]_2) \cdot e(C, [\delta]_2) \\
I &= \kzgcom + D_x + D_\tau + \mathtt{apk} \\
\end{aligned} $$
<!-- Z_{\mathsf{sec}} + Z_{\mathsf{pub}} -->
$$ \begin{aligned}
\\
\end{aligned} $$
### Alternatives
Caulk-- https://hackmd.io/Y7bmKXrOQricqhggpVFxfA
We introduce a single blinding term so these can all be handled as Pedersen commitments.
$$ e(A_1,B_1) \cdot e(A_2,B_2)
= e([\alpha_1]_1, [\beta_1]_2) \cdot e([\alpha_2]_1, [\beta_2]_2)
\cdot e( Z_{\mathsf{sec}} + Z_{\mathsf{pub}} + \kzgcom, [\gamma]) \cdot e(C_1, [\delta]_2) \mathperiod $$
<!--
$$ e(A_1,B_1) \cdot e(A_2,B_2)
= e([\alpha_1]_1, [\beta_1]_2) \cdot e([\alpha_2]_1, [\beta_2]_2)
\cdot e( Z_{\mathsf{sec}} + Z_{\mathsf{pub}} + \kzgcom, [\gamma]) \cdot e(C_1, [\delta]_2) \mathperiod $$
-->
<!--
$$ \begin{aligned}
e(\pi, [\tau \delta]_2 - x [\delta]_2)
&= e(\kzgcom - y [1/\gamma]_1, [\gamma]_2) \\
e(\pi, [\tau \delta]_2) - e(x \pi, [\delta]_2)
&= e(\kzgcom - y [1/\gamma]_1, [\gamma]_2) \\
e(\pi \color{blue}{+ (b_p + b_v) [\eta]_1}, [\tau \delta]_2) - e(x \pi, [\delta]_2) &= e(\kzgcom - y [1/\gamma]_1, [\gamma]_2) \\
& - e(\color{blue}{(b_p + b_v) [\eta \tau]_1}, [\delta]_2)
\end{aligned} $$
-->
<!-- $$ \textrm{DLEQ}\left( {x b_\pi (b_p + \fkvg) [\epsilon/\delta]_1 \over b_\pi (b_p + \fkvg) [\tau\epsilon/\delta]_1} = {x [\zeta]_1 \over [\tau\zeta]_1} \right) $$ -->
<!--
Prove $D_\tau$ is a multiple of $[\tau\epsilon/\delta]_1$.
Prove $D_1$ is a multiple of $D_\tau + [\tau\zeta]_1$.
Prove $D$ is a linear combination of $[\epsilon/\delta]_1$ and $[\zeta]_1$
Prove DLEQ between $D_1$ and $D$
Prove $D_1$ is a multiple of some $D$, which an honest prover choses to be $D = D_x + x [\zeta]_1$.
\color{blue}{f_z}
$U = [\epsilon/\delta]_1 + b_e [\eta]_1$
$K = [\epsilon/\delta]_1 + f_z [\tau\epsilon/\delta]_1$
$[\epsilon/\delta]_1 + [\tau\epsilon/\delta]_1$
$x [\zeta]_1 + [\tau\zeta]_1$
\color{blue}{+ x (b_p + b_v) [\eta/\gamma]_1}
-->