# ZeroMorph

## Fundamental preliminaries

WARNING: This doc is a work in progress. It started as my personal notes but has evolved into something that might be useful for others. It is incomplete and may have errors/typos!

This document is meant to be a self contained guide to ZeroMorph, or at least the details required for its implementation. It lays out the unrolled (i.e. explicit) protocols for (1) proving and verifying a single multivariate evaluation, and (2) proving and verifying a batched evaluation, including shifts. The [ZeroMorph](https://eprint.iacr.org/2023/917) paper is excellent and can be used to fill in theoretical gaps as necessary.

Note: For now, the ZK-ification of ZM (detailed in the paper) has been left out of this document entirely.

### Notation
In nearly all cases, the notation herein matches that of the ZeroMorph paper.

We denote $\Phi_n(X) = \sum_{i=0}^{2^n-1}X^i$. The evaluation $\Phi_n(x)$ is simply a geometric series and can be efficiently computed as $$\Phi_n(x) = \frac{x^{2^n} - 1}{x - 1}$$

$U_n$ is the univariatization map. (I'll drop the $n$ and use $U$). It's defined formally in the paper but it's essentially the map from the coefficients of a multilinear polynomial in the multilinear lagrange basis to the coefficients of a univariate polynomial in the monomial basis. (In implementation, there is no map, just two different ways of interpreting a vector of coefficients).

$U^{<2^k}$ is $U$ with the additional action of truncating the result after the first $2^k$ coefficients.

Univariate polynomials are generally, but not always, wearing hats. Like this: $\hat{f}$.

### The ZeroMorph identity
Standard univariate KZG leverages the fact that for univariate $f$, $f(u) = v$ if and only if there exists univariate $q$ such that $$f(X) - v = (X - u)q(X)$$

ZeroMorph is based on the multivariate analog: $f({\bf u}) = v$ $\iff \exists \, q_k$ such that $$f(X_0,\dots,X_{n-1}) - v = \sum_{k=0}^{n-1}(X_k - u_k)q_k(X_0,\dots,X_{k-1})$$

An efficient algorithm for iteratively computing the $q_k$ is provided in the paper, but they can be computed explicitly as $$q_k = f(X_0,\dots,X_{k-1},u_k+1,u_{k+1},\dots,u_{n-1}) - f(X_0,\dots,X_{k-1},u_k,u_{k+1},\dots,u_{n-1})$$

The univariatization map $U$ takes the evaluations of a multilinear polynomial $f = f(X_0,\dots,X_{n-1})$ on the hypercube $\{0,1\}^n$ to the coefficients of a univariate polynomial $\hat{f} = \hat{f}(X)$ expressed in the monomial basis. Applying the univariatization map $U$ to the multivariate KZG identity gives $$U(f) - U(v) = \sum_{k=0}^{n-1}U(X_kq_k) - u_kU(q_k)$$

This expression can be simplified via the following useful identities established in the paper: $$U(a) = a\cdot U(1) = a\cdot\Phi_n(X)$$ $$U(X_kq_k) = X^{2^k}\Phi_{n-k-1}\left(X^{2^{k+1}}\right)U(q_k)^{<2^k}$$ $$U(q_k) = \Phi_{n-k}(X^{2^k})U(q_k)^{<2^k}$$

Denoting by $\hat{f}$ and $\hat{q}_k$ the univariatizations $U(f)$ and $U(q_k)^{<2^k}$ and applying the above identities yields what we'll call the *ZeroMorph identity*: $$\hat{f} - v\cdot\Phi_n(X) = \sum_{k=0}^{n-1}\left(X^{2^k}\Phi_{n-k-1}\left(X^{2^{k+1}}\right) - u_k\cdot\Phi_{n-k}\left(X^{2^k}\right)\right)\hat{q}_k$$

This identity, in conjuction with a degree check protocol, will allow us to efficiently prove evaluations of multilinear polynomials.

### Degree checks

Degree checks in ZeroMorph are based on the following simple fact: If the srs used to commit to polynomials has $N_{max}$ group-1 elements, it is not possible to commit to a polynomial of degree $\geq N_{max}-1$. If we want to prove that a univariate polynomial $f$ has $\text{deg}(f) \leq D$, all we have to do is prove that we can commit to $X^{N_{max} - D - 1}f(X)$.

Degree checks can easily be combined with KZG evaluation proofs. Say for example we want to prove simultaneously that $f(u) = v$ and $\text{deg}(f) \leq D$. The relevant identity is simply the standard KZG identity multiplied by $X^{N_{max} - D - 1}$ to obtain $$X^{N_{max} - D - 1}(f - v) = X^{N_{max} - D - 1}(X - u)q$$

This validity of the claim can be established via the usual pairing check modified in a corresponding way.

## Unrolled ZM protocol for evaluating a single multilinear polynomial (instatiated with KZG)

### Prover

#### Step 0: Commitment to and evaluation of $f$
- Note: in practice we commit to $f$ prior to Sumcheck, and the evaluation $v=f(\textbf{u})$ is an output of Sumcheck.
- Commit to $U(f) = \hat{f}$ and compute evaluation $v = f(\textbf{u})$
- Output: Commitment $C_f = [\hat{f}]_1$, and evaluation $v$

#### Step 1: Commitments to $f$ and $q_k$

- Compute the multivariate quotients $q_k(X_0,\dots,X_{k-1})$
- :::info
:::spoiler
Given a multilinear $f$, the $q_k$ may be computed as $$q_k = f(X_0,\dots,X_{k-1},u_k+1,u_{k+1},\dots,u_n) - f(X_0,\dots,X_{k-1},u_k,u_{k+1},\dots,u_n).$$ The paper details an efficient scheme for computing these iteratively but one can also compute them naively using the above formula.
:::
- Commit to the restrictions $U_n(q_k)^{<2^k} = \hat{q}_k$.
- :::info
:::spoiler
The univariates $U_n(q_k)$ do not have degree $2^k-1$, but rather $2^n-1$. However, the coefficients of $U_n(q_k)$ are $2^k$-periodic, so the truncation $U_n(q_k)^{<2^k}$ is constructing the degree $2^k-1$ polynomial from one period's worth of coefficients.
:::
- Output: Commitments $\{C_{\hat{q}_k} = [\hat{q}_k]_1\}_{k=0}^{n-1}$

#### Step 2:
- Challenge: $y$
- Construct and commit to the batched lifted degree polynomial $$\hat{q} = \sum_{k=0}^{n-1}y^kX^{N-d_k-1}\hat{q}_k, \,\,\, d_k = \textrm{deg}(\hat{q}_k)$$
- :::info
:::spoiler
The goal here is to allow for the degree checks on $q_k$ to be batched into one degree check on $\hat{q}$, which will in turn be batched with other degree checks. Note that $\textrm{deg}(\hat{q}) = N-1$, since $\textrm{deg}(X^{N-d_k-1}\hat{q}_k) = N-1$. Note, however, that the degree of $\hat{q}_k$ is $2^k-1$, and thus the largest degree is $2^{n-1}-1$ or $N/2-1$. If we were only interested in degree checking the quotients $q_k$ in isolation, we could construct $\hat{q}$ to have degree $N/2-1$, instead of $N-1$. We lift all the way to $N-1$ simply because we want to batch the degree check on $\hat{q}_k$ with a degree check on another polynomial ($Z_x$, introduced later) whose degree is $N-1$. Importantly, the cost of committing to $\hat{q}$ is still only proportional to $N/2$, since it's first $N/2$ coefficients are zero.
:::
- Output: $C_{\hat{q}}$

#### Step 3:
- Challenges: $x, z$. (Respectively for for partial evaluation and batching).
- Compute the partially evaluated univariate degree check polynomial $\zeta_x$
$$\zeta_x = \hat{q} - \sum_{k=0}^{n-1}y^kx^{N-d_k-1}\hat{q}_k$$ and the partially evaluated univariate ZeroMorph polynomial $$Z_x = \hat{f} - v\cdot\Phi_n(x) - \sum_{k=0}^{n-1}\left(x^{2^k}\Phi_{n-k-1}(x^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot \hat{q}_k$$
- :::info
:::spoiler
By construction, $\zeta_x(x) = 0$ and $Z_x(x) = 0$. We do not constuct $Z(X)$ and $\zeta(X)$ explicitly (by construction they are just the 0 polynomial), only their partial evaluations.
:::
- :::info
:::spoiler
We compute $\Phi_{n-k-1}(x^{2^{k+1}})$ and $\Phi_{n-k}(x^{2^k})$ efficiently via
- $$\Phi_{n-k-1}(x^{2^{k+1}}) = \frac{(x^{2^{k+1}})^{2^{n-k-1}}-1}{x^{2^{k+1}}-1} = \frac{x^{2^n}-1}{x^{2^{k+1}}-1}$$
- $$\Phi_{n-k}(x^{2^k}) = \frac{(x^{2^k})^{2^{n-k}}-1}{x^{2^k}-1} = \frac{x^{2^n}-1}{x^{2^k}-1}$$
:::
- Compute quotients $q_\zeta = \zeta_x/(X-x)$, and $q_Z = Z_x/(X-x)$
- :::info
:::spoiler
These quotients have degree $N-2$ since we're dividing a degree $N-1$ polynomial by the degree 1 monomial $(X-x)$. When we multiply by $X^{N_{max}-(N-1)}$ on the next step, we get something of degree $N_{max}-(N-1) + (N-2) = N_{max}-1$, i.e. the maximum degree of a polynomial that can be committed to with an SRS with $N_{max}$ elements.
:::
- Compute the batched evaluation/degree-check proof $\pi = [\left(q_\zeta + z\cdot q_Z\right) X^{N_{max}-(N-1)}]_1$
- :::info
:::spoiler
This proof establishes that $\hat{q}$ and the $\hat{q}_k$ are well formed and that $\textrm{deg} (\zeta + zZ) \leq 2^n-1$, which in turn implies $\textrm{deg}(\hat{q}_k) \leq 2^k-1$, and $\hat{f}, \hat{q}$ have degree $\leq N-1$.

Note: A natural quesiton is why are no similar degree checks needed in Gemini? The answer is that the degree of polynomials is established via opening the final folded polynomial (which is a constant) and showing that the folded polynomials were well formed. Tohru and I discussed the possibility that something similar could be done in the context of ZM. He was not optimistic but it seems worth further consideration.
:::
- Output: $\pi$

### Verifier

#### Step 0:
- Receive: $C = [f]_1$, $v$

#### Step 1:
- Receive: $\{C_{q_k} = [q_k]\}_{k=0}^{n-1}$
- Challenge: y

#### Step 2:
- Receive: $C_{\hat{q}}$
- Challenges: $x, z$
- Compute commitment $C_{v,x}$ = $v\cdot \Phi_n(x)\cdot [1]_1$
- Compute $$C_{\zeta_x} = C_{\hat{q}} - \sum_{k=0}^{n-1}y^kx^{2^n-d_k-1}C_k$$
- Compute commitment to partially evaluated polynomial $Z_x$ as $$C_{Z_x} = C - C_{v,x} - \sum_{k=0}^{n-1}\left(x^{2^k}\Phi_{n-k-1}(x^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot C_k$$
- Compute batched commitment $$C_{\zeta, Z} = C_{\zeta_x} + z\cdot C_{Z_x}$$
- Receive commitment $\pi$
- Check: $$e\left(\pi, [X]_2 - x\cdot[1]_2\right) = e\left(C_{\zeta, Z}, \left[X^{N_{max}-2^n-1}\right]_2 \right)$$ or equivalently (e.g. see plonk paper) $$e\left(C_{\zeta, Z} - x\cdot\pi, \left[X^{N_{max}-2^n-1}\right]_2 \right)\cdot e\left(-\pi, [X]_2\right) = 1$$

## Full Batched ZeroMorph

### Batched ZeroMorph

Say we want to prove evaluations of $m$ multilinear polynomials $f_i$ at the single challenge $\textbf{u}$. It turns out, we can simply batch these polynomials together using a challenge $\rho$ to form a single polynomial $f$, i.e. $$f = \sum_{i=0}^{m-1}\rho^i f_i + \sum_{i=0}^{l-1}\rho^{m+i} h_i$$ then proceed with the protocol described earlier for proving evaluation of a single multilinear polynomial. The ZeroMorph identity partially evaluated at challenge $x$ is still of the form $$Z_x = \hat{f} - v\cdot\Phi_n(x) - \sum_{k=0}^{n-1}\left(x^{2^k}\Phi_{n-k-1}(x^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot \hat{q}_k$$

This can be thought of as the batching of $m$ individual $Z_{x,i}$, which works because $$v = f(\textbf{u}) = \sum_{i=0}^{m-1}\rho^i v_i$$ and $$\hat{q}_k = \sum_{i=0}^{m-1}\rho^i \hat{q}_{f_i,k}$$

This latter identity also suggests that the prover need only compute the $q_k$ for the batched polynomial $f$, not individually for each $f_i$. The prover evaluates and commits to the individual $f_i$, and the verifier reconstructs $C = [f]_1$ as $$C = [f]_1 = \sum_{i=0}^{m-1}\rho^i [f_i]_1$$

The protocol is otherwise idenitical to the simple case of a single polynomial $f$.

### Batched ZeroMorph with Shifts

Extending the above batching scheme to allow for proving evaluations of shifts is also quite simple. Assume that in addition to the $m$ multilinear polynomials $f_i$ with $f_i(\textbf{u}) = v_i$, we also want to prove evaluation of $l$ multilinear polynomials $h_i$, with $h_i(\textbf{u}) = w_i$. The $h_i$ are the left-shift-by-one of polynomials $g_i$, which are assumed to be a subset of the $f_i$. If we were willing to commit to the shifts $h_i$, there is nothing to do; the protocol is identical to the batched protocol outlined above, now with $m + l$ polynomials.

However, since by committing to the $f_i$, we automatically have the commitments to $g_i$, we instead seek to use $[g_i]$ to prove evaluations of $h_i$. We can do this by making a small change to the ZeroMorph identity. Construct a batched polynomial $f$ as follows $$f = \sum_{i=0}^{m-1}\rho^i f_i + \sum_{i=0}^{l-1}\rho^{m+i} h_i$$

The ZeroMorph identity can then be written as $$\sum_{i=0}^{m-1}\rho^i \hat{f}_i + \sum_{i=0}^{l-1}\rho^{m+i} \hat{h}_i - v\cdot\Phi_n(x) = \sum_{k=0}^{n-1}\left(X^{2^k}\Phi_{n-k-1}(X^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(X^{2^k})\right)\cdot \hat{q}_k$$

We can remove $h_i$ from this expression in favor of $g_i$ by simply multiplying by $X$ to obtain $$X\cdot\sum_{i=0}^{m-1}\rho^i \hat{f}_i + \sum_{i=0}^{l-1}\rho^{m+i} \hat{g}_i - v\cdot X\cdot\Phi_n(x) = X\cdot\sum_{k=0}^{n-1}\left(X^{2^k}\Phi_{n-k-1}(X^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(X^{2^k})\right)\cdot \hat{q}_k$$

:::info
:::spoiler
If a polynomial $\hat{g}$ is represented by coefficients $(a_0,\dots , a_{N-1})$, then its shift (left-shift-by-one) $\hat{h}$ is given by $(a_1,\dots , a_{N-1}, a_0)$. Therefore, we have the identity $$X\hat{h} = \hat{g} + a_0 - a_0X^{N}.$$ If $a_0 = 0$ this reduces to simply $X\hat{h} = \hat{g}$.
:::

And that's it. The partially evaluated polynomial $Z_x$ is now given by $$Z_x = x\cdot\sum_{i=0}^{m-1}\rho^i \hat{f}_i + \sum_{i=0}^{l-1}\rho^{m+i} \hat{g}_i - v\cdot x\cdot\Phi_n(x) - x\cdot\sum_{k=0}^{n-1}\left(x^{2^k}\Phi_{n-k-1}(x^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot \hat{q}_k$$

Note that the commitment to $Z_x$ can be computed by the verifier given the $m + l$ commitments $[f_i]_1, [g_i]_1$.

## Full Unrolled Protocol for Batched Evaluations

The following is the protocol for proving evaluations using ZeroMorph of evaluations at $\textbf{u}$ of multilinear polynomials $f_0,\dots,f_{m-1}$ and $h_0,\dots,h_{l-1}$. We denote by $h_i$ the left-shift by one of $g_i$ (interpreted as univariates).

### Prover

#### Step 0:
- Compute commitments $C_0,\dots,C_{m-1}$ and $D_0,\dots,D_{l-1}$ to $f_0,\dots,f_{m-1}$ and $g_0,\dots,g_{l-1}$.
- Note: In practice the $D_i$ are a subset of the $C_i$
- Output: Commitments $\{C_i\}_{i=0}^{m-1}, \{D_i\}_{i=0}^{l-1}$ and evaluations $\{v_i\}_{i=0}^{m-1}, \{w_i\}_{i=0}^{l-1}$

#### Step 1:
- Challenge: $\rho$
- Compute $f$ and its evaluation $v = f(\textbf{u})$ as $$f = \sum_{i=0}^{m-1}\rho^i f_i + \sum_{i=0}^{l-1}\rho^{m+i} h_i, \,\,\, v = \sum_{i=0}^{m-1}\rho^i v_i + \sum_{i=0}^{l-1}\rho^{m+i} w_i$$
- Compute the multivariate quotients $q_k(X_0,\dots,X_{k-1})$ such that $$f - v = \sum_{k=0}^{n-1}(X_k - u_k)q_k$$
- Compute the commitments $C_{\hat{q}_k}$ to the restrictions $U_n(q_k)^{<2^k} = \hat{q}_k$.
- Output: Commitments $\{C_{\hat{q}_k}\}_{k=0}^{n-1}$

#### Step 2:
- Challenge: $y$
- Construct and commit to the batched lifted degree polynomial $$\hat{q} = \sum_{k=0}^{n-1}y^kX^{N-d_k-1}\hat{q}_k, \,\,\, d_k = \textrm{deg}(\hat{q}_k)$$
- Output: Commitments $C_{\hat{q}}$

#### Step 3:
- Challenges: $x, z$.
- Compute the partially evaluated univariate degree check polynomial $\zeta_x$
$$\zeta_x = \hat{q} - \sum_{k=0}^{n-1}y^kx^{N-d_k-1}\hat{q}_k$$ and the partially evaluated univariate ZeroMorph polynomial $$Z_x = x\cdot\sum_{i=0}^{m-1}\rho^i \hat{f}_i + \sum_{i=0}^{l-1}\rho^{m+i} \hat{g}_i - v\cdot x\cdot\Phi_n(x) - x\cdot\sum_{k=0}^{n-1}\left(x^{2^k}\Phi_{n-k-1}(x^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot \hat{q}_k$$
- Compute quotients $q_\zeta = \zeta_x/(X-x)$, and $q_Z = Z_x/(X-x)$
- Compute the batched evaluation/degree-check proof $\pi = [\left(q_\zeta + z\cdot q_Z\right) X^{N_{max}-(N-1)}]_1$
- Output: $\pi$

### Verifier

#### Step 0:
- Receive: Commitments $\{C_i\}_{i=0}^{m-1}, \{D_i\}_{i=0}^{l-1}$ and evaluations $\{v_i\}_{i=0}^{m-1}, \{w_i\}_{i=0}^{l-1}$

#### Step 1:
- Challenge: $\rho$
- Construct batched evaluation $v = \sum_{i=0}^{m-1}\rho^i v_i + \sum_{i=0}^{l-1}\rho^{m+i} w_i$
- Receive: Commitments $\{C_{\hat{q}_k}\}_{k=0}^{n-1}$

#### Step 2:
- Challenge: y
- Receive: Commitment $C_{\hat{q}}$

#### Step 3:
- Challenges: $x, z$
- Compute commitment $C_{v,x}$ as $v\cdot x\cdot \Phi_n(x)\cdot [1]_1$
- Compute commitment to partially evaulated $\zeta_x$ as $$C_{\zeta_x} = C_{\hat{q}} - \sum_{k=0}^{n-1}y^kx^{2^n-d_k-1}C_{\hat{q}_k}$$
- Compute commitment to partially evaluated polynomial $Z_x$ as $$C_{Z_x} = x\cdot\sum_{i=0}^{m-1}\rho^i C_i + \sum_{i=0}^{l-1}\rho^{m+i} D_i - C_{v,x} - x\cdot\sum_{k=0}^{n-1}\left(x^{2^k}\Phi_{n-k-1}(x^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot C_{\hat{q}_k}$$
- Compute batched commitment $$C_{\zeta, Z} = C_{\zeta_x} + z\cdot C_{Z_x}$$
- Pairing check: $$e\left(\pi, [X]_2 - x\cdot[1]_2\right) = e\left(C_{\zeta, Z}, \left[X^{N_{max}-2^n-1}\right]_2 \right)$$

### Note about the degree check
Since we do not yet have an SRS (faked or genuine) with the G2 elements needed for ZeroMorph, I have not implemented the final stage of the degree check. Specifically, this means that the proof input $\pi$ to the final pairing check is given by $\pi = [\left(q_\zeta + z\cdot q_Z\right)]_1$ instead of the shifted version $\pi = [\left(q_\zeta + z\cdot q_Z\right) X^{N_{max}-(N-1)}]_1$, and the pairing is performed accordingly as $$e\left(C_{\zeta, Z} - x\cdot\pi, [1]_2 \right)\cdot e\left(-\pi, [X]_2\right) = 1$$ instead of $$e\left(C_{\zeta, Z} - x\cdot\pi, \left[X^{N_{max}-2^n-1}\right]_2 \right)\cdot e\left(-\pi, [X]_2\right) = 1$$

Completing this final step amounts to faking an SRS with known toxic waste $\tau$. Then $\left[X^{N_{max}-2^n-1}\right]_2$ can be computed as $\tau^{N_{max}-2^n-1}\cdot[1]_2$. From here it should be straightforward to shift the final batched quotient and update the pairing to use $\left[X^{N_{max}-2^n-1}\right]_2$ instead of $[1]_2$.

Currently, we perform the pairing check via a call like this:

reduced_ate_pairing_batch_precomputed({P_0, P_1}, {Q_0_lines, Q_1_lines}, 2)

where $P_0,P_1$ are the G1 elements and $Q_0,Q_1$ are the G2 elements in the pairing check above. The "lines" are a precomputable efficiency detail stemming from the fact that our G2 points have historically been fixed ($[1]_2$ and $[X]_2$). (Presumably we could still precompute these for $[X^{N_{max}-2^n-1}]_2$ given a fixed set of circuit sizes $n$). We can use this same method if we compute the miller lines for the appropriate monomial commitment. We could also simply use

reduced_ate_pairing_batch({P_0, P_1}, {Q_0, Q_1}, 2)

which takes the points directly without assuming precomputed data.