解释 SNARKs 第六部分: 匹诺曹协议

<< 第五部分

在第五部分中,我们看到了 Alice 为 Bob 验证声明的过程使如何被翻译成一个 “语言多项式” 的,它被称为二次运算程序 (QAP)。

在本部分中,我们将展示 Alice 如何发送一个短证明给 Bob来验证她对于 QAP 的成真指派。 我们将使用 Parno, Howell, Gentry 和 Raykova 的 匹诺曹协议。但是先让我们回忆一下我们上次给出的 QAP 的定义:

一个二次算数程序 QQ,有 阶数 |d| *和尺寸 mm ,它由多项式 L1,,LmL1,…,Lm, R1,,RmR1,…,Rm, O1,,OmO1,…,Om 组成,并且有一个目标多项式 TT 阶数dd

一个赋值操作 (c1,,cm)(c1,…,cm) 满足 QQ 如果,定义 L:=mi=1ciLi,R:=mi=1ciRi,O:=mi=1ciOiL:=∑i=1mci⋅Li,R:=∑i=1mci⋅Ri,O:=∑i=1mci⋅Oi 并且 P:=LROP:=L⋅R−O, 我们得到 TT 可以整除 PP

正如我们在第 5 本分中看到的,Alice 通常希望来验证她有一个成真指派来处理一些额外的限制,比如 cm=7cm=7; 但是我们在这里出于简便考虑将其忽略,并显示如何验证 某些 成真指派。

如果 Alice 有一个成真指派,这意味着根据之前定义的 L,R,O,PL,R,O,P,这里存在一个多项式 HH 使得 P=HTP=H⋅T 成立。特别的,对于任意 s?ps∈Fp,我们有 P(s)=H(s)T(s)P(s)=H(s)⋅T(s)

假设现在 ALice 没有 一个成真指派,但是她现在依然根据一些非成真指派 (c1,,cm)(c1,…,cm) 建立了 L,R,O,PL,R,O,P 。这时我们得到保证 TT 无法整除 PP。这意味着对于任意多项式 HH ,同时多项式中最高的阶数为 ddPPHTH⋅T 将是不同的多项式。注意到 PPHTH⋅T 中的最高阶数为 2d2d

现在我们可以使用著名的 Schwartz-Zippel Lemma ,它告诉我们两个阶数不同的多项式,如果在 2d2d 点可以取到相同的值,则它们在 2d2d 点的 s?ps∈Fp 也相同。因此,如果 pp2d2d 大很多,则很有可能 P(s)=H(s)T(s)P(s)=H(s)⋅T(s),因为随机取值的 s?ps∈Fp 非常小。

这表明接下来的协议草案可以测试 ALice 是否有一个成真指派。

  1. Alice 选择多项式 L,R,O,HL,R,O,H 的最高阶数为 dd
  2. Bob 随机选择一个点 s?ps∈Fp,并且计算 E(T(s))E(T(s))
  3. Alice 发送给 Bob 这些多项式在 ss 点的 隐藏值,比如 E(L(s)),E(R(s)),E(O(s)),E(H(s))E(L(s)),E(R(s)),E(O(s)),E(H(s))
  4. Bob 检查目标多项式是否在 ss 处收敛。也就是说,他会检查是否有 E(L(s)R(s)O(s))=E(T(s)H(s))E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s)) 等式成立。

接下来,如果 ALice 没有一个成真指派,她将最终使用一个与等式不相成立多项式,也因此并没有得到 ss 的大多数选择。因此,Bob 在这种情况下有很高的概率会拒绝选择 ss

现在问题是,我们是否有工具来实施这种设计。其中的关键点是 Alice 必须选择她将要使用的多项式,且在 直到 ss 的前提下。但是,这正是我们要解决的问题 可验证的盲评价协议,这些已经在第 2-4 部分中讨论过了。

考虑到我们已经具备了这些知识,在把这个构想变成 zk-SNARK 之前,我们需要确定四个关键问题。我们将在本部分中解决其中两个,而另外两个将在下一部分中讨论。

确认 ALICE 根据一个赋值选择她的多项式

这是一个要点:如果 Alice 没有一个满意的赋值,这并不意味着她不能找到 任何 L,R,O,HL,R,O,H 多项式,这些多项式在 dd 点处有 LRO=THL⋅R−O=T⋅H,它仅意味着她不能找到 L,RL,ROO 都是 由赋值产生的 一类多项式,也就是,对于 相同的 (c1,,cm)(c1,…,cm)L:=mi=1ciLi,R:=mi=1ciRi,O:=mi=1ciOiL:=∑i=1mci⋅Li,R:=∑i=1mci⋅Ri,O:=∑i=1mci⋅Oi

在第四部分中的协议仅仅保证了她在相同的度上使用了相同的多项式 L,R,OL,R,O,但并不保证它们是由赋值产生的。这就是一个使正式的证明变的模糊的点,也是我们的方案解决的不够清晰的点。

让我们用以下的方法将多项式组 L,R,OL,R,O 结合入同一多项式 FF

F=L+Xd+1R+X2(d+1)OF=L+Xd+1⋅R+X2(d+1)⋅O

使用 RR 乘以 Xd+1Xd+1 和 使用 OO 乘以 X2(d+1)X2(d+1) 的目的是 L,R,OL,R,O 的系数在 FF 中 “不会被混用”:在 FF1,X,,Xd1,X,…,Xd 的系数是 LL 的精确系数,下一个 d+1d+1Xd+1,,X2d+1Xd+1,…,X2d+1 中的系数是 RR 的精确系数,而最后一个 d+1d+1 的系数是 OO.

让我们使用相似的方式在 QAP 的定义中结合多项式,为每一个 i{1,,m}i∈{1,…,m} 定义一个多项式 FiFi,它的第一个 d+1d+1 的系数是 LiLi 的系数,之后跟随的系数是 RiRiOiOi。也就是说,对于每一个 i{1,,m}i∈{1,…,m} ,我们都定义了多项式。

Fi=Li+Xd+1Ri+X2(d+1)OiFi=Li+Xd+1⋅Ri+X2(d+1)⋅Oi

注意到,当我们将 FiFi 中的 LiLi, RiRi, 和 OiOi 的其中两个“分别相加”时,比如,F1+F2=(L1+L2)+Xd+1(R1+R2)+X2(d+1)(O1+O2)F1+F2=(L1+L2)+Xd+1⋅(R1+R2)+X2(d+1)⋅(O1+O2)

更概括的,假设对于某些 (c1,,cm)(c1,…,cm) 我们有 F=mi=1ciFiF=∑i=1mci⋅Fi 。而对于相同的系数 (c1,,cm)(c1,…,cm),我们将得到 L=mi=1ciLi,R=mi=1ciRi,O=mi=1ciOiL=∑i=1mci⋅Li,R=∑i=1mci⋅Ri,O=∑i=1mci⋅Oi。 换句话来说,如果 FFFiFi 的线性组合,这意味着 L,R,OL,R,O 确实是有赋值产生的结果。

因此,Bob 将询问 Alice 来验证 FF 是否是 FiFi 的线性组合。 这样的做法与评价可验证的协议相类似:

Bob 选择一个随机的 β?pβ∈Fp∗,并且将隐藏的部分 E(βF1(s)),,E(βFm(s))E(β⋅F1(s)),…,E(β⋅Fm(s)) 发送给 Alice。他这是向 Alice 索取 E(βF(s))E(β⋅F(s)) 元素。如果她成功了,随之会产生一个拓展版本的 知识系数假设,这个证据按时她知道如何编写 FiFi 的线性组合 FF

添加零知识部分 – 隐藏赋值

在一份 zk-SNARK 中,Alice 想要隐藏所有有关她赋值的信息。然而,隐藏的 E(L(s)),E(R(s)),E(O(s)),E(H(s))E(L(s)),E(R(s)),E(O(s)),E(H(s)) 确实包含了 某些 赋值信息。

比如,对于某些其他的满意赋值 (c1,,cm)(c1′,…,cm′),Bob 可以计算出对应的 L,R,O,HL′,R′,O′,H′ 和隐藏的 E(L(s)),E(R(s)),E(O(s)),E(H(s))E(L′(s)),E(R′(s)),E(O′(s)),E(H′(s))。如果这些与 Alice 的隐藏值不相同,他就可以推断出 (c1,,cm)(c1′,…,cm′) 不是 Alice 的赋值。

为了避免在她的赋值操作中的信息泄露,Alice 将通过为每一个多项式添加一个 “随机的 TT-转移” 的方式来隐藏她的赋值操作。 那就是,她随机地选择 δ1,δ2,δ3?pδ1,δ2,δ3∈Fp∗ 并且定义 Lz:=L+δ1T,Rz:=R+δ2T,Oz:=O+δ3TLz:=L+δ1⋅T,Rz:=R+δ2⋅T,Oz:=O+δ3⋅T

假设 L,R,OL,R,O 是由满意赋值产生的;因此,对于某些 HHLRO=THL⋅R−O=T⋅H 。由于我们刚刚在各处添加了 TTTT 同样可以整除 LzRzOzLz⋅Rz−Oz。 让我们做一些计算来看看:

LzRzOz=(L+δ1T)(R+δ2T)Oδ3TLz⋅Rz−Oz=(L+δ1⋅T)(R+δ2⋅T)−O−δ3⋅T =(LRO)+Lδ2T+δ1TR+δ1δ2T2δ3T=(L⋅R−O)+L⋅δ2⋅T+δ1⋅T⋅R+δ1δ2⋅T2−δ3⋅T =T(H+Lδ2+δ1R+δ1δ2T)=T⋅(H+L⋅δ2+δ1⋅R+δ1δ2⋅T)

因此,定义 H=H+Lδ2+δ1R+δ1δ2TH′=H+L⋅δ2+δ1⋅R+δ1δ2⋅T,我们有 LzRzOz=THzLz⋅Rz−Oz=T⋅Hz。 因此,如果 Alice 使用多项式 Lz,Rz,Oz,HzLz,Rz,Oz,Hz 而不是 L,R,O,HL,R,O,H,Bob 将接受这笔交易。

在另一方面,这些多项式使用 T(s)0T(s)≠0 评价了 s?ps∈Fp (它们几乎全都是 ddss),这并不会揭露赋值的相关信息。比如,由于 T(s)T(s) 非零且 δ1δ1 随机, δ1T(s)δ1⋅T(s) 是一个随机值,并且因此 Lz(s)=L(s)+δ1T(s)Lz(s)=L(s)+δ1⋅T(s) 并不会揭露 L(s)L(s) 的任何信息,这是由于随机价值所掩盖的。

下一次会有什么内容?

我们已经展示了匹诺曹协议的设计,从中了解了 Alice 可以向 Bob 证实她拥有一个对于 QAP 的满意赋值,并且不需要揭露赋值的内容。然而,在获得 zk-SNARK 之前还有两个重要的问题需要提前解决:

  • 在这份草案中,Bob 需要一个”支持乘法”的 HH。比如,他需要计算 E(H(s)T(s))E(H(s)⋅T(s)) from E(H(s))E(H(s))E(T(s))E(T(s))。然而,我们目前并没有看到任何一个HH 可以实现这个方法的例子。我们仅仅看到了一个 HH 可以支持加法和线性组合。
  • 贯穿整个系列,我们已经讨论了 Alice 和 Bob 之间的 互动 协议。我们最终的目标,是让 Alice 发送单独的信息 非交互式证明,它同时是 公开可验证的 – 这意味着任何看到这个单独的信息证明的人,将能够确信它的有效性,而不仅仅是 Bob (他之前和 Alice 交流过)。

这些问题都能够通过配对椭圆曲线的方法解决,我们将在接下来和最后的部分中加以说明。

发表评论

电子邮件地址不会被公开。 必填项已用*标注