零知识证明 - 深入理解ZoKrates

显示全部楼层 · 发表于 2019-8-9 12:05:02

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

https://www.ise.tu-berlin.de/fileadmin/fg308/publications/2018/2018_eberhardt_ZoKrates.pdf

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

01链下计算/链上验证

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

传统的区块链和ZoKrates的区别如下图所示：

02ZoKrates工具链

使用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描述，最后到生成以太坊上的智能合约的流程，如下图：

03DSL电路示例

ZoKrates给出了详细的电路描述和编译的说明：

https://zokrates.github.io/

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

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为后缀。

04ZoKrates源代码导读

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

commit 87312a55e94055f14f95afeaa2790783d79a1ee5 Author: schaeff [email protected] Date: Sun Jun 23 13:35:03 2019 +0200
remove invalid test case

整个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命令行为起点，解析逻辑相关的代码。

4.1 compile命令

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

./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）：

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文件中）。

4.2 setup命令

setup命令生成CRS。

./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。

4.3 compute-witness命令

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

./zokrates compute-witness -a 337 113569

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

4.4 generate-proof命令

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

./zokrates generate-proof

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

4.5 export-verifier命令

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

./zokrates export-verifier

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

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工具库实现链下计算，同时可以导出以太坊上对应的智能合约，实现对应电路的证明验证。

w5tchslc1h3.png