品牌网站建设哪里好,市场营销具体是做什么的,网站建设 麓谷,WordPress搬家文章4041. 引言
主要参考Ingonyama团队2023年4月文章《A Brief History of Lookup Arguments》。
近年来zk-SNARKs的研究热点有#xff1a;
让ZKP proof更succinct降低Prover time和Verifier time
但#xff0c;大多数SNARKs仍受限于#xff0c;易于转换为多项式的算术运算。通…1. 引言
主要参考Ingonyama团队2023年4月文章《A Brief History of Lookup Arguments》。
近年来zk-SNARKs的研究热点有
让ZKP proof更succinct降低Prover time和Verifier time
但大多数SNARKs仍受限于易于转换为多项式的算术运算。通常将“易于转换为多项式的算术运算” 称为 “SNARK-friendly”的而其它“SNARK-unfriendly”运算则仍未解决。
直到2018年Jonathan Bootle等人在《BCG18 Nearly linear-time zero-knowledge proofs for correct program execution》论文中提出了lookup协议来处理某些SNARK-unfriendly运算。lookup协议用于证明如下statement
已知table T { t i } i 0 , ⋯ , N − 1 T\{t_i\}_{i0,\cdots,N-1} T{ti}i0,⋯,N−1具有不同值“rows”一组lookups F { f j } j 0 , ⋯ , m − 1 F\{f_j\}_{j0,\cdots,m-1} F{fj}j0,⋯,m−1可能有重复值证明所有lookups均包含在table内即 F ⊆ T F\subseteq T F⊆T。
table T T T通常是public的而lookups通常为private witness。 可
将table看成是某特定变量的所有合法值而lookups为某特定程序执行给出的该变量值。则以上statement即表示该变量维护了整个执行过程中的合法状态。除非明确指出可假定 m N mN mN且大多数情况下 m ≪ N m\ll N m≪N。
本文关注各种不同的lookup argument及其变种演变思路重点关注
plookupAriel Gabizon等人2020年论文 plookup: A simplified polynomial protocol for lookup tablescqLiam Eagen等人2022年论文 cq: Cached quotients for fast lookups
2. lookup argument用途
2.1 范围检查
当检查数字 x x x在 { 0 , 1 , ⋯ , N − 1 } \{0,1,\cdots,N-1\} {0,1,⋯,N−1}范围内其中 N 2 n N2^n N2n。 对应的算术约束方式为
定义 n n n个数字 b 0 , ⋯ , b n − 1 b_0,\cdots,b_{n-1} b0,⋯,bn−1检查对于每个 i i i有 b i ∈ { 0 , 1 } b_i\in\{0,1\} bi∈{0,1}且 ∑ i b i 2 i x \sum_{i}b_i2^ix ∑ibi2ix。一共需要 n 1 n1 n1个约束。若需要做 m m m个数字的范围检查则需要 O ( m n ) O ( m log N ) O(mn)O(m\log N) O(mn)O(mlogN)个约束。
而若借助lookup argument则仅需要一个lookup约束就可检查 m m m个数字在 { 0 , 1 , ⋯ , N − 1 } \{0,1,\cdots,N-1\} {0,1,⋯,N−1}范围内。后面将介绍这样一个lookup约束的开销。且当 N N N不是为power of 2时上面的算术约束方式将是笨重的而lookup argument无需关注 N N N是否为power of 2。
2.2 有限域函数
lookup argument可用于实现任意有限域函数通过简单将该函数的完整输入输出值来定义table。可用于实现具有任意多个变量的函数。
如哈希计算中广泛使用的 k k k-bit XOR函数。遵循2.1节的逻辑使用算术约束方式将需要 6 k 6k 6k个约束。而借助lookup argument可直接借助table T T T来实现其中table T T T的rows为 t i ( A , B , C ) t_i(A,B,C) ti(A,B,C) 其中
对于每个 i i i A , B ∈ { 0 , 1 , ⋯ , 2 k − 1 } A,B\in\{0,1,\cdots,2^k-1\} A,B∈{0,1,⋯,2k−1}为2个 k k k-bit数字的不同组合且 C A ⊕ B CA\oplus B CA⊕B。整个table T T T具有 2 2 k 2^{2k} 22k行且每行需存储 3 k 3k 3k bits。 当 k 32 k32 k32时很多哈希函数的通用取值则这样的table是完全不实用的。当 k 16 k16 k16时这样的table需要24GB存储空间对大多数应用场景来说也是不实用的。
2.3 更好的XOR
Halo2中的16-bit table chip for SHA-256通过利用zero-interleaving借助lookup argument实现了更好的bit-wise XOR函数。 zero-interleaving是指以二进制来表示数字 A ∑ l 0 k − 1 a l 2 l A\sum_{l0}^{k-1}a_l2^l A∑l0k−1al2l 然后在任意2个原始bits之间添加一个‘0’ bit从而有 A ′ ∑ l 0 k − 1 a l 4 l A\sum_{l0}^{k-1}a_l4^l A′∑l0k−1al4l 对XOR的2个输入 A , B A,B A,B均做zero-interleaving之后有 A ′ , B ′ A,B A′,B′。计算 C ′ ′ A ′ B ′ CAB C′′A′B′则 C ′ ′ C C′′的偶数位置的bit即为 C A ⊕ B CA\oplus B CA⊕B。为根据 C ′ ′ C C′′获得 C C C需将 C ′ ′ C C′′分解为奇数bit和偶数bit C ′ ′ ∑ l 0 k − 1 c l e v e n 4 l 2 ∑ l 0 k − 1 c l o d d 4 l C\sum_{l0}^{k-1}c_l^{even}4^l2\sum_{l0}^{k-1}c_{l}^{odd}4^l C′′∑l0k−1cleven4l2∑l0k−1clodd4l
从而
有 c l e v e n c_l^{even} cleven为 C A ⊕ B CA\oplus B CA⊕B的二进制表示同时有副产品 c l o d d c_l^{odd} clodd为 D A ∧ B DA\land B DA∧B的二进制表示。 ∧ \land ∧表示bit-wise AND。借助4次zero-interleaving table A , B , C , D → A ′ , B ′ , C ′ , D ′ A,B,C,D\rightarrow A,B,C,D A,B,C,D→A′,B′,C′,D′以及一个算术约束 A ′ B ′ C ′ ′ C ′ 2 D ′ ABCC2D A′B′C′′C′2D′ 可同时证明 A , B A,B A,B的bit-wise XOR和bit-wise AND结果。
当 k 32 k32 k32时以上实现仍是不切实际的大单个table需要48GB存储空间。 但对于 k 16 k16 k16的情况以上实现对应的lookup table仅需要384kB。 可通过slicing以SNARK-friendly的方式来降低bits数即引入arithmetic gate——其以2个16-bit数字 x 0 , x 1 x_0,x_1 x0,x1为输入然后最终获得32-bit的数字 x x 0 ⋅ 1 x 1 ⋅ 2 16 xx_0\cdot 1x_1\cdot 2^{16} xx0⋅1x1⋅216。
2.4 有限状态机
lookup table可用于实现有限状态机。状态机内包含一组状态以及依赖于输入的状态变化。实现状态机的lookup table内包含 (current state, input, next state) 的所有合法组合。状态机的execution trace通常表示为 ( s t a t e ( j ) , i n p u t ( j ) , n e x t _ s t a t e ( j ) ) (state(j),input(j),next\_state(j)) (state(j),input(j),next_state(j))
可使用lookup argument来证明该状态机的合法执行同时证明wiring约束 n e x t _ s t a t e ( j ) s t a t e ( j 1 ) next\_state(j)state(j1) next_state(j)state(j1)
该wiring 约束是SNARK-friendly的。
3. Plookup
Plookup为早期的lookup协议之一其为首个lookup协议的简化版。 Plookup的基于的思想为
已知向量 t ∈ F N , f ∈ F m , s ∈ F N m t\in\mathbb{F}^N,f\in\mathbb{F}^m,s\in\mathbb{F}^{Nm} t∈FN,f∈Fm,s∈FNm和双变量多项式 F ( β , γ ) ( 1 β ) m ∏ j 1 m ( γ f j ) ∏ i 1 N − 1 ( γ ( 1 β ) t i β t i 1 ) F(\beta,\gamma)(1\beta)^m\prod_{j1}^{m}(\gammaf_j)\prod_{i1}^{N-1}(\gamma(1\beta)t_i\beta t_{i1}) F(β,γ)(1β)m∏j1m(γfj)∏i1N−1(γ(1β)tiβti1) G ( β , γ ) ∏ k 1 m N − 1 ( γ ( 1 β ) s k β s k 1 ) G(\beta,\gamma)\prod_{k1}^{mN-1}(\gamma(1\beta)s_k\beta s_{k1}) G(β,γ)∏k1mN−1(γ(1β)skβsk1)则有 F ≡ G ⇔ { { f j } ⊆ { t i } , 且 s ( f , t ) sorted by t F\equiv G \Leftrightarrow \left\{\begin{matrix} \{f_j\}\subseteq \{t_i\}, 且 \\ s(f,t) \text{ sorted by } t \\ \end{matrix}\right. F≡G⇔{{fj}⊆{ti},s(f,t) sorted by t且 其中 s ( f , t ) sorted by t s(f,t) \text{ sorted by } t s(f,t) sorted by t表示 s s s中值的出现顺序与 t t t中的出现顺序一样因为有 { f j } ⊆ { t i } \{f_j\}\subseteq \{t_i\} {fj}⊆{ti}。
若有 s ( f , t ) sorted by t s(f,t) \text{ sorted by } t s(f,t) sorted by t且 { f j } ⊆ { t i } \{f_j\}\subseteq \{t_i\} {fj}⊆{ti}则对于每个 i 1 , ⋯ , N − 1 i1,\cdots,N-1 i1,⋯,N−1都有不同的 k ∈ { 1 , ⋯ , m N − 1 } k\in\{1,\cdots,mN-1\} k∈{1,⋯,mN−1}使得 ( γ ( 1 β ) t i β t i 1 ) ( γ ( 1 β ) s k β s k 1 ) (3.4) (\gamma (1\beta)t_i\beta t_{i1})(\gamma(1\beta)s_k\beta s_{k1}) \tag{3.4} (γ(1β)tiβti1)(γ(1β)skβsk1)(3.4) 而对于其它 s k s k 1 s_ks_{k1} sksk1的索引值 k k k存在 j ∈ { 1 , ⋯ , m } j\in\{1,\cdots,m\} j∈{1,⋯,m}使得 f j s k f_js_k fjsk且 ( 1 β ) ( γ f j ) ( γ ( 1 β ) s k β s k 1 ) (3.5) (1\beta)(\gammaf_j)(\gamma(1\beta)s_k\beta s_{k1}) \tag{3.5} (1β)(γfj)(γ(1β)skβsk1)(3.5)
将 β \beta β看成是系数则可将 F , G F,G F,G看成是 F [ γ ] \mathbb{F}[\gamma] F[γ]多项式从而具有唯一分解因子。通过识别以上3.4和3.5方程式中的因子可发现其因子为关于变量 β \beta β的多项式。
3.1 Plookup定义
Plookup使用如下定义
1取 m N − 1 mN-1 mN−1若不满足 N m 1 Nm1 Nm1则需重复最后一个元素来填充相应的table直到其满足 N m 1 Nm1 Nm1。2 H { g , ⋯ , g N 1 } H\{g,\cdots,g^N1\} H{g,⋯,gN1}为 F \mathbb{F} F中order为 N N N的multiplicative subgroup。3对于向量 p F N p\mathbb{F}^N pFN定义多项式 p ( x ) ∈ F [ X ] N p(x)\in\mathbb{F}[X]_{N} p(x)∈F[X]N使得向量值为该多项式的evaluation值即满足 p i p ( g i ) p_ip(g^i) pip(gi)。4令 L i ( x ) ∈ F [ X ] N L_i(x)\in\mathbb{F}[X]_{N} Li(x)∈F[X]N为基于 H H H的第 i i i个Lagrange都像是满足 L i ( g j ) δ i j L_i(g^j)\delta_{ij} Li(gj)δij为Kronecker delta。5 s ∈ F 2 N − 1 s\in \mathbb{F}^{2N-1} s∈F2N−1为 ( f , t ) (f,t) (f,t) sorted by t t t。
3.2 Plookup协议
最终的Plookup协议为
1Prover计算并对2个多项式 h 1 , h 2 ∈ F [ x ] N h_1,h_2\in\mathbb{F}[x]_{N} h1,h2∈F[x]N进行承诺使得对于每个 i 1 , ⋯ , N i1,\cdots,N i1,⋯,N有 h 1 ( g i ) s i h_1(g^i)s_i h1(gi)si h 2 ( g i ) s N i − 1 h_2(g^i)s_{Ni-1} h2(gi)sNi−12Verifier给Prover发送随机值 β , γ \beta,\gamma β,γ。3Prover计算并对多项式 Z ∈ F [ x ] N Z\in \mathbb{F}[x]_{N} Z∈F[x]N多项式进行承诺 Z Z Z聚合了 F ( β , γ ) / G ( β , γ ) F(\beta,\gamma)/G(\beta,\gamma) F(β,γ)/G(β,γ)有 Z ( g ) 1 Z(g)1 Z(g)1 对于 i 2 , ⋯ , N − 1 i2,\cdots,N-1 i2,⋯,N−1有 Z ( g i ) ( 1 β ) i − 1 ∏ l 1 i − 1 ( γ f l ) ( γ ( 1 β ) t l β t l 1 ) ∏ l 1 i − 1 ( γ ( 1 β ) s l β s l 1 ) ( γ ( 1 β ) s N l β s N l 1 ) (3.9) Z(g^i)\frac{(1\beta)^{i-1}\prod_{l1}^{i-1}(\gammaf_l)(\gamma(1\beta)t_l\beta t_{l1})}{\prod_{l1}^{i-1}(\gamma (1\beta)s_l\beta s_{l1})(\gamma(1\beta)s_{Nl}\beta s_{Nl1})}\tag{3.9} Z(gi)∏l1i−1(γ(1β)slβsl1)(γ(1β)sNlβsNl1)(1β)i−1∏l1i−1(γfl)(γ(1β)tlβtl1)(3.9) Z ( g N ) 1 Z(g^N)1 Z(gN)14Verifier对所有 x ∈ H x\in H x∈H检查如下identities L 1 ( x ) ( Z ( x ) − 1 ) 0 (3.11) L_1(x)(Z(x)-1)0\tag{3.11} L1(x)(Z(x)−1)0(3.11) L N ( x ) ( Z ( x ) − 1 ) 0 (3.12) L_N(x)(Z(x)-1)0\tag{3.12} LN(x)(Z(x)−1)0(3.12) L N ( x ) ( h 1 ( x ) − h 2 ( g x ) ) 0 (3.13) L_N(x)(h_1(x)-h_2(gx))0\tag{3.13} LN(x)(h1(x)−h2(gx))0(3.13) ( x − g N ) Z ( x ) ( 1 β ) ( γ f ( x ) ) ( γ ( 1 β ) t ( x ) β t ( g x ) ) ( x − g N ) Z ( g x ) ( γ ( 1 β ) h 1 ( x ) β h 1 ( g x ) ) ( γ ( 1 β ) h 2 ( x ) β h 2 ( g x ) ) (3.14) (x-g^N)Z(x)(1\beta)(\gammaf(x))(\gamma(1\beta)t(x)\beta t(gx))(x-g^N)Z(gx)(\gamma(1\beta)h_1(x)\beta h_1(gx))(\gamma(1\beta)h_2(x)\beta h_2(gx))\tag{3.14} (x−gN)Z(x)(1β)(γf(x))(γ(1β)t(x)βt(gx))(x−gN)Z(gx)(γ(1β)h1(x)βh1(gx))(γ(1β)h2(x)βh2(gx))(3.14)
注意所构建的 Z ( x ) Z(x) Z(x)多项式在3.9方程式的基础上分子分母乘以了相同的乘数项。即意味着添加了第 N N N项后 F , G F,G F,G的等价性暗含了所有项可消减最终获得1。3.11和3.12方程式检查了 Z ( g ) Z ( g N ) 1 Z(g)Z(g^N)1 Z(g)Z(gN)1而3.14方程式检查了每个evaluation值确实添加了正确的乘数项——其两边增加的 ( x − g N ) (x-g^N) (x−gN)乘数项可确保不包含 Z ( g N ) Z(g^N) Z(gN)和 Z ( g N 1 ) Z ( g ) Z(g^{N1})Z(g) Z(gN1)Z(g)之间的关系。
3.3 Plookup开销
Plookup协议不依赖于任何特殊的承诺方案。通常
其Prover runtime为 O ( N log N ) O(N\log N) O(NlogN)个域运算以根据evaluations值构建多项式和 O ( N ) O(N) O(N)个group运算以构建多项式 Z Z Z。当使用KZG承诺方案时其proof size为5个group元素和9个域元素而Verifier runtime为2个pairing函数。
3.4 Plookup泛化与优化
Plookup协议可泛化为多个witness多项式 f 1 , ⋯ , f w ∈ F [ x ] m f_1,\cdots,f_w\in\mathbb{F}[x]_{m} f1,⋯,fw∈F[x]m和多个tables t 1 , ⋯ , t w ∈ F [ x ] N t_1,\cdots,t_w\in\mathbb{F}[x]_{N} t1,⋯,tw∈F[x]N。Verifier选择随机值 α \alpha α然后这些多项式可聚合为 t ∑ l 1 w α l t l t\sum_{l1}^{w}\alpha^lt_l t∑l1wαltl f ∑ l 1 w α l f l f\sum_{l1}^{w}\alpha^lf_l f∑l1wαlfl
然后像之前那样处理 f , t f,t f,t。
若table为一组连续的整数即有 t l 1 t l t_{l1}t_l tl1tl则可将Plookup协议中的3.9方式简化为 Z ( g i ) ∏ l 1 i − 1 ( γ f l ) ( γ t l ) ∏ l 1 i − 1 ( γ s l ) ( γ s N l ) Z(g^i)\frac{\prod_{l1}^{i-1}(\gammaf_l)(\gammat_l)}{\prod_{l1}^{i-1}(\gammas_l)(\gammas_{Nl})} Z(gi)∏l1i−1(γsl)(γsNl)∏l1i−1(γfl)(γtl)
对应的Verifier checks也需做相应调整。
Plookup协议另一个泛化是plonkup协议见Luke Pearson等人2022年论文 Plonkup: Reconciling plonk with plookupplonkup协议集成了plonk和plookup支持引入通用plonk gates的高效lookup table。
4. cq协议
plookup协议的主要问题在于
对于 m ≪ N m\ll N m≪N的常见场景plookup协议开销大。
自plookup协议问世以来迭代了多个lookup协议每个新的lookup协议相比于之前协议对 N N N的依赖性都有所减弱这些新lookup协议背后的核心思想为
将大部分table计算移到预计算中。
截止2023年4月最好的lookup协议为cq见Liam Eagen等人2022年论文 cq: Cached quotients for fast lookups。
4.1 Logarithmic Derivative对数导数
cq协议基于如下 Logarithmic Derivative trick
2个多项式 p ( x ) ∏ a ∈ A ( x a ) p(x)\prod_{a\in A}(xa) p(x)∏a∈A(xa)和 q ( x ) ∏ b ∈ B ( x b ) q(x)\prod_{b\in B}(xb) q(x)∏b∈B(xb)相等当且仅当如下有理函数相等 p ′ ( x ) p ( x ) ∑ a ∈ A 1 x a \frac{p(x)}{p(x)}\sum_{a\in A}\frac{1}{xa} p(x)p′(x)∑a∈Axa1 q ′ ( x ) q ( x ) ∑ b ∈ B 1 x b \frac{q(x)}{q(x)}\sum_{b\in B}\frac{1}{xb} q(x)q′(x)∑b∈Bxb1
即由 p ( x ) q ( x ) p(x)q(x) p(x)q(x)推导出有 p ′ ( x ) / p ( x ) q ′ ( x ) / q ( x ) p(x)/p(x)q(x)/q(x) p′(x)/p(x)q′(x)/q(x)是trivial的而反之由 p ′ ( x ) / p ( x ) q ′ ( x ) / q ( x ) p(x)/p(x)q(x)/q(x) p′(x)/p(x)q′(x)/q(x)有 ( p ( x ) q ( x ) ) ′ p ′ ( x ) q ( x ) − q ′ ( x ) p ( x ) p 2 ( x ) 0 (\frac{p(x)}{q(x)})\frac{p(x)q(x)-q(x)p(x)}{p^2(x)}0 (q(x)p(x))′p2(x)p′(x)q(x)−q′(x)p(x)0
即意味着有 p ( x ) / q ( x ) c p(x)/q(x)c p(x)/q(x)c其中 c c c为常数值。但是由于 p ( x ) , q ( x ) p(x),q(x) p(x),q(x)的leading系数均为1则有 c 1 c1 c1且 p ( x ) q ( x ) p(x)q(x) p(x)q(x)。从而lookups f f f包含在table t t t中当且仅当 ∑ i 1 N m i x t i ∑ j 1 m 1 x f j (4.4) \sum_{i1}^{N}\frac{m_i}{xt_i}\sum_{j1}^{m}\frac{1}{xf_j}\tag{4.4} i1∑Nxtimij1∑mxfj1(4.4) 其中 m i m_i mi为lookup f j f_j fj中 t i t_i ti值出现的次数。注意每个 t i t_i ti是唯一的而 f j f_j fj值支持重复且对于许多 t i t_i ti可以有 m i m_i mi值为0。
cq协议的核心思想为测试4.4方程式在某随机点 x β x\beta xβ的有理函数identity。
4.2 将cq协议identity调整为Sumcheck
可定义多项式 A ( x ) , B ( x ) A(x),B(x) A(x),B(x)使得其evaluations值为 A i m i β t i , i 1 , ⋯ , N (4.5) A_i\frac{m_i}{\betat_i},i1,\cdots,N \tag{4.5} Aiβtimi,i1,⋯,N(4.5) B j 1 β f j , j 1 , ⋯ , m B_j\frac{1}{\betaf_j},j1,\cdots,m Bjβfj1,j1,⋯,m
来做4.4方程式的cq协议 identity检查。
此处有 A i A ( g i ) A_iA(g^i) AiA(gi)其中 g g g为order为 N N N的multiplicative subgroup V ⊂ F V\subset \mathbb{F} V⊂F的generator。 B j B ( w j ) B_jB(w^j) BjB(wj)其中 w w w为order为 m m m的multiplicative subgroup H ⊂ F H\subset \mathbb{F} H⊂F的generator。
基于随机点 β \beta β为满足方程式4.4中的关系 A i , B j A_i,B_j Ai,Bj需满足 ∑ i A i ∑ j B j \sum_i A_i\sum_j B_j ∑iAi∑jBj且基于multiplicative groups的这些多项式evaluations值遵循 ∑ i 1 N A i N ⋅ A ( 0 ) \sum_{i1}^{N}A_iN\cdot A(0) ∑i1NAiN⋅A(0) ∑ i j m B j m ⋅ B ( 0 ) \sum_{ij}^{m}B_jm\cdot B(0) ∑ijmBjm⋅B(0)
然后Prover必须证明 N ⋅ A ( 0 ) m ⋅ B ( 0 ) (4.9) N\cdot A(0)m\cdot B(0)\tag{4.9} N⋅A(0)m⋅B(0)(4.9)
这对应的单变量sumcheck问题。
4.3 cq协议的quotient多项式
多项式 p ( x ) A ( x ) ( T ( x ) β ) − m ( x ) p(x)A(x)(T(x)\beta)-m(x) p(x)A(x)(T(x)β)−m(x) q ( x ) B ( x ) ( F ( x ) β ) − 1 q(x)B(x)(F(x)\beta)-1 q(x)B(x)(F(x)β)−1 其中 T ( x ) , m ( x ) , F ( x ) T(x), m(x), F(x) T(x),m(x),F(x)多项式的evaluation值分别为 t i , m i , f j t_i,m_i,f_j ti,mi,fj。对于 V V V p ( x ) p(x) p(x)的evaluation值必须为0。对于 H H H q ( x ) q(x) q(x)的evaluation值必须为0。
从而可定义quotient多项式 Q A ( x ) , Q B ( x ) Q_A(x),Q_B(x) QA(x),QB(x)为 Q A ( x ) A ( x ) ( T ( x ) β ) − m ( x ) Z V ( x ) (4.12) Q_A(x)\frac{A(x)(T(x)\beta)-m(x)}{Z_V(x)}\tag{4.12} QA(x)ZV(x)A(x)(T(x)β)−m(x)(4.12) Q B ( x ) B ( x ) ( F ( x ) β ) − 1 Z H ( x ) (4.13) Q_B(x)\frac{B(x)(F(x)\beta)-1}{Z_H(x)}\tag{4.13} QB(x)ZH(x)B(x)(F(x)β)−1(4.13) 其中 Z V ( x ) , Z H ( x ) Z_V(x),Z_H(x) ZV(x),ZH(x)分别为 V , H V,H V,H的vanishing多项式。
Prover需证明2件事
1其知道多项式 A , B , Q A , Q B , F , m A,B,Q_A,Q_B,F,m A,B,QA,QB,F,m。2这些多项式满足上面4.9、4.12、4.13方程式关系。
若使用KZG承诺方案则其只需要使用pairing来检查这些方程式关系。不过接下来将进一步将这些statements切分。
4.4 cq协议中证明其知道多项式 A A A及其sum
当使用KZG承诺值 [ ϕ ( x ) ] 1 [\phi(x)]_1 [ϕ(x)]1来证明其知道多项式 ϕ ( x ) \phi(x) ϕ(x)时Prover会对其在 z z z点进行evaluate以定义新的多项式 P ϕ ϕ ( x ) − ϕ ( z ) x − z P_{\phi}\frac{\phi(x)-\phi(z)}{x-z} Pϕx−zϕ(x)−ϕ(z) 并发送承诺值 [ P ϕ ] 1 [P_{\phi}]_1 [Pϕ]1。Verifier会检查pairing方程式 e ( [ ϕ ( x ) ] 1 − [ ϕ ( z ) ] 1 , [ 1 ] 2 ) e ( [ P ϕ ] 1 , [ x − z ] 2 ) e([\phi(x)]_1-[\phi(z)]_1,[1]_2)e([P_{\phi}]_1,[x-z]_2) e([ϕ(x)]1−[ϕ(z)]1,[1]2)e([Pϕ]1,[x−z]2)
将其重写为 e ( [ ϕ ( x ) ] 1 − [ ϕ ( z ) ] 1 z ⋅ [ P ϕ ] 1 , [ 1 ] 2 ) e ( [ P ϕ ] 1 , [ x ] 2 ) e([\phi(x)]_1-[\phi(z)]_1z\cdot [P_{\phi}]_1,[1]_2)e([P_{\phi}]_1,[x]_2) e([ϕ(x)]1−[ϕ(z)]1z⋅[Pϕ]1,[1]2)e([Pϕ]1,[x]2)
使得该pairing函数的第二个参数总为 [ 1 ] 2 [1]_2 [1]2或 [ x ] 2 [x]_2 [x]2。
为证明其知道多项式 A A A对 A A A在 x 0 x0 x0点进行evaluate有 P A ( x ) A ( x ) − A ( 0 ) x P_A(x)\frac{A(x)-A(0)}{x} PA(x)xA(x)−A(0) 并承诺 [ P A ] 1 [P_A]_1 [PA]1然后使用 e ( [ A ( x ) ] 1 − [ A ( 0 ) ] 1 , [ 1 ] 2 ) e ( [ P A ( x ) ] 1 , [ x ] 2 ) e([A(x)]_1-[A(0)]_1,[1]_2)e([P_A(x)]_1,[x]_2) e([A(x)]1−[A(0)]1,[1]2)e([PA(x)]1,[x]2) 来证明。
4.5 cq协议中 B B B多项式的low degree testing
为证明知道多项式 B B B
首先证明多项式 B B B的degree确实 m m m。
注意无需证明 A ( x ) A(x) A(x)的degree因其degree为SRS所支持的最大degree。
在KZG承诺方案中为证明多项式 B B B的degree确实 m m m可定义 P B ( x ) B ( x ) − B ( 0 ) x P_B(x)\frac{B(x)-B(0)}{x} PB(x)xB(x)−B(0) 然后承诺 [ P B ( x ) ⋅ x N − m 1 ] 1 [P_B(x)\cdot x^{N-m1}]_1 [PB(x)⋅xN−m1]1最后测试 e ( [ P B ( x ) ] 1 , [ x N − m 1 ] 2 ) e ( [ P B ( x ) ⋅ x N − m 1 ] 1 , [ 1 ] 2 ) e([P_B(x)]_1,[x^{N-m1}]_2)e([P_B(x)\cdot x^{N-m1}]_1,[1]_2) e([PB(x)]1,[xN−m1]2)e([PB(x)⋅xN−m1]1,[1]2)
注意若 B ( x ) B(x) B(x)中有degree ≥ m \geq m ≥m的项则将包括在承诺值 [ P B ( x ) ⋅ x N − m 1 ] 1 [P_B(x)\cdot x^{N-m1}]_1 [PB(x)⋅xN−m1]1中而SRS不支持对degree ≥ N \geq N ≥N的项进行承诺。
4.6 cq协议中使用Cached Quotients来证明4.12方程式关系
可通过如下testing e ( [ A ( x ) ] 1 , [ T ( x ) ] 2 ) e ( [ Q A ( x ) ] 1 , [ Z V ( x ) ] 2 ) ⋅ e ( [ m ( x ) ] 1 − β [ A ( x ) ] 1 , [ 1 ] 2 ) e([A(x)]_1,[T(x)]_2)e([Q_A(x)]_1,[Z_V(x)]_2)\cdot e([m(x)]_1-\beta [A(x)]_1,[1]_2) e([A(x)]1,[T(x)]2)e([QA(x)]1,[ZV(x)]2)⋅e([m(x)]1−β[A(x)]1,[1]2)
来检查4.12方程式关系。
其中 [ T ] 2 , [ Z V ] 2 , [ 1 ] 2 , [ x ] 2 [T]_2,[Z_V]_2,[1]_2,[x]_2 [T]2,[ZV]2,[1]2,[x]2均独立于lookups可预计算。Prover需计算 [ A ( x ) ] 1 , [ Q A ( x ) ] 1 , [ m ( x ) ] 1 , A ( 0 ) , [ A ( x ) − A ( 0 ) x ] 1 [A(x)]_1,[Q_A(x)]_1,[m(x)]_1,A(0),[\frac{A(x)-A(0)}{x}]_1 [A(x)]1,[QA(x)]1,[m(x)]1,A(0),[xA(x)−A(0)]1。 这些计算复杂度为 O ( m ) O(m) O(m)因其仅需要计算lookups。若 t i t_i ti不存在于lookups中则有 m i 0 , A i 0 m_i0,A_i0 mi0,Ai0。只有 [ Q A ( x ) ] 1 [Q_A(x)]_1 [QA(x)]1的计算为 O ( N ) O(N) O(N)。对应的解决方案为 预计算cached quotients Q i ( x ) L i ( x ) ( T ( x ) − t i ) Z V ( x ) T ( x ) − t i k i ( x − g i ) (4.22) Q_i(x)\frac{L_i(x)(T(x)-t_i)}{Z_V(x)}\frac{T(x)-t_i}{k^i(x-g^i)}\tag{4.22} Qi(x)ZV(x)Li(x)(T(x)−ti)ki(x−gi)T(x)−ti(4.22) 其中 L i ( x ) L_i(x) Li(x)为Lagrange多项式 L i ( x ) Z V ( x ) k i ( x − g i ) L_i(x)\frac{Z_V(x)}{k^i(x-g^i)} Li(x)ki(x−gi)ZV(x) k i Z V ′ ( g i ) ( x N − 1 ) ′ ∣ x g i N ⋅ g i N − 1 N g i k^iZ_V(g^i)(x^N-1)|_{xg^i}N\cdot g_i^{N-1}\frac{N}{g^i} kiZV′(gi)(xN−1)′∣xgiN⋅giN−1giN使用NTT Q i ( x ) Q_i(x) Qi(x)的计算量为 O ( N log N ) O(N\log N) O(NlogN)。使用 Q i ( x ) Q_i(x) Qi(x) [ Q A ] 1 [Q_A]_1 [QA]1的计算量为 O ( m ) O(m) O(m)有 [ Q A ( x ) ] 1 ∑ A i ≠ 0 A i ⋅ [ Q i ( x ) ] 1 [Q_A(x)]_1\sum_{A_i\neq 0}A_i\cdot [Q_i(x)]_1 [QA(x)]1∑Ai0Ai⋅[Qi(x)]1 其中 A i A_i Ai为4.5方程式中多项式 A ( x ) A(x) A(x)的evaluation值。
4.7 cq协议中证明4.94.13方程式关系
引入另一随机值 x γ x\gamma xγ
首先对多项式 P F ( x ) F ( x ) − F ( γ ) x − γ P_F(x)\frac{F(x)-F(\gamma)}{x-\gamma} PF(x)x−γF(x)−F(γ) P B , γ ( x ) P B ( x ) − P B ( γ ) x − γ P_{B,\gamma}(x)\frac{P_B(x)-P_B(\gamma)}{x-\gamma} PB,γ(x)x−γPB(x)−PB(γ) 承诺来证明知道 F ( γ ) , P B ( γ ) F(\gamma),P_B(\gamma) F(γ),PB(γ)。 可通过验证 e ( [ F ( x ) ] 1 − [ F ( γ ) ] 1 γ [ P F ( x ) ] 1 , [ 1 ] 2 ) e ( [ P F ( x ) ] 1 , [ x ] 2 ) (4.28) e([F(x)]_1-[F(\gamma)]_1\gamma [P_F(x)]_1,[1]_2)e([P_F(x)]_1,[x]_2)\tag{4.28} e([F(x)]1−[F(γ)]1γ[PF(x)]1,[1]2)e([PF(x)]1,[x]2)(4.28) e ( [ P B ( x ) ] 1 − [ P B ( γ ) ] 1 γ [ P B , γ ( x ) ] 1 , [ 1 ] 2 ) e ( [ P B , γ ( x ) ] 1 , [ x ] 2 ) (4.29) e([P_B(x)]_1-[P_B(\gamma)]_1\gamma [P_{B,\gamma}(x)]_1,[1]_2)e([P_{B,\gamma}(x)]_1,[x]_2)\tag{4.29} e([PB(x)]1−[PB(γ)]1γ[PB,γ(x)]1,[1]2)e([PB,γ(x)]1,[x]2)(4.29) 来证明 B ( x ) , F ( x ) B(x),F(x) B(x),F(x)确实evaluate到 B ( γ ) , F ( γ ) B(\gamma),F(\gamma) B(γ),F(γ)从而可使用这些evaluations值来证明所需的关系。定义 Q b , γ ( B ( γ ) − B ( 0 ) A ( 0 ) ⋅ N / m ) ( F ( γ ) β ) − 1 Z H ( γ ) (4.30) Q_{b,\gamma}\frac{(B(\gamma)-B(0)A(0)\cdot N/m)(F(\gamma)\beta)-1}{Z_H(\gamma)}\tag{4.30} Qb,γZH(γ)(B(γ)−B(0)A(0)⋅N/m)(F(γ)β)−1(4.30) P Q B ( x ) Q B ( x ) − Q b , γ x − γ P_{Q_B}(x)\frac{Q_B(x)-Q_{b,\gamma}}{x-\gamma} PQB(x)x−γQB(x)−Qb,γ 然后发送承诺值 [ Q b , γ ] 1 , [ P Q B ( x ) ] 1 [Q_{b,\gamma}]_1,[P_{Q_B}(x)]_1 [Qb,γ]1,[PQB(x)]1可通过如下pairing等式来验证 e ( [ Q B ( x ) ] 1 − [ Q b , γ ] 1 γ [ P Q B ( x ) ] 1 , [ 1 ] 2 ) e ( [ P Q B ( x ) ] 1 , [ x ] 2 ) (4.32) e([Q_B(x)]_1-[Q_{b,\gamma}]_1\gamma [P_{Q_B}(x)]_1,[1]_2)e([P_{Q_B}(x)]_1,[x]_2)\tag{4.32} e([QB(x)]1−[Qb,γ]1γ[PQB(x)]1,[1]2)e([PQB(x)]1,[x]2)(4.32) 注意该构建可同时证明如下statements Q B ( γ ) ( B ( γ ) ) ( F ( γ ) β ) − 1 Z H ( x ) Q_B(\gamma)\frac{(B(\gamma))(F(\gamma)\beta)-1}{Z_H(x)} QB(γ)ZH(x)(B(γ))(F(γ)β)−1 B ( 0 ) ⋅ m A ( 0 ) ⋅ N B(0)\cdot mA(0)\cdot N B(0)⋅mA(0)⋅N 这样整个证明结束。
4.8 cq协议的proof batching
最后的3个proofs结构相似cq协议可将其batch为单个协议——通过引入新的随机变量 η \eta η并定义 c ( x ) P B ( x ) η F ( x ) η 2 Q B ( x ) c(x)P_B(x)\eta F(x)\eta^2 Q_B(x) c(x)PB(x)ηF(x)η2QB(x) v P B ( γ ) η F ( γ ) η 2 Q b , γ vP_B(\gamma)\eta F(\gamma)\eta^2 Q_{b,\gamma} vPB(γ)ηF(γ)η2Qb,γ P γ ( x ) P B , γ ( x ) η P F ( x ) η 2 P Q B ( x ) P_{\gamma}(x)P_{B,\gamma}(x)\eta P_F(x)\eta^2 P_{Q_B}(x) Pγ(x)PB,γ(x)ηPF(x)η2PQB(x)
然后将4.28、4.29、4.32聚合为单个check e ( [ c ( x ) ] 1 − [ v ] 1 γ [ P γ ( x ) ] 1 , [ 1 ] 2 ) e ( [ P γ ( x ) ] 1 , [ x ] 2 ) e([c(x)]_1-[v]_1\gamma[P_{\gamma}(x)]_1,[1]_2)e([P_{\gamma}(x)]_1,[x]_2) e([c(x)]1−[v]1γ[Pγ(x)]1,[1]2)e([Pγ(x)]1,[x]2)
4.9 cq完整协议
4.9.1 Setup阶段
Prover和Verifier均有公开输入 t i t_i ti i 1 , ⋯ , N i1,\cdots,N i1,⋯,N。如下流程由某可信方执行
1选择随机值 x ∈ F x\in \mathbb{F} x∈F输出 { [ x i ] 1 } i 0 N − 1 \{[x^i]_1\}_{i0}^{N-1} {[xi]1}i0N−1和 { [ x i ] 2 } i 0 N \{[x^i]_2\}_{i0}^{N} {[xi]2}i0N。数字 x x x必须删除。2计算并输出 [ Z V ( x ) ] 2 [Z_V(x)]_2 [ZV(x)]2。3计算 T ( x ) ∑ i t i L i ( x ) T(x)\sum_i t_iL_i(x) T(x)∑itiLi(x)。计算并输出 [ T ( x ) ] 2 [T(x)]_2 [T(x)]2。4对于每个 i 1 , ⋯ , N i1,\cdots,N i1,⋯,N计算并输出 根据4.22方程式计算并输出 [ Q i ( x ) ] 1 [Q_i(x)]_1 [Qi(x)]1 [ L i ( x ) ] 1 [L_i(x)]_1 [Li(x)]1 [ L i ( x ) − L i ( 0 ) x ] 1 [\frac{L_i(x)-L_i(0)}{x}]_1 [xLi(x)−Li(0)]1
setup阶段的输出组成SRS会同时发送给Prover和Verifier。
4.9.2 Proving阶段
Prover获得private witness值 f j f_j fj j 1 , ⋯ , m j1,\cdots,m j1,⋯,m而Verifier获得的为这些输入的承诺值 [ F ( x ) ] 1 [F(x)]_1 [F(x)]1。这些输入需源自同一可信方以对待证明的问题达成共识。
cq协议证明阶段流程为 注意Verifier根据4.30方程式计算 Q b , γ Q_{b,\gamma} Qb,γ其需要的 B ( γ ) , B ( 0 ) B(\gamma),B(0) B(γ),B(0)并不是由Prover发送。但Prover发送了 P B ( γ ) ( B ( γ ) − B ( 0 ) ) / γ P_{B}(\gamma)(B(\gamma)-B(0))/\gamma PB(γ)(B(γ)−B(0))/γ因此Verifier可计算 Q b , γ ( P B ( γ ) ⋅ γ A ( 0 ) ⋅ N / m ) ( F ( γ ) β ) − 1 Z H ( γ ) Q_{b,\gamma}\frac{(P_B(\gamma)\cdot \gammaA(0)\cdot N/m)(F(\gamma)\beta)-1}{Z_H(\gamma)} Qb,γZH(γ)(PB(γ)⋅γA(0)⋅N/m)(F(γ)β)−1
4.10 cq协议进一步batching和聚合
可使用Fiat-Shamir transformation来将以上协议转换为非交互式的。此时proof内容为 π c q { [ m ] 1 , [ A ] 1 , [ Q A ] 1 , [ Q B ] 1 , [ P A ] 1 , [ P B ] 1 , [ P B x N − m 1 ] 1 , [ P γ ] 1 , P B ( γ ) , F ( γ ) , A ( 0 ) } \pi_{cq}\{[m]_1,[A]_1,[Q_A]_1,[Q_B]_1,[P_A]_1,[P_B]_1,[P_Bx^{N-m1}]_1,[P_{\gamma}]_1,P_B(\gamma),F(\gamma),A(0)\} πcq{[m]1,[A]1,[QA]1,[QB]1,[PA]1,[PB]1,[PBxN−m1]1,[Pγ]1,PB(γ),F(γ),A(0)} 其中
前8个为group元素最后3个为field元素
相应的pairing等式有 e ( [ P B ( x ) ] 1 , [ x N − m 1 ] 2 ) e ( [ P B ( x ) ⋅ x N − m 1 ] 1 , [ 1 ] 2 ) e([P_B(x)]_1,[x^{N-m1}]_2)e([P_B(x)\cdot x^{N-m1}]_1,[1]_2) e([PB(x)]1,[xN−m1]2)e([PB(x)⋅xN−m1]1,[1]2) e ( [ A ( x ) ] 1 , [ T ( x ) ] 2 ) e ( [ Q A ( x ) ] 1 , [ Z V ( x ) ] 2 ) ⋅ e ( [ m ( x ) ] 1 − β [ A ( x ) ] 1 , [ 1 ] 2 ) e([A(x)]_1, [T(x)]_2)e([Q_A(x)]_1,[Z_V(x)]_2)\cdot e([m(x)]_1-\beta[A(x)]_1,[1]_2) e([A(x)]1,[T(x)]2)e([QA(x)]1,[ZV(x)]2)⋅e([m(x)]1−β[A(x)]1,[1]2) e ( [ A ( x ) ] 1 − [ A ( 0 ) ] 1 , [ 1 ] 2 ) e ( [ P A ( x ) ] 1 , [ x ] 2 ) e([A(x)]_1-[A(0)]_1,[1]_2)e([P_A(x)]_1,[x]_2) e([A(x)]1−[A(0)]1,[1]2)e([PA(x)]1,[x]2) e ( [ c ( x ) ] 1 − [ v ] 1 γ [ P γ ( x ) ] 1 , [ 1 ] 2 ) e ( [ P γ ( x ) ] 1 , [ x ] 2 ) e([c(x)]_1-[v]_1\gamma [P_{\gamma}(x)]_1,[1]_2)e([P_{\gamma}(x)]_1,[x]_2) e([c(x)]1−[v]1γ[Pγ(x)]1,[1]2)e([Pγ(x)]1,[x]2)
引入新的随机值 μ ∈ F \mu\in \mathbb{F} μ∈F很容易将以上最后2个pairing等式batch为 e ( [ c ( x ) ] 1 − [ v ] 1 γ [ P γ ( x ) ] 1 μ ( [ A ( x ) ] 1 − [ A ( 0 ) ] 1 ) , [ 1 ] 2 ) e ( [ P γ ( x ) ] 1 μ [ P A ( x ) ] 1 , [ x ] 2 ) e([c(x)]_1-[v]_1\gamma [P_{\gamma}(x)]_1\mu ([A(x)]_1-[A(0)]_1), [1]_2)e([P_{\gamma}(x)]_1\mu [P_A(x)]_1,[x]_2) e([c(x)]1−[v]1γ[Pγ(x)]1μ([A(x)]1−[A(0)]1),[1]2)e([Pγ(x)]1μ[PA(x)]1,[x]2) 再引入 ρ ∈ F \rho\in \mathbb{F} ρ∈F将其与第一个pairing等式batch有 e ( [ P γ ( x ) ] 1 μ [ P A ( x ) ] 1 , [ x ] 2 ) ⋅ e ( ρ [ P B ( x ) ] 1 , [ x N − m 1 ] 2 ) e ( [ c ( x ) ] 1 − [ v ] 1 γ [ P γ ( x ) ] 1 μ ( [ A ( x ) ] 1 − [ A ( 0 ) ] 1 ) ρ [ P B ( x ) ⋅ x N − m 1 ] 1 , [ 1 ] 2 ) e([P_{\gamma}(x)]_1\mu [P_A(x)]_1,[x]_2)\cdot e(\rho[P_B(x)]_1,[x^{N-m1}]_2)e([c(x)]_1-[v]_1\gamma [P_{\gamma}(x)]_1\mu ([A(x)]_1-[A(0)]_1)\rho [P_B(x)\cdot x^{N-m1}]_1,[1]_2) e([Pγ(x)]1μ[PA(x)]1,[x]2)⋅e(ρ[PB(x)]1,[xN−m1]2)e([c(x)]1−[v]1γ[Pγ(x)]1μ([A(x)]1−[A(0)]1)ρ[PB(x)⋅xN−m1]1,[1]2)
再引入 σ ∈ F \sigma\in\mathbb{F} σ∈F将其与第二个pairing等式batch为单个pairing等式。定义 L a [ P γ ( x ) ] 1 μ [ P A ( x ) ] 1 L_a[P_{\gamma}(x)]_1\mu [P_A(x)]_1 La[Pγ(x)]1μ[PA(x)]1 L b ρ [ P B ( x ) ] 1 L_b\rho [P_B(x)]_1 Lbρ[PB(x)]1 L c σ [ A ( x ) ] 1 L_c\sigma [A(x)]_1 Lcσ[A(x)]1 L d − σ [ Q A ( x ) ] 1 L_d-\sigma [Q_A(x)]_1 Ld−σ[QA(x)]1 R [ c ( x ) ] 1 − [ v ] 1 γ [ P γ ( x ) ] 1 μ ( [ A ( x ) ] 1 − [ A ( 0 ) ] 1 ) ρ [ P B ( x ) ⋅ x N − m 1 ] 1 σ ( [ m ( x ) ] 1 − β [ A ( x ) ] 1 ) R[c(x)]_1-[v]_1\gamma [P_{\gamma}(x)]_1\mu ([A(x)]_1-[A(0)]_1)\rho [P_B(x)\cdot x^{N-m1}]_1\sigma ([m(x)]_1-\beta [A(x)]_1) R[c(x)]1−[v]1γ[Pγ(x)]1μ([A(x)]1−[A(0)]1)ρ[PB(x)⋅xN−m1]1σ([m(x)]1−β[A(x)]1)
最终batch的单个pairing等式为 e ( L a , [ x ] 2 ) ⋅ e ( L b , [ x N − m 1 ] 2 ) ⋅ e ( L c , [ T ( x ) ] 2 ) ⋅ e ( L d , [ Z V ( x ) ] 2 ) e ( R , [ 1 ] 2 ) e(L_a,[x]_2)\cdot e(L_b, [x^{N-m1}]_2)\cdot e(L_c,[T(x)]_2)\cdot e(L_d,[Z_V(x)]_2)e(R,[1]_2) e(La,[x]2)⋅e(Lb,[xN−m1]2)⋅e(Lc,[T(x)]2)⋅e(Ld,[ZV(x)]2)e(R,[1]2)
由于以上每个pairing函数中的第二个参数均只依赖于setup具有相同setup的不同proofs通过引入新的随机参数 χ ∈ F \chi \in\mathbb{F} χ∈F来聚合为单个proof e ( ∑ k χ k L a , k , [ x ] 2 ) ⋅ e ( ∑ k χ k L b , k , [ x N − m 1 ] 2 ) ⋅ e ( ∑ k χ k L c , k , [ T ( x ) ] 2 ) ⋅ e ( ∑ k χ k L d , k , [ Z V ( x ) ] 2 ) e ( ∑ k χ k R k , [ 1 ] 2 ) e(\sum_k\chi ^kL_{a,k},[x]_2)\cdot e(\sum_k\chi^kL_{b,k},[x^{N-m1}]_2)\cdot e(\sum_k\chi^kL_{c,k},[T(x)]_2)\cdot e(\sum_k\chi^kL_{d,k},[Z_V(x)]_2)e(\sum_k\chi^kR_k,[1]_2) e(∑kχkLa,k,[x]2)⋅e(∑kχkLb,k,[xN−m1]2)⋅e(∑kχkLc,k,[T(x)]2)⋅e(∑kχkLd,k,[ZV(x)]2)e(∑kχkRk,[1]2)
4.11 cq协议开销
不同于plookup协议cq协议高度依赖KZG承诺方案。
cq协议的开销为
cq协议将plookup协议 O ( N log N ) O(N\log N) O(NlogN)复杂度移到了setup阶段使得这些计算对同一table只需做一次。cq协议证明阶段计算完全依赖于 m m m而可假设 m ≪ N m\ll N m≪N。【也就是说若 m ≪ N m\ll N m≪N条件不成立则没理由使用cq协议plookup协议的性能会更佳。】cq协议Prover工作量为 O ( m log m ) O(m\log m) O(mlogm)。cq协议proof size和Verifier工作量均为常量。
5. lookup协议演进
本节将简要介绍由plookup到cq的改进点并回顾二者之间的其它lookup协议。注意这些lookup协议都明确依赖KZG承诺方案。
5.1 Caulk
Arantxa Zapico等人2022年论文《 Caulk: Lookup arguments in sublinear time》提出了Caulk协议。 Caulk协议背后的核心思想为
以 O ( N log N ) O(N\log N) O(NlogN)预计算table encoding使得该table searchable in O ( log N ) O(\log N) O(logN)lookups也做类似的encoding使得对其的查找复杂度为 O ( m log N ) O(m\log N) O(mlogN)证明该encoding的额外复杂度为 O ( m 2 ) O(m^2) O(m2)。
Caulk协议
将table预计算为vanishing多项式 Z T ( x ) ∏ i 1 N ( x − t i ) Z_T(x)\prod_{i1}^{N}(x-t_i) ZT(x)∏i1N(x−ti)将lookups类似计算为 f ( x ) ∏ j 1 m ( x − f j ) f(x)\prod_{j1}^{m}(x-f_j) f(x)∏j1m(x−fj)Prover发送 Z T , f Z_T,f ZT,f的承诺值。将证明对于 S ⊆ T S\subseteq T S⊆T有 f Z S fZ_S fZS 转换为证明 Z T ∖ S ( x ) Z T ( x ) / Z S ( x ) Z_{T\setminus S}(x)Z_T(x)/Z_S(x) ZT∖S(x)ZT(x)/ZS(x)为一个多项式。对于每个 i 1 , ⋯ N i1,\cdots N i1,⋯Ncaulk会预计算多项式 g i ( x ) Z T ∖ t i ( x ) g_i(x)Z_{T\setminus t_i}(x) gi(x)ZT∖ti(x) 事实上这些就是cq协议中的cached quotients。若 S ⊆ T S\subseteq T S⊆T则有某些数字 c j ∈ F c_j\in\mathbb{F} cj∈F使得 Z T ∖ S ( x ) Z_{T\setminus S}(x) ZT∖S(x)可分解表示为 Z T ∖ S ( x ) ∑ j 1 m c j g i ( j ) ( x ) Z_{T\setminus S}(x)\sum_{j1}^{m}c_jg_i(j)(x) ZT∖S(x)∑j1mcjgi(j)(x) Prover仅需要计算 Z T ∖ S ( x ) Z_{T\setminus S}(x) ZT∖S(x)多项式的承诺值而Verifier仅需使用pairing检查 e ( [ f ] , [ Z T ∖ S ] ) e ( [ Z T ] , [ 1 ] ) e([f], [Z_{T\setminus S}])e([Z_T],[1]) e([f],[ZT∖S])e([ZT],[1])
5.2 Caulk 协议
Jim Posen等人2022年论文《Caulk: Table-independent lookup arguments》中提出了Caulk协议
Caulk协议中的主要缺点为其将table看成是通用集合而不是将其编码为某group。Caulk 协议通过预计算table改进了Caulk协议中的缺点。 Caulk 将table看成是某multiplicative group其初始值为group generator powers。从而消除了计算中对 N N N的依赖prover time仅为 O ( m 2 ) O(m^2) O(m2)。
5.3 Flookup 协议
Ariel Gabizon等人2022年论文《flookup: Fractional decompositionbased lookups in quasi-linear time independent of table size》提出了flookup协议
将预处理开销增加到了 O ( N log 2 N ) O(N\log ^2 N) O(Nlog2N)将Prover runtime降低到了 O ( m log 2 m ) O(m\log^2 m) O(mlog2m)同时牺牲了承诺方案的同态属性从而不支持将多个lookups和tables进行合并。
5.4 Baloo 协议
Arantxa Zapico等人2022年论文《Baloo: Nearly optimal lookup arguments》中提出了Baloo协议其为Caulk 协议的优化版
将lookups替换为a linear variant。然后使用单变量sumcheck来证明其所承诺的多项式。其预处理开销与Caulk相同为 O ( N log N ) O(N\log N) O(NlogN)。其Prover开销与flookup相同为 O ( m log 2 m ) O(m\log^2 m) O(mlog2m)。由于Baloo协议中的constants更大Baloo协议的实际开销要略高于flookup。但其保留了承诺方案的同态属性从而支持将多个lookups和tables进行合并。
lookup系列博客
PLOOKUPPLOOKUP代码解析Efficient polynomial commitment schemes for multiple points and polynomials学习笔记PLONK PLOOKUPPlonKup: Reconciling PlonK with plookupPLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge 学习笔记Plonk代码解析RapidUp: Multi-Domain Permutation Protocol for Lookup Tables学习笔记Lookup argument总览Halo2 学习笔记——设计之Proving system之Lookup argument1logUp-Multivariate lookups based on logarithmic derivativescqfast lookup argumentLookup Argument性能优化——Caulk2023年 ZK Hack以及ZK Summit 亮点记Research Day 2023Succinct ZKP最新进展Lasso、Jolt 以及 Lookup Singularity——Part 1Lasso、Jolt 以及 Lookup Singularity——Part 2深入了解LassoJoltLookup SingularityHalo2、Caulk、Baloo、Cq Lookup argument细览
