# Maller’s optimization for kimchi

This document proposes a protocol change for kimchi.

## What is Maller’s optimization?

See the section on Maller’s optimization for background.

## Overview

We want the verifier to form commitment to the following polynomial:

$L(x)=f(x)−Z_{H}(ζ)⋅t(x)$

They could do this like so:

$com(L)=com(f)−Z_{H}(ζ)⋅com(t)$

Since they already know $f$, they can produce $com(f)$, the only thing they need is $com(t)$. So the protocol looks like that:

In the rest of this document, we review the details and considerations needed to implement this change in kimchi.

## How to deal with a chunked $t$?

There’s one challenge that prevents us from directly using this approach: $com(t)$ is typically sent and received in several commitments (called chunks or segments throughout the codebase). As $t$ is the largest polynomial, usually exceeding the size of the SRS (which is by default set to be the size of the domain).

### The verifier side

Thus, the **verifier** will have to produce split commitments of $L$ and combine them with powers of $ζ_{n}$ to verify an evaluation proof. Let’s define $L$ as:

$L=L_{0}+x_{n}L_{1}+x_{2n}L_{1}+⋯$

where every $L_{i}$ is of degree $n−1$ at most. Then we have that

$com(L)=com(L_{0})+com(x_{n}⋅L_{1})+com(x_{2n}⋅L_{2})+⋯$

Which the verifier can’t produce because of the powers of $x_{n}$, but we can linearize it as we already know which $x$ we’re going to evaluate that polynomial with:

$com(L~)=com(L_{0})+ζ_{n}⋅com(L_{1})+ζ_{2n}⋅com(L_{2})+⋯$

### The prover side

This means that the **prover** will produce evaluation proofs on the following linearized polynomial:

$L~(x)=1⋅L_{0}(x)+ζ_{n}⋅L_{1}(x)+ζ_{2n}⋅L_{2}(x)+⋯$

which is the same as $L(x)$ only if evaluated at $ζ$. As the previous section pointed out, we will need $L~(ζω)$ and $L~(ζω)=L(ζω)$.

## Evaluation proof and blinding factors

To create an evaluation proof, the prover also needs to produce the blinding factor $r_{L}$ associated with the chunked commitment of:

$L~=f~ −(ζ_{n}−1)t~$

To compute it, there are two rules to follow:

- when two commitment are
**added**together, their associated blinding factors get added as well: $com(a)+com(b)⟹r_{a}+r_{b}$ - when
**scaling**a commitment, its blinding factor gets scalled too: $n⋅com(a)⟹n⋅r_{a}$

As such, if we know $r_{f}$ and $r_{t}$, we can compute:

$r_{L~}=r_{f~}+(ζ_{n}−1)⋅r_{t~}$

The prover knows the blinding factor of the commitment to $t$, as they committed to it. But what about $f$? They never commit to it really, and the verifier recreates it from scratch using:

**The commitments we sent them**. In the linearization process, the verifier actually gets rid of most prover commitments, except for the commitment to the last sigma commitment $S_{σ6}$. (TODO: link to the relevant part in the spec) As this commitment is public, it is not blinded.**The public commitments**. Think commitment to selector polynomials or the public input polynomial. These commitments are not blinded, and thus do not impact the calculation of the blinding factor.**The evaluations we sent them**. Instead of using commitments to the wires when recreating $f$, the verifier uses the (verified) evaluations of these in $ζ$. If we scale our commitment $com(z)$ with any of these scalars, we will have to do the same with $r_{z}$.

Thus, the blinding factor of $L~$ is $(ζ_{n}−1)⋅r_{t~}$.

## The evaluation of $L~$

The prover actually does not send a commitment to the full $f$ polynomial. As described in the last check section. The verifier will have to compute the evaluation of $L~(ζ)$ because it won’t be zero. It should be equal to the following:

$ f~ (ζ)−t~(ζ)(ζ_{n}−1)=(ζ−1)(ζ−ω_{n−k})1−z(ζ) [n(ζ_{n}−1)(ζ−ω_{n−k}) α_{PERM1}+nω_{n−k}(ζ_{n}−1)(ζ−1) α_{PERM2}]−pub(ζ)−z(ζ)⋅zkpm(ζ)⋅α_{PERM0}⋅(w[0](ζ)+β⋅shift[0]ζ+γ)⋅(w[1](ζ)+β⋅shift[1]ζ+γ)⋅(w[2](ζ)+β⋅shift[2]ζ+γ)⋅(w[3](ζ)+β⋅shift[3]ζ+γ)⋅(w[4](ζ)+β⋅shift[4]ζ+γ)⋅(w[5](ζ)+β⋅shift[5]ζ+γ)⋅(w[6](ζ)+β⋅shift[6]ζ+γ)++z(ζω)⋅zkpm(ζ)⋅α_{PERM0}⋅(w[0](ζ)+β⋅σ[0](ζ)+γ)⋅(w[1](ζ)+β⋅σ[1](ζ)+γ)⋅(w[2](ζ)+β⋅σ[2](ζ)+γ)⋅(w[3](ζ)+β⋅σ[3](ζ)+γ)⋅(w[4](ζ)+β⋅σ[4](ζ)+γ)⋅(w[5](ζ)+β⋅σ[5](ζ)+γ)⋅(w[6](ζ)+γ)+ $

Because we use the inner product polynomial commitment, we also need:

$L~(ζω)=f~ (ζω)−Z_{H}(ζ)⋅t~(ζω)$ Notice the $Z_{H}(ζ)$. That evaluation must be sent as part of the proof as well.

## The actual protocol changes

Now here’s how we need to modify the current protocol:

- The evaluations $f(ζ),f(ζω),t(ζ),t(ζω)$ (and their corresponding evaluation proofs) don’t have to be part of the protocol anymore.
- The prover must still send the chunked commitments to $t$.
- The prover must create a linearized polynomial $L~$ by creating a linearized polynomial $f~ $ and a linearized polynomial $t~$ and computing: $L~=f~ +(ζ_{n}−1)⋅t~$
- While the verifier can compute the evaluation of $L~(ζ)$ by themselves, they don’t know the evaluation of $L~(ζω)$, so the prover needs to send that.
- The verifier must recreate $com(L~)$, the commitment to $L~$, themselves so that they can verify the evaluation proofs of both $L~(ζ)$ and $L~(ζω)$.
- The evaluation of $L~(ζω)$ must be absorbed in both sponges (Fq and Fr).

The proposal is implemented in #150 with the following details:

- the $L~$ polynomial is called $ft$.
- the evaluation of $L~(ζ)$ is called $ft_{e}val0$.
- the evaluation $L~(ζω)$ is called $ft_{e}val1$