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+4f(x,y) = 2xy + x + y + 4

it evaluation form can be expressed in this manner;

Boolean Hypercube
Poly Eval
Evaluation result

0,00,0

f(0,0)f(0,0)

44

0,10,1

f(0,1)f(0,1)

55

1,01,0

f(1,0)f(1,0)

55

1,11,1

f(1,1)f(1,1)

88

f(x,y)=[4,5,5,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ā„“Ļ„ ∈F^ā„“. That is, if χ1,...,χ2ℓχ_1, . . . , χ_{2^ā„“} denotes an enumeration of the 2ā„“2^ā„“ Lagrange basis polynomials, the SRS equals (gχ1(Ļ„),...,gχ2ā„“(Ļ„))(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Ļ„ā„“āˆ’1g^{Ļ„_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=0ciχi(X)q(X) = āˆ‘^{2ā„“}{i=0} c_iχ_i(X), then

gq(Ļ„)=āˆ2ā„“i=0(gχi(Ļ„))cig^{q(Ļ„)} = āˆ^{2ā„“}{i=0} (g^{χ_i(Ļ„)})^{c_i}

which can be computed given the values gχi(r)g^{χ_i(r)} for all i=0,...,2ā„“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∈Fpā„“z ∈ F^ā„“_p to some value vv, i.e., to prove that q(z)=vq(z) = v, the committer computes a series of ā„“ā„“ ā€œwitness polynomialsā€ w1,...,wā„“w_1, . . . , w_ā„“, defined in the following fact. For any fixed z=(z1,...,zā„“)∈Fpā„“z = (z_1, . . . , z_ā„“) ∈ F^ā„“_p and any multilinear polynomial qq, q(z)=vq(z) = v if and only if there is a unique set of ā„“ā„“ multilinear polynomials w1,...,wā„“w_1, . . . , w_ā„“ such that;

q(X)āˆ’v=āˆ‘i=1ā„“(Xiāˆ’zi)wi(X)q(X)āˆ’v = āˆ‘^ā„“_{i=1}(X_iāˆ’z_i)w_i(X)

If q(X)āˆ’vq(X)āˆ’v can be expressed as the right part of the equation above then clearly q(z)āˆ’v=0q(z)āˆ’v = 0, and hence q(z)=vq(z) = v.

On the other hand, suppose that q(z) = v. Then by dividing the polynomial q(X)āˆ’vq(X)āˆ’v by the polynomial (X1āˆ’z1)(X_1āˆ’z_1), we can identify multilinear polynomials w1w_1 and s1s_1 such that;

q(X)āˆ’v=(X1āˆ’z1)ā‹…w1(X1,X2,...,Xā„“)+s1(X2,X3,...,Xā„“)q(X)āˆ’v = (X_1āˆ’z_1)Ā·w_1(X_1, X_2, . . . , X_ā„“) + s_1(X_2, X_3, . . . , X_ā„“)

where s1(X2,X3,...,Xā„“)s_1(X_2, X_3, . . . , X_ā„“) is the remainder term, and does not depend on variable X1X_1. Iterating this process, we can divide s1s_1 by the polynomial (X2āˆ’Z2)(X_2āˆ’Z_2) to write;

q(X)āˆ’v=(X1āˆ’z1)ā‹…w1(X1,X2,...,Xā„“)+(X2āˆ’z2)ā‹…w2(X2,...,Xā„“)+s2(X3,X4,...,Xā„“)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ā„“(Xiāˆ’zi)ā‹…wi(X1,X2,...,Xā„“)+sā„“q(X)āˆ’v = āˆ‘^ā„“_{i=1}(X_iāˆ’z_i)Ā·w_i(X_1, X_2, . . . , X_ā„“) + s_ā„“

where sā„“s_ā„“ depends on no variables, i.e., sā„“s_ā„“ is simply an element in FpF_p. Since q(z)āˆ’v=0q(z)āˆ’v = 0, it must hold that sā„“=0s_ā„“ = 0, completing the proof.

To open the commitment at input z∈Fpā„“z ∈ F^ā„“_p to value vv, the prover computes w1,...,wā„“w_1, . . . , w_ā„“ and sends to the verifier values y1,...,yā„“y_1, . . . , y_ā„“ claimed to equal gwi(Ļ„)g^{w_i(Ļ„)} for i=1,...,ā„“i= 1, . . . , ā„“. Again, since each wiw_i is multilinear, gwi(Ļ„)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(yi,gĻ„iā‹…gāˆ’zi)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+3f(x,y) = 2xy + 4x + 3

This is it representation in evaluation form over the boolean hypercube;

Boolean Hypercube
Poly Eval
Evaluation result

0,00,0

f(0,0)f(0,0)

33

0,10,1

f(0,1)f(0,1)

33

1,01,0

f(1,0)f(1,0)

77

1,11,1

f(1,1)f(1,1)

99

f(x,y)=[3,3,7,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τ_x = 2, τ_y = 4
  1. Perform the SRS generation step;

Boolean Hypercube
Operation
Result

0,00,0

(1āˆ’2)(1āˆ’4)(1-2)(1-4)

33

0,10,1

(1āˆ’2)4(1-2)4

āˆ’4-4

1,01,0

2(1āˆ’4)2(1-4)

āˆ’6-6

1,11,1

2ā‹…42 \cdot 4

88

Commitment

f(x,y)=[3,3,7,9]f(x,y) = [3, 3, 7, 9]

[g3,gāˆ’4,gāˆ’6,g8][g^3, g^{-4}, g^{-6}, g^8]

[(g3)3+(gāˆ’4)3+(gāˆ’6)7,(g8)9][(g^3)^3 + (g^{-4})^3 + (g^{-6})^7, (g^8)^9]

commitment=[g9+gāˆ’12+gāˆ’42,g72]=g27commitment = [g^9 + g^{-12} + g^{-42}, g^{72}] = g^{27}

Opening

open at x=2x = 2, y=3y = 3;

factors = (xāˆ’2)(x - 2) and (yāˆ’3)(y - 3)

evaluating => 2(2*3) + 4(2) + 3 = 12 + 8 + 3 = 23

2xy+4x+3āˆ’23=0=>2xy+4xāˆ’202xy + 4x + 3 - 23 = 0 => 2xy + 4x - 20

qpx=2xy+4xāˆ’20/xāˆ’2=2y+4q_{px} = 2xy + 4x - 20 / x - 2 = 2y + 4 rem 4yāˆ’124y - 12

qpy=4yāˆ’12/yāˆ’3=4q_{py} = 4y - 12 / y - 3 = 4

proofx=2y+4=2(4)+4=8+4=12proof_x = 2y + 4 = 2(4) + 4 = 8 + 4 = 12 proofy=4proof_y = 4

Verification

f(Ļ„x,Ļ„y)āˆ’f(2,3)=āˆ‘i=1ā„“(Ļ„iāˆ’zi)āˆ—qpif(Ļ„_x, Ļ„_y) - f(2,3) = āˆ‘^ā„“_{i=1}(Ļ„_i - z_i) * qp_i
(g127āˆ’g123)āˆ—g21=((g22āˆ’g22)āˆ—g112)+((g24āˆ’g23)āˆ—g14)(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)
g14āˆ—g21=(g20āˆ—g112)+(g21āˆ—g14)g_1^4 * g_2^1 = (g_2^0 * g_1^{12}) + (g_2^1 * g_1^4)

g34=g30+g34g_3^4 = g_3^0 + g_3^4

g34=g34g_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

Last updated