# 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:
```cpp
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
```cpp!
reduced_ate_pairing_batch({P_0, P_1}, {Q_0, Q_1}, 2)
```
which takes the points directly without assuming precomputed data.

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up