# Zeromorph ## Introduction Aztec uses [Sumcheck](https://fractalyze.gitbook.io/intro/~/revisions/0AAov1j5GF4J6Ca62R1w/primitives/sumcheck) to prove the proof of **circuit satisfiability**. In Sumcheck, a multilinear polynomial is used. Therefore, it is necessary to efficiently commit to and open this multilinear polynomial. Additionally, since Aztec is a privacy-focused Layer 2, an efficient way to achieve zero-knowledge (ZK) is also required. To address this, Aztec introduces a method called Zeromorph, which is currently implemented in [Aztec Zeromorph](https://github.com/AztecProtocol/aztec-packages/tree/98cd1bb/barretenberg/cpp/src/barretenberg/commitment_schemes/zeromorph). ## Background ### KZG 1. $$\mathsf{KZG.Setup}(1^\lambda, N\_{\mathsf{max}}) \rightarrow (\[1]\_1, \[s]*1, \dots, \[s^{N*{\mathsf{max}}}]\_1, \[1]\_2, \[s]\_2)$$ 2. $$\mathsf{KZG.Commit}(f \in F\[X]^{N\_{\mathsf{max}}}) \rightarrow C = \[f(s)]\_1$$ 3. $$\mathsf{KZG.ProveEval}(f, z, v) \rightarrow W = \left\[\frac{f(s) - v}{s - z}\right]\_1$$ 4. $$\mathsf{KZG.VerifyEval}(C, W, z, v) \rightarrow b \in {0, 1}$$: The verifier checks the following equation: $$ e(C - \[v]\_1, \[1]\_2) \stackrel{?}=e(W, \[s]\_2 - \[z]\_2) $$ Here, the verifier learns the information $$(C, W, v)$$, which presents two issues: 1. Since KZG is a **computationally hiding commitment**, if quantum computing becomes feasible, revealing $$(C, W)$$ may no longer satisfy the ZK property. 2. While it proves **circuit satisfiability**, it also reveals information of the polynomial with $$P(z) = v$$. ### Hiding KZG Instead of the naive KZG scheme outlined above, Zeromorph uses a more secure variant named "Hiding KZG." #### $$\mathsf{HidingKZG.Setup}(1^\lambda, N\_{\mathsf{max}}) \rightarrow (\[1]\_1, \[s]\_1, \dots, \[s^{N{\mathsf{max}}}]\_1, \[\xi]\_1, \[1]\_2, \[s]\_2, \[\xi]\_2)$$ #### $$\mathsf{HidingKZG.Commit}(f \in \mathsf{F}\[X]^{\ 1$$, $$f$$ is divided by $$(X\_{n-1} - z\_{n-1})$$ results in quotient $$q\_{n-1}$$ with remainder $$f(X\_0, \dots, X\_{n-2}, z\_{n-1})$$ as follows: $$ f(X\_0, \dots, X\_{n-1}) = (X\_{n-1} - z\_{n-1})q\_{n-1} + f(X\_0, \dots, X\_{n-2}, z\_{n-1}) $$ The polynomial $$f(X\_0, \dots, X\_{n-1}) - f(X\_0, \dots, X\_{n-2}, z\_{n-1})$$ has a degree of at most 1 in all variables. Therefore, $$q\_{n-1}$$ must have a degree of at most 1 in $$X\_0, \dots, X\_{n-2}$$, and a degree of at most 0 in $$X\_{n-1}$$. This implies $$q\_{n-1} \in \mathbb{F}\[X\_0, \dots ,X\_{n-2}]^{\le1}$$. Using this information and recursive decomposition, we derive the following: $$ f(X\_0, \dots, X\_{n-2}, z\_{n-1}) = (X\_{n-2} - z\_{n-2})q\_{n-2} + f(X\_0, \dots, X\_{n-3}, z\_{n-2}, z\_{n-1}) \\ \dots \\ f(X\_0, z\_1, \dots z\_{n-1}) = (X\_0 - z\_0) q\_0 + f(z\_0, \dots, z\_{n-1}) $$ Iteratively substituting all the equations above yields: $$ f = \sum\_{i=0}^{n-1}(X\_i - z\_i)q\_i + f(z\_0, \dots, z\_{n-1}) $$ Therefore, by equation $$(1)$$, we confirm $$f(z\_0, \dots, z\_{n-1}) = f(\bm{z}) =v$$. #### **Computing** $$q\_i$$ According to [**Lemma 2.3.1**](https://eprint.iacr.org/2023/917.pdf#page=9\&zoom=100,180,400) in [the Zeromorph paper](https://eprint.iacr.org/2023/917.pdf), $$q\_i$$ can be computed as: $$ q\_i = f(X\_0, \dots, X\_{i-1}, z\_i + 1, z\_{i+1}, \dots, z\_{n-1}) - f(X\_0, \dots, X\_{i-1}, z\_i, z\_{i+1}, \dots, z\_{n-1}) $$ **Example:** Let's calculate $$q\_1$$, the quotient from dividing $$f(X\_0, X\_1, z\_2)$$ by $$(X\_1 - z\_1)$$: $$ q\_1 = f(X\_0, z\_1 + 1, z\_2) - f(X\_0, z\_1, z\_2) $$ $$f(X\_0, z\_1 + 1, z\_2)$$ will be evaluated as follows: $$ \begin{align\*}f(X\_0, z\_1 + 1, z\_2) = c\_0X\_0(z\_1 + 1)z\_2 + c\_1X\_0(z\_1 + 1) + c\_2X\_0z\_2 + c\_3(z\_1 + 1)z\_2 + c\_4X\_0 + c\_5(z\_1 + 1) + c\_6z\_2 + c\_7 && (a)\end{align\*} $$ $$f(X\_0, z\_1, z\_2)$$ will be evaluated as follows: $$ \begin{align\*}f(X\_0, z\_1, z\_2) = c\_0X\_0z\_1z\_2 + c\_1X\_0z\_1 + c\_2X\_0z\_2 + c\_3z\_1z\_2 + c\_4X\_0 + c\_5z\_1 + c\_6z\_2 + c\_7 && (b)\end{align\*} $$ Subtracting equation $$(b)$$ from equation $$(a)$$ allows us to compute $$q\_1$$ as the following: $$ \begin{aligned} f(X\_0, z\_1 + 1, z\_2) - f(X\_0, z\_1, z\_2) &= c\_0X\_0(z\_1 + 1)z\_2 + c\_1X\_0(z\_1 + 1) + c\_2X\_0z\_2 + c\_3(z\_1 + 1)z\_2 \\ &\quad + c\_4X\_0 + c\_5(z\_1 + 1) + c\_6z\_2 + c\_7 \\ &\quad - c\_0X\_0z\_1z\_2 - c\_1X\_0z\_1 - c\_2X\_0z\_2 - c\_3z\_1z\_2 \\ &\quad - c\_4X\_0 - c\_5z\_1 - c\_6z\_2 - c\_7 \\ &= c\_0X\_0z\_2 + c\_1X\_0 + c\_3z\_2 + c\_5. \end{aligned} $$ Now we can see that $$f(X\_0, X\_1, z\_2)$$ can be decomposed as the following: $$ \begin{align\*} f(X\_0, X\_1, z\_2) &= (X\_1 - z\_1) \underbrace{(c\_0X\_0z\_2 + c\_1X\_0 + c\_3z\_2 + c\_5)}\_{q\_1 } + f(X\_0, z\_1, z\_2) \\ \end{align\*} $$ The validity of this statement can be ensured by multiplying all terms out $$ \begin{align\*} f(X\_0, X\_1, z\_2) &= c\_0X\_0X\_1z\_2 + c\_1X\_0X\_1 + c\_3X\_1z\_2 + c\_5X\_1 \\ &\quad - c\_0X\_0z\_1z\_2 - c\_1X\_0z\_1 - c\_3z\_1z\_2 - c\_5z\_1 \\ &\quad + c\_0X\_0z\_1z\_2 + c\_1X\_0z\_1 + c\_2X\_0z\_2 + c\_3z\_1z\_2 \\ &\quad + c\_4X\_0 + c\_5z\_1 + c\_6z\_2 + c\_7 \\ &= c\_0X\_0X\_1z\_2 + c\_1X\_0X\_1 + c\_2X\_0z\_2 + c\_3X\_1z\_2 \\ &\quad + c\_4X\_0 + c\_5X\_1 + c\_6z\_2 + c\_7. \end{align\*} $$ #### **Verifying the Multilinear Polynomial Identity** Verifying equation $$(1)$$ requires $$n$$ pairing operations, which imposes a computational overhead on the verifier: $$ e(\[f(s\_0, \dots, s\_{n-1})]\_1 - \[v]*1,\[1]*2) \stackrel{?}= \prod*{i = 0}^{n-1} e(\[q\_i(s\_0, \dots, s*{i-1})]\_1, \[s\_i]\_2 - \[z\_i]\_2) $$ Additionally, $$q\_i \in \mathbb{F}\[X\_0, \dots ,X\_{i-1}]^{\le1}$$ must be verified, which will be checked using the [**degree check protocol**](#degree-check-protocol) introduced later. ## Protocol Explanation ### Multilinear Polynomial Identity using Univariate PCS To efficiently verify the multilinear polynomial identity, we first define the following mapping: $$ \mathcal{U}*n: \mathbb{F}\[X\_0, \dots, X*{n-1}]^{\le1} \rightarrow \mathbb{F}\[X]^{<2^n} $$ Given $$f(\bm{X})$$ defined as: $$ f(\bm{X}) := \sum\_{\bm{b} \in {0, 1}^n}v\_{\bm{b}} \cdot \mathsf{\widetilde{eq}}(\bm{X}, \bm{b}) $$ the function $$\mathcal{U}\_n(f)$$ transforms the following expression: $$ \mathsf{\widetilde{eq}}(\bm{X}, \bm{b}) =\prod\_{i = 0}^{n-1} (b\_i X\_i +(1-b\_i)(1 - X\_i)) \rightarrow \prod\_{i=0}^{n-1} \left(X^{2^i}\right)^{b\_i} $$ This seemingly expensive operation actually introduces no computational overhead. This is because the witness generation process for constructing a ZK proof already outputs polynomial evaluations, making this mapping essentially free. If $$f = c \in \mathbb{F}$$ is a constant function, we can compute: $$ \mathcal{U}\_n(f) = c \cdot \Phi\_n(X) $$ where $$\Phi\_n(X)$$ is defined as: $$ \Phi\_n(X) :=\sum\_{i = 0}^{2^n - 1}X^i $$ This satisfies the following equation, meaning that evaluating $$\Phi\_n(X)$$ at any point $$x$$ requires only $$n + 1$$ multiplications and $$2$$ additions: $$ \Phi\_n(X) = \frac{X^{2^n} - 1}{X - 1} $$ For example, if $$n = 2$$, we can compute: $$ \mathcal{U}\_2(f) = f(0, 0) + f(1, 0)X + f(0, 1)X^2 + f(1, 1)X^3 $$ Applying this mapping to both sides of equation $$(1)$$, we transform it into: $$ \begin{align\*} \mathcal{U}\_n(f) - v \cdot \mathcal{U}*n(1) = \sum*{i=0}^{n-1}\mathcal{U}\_n(X\_iq\_i)- z\_i \cdot \mathcal{U}\_n(q\_i) && (2) \end{align\*} $$ Since $$\mathcal{U}\_n(f)$$ is a linear isomorphism, satisfying equation $$(2)$$ implies equation $$(1)$$ is also satisfied. Instead of using a multilinear PCS to commit to $$f$$, we can now use a univariate PCS via $$\mathcal{U}\_n(f)$$. Next, we analyze how the verifier can efficiently verify the claim. The prover will commit to $$\mathcal{U}\_n(f)$$ and $$\mathcal{U}\_n(q\_i)$$, while $$\mathcal{U}\_n(1) = \Phi\_n(X)$$ can be easily computed. The key question now is: how can we efficiently compute $$\mathcal{U}\_n(X\_iq\_i)$$? By [**Lemma 2.5.2**](https://eprint.iacr.org/2023/917.pdf#page=11\&zoom=100,180,669), let $$\hat{f} \in \mathbb{F}^{\le2^n -1}$$ and define $$f := \mathcal{U}*n^{-1}\left(\hat{f}\right)$$. For $$0 \le i < n$$, if $$f \in \mathbb{F}\[X\_0, \dots, X*{i-1}]^{\le 1}$$, then $$\hat{f}(X) = \Phi\_{n-i}\left(X^{2^i} \right) \hat{f}^{<2^i}$$, where $$\hat{f}^{<2^i} =\mathcal{U}\_i(f)$$. For example, if $$i = 2, n = 3$$ and $$f = 2X\_0 + X\_1 + 0X\_2$$​, then $$\mathcal{U}\_3(f)$$ can be computed as: $$ \begin{align\*} \mathcal{U}*3(f) &= \textcolor{red}{f(0, 0, 0) + f(1, 0, 0) X + f(0,1,0)X^2 + f(1,1,0) X^3} + f(0, 0, 1)X^4 + f(1,0,1)X^5 + f(0,1,1)X^6 + f(1,1,1)X^7 \\ &= \textcolor{red}{0 + 2X + 1X^2 + 3X^3} + 0X^4 + 2X^5 + 1X^6 + 3X^7 \ &= \underbrace{(X^4 + 1)}*{\Phi\_1(X^4)}\underbrace{\textcolor{red}{(0 + 2X + 1X^2 + 3X^3)}}\_{ \mathcal{U}\_2(f)^{<4}} \end{align\*} $$ By [**Lemma 2.5.3**](https://eprint.iacr.org/2023/917.pdf#page=12\&zoom=100,180,565), if $$f \in \mathbb{F}\[X\_0, \dots, X\_{i-1} ]^{\le1}$$, we can compute: $$ \mathcal{U}\_n(X\_if) = \frac{X^{2^i}}{X^{2^i} + 1}\mathcal{U}\_n(f) $$ For example, if $$i = 2, n = 3$$, and $$f = 2X\_0 + X\_1$$​, then multiplying by $$X\_2$$​ gives $$f' = X\_2f = 2X\_0X\_2 + X\_1X\_2$$. Thus, when $$X\_2 = 0$$, both $$f$$ and $$f'$$ evaluate to 0. When $$X\_2 = 1$$, $$f'$$ takes the same value as $$f$$. $$ \begin{align\*} \mathcal{U}*3(f') &= f'(0, 0, 0) + f'(1, 0, 0) X + f'(0,1,0)X^2 + f'(1,1,0) X^3 + f'(0, 0, 1)X^4 + f'(1,0,1)X^5 + f'(0,1,1)X^6 + f'(1,1,1)X^7 \\ &= f(0, 0, 1)X^4 + f(1,0,1)X^5 + f(0,1,1)X^6 + f(1,1,1)X^7 \\ &= \frac{X^4}{X^4 + 1}\underbrace{\left({f(0, 0, 0) + f(1, 0, 0) X + f(0,1,0)X^2 + f(1,1,0) X^3} + f(0, 0, 1)X^4 + f(1,0,1)X^5 + f(0,1,1)X^6 + f(1,1,1)X^7\right)}*{\mathcal{U}\_3(f)} \end{align\*} $$ Applying [**Lemma 2.5.3**](https://eprint.iacr.org/2023/917.pdf#page=12\&zoom=100,180,565) to equation $$(2)$$, we transform it into: $$ \begin{align\*} \mathcal{U}\_n(f) - v \cdot \mathcal{U}*n(1) = \sum*{i=0}^{n-1}\left(\frac{X^{2^i}}{X^{2^i} + 1}- z\_i\right) \mathcal{U}\_n(q\_i) && (3) \end{align\*} $$ At this stage, the verifier must check whether $$q\_i \in \mathbb{F}\[X\_0, \dots, X\_{i-1} ]^{\le1}$$. We can verify this using $$\mathcal{U}\_n(q\_i) \in \mathbb{F}\[X]^{<2^i}$$ through a **degree check protocol**. by substituting **Lemma 2.5.2** into equation $$(3)$$, which results in: $$ \begin{align\*} \mathcal{U}*n(f) - v \cdot \mathcal{U}*n(1) = \sum*{i=0}^{n-1}\left(\frac{X^{2^i}}{X^{2^i} + 1}- z\_i\right) \Phi*{n-i}\left(X^{2^i}\right)\mathcal{U}\_n(q\_i)^{<2^i} && (4) \end{align\*} $$ Since $$\Phi\_{n-i}\left(X^{2^i}\right)$$ is defined as: $$ \begin{align\*} \Phi\_{n-i}\left(X^{2^i}\right) &= 1 + X^{2^i} + \left(X^{2^i}\right)^2 + \dots + \left(X^{2^i}\right)^{2^{n-i} - 1} \\ &= \frac{X^{2^n} - 1}{X^{2^i} - 1} \end{align\*} $$ we can simplify: $$ \frac{X^{2^i}}{X^{2^i} + 1}\Phi\_{n-i}\left(X^{2^i}\right) = \frac{X^{2^i}}{X^{2^i} + 1}\frac{X^{2^n} - 1}{X^{2^i} - 1} = X^{2^i}\frac{X^{2^n} - 1}{X^{2^{i + 1}} - 1} = X^{2^i}\Phi\_{n-i-1}\left(X^{2^{i+1}}\right) $$ Applying this to equation $$(4)$$, we obtain: $$ \begin{align\*} \mathcal{U}*n(f) - v \cdot \mathcal{U}*n(1) = \sum*{i=0}^{n-1}\left(X^{2^i}\Phi*{n-i-1}\left(X^{2^{i+1}}\right)- z\_i \cdot \Phi\_{n-i}\left(X^{2^i}\right)\right) \mathcal{U}\_n(q\_i)^{<2^i} && (5) \end{align\*} $$ Now we can define $$\zeta\_x(X)$$ using equation (5), which is partially evaluated at $$x$$ on $$\Phi\_n(X)$$ as: $$ \zeta\_x(X) := \mathcal{U}*n(f) - v \cdot \Phi\_n(x) - \sum*{i=0}^{n-1}\left(x^{2^i}\Phi\_{n-i-1}\left(x^{2^{k+1}}\right)- z\_i \cdot \Phi\_{n-i} \left( x^{2^i} \right) \right)\mathcal{U}\_n(q\_i)^{<2^i}(X) \\ $$ Then the prover needs to commit to this polynomial $$(C\_{\zeta\_x}, r) = \mathsf{HidingKZG.Commit}(\zeta\_x)$$. If the prover sends $$(W, \delta) = \mathsf{HidingKZG.ProveEval}(C\_{\zeta\_x}, r, x, 0)$$ to the verifier, then the verifier can verify using 3 pairing operations with $$\mathsf{HidingKZG.VerifyEval}(C\_{\zeta\_x}, W, \delta, x, 0)$$. Note that since only $$\zeta\_x(x) = 0$$ is opened for $$\zeta\_x(X)$$, it is now possible to prove **circuit satisfiability** **without revealing any additional information.** ### Degree Check Protocol #### Single KZG Degree Check Let's construct a protocol based on $$\mathsf{HidingKZG}$$ that verifies whether a given polynomial $$f \in \mathbb{F}\[X]$$ satisfies $$\deg(f) \le d < N\_{\mathsf{max}}$$. $$\mathsf{HidingKZG.ProveOpenWithDegreeCheck}(C, r, d) \rightarrow (W, \delta)$$: 1. The prover samples $$\alpha \leftarrow \mathbb{F}$$. 2. The prover provides the verifier with $$W, \delta$$: $$ W = \left\[f(s)s^{N\_{\mathsf{max}} - 1 -d} \right]\_1 + \alpha\cdot \[\xi]*1, \quad \delta = r \cdot \left\[s^{N*{\mathsf{max}}-1-d}\right]\_1 - \[\alpha]\_1 $$ $$\mathsf{HidingKZG.VerifyOpenWithDegreeCheck}(C, W, \delta, d) \rightarrow b \in {0, 1}$$: The verifier checks the following equation: $$ e(C, \left\[ s^{N\_{\mathsf{max}}-1-d} \right]\_2) \stackrel{?}= e(W, \[1]\_2) \cdot e(\delta, \[\xi]\_2) $$ This is satisfied iff $$\mathsf{HidingKZG.Open}(C, f, r) = 1 \land f \in \mathbb{F}\[X]^{\le d}$$. **Soundness Proof:** Suppose $$\deg(f) > d$$. Then, the degree of $$f(X) \cdot X^{N\_{\mathsf{max}}-1-d}$$ is at least $$N\_{\mathsf{max}}$$, making it impossible to commit to $$W$$. **Completeness Proof:** $$ \begin{align\*} C \cdot s^{N\_{\mathsf{max} - 1 - d}} =(f(s) + r\xi) \cdot s^{N\_{\mathsf{max} - 1 - d}} &= f(s)s^{N\_{\mathsf{max}}-1-d} +\alpha\xi + (r\cdot s^{N\_{\mathsf{max}} - 1 - d} - \alpha)\xi \\ &= f(s)s^{N\_{\mathsf{max}}-1-d} + r \xi \cdot s^{N\_{\mathsf{max}} - 1 - d} \end{align\*} $$ $$\mathsf{HidingKZG.ProveEvalWithDegreeCheck}(C, r, d, z, v) \rightarrow (W, \delta)$$: 1. The prover samples $$\alpha \leftarrow \mathbb{F}$$. 2. The prover provides the verifier with $$W, \delta$$: $$ W = \left\[\frac{f(s) - v}{s - z}s^{N\_{\mathsf{max}}-d} \right]\_1 + \alpha\cdot \[\xi]*1, \quad \delta = r \cdot \left\[s^{N*{\mathsf{max}}-d} \right]\_1 - \[\alpha(s - z)]\_1 $$ $$\mathsf{HidingKZG.VerifyEvalWithDegreeCheck}(C, W, \delta, d, z, v) \rightarrow b \in {0, 1}$$: The verifier checks the following equation: $$ e(C - \[v]*1, \left\[ s^{N*{\mathsf{max}}-d} \right]\_2) \stackrel{?}= e(W, \[s]\_2 - \[z]\_2) \cdot e(\delta, \[\xi]\_2) $$ This is satisfied iff $$\mathsf{HidingKZG.Open}(C, f, r) = 1 \land f \in \mathbb{F}\[X]^{\le d} \land f(z) = v$$. **Soundness Proof:** Suppose $$\deg(f) > d$$. Then, the degree of $$\frac{f(X) - v}{X - z}X^{N\_{\mathsf{max}}-d}$$ is at least $$N\_{\mathsf{max}}$$, making it impossible to commit to $$W$$. **Completeness Proof:** $$ \begin{align\*} (C -v ) \cdot s^{N\_{\mathsf{max}} - d} =(f(s) + r\xi -v ) \cdot s^{N\_{\mathsf{max}} - d} &= (f(s) - v)s^{N\_{\mathsf{max}}-d} + \alpha\xi(s - z) + (r\cdot s^{N\_{\mathsf{max}} - d} - \alpha(s - z))\xi \\ &= (f(s) - v)s^{N\_{\mathsf{max}}-d} + r\xi \cdot s^{N\_{\mathsf{max}}-d} \end{align\*} $$ #### Batch Degree Check Now, let’s consider a set of polynomials $$\bm{f} = {f\_0, \dots, f\_{k-1}}$$ and their respective degree bounds $$\bm{d} = {d\_0, \dots, d\_{k-1}}$$. For $$0 \le i < k$$, each $$f\_i$$ belongs to $$\mathbb{F}\[X]$$, and we aim to construct a batch protocol to verify whether $$\deg(f\_i) \le d\_i < N\_{\mathsf{max}}$$. First, we choose $$\max d\_i \le d^\* \le N\_{\mathsf{max}} - 2$$. Let $$\bm{C} = {C\_0, \dots, C\_{k-1}}$$ and $$\bm{r} ={r\_0, \dots, r\_{k-1}}$$ be the set of commitments and randomness corresponding to $$\bm{f}$$. $$\mathsf{HidingKZG.ProveOpenWithBatchDegreeCheck}(\bm{f}, \bm{r}, \bm{d}) \rightarrow (C\_f, W, \delta)$$: 1. The verifier samples $$y \leftarrow \mathbb{F}$$ and sends it to the prover. 2. The prover computes $$(C\_f, r) = \mathsf{HidingKZG.Commit}(f)$$ and sends it to the verifier: $$ f := \sum\_{i=0}^{k-1}y^iX^{d^\*-d\_i+1}f\_i $$ 3. The verifier samples $$x \leftarrow \mathbb{F}^\*$$ (where $$x \ne 0$$) and sends it to the prover. 4. The prover samples $$\alpha \leftarrow \mathbb{F}$$. 5. The prover sends $$W, \delta$$ to the verifier: $$ W = \left\[\frac{\zeta\_x(s)}{s - x} s^{N\_{\mathsf{max}} - d^\* - 1}\right]*1 + \alpha \cdot \[\xi]*1 \ \delta = \left(r - \sum*{i=0}^{k-1}y^ix^{d^\*-d\_i+1}r\_i\right)\cdot\left\[ s^{N*{\mathsf{max}}-d\*-1}\right]\_1 - \[\alpha(s - x)]\_1 $$ Here, $$\zeta\_x(X)$$ is defined as: $$ \zeta\_x(X) := f(X) - \sum\_{i = 0}^{k-1}y^ix^{d^\*-d\_i+1}f\_i(X) $$ $$\mathsf{HidingKZG.VerifyOpenWithBatchDegreeCheck}(\bm{C}, C\_f, W, \delta, \bm{d}) \rightarrow b \in {0, 1}$$ The verifier checks the following equation: $$ e(C\_{\zeta\_x},\left\[ s^{N\_{\mathsf{max}} - d^\* - 1} \right]\_2) \stackrel{?}= e(W, \[s]\_2 - \[x]\_2) \cdot e(\delta, \[\xi]\_2) $$ The commitment $$C\_{\zeta\_x}$$ is defined as: $$ C\_{\zeta\_X} := C\_f - \sum\_{i=0}^{k-1}y^ix^{d^\*-d\_i+1}C\_i $$ This is satisfied iff $$\mathsf{HidingKZG.Open}(C\_i, f\_i, r\_i) = 1 \land f\_i \in \mathbb{F}\[X]^{\le d\_i}$$ for $$0 \le i < k$$. **Soundness Proof:** Suppose that for some $$0 \le i < k$$, we have $$\deg(f\_i) > d\_i$$. Then the degree of $$f$$ becomes: $$ \deg(\zeta\_x(X)) = \deg (f) \ge d^\* + 2 $$ which leads to: $$ \deg\left(\frac{\zeta\_x(X)}{X - x}X^{N\_{\mathsf{max}} - d^\* -1}\right) \ge N\_{\mathsf{max}} $$ making it impossible to commit to $$W$$. **Completeness Proof:** $$ \begin{align\*} \left(\zeta\_x(s) + \left(r - \sum\_{i=0}^{k-1}y\_ix^{d^*-d\_i+1}r\_i\right)\xi\right)\cdot s^{N\_{\mathsf{max}} - d^* - 1} &= \zeta\_x(s) \cdot s^{N\_{\mathsf{max}} - d^\* - 1} + \alpha\xi(s - x) + \left(\left(r - \sum\_{i=0}^{k-1}y\_ix^{d^*-d\_i+1}r\_i\right) \cdot s^{N\_{\mathsf{max}} - d^* - 1} - \alpha(s - x)\right)\xi \\ &= \zeta\_x(s)\cdot s^{N\_{\mathsf{max}} - d^\* - 1} + \left(r - \sum\_{i=0}^{k-1}y\_ix^{d^*-d\_i+1}r\_i\right)\xi \cdot s^{N\_{\mathsf{max}} - d^* - 1} \end{align\*} $$ In the above protocol, we designed the batch degree check using the $$\mathsf{HidingKZG}$$ protocol. However, as discussed in [Section 5.4](https://eprint.iacr.org/2023/917.pdf#page=28\&zoom=100,180,362) of the paper, this method is applicable in a more general setting, provided that: * The commitment scheme satisfies additive homomorphism. * The evaluation protocol is knowledge-sound. These conditions allow the batch degree check to be used in other polynomial commitment schemes as well. #### Batch Evaluation with Degree Check Now, let’s consider a set of polynomials $$\bm{f} = {f\_0, \dots, f\_{k-1}}$$ and their respective evaluation values $$\bm{v} = {v\_0, \dots, v\_{k-1}}$$. For $$0 \le i < k$$, each $$f\_i$$ belongs to $$\mathbb{F}\[X]$$, and we aim to construct a batch protocol to verify whether $$\deg(f\_i) \le d < N\_{\mathsf{max}}$$ and $$f\_i(z) = v\_i$$. Let $$\bm{C} = {C\_0, \dots, C\_{k-1}}$$ and $$\bm{r} ={r\_0, \dots, r\_{k-1}}$$ be the set of commitments and randomness corresponding to $$\bm{f}$$. $$\mathsf{HidingKZG.ProveBatchEvalWithDegreeCheck}(\bm{C}, \bm{r}, d, z, \bm{v}) \rightarrow (W, \delta)$$: 1. The verifier samples $$y \leftarrow \mathbb{F}$$ and sends it to the prover. 2. The prover samples $$\alpha \leftarrow \mathbb{F}$$. 3. The prover provides the verifier with $$W, \delta$$: $$ W = \left\[\frac{\sum\_{i = 0}^{k-1}y^i(f\_i(s) - v\_i)}{s - z} s^{N\_{\mathsf{max}} - d}\right]*1 + \alpha \cdot \[\xi]*1 \\ \delta = \left(\sum*{i=0}^{k-1}y^ir\_i\right)\cdot\left\[ s^{N*{\mathsf{max}}-d}\right]\_1 - \[\alpha(s - z)]\_1 $$ $$\mathsf{HidingKZG.VerifyBatchEvalWithDegreeCheck}(\bm{C}, W, \delta, d, z, \bm{v}) \rightarrow b \in {0, 1}$$: The verifier checks the following equation: $$ e(\sum\_{i=0}^{k-1}y\_iC\_i - \left\[\sum\_{i=0}^{k-1}y^iv\_i\right]*1,\left\[ s^{N*{\mathsf{max}} - d} \right]\_2) \stackrel{?}= e(W, \[s]\_2 - \[x]\_2) \cdot e(\delta, \[\xi]\_2) $$ This is satisfied iff $$\mathsf{HidingKZG.Open}(C\_i, f\_i, r\_i) = 1 \land f\_i \in \mathbb{F}\[X]^{\le d} \land f\_i(z) = v\_i$$ for $$0 \le i < k$$. **Soundness Proof:** Suppose that for some $$0 \le i < k$$, we have $$\deg(f\_i) > d$$. Then the degree of the expression: $$ \deg\left(\frac{\sum\_{i=0}^{k-1}y^i(f\_i(X) - v)}{X - x}X^{N\_{\mathsf{max}} - d}\right) \ge N\_{\mathsf{max}} $$ making it impossible to commit to $$W$$. **Completeness Proof:** $$ \begin{align\*} \sum\_{i=0}^{k-1}y\_i\left(f\_i(s) + r\_i\xi - v\_i\right) \cdot s^{N\_{\mathsf{max}} - d} &= \sum\_{i=0}^{k-1}y\_i(f\_i(s) - v\_i) \cdot s^{N\_{\mathsf{max}} - d} + \alpha\xi(s - z) + \left(\sum\_{i=0}^{k-1}y^ir\_i \cdot s^{N\_{\mathsf{max}} - d} - \alpha(s - z)\right)\xi \\ &=\sum\_{i=0}^{k-1}y\_i(f\_i(s) - v\_i) \cdot s^{N\_{\mathsf{max}} - d} + \sum\_{i=0}^{k-1}y^ir\_i\xi \cdot s^{N\_{\mathsf{max}} - d} \end{align\*} $$ ### Put Together To summarize, in order to prove $$f(\bm{z}) \stackrel{?}= v$$, we transformed the problem as follows: $$ \mathcal{U}*n(f) - v \cdot \Phi\_n(X) = \sum*{i=0}^{n-1}\left(X^{2^i}\Phi\_{n-i-1}\left(X^{2^{i+1}}\right)- z\_i \cdot \Phi\_{n-i}\left(X^{2^i}\right)\right) \mathcal{U}\_n(q\_i)^{<2^i} $$ Now, let's prove the above equation using $$\mathsf{HidingKZG}$$. 1. The prover computes commitments $$(C\_i, r\_i) := \mathsf{HidingKZG.commit}\left(\mathcal{U}\_n(q\_i)^{<2^i}\right)$$ for $$0 \le i < n$$, and sends them to the verifier. 2. The verifier randomly samples $$y \leftarrow \mathbb{F}$$. 3. The prover computes $$(C\_{\hat{q}}, \hat{r}) := \mathsf{HidingKZG.commit}\left(\hat{q}\right)$$ for $$0 \le i < n$$ and sends the commitments to the verifier, where: $$ \hat{q}(X) := \sum\_{i=0}^{n-1}y^iX^{2^n-d\_i-1}\mathcal{U}\_n(q\_i)^{<2^i} $$ 4. The verifier randomly samples $$x \leftarrow \mathbb{F}^\*, z\leftarrow \mathbb{F}$$ (where $$x \neq 0$$). 5. The prover samples $$\alpha \leftarrow \mathbb{F}$$. 6. The prover provides the verifier with $$W, \delta$$: $$ W = \left\[\left(\frac{\zeta\_x(s) + z \cdot Z\_x(s)}{s- x}\right)s^{N\_{\mathsf{max}} - (2^n - 1)} \right]*1 + \alpha \cdot \[\xi]*1 \\ \delta = \left\[ (r*\zeta + z r\_Z) s^{N*{\mathsf{max}} - (2^n - 1)} -\alpha (s - x)\right]\_1 $$ Where the values are defined as follows: $$ \zeta\_x(X) := \hat{q}(X) - \sum\_{i=0}^{n-1}y^ix^{2^n-d\_i-1}\mathcal{U}*n(q\_i)^{<2^i}\\ Z\_x(X) := \mathcal{U}*n(f) - v \cdot \Phi\_n(x) - \sum*{i=0}^{n-1}\left(x^{2^i}\Phi*{n-i-1}\left(x^{2^{k+1}}\right)- z\_i \cdot \Phi\_{n-i} \left( x^{2^i} \right) \right)\mathcal{U}*n(q\_i)^{<2^i} \\ r*\zeta := r - \sum\_{i=0}^{n-1}\left(x^{2^i}\Phi\_{n-i-1}\left(x^{2^{i+1}}\right)-z\_i \cdot \Phi\_{n-i}\left(x^{2^i}\right)\right) \cdot r\_i \\ r\_Z := \hat{r} - \sum\_{i=0}^{n-1}y^ix^{2^n-d\_i-1}r\_i $$ 7. The verifier checks the following equation: $$ e(C\_{\zeta\_x} + z \cdot C\_{Z\_x}, \[s^{N\_{\mathsf{max}}-(2^n-1)}]\_2) \stackrel{?}= e(W, \[s - x]\_2) \cdot e(\delta, \[\xi]\_2) $$ Where the values are defined as follows: $$ C\_{\zeta\_x} := C\_{\hat{q}} - \sum\_{i=0}^{n-1}y^ix^{2^n-d\_i-1}C\_i \\ C\_{Z\_x} := \[\mathcal{U}*n(f)(s)]*1 - \[v \cdot \Phi\_n(x)]*1 - \sum*{i=0}^{n-1}\left(x^{2^i}\Phi*{n-i-1}\left(x^{2^{i+1}}\right) - z\_i \cdot \Phi*{n-i}\left(x^{2^i})\right)\right)\cdot C\_i $$ **Completeness Proof:** $$ \begin{align\*} (\zeta\_x(s) + r\_{\zeta} + z \cdot (Z\_x(s) + r\_Z))s^{N\_{\mathsf{max}} - (2^n - 1)} &= (\zeta\_x(s) + z \cdot Z\_x(s))s^{N\_{\mathsf{max}} - (2^n - 1)} + \alpha\xi(s- x) + ((r\_\zeta + z r\_Z) s^{N\_{\mathsf{max}} - (2^n - 1)} * \alpha(s - x))\xi \\ &= (\zeta\_x(s) + z \cdot Z\_x(s))s^{N\_{\mathsf{max}} - (2^n - 1)} + (r\_\zeta + z r\_Z) s^{N\_{\mathsf{max}} - (2^n - 1)} \end{align\*} $$ **Analysis:** * $$\mathsf{srs}$$(structure reference string) **size**: $$N^{\mathsf{max}}+1\mathbb{G}\_1, N^{\mathsf{max}}+1\mathbb{G}\_2$$ * **Prover work**: $$O(n)\ \mathsf{MSM}$$ * To compute each $$C\_i$$, it takes $$2^i + 1 \ \mathsf{MSM}$$ operations. * To compute $$C\_{\hat{q}}$$, it takes at most $$2^{n-1}\ \mathsf{MSM}$$ operations. This is because $$\hat{q}$$ ​ has nonzero coefficients ranging from a maximum degree of $$2^{n-1}=2^n- d\_{n-1}-1$$ to $$2^{n}-1 = 2^n - d\_0 - 1$$. * To compute $$W$$, it takes at most $$2^n\ \mathsf{MSM}$$ operations. * To compute $$\delta$$, it takes $$3\ \mathsf{MSM}$$ operations: $$(r\_\zeta + z r\_Z) \cdot \[ s^{N\_{\mathsf{max}} - (2^n - 1)}]\_1 -\alpha \cdot \[s]\_1 + \alpha x \cdot \[1]\_1$$. * **Proof length**: $$n+3\mathbb{G}\_1,3\mathbb{F}$$ * $$n + 3\mathbb{G}*1$$: $$(C\_0, \dots, C*{n-1}, C\_{\hat{q}}, W, \delta)$$ * $$3\mathbb{F}$$: $$(y, x, z)$$ * **Verifier work**: $$2n+6 \mathsf{MSM}\_1, 2\mathbb{G}\_2, 3\mathsf{P}$$ * To compute $$\[v \cdot \Phi\_n(x)]\_1$$, it takes $$1\ \mathsf{MSM}$$ operation. * To compute $$C\_{Zx}$$, it takes $$n + 2\ \mathsf{MSM}$$ operations. * To compute $$C\_{\zeta\_x}$$, it takes $$n + 1\ \mathsf{MSM}$$ operations. * To compute $$C\_{\zeta\_x} + z \cdot C\_{Z\_x}$$, it takes $$2\ \mathsf{MSM}$$ operations. * To compuete $$\[s]\_2 - \[x]\_2$$, it takes $$2 \mathbb{G}\_2$$ operations. Here, $$\mathsf{MSM}$$ represents MSM operations in $$\mathbb{G}\_1$$, $$\mathbb{F}$$ represents addition or multiplication in $$\mathbb{F}$$, and $$\mathsf{P}$$ denotes a pairing operation. ### Shift Evaluation In permutation arguments or lookup arguments like Plookup, computing the evaluations of shifted polynomials is necessary. For example, if $$f \in \mathbb{F}\[X\_0, \dots, X\_{n-1}]^{\le 1}$$ has the following evaluations: $$ \bm{v} = { v\_0, v\_1, \dots, v\_{2^n-2}, v\_{2^n-1} } $$ then the evaluations of $$\mathsf{shift}(f)$$ are: $$ \bm{v'} = { v\_1, v\_2, \dots, v\_{2^n-1}, v\_0 } $$ Applying the $$\mathcal{U}\_n$$ mapping results in: $$ \mathcal{U}*n(f) = v\_0 + v\_1X \dots + v*{2^n-2}X^{2^n-2} + v\_{2^n-1}X^{2^n-1} \\ \mathcal{U}*n(\mathsf{shift}(f) ) =v\_1 + v\_2X + \dots + v*{2^n-1}X^{2^n -2} + v\_0X^{2^n -1} $$ To prove $$\mathsf{shift}(f)(\bm{z}) = v$$, we construct the following equation: $$ \mathsf{shift}(f) - v = \sum\_{i=0}^{n-1}(X\_i - z\_i)q\_i $$ and demonstrate the existence of a suitable $$q\_i$$ satisfying: * $$i = 0 \Rightarrow q\_0 \in \mathbb{F}$$ * $$0 < i < n \Rightarrow q\_i \in \mathbb{F}\[X\_0, \dots, X\_{i-1}]^{\le 1}$$ Applying the transformation from equation $$(1)$$ to $$(5)$$, we obtain: $$ \begin{align\*} \mathcal{U}*n(\mathsf{shift}(f)) - v \cdot \Phi\_n(X) = \sum*{i=0}^{n-1}\left(X^{2^i}\Phi\_{n-i-1}\left(X^{2^{i+1}}\right)- z\_i \cdot \Phi\_{n-i}\left(X^{2^i}\right)\right) \mathcal{U}\_n(q\_i)^{<2^i} && (6) \end{align\*} $$ Multiplying $$\mathcal{U}\_n(\mathsf{shift}(f))$$ by $$X$$, we get: $$ \begin{align\*} X\mathcal{U}*n(\mathsf{shift}(f)) &= v\_1X + v\_2X^2 + \dots +v*{2^n-1}X^{2^n-1} + v\_0X^{2^n} \\ &= v\_0 + v\_1X + v\_2X^2 + \dots +v\_{2^n-1}X^{2^n-1} + v\_0X^{2^n} - v\_0 \\ &= \mathcal{U}\_n(f) + v\_0(X^{2^n} - 1) \end{align\*} $$ Thus, multiplying both sides of equation $$(6)$$ by $$X$$, we obtain: $$ \begin{align\*} \mathcal{U}\_n(f) + v\_0(X^{2^n} - 1) * v \cdot X \Phi\_n(X) = X \cdot \sum\_{i=0}^{n-1}\left(X^{2^i}\Phi\_{n-i-1}\left(X^{2^{i+1}}\right)- z\_i \cdot \Phi\_{n-i}\left(X^{2^i}\right)\right) \mathcal{U}\_n(q\_i)^{<2^i} && (7) \end{align\*} $$ Since equation $$(7)$$ holds, we can prove that $$\mathsf{shift}(f)$$ is indeed a shifted version of $$f$$ by committing only once to $$\mathcal{U}\_n(f)$$ and then using it to verify the evaluation claim of $$\mathsf{shift}(f)$$. If $$v\_0 = 0$$, the protocol simplifies even further! While the referenced paper discusses high-degree shifts and batched verification methods, these are omitted here for brevity. Interested readers are encouraged to refer to [**Sections 7**](https://eprint.iacr.org/2023/917.pdf#page=39\&zoom=100,180,786) and [**8**](https://eprint.iacr.org/2023/917.pdf#page=41\&zoom=100,180,693) for more details! ## Conclusion
The multilinear polynomial identity originally required $$n$$ pairing operations. However, thanks to $$\mathcal{U}\_n$$ mapping, the verifier can now perform the expensive pairing computation in just three operations. Meanwhile, to prove that $$q\_i$$ is bounded by a certain degree, the degree check protocol must be executed, which requires an $$\mathsf{srs}$$ proportional to $$N\_{\mathsf{max}}$$ in $$\mathbb{G}\_1$$ and $$\mathbb{G}\_2$$. Fortunately, the verifier does not need to perform the costly $$\mathbb{G}\_2$$ operations. Additionally, an important point is that for hiding, only $$\log N + 5$$ elements in $$\mathbb{G}\_1$$ are required. ## References * * > Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze