*Evaldas Drąsutis
IOTA Foundation*

# Formulas for polynomial KZG commitments in Lagrange basis

## Summary
This post describes an experimental implementation of polynomial *KZG commitments*, aka *Kate commitments*. The implementation uses the *trusted setup* completely in Lagrange basis calculated upon secret $s$, non-secret value $\omega$ and its powers. All computations are performed in the *evaluation form*. The powers of a secret on the curve $[s^i]_1$ nor any FFT operations are not needed in any stage.

The math mostly follows articles on KZG by Dankrad Feist, specifically [this](https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html) and [this](https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html). We assume the reader is familiar with the content of it.

The implemented experimental Go package is based on [DEDIS Advanced Crypto Library for Go Kyber v3](https://github.com/dedis/kyber) and uses $bn256$ BLS suite. It can be found here: [https://github.com/lunfardo314/verkle](https://github.com/lunfardo314/verkle)
## General

### Constant $d$
$d$ is a global constant which defines maximum length of the vector we want to commit to. The shorter vectors can be commited by providing zeroes as values, however we can't commit vectors longer than $d$.

### The $\omega$ value
The $\omega$ is a scalar in the underlying field with the property of $\omega^k\not=1, k=1 \dots d-1$.

We use values $\omega^0, \omega^1, \dots, \omega^{d-1}$ to calculate the Lagrange basis. The Lagrange polynomial is defined the following way:
$$
l_i(X)= \prod_{j=0,j\not=i}^{d-1}\frac{X-\omega^i}{\omega^j-\omega^i}
$$
Any vector $V=(v_0, v_1, \dots, v_{d-1})$ on the field corresponds to the polynomial $f(X)=\sum_{i=0}^{d-1}v_il_i(X)$. It makes $f(\omega^i)=v_i$ for $i=0 \dots d-1$.

The auxiliarly polynomial $A(X)=\prod_{i=0}^{d-1}(X-\omega^i)$ has its roots at $\omega^k, k=0 \dots d-1$

The formal derivate $A'(X)=\sum_{j=0}^{d-1}\prod_{i\not=j}(X-\omega^i)$ has the following values at these roots:

$A'(\omega^j)=\prod_{i\not=j}(\omega^j-\omega^i)$

We could assume $\omega^d=1$, i.e $\omega$ to be a [primitive root of unity](https://en.wikipedia.org/wiki/Root_of_unity) Then we'll have $A(X)=X^d-1$ and $A'(X)=dX^{d-1}$, $A'(\omega^i)=d\omega^{-i}$. It would make some calculation below more economic, however in this implementation we aim to avoid this assumption due to reasons explained below.

We can always assume $\omega = r^\frac{p-1}{d}$ where $p$ is the number of elements of the scalar field and $r$ is a field element selected so that the $\omega$ is a primitive root of unity of degree $d$ (any non-zero and non-one $r$ would give a root of unity but not any would give a *primitive* root of unity, which is needed in our case, because we need $\omega^i\not=1,\quad i=1 \dots d-1$. In practice we can keep trying random elements $r$ until $\omega$ is a primitive. See code in the experimental implementation).

However, the above implies $d$ is a divisor of $p-1$. Since $d$ is an essential constant of the setup, the assumption $\omega^d=1$ significantly limits possible values of $d$ and this, in turn, has consequences in performance. For example, in the BLS suite we use in this implementation, smallest divisor of $p-1$ after $2^5$ is $5743$. If we want to create commitments of vectors of size $257$ ($256$ children plus terminal value in the node of a 257-ary *verkle trie*), we would still have to use $d=5743$.

So, we want to provide setup for calculations for arbitrary $d$ and therefore avoid assumption of $\omega^d=1$.

### Trusted setup
The Lagrange basis for a secret $s$ is a collection of $d$ values on the curve:
$$
TL_i =[l_i(s)]_1 \quad i=0 \dots d-1
$$

Note that $TL_i$ also depends on $\omega$.
The *trusted setup* $T(d, \omega, s)$ is a collection of public values on $G_1$ and $G_2$ which includes:
* $d$
* $\omega$
* $[l_i(s)]_1 \quad i=0 \dots d-1$
* $[s-\omega^i]_2 \quad i=0 \dots d-1$.

We assume $s$ is a scalar value on the field not known to anyone, a secret. The secret value $s$ and public values $d$ and $\omega$ are used to compute all the values in the *trusted setup* $T(d, \omega, s)$. The secret value $s$ is destroyed immediately after the generation of $T$ so that noone in the world should know it.

The *trusted setup* is public, i.e. it does not contain any secrets. It is computationally non-feasible neither to re-construct $s$ from the given $T$ nor to create another valid $T'(d, \omega, s') = T(d, \omega, s)$ for some other $s'\not=s$.

### What do we want to achieve?
We aim to commit to vectors of scalar values on the underlying field $V=(v_0, v_1, \dots, v_{d-1})$ and to prove inclusion of value $v_i$ in a position $i$ by providing the commitment to the whole vector (polynomial) and the *proof* (no need for the vector itself).

The commitment to the vector $V$ is a commitment to the polynomial $f(X)$ such that $f(\omega^i)=v_i$. The KZG commitment to the polynomial is $C=[f(s)]_1$. It is calculated by the prover.

The *proof* $\pi_i = \pi_i(T, V, i)$ is a value on $G_1$. It is calculated by the prover to prove the fact that vector $V$ contains $v_i$ at the index $i$.

The condition $verify(T, C, \pi_i, v_i, i) = true$ is practically impossible to satisfy when $f(\omega^i)\not=v_i$. The $verify$ function is calculated by verifier. It uses bilinear pairing $e:G_1\times G_2\rightarrow G_T$ and the following equation to check the validity of the proof:
$$
e(\pi_i, [s-\omega^i]_2) = e(C-[v_i]_1, H)
$$
where $H$ is the generator of the group $G_2$

## Calculating commitment to the vector

KZG commitment to the vector is:
$$
C(T,V)=[f(s)]_1
$$
we calculate it from the trusted setup, i.e. not knowing the secret $s$:
$$
C(T,V)=\sum_{i=0}^{d-1} v_i\times TL_i
$$
Note that once we have $TL_i$ constants precalculated, the $C$ can be calulated in $O(d)$ multiplications to scalar and additions on the curve. If the vector is sparse, i.e. with just few non-zero elements, the number of operations on curve is equal to the number of non-zero values.

Setting a new value at some position in the vector does not require complete re-calculation of $C$, two operations on the curve is enough to update $C$. Let's say the old value $v_i$ is replaced with the new value $v'_i$. The commitment to the updated vector $C'$ can be calculated as $C'=C+TL_i\times(v'_i-v_i)$.

## Calculating the proof

How do we calulate the proof $\pi_i$ that value $v_i$ is in the position $i$ of the vector?

The simple but naive and wrong approach can be found below in the *Annex. Calculating the proof. Naive approach (wrong)*.

To calculate $\pi_i$ correctly we have to perform true division of polynomials.
The function $q_i(X)=\frac{f(X)-v_i}{X-\omega^i}$ is a polynomial because $X-\omega^i$ is a factor of $f(X)-v_i$. The latter is a polynomial which has root $\omega^i$ by the very construction of $f$.

The KZG proof of $f(\omega^i)=v_i$ is $\pi_i = [q_i(s)]_1$.

Just like we calculate $f$ in Lagrange basis:
$$
\\f(X) = \sum_{i=0}^{d-1} v_il_i(X)
\\f(\omega^j) = \sum_{i=0}^{d-1} v_il_i(\omega^j) = \sum_{i=0}^{d-1} f(\omega^i)l_i(\omega^j)
\\f(s) = \sum_{i=0}^{d-1} f(\omega^i)l_i(s)
$$
we aim to calculate $q_i(X)$ in Lagrange basis too:
$$
q_i(X)=\sum_{m=0}^{d-1}q_i(\omega^m) l_m(X)
\\ q_i(s)=\sum_{m=0}^{d-1}q_i(\omega^m) l_m(s)$$

So, we only need to calculate the $q_i(\omega^m)$ for each $m$ but how? The problem is, in the direct calculation it leads to zero denominator, even if we know it has value there because $q_i(X)$ is a polynomial.

To calculate $q_i(\omega^m)$, we follow formulas in the article mentioned above, the chapter [Dividing when one of the points is zero](https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html). We adjust formulas to our use of $\{\omega^j\}$ and to be more clear for our implementation.

### Calculating $q_i(\omega^m)$ with $m \not=i$
$$
\\ q_i(X) = \frac{f(X)-v_i}{X-\omega^i} = \frac{\sum_{j=0}^{d-1}v_j
l_j(X)-v_i}{X-\omega^i}
\\ q_i(\omega^m)= \frac{\sum_{j=0}^{d-1}(v_j-v_i)
l_j(\omega^m)}{\omega^m-\omega^i} = \frac{\sum_{j=0, j\not=i}^{d-1}(v_j-v_i)
l_j(\omega^m)}{\omega^m-\omega^i}
\\ q_i(\omega^m)= \frac{v_m-v_i}{\omega^m-\omega^i}
\quad , m \not= i$$

Almost there. Now we only have to figure out how to calculate $q_m(\omega^m)$.

### Calculating $q_m(\omega^m)$
We can rewrite formulas for the Lagrange polynomial:
$$
\\ l_j(X)=\frac{1}{A'(\omega^j)}\frac{A(X)}{X-\omega^j}
\\ \frac{l_j(X)}{X-\omega^i}=\frac{1}{A'(\omega^j)}\frac{A(X)}{(X-\omega^j)(X-\omega^i)}\frac{A'(\omega^i)}{A'(\omega^i)}
\\=\frac{A'(\omega^i)}{A'(\omega^j)}(\frac{1}{A'(\omega^i)}\frac{A(X)}{X-\omega^i})\frac{1}{X-\omega^j} \\=\frac{A'(\omega^i)}{A'(\omega^j)}\frac{l_i(X)}{X-\omega^j}
$$
Note that the formulas above are defined for any $i,j=0 \dots d-1$. Let's assume $X=\omega^m$ in the above:
$$
\frac{l_j(\omega^m)}{\omega^m-\omega^i} = \frac{A'(\omega^i)}{A'(\omega^j)}\frac{l_i(\omega^m)}{\omega^m-\omega^j}
\\q_i(\omega^m)=\sum_{j=0, j\not=i}^{d-1}(v_j-v_i) \frac{l_j(\omega^m)}{\omega^m-\omega^i}=
\\=\sum_{j=0, j\not=i}^{d-1}(v_j-v_i)\frac{A'(\omega^i)}{A'(\omega^j)}\frac{l_i(\omega^m)}{\omega^m-\omega^j}
\\q_m(\omega^m)=\sum_{j=0, j\not=m}^{d-1}(v_j-v_m)\frac{A'(\omega^m)}{A'(\omega^j)}\frac{l_m(\omega^m)}{\omega^m-\omega^j}
\\=\sum_{j=0, j\not=m}^{d-1}(v_j-v_m)\frac{A'(\omega^m)}{A'(\omega^j)}\frac{1}{\omega^m-\omega^j}=
\\= \sum_{j=0,j \not= m}^{d-1}v_j \times \frac{A'(\omega^m)}{A'(\omega^j)}\frac{1}{\omega^m-\omega^j} - v_m \times\sum_{j=0,j \not= m}^{d-1} \frac{A'(\omega^m)}{A'(\omega^j)}\frac{1}{\omega^m-\omega^j}
$$
The following pre-calculated values would improve performace:
$$
TA_{mj}=\frac{A'(\omega^m)}{A'(\omega^j)}\frac{1}{\omega^m-\omega^j} \quad m \not=j
\\ TK_m = \sum_{j=0,j \not= m}^{d-1} \frac{A'(\omega^m)}{A'(\omega^j)}\frac{1}{\omega^m-\omega^j}
\\q_m(\omega^m) = \sum_{j=0,j\not=m}^{d-1}v_j \times TA_{mj} - v_m \times TK_m
$$

### Final formulas to calculate KZG proof $\pi_i$
Note that we assume trusted setup is completely in Lagrange basis:
$$
\\ q_i(\omega^m)= \frac{v_m-v_i}{\omega^m-\omega^i}
\quad , i \not= m
\\q_m(\omega^m) = \sum_{j=0,j\not=m}^{d-1}v_j \times TA_{mj} - v_m \times TK_m
\\ \pi_i =\sum_{j=0}^{d-1}q_i(\omega^j) \times TL_j
$$
where
$$
TA_{mj}=\frac{A'(\omega^m)}{A'(\omega^j)}\frac{1}{\omega^m-\omega^j} \quad m \not=j
\\ TK_m = \sum_{j=0,j \not= m}^{d-1} \frac{A'(\omega^m)}{A'(\omega^j)}\frac{1}{\omega^m-\omega^j} = \sum_{j=0, j\not=m}^{d-1}TA_{mj}
$$

Precalculation of $TK_{m}$ allows significantly speed up calculation of $q_m(\omega^m)$ when $V$ is sparse.

Precalculation of $TA_{mj}$ could take a lot, $O(d^2)$, of memory, so probably not worth it when $d$ is large. Pre-calculation of $A'(\omega^i)$ would be enough.

### Some observations
*1*. The formulas above are valid for arbitrary $d$, i.e. not constrained by the condition $\omega^d=1$. We chose to (pre)calculate values $A'(\omega^i)$ instead

*2*. Funny enough, it is not clear how, using the trusted setup, we could even calculate a fake proof $\pi_i^{fake}$ which would state (wrongly) $f(\omega^i)=y$ for arbitrary $y\not=v_i$.

*3*. We can provide proof of *the absense of a key* in the *verkle tree*. For this we just need to provide proof of $v_i=0$ i.e. $f(\omega^i)=0$.

*4*. Since $q_i(\omega^m)$ are all non-zero, calculation of $\pi_i$ requires $d$ operations on the curve. So, calculating the proof is an expensive operation and it does not look like it is possible to optimize it.

*5*. It turns out, we can update any trusted setup with the additional secret $t$ by multiplying its public values without knowing the underlying secret. This property can be used to increase security of the trusted setup the following way:
* let's say we have $N$ unrelated parties
* party $0$ generates trusted setup $T_0$ for its secret $s_0$, destroys it and passes $T_0$ to the party $T_1$.
* And so on: party $j$ receives trusted setup $T_{j-1}$ from the previous party, generates it own secret $s_j$, multiplies previous trusted setup to get the next: $T_{j}=s_j \times T_{j-1}$ and destroys the secret $s_j$.
* the last trusted setup $T=T_{N-1}$ is secure if **any one of $N$** parties were honest, i.e. it destroyed and forgot its secret.

### Using other domain than $\omega^i$
Since we do not use the property of $\omega$ being a root of unity on the field, i.e. $\omega^d=1$, the domain where Lagrange polynomials are calculated can be almost any collection of different values on the field.

For example, in the above we could replace $\omega^i$ with $i$, i.e we'd be using $0, 1, 2, \dots d-1$ on the field as points to calculate the Lagrange basis. The pre-calculated values would become simpler and (pre) calculations faster:
$$
TA_{mj}=\frac{A'(m)}{A'(j)}\frac{1}{m-j} \quad m \not=j
\\ TK_m = \sum_{j=0,j \not= m}^{d-1} \frac{A'(m)}{A'(j)}\frac{1}{m-j} = \sum_{j=0,j \not= m}^{d-1}TA_{mj}
$$

# Annex. Calculating the proof. Naive approach (wrong)

The proof that vector (the committed polynomial) has value $v_i$ in the _i-th_ position is calculated the following way:
$$
\pi_i = \pi_i(T,V, i) = [\frac{f(s)-v_i}{s-\omega^i}]_1
$$
$\pi_i$ is a point on $G_1$, just like $C$. How do we calculate it? Let's expand the formula.

$$
\pi_i = [\frac{\sum_{j=0}^{d-1} v_jl_j(s)}{s-\omega^i}]_1 - [\frac{v_i}{s-\omega^i}]_1 =
\sum_{j=0}^{d-1}{v_j}[\frac{l_j(s)}{s-\omega^i}]_1 - v_i[\frac{1}{s-\omega^i}]_1
$$
So, we only need to pracalculate values $[\frac{l_j(s)}{s-\omega^i}]_1$ and $[\frac{1}{s-\omega^i}]_1$ and make it a part of the *trusted setup*, after that we can calculate $\pi_i$ for any $V$.Right? No!

As it was pointed out by Dankrad Feist in private email, after exposing value $[\frac{1}{s-\omega^i}]_1$ in public we make $\pi_i$ fakeable:

$$
\pi_i^{fake} = \sum_{j=0}^{d-1}{r_j}[\frac{l_j(s)}{s-\omega^i}]_1 - r_i[\frac{1}{s-\omega^i}]_1
\\ = \frac{1}{s-\omega_i}(C-r_i[1]_1)
\\e(\frac{1}{s-\omega^i}(C-r_i[1]_1), [s-\omega^i]_2) = e(C-[r_i]_1, H)
$$
for any $r_i$.

The above means pairing equation is always satisfied for any value we want. It does not make any sense, so, the approach is wrong.