技术干货 | 零知识证明Learn by Coding:libsnark 入门篇
1、zk-SNARKs 和 libsnark 背景简介
零知识证明,可能是目前最具应用前景和想象力的密码学黑科技。而 zk-SNARKs 正是一类零知识证明方案的简称,全称为 Zero-Knowledge Succinct Non-interactive Arguments of Knowledge。这一名字几乎包含了其所有技术特征,即可以在不泄露任何其他信息的前提下证明一个命题的正确性,并且最终生成的证明具有简洁性(Succinct),也就是说最终生成的证明足够小,并且与计算量大小无关,是一个常数。用白话说就是,你理论上可以在不暴露任何隐私的情况下向其他所有人证明某件事,并且生成的证明体积很小,校验成本很低,与需要证明的内容计算量无关。听起来简直太美好了!
zk-SNARKs 能应用到很多场景,比如隐私保护、区块链扩容、可验证计算等。本文不介绍 zk-SNARKS 和零知识证明的理论细节,不熟悉或想深入了解的同学可阅读其他文章或论文。
如 Vitalik 写的关于 zk-SNARKs 著名的三篇博文。
-
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649 -
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627 -
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
- 「深入浅出零知识证明之zk-SNARKs」:https://www.yuque.com/u428635/scg32w/edmn74
- 「浅谈零知识证明之二: 简短无交互证明(SNARK)」:https://mp.weixin.qq.com/s/623bceLkCjgtFHB6W3D0oA
- 「探索零知识证明」系列:https://sec-bit.github.io/blog/2019/07/31/zero-knowledge-and-proof/
- 「从零开始学习 zk-SNARK」系列:https://sec-bit.github.io/blog/2019/12/25/learn-zk-snark-from-zero-part-one/
- 「零知识证明学习资源汇总」:https://sec-bit.github.io/blog/2019/11/07/zkp-learning-resources/
-
[GGPR13] Quadratic span programs and succinct NIZKs without PCPs , Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova, EUROCRYPT 2013 -
[PGHR13] Pinocchio: Nearly Practical Verifiable Computation , Bryan Parno, Craig Gentry, Jon Howell, Mariana Raykova, IEEE Symposium on Security and Privacy (Oakland) 2013 -
[BCGTV13] SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge , Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza, CRYPTO 2013 -
[BCIOP13] Succinct non-interactive arguments via linear interactive Proofs , Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth, Theory of Cryptography Conference 2013 -
[BCTV14a] Succinct non-interactive zero knowledge for a von Neumann architecture , Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, USENIX Security 2014 -
[BCTV14b] Scalable succinct non-interactive arguments via cycles of elliptic curves , Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, CRYPTO 2014 -
[Groth16] On the Size of Pairing-based Non-interactive Arguments , Jens Groth, EUROCRYPT 2016
扎实的理论基础和工程能力,让 libsnark 的作者们能够化繁为简,将形如下图的高深理论和复杂公式逐一实现,高度工程化地抽象出简洁的接口供广大开发者方便地调用。向这些将非凡的理论研究推广至更大规模应用的先锋们致敬。
下图是 libsnark 的模块总览图,摘自 libsnark 代码贡献量第一作者 Madars Virza 在 MIT 的博士论文(https://madars.org/phd-thesis/)。
libsnark 框架提供了多个通用证明系统的实现,其中使用较多的是 BCTV14a 和 Groth16。
查看 libsnark/libsnark/zk_proof_systems 路径,就能发现 libsnark 对各种证明系统的具体实现,并且均按不同类别进行了分类,还附上了实现依照的具体论文。
其中:
-
zk_proof_systems/ppzksnark/r1cs_ppzksnark 对应的是 BCTV14a -
zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark 对应的是 Groth16
2、基本原理与步骤
利用 libsnark 库开发 zk-SNARKs 应用从原理上可简要概括为以下四个步骤:
-
将待证明的命题表达为 R1CS (Rank One Constraint System) -
使用生成算法( G )为该命题生成公共参数 -
使用证明算法( P )生成 R1CS 可满足性的证明 -
使用验证算法( V )来验证证明
有这样一个函数 C(x, out),用于判断秘密 x 是否满足等式 x^3 + x + 5 == out,若满足则返回 true。
function C(x, out) {
return ( x^3 + x + 5 == out );
}
lambda <- random()
(pk, vk) = G(C, lambda)
proof = P(pk, out, x)
V(vk, out, proof) ?= true
3、搭建 zk-SNARKs 应用开发环境
下面进入动手环节,快速上手 libsnark,跑通例子。
先下载本文对应的 libsnark 最小可用例子代码库 libsnark_abc。
git clone https://github.com/sec-bit/libsnark_abc.git
通过 git submodule 拉取 libsnark 代码。
cd libsnark_abc
git submodule update --init --recursive
sudo apt-get install build-essential cmake git libgmp3-dev libprocps4-dev python-markdown libboost-all-dev libssl-dev
mkdir build && cd build && cmake ..
mkdir build && cd build && CPPFLAGS=-I/usr/local/opt/openssl/include LDFLAGS=-L/usr/local/opt/openssl/lib PKG_CONFIG_PATH=/usr/local/opt/openssl/lib/pkgconfig cmake -DWITH_PROCPS=OFF -DWITH_SUPERCOP=OFF ..
make
main
range
test
./src/main
最终出现如下日志,则说明一切正常。
你已顺利拥有了 zkSNARK 应用开发环境,并成功跑了第一个 zk-SNARKs 的 demo
。
4、理解示例代码
下面我们一起来仔细瞅瞅代码。示例项目包含了 3 份代码(也可查看文末附录)。
r1cs_gg_ppzksnark_keypair<ppT> keypair = r1cs_gg_ppzksnark_generator<ppT>(example.constraint_system);
r1cs_gg_ppzksnark_processed_verification_key<ppT> pvk = r1cs_gg_ppzksnark_verifier_process_vk<ppT>(keypair.vk);
r1cs_gg_ppzksnark_proof<ppT> proof = r1cs_gg_ppzksnark_prover<ppT>(keypair.pk, example.primary_input, example.auxiliary_input);
const bool ans = r1cs_gg_ppzksnark_verifier_strong_IC<ppT>(keypair.vk, example.primary_input, proof);
const bool ans2 = r1cs_gg_ppzksnark_online_verifier_strong_IC<ppT>(pvk, example.primary_input, proof);
仅从“超长”的函数名就能看出来每步是在做什么,但是却看不到如何构造电路的细节。实际上这里仅仅是调用了自带的 r1cs_example,隐去了实现细节。
既然如此, 那让我们通过一个更直观的例子来学习电路细节 。研究 src/test.cpp,这个例子改编自 Christian Lundkvist 的 libsnark-tutorial(https://github.com/christianlundkvist/libsnark-tutorial)。
代码开头仅引用了三个头文件,分别是:
#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();
接下来就需要明确「待证命题」是什么。这里不妨沿用之前的例子,证明秘密 x 满足等式 x^3 + x + 5 == out。这实际也是 Vitalik 博文 "Quadratic Arithmetic Programs: from Zero to Hero"(https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) 中用的例子。如果对下面的变化陌生,可尝试阅读该博文。
通过引入中间变量 sym_1、y、sym_2 将 x^3 + x + 5 = out 扁平化为若干个二次方程式,几个只涉及简单乘法或加法的式子,对应到算术电路中就是乘法门和加法门。你可以很容易地在纸上画出对应的电路。
x * x = sym_1
sym_1 * x = y
y + x = sym_2
sym_2 + 5 = out
// Create protoboard
protoboard<FieldT> pb;
// Define variables
pb_variable<FieldT> x;
pb_variable<FieldT> sym_1;
pb_variable<FieldT> y;
pb_variable<FieldT> sym_2;
pb_variable<FieldT> out;
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);
// x*x = sym_1
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(x, x, sym_1));
// sym_1 * x = y
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(sym_1, x, y));
// y + x = sym_2
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(y + x, 1, sym_2));
// sym_2 + 5 = ~out
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(sym_2 + 5, 1, out));
const r1cs_constraint_system<FieldT> constraint_system = pb.get_constraint_system();
const r1cs_gg_ppzksnark_keypair<default_r1cs_gg_ppzksnark_pp> keypair = r1cs_gg_ppzksnark_generator<default_r1cs_gg_ppzksnark_pp>(constraint_system);
pb.val(out) = 35;
pb.val(x) = 3;
pb.val(sym_1) = 9;
pb.val(y) = 27;
pb.val(sym_2) = 30;
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());
bool verified = r1cs_gg_ppzksnark_verifier_strong_IC<default_r1cs_gg_ppzksnark_pp>(keypair.vk, pb.primary_input(), proof);
5、再次上手实践
经过上面的例子,我们已经了解了利用 libsnark 库开发 zk-SNARKs 电路的所有重要步骤。
现在不妨用新的例子来巩固一下: 在不泄露秘密数字大小的前提下,证明数字小于 60 。
这个在常规程序里用一个运算符就能完成的事情,在 libsnark 下面应该如何表示呢?
zk-SNARKs 电路开发的主要工作量和难点在于如何用代码“精确”地描述命题中的所有约束。一旦描述不“精确”,则要么是漏掉约束、要么是写错约束,最终电路想要证明的内容则会与原命题相差甚远。上一节的例子只涉及简单的乘法和加法,与 r1cs_constraint 最基本的形式一致,因此约束的表达相对容易。除此之外几乎所有的约束都不是很直观,作为初学者很难正确地描述约束细节。
幸好 libsnark 已经为我们实现了大量基础电路小组件。gadgetlib1 和 gadgetlib2 下提供了许多可以直接使用的 gadget。其中 gadgetlib1 更常用一些,里面收集了包括 sha256 在内的 hash 计算、merkle tree、pairing 等电路实现。
DangDangDang ,gadgetlib1/gadgets/basic_gadgets.hpp 中的 comparison_gadget 正是我们所需。
comparison_gadget(protoboard<FieldT>& pb,
const size_t n,
const pb_linear_combination<FieldT> &A,
const pb_linear_combination<FieldT> &B,
const pb_variable<FieldT> &less,
const pb_variable<FieldT> &less_or_eq,
const std::string &annotation_prefix="")
protoboard<FieldT> pb;
pb_variable<FieldT> x, max;
pb_variable<FieldT> less, less_or_eq;
x.allocate(pb, "x");
max.allocate(pb, "max");
pb.val(max)= 60;
comparison_gadget<FieldT> cmp(pb, 10, x, max, less, less_or_eq, "cmp");
cmp.generate_r1cs_constraints();
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(less, 1, FieldT::one()));
// Add witness values
pb.val(x) = 18; // secret
cmp.generate_r1cs_witness();
6、What's NEXT?
读到这里,相信大家都对 libsnark 的使用方法和 zk-SNARKs 电路开发有了一个初步的了解。
你或许已经发现,libsnark 的使用方法较简单,而真正的重点在于 zk-SNARKs 电路开发。正如前面提过的,必须用代码“精确”描述待证命题中的所有约束,“漏掉”或“写错”约束都会让证明内容与原本意图大相径庭,从而导致证明无意义。
如何正确高效地把真实业务逻辑转化为 zk-SNARKs 电路代码,这正是我们开发者需要不断研究和练习的。
好在我们已经有了一个 libsnark 试验场,可以很方便地自由修改、添加代码来尝试。
不论多复杂的电路实现,都是通过一个个更简单地「电路组件」组合封装而形成。因此 libsnark 自带的基础库是一个非常重要的学习资料——既要学习它们的使用方法,又要研究其实现原理。
我们也能通过阅读其他项目的电路实现来了解如何将 ZKP 应用到实际业务中,如 HarryR 的 ethsnarks-miximus(https://github.com/HarryR/ethsnarks-miximus) 和 Loopring 的 protocol3-circuits(https://github.com/Loopring/protocol3-circuits)。从这些项目中可以学习到如何工程化地开发更大规模的电路,以及与电路性能相关的各种设计优化细节,同时对电路约束规模会有更深刻的理解。
同时也欢迎大家继续关注安比实验室「零知识证明 Learn by Coding:libsnark 系列」后续文章,下次我们将尝试从 zk-SNARKs 与智能合约的结合、电路模块化开发、更复杂的 libsnark 实现案例、电路开发过程中容易踩的坑等角度来进一步讨论。
7、附录
main.cpp
#include <libff/common/default_types/ec_pp.hpp>
#include <libsnark/common/default_types/r1cs_gg_ppzksnark_pp.hpp>
#include <libsnark/relations/constraint_satisfaction_problems/r1cs/examples/r1cs_examples.hpp>
#include <libsnark/zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/r1cs_gg_ppzksnark.hpp>
using namespace libsnark;
/**
* The code below provides an example of all stages of running a R1CS GG-ppzkSNARK.
*
* Of course, in a real-life scenario, we would have three distinct entities,
* mangled into one in the demonstration below. The three entities are as follows.
* (1) The "generator", which runs the ppzkSNARK generator on input a given
* constraint system CS to create a proving and a verification key for CS.
* (2) The "prover", which runs the ppzkSNARK prover on input the proving key,
* a primary input for CS, and an auxiliary input for CS.
* (3) The "verifier", which runs the ppzkSNARK verifier on input the verification key,
* a primary input for CS, and a proof.
*/
template<typename ppT>
bool run_r1cs_gg_ppzksnark(const r1cs_example<libff::Fr<ppT> > &example)
{
libff::print_header("R1CS GG-ppzkSNARK Generator");
r1cs_gg_ppzksnark_keypair<ppT> keypair = r1cs_gg_ppzksnark_generator<ppT>(example.constraint_system);
printf("\n"); libff::print_indent(); libff::print_mem("after generator");
libff::print_header("Preprocess verification key");
r1cs_gg_ppzksnark_processed_verification_key<ppT> pvk = r1cs_gg_ppzksnark_verifier_process_vk<ppT>(keypair.vk);
libff::print_header("R1CS GG-ppzkSNARK Prover");
r1cs_gg_ppzksnark_proof<ppT> proof = r1cs_gg_ppzksnark_prover<ppT>(keypair.pk, example.primary_input, example.auxiliary_input);
printf("\n"); libff::print_indent(); libff::print_mem("after prover");
libff::print_header("R1CS GG-ppzkSNARK Verifier");
const bool ans = r1cs_gg_ppzksnark_verifier_strong_IC<ppT>(keypair.vk, example.primary_input, proof);
printf("\n"); libff::print_indent(); libff::print_mem("after verifier");
printf("* The verification result is: %s\n", (ans ? "PASS" : "FAIL"));
libff::print_header("R1CS GG-ppzkSNARK Online Verifier");
const bool ans2 = r1cs_gg_ppzksnark_online_verifier_strong_IC<ppT>(pvk, example.primary_input, proof);
assert(ans == ans2);
return ans;
}
template<typename ppT>
void test_r1cs_gg_ppzksnark(size_t num_constraints, size_t input_size)
{
r1cs_example<libff::Fr<ppT> > example = generate_r1cs_example_with_binary_input<libff::Fr<ppT> >(num_constraints, input_size);
const bool bit = run_r1cs_gg_ppzksnark<ppT>(example);
assert(bit);
}
int main () {
default_r1cs_gg_ppzksnark_pp::init_public_params();
test_r1cs_gg_ppzksnark<default_r1cs_gg_ppzksnark_pp>(1000, 100);
return 0;
}
#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>
using namespace libsnark;
using namespace std;
int main () {
typedef libff::Fr<default_r1cs_gg_ppzksnark_pp> FieldT;
// Initialize the curve parameters
default_r1cs_gg_ppzksnark_pp::init_public_params();
// Create protoboard
protoboard<FieldT> pb;
// Define variables
pb_variable<FieldT> x;
pb_variable<FieldT> sym_1;
pb_variable<FieldT> y;
pb_variable<FieldT> sym_2;
pb_variable<FieldT> out;
// Allocate variables to protoboard
// The strings (like "x") are only for debugging purposes
out.allocate(pb, "out");
x.allocate(pb, "x");
sym_1.allocate(pb, "sym_1");
y.allocate(pb, "y");
sym_2.allocate(pb, "sym_2");
// This sets up the protoboard variables
// so that the first one (out) represents the public
// input and the rest is private input
pb.set_input_sizes(1);
// Add R1CS constraints to protoboard
// x*x = sym_1
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(x, x, sym_1));
// sym_1 * x = y
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(sym_1, x, y));
// y + x = sym_2
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(y + x, 1, sym_2));
// sym_2 + 5 = ~out
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(sym_2 + 5, 1, out));
const r1cs_constraint_system<FieldT> constraint_system = pb.get_constraint_system();
// generate keypair
const r1cs_gg_ppzksnark_keypair<default_r1cs_gg_ppzksnark_pp> keypair = r1cs_gg_ppzksnark_generator<default_r1cs_gg_ppzksnark_pp>(constraint_system);
// Add public input and witness values
pb.val(out) = 35;
pb.val(x) = 3;
pb.val(sym_1) = 9;
pb.val(y) = 27;
pb.val(sym_2) = 30;
// generate 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());
// verify
bool verified = r1cs_gg_ppzksnark_verifier_strong_IC<default_r1cs_gg_ppzksnark_pp>(keypair.vk, pb.primary_input(), proof);
cout << "Number of R1CS constraints: " << constraint_system.num_constraints() << endl;
cout << "Primary (public) input: " << pb.primary_input() << endl;
cout << "Auxiliary (private) input: " << pb.auxiliary_input() << endl;
cout << "Verification status: " << verified << endl;
}
#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>
#include <libsnark/gadgetlib1/gadgets/basic_gadgets.hpp>
using namespace libsnark;
using namespace std;
int main () {
typedef libff::Fr<default_r1cs_gg_ppzksnark_pp> FieldT;
// Initialize the curve parameters
default_r1cs_gg_ppzksnark_pp::init_public_params();
// Create protoboard
protoboard<FieldT> pb;
pb_variable<FieldT> x, max;
pb_variable<FieldT> less, less_or_eq;
x.allocate(pb, "x");
max.allocate(pb, "max");
pb.val(max)= 60;
comparison_gadget<FieldT> cmp(pb, 10, x, max, less, less_or_eq, "cmp");
cmp.generate_r1cs_constraints();
pb.add_r1cs_constraint(r1cs_constraint<FieldT>(less, 1, FieldT::one()));
const r1cs_constraint_system<FieldT> constraint_system = pb.get_constraint_system();
// generate keypair
const r1cs_gg_ppzksnark_keypair<default_r1cs_gg_ppzksnark_pp> keypair = r1cs_gg_ppzksnark_generator<default_r1cs_gg_ppzksnark_pp>(constraint_system);
// Add witness values
pb.val(x) = 18; // secret
cmp.generate_r1cs_witness();
// generate 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());
// verify
bool verified = r1cs_gg_ppzksnark_verifier_strong_IC<default_r1cs_gg_ppzksnark_pp>(keypair.vk, pb.primary_input(), proof);
cout << "Number of R1CS constraints: " << constraint_system.num_constraints() << endl;
cout << "Primary (public) input: " << pb.primary_input() << endl;
cout << "Auxiliary (private) input: " << pb.auxiliary_input() << endl;
cout << "Verification status: " << verified << endl;
}