零知识证明 – 深入理解 ZoKrates

2018 年 Jacob Eberhardt 和 Stefan Tai 两位德国柏林工业大学博士生,提出了链下计算 / 链上验证的处理框架,并提供了在以太坊上的整个框架的工具链。链下计算 / 链上验证的思想很早就有,但是能提供比较完善的工具链的实属难得。目前 ZoKrates 使用 zk-SNARK 算法实现零知识证明

本文介绍 ZoKrates 的思想,工具链的使用以及源代码导读。

链下计算 / 链上验证

传统区块链整个交易或者计算(Tx)的内容都是存储在区块链上,并且每个节点都需要执行整个交易或者计算。ZoKrates 将计算移到链下,并生成证明,链上只需要验证证明是否正确,从而确认相应的计算。链下计算 / 链上验证的方式有一些好处:1)提供隐私的能力 2)降低链上数据存储 3)减少链上的计算量。

传统的区块链和 ZoKrates 的区别如下图所示:
传统区块链和ZoKrates处理交易的区别

ZoKrates 工具链

使用 ZoKrates 工具链可以很方面地提供某种计算的证明,整个流程由如下的步骤(命令)组成:
ZoKrates工具链证明步骤

1. compile – 编译电路。对于想证明的计算,需要设计和开发电路。ZoKrates 采用 DSL(Domain Specific Language)描述电路。ZoKrates 也提供了一些常用的电路库(SHA256,椭圆曲线的计算等等)。

2. setup – 设置。对于每个电路,在生成证明之前,必须 setup 一次,生成 CRS。

3. compute-witness – 生成 witness。在提供了 private/public 输入的情况下,ZoKrates 自动根据电路计算出对应的 witness。

4. generate-proof – 生成证明信息

5. export-verifier – 导出验证工具。比如在以太坊上,export-verifier 可以导出可在以太坊上部署的证明验证合约。

从电路的 DSL 描述,最后到生成以太坊上的智能合约的流程,如下图:

DSL 电路示例

ZoKrates 给出了详细的电路描述和编译的说明,可以查看链接

如下的电路是最简单的 DSL 电路描述,判断 a 的平方是否等于 b,等于返回 1,不等于返回 0:

1
2
3
def main(private field a, field b) -> (field):
 field result = if a * a == b then 1 else 0 fi
 return result

field 是 DSL 电路的基本数据类型。一个 field 代表一个整数,范围 [0, p-1],其中 p 为大的质数。field 前面加上关键词 private,说明这个 field 的数据是 private 的,属于 “witness”。电路的描述文件以.code 为后缀。

ZoKrates 源代码导读

本文中使用的 ZoKrates 源代码的最后一个 commit 信息如下:

commit 87312a55e94055f14f95afeaa2790783d79a1ee5 Author: schaeff thibaut@schaeff.fr Date: Sun Jun 23 13:35:03 2019 +0200

remove invalid test case

整个 ZoKrates 的源代码的目录如下图:

ZoKrates源代码目录

zokrates_cli:命令行接口实现。

zokrates_fs_resolver: 文件系统解析。

zokrates_parser: .code 电路代码解析。

zokrates_pest_ast: 解析电路为 AST(Abstract Syntax Tree)。

zokrates_stdlib: 一些预实现的电路(比如,sha256 函数,pedersen hash 函数,ecc 相关计算)。

zokrates_core: zokrates 的核心逻辑代码。解析.code 电路,调用 bellman 相关接口,实现电路的生成,proof 的生成和验证。

简单的说,ZoKrates 的逻辑分为三部分:CLI 代码,电路的解析(pest/ast)以及调用 bellman 生成电路 / 证明。以下从 CLI 命令行为起点,解析逻辑相关的代码。

compile 命令

compile 命令编译.code 描述的电路:

1
./zokrates compile -i sample.code

编译的逻辑在 zokrates_core/src/compile.rs 模块的 compile_aux 函数中。

通过 zokrates_parser 模块解析.code 电路。电路程序的语法定义在 zokrates_parser/src/zokrates.pest 文件中。也就是说,电路程序使用 pest 库进行语法解析。进行语法解析后,通过 zokrates_pest_ast 模块生成 ast(语法树)。最后再通过 flatten 模块,将电路 “拍平”。最后编译后的程序,用 FlatProg 表示(定义在 zokrates_core/src/flat_absy/mod.rs):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub struct FlatProg {
 /// FlatFunctions of the program
 pub functions: Vec>,
 }
 pub struct FlatFunction {
 /// Name of the program
 pub id: String,
 /// Arguments of the function
 pub arguments: Vec,
 /// Vector of statements that are executed when running the function
 pub statements: Vec>,
 /// Typed signature
 pub signature: Signature,
 }

也就是说,一个电路程序由一个个的 FlatFunction 构成,每个 FlatFunction 中包含参数以及一系列的 FlatStatement(R1CS 表达式)。解析完成的电路程序会存放在临时文件中(当前目录下的 output 文件中)。

setup 命令

setup 命令生成 CRS。

1
./zokrates setup

ZoKrates 提供几种零知识证明的方案:PGHR13, G16 和 GM17。默认采用 G16 的方案。

核心逻辑在 zokrates_core/src/proof_system/bn128/g16.rs 的 setup 函数中。

通过 zokrates_core/proof_system/utils/bellman 模块,调用 bellman 库中的 generate_random_parameters 函数生成随机数,并算出对应的 CRS 数据。注意,在生成 CRS 数据之前,需要 synthesize 电路生成 R1CS。

compute-witness 命令

compute-witness 命令,指定输入参数,生成满足电路 R1CS 限制的所有变量对应的值。如下是示例电路对应的 compute-witness 的命令,示例电路对应的 a 为 337,b 为 113569:

1
./zokrates compute-witness -a 337 113569

核心逻辑在 zokrates_core/src/ir/interpreter.rs 的 execute 函数中。获得满足电路的所有变量的值,就是 “执行” 一下电路逻辑,记录相应变量的值即可。

generate-proof 命令

generate-proof 命令,使用 compute-witness 生成的 witness 信息,以及 setup 生成的 CRS 数据,生成 proof 证明。

1
./zokrates generate-proof

核心逻辑在 zokrates_core/src/proof_system/bn128/g16.rs 的 generate_proof 函数中。调用 bellman 库的 create_random_proof 生成证明。

export-verifier 命令

export-verifier 命令,导出以太坊上可以部署的验证证明的智能合约。

1
./zokrates export-verifier

核心逻辑在 zokrates_core/src/proof_system/bn128/g16.rs 的 export_solidity_verifier 函数中。在 g16.rs 中,定义了一个 Groth16 证明验证的模版程序(其中一部分如下):

1
2
3
4
5
6
7
8
function verifyingKey() pure internal returns (VerifyingKey memory vk) {
vk.a = Pairing.G1Point();
vk.b = Pairing.G2Point();
vk.gamma = Pairing.G2Point();
vk.delta = Pairing.G2Point();
vk.gammaABC = new Pairing.G1Point[]();

}

这个模版程序定义了一些 “宏变量”(vk_a, vk_b, vk_gamma, vk_delta 等等)。export-verifier 函数,针对当前的电路以及 CRS 信息,替换相应 “宏变量”,生成真实的验证电路的智能合约。

总结:

ZoKrates 提出了链下计算 / 链上验证的处理框架,并提供了在以太坊上的整个框架的工具链。ZoKrates 使用 zk-SNARK 算法实现零知识证明。ZoKrates 的工具链,极大地降低了在以太坊上实现链下计算 / 链上验证的逻辑的门槛。只需要使用 DSL 语言编写电路,就能使用 ZoKrates 工具库实现链下计算,同时可以导出以太坊上对应的智能合约,实现对应电路的证明验证。

本文作者 Star Li,他的公众号星想法有很多原创高质量文章,欢迎大家扫码关注。

公众号-星想法

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享