polynomial commitment and KZG commitment
polynomial commitment and KZG commitment
Merkle tree commitment:
- commitment = root hash (For SHA256, 32 bytes)
- Proof: log(n)log(n) proof size
- Application: state trie / Merkle Patricia Trie
KZG commitment:
- commitment = 48 bytes (a Jacobian elliptic curve point)
- Proof: 48 bytes (no matter nn is)
- Multi-point proof/batch proof yi(0),yi(1),⋯,yi(m−1)yi(0),yi(1),⋯,yi(m−1): 48 bytes (no matter nn is)
- Multi-polynomial commitment、proof aggregation
- Application: Stateless (Verkle tree), DAS (data availability sampling)
Overall procedures of KZG
1 | Knowledge ->(Point-Values ->) Coefficients -> Commitment -> Open&Prove&Verify |
Encode data into Polynomial
Give (xi,yi)(xi,yi), xi≠xj∀i≠jxi≠xj∀i≠j, there are two way to encode the data into the polynomial.
If the xixi is just indices without other sense, then only data is valuable. The data can be converted into integers and treated as the coefficients of the polynomial.
Regardless of whether xixi is a sequential index, whether it stores information or not, these points can be treated as the point-value representation of the polynomials. The Inverse FFT can be used to convert the point-value representation to coefficient representation.
Normally, the binary or integer data are encoded into a finite field FqFq, q is a prime such that {0, 1, 2, , q-1} modulo q.
a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. -- wikipedia
Elliptic curve groups are additive groups; that is, their basic function is addition. When it comes to the multiplication of curve points, the pairing is introduced.
Polynomial on Elliptic curve
Elliptic curve G1=[0,G1,G1+G1=[2]G2,⋯,[q]G1]G1=[0,G1,G1+G1=[2]G2,⋯,[q]G1], where [q+1]G1=0[q+1]G1=0
[f(x)]G1=[∑ni=0aixi]G1=∑ni=0ai([xiG1])=∑ni=0ai[xi]1[f(x)]G1=[∑ni=0aixi]G1=∑ni=0ai([xiG1])=∑ni=0ai[xi]1
Polynomial Commitment with Trusted Setup
a secret s∈Fqs∈Fq can be generates, such that
- nobody knows the ss (private key of 'god')
- [si]G1=[si]1,i=1,⋯[si]G1=[si]1,i=1,⋯ and [si]G2=[si]2,j=1,⋯[si]G2=[si]2,j=1,⋯ is known to everybody. (public key of 'god')
- Benefiting from the discrete log problem of the Elliptic curve, no one can recover sisi though [si]1or[si]2[si]1or[si]2
If you are familiar with the secret key in EDCSA signature, that's it. The [si]Gi,[si]G2[si]Gi,[si]G2 can be seen as the public key.
Nowdays, popular way to generate ss is MPC. Besides, Ethereum is doing KZG ceremony, ethereum/kzg-ceremony-specs: Specs for Ethereum's KZG Powers of Tau Ceremony. The degree of G2G2 is significantly smaller than G1G1. Therefore, in pairings, the high degree part should match with G1G1 and the low degree part with $G_2".
Commitment: Com=[f(s)]1=∑ni=0[aisi]G1=∑ni=0ai[si]1Com=[f(s)]1=∑ni=0[aisi]G1=∑ni=0ai[si]1, where Com is actually a point on the elliptic curve.
From the Schwartz-Zippel Lemma, finding a random x0x0 such that the probability of F(x0)=f(s)F(x0)=f(s) is impossible.
Single proof
Given xixi, we want to prove the computing result yi=f(xi)yi=f(xi),
f(x)−yi=q(x)(x−xi)q(x)=f(x)−y0x−x0
Let's integrate the formula with an elliptic curve,
G1=[q(x)(x−xi)]G1[f(x)]1−[yi]1=?
However, q(x)xG1−q(x)xiG1 cannot be evaluated at coordinate x=s without knowing s. To solve the problem, q(x) and x−xi need to be split into multiplication. While the pairing allows to "multiply" the exponents of two group elements, while the usual group structure only allows adding or subtracting exponents
So let pairing, e:G1×G2→GT
G1G2=[q(s)(s−xi)]G1G2e([f(s)−yi]G1,G2)=e(q(s)G1,(s−xi)G2)e([f(s)]1−[yi]1,G2)=e([q(s)]1,[s]2−[xi]2)e(Com−[yi]1,G2)=e([q(s)]1,[s]2−[xi]2),
where q(s)1 is the proof (48 bytes as a point on an elliptic curve).
Great, the above all can be calculated without s.
Note: Not all curve can do pairing, G1 and G2 is pairing-friendly.
For multi-proof, assume that you have an interpolation polynomial I(X) such that I(xi)=yi, where (xi,yi) is a list of evaluation points.
q(x)=f(x)−I(x)∏(x−xi)
Polynomial Commitment 的其他实现
- KZG:PLONK、Marlin
- FRI:zkSTARK
- IPA:Bulletproof
- IPA + Halo-style aggregation:Halo 2

- KZG Commitment 的优缺点
- 缺点:需要 Trusted Setup
- 优点:proof 长度短且恒定
TODO
后面读一下 kzg 原论文
多项式承诺计算就是 MSM,MSM 的高效实现 pippenger 算法
References
- Recommended KZG 多项式承诺 | Dankrad Feist
- Polynomial Commitment KZG with Examples ( part 1 ) - YouTube
- KZG in Practice: Polynomial Commitment Schemes and Their Usage in Scaling Ethereum - Scroll
- Why "pairings on elliptic curve" are used? - Cryptography Stack Exchange
- 零知识证明 KZG Commitment 1: Polynomial Commitment 20221129 - YouTube
- Polynomial (KZG or Kate) Commitment (DappLearning) Notes
- KZG Polynomial Commitments. This article is based on Dankrad… | by Ozgun Ozerk | Subspace Network
- [./media/kzg_exercise_sol.pdf]