> For the complete documentation index, see [llms.txt](https://developeruche.gitbook.io/computational-proof-systems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://developeruche.gitbook.io/computational-proof-systems/protocol-and-primitives/chapter-three-ploynomial-commitment-schemes/kzg-polynomial-commitment-scheme/multilinear-kzg-polynomial-commitment-scheme.md). # 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. ```rust pub struct MultiLinearSRS { pub g1_power_of_taus: Vec, // this is an expression of g1^tau^i over the boolean hypercube (every possible combination of each monomial) pub g2_power_of_taus: Vec, // 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(srs: &MultiLinearSRS

, poly: &Multilinear) -> 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; ```rust fn open( srs: &MultiLinearSRS

, poly: &Multilinear, points: &[F], ) -> (F, Vec<

::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` 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 \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](https://x.com/SuccinctJT) [Mike Francis](https://x.com/only1franchesco) Rust Implementation: {% @github-files/github-code-block url="" %}