1. 主页
  2. 文档
  3. zk-SNARKS验证教程
  4. 构建算数电路

构建算数电路

为了使 Zcash 内包含基于零知识构建的隐私体系,根据网络的共识规则确定交易有效性的函数必须返回交易是否有效的判断,并且不披露其计算执行中的任何信息,这是通过在 zk-SNARK 中编码网络共识规则来实现的。

从更高维度上来说,Zk-snarks 首先将要证明的内容转化为关于某些代数方程解的等价形式,以及如何将确定有效交易的规则转换为方程式,然后在候选解决方案上进行评估,而不会向验证方程的各方透露信息。

过程是:

“`Computation $\to$ Arithmetic Circuit $\to$ R1CS $\to$QAP$\to$zk-SNARK“`

将交易有效性函数转换为数学表示的操作如下:

第一步

将逻辑步骤分解为最小操作单元,以创建“算数电路”。

算数电路类似于布尔电路,其中程序被编译为离散的单个步骤,如 AND,OR,NOT ; 当程序转换为运算电路时,它被分解为单个步骤,包括加法,减法等基本算数运算,尽量避免使用除法。

以计算表达式 (a+b)*(b*c)的运算电路为例:
可以将输入值 a,b,c 视为在导线上从左到右“行进”到输出端。

第二步

构建所谓的 Rank1 约束系统,以检查是否“正确行进” 。

在本表达式中,R1CS将确认从 b 和 c 进入的乘法门出来的值是 b*c。在 R1CS 中,验证器必须检查诸多约束,包括每个约束电路。

2012年,Gennaro,Gentry,Parno 和 Raykova 在论文中提出了一种很好的方法来将所有的约束进行捆绑,这种方法称为 QAP ,即二次运算程序的电路表示。

多项式可能会非常大,但这是正常的,因为当多项式之间不存在同一性时,无法保证多项式大多数的点相同,因此,只需检查两个多项式在一个随机选择的点是否匹配,便可以高概率地正确验证证明。

那么会存在一个问题,即当证明者事先知道验证者选择检查的点,那么仍然可能构建无效的多项式,但满足该点,
基于 zk-SNARKS,使用诸如同态加密和椭圆曲线的配对等复杂数学技术来“盲目地”评估多项式,即不知道正在评估哪个点。

上面的公共参数用于确定将检查哪个点,但是是以加密的形式,以便证明者和验证者都不知道这个点是什么。

上述主要解决了“SNARKs”中的 “S” 和 “N” 部分,即获取剪短的,非交互式的单一消息证明,但是没有解决“zk”部分,以证明秘密数据的保密性。

在这个阶段,通过让证明者使用仍然满足所需身份的原始多项式的“随机移位”,可以很容易地满足“zk”所需的要求。

为了更深入地了解 Zcash 中包含的 Zk-SNARKs 关键思想,请关注后续的几篇文章,会一一阐述相关思想及其实现

1)同态隐藏
2)多项式盲估
3) 系数测试及假设
4)可验证的多项式盲估实现
5)从计算到多项式
6)Pinocchio 协议
7)椭圆曲线配对

See U guys later !

我们要如何帮助您?