VincentC

KZG 承诺的同点批量打开：一个引理及其证明

· 更新于

多项式承诺让证明者先承诺一个多项式 ff，之后再令人信服地打开它在任意一点的取值。KZG 方案1的承诺和打开证明都只有一个群元素，这使它成为 PLONK 等证明系统的基础构件。实际系统里，验证者往往需要在同一个点 zz 上同时打开 tt 个多项式：逐个验证需要 2t2t 次配对，而一次随机线性组合可以把它降到 22 次。2 这篇笔记把其中用到的引理单独拿出来，完整地证明一遍。

记号

设 G1,G2,GT\G_1, \G_2, \G_T 是阶为素数 pp 的循环群，生成元分别为 g1,g2,gTg_1, g_2, g_T；e ⁣:G1×G2→GTe\colon \G_1 \times \G_2 \to \G_T 是非退化的双线性映射，F=Fp\F = \F_p。对 a∈Fa \in \F，记 [a]1=a⋅g1\gi{a} = a \cdot g_1，[a]2=a⋅g2\gii{a} = a \cdot g_2。

定义（KZG 多项式承诺）

令 dd 为次数上界。可信设置选取随机的 τ←F\tau \gets \F，输出

srs=([1]1, [τ]1, [τ2]1, …, [τd]1;    [1]2, [τ]2)\srs = \bigl(\gi{1},\, \gi{\tau},\, \gi{\tau^2},\, \dots,\, \gi{\tau^d};\;\; \gii{1},\, \gii{\tau}\bigr)

并销毁 τ\tau。对任意 f∈F[X]f \in \F[X]，deg⁡f≤d\deg f \le d：

  • 承诺：com(f)=[f(τ)]1\com(f) = \gi{f(\tau)}，它可以由 srs\srs 线性地算出；
  • 打开：要证明 f(z)=vf(z) = v，令 q(X)=f(X)−vX−zq(X) = \dfrac{f(X) - v}{X - z}，证明为 π=[q(τ)]1\pi = \gi{q(\tau)}；
  • 验证：接受当且仅当 e(C−[v]1, [1]2)=e(π, [τ]2−[z]2)e\bigl(C - \gi{v},\, \gii{1}\bigr) = e\bigl(\pi,\, \gii{\tau} - \gii{z}\bigr)。

验证等式之所以成立，是因为 qq 是多项式当且仅当 (X−z)∣f(X)−v(X - z) \mid f(X) - v，也就是当且仅当 f(z)=vf(z) = v。

同点批量打开

设证明者已经承诺了 f1,…,ftf_1, \dots, f_t，承诺为 Ci=com(fi)C_i = \com(f_i)，并声称对所有 ii 都有 fi(z)=vif_i(z) = v_i。协议如下：

  1. 验证者发送随机挑战 γ←F\gamma \gets \F（非交互的情形下，γ\gamma 由 Fiat–Shamir 变换得到）；
  2. 证明者计算批量商多项式 h(X)=∑i=1tγi−1⋅fi(X)−viX−zh(X) = \sum_{i=1}^{t} \gamma^{i-1} \cdot \dfrac{f_i(X) - v_i}{X - z}，发送 π=[h(τ)]1\pi = \gi{h(\tau)}；
  3. 验证者计算 Cγ=∑i=1tγi−1CiC_\gamma = \sum_{i=1}^{t} \gamma^{i-1} C_i 与 vγ=∑i=1tγi−1viv_\gamma = \sum_{i=1}^{t} \gamma^{i-1} v_i，接受当且仅当
e(Cγ−[vγ]1, [1]2)=e(π, [τ]2−[z]2).e\bigl(C_\gamma - \gi{v_\gamma},\, \gii{1}\bigr) = e\bigl(\pi,\, \gii{\tau} - \gii{z}\bigr).

记 Fγ(X)=∑i=1tγi−1(fi(X)−vi)F_\gamma(X) = \sum_{i=1}^{t} \gamma^{i-1}\bigl(f_i(X) - v_i\bigr)。诚实的证明者满足 Cγ−[vγ]1=[Fγ(τ)]1C_\gamma - \gi{v_\gamma} = \gi{F_\gamma(\tau)} 以及 Fγ(X)=h(X) (X−z)F_\gamma(X) = h(X)\,(X - z)，于是完备性由双线性直接得到：

e(Cγ−[vγ]1, [1]2)=e([Fγ(τ)]1, [1]2)=e([h(τ) (τ−z)]1, [1]2)=e([h(τ)]1, [τ−z]2)=e(π, [τ]2−[z]2).\begin{aligned} e\bigl(C_\gamma - \gi{v_\gamma},\, \gii{1}\bigr) &= e\bigl(\gi{F_\gamma(\tau)},\, \gii{1}\bigr) \\ &= e\bigl(\gi{h(\tau)\,(\tau - z)},\, \gii{1}\bigr) \\ &= e\bigl(\gi{h(\tau)},\, \gii{\tau - z}\bigr) = e\bigl(\pi,\, \gii{\tau} - \gii{z}\bigr). \end{aligned}

把 hh 完全展开，就是下面这个很长的式子（它同时用来测试窄屏上的横向滚动）：

h(X)=f1(X)−v1X−z+γ⋅f2(X)−v2X−z+γ2⋅f3(X)−v3X−z+γ3⋅f4(X)−v4X−z+⋯+γt−1⋅ft(X)−vtX−z=1X−z∑i=1tγi−1(fi(X)−vi).h(X) = \frac{f_1(X) - v_1}{X - z} + \gamma \cdot \frac{f_2(X) - v_2}{X - z} + \gamma^{2} \cdot \frac{f_3(X) - v_3}{X - z} + \gamma^{3} \cdot \frac{f_4(X) - v_4}{X - z} + \cdots + \gamma^{t-1} \cdot \frac{f_t(X) - v_t}{X - z} = \frac{1}{X - z} \sum_{i=1}^{t} \gamma^{i-1} \bigl(f_i(X) - v_i\bigr).

引理与证明

可靠性的核心是：只要有一个声称的取值是错的，做完随机线性组合之后它以压倒性的概率「仍然是错的」。

引理（随机线性组合）

设 f1,…,ft∈F[X]f_1, \dots, f_t \in \F[X]，z,v1,…,vt∈Fz, v_1, \dots, v_t \in \F，FγF_\gamma 如上定义。若存在 jj 使得 fj(z)≠vjf_j(z) \neq v_j，则

Pr⁡γ←F[ (X−z)∣Fγ(X) ]  ≤  t−1∣F∣.\Pr_{\gamma \gets \F}\Bigl[\, (X - z) \mid F_\gamma(X) \,\Bigr] \;\le\; \frac{t-1}{|\F|}.
证明

由余式定理，(X−z)∣Fγ(X)(X - z) \mid F_\gamma(X) 当且仅当 Fγ(z)=0F_\gamma(z) = 0。把 Fγ(z)F_\gamma(z) 看成关于 γ\gamma 的多项式：

P(γ)=∑i=1t(fi(z)−vi) γi−1  ∈  F[γ].P(\gamma) = \sum_{i=1}^{t} \bigl(f_i(z) - v_i\bigr)\, \gamma^{i-1} \;\in\; \F[\gamma].

它的次数至多为 t−1t - 1，并且 γj−1\gamma^{j-1} 的系数 fj(z)−vj≠0f_j(z) - v_j \neq 0，所以 PP 不是零多项式。域上非零多项式的根的个数不超过它的次数，因此使 P(γ)=0P(\gamma) = 0 的 γ\gamma 至多有 t−1t - 1 个；而 γ\gamma 在 F\F 上均匀分布，故所求概率不超过 (t−1)/∣F∣(t-1)/|\F|。

定理（批量打开的可靠性，非正式）

假设单个多项式的 KZG 方案满足求值绑定性，并且从敌手输出的每个承诺 CiC_i 都能提取出对应的多项式 fif_i（例如在代数群模型中3）。那么对任何多项式时间的敌手，批量验证通过、同时又存在某个 jj 使 fj(z)≠vjf_j(z) \neq v_j 的概率至多为 (t−1)/∣F∣+negl(λ)(t-1)/|\F| + \negl(\lambda)。

证明

（概要）设验证通过且某个 fj(z)≠vjf_j(z) \neq v_j。由引理 1，除去至多 (t−1)/∣F∣(t-1)/|\F| 的概率，有 Fγ(z)≠0F_\gamma(z) \neq 0。此时 Cγ−[vγ]1C_\gamma - \gi{v_\gamma} 是多项式 FγF_\gamma 的承诺，而敌手的 π\pi 把它在 zz 处打开为 00；归约算法知道所有的 fif_i，可以自己诚实地算出把同一个承诺在 zz 处打开为 Fγ(z)≠0F_\gamma(z) \neq 0 的证明。同一个承诺在同一点有两个取值不同的合法打开，与求值绑定性矛盾。

代价

逐个打开批量打开
证明大小tt 个 G1\G_1 元素11 个 G1\G_1 元素
配对次数2t2t22
G1\G_1 上的标量乘约 2t2t约 t+1t + 1
额外的可靠性损失无(t−1)/∣F∣(t-1)/\lvert\F\rvert

对 ∣F∣≈2255|\F| \approx 2^{255} 和实际中出现的 t≤210t \le 2^{10}，这个损失完全可以忽略。

Footnotes

  1. Aniket Kate, Gregory M. Zaverucha, Ian Goldberg, “Constant-Size Commitments to Polynomials and Their Applications”, ASIACRYPT 2010. ↩︎

  2. Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru, “PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge”, IACR ePrint 2019/953. ↩︎

  3. Georg Fuchsbauer, Eike Kiltz, Julian Loss, “The Algebraic Group Model and its Applications”, CRYPTO 2018. ↩︎

Comments