KZG polynomial commitmentsThe KZG polynomial commitment scheme [1] is also known as the Kate method. It allows a committer (Peggy) to commit to a polynomial with a short string. Victor can send Peggy a challenge, and of which she creates a proof against the committed polynomial. It has applications into Credentials and Selective Disclosure of Signed Data. ZKS (zero-knowledge sets), and Veriable Secret Sharing (VSS). We will use a commitment to the polynomial of \(x^3+x+5\). TheoryOverall, \(x G \in \mathbb{G}_1\) defines a point (\(x.G\)) on one curve (\(\mathbb{G}_1)\) and \(x H \in \mathbb{G}_2\) defines a point (\(x.H\)) on the other curve (\(\mathbb{G}_2)\). The notation we will use is: \([x]_1 = x G \in \mathbb{G}_1\) \([x]_2 = x H \in \mathbb{G}_2\) and \(\mathbb{G}_1 = \langle G \rangle\) and \(\mathbb{G}_2 = \langle H \rangle\). \(G\) is the generator of \(\mathbb{G}_1\), and \(H\) is the generator of \(\mathbb{G}_2\). Trusted SetupIn the first part, we use a Trusted Setup, and should be computed with a Multi-Party Computation (MPC). The parameters are generated from random \(\tau \in \mathbb{F}_p\), and from this parameter we can compute \([\tau^i]_1\) and \([\tau^i]_2\) for \(i=0,...,n−1\): \([\tau^i]_1 = ([\tau^0]_1, [\tau^1]_1, [\tau^2]_1, ..., [\tau^{n-1}]_1)\) \([\tau^i]_2 = ([\tau^0]_2, [\tau^1]_2, [\tau^2]_2, ..., [\tau^{n-1}]_2)\) Which in additive representation is: \((G, \tau G, \tau^2 G, ..., \tau^{n-1} G) \in \mathbb{G}_1\) \((H, \tau H, \tau^2 H, ..., \tau^{n-1} H) \in \mathbb{G}_2\) In this stage we have taken a random value (\(\tau\)) and produced a tuple of size \(d+1\) and where \(d\) is the polynomial degree of our target polynomial. We end up with \(\{G,\tau G,\tau^2 G,\tau^3 G,…, \tau^{d} G\}\). After generating this, the random value of \(\tau\) should be deleted. CommitmentWith this we have a polynomial of \(p(x) = \sum^n_{i=0} p_i x^i\) and then can create a commitment with: \(c=[p(\tau)]_1\) and where \(c = \sum^{deg(p(x))}_{i=0} [\tau^i] \cdot p_i\) Peggy ('the prover') would then send this commitment \(c\) to Victor (the verifier) as a proof against the polynomial. Victor would then choose a value \(z \in \mathbb{F}_p\), and where \(\mathbb{F}_p\) is the finite field defined by the polynomial. Evaluating the proofPeggy then computes \(p(z)=y\), and a quotient polynomial is derived as: \(q(x) = \frac{p(x)-y}{x-z}\). This polynomial proves that \(p(z)=y\), and where \(p(x)-y\) is divisible by \(x-z\). This means it has a root at \(z\) - as \(p(z)-y=0\). The evaluation proof is then: \(\pi = [q(\tau)]_1\) and which is determine from \(\pi=\sum^{deg(q(x))}_{i=0} [\tau^i] \cdot q_i\) Peggy can then send this evaluation proof \(\pi\) to Victor. Verifying the proofVictor has the commitment of \(c=[p(\tau)]_1\), the evaluation of \(y=p(z)\), and the proof of \(\pi=[q(\tau)]_1\). He can now check the pairing of: \(\hat{e}(\pi, [\tau]_2 - [z]_2) == \hat{e}(c - [y]_1, H)\) The prover provides \(\pi\) and \(c\) are given by Peggy, and where \([\tau]_2\) is derived in the trusted setup, \([z]_2\) defines the point at which the polynomial has been evaluated with, and \([y]_1\) defines the claimed value of \(p(z)\). This works because: \(\hat{e}(\pi, [\tau]_2 - [z]_2) == \hat{e}(c - [y]_1, H)\) \(\Rightarrow \hat{e}([q(\tau)]_1, [\tau-z]_2) == \hat{e}([p(\tau)]_1 - [y]_1, H)\) \(\Rightarrow [q(\tau) \cdot (\tau-z)]_T == [p(\tau) - y]_T\) For this we see that we have \(q(x)(x-z)=p(x)-y\), and which can be rearranged as \(q(x) = \frac{p(x) - y}{x-z}\). This is evaluated at \(\tau\) for the trusted setup and not known for \(q(\tau) = \frac{p(\tau) - y}{\tau-z}\). CodingHere is the coding for a commitment to the polynomial of \(x^3+x+5\) and where we have a challenge of \(z=3\), and where \(p(3)=3^3+3+5=35\): package main import ( "fmt" "math" "math/big" "os" "strconv" zzz "github.com/arnaucube/kzg-commitments-study" ) func powInt(x, y int) int { return int(math.Pow(float64(x), float64(y))) } func main() { argCount := len(os.Args[1:]) z1 := 3 if argCount > 0 { z1, _ = strconv.Atoi(os.Args[1]) } p := []*big.Int{ big.NewInt(5), big.NewInt(1), // x^1 big.NewInt(0), // x^2 big.NewInt(1), // x^3 } // TrustedSetup ts, _ := zzz.NewTrustedSetup(len(p)) // Commit c := zzz.Commit(ts, p) y1 := powInt(z1, 3) + z1 + 5 // p(z)=y --> p(3)=35 z := big.NewInt(int64(z1)) y := big.NewInt(int64(y1)) fmt.Printf("%v\n", y) // z & y: to prove an evaluation p(z)=y proof, _ := zzz.EvaluationProof(ts, p, z, y) // verification v := zzz.Verify(ts, c, proof, z, y) fmt.Printf("Polynomial: %s\n\n", zzz.PolynomialToString(p)) fmt.Printf("Ts=%v\n\nz=%v\n\ny=%v\n\n", ts, z, y) fmt.Printf("Proof: %s\n\n", proof) fmt.Printf("Verified: %v", v) } and a sample run: Polynomial: x³ + x¹ + 5 Ts=&{[bn256.G1(0000000000000000000000000000000000000000000000000000000000000001, 0000000000000000000000000000000000000000000000000000000000000002) bn256.G1(2e16fb2d6441058fd96668f7011657672bcd4590dd0a27a26bcb3ce4339d435b, 2b1496f37a27b0c0874ba265341b915f6e075cca2bf4524c62de45325d8d89ec) bn256.G1(195cea9981977bb1be1e954e1037e8394875cb13a4ba27ffe4b0410a7d828294, 1f3766199b55276e127cb578483b148b0fd848477b29523d6da9a7105a3ea193) bn256.G1(130b08bd79890c11f9c02ae0d0a73d507e7a0b1d2a6a3d4bdfb9dae383a6e8fb, 1b7ada10ecba4a4c105235ca859f562d4e90ffdae5e8030d6862f3c2cfd1078f)] [bn256.G2((198e9393920d483a7260bfb731fb5d25f1aa493335a9e71297e485b7aef312c2, 1800deef121f1e76426a00665e5c4479674322d4f75edadd46debd5cd992f6ed), (090689d0585ff075ec9e99ad690c3395bc4b313370b38ef355acdadcd122975b, 12c85ea5db8c6deb4aab71808dcb408fe3d1e7690c43d37b4ce6cc0166fa7daa)) bn256.G2((27649cf8bc9235496a95a0eed267ab0575fc0e5ee617030000ed32b7ddefdc2b, 26825048b9c228e19b608c7b5decd53a5933382a2f939450c0e762b28df9d91e), (121a56dd25b40d35fdc66b29ebcb931e38a46d7c35f4ff886bc47cb0931b09f4, 061e6c2d84c94995ad887e089a16bacd786d21b69554e40d061d2872dfad75f7)) bn256.G2((019845d01267e61f923d30c0e6e6d4cf93731a4821c008d87d037e1c9cba446f, 2d88a13dc9ecfc314ed03cb94c3919658e99c52bdda0e18403e1c036f2dea796), (1de3b8cff466dcfe069844a225654a35f573971a855ab1d2771083fe0d9f1c41, 14b34109ba5ac99b67139e44adce4c395f260ec7ce0b8d97ed1d4a8db0ca16ea)) bn256.G2((290c20c370ffd4bf2d928265eef38f85934b9e7c75511f4e4a7a068278ee5298, 17596d2ed876e2198fecc136ea3bf189d6a97b25da28be2218693aa93bc761ed), (2363ba96a818adbf3e6f95d8b5c19daf3a0fbd789ba22be82de387ef79399314, 17e9091710f525baa7f8fad9ba636a193abf138f75fe3117280b99e468c66785))]} z=3 y=35 Proof: bn256.G1(0a0d867417b725296c5f749cb0dcc5c39b6b07572c9c7f95a831672acd242abe, 0d1c632b099402acc37d35f03d69c4d07ffa399a28c4f4ad0a2f6f210fb3075f) Verified: true References[1] Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-size commitments to polynomials and their applications. In Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16 (pp. 177-194). Springer Berlin Heidelberg. |