本文主要是介绍Plonky3和Binius中的Brakedown多项式承诺协议解析及优化（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3. Breakdown Commitment
3.1 Linear Codes Polynomial Commitments
Breakown的基础就是使用线性码构建多项式承诺，优点在于证明大小和验证时间复杂度都是长度的平方根。
下面给出一个简单的线性码多项式承诺过程。假设多项式 g g g的系数向量的长度为 n n n，并且可以使用填充0的方式扩充到 d = k 2 d=k^2 d=k2且 d ≥ n d \geq n d≥n。因此有:
g ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a d − 1 x d − 1 = ∑ i = 0 d − 1 a i x i = [ 1 , x , x 2 , ⋯ , x k − 1 ] [ b 1 , 1 b 1 , 2 ⋯ b 1 , k b 2 , 1 b 2 , 2 ⋯ b 2 , k ⋮ ⋮ ⋱ ⋮ b k , 1 b k , 2 ⋯ b k , k ] [ 1 x k x 2 k ⋮ x ( k − 1 ) k ] = ∑ p = 1 k ∑ q = 1 k b p , q x ( p − 1 ) + ( q − 1 ) k \begin{aligned} g(x)&=a_0+a_1x+a_2x^2+\cdots+a_{d-1}x^{d-1}=\sum_{i=0}^{d-1}a_ix^i\\ &=[1,x,x^2,\cdots,x^{k-1}]\left[\begin{matrix}b_{1,1}&b_{1,2}&\cdots &b_{1,k}\\b_{2,1}&b_{2,2}&\cdots &b_{2,k}\\ \vdots &\vdots&\ddots &\vdots\\b_{k,1}&b_{k,2}&\cdots &b_{k,k}\end{matrix}\right]\left[\begin{matrix}1\\x^k\\ x^{2k}\\ \vdots\\x^{(k-1)k}\end{matrix}\right]\\ &=\sum_{p=1}^{k}\sum_{q=1}^{k}b_{p,q}x^{(p-1)+(q-1)k} \end{aligned} g(x)=a0+a1x+a2x2+⋯+ad−1xd−1=i=0∑d−1aixi=[1,x,x2,⋯,xk−1] b1,1b2,1⋮bk,1b1,2b2,2⋮bk,2⋯⋯⋱⋯b1,kb2,k⋮bk,k 1xkx2k⋮x(k−1)k =p=1∑kq=1∑kbp,qx(p−1)+(q−1)k
通过上式，把长度为 d = k 2 d=k^2 d=k2的多项式系数转化为 k k k阶方阵 B \mathbf{B} B，我们希望仅需构造一个证明大小为行数 k = d k=\sqrt{d} k=d的多项式承诺就可等价于原长度为 d d d的多项式承诺，要实现这一点还需要借助线性纠错码(如上小节介绍的Linear-Time Encoding)和Merkle树。
首先，使用线性纠错码对方阵 B \mathbf{B} B的每一行编码，记为 E n c ( B i ) \mathbf{Enc}(\mathbf{B}_i) Enc(Bi)，将其扩展为 k × m k\times m k×m的矩阵 C \mathbf{C} C，其中 l l l为码字长度(这里为了确保
l l l不会太大，所以一般采用码率为常数的编码方式)。
[ b 1 , 1 b 1 , 2 ⋯ b 1 , k b 2 , 1 b 2 , 2 ⋯ b 2 , k ⋮ ⋮ ⋱ ⋮ b k , 1 b k , 2 ⋯ b k , k ] ⟹ L i n e a r C o d e s [ c 1 , 1 c 1 , 2 ⋯ c 1 , m c 2 , 1 c 2 , 2 ⋯ c 2 , m ⋮ ⋮ ⋱ ⋮ c k , 1 c k , 2 ⋯ c k , m ] \left[\begin{matrix}b_{1,1}&b_{1,2}&\cdots &b_{1,k}\\b_{2,1}&b_{2,2}&\cdots &b_{2,k}\\ \vdots &\vdots&\ddots &\vdots\\b_{k,1}&b_{k,2}&\cdots &b_{k,k}\end{matrix}\right]\stackrel{Linear Codes}{\Longrightarrow} \left[\begin{matrix}c_{1,1}&c_{1,2}&\cdots &c_{1,m}\\c_{2,1}&c_{2,2}&\cdots &c_{2,m}\\ \vdots &\vdots&\ddots &\vdots\\c_{k,1}&c_{k,2}&\cdots &c_{k,m}\end{matrix}\right] b1,1b2,1⋮bk,1b1,2b2,2⋮bk,2⋯⋯⋱⋯b1,kb2,k⋮bk,k ⟹LinearCodes c1,1c2,1⋮ck,1c1,2c2,2⋮ck,2⋯⋯⋱⋯c1,mc2,m⋮ck,m
然后，对矩阵的每一列( k k k个值)进行承诺并建立第一个Merkle树，并以每一列Merkle树的根哈希作为叶子节点(共 l l l个)建立第二个Merkle树。最后，基于第二个Merkle树来构建多项式承诺即可。
在取值证明的计算中，需要完成两步，一是Proximity Test，二是Consistency Test。Proximity Test保证了需要检查 Merkle Tree所承诺的矩阵确实承诺了 k = d k=\sqrt{d} k=d个码字。Consistency Test保证原来的求值点向量 与原始矩阵的乘积与结果向量之间的一致性。
Proximity Test :Verifier向Prover发送一个长度为 k k k的随机向量 r = [ r 1 , r 2 , ⋯ ， r k ] r=[r_1,r_2,\cdots，r_k] r=[r1,r2,⋯，rk]，之后Prover计算这个随机向量与方阵 B \mathbf{B} B的乘积，得到一个长度为 k k k的目标向量 u u u（ u u u相当于是方阵 B \mathbf{B} B在向量 r r r下的随即线性组合），Prover 将 u u u返回给 Verifier，Verifier 收到 u u u后，需要检查其与承诺值 u ^ = [ u ^ 1 , u ^ 2 , ⋯ , u ^ m ] \hat{u}=[\hat{u}_1,\hat{u}_2,\cdots,\hat{u}_m] u^=[u^1,u^2,⋯,u^m]的一致性（ u ^ i \hat{u}_i u^i表示编码后矩阵 C \mathbf{C} C的第 i ( 0 ≤ i ≤ m ) i(0\leq i \leq m) i(0≤i≤m)列）。
首先,Verifier对 u u u进行编码，得到 E n c ( u ′ ) \mathbf{Enc}(u') Enc(u′)，然后,Verifier根据 r r r和 u ^ \hat{u} u^计算一个向量 ν \nu ν
ν = ∑ i = 1 k r i ⋅ u ^ i \nu=\sum_{i=1}^{k}{r_i\cdot\hat{u}_i} ν=i=1∑kri⋅u^i
然后Verifier选择 E n c ( u ′ ) \mathbf{Enc}(u') Enc(u′)中 l l l个（ l = Θ ( λ ) l=\Theta(\lambda) l=Θ(λ) 个）随机点，检查这些点是否都与向量 ν \nu ν对应位置的值相等，若均相等，则Proximity Test通过，这里用到了线性码的基本性质：码字之间的任意线性组合仍然是一个码字。
Consistency Test：该步骤和Proximity Test的工作差不多，只不过将随机向量 r r r替换为一个特定向量 q 1 \mathbf{q}_1 q1。接下来看如何获得 q 1 \mathbf{q}_1 q1。
首先多项式取值可以表示为系数矩阵与坐标矩阵的内积：
g ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a d − 1 x d − 1 = ⟨ X , B ⟩ = ⟨ [ x 0 x 1 ⋯ x k − 1 x k x k + 1 ⋯ x 2 k − 1 ⋮ ⋮ ⋱ ⋮ x ( k − 1 ) k x ( k − 1 ) k + 1 ⋯ x k 2 − 1 ] , [ b 1 , 1 b 1 , 2 ⋯ b 1 , k b 2 , 1 b 2 , 2 ⋯ b 2 , k ⋮ ⋮ ⋱ ⋮ b k , 1 b k , 2 ⋯ b k , k ] ⟩ \begin{aligned} g(x)&=a_0+a_1x+a_2x^2+\cdots+a_{d-1}x^{d-1}\\ &=\langle\mathbf{X},\mathbf{B}\rangle\\ &=\Bigg\langle\left[\begin{matrix}x^{0}&x^{1}&\cdots &x^{k-1}\\x^{k}&x^{k+1}&\cdots &x^{2k-1}\\ \vdots &\vdots&\ddots &\vdots\\x^{(k-1)k}&x^{(k-1)k+1}&\cdots &x^{k^2-1}\end{matrix}\right],\left[\begin{matrix}b_{1,1}&b_{1,2}&\cdots &b_{1,k}\\b_{2,1}&b_{2,2}&\cdots &b_{2,k}\\ \vdots &\vdots&\ddots &\vdots\\b_{k,1}&b_{k,2}&\cdots &b_{k,k}\end{matrix}\right]\Bigg\rangle\\ \end{aligned} g(x)=a0+a1x+a2x2+⋯+ad−1xd−1=⟨X,B⟩=⟨ x0xk⋮x(k−1)kx1xk+1⋮x(k−1)k+1⋯⋯⋱⋯xk−1x2k−1⋮xk2−1 , b1,1b2,1⋮bk,1b1,2b2,2⋮bk,2⋯⋯⋱⋯b1,kb2,k⋮bk,k ⟩
在上式中，方阵 X \mathbf{X} X可以表示为两个长度为 k k k的向量 q 1 \mathbf{q}_1 q1和 q 2 \mathbf{q}_2 q2的张量积，所以有：
g ( x ) = ⟨ q 1 ⊗ q 2 , B ⟩ \begin{aligned} g(x)=\langle\mathbf{q}_1\otimes\mathbf{q}_2,\mathbf{B} \rangle\end{aligned} g(x)=⟨q1⊗q2,B⟩
也就是说，对于多项式的的任意输入 q q q，均存在两个向量 q 1 \mathbf{q}_1 q1和 q 2 \mathbf{q}_2 q2，使得 g ( q ) = ⟨ q 1 ⊗ q 2 , B ⟩ \begin{aligned} g(q)=\langle\mathbf{q}_1\otimes\mathbf{q}_2,\mathbf{B} \rangle\end{aligned} g(q)=⟨q1⊗q2,B⟩。
在Consistency Test阶段就是用 q 1 \mathbf{q}_1 q1替换Proximity Test中的 r r r， q 1 \mathbf{q}_1 q1与方阵 B \mathbf{B} B的相乘得到 u ′ ′ u'' u′′，这个步骤中，如果Prover是诚实的，则 u ′ ′ u'' u′′必然满足：
⟨ u ′ ′ , q 2 ⟩ = ⟨ q 1 ⊗ q 2 , B ⟩ \langle u'',\mathbf{q}_2 \rangle=\langle \mathbf{q}_1 \otimes\mathbf{q}_2,\mathbf{B} \rangle ⟨u′′,q2⟩=⟨q1⊗q2,B⟩
否则测试不通过。完整的承诺方案如下所示。
Commit:
- P → V: a commit vector u ^ = ( u ^ 1 , . . . , u ^ m ) ∈ F m \hat{u} = (\hat{u}_1, ..., \hat{u}_m) \in \mathbf{F}^m u^=(u^1,...,u^m)∈Fm. If P is honest, each “row” u ^ i \hat{u}_i u^i of u ^ \hat{u} u^ contains a codeword in E n c \mathbf{Enc} Enc.
Proximity Test:
- V → P: a random vector r ∈ F k r \in \mathbf{F}^k r∈Fk.
- P → V: a vector u ′ ∈ F k u' \in \mathbf{F}^k u′∈Fk. claimed to equal v = ∑ i = 1 k r i ⋅ u i ∈ F k v = \sum_{i=1}^k r_i \cdot u_i \in \mathbf{F}^k v=∑i=1kri⋅ui∈Fk.
- // Now V probabilistically checks consistency between u ^ \hat{u} u^ and u ′ u' u′ (V reads the entirety of u ^ \hat{u} u^).
- V: chooses Q Q Q to be a random set of size l = Θ ( λ ) l = \Theta(\lambda) l=Θ(λ) . For each j ∈ Q j \in Q j∈Q:
- V queries all m m m entries of the corresponding “column” of u ^ \hat{u} u^, namely u ^ 1 , j , . . . , u ^ m , j \hat{u}_{1,j}, ..., \hat{u}_{m,j} u^1,j,...,u^m,j.
- V confirms E n c ( u ′ ) j = ∑ i = 1 m r ⋅ u ^ i , j \mathbf{En}c(u')_j = \sum_{i=1}^m r \cdot \hat{u}_{i,j} Enc(u′)j=∑i=1mr⋅u^i,j, halting and rejecting if not.
Consistency Test
- Let q 1 , q 2 ∈ F k \mathbf{q}_1, \mathbf{q}_2 \in \mathbf{F}^k q1,q2∈Fk such that g ( x ) = ( ( q 1 ⊗ q 2 ) , B ) g(x) = ((\mathbf{q}_1 \otimes \mathbf{q}_2), \mathbf{B}) g(x)=((q1⊗q2),B).
- The evaluation phase is identical to the testing phase except that r r r is replaced with q 1 \mathbf{q}_1 q1 (and fresh randomness is used to choose a set Q ′ Q' Q′ of columns for use in consistency testing).
- If all consistency tests pass, then V outputs ( u ′ ′ , q 2 ) (u'', \mathbf{q}_2) (u′′,q2) as g ( x ) g(x) g(x).
References：
[1]https://drops.dagstuhl.de/storage/00lipics/lipics-vol107-icalp2018/LIPIcs.ICALP.2018.14/LIPIcs.ICALP.2018.14.pdf
[2] Kate, A., Zaverucha, G.M., Goldberg, I.. Constant-Size Commitments to Polynomials and Their Applications. International Conference on the Theory and Application of Cryptology and Information Security, 2010.
[3] https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/i ndex.html
[4] Ulrich Haböck. A summary on the fri low degree test. Cryptology ePrint Archive, Paper 2022/1216, 2022.
[5] https://eprint.iacr.org/2021/1043.pdf?ref=hackernoon.com
[6] J. Bootle, A. Chiesa, and J. Groth. Linear-time arguments with sub-linear verification from tensor codes. In TCC, 2020.
[7] S. Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In CRYPTO, 2020.
[8] T. Xie, Y. Zhang, and D. Song, “Orion: Zero knowledge proof with linear prover time,” Cryptology ePrint Archive, Paper 2022/1010, 2022, https://eprint.iacr.org/2022/1010.
[9] B. Diamond, J. Posen,“Succinct Arguments over Towers of Binary Fields,” Cryptology ePrint Archive, Paper 2023/1784, 2023, https://eprint.iacr.org/2023/1784.pdf
[10] https://github.com/IrreducibleOSS/binius
[11] S. Ames, C. Hazay, Y. Ishai, and M. Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In CCS, 2017
这篇关于Plonky3和Binius中的Brakedown多项式承诺协议解析及优化（2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
