理解Groth16，一些细节上的说明

Tiny熊

发布于 2022-05-25 16:09:01

8810

发布于 2022-05-25 16:09:01

本文作者：hsyodyssey[1]

V 神曾经写过一篇非常好的介绍 R1CS 与 QAP 问题的文章[2]。但是，对于不熟悉密码学[3]的，或者说如何使用密码学的思想来解决问题的票友们来说，文章中的一些逻辑上的跨度还是大了一些。尤其是在 R1CS 转换成多项式的地方，初次接触的人可能会一脸懵逼，不明白为什么要这么做。下面我就从我的理解来谈一谈，从 R1CS 到 QAP 这一过程。

在 Groth16 的流程中，我们首先需要把计算问题拍平成电路的形式。在这一步骤中，我们会将原始的计算问题，解构成电路的形式(Circuit)。这个电路和原始的计算问题是等价。电路由若干的有输入有输出的算数电路门(Gate)组成。通常情况下，这些电路门都是由两个输入变量，一个输出变量组成。然后我们基于每一个电路门，来构造 R1CS 约束。

a * b = c

这里我们直接使用 V 神的博客[4]中的例子。下面的三个矩阵是就是原问题对应的电路的 R1CS 的约束矩阵。

A [0, 1, 0, 0, 0, 0][0, 0, 0, 1, 0, 0] [0, 1, 0, 0, 1, 0][5, 0, 0, 0, 0, 1]

B [0, 1, 0, 0, 0, 0][0, 1, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0][1, 0, 0, 0, 0, 0]

C [0, 0, 0, 1, 0, 0][0, 0, 0, 0, 1, 0] [0, 0, 0, 0, 0, 1][0, 0, 1, 0, 0, 0]

这三个矩阵都包含了四个行向量，代表了原始的计算被拍平成了在 R1CS 约束下的四个电路门。到了这一步，我们的原问题”我们知道原始计算的一个解“就转化成了，“我们知道一个解向量，使得它在每个电路约束下都成立”。我们用 S 来表示解向量，本例中 S 的值如下所示。

1 3 35 9 27 30

此时，如果我们想证明我们知道原始计算的一个解，那么就需要证明 A，B，C 矩阵中的每个行向量与解向量 S 的内积之后的值是符合 R1CS 约束的(A_i,B_i,C_i 表示矩阵中的行向量)：

(A_i*S)* (B_i*S) - C_i*S = 0

在接下来的一步，我们需要将 R1CS 的约束转换成一个 QAP 问题。我觉得原文中没有提到的一点时，我们为什么要这么做的？这样的转换目的是什么？V 神的原文只描述了这一步骤的目标是把向量的内积计算转化为多项式的形式，以及如何进行拉普拉斯插值求多项式。所以第一次读到这里的时候，我感觉一头雾水。

这一过程是理解包括 Groth16 在内的所有 ZK-Proof System 的重点。这里阐述一下我的理解。这样做的原因是，如果只使用 R1CS 的约束矩阵来验证，我们只能一个电路门，一个电路门的，使用列向量与解向量的内积来验证是否满足 R1CS 的约束。这样在方式在大规模电路下（几十万，上百万的电路门）显然是十分低效的。

那么接下来的自然思考方向就变成了，存不存在一种办法，可以让我们通过一次/个计算来验证所有约束的正确性？

((1 * A_1(x))+(3 * A_2(x))+(35 * A_3(x)) + (9 * A_4(x)) +(27 * A_5(x))+(30 * A_6(x))) \\ *（(1 * B_1(x)+(3 * B_2(x))+(35 * B_3(x)) + (9 * B_4(x)) +(27 * B_5(x))+(30 * B_6(x))) \\ - （(1 * C_1(x)+(3 * C_2(x))+(35 * C_3(x)) + (9 * C_4(x)) +(27 * C_5(x))+(30 * C_6(x)))

当 x 取 1 时，上面的多项式就等于验证第一个门电路是否满足 R1CS 约束；当 x 取 2 时，上面的多项式就等于验证第二个门电路是否满足 R1CS 约束。以此类推。现在我们已经将实际的值转换成了多项式，根据 x 的取值的不同，来描述不同的 R1CS 约束。

那么，更进一步的来说，因为上面的式子中都是多项式，我们可以把等式左边展开成一个更简洁的多项式 p(x) :

p(x) = (-5.166*x^3+38.5*x^2-73.333*x+43)*(0.666*x^3-5.0*x^2+10.333*x-3.0)-(2.833*x^3-24.5*x^2+10.333*x-41.0)\\ = -3.440556*x^6+51.471*x^5-294.720056*x^4+805.7885*x^3-1063.749889*x^2+592.652*x-88

同时我们需要让等式右边的值等于 0。因此，我们就可以先构造一个多项式 t(x)=(x-1)(x-2)(x-3)(x-4) 。显然 t(x)

在 x 的取值为[1，2，3，4]值情况下都等于 0。在本例中，显然 t(x) 是不等于 t(x) （多项式的阶不同），所以我们引入另一个多项式 h(x) ，使得 p(x)=t(x)h(x) 。

这一步的操作中蕴含了一个数学引理: Schwartz–Zippel lemma[5]。感兴趣的读者可以深入了解一下这个引理。

这样我们就实现了用一个多项式来描述所有的 R1CS 的约束了。我们可以设置 x 值取 1，2，3，4，来验证对应的电路的 R1CS 约束是不是合法。在实际问题上，x 的取值远不止范围 1，2，3，4 四个值。

这一步就是文章中从 QAP 到 PCP(Probabilistic Checkable Proofs)这一步. 目前这部分主要是通过 KCA(Knowledge of Coefficient Test and Assumption)来实现的。Groth16 中，我们需要对多项式(电路)建立 Common Reference String(CRS)，来保证 non-interactive。这也就是我们常常听到的 Trusted Setup。Trusted Setup 带了不少负面效果。一旦 Trusted Setup 时的信息发生了泄漏，整个的 Proof System 的安全性保证也就不存在了。同时在 Groth16 中，我们需要对每个多项式都进行 Trusted Setup 的。换句话说，我们需要对每个计算电路都要进行一次的 Trusted Setup，这对于图灵完备的通用计算来说成本是非常高的。这也是为什么目前只有 ZCash 可以良好的运行 ZK-SNARKs，而很少见到在 General-Purpose Blockchain 中使用 ZK-SNARKs 相关技术的原因之一。

为了解决这方面的问题，研究人员提出了BulletProofs[6]。BulletProofs 将 Groth16 中的多项式证明的部分升级成了基于 Inner production-base Polynomial Commitment Scheme。在 BulletProofs 中，多项式的验证不再需要 Trusted Setup，但是需要更大的 Proof Size。

另一方面，研究人员提出了 Plonk 协议，这是另一种证明体系。在 Plonk 中的电路约束不再是 R1CS 的形式，并且引入了[KZG(KATE Commitment)](https://www.youtube.com/watch?v=W1E2CI_u6d0 "KZG(KATE Commitment "KZG(KATE Commitment)")")作为 Polynomial Commitment Scheme。在 Plonk 体系中，只需要一次的 Trusted Setup，就可以给多个多项式进行验证。目前，基于 zk-rollup 技术的 Layer-2 解决方案 ZKSync 就是基于 Plonk 协议开发的。

关于 Plonk，PCS 的技术在本篇中不做详解。感兴趣的读者可以搜索相关的关键词进行学习。

Thanks to Zhang Ye, Peng Jingshu for review.

References

Bulletproofs: Short Proofs for Confidential Transactions and More, [link][7]
Schwartz–Zippel lemma, [link][8]
Quadratic Arithmetic Programs: from Zero to Hero, [link][9]
Kate Commitments: A Primer, [link][10]
Constant-Size Commitments to Polynomials and Their Applications, [link][11]
Understanding PLONK, [link][12]

参考资料

[1]

hsyodyssey: https://learnblockchain.cn/people/6574

[2]

文章: https://vitalik.ca/general/2016/12/10/qap.html

[3]

密码学: https://learnblockchain.cn/article/798

[4]

博客: https://vitalik.ca/general/2016/12/10/qap.html

[5]

Schwartz–Zippel lemma: https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

[6]

BulletProofs: https://crypto.stanford.edu/bulletproofs/

[7]

[link]: https://crypto.stanford.edu/bulletproofs/

[8]

[link]: https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

[9]

[link]: https://vitalik.ca/general/2016/12/10/qap.html

[10]

[link]: https://hackmd.io/@tompocock/Hk2A7BD6U

[11]

[link]: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf

[12]

[link]: https://vitalik.ca/general/2019/09/22/plonk.html

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-04-24，如有侵权请联系 cloudcommunity@tencent.com 删除

https

网络安全

node.js

html

本文分享自深入浅出区块链技术微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度