halo2 recursion example

# halo2 recursion example ## Setup - Two provers, $p_1$ and $p_2$. With witnesses $w_{1, 1}, w_{1, 2}, w_{1, 3}$ and $w_{2, 1}, w_{2, 2}, w_{2, 3}$ respectively. - For simplicity, each witness is a polynomial with degree less than $2^2 = 4$. - Vanishing polynomials are defined as $$\forall i \in \{1, 2\},\quad t_i = (w_{i, 1} + w_{i, 2} - w_{i, 3})/(x^4-1)$$ which is simply an addition gate. - Challenges are denoted by $\alpha_1$ and $\alpha_2$, derived via Fiat-Shamir.  ## Without recursion We are to generate two separate proof $\pi_1, \pi_2$, consists of the following: \begin{align*} \pi_i = &{t_i(\alpha_i), w_{i, 1}(\alpha_i), w_{i, 2}(\alpha_i), w_{i, 3}(\alpha_i)},\\ &\texttt{IPACommit}(w_{i, 1}),\texttt{IPACommit}(w_{i, 2}),\texttt{IPACommit}(w_{i, 3}), \\ &\texttt{IPAOpen}(w_{i, 1},\alpha_i),\texttt{IPAOpen}(w_{i, 2},\alpha_i),\texttt{IPAOpen}(w_{i, 3},\alpha_i) \end{align*} For $i \in\{1,2 \}$, the verifier $v_i$ checks - $t_i(\alpha_i)\times(\alpha_i^4-1)== w_{i, 1}(\alpha_i)+ w_{i, 2}(\alpha_i)- w_{i, 3}(\alpha_i)$ - $\forall j\in\{1,2,3\},\quad \texttt{IPAVerify}(\texttt{IPACommit}(w_{i, j}), \texttt{IPAOpen}(w_{i, j},\alpha_i), \alpha_i)==1$ ## With recursion The goal is to generate a single proof $\pi$ by $p_2$, while doing as little work as possible for $p_1$. ### Naive approach. $p_1$ does nothing. It sends $w_{1,j}, \forall j\in \{1,2,3\}$ to $p_2$. $p_2$ then generates both $\pi_1$ and $\pi_2$. The saving, in terms of total amount of work between $p_1$ and $p_2$, is that IPA may be batch opened at the same challenge point. The catch is, the communication between $p_1$ and $p_2$ is linear in the size of the witnesses. ### Full recursive approach. $p_1$ generates its proof $\pi_1$ as usual. $p_2$ additional proves the statement $\texttt{Verify}(\pi_2)==1$ in circuit, and combine the verification circuit with $w_{2,j},\forall j\in\{1,2,3\}$ to generate a new proof $\pi_2'$. The advantage is this design is clean, with clearly defined APIs and easy to benchmark. The drawback is this may be really slow as the total work done by $p_1$ and $p_2$ is increased by proving a recursive circuit. ### Almost full recursive approach. This is the approach taken by Halo2-KZG. To verify $p_1$ there are two components: 1. verify $t_i(\alpha_i)\times(\alpha_i^4-1)== w_{i, 1}(\alpha_i)+ w_{i, 2}(\alpha_i)- w_{i, 3}(\alpha_i)$ 2. verify the KZG commitment and opening is correct. This breaks down to a. compute some group elements (G1 component to the left and right part of the pairing equation) via group operations b. check that pairing is valid for those group elements In an almost fully recursive approach, the circuit proves the statements of 1 and 2(a). Statement 2(a) is sufficient to argue that the group elements are correctly computed, i.e., the proof is valid as long as the pairing is correct. The pairing itself is deferred to the final prover, and is checked out of the circuit. The total amount of work, compared to no recursion at all, is to prove in circuit that the vanishing polynomial is correct, and that the accumulator is corrected via __non-native field arithmetics__. ### Halo2 approach. Halo2 approach is similar to the almost full recursive approach. The details can be found in the [book](https://zcash.github.io/halo2/background/recursion.html). The difference is that in step 2(a) one is only required to prove that the field elements are generated correctly. In step 2(b) an O(n) group operation is done to verify the correctness. Similarly, those group operations are deferred to the final prover. That is, given a proof \begin{align*} \pi_1 = &{t_1(\alpha_i), w_{1, 1}(\alpha_1), w_{1, 2}(\alpha_1), w_{1, 3}(\alpha_1)},\\ &\texttt{IPACommit}(w_{1, 1}),\texttt{IPACommit}(w_{1, 2}),\texttt{IPACommit}(w_{1, 3}), \\ &\texttt{IPAOpen}(w_{1, 1},\alpha_i),\texttt{IPAOpen}(w_{1, 2},\alpha_i),\texttt{IPAOpen}(w_{1, 3},\alpha_i) \end{align*} and an accumulator $\vec a = \left<a_1, a_2, a_3\right>\in \mathbb G^3$. $p_2$ does the following: 1. verify in circuit $t_i(\alpha_i)\times(\alpha_i^4-1)== w_{i, 1}(\alpha_i)+ w_{i, 2}(\alpha_i)- w_{i, 3}(\alpha_i)$ 2. derive $log(n)=2$ challenges $u_1$ and $u_2$ 3. prove in circuit that $\vec a$ is updated correctly using $u_1$ and $u_2$ and SRS. Caveat: - Step 3 is done in native field arithmetics. This requires cyclic curves. - The data that send from $p_1$ to $p_2$ is $\pi_1$ which is of size $2 log(n)$, The total amount of work, compared to no recursion at all, is to prove in circuit that the vanishing polynomial is correct, and that the accumulator is corrected via __native field arithmetics__. # Cost analysis We are probably fine if each recursive circuit is bounded by degree $n=2^{20}$ of $m=20$ polynomials (preliminary data point). We want to ensure that this size is sufficient to update accumulators in halo2. Each recursive prover will require $ mlog(n) = 400$ native field group operations. Where each group operation takes roughly 300 plonk constraints. So in total the recursive circuit size is expected at 120k constraints. Taking into account that there are likely some hidden constants, setting $n=2^{20}$ seems appropriate. ---- ---- # Costs breakdown Let's say circuit size is $n = 2^{16}$ gates (XXX break it down!) Curves: secp/secq ## Communication cost This is the size of the proof object we send to the next prover: 1. Halo2 proof size. For each witness column: - Commitment (one group element) - Opening value at random element (field element) - IPA opening proof ($2 log n$ group elements, $1$ field element) 2. Accumulator size. For each witness column: - Precomputed $G = <\vec{s}, \vec{G}>$ (1 group element) ## Decider cost (aka cost of non-aggregating verifiers) This is the time someone needs to verify a merged signature. This cost must be paid by aggregators before they merge a signature, by network participants before gossiping a merged signature, and by validators verifying a merged-signature posted on chain. 1. Verify the halo2 proof completely (out of circ) - Batch all the IPA openings - Verify batched IPA opening: essentially an $O(n)$ MSM MSM of size $2^{16}$ (on secp): 124ms ## Aggregator cost (aka prover cost) This is the time that an aggregator needs to spend to merge a signature into an already existing merged signature: First of all, **the aggregator needs to to run the decider** on the to-be-merged signature (see above). Then pay the costs below for merging the signature: ### Recursion overhead (proving function F'): #### Useful computation (function F) 1. sig verify 2. OR bitfields #### Perform the IVC/PCD logic Hashing? Poly evals? we need some way to link inputs and outputs on the PCD graph #### Halo2 partial-verifier 1. Zero check: $t_i(\alpha_i)\times(\alpha_i^4-1)== w_{i, 1}(\alpha_i)+ w_{i, 2}(\alpha_i)- w_{i, 3}(\alpha_i)$ few constraints (?) 2. Batch inner products (??) 3. Partial-verify inner product in-circuit - perform $logn$ hashes $H(\mathbb{G} || \mathbb{G})$ to compute IPA challenges - $2logn$ ECMULs and $2logn$ ECADDs for computing $Q$ 4. derive challenges $u_1$ and $u_2$ via hashing (what?) 5. prove in circuit that accumulator $\vec a$ is updated correctly using $u_1$ and $u_2$ and SRS. - Two ECMULs and one ECADD? We pay all the above twice due to curve cycles?