围炉网

一行代码,一篇日志,一个梦想,一个世界

零知识证明读书笔记

  • SNARK stands for Succinct, Non-interactive, ARguments of Knowledge

  • 电路一般采用R1CS语言描述,R1CS相对来说非常直观,A*B=C (A/B/C分别是输入变量的线性组合)。但是要应用Groth16算法,需要将R1CS描述的电路,转化为QAP描述。两种电路描述语言的转化,称为Reduction

    • 在创建任何证明之前,我们需要计算与(所有)电路约束匹配的所有电路信号。snarkjs会帮我们计算这些。我们需要提供一个包含输入的文件,它将执行电路并计算所有中间信号和输出。这组信号就是“见证”。零知识证明证明你知道一组与所有约束匹配的信号(见证),但不透露任何信号(公共输入和输出除外)。

    • 见证(witness)对验证者是保密的。 证明人仅使用它生成证明,证明她知道见证中包含的一组信号(包括私有信号)。

  • R1CS(rank-1 constraint system,一阶约束系统)。

    • R1CS 是一个由三向量组 (a,b,c) 组成的序列,R1CS 有个解向量 s,s 必须满足,符号表示向量的内积运算。这里的解向量 s 就是 witness。

  • QAP

    • 使用多项式来代替点积运算,可以将任何计算问题转化为多项式等式形式,这样可以更容易验证数学欺骗。

  • 如果有上百亿个门,可能验证要花不止一年的时间。有没有一种办法把这么多门的验证过程变的简单?

    • 用「多项式编码」这个数学工具可以做到这一点。

    • 比如说有一些数:y0、y1、y2,我们把他们放到一个 XY 轴平面上,变成一个个的点,然后找到一根曲线恰好通过那些点,相当于用一根曲线编码了所有的数值,从 y0 到 yn。

  • 编码成曲线有什么好处呢?

    • 好处是如果我想改其中某一个值 yk,哪怕只要改动一点点,整条曲线就会发生明显的扰动。扰动后的曲线和原曲线只在 n 个点处相同,而其它的点都产生了偏离。多项式编码之后能放大任何一个哪怕微小的修改。于是我们可以通过随机验证一个点,就能检查曲线编码的点有没有被修改过。

  • 接下来可以对刚才算术电路中所有乘法门的左输入门、右输入门、输出门做三个不同的多项式编码,形成三根曲线。现在只要有三根曲线,验证这三根曲线(三个多项式)之间满足乘法关系就够了。验证乘法关系只需要随机抽样 X 轴上的一个点均可,不需要再验证一百亿个门。虽然验证了这三根曲线,但显然验证者看到了太多的秘密,零知识证明要保证计算过程的秘密不被泄漏。怎么做?

    • 可以把多项式运算同态映射到椭圆曲线群上。

  • 整数有限域的加法运算会映射到椭圆曲线群上的二元运算。整数乘法运算可以同态映射到椭圆曲线群上的双线性配对(Pairing)操作,乘法只能是单乘法,但足可以验证算术电路的运算关系。

  • 看一下 GGPR13/Pinocchio/Groth16 框架。当我们想表达任何计算的时候,先用高级语言编写代码,然后通过 compiler 编译成算术电路,再通过矩阵表示产生 R1CS 矩阵,并通过多项式编码产生 QAP,最后通过 Trusted-Setup 产生:Proving Key、Verifying Key。用 Proving Key 可以证明计算过程,而通过 Verifying Key 就可以知道证明π是对的。

  • Powers of Tau 

    • Zcash 社区发起的一项活动,旨在解决 zkSNARK 算法中公钥生成的问题。同时,这一活动也有希望为零知识证明使用者解决可信公钥生成的问题。零知识证明 zkSNARK 算法依赖于可信的公共参数生成。在算法的初始化阶段,需要一个人从电脑里生成一些原始随机数,用这些原始随机数生成 zkSNARK 的证明公钥和验证公钥,然后把这些原始随机数删掉。如果这个原始随机数被保留下来或是被泄露,拥有原始随机数的人可以随意伪造证明、超发代币,摧毁整个系统的正确性。

    • 之前 Zcash 使用的证明公钥和验证公钥,是通过 6 台机器做多方安全运算生成的,只有把 6 台机器的原始随机数全部拿到,才能做上述那些造假的事情。机器在计算完成后立刻就在物理上进行毁坏。为什么只有 6 台机器?因为算法效率和不可扩展性只允许这个量级数量的参与者。如今,学术界找到了更好的方案,一个更高效的多方安全计算的方法。这一算法理论上允许上千人的非同步参与,生成公钥。只要有一个人安全删除了原始随机数,公钥就是安全的。为了鼓励让更多的人参与公钥生成,Zcash 社区做了名为 The Powers of Tau 的活动[4],鼓励每一个人参与,其结果被用于公钥生成。最终,在 2017 年 11 月到 2018 年 4 月期间,共有九十多人参与了这一活动,87 人成功参与。参与者主要是密码学教授和 Zcash 社区成员。其中甚至有人带着放射性物质和盖革计数器,开着螺旋桨飞机跑到天上去做计算,以防止可能的窃听或攻击。

    • 目前公钥已经生成,将被用在 Zcash 的 Sapling 更新中。同时,任何其他的业务逻辑,如果编译成 zkSNARK 输入格式后少于 200 万个乘法操作,均可复用 Powers of Tau 的中间结果。后续的使用者也可以在此基础上继续更新这一结果,然后生成自己的公钥。只要新参与者和原先的 87 个参与者加起来有一个人真的删除了原始随机数,就没人能伪造证明。可以说很大程度上缓解了 zkSNARK 的可信初始化问题,提高了 zkSNARK 的可用性。

  • 给任意一个有限域上的整数 r,我们就可以在循环群中找到一个对应的点 rG,或者用一个标量乘法来表示 r*G。但是反过来计算是很「困难」的,这是一个「密码学难题」—— 被称为离散对数难题。Schnorr 协议充分利用了有限域和循环群之间单向映射,实现了最简单的零知识证明安全协议:Alice 向 Bob 证明她拥有 PK 对应的私钥 sk。

  • libsnark代码中primary input就是statement, auxiliary input就是witness

  • pb.set_input_sizes(const size_t primary_input_size); 设置的变量位于前面的几个是公开的,其他的是witness

#include <libsnark/common/default_types/r1cs_gg_ppzksnark_pp.hpp>
#include <libsnark/zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/r1cs_gg_ppzksnark.hpp>
#include <libsnark/gadgetlib1/pb_variable.hpp>
  • 前面提到 r1cs_gg_ppzksnark 对应的是 Groth16 方案。这里加了 gg 是为了区别 r1cs_ppzksnark(也就是 BCTV14a 方案),表示 Generic Group Model(通用群模型)。Groth16 安全性证明依赖 Generic Group Model,以更强的安全假设换得了更好的性能和更短的证明。

  • 第一个头文件是为了引入 default_r1cs_gg_ppzksnark_pp 类型,第二个则为了引入证明相关的各个接口。pb_variable 则是用来定义电路相关的变量。

  • 下面需要进行一些初始化,定义使用的有限域,并初始化曲线参数。这是相当于每次的准备工作。

typedef libff::Fr<default_r1cs_gg_ppzksnark_pp> FieldT;
default_r1cs_gg_ppzksnark_pp::init_public_params();
  • 接下来就需要明确「待证命题」是什么。

  • allocate() 函数的第二个 string 类型变量仅是用来方便 DEBUG 时的注释,方便 DEBUG 时查看日志。

out.allocate(pb, "out");
x.allocate(pb, "x");
sym_1.allocate(pb, "sym_1");
y.allocate(pb, "y");
sym_2.allocate(pb, "sym_2");
pb.set_input_sizes(1);

发表评论

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

沪ICP备15009335号-2