# 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} -->
Last changed by  
 
Jeff Burdges
97

Read more

Subsrtate next generation storage

https://forum.polkadot.network/t/generalized-storage-proofs/1315

2/26/2024
Aggregation of Merkle proofs from homomorphic hashes

Let P(x,y) = x A + y B denote a Pedersen hash on the curve E over F_q. Assume p = |E| < q.

10/17/2023
Validator rewards in Polkadot/Kusama

Ideally, almost all rewards in Kusama/Polkadot would come from work done securing parachains like backing and approval checkers, including work supporting XCMP, and availability. We do need participation in relay chain block production and finality, so some rewards must continue, but their levels shall wind up greatly reduced.

10/7/2023
ark-substrate design choices

https://github.com/paritytech/substrate/pull/13031 https://github.com/paritytech/ark-substrate https://github.com/w3f/ark-scale/ Coordinates Affine coordinates and serialized forms differe in Arkworks and ZCash/BLST, but an easy conversion is given by https://github.com/MystenLabs/fastcrypto/tree/main/fastcrypto-zkp/src/bls12381

6/6/2023
Read more from Jeff Burdges
Published on HackMD