# UltraGroth
## Challenge rounds in Groth16-like system

This is a continuation and clarification of my [previous post](https://hackmd.io/@Merlin404/SJmtF_k-2) which was a very rough description of a possible scheme of adding lookups (and any other challenge arguments) to Groth16.

It generated some traction and comments. Mainly I would like to thank Weikeng Chen who gave me some references on similar approaches (based on LegoSNARK), and confirmed that it should be possible to get rid of all interfacing between different argument systems (which loosely works similar to Pinoccio), instead using a singular Groth16-styled equation.

It seems that it is, indeed, possible. I describe the protocol here, and provide a sketch of proof.

### Let's recall normal Groth16 protocol, first

This turned out to be quite long, tbh. Can be skipped, but it makes sense to look on zero-knowledgness / soundness proofs here to make sense of my arguments for the UltraGroth.

<details>
<summary>R1CS</summary>
In normal Groth16, we start from a rank 1 constraint system, R1CS:

$L w \circ R w = O w$

Here, $L, R, O$ are matrices of size $m \times n$, where $m$ is a size of a witness vector $w^i$, and $n$ is the amount of constraints, and $\circ$ is a Hadamard product.

Individual constraints, thus, correspond to the rows of the matrix:

$L^i w * R^i w = O^i w$
$(\underset{j}\sum L^{i}_jw^j )*(\underset{j}\sum R^i_jw^j) = \underset{j} \sum O^{i}_jw^j$

Some subset of indices of the witness, is also called "public inputs", and will be exposed by the proof, and all others are private.

Now, we map the set of constraints to some set $S$ in the scalar field of a pairing-friendly curve - I will denote $x_i$ the point corresponding to the constraint $i$. $Z(x)=\underset{i}\prod (x-x_i)$ denotes the vanishing polynomial of this set, and we also define $L_j(x), R_j(x), O_j(x)$ by their Lagrange interpolation of the values over the set: $L_j(x_i) = L^i_j$ (and the same for $R, O$).

Then, the R1CS problem can be reformulated as finding such witness vector $w^j$ that
$(\underset{j}\sum w_j L_j(x))(\underset{j}\sum R_j(x))-(\underset{j}\sum O_j(x))$ vanishes on $S$, <=> divisble by $Z(x)$, <=> there exists such $H(x)$ (of degree at most $n$) that:
$L(x)R(x)-O(x) = Z(x)H(x)$
where
$L = \underset{j}\sum w_j L_j(x)$
$R = \underset{j}\sum w_j R_j(x)$
$O = \underset{j}\sum w_j O_j(x)$

</details>

<details>
<summary>Groth16 argument</summary>

Now, lets recall how this problem is turned into a zk-proof.

We have the following toxic waste elements: $(\alpha, \beta, \gamma,\delta,\tau)$, and the reference string is computed as follows:

$[\alpha]_1, [\beta]_1, [\beta]_2, [\gamma]_2, [\delta]_1, [\delta]_2$,
for $0 \leq k \leq n:$ $Z_k = [\frac{\tau^kZ(\tau)}{\delta}]_1$ <-- these will allow us to compute $[\frac{H(\tau)Z(\tau)}{\delta}]_1$
$A_j = [L_j(\tau)]_1, B_j = [R_j(\tau)]_2$, $B'_j = [R_j(\tau)]_1$
for $j \in \text{priv}:$ $C_j = [\frac{O_j(\tau) + \beta L_j(\tau) + \alpha R_j(\tau)}{\delta}]_1$
for $j \in \text{pub}:$ $C_j = [\frac{O_j(\tau) + \beta L_j(\tau) + \alpha R_j(\tau)}{\gamma}]_1$

[...]

The Groth16 prover (given the solution to R1CS in the polynomial form described above) creates two random blinding scalars $r, s$ and computes the following:

$A = [\alpha]_1 + \underset{j}\sum w_j A_j + r[\delta]_1$
$B = [\beta]_2 + \underset{j}\sum w_j B_j + s[\delta]_2$, $B' = [\beta]_1 + \underset{j}\sum w_j B'_j + s[\delta]_1$
$C = \underset{j \in \text{priv}}\sum w_j C_j + \sum h_k Z_k +rB' + sA - rs[\delta]_1$

and $IC$ is computed from public inputs by both sides:

$IC = \underset{j \in \text{pub}}\sum w_j C_j$

And the verifier does the following check:

$\langle A, B \rangle = \langle[\alpha]_1, [\beta]_2 \rangle + \langle C, [\delta]_2 \rangle + \langle IC, [\gamma]_2\rangle$

</details>

<details>
<summary>Why this holds for a valid R1CS instance</summary>

Let's see why this works:

First, unwind this check to see that it passes. I will calculate LHS and RHS (and abuse notation a bit to calculate by omitting casting it to multiplication group $[]_m$ everywhere). I will also use "A, B, C" as shorthands of their dlogs as scalars.

LHS: $AB = (\alpha + \underset{j}\sum w_j L_j(\tau) + r \delta)(\beta + \underset{j}\sum w_j R_j(\tau) + s\delta)$

RHS: $\alpha \beta + C \delta + IC \gamma = \alpha\beta + \underset{j}\sum w_j(O_j(\tau) + \beta L_j(\tau) + \alpha R_j(\tau)) + H(\tau)Z(\tau) + r\delta B + s \delta A - rs\delta^2$

Now, small modification of LHS makes clear that all terms with $\delta$ will cancel out:

LHS: $AB = sA\delta + rB\delta - rs\delta^2 + (\alpha + \underset{j}\sum w_j L_j (\tau))(\beta + \underset{j}\sum w_j R_j(\tau))$.

The rest is direct inspection.

</details>

<details>
<summary>Zero-knowledge</summary>

Now, let's recall why this is perfectly zero-knowledge, and why this is computationally sound in algebraic group model.

**Zero-knowledge:** it is clear that $A, B$ are uniformly distributed (because prover adds up random uniformly distributed elements $r[\delta]_1, s[\delta]_2$). $C$ is uniquely defined if other variables are fixed (because it is a linear equation), and, therefore, the probability distribution of proofs on a space of solutions of this equation is uniformly random.

*Note: even a stronger fascinating property, re-randomizability, holds. It means that having a correct proof triple (A, B, C) one can construct a new proof (A', B', C') uniformly randomly distributed in the space of all proofs, without knowing the original witness. This property will, sadly, be broken in my extended UltraGroth protocol.*
</details>

<details>
<summary>Soundness in Algebraic Group Model</summary>

**Soundness in AGM:** I won't go into details of AGM, but this has the following intuition: imagine that $\alpha, \beta, \gamma, \delta, \tau$ are variables (i.e. we now calculate in a rational function ring depending on this variables). The adversary then tries to construct a proof, with

$A$ and $C$ being linear combination of expressions
$\alpha, \beta, \delta, \frac{\tau^k Z(\tau)}{\delta}, L_j(\tau), R_j(\tau)$, for $j \in \text{priv}:$ $\frac{O_j(\tau) + \beta L_j(\tau) + \alpha R_j(\tau)}{\delta}$, for $j \in \text{pub}:$ $\frac{O_j(\tau) + \alpha R_j(\tau) + \beta L_j(\tau)}{\gamma}$

and $B$ being linear combination of
$\beta, \delta, \gamma, R_j(\tau)$

And let's assume they succeed, i.e. the expressions satisfy

$AB = \alpha\beta + C\delta + IC\gamma$

First, let's notice that $A$ must contain $\alpha$ and $B$ must contain $\beta$. Moreover, let's wlog rescale them in such a way that both of these are with coefficient $1$.

Ocurrence of $\beta$ in $A$ is then prohibited due to the fact that $\beta^2$ can not occur on RHS.

Now, let's see that in $A$ there should be no terms with $\delta$ or $\gamma$ in denominator. Indeed, if there were, their products by $\beta$ would not be cancelled by anything in LHS, and neither in RHS (because RHS doesn't have a pole at $\delta = 0$).

Let us also notice that occurence of $\gamma$ in $B$ is unwelcome because $\gamma \alpha$ can not occure in RHS.

Therefore, we are in a situation where $A = \alpha + \sum a_j L_j(\tau) + \sum q_j R_j(\tau) + r\delta$ and $B = \beta + \sum b_j R_j(\tau) + s\delta$. We have neither shown that $a_j \neq b_j$ yet, nor $q_j = 0$, nor stated anything about $C$.

WLOG, lets modify $A$ and $B$ by removing $r\delta$ and $s\delta$, and $C$ by subtracting $sA$, $rB$ and adding $rs\delta$. We have successfully exiled $\delta$ from LHS, now it has the form:

$A = \alpha +\sum a_j L_j(\tau)$
$B = \beta + \sum b_j R_j(\tau) + \sum q_j L_j(\tau)$

In this form, appeareance of any nonzero $L_j(\tau)$, $R_j(\tau)$ or $\alpha$ or $\beta$ in $C$ is strictly prohibited - it will lead to occurence of the uncancelled term divisible by $\delta$ in RHS.

The terms with $\gamma$ in numerator are also banned in $C$ for trivial reasons.

Hence, $C$ has the following form:

$C = \underset{j \in \text{priv}}\sum c_j \frac{O_j(\tau) + \beta L_j(\tau) + \alpha R_j(\tau)}{\delta} + \sum h_k \frac{Z(\tau)\tau^k}{\delta}$.

Wlog, assume that there is no linear dependencies between nonzero $L_j(\tau)$-s and $R_j(\tau)$-s (separately). If there were, we could use them to make some of the coefficients vanish, and proceed in such assumption.

Assume also wlog that in such form no linear combination of $L_j(\tau)$-s occuring in $B$ can be expressed as a sum of $R_j$-s - if it was, make such substitution in $B$ to increase the amount of vanishing coefficients, and proceed.

Now, we want to show that after such transformations $q_j = 0$, and $a_j = b_j = c_j$. Indeed, grabbing all terms with $\beta$, we see that RHS contains $\sum c_j \beta L_j(\tau)$ and LHS contains $\sum a_j L_j(\tau)$, which implies $a_j = c_j$ using the fact that we don't have non-trivial linear combinations.

Similarly, all terms with $\alpha$ yield in RHS contains $\sum c_j \alpha R_j(\tau)$, and LHS contains $\sum b_j \alpha R_j(\tau) + \sum q_j \alpha L_j (\tau)$. Due to our assumptions on absence of linear combinations, all $q_j$ are forced to vanish, $b_j = c_j$.
</details>

## UltraGroth argument

Assume, that our R1CS circuit is endowed with the additional structure. I.e., private section of the set of indices $1..n$ is separated into $d+1$ parts, $\text{round}_0$, ..., $\text{round}_d$. Additionally, some public inputs are called "challenges", and the set of challenges is separated into $d$ parts. The vector space $C^k$ will denote the space of challenges in round $k$.

Let's define the space $V^k$ as space of vectors with indices of nontrivial coeffs inside of $\text{round}_k$. The "old" witness then lives in $\underset{k}\bigoplus V^k \oplus \text{public inputs}$.

We define $k+1$-st round strategy as a function $F_k: C^k \times \underset{i \leq k}\bigoplus V^k \rightarrow V^{k+1}$

Strategy of $0$-th round is just a vector in $V^0$.

We will call a full witness the set of such strategies, for each round, which, while being used successively, succeed with overwhelming probability for random challenges.

**Definition: Algebraic witness** is a solution of R1CS over the field of rational functions on the space of challenges $\mathbb{F}_q(C)$, such that round k+1 witness depends only on challenges from rounds up to k.

Algebraic witness trivially implies the aforementioned strategy.

*It is useful to think about algebraic witnessess, but likely not so useful to work with them in practice - computations in the field of rational functions are not that friendly. I believe the mentioned above general definition in terms of strategies is a more adequate abstractions; i.e. in practice the witness to the circuit will be a bunch of functions executing some computations on the already computed part of the witness vector.*

---

Now, we will emulate the challenge responses of the verifier, using Fiat-Shamir heuristic. Let's construct the following toxic waste:

$\alpha, \beta, \gamma, \delta_0, ..., \delta_d, \tau$

and obtain the following reference string:
all as before, with $\delta$'s known in both G1 and G2, and $C_j$ for private indices being computed as for $j \in \text{round}_k:$ $C_j = \frac{O_j(\tau)+\beta L_j(\tau) + \alpha R_j (\tau)}{\delta_k}$.

Now, for each round but the last, lets assume that the prover also exposes some point $C^{(k)}$ to the verifier, and honest prover puts $C^{(k)} = \underset{j \in \text{round}_k}\sum w_j C_j + r_k [\delta_d]_1$, with $r_k$ being the blinding factor.

Verifier, then, sends the set of challenge inputs $w_j | j \in \text{chall}_{k+1}$ by setting $\text{acc}_{k+1} = \text{Hash}(\text{acc}_k, C^{(k)})$, and $w_j = \text{Hash}(j, \text{acc}_{k+1})$.

*!! Note: it is important that we can not just put challenge to be the hash of j and C^(k), without running the risk of prover retroactively rewinding previous rounds without changing C^(k), which might be possible in some cases.*

After we have run such process non-interactively, we have obtained the full witness vector $w$. We then do the same computation as in normal R1CS to obtain $H(x)$.

Honest prover, then, picks two more random values $r, s$, and sets the following:

$A = [\alpha]_1 + \underset{j}\sum w_j A_j + r \delta_d$
$B = [\beta]_2 + \underset{j}\sum w_j B_j + s \delta_d$
$IC = \underset{j \in \text{pub}}\sum w_j C_j$ - here as everywhere pub inputs include challenges
for k &lt; d as before $C^{(k)} = \underset{j \in \text{round}_k}\sum w_j C_j + r_k [\delta_d]_1$
$C^{(d)} = \underset{j \in \text{round}_d}\sum w_jC_j + \underset{s \leq n}\sum h_s Z_s + sA + rB' - \underset{k\ <\>d}\sum r_k [\delta_k]_1 - rs[\delta_d]_1$

Then, the following equation (\*) holds:

$\langle A, B \rangle = \langle \alpha, \beta \rangle + \langle IC, [\gamma]_2 \rangle + \underset{k\leq d}\sum \langle C^{(k)}, [\delta_k]_2 \rangle$

Full verification algorithm checks this equation, correctness of public input and correctness of challenges.

<details>
<summary>Why this equation holds</summary>

It is, in fact, a direct inspection. Only thing that sufficiently differs from normal Groth16 is the blinding factors. Let's see how it works: the factor $r_k \delta_d$ from $C^{(k)}$ is multiplied by $\delta_k$, which is exactly cancelled by the term $- r_k \delta_k \delta_d$ coming from $C^{(d)}$. The remaining blinding factors look exactly as in Groth16.
</details>

<details>
<summary>Zero knowledge</summary>

I claim that the honest verifier produces an uniformly random proof. Reason for this is the fact that $A, B$ and $C^{(k)}$ for k&lt;d are all equidistributed, and $C^{(d)}$ is then unique.
</details>

<details>
<summary>Soundness?</summary>

I feel a bit shaky here. Anyways, let's proceed and work in AGM + ROM for the hash. Then, we first prove the following lemma:

**Lemma:** *Any solution to equation (\*) is a valid solution to R1CS, and $C^k$'s are binding commitments to the round witnesses*.

The fact that solution to this equation in AGM leads to R1CS can be done with the following trick. Solution in AGM is solution in terms of some polynomials (i.e. treating toxic waste as variables). Let's substitute in this solution $\delta_k = \delta, \forall k$.
It is also easy to see that $C^{(k)}$ are not allowed to contain any $C_j$'s from different rounds as this leads to the uncancellable $\frac{\delta_k}{\delta_s}$ factor (it can not come from RHS because $A$ does no admit terms with nontrivial denominator, similar to the proof for normal Groth16). They might also contain some other terms, but because we don't know any linear dependencies between them, it is still a binding commitment. $\square$.

Therefore, interactive protocol of communication with verifier (which we emulate by Fiat-Shamir) can be represented as follows: prover is providing some sequence of commitments to parts of the witness, and then generates a valid zk-proof with witness it had committed to.

I am not sure if I messed up here somewhere, requires proofread / review.

</details>