# Multilinear KZG Polynomial commitment scheme
Similar to the Univariate KZG Polynomial commitment scheme, this interface of this commitment scheme entails;
1. Generate SRS
2. Commit function
3. Opening
4. Verification
Because we would be dealing with multiple variables, finding a way to efficiently find tone these functions to meet the demands placed my these multiple variables in terms of security and succinctness.
KZG PCS on multilinear polynomials is quite different compare to that of the Univariate polynomial, first this multilinear polynomial is expressed as an evaluation of the polynomial of the bolean hypercube where the size of the boolean hypercube `n` is directly proportional to the number of variables `n_var` of the multilinear polynomial.
Example;
Given this multilinear polynomial,
$f(x,y) = 2xy + x + y + 4$
it evaluation form form can be expressed in this manner;
| Boolean Hypercube | Poly Eval | Evaluation result |
| ----------------- | --------- | ----------------- |
| $0,0$ | $f(0,0)$ | $4$ |
| $0,1$ | $f(0,1)$ | $5$ |
| $1,0$ | $f(1,0)$ | $5$ |
| $1,1$ | $f(1,1)$ | $8$ |
$f(x,y) = [4, 5, 5, 8]$
## Generating the Shared Reference String (SRS)
The structured reference string (SRS) now consists of encodings in $G$ of all powers of all Lagrange basis polynomials evaluated at a randomly chosen input $τ ∈F^ℓ$. That is, if $χ_1, . . . , χ_{2^ℓ}$ denotes an enumeration of the $2^ℓ$ Lagrange basis polynomials, the SRS equals $(g^{χ_1(τ)}, . . . , g^{χ_{2^ℓ}(τ)})$. Once again, the toxic waste that must be discarded because it can be used to destroy binding is the value $τ$ having in mind that $ℓ$ is the number of variable of the multilinear polynomial.
```rust
pub struct MultiLinearSRS<P: Pairing> {
pub g1_power_of_taus: Vec<P::G1>, // this is an expression of g1^tau^i over the boolean hypercube (every possible combination of each monomial)
pub g2_power_of_taus: Vec<P::G2>, // this is a vector of g2^tau^i
}
```
This is the interface of `MultilinearSRS`, ww have already obtained `g1_power_of_taus`, getting ``
`g2_power_of_taus` is relatively easier, we just need to perform the group operation on the vector of tau using the generator from `G2`;
$g2\_power\_of\_taus = g^{τ_0}....g^{τ_{ℓ-1}}$
## Commit Function
This function simply commits to the polynomial return a Group element representing the commitment to this polynomial and can be used for verification in the future. This is how the function interface looks like;
```rust
fn commit<F: PrimeField>(srs: &MultiLinearSRS<P>, poly: &Multilinear<F>) -> P::G1
```
Function takes in the `srs`, `poly` to commit to and returns the commitment to the polynomial.
This commit function is quite simple, it involves performing the group operation on the element in the `srs` and the evaluation element in the `poly`. Representing this mathematically;
if $q(X) = ∑^{2ℓ}_{i=0} c_iχ_i(X)$, then $g^{q(τ)} = ∏^{2ℓ}_{i=0} (g^{χ_i(τ)})^{c_i}$ , which can be computed given the values $g^{χ_i(r)}$ for all $i= 0, . . . , 2^ℓ$ even without knowing $τ$.
## Opening Function
This is also know as making an evaluation and creating a proof for this evaluation;
This is how the interface of the `open_fn` would look like;
```rust
fn open<F: PrimeField>(
srs: &MultiLinearSRS<P>,
poly: &Multilinear<F>,
points: &[F],
) -> (F, Vec<<P as Pairing>::G1>)
```
This function would take in the `srs`, `poly`, the points at which the polynomial would be evaluated at `points` returning the evaluation of this polynomial and commitment to this polynomial `Vec<GroupElements>` where is element is a commitment associated with one variable of the polynomial.
**Mathematically**
To open the commitment at input $z ∈ F^ℓ_p$ to some value $v$, i.e., to prove that $q(z) = v$, the committer computes a series of $ℓ$ “witness polynomials” $w_1, . . . , w_ℓ$, defined in the following fact.
For any fixed $z = (z_1, . . . , z_ℓ) ∈ F^ℓ_p$ and any multilinear polynomial $q$, $q(z) = v$ if and only if there is a unique set of $ℓ$ multilinear polynomials $w_1, . . . , w_ℓ$ such that;
$$
q(X)−v = ∑^ℓ_{i=1}(X_i−z_i)w_i(X)
$$
If $q(X)−v$ can be expressed as the right part of the equation above then clearly $q(z)−v = 0$, and hence $q(z) = v$.
On the other hand, suppose that q(z) = v. Then by dividing the polynomial $q(X)−v$ by the polynomial $(X_1−z_1)$, we can identify multilinear polynomials $w_1$ and $s_1$ such that;
$$
q(X)−v = (X_1−z_1)·w_1(X_1, X_2, . . . , X_ℓ) + s_1(X_2, X_3, . . . , X_ℓ)
$$
where $s_1(X_2, X_3, . . . , X_ℓ)$ is the remainder term, and does not depend on variable $X_1$. Iterating this process, we can divide $s_1$ by the polynomial $(X_2−Z_2)$ to write;
$$
q(X)−v = (X_1−z_1)·w_1(X_1, X_2, . . . , X_ℓ) + (X_2−z_2)·w_2(X_2, . . . , X_ℓ) + s_2(X_3, X_4, . . . , X_ℓ)
$$
and so forth until we have written;
$$
q(X)−v = ∑^ℓ_{i=1}(X_i−z_i)·w_i(X_1, X_2, . . . , X_ℓ) + s_ℓ
$$
where $s_ℓ$ depends on no variables, i.e., $s_ℓ$ is simply an element in $F_p$. Since $q(z)−v = 0$, it must hold that $s_ℓ = 0$, completing the proof.
To open the commitment at input $z ∈ F^ℓ_p$ to value $v$, the prover computes $w_1, . . . , w_ℓ$ and sends to the verifier values $y_1, . . . , y_ℓ$ claimed to equal $g^{w_i(τ)}$ for $i= 1, . . . , ℓ$. Again, since each $w_i$ is multilinear, $g^{w_i(τ)}$ can be computed from the `SRS` despite the fact that the prover does not know $τ$.
## Verification
The verification stage is less trouble than the opening fn, this major operations that would be done here are creation of some elliptic curve pairings, summation of some pairings and a pairing assertion.
Mathematically, this can be represented by;
$$
e(c·g^{−v}, g) = ∏^ℓ_{i=1} e(y_i, g^{τ_i}·g^{−z_i})
$$
This look complete, yes! it is, but still confusing...
## Example
given a polynomial;
$f(x,y) = 2xy + 4x + 3$
This is it representation in evaluation form over the boolean hypercube;
| Boolean Hypercube | Poly Eval | Evaluation result |
| ----------------- | --------- | ----------------- |
| $0,0$ | $f(0,0)$ | $3$ |
| $0,1$ | $f(0,1)$ | $3$ |
| $1,0$ | $f(1,0)$ | $7$ |
| $1,1$ | $f(1,1)$ | $9$ |
$f(x,y) = [3, 3, 7, 9]$
**Trusted Setup**
1. Generate a vector of tau where the length of this vector is the number of variables in the polynomial.
$$
τ_x = 2, τ_y = 4
$$
2. Perform the SRS generation step;
| Boolean Hypercube | Operation | Result |
| ----------------- | ------------ | ------ |
| $0,0$ | $(1-2)(1-4)$ | $3$ |
| $0,1$ | $(1-2)4$ | $-4$ |
| $1,0$ | $2(1-4)$ | $-6$ |
| $1,1$ | $2 * 4$ | $8$ |
SRS = {
g1_points: $[g^3, g^{-4}, g^{-6}, g^8]$
g2_points: $[g^2, g^4]$
}
**Commitment**
$f(x,y) = [3, 3, 7, 9]$
$[g^3, g^{-4}, g^{-6}, g^8]$
$[(g^3)^3 + (g^{-4})^3 + (g^{-6})^7, (g^8)^9]$
$commitment = [g^9 + g^{-12} + g^{-42}, g^{72}] = g^{27}$
**Opening**
open at $x = 2$,$ y = 3$ ; factors = $(x - 2)$ and $(y - 3)$
evaluating => $2(2*3) + 4(2) + 3 = 12 + 8 + 3 = 23$
$2xy + 4x + 3 - 23 = 0 => 2xy + 4x - 20$
$q_{px} = 2xy + 4x - 20 / x - 2 = 2y + 4$ rem $4y - 12$
$q_{py} = 4y - 12 / y - 3 = 4$
$proof_x = 2y + 4 = 2(4) + 4 = 8 + 4 = 12$
$proof_y = 4$
**Verification**
$f(τ_x, τ_y) - f(2,3) = ∑^ℓ_{i=1}(τ_i - z_i) * qp_i$
$(g_1^{27} - g_1^{23}) * g_2^1 = ((g_2^2 - g_2^2) * g_1^{12})+ ((g_2^4 - g_2^3) * g_1^4)$
$g_1^4 * g_2^1 = (g_2^0 * g_1^{12}) + (g_2^1 * g_1^4)$
$g_3^4 = g_3^0 + g_3^4$
$g_3^4 = g_3^4$
Specical credit to;
Proofs, Arguments, and Zero-Knowledge by [Justin Thaler](https://x.com/SuccinctJT)
[Mike Francis ](https://x.com/only1franchesco)
Sign in with Wallet
Connect another wallet