3.4　libsnark开源实践简介

libsnark是目前实现zk-SNARKs电路最重要的框架，在众多私密交易或隐私计算相关项目间广泛应用，其中最著名当然要数Zcash。Zcash在Sapling版本升级前一直使用libsnark来实现电路（之后才替换为bellman）。毫不夸张地说，libsnark支撑并促进了zk-SNARKs技术的首次大规模应用，填补了零知识证明技术从最新理论到工程实现间的空缺。

libsnark是用于开发zk-SNARKs应用的C++代码库，由SCIPR Lab开发并维护。libsnark工程实现背后的理论基础是近年来（尤其是2013年以来）零知识证明特别是zk-SNARKs方向的一系列重要论文。

从Github上可以看到这个项目的主要开发者，如：

• 马达斯·维嘉（Madars Virza）
• 霍华德·吴（Howard Wu）
• 伊兰·特鲁莫（Eran Tromer）

他们大多都是这个领域内顶尖的学者或研究牛人。扎实的理论基础和工程能力，让libsnark的作者们能够化繁为简，将论文中的高深理论和复杂公式逐一实现，高度工程化地抽象出简洁的接口供广大开发者方便地调用。

libsnark的模块总览如图3-11所示，摘自libsnark代码贡献量第一作者马达斯·维嘉在MIT的博士论文。

图3-11　libsnark的模块总览图

libsnark框架提供了多个通用证明系统的实现，其中使用较多的是BCTV14a和Groth16。

查看libsnark/libsnark/zk_proof_systems路径，就能发现libsnark对各种证明系统的具体实现，并且均按不同类别进行了分类，还附上了实现依照的具体论文。

其中，zk_proof_systems/ppzksnark/r1cs_ppzksnark对应的是BCTV14a，zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark对应的是Groth16。

ppzksnark是指preprocessing zkSNARK。这里的pp/preprocessing其实就是指我们常说的trusted setup，即在证明生成和验证之前，需要通过一个生成算法来创建相关的公共参数（proving key和verification key）。我们也把这个提前生成的参数称为“公共参考串“（Common Reference String），或简称为CRS。

基本原理与步骤

使用libsnark库进行开发zk-SNARKs应用，从原理上可简要概括为主要4个步骤：

（1）将待证明的命题表达为R1CS（Rank One Constraint System）；

（2）使用生成算法（G）为该命题生成公共参数；

（3）使用证明算法（P）生成R1CS可满足性的证明；

（4）使用验证算法（V）来验证证明。

R1CS是一种表示计算的方法，使其能够满足零知识证明。基本上任何计算都可以简化（或平铺）为一个R1CS。例如向量w上的一个秩为1的约束被定义为

第一步：我们需要将函数C（x, out）在libsnark中进行表达。此处先省略，后面介绍详细过程。

第二步：对应下面的Generator函数G，lambda为随机产生，也就是常说的trusted setup过程中产生的“toxic waste”。人们喜欢称它为“有毒废物”，是因为它必须被妥善处理（如必须销毁，不能让任何人知道），否则会影响证明协议安全。

     lambda <- random（）
（pk, vk） = G（C, lambda）

最终生成proving key（pk）和verification key（vk）。

第三步：对应使用Prove函数（P）生成证明。这里想证明的是prover知道一个秘密值x和计算结果out 可使等式满足。因此将x、out还有pk 作为输入一起传给P，最终生成证明proof。

     proof = P（pk, out, x）

第四步：对应使用Verify函数（V）验证证明，将proof、out还有vk 传给G，即可在不暴露秘密的情况下证明存在一个秘密值可使等式满足。

     V（vk, out, proof） ?= true

而开发者主要工作量就集中在第一步，需要按照libsnark的接口规则手写C++电路代码来描述命题，由代码构造R1CS约束。整个过程也就对应图3-12的计算（Computation）→算法电路（Arithmetic Circuit）→R1CS。

图3-12　电路代码过程图

具体的例子，可参见如下两个项目：

• https://github.com/howardwu/libsnark-tutorial
• https://github.com/christianlundkvist/libsnark-tutorial

根据霍华德·吴（libsnark作者之一）的libsnark_tutorial，run_r1cs_gg_ppzksnark（）是主要部分。很容易发现，真正起作用的实质代码只有下面5行。

我们从“超长”的函数名上能直观地看出每一步是在做什么，但是却看不到如何构造电路的细节。实际上这里仅仅是调用了自带的r1cs_example，隐去了实现细节。

下面通过一个更直观的例子来学习电路细节。研究src/test.cpp，这个例子改编自克里斯汀·伦德伟（Christian Lundkvist）的libsnark-tutorial。

代码开头仅引用了三个头文件：

前面提到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（）;

接下来就需要明确“待证命题“是什么。这里不妨沿用之前的例子，证明秘密x满足等式x3 + x + 5 == out。这实际也是维塔利（Vitalik）博客文章 Quadratic Arithmetic Programs: from Zero to Hero中用的例子。如果对下面的变化陌生，可尝试阅读该文章。

通过引入中间变量sym_1、y、sym_2将x3 + x + 5 = out扁平化为若干个二次方程式，几个只涉及简单乘法或加法的式子，对应到算术电路中就是乘法门和加法门。你可以很容易地在纸上画出对应的电路。

     x * x = sym_1
sym_1 * x = y
y + x = sym_2
sym_2 + 5 = out

通常文章到这里便会顺着介绍如何按照R1CS的形式编排上面几个等式，并一步步推导出具体对应的向量。这对理解如何把Gate转换为R1CS有帮助，然而却不是本书的核心目的。所以此处省略这些内容。

下面定义与命题相关的变量。首先创建的protoboard是libsnark中的一个重要概念，顾名思义就是“原型板”或者“面包板”，用来快速搭建电路，在zk-SNARKs电路中则是用来关联所有变量、组件和约束。接下来的代码定义了所有需要外部输入的变量以及中间变量。

下面将各个变量与protoboard连接，相当于把各个元器件插到“面包板”上。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）;

注意，此处第一个与pb连接的是out变量。我们知道zk-SNARKs中有public input和private witness的概念，分别对应libsnark中的primary和auxiliary变量。那么如何在代码中进行区分呢？我们需要借助set_input_sizes（n）来声明与protoboard连接的public/primary变量的个数n。在这里n = 1，表明与pb连接的前n = 1个变量属性是public，其余变量的属性都是private。

至此，所有变量都已经顺利与protoboard相连，下面需要确定的是这些变量间的约束关系。这个也很好理解，类似元器件插至面包板后，需要根据电路需求确定它们之间的关系再连线焊接。如下调用protoboard的add_r1cs_constraint（）函数，为pb添加形如a * b = c的r1cs_constraint，即r1cs_constraint（a, b, c）中参数应该满足a * b = c。根据注释，不难理解每个等式和约束之间的关系。

至此，变量间的约束添加完成，针对命题的电路构建完毕。下面进入前文提到的“4个步骤”中的第二步：使用生成算法（G）为该命题生成公共参数（pk和vk），即trusted setup。生成出来的proving key和verification key分别可以通过keypair.pk和keypair.vk获得。

进入第三步，生成证明。先为public input以及witness提供具体数值。不难发现，x = 3, out = 35是原始方程的一个解，则依次为x、out以及各个中间变量赋值。

再把public input以及witness的数值传给prover函数进行证明，可分别通过pb.primary_input（）和pb.auxiliary_input（）访问。生成的证明用proof变量保存。

    const r1cs_gg_ppzksnark_proof<default_r1cs_gg_ppzksnark_pp> proof
= r1cs_gg_ppzksnark_prover<default_r1cs_gg_ppzksnark_pp>(keypair.pk,
pb.primary_input(), pb.auxiliary_input());

最后我们使用verifier函数校验证明。如果verified = true则说明证明验证成功。

    bool verified = r1cs_gg_ppzksnark_verifier_strong_IC<default_r1cs_gg_
ppzksnark_pp>（keypair.vk, pb.primary_input（）, proof）;

从日志输出中可以看出验证结果为true，R1CS约束数量为4，public input和private input数量分别为1和4。日志输出符合预期。

实际应用中，trusted setup、prove、verify会由不同角色分别开展，最终实现的效果就是prover给verifier一段简短的proof和public input，verifier可以自行校验某命题是否成立。对于前面的例子，就是能在不知道方程的解x具体是多少的情况下，验证prover知道一个秘密的x可以使得x3 + x + 5 = out成立。

通过上面短短的几十行代码，就已经使用了zk-SNARKs。

使用它进行实战，我们可以参见安比实验室的开源代码示例：https://github.com/secbit/libsnark_abc。