如何在zkSNARK中构造电路

Question

我有几个关于如何使用zk的问题。因为使用的基本逻辑是：

1. 用电路来表示问题，
2. 从电路中产生一个R1CS，
3. 将R1CS转换为QAP，然后我们可以运行zk-snark。

对于第一部分，该问题是否有特定的定义或特征，所有可以验证的问题都能转化为电路，并使用zk生成证明吗？此外，如何通过编程或使用数学方法将问题简化为一个电路？

Answer 1

对于这个问题是否有任何具体的定义或特征，所有可以验证的问题都可以转换成电路，并使用zk生成证明吗？

问题应该在NP类NP类中。NP问题是存在一种有效的算法，它可以在多项式时间内判定或证明S的陈述(他们的陈述)是否成立，许多zkSNARK都是基于电路可满足性问题的。电路可满足性是一个NP-完全问题.有两种类型的电路:布尔电路和算术电路，可以相互转换。粗略地说，我们可以为所有算法设计电路(例如。我们可以在电脑上运行。下面的图片是一个简单的布尔电路，由电线和逻辑门(和，或和不)组成。在一个基于这个简单电路的zkSNARK系统中，验证者想让验证者相信他知道输入(x_1 = 1，x_2 = 1，x_3= 0)，对于这些输入，电路的输出是真的，换句话说，他知道满足这个电路的输入。

如何通过编程或使用数学方法将问题压平成电路？

在将NP问题转换为(布尔或算术)电路后，您应该将该电路转换为R1CS这样的SNARK友好格式。有一些编译器可以用高级编程语言编写问题，并将问题编译成R1CS格式，例如，您可以使用ZoKrates，Ethereum上的zkSNARKs工具箱，也可以使用利布斯纳克的S小工具库。

Answer 2

为了回答你的第一个问题，问题的特点通常来自NP类，在NP类中，你在不确定多项式(NP)时间内进行计算，但是验证计算所需的时间应该小于或等于多项式时间。

我们处理ZK的问题之一是证明需要NP时间但验证该证明所需的时间小于或等于多项式时间的语句。您可以证明“我使用我的私钥签署了这个事务”，验证器可以使用公共输入(事务和公钥)进行验证。您可以创建电路，例如，ECDSA生成提供签名真实性的证据的ECDSA，或证明包含数据的Merkle树电路。

为了回答你的第二个问题，理论上，你可以为可以转换成代数方程的语句建立电路。我们编写的每一种算法都可以转化为一个电路，其中算法的每一步都受到约束(必须满足约束条件才能产生有效的证明)。有一些数学思想来创建电路是很有用的，特别是当你用Circom这样的语言编程时。而在另一个用于电路编程的DSL Noir中，您只需要声明约束(a+b-c == 0)来创建约束。其他每一件事都与正常编程相同。但是Noir仍然缺乏一些功能，因为现在还太早。您也可以使用锈蚀，因为一些验证系统，如Halo2在锈蚀，但您需要处理样板。