# 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} -->