Multilinear KZG Polynomial commitment scheme

exploring KZG polynomial commitment scheme on Multilinear polynomial

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 Boolean 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 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.

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;

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 known as making an evaluation and creating a proof for this evaluation;

This is how the interface of the open_fn would look like;

    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$$

1. 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 \cdot 4$	$8$

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$

Special credit to;

Proofs, Arguments, and Zero-Knowledge by Justin Thaler

Mike Francis

Rust Implementation:

https://github.com/developeruche/cryptography-n-zk-research/blob/main/polynomial-commitment-schemes/kzg-rust/src/multilinear.rs