原文标题：《从零开始学习 zk-SNARK（五）——Pinocchio 协议》
原文来源：安比实验室 作者：Maksym Petkus
导读
even@ 安比实验室: 作为本系列的最后一篇文章，本文继续对 zk-SNARK 协议进行完善，最终形成一个完整的 zk-SNARK 协议。
作者：Maksym Petkus
翻译 & 注解：even@ 安比实验室（[email protected]）
校对：valuka@ 安比实验室
本系列文章已获作者中文翻译授权。
回顾
【零知识证明】zk-SNARK（一）——多项式的性质与证明
【零知识证明】zk-SNARK（二）——多项式非交互式零知识证明
【零知识证明】zk-SNARK（三）——从程序到多项式的构造
【零知识证明】zk-SNARK（四）——多项式的约束
约束和公共输
约束
我们的分析主要集中在运算的概念上。但是，协议实际上不是去做」计算「，而是检验输出值是否是操作数正确运算得到的结果。所以我们称之为约束，即一个 verifier 约束 prover 去为预定义的「程序」提供有效值，而无论这个「程序」是什么。多个约束组成的系统被称为「约束系统」（在我们的例子中这是一个一阶约束系统，或被称为 R1CS）。
@Maksym（作者）：这里其实隐含了寻找所有正确答案的一个方法就是对所有可能的组合值进行一次暴力破解，然后只选择一个满足的约束，或者使用可满足约束的更精密的技术 [con18]。
注解
even@ 安比实验室：请注意这个约束是定义在算术电路，或者布尔电路上。因为这两类电路的可满足性问题是 NP-Complete 问题。
因而我们也可以使用约束来确保其它的关系。例如，如果我们想要确认变量 a 的值只能为 0 或 1（即二进制数），我们可以用一个简单的约束去做这件事：
更复杂的约束也可以用这种方式表示，以此来确保使用的值满足规则。注意很重要的一点是在当前的计算结构中是不能对 1 进行约束的：
因为值 1（以及前面约束中的 2）必须通过 c·vone 表达出来，其中 c 可以被固定到 proving key 中，但是因为 v 是由 prover 提供的，所以可以是任何别的值。尽管我们可以通过设置 c=0 来强制 c·vone 变成 0，但是在我们前面受限的构造方法中很难找到一个约束来强制 vone 为 1。于是，Verifier 需要有一种办法来设置 vone 的值。
注解
even@ 安比实验室：我们前文中提到的表达式的约束关系就称为 R1CS。
公共输入和 1
如果不能根据 verifier 的输入对其进行检查，那么证明的可用性将受到限制。也就是说，虽然知道 prover 将两个值相乘但是并不知道这些值和/或计算结果。尽管有可能在 proving key 中通过「硬编码」来进行验证一些特定的值（如，乘法运算的结果必须为 12），但这就需要针对每一个想要的「verifier 的输入」生成单独的密钥对。
注解
even@ 安比实验室：这样会严重限制实用性，电路需要支持参数。
因而如果可以由 verifier 而不是 prover 为计算指定一些值（输入或者输出），包括，那证明就可以变得更通用了。
首先，我们看一下要证明的值 gL(s)，gR(s)，gO(s)。因为这里使用了同态加密所以可以增大这些值，例如，我们可以与另一个加密的多项式相加使得值为 gL(s) · glv(s) =gL(s)+lv(s)。
这样如果我们能够在提供给 prover 的变量多项式中排除必要的一项，verifier 就可以在这一项变量多项式上设置他自己的值，并且使得检查依然能够通过。
因为 verifier 已经可以通过加入α-转换来限制 prover 选择多项式了，所以这个检查结果就很容易得到。因而当消除了它的 αs 和 β 校验和对应的项，这些可变多项式就可以从 proving key 转移到 verification key 当中去了。
必要的协议更新为：
注意：根据协议（单个变量操作数多项式 的章节）的性质，由多项式 l0(x),r0(x),o0(x) 表示的值 1 已在相应的运算中具备了合适的值，因此不需要再赋值了。
verifier 将不得不在验证步骤中做额外的工作，使得赋值的变量成比例。
这实际上是把一些变量从 prover 手中拿到 verifier 的手中，并同时保持等式相等。因而只有当 prover 和 verifier 的输入中使用相同值的时候，有效计算检查才依然成立。
1 这个值相当重要，它能够通过与任意一个常数项相乘来生成这个值（从选择的有限域上），例如，用 123 去乘以 a：
注解
even@ 安比实验室：这里将原本由 prover 赋值的一些变量改为由拿到 verifier 赋值，使得 prover 不得不与 verifier 保持相同的输入。这不仅解决了 Verifier 参数输入的问题，也间接解决了常数赋值的问题。
零知识计算
计算的零知识证明
自从引入通用计算协议（计算的证明这一章节），我们一直放弃了零知识 的性质，这是为了让协议的改进变得更简单。至此，我们已经构建了可验证的计算协议。
以前我们使用随机数δ-转换来构造多项式的「零知识」证明，这种方法能够使得证明与随机数无法区分（零知识这一章节）：
通过计算我们证明了：
但是问题是使用相同的 δ 会妨碍安全性，因为我们在证明中分别用了以下这些值：
其他人可以很容易得辨认出两个不同的多项式值是否相同，以此来获取一些知识，即：gδL(s)=gδR(s)
L(s) 和 R(s) 的不同值之间潜在的微小关系可能会通过暴力破解来区分开来，例如如果 L(s) = 5R(s)，就可以对 i ∈ {1…N} 取值反复校验 gL(s)=(gR(s))i，只需要执行 5 步就可以揭示出两者 5 倍区别的关系。同样的暴力破解也可以用在破解加密值的加法运算上，如：gL(s) = gR(s)+5
证明元素之间的其它关系也可能会被发现，例如，如果 e(gδL(s),gδR(s)) = e(gδ2O(s),g)，那么也就表示 L(x) ? R(x) = O(x)。
注意：一致性检查优化 使得挖掘数据关系变得更加困难了，但是依然能够发现一些关系，且不说 verifier 可以选择特定 ρl，ρr 来为揭示知识提供便利（只要这不是一个多样化的 setup）。
最终，我们需要对每一个多项式的值使用不同的随机数 (δs)，例如：
δlL(s) ·δrR(s) - δoO(s) =t(s)·(△??h(s))
为了解决等式右边不相等的问题，我们不必改变协议，只要修改证明的值 h(s) 即可。这里 Delta (Δ) 代表为了平衡方程另一侧的随机性而对 h(s) 做的处理，??代表乘法运算或者加法运算（这个反过来也适应了除法和减法）。如果我们选择用乘法 (?? = ×) 来计算 Δ，也就意味着不太可能有较大的概率可以找到一个 Δ，因为存在随机性：
于是既隐藏了加密值，又使得等式可以通过有效计算 的检查。
非常奇怪的是最初的 Pinocchio 协议 [Par+13] 主要关注可验证的计算，而较少涉及 零知识 性质，这其实只需要一点点小修改，这个几乎是没有什么成本的。
注解
even@ 安比实验室: 与前文中的零知方案不同，这里通过相加而不是相乘的方式来确保 prover 知识的零知性。
Pinocchio 协议是针对 GGPR 论文的改进，在 3.1 节中也提到了实现零知识只需要沿用 GGPR 论文的方法即可，并不是这篇论文的贡献。另外，Pinocchio 协议论文侧重工程实践，在 2013 年时，零知识证明还并没有得到应用。真正的应用还是自从匿名币 ZCash 起。
zk-SNARK 协议
在这一步步的改进之后，我们得到了最终版本的 zkSNARK，又名 Pinocchio [Par + 13]，协议（零知识 部分是可选的并用不同的颜色 标注出来了），就是：
结论
我们最终完成了一个允许证明计算的有效协议：
简明 (Succinctly)——独立于计算量，证明是恒定的，小尺寸的
非交互性 (Non-interactive)——证明只要一经计算就可以在不直接与 prover 交互的前提下使任意数量的 verifier 确信
可论证的知识 (with Argument of Knowledge)——对于陈述是正确的这点有不可忽略的概率，即无法构造假证据；并且 prover 知道正确陈述的对应值（即：证据），例如，如果陈述是「B 是 sha256(a) 的结果」那么就说明 prover 知道一些值 a 能够使得 B = sha256(a) 成立，因为 B 只能够通过 a 的知识计算出来，换句话说就是无法通过 B 来反算出 a（假定 a 的熵足够）。
陈述有不可忽略的概率是正确的 (even@ 安比实验室: 这里指 Soundness 可靠性)，即，构造假证据是不可行的
零知识 ( zero-knowledge)——很「难」从证明中提取任何知识，即，它与随机数无法区分。
注解
even@ 安比实验室: 所谓 Argument——论证，区别于 Proof——证明。Pinocchio 协议是 Argument 而非 Proof。这是因为 Pinocchio 的可靠性是 Computational Soundness，Statistical ZK，这一类的证明系统被称为 Argument。所谓的 Computational Soundness 暗含了这样的事实：如果 Prover 计算能力足够强大的话，可以破坏可靠性。
基于多项式的特殊性质，模运算，同态加密，椭圆曲线密码学，加密配对和发明者的聪明才智才使得这个协议得以实现。
这个协议证明了一个特殊有限执行机制的计算，即在一次运算中可以将几乎任意数量的变量加在一起但是只能执行一次乘法，因而就有机会优化程序以有效地利用这种特性的同时也使用这个结构最大限度地减少计算次数。
为了验证一个证明，verifier 并不需要知道所有的秘密数据，这一点很关键，这就使得任何人都可以以非交互式方式发布和使用正确构造的 verification key。这一点与只能让一个参与者确信证明的"指定 verifier"方案相反，因而它的信任是不可转移的。在 zkSNARK 中，如果不可信或由单方生成密钥对，则可以实现这个属性。
零知识证明构造领域正在不断发展，包括引入了优化（[BCTV13, Gro16, GM17]），改进例如可更新的 proving key 和 verification key（[Gro+18]），以及新的构造方法（Bulletproofs [Bün+17], ZK-STARK [Ben+18], Sonic [Mal+19]）。
注解
even@ 安比实验室: 至此, 本系列文章的介绍已经全部结束，大家是不是已经对 zkSNARK 协议（Pinocchio 协议）非常熟悉了？其实任何复杂的协议掌握了核心思想，都可以抽丝剥茧将其变得通俗易懂。
零知识证明的学习还有很长的路要走，本文只是一个入门的资料，正如文章中所述，零知识证明构造领域正在不断发展，不断的有新的研究突破呈现在我们面前。这是一个非常有趣的领域，后续也非常欢迎小伙伴跟我们一起继续学习和研究零知识证明技术。
再次感谢 Maksym Petkus 大神的分享和授权。文章翻译存在不足之处，欢迎纠正，补充，指导。
对文章有任何疑问欢迎进入微信圈子「零知识证明」留言，对零知识证明感兴趣的小伙伴欢迎加入安比实验室讨论群一起讨论。
原文链接
https://arxiv.org/pdf/1906.07221.pdf
https://medium.com/@imolfar/why-and-how-zk-snark-works-7-constraints-and-public-inputs-e95f6596dd1c
https://medium.com/@imolfar/why-and-how-zk-snark-works-8-zero-knowledge-computation-f120339c2c55
参考文献
[con18]—Wikipedia contributors. Constraint satisfaction. Wikipedia, The Free Encyclopedia. 2018.
[Gen+12]—Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. Cryptology ePrint Archive, Report 2012/215. https://eprint.iacr.org/2012/215. 2012.
[Par+13]—Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. Cryptology ePrint Archive, Report 2013/279. https://eprint.iacr.org/2013/279. 2013.
[BCTV13]—Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. Cryptology ePrint Archive, Report 2013/879. https://eprint.iacr.org/2013/879. 2013.
[Gro10]—Jens Groth.「Short pairing-based non-interactive zero-knowledge arguments」. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2010, pp. 321–340.
[GM17]—Jens Groth, Mary Maller. Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs. Cryptology ePrint Archive, Report 2017/540. https://eprint.iacr.org/2017/540. 2017.
[Gro+18]—Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, and Ian Miers. Updatable and Universal Common Reference Strings with Applications to zk-SNARKs. Cryptology ePrint Archive, Report 2018/280. https://eprint.iacr.org/2018/280. 2018.
[Bün+17]—Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. Cryptology ePrint Archive, Report 2017/1066. https://eprint.iacr.org/2017/1066. 2017.
[Ben+18]—Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046. https://eprint.iacr.org/2018/046. 2018.
[Mal+19]—Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings. Cryptology ePrint Archive, Report 2019/099. https://eprint.iacr.org/2019/099. 2019.
来源链接：weixin.qq.com
区块律动 BlockBeats 提醒，根据银保监会等五部门于 2018 年 8 月发布《关于防范以「虚拟货币」「区块链」名义进行非法集资的风险提示》的文件，请广大公众理性看待区块链，不要盲目相信天花乱坠的承诺，树立正确的货币观念和投资理念，切实提高风险意识；对发现的违法犯罪线索，可积极向有关部门举报反映。
—-
编译者/作者：区块律动BlockBeat
玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。
|
