零知识证明 – zkSNARK 应用场景分析

前几天在魔笛社区分享了三个 zk-SNARK 技术应用的场景，可以让大家 zk-SNARK（Groth16）技术和场景的结合有初步的认识。

隐私：ZCash 项目

Zcash 项目，大家都知道是 “隐私交易”。Zcash 代表了 zk-SNARK 的一个应用方向：隐私。隐私有不同的程度，ZCash 的隐私交易指的是隐藏交易的发送方，接收方以及交易金额。Zcash 已经经历过三个版本：Sprout， Overwinter，Sapling。这三个版本本质上都没有太大的变化，只是支持的功能更多，生成证明更快，体验更好。

一笔转账用 Note 来表示，包括转账的金额 v 和一个随机数。Note 有两个外在的表现形式：一个是 Commitment，一个是 Nullifier。Commitment 和 Nullifier 都是通过不同的 Hash 函数生成。Commitment 代表一次金额转入，Nullifier 代表一次消费。注意，对于一个 Note，Commitment 和 Nullifier 都是唯一的。因为 Commitment 和 Nullifier 是 Hash 的结果，即使这两个数据公开，其他人也无法推断出 Commitment 和 Nullifier 之间存在联系。也就是说，提供一个 Commitment，能说明进行了一笔转账（具体信息其他人未知）。能提供对应的 Nullifier，就能消费。

区块链，作为一个隐私转账平台，将所有的 Commitment（cm），组成一个 Merkle 树：

某个用户需要消费某个 cm，必须向区块链提供零知识证明：

他知道一个 Note，并能生成一个 cm，而且这个 cm 在以 rt 为树根的 Merkle 树上
用同样的 Note 信息，能生成一个 nullfier，而且这个 nullfier 之前没有生成过。

以上只是最简单的概括 Zcash 零知识证明的大体思路，ZCash 的设计非常复杂和严谨，有很多细节。顺便说一句，理解 ZCash，只需要看 ZCash 的白皮书 protocol.pdf。理解了白皮书的设计，看源代码非常直接。

这就是零知识证明的一个重要的运用方向 – 隐私，现实中还有很多应用类似技术的项目：EYBlockchain (EY，安永)，Quorum (JPMorgan)。

链上数据压缩：Filecoin 项目

Filecoin 是存储行业比较热门的项目。Filecoin 想搭建一个去中心化的存储交易平台。去中心化的存储，有个核心问题，怎么证明存储提供方，真实有效的存储了指定的数据。Filecoin 是通过 PoREP 以及 PoST 算法实现（其中就包括零知识证明）。

PoREP 是数据存储证明算法（证明用户数据被正确的处理）。PoRep 算法的全称是 ZigZag-DRG-PoRep。

Sector 中未 Seal 的原始数据首先依次分成一个个小数据，每个小数据 32 个字节。这些小数据之间按照 DRG（Depth Robust Graph）建立连接关系。按照每个小数据的依赖关系，通过 VDE（Verifiable Delay Encode）函数，计算出下一层的所有小数据。整个 PoRep 的计算过程分为若干层（目前代码设置为 4 层），仔细观察每一层的 DRG 关系的箭头方向，上一层向右，下一层就向左，因此得名 ZigZag（Z 字型）。

每一层的输入称为 d（data），每一层的 VDE 的结果称为 r（replica）。对每一层的输入，建构默克尔树，树根为 comm_d, 整个树的数据结构称为 tree_d。对每一层的输出，建构默克尔树，树根为 comm_r，整个树的数据结构称为 tree_r。

简单的说，PoREP 通过零知识证明，证明每一层的数据都经过 VDE 计算生成，并提供最后结果的 Merkle 树的树根。

在数据处理并存储后，每隔一段时间，需要提交存在性证明，也就是 PoST 算法。PoST 算法的基本思想，随机挑选一个 Merkle 树的叶子节点位置，需要提供出一条 Merkle 路径的零知识证明。

这个零知识证明的第二个应用方向：链上数据压缩。PoREP 算法，通过零知识证明证明数据已经正确处理，并提供了处理后数据形成的 Merkle 树的树根。PoST，每隔一段时间，随机抽选一个叶子数据，需要存储提供者在一定的时间内提供从该叶子数据到 Merkle 树根的路径证明。如果，处理完的数据没有保存在一个可靠的存储上，无法在合理的时间内重建整个 Merkle 树，也就无法提供证明。

扩展性：Loopring DEX 3.0 项目

从 2017 年，路印从 “环路撮合” 的最初设计，经过了 1.0，2.0 以及 3.0 的三个大的版本的协议升级。1.0/2.0，相对来说，受限以太坊本身性能的限制，交易流程复杂，体验和中心化交易所相比，有较大的差距。路印协议 3.0，通过 zk-SNARK 技术，在 zk Rollup 的基础上，结合 DEX 的业务场景开发设计，兼顾去中心化和交易性能。

相对 1.0，2.0 来说，路印协议 3.0 将所有的撮合逻辑都在链下完成。每一笔撮合（Settlement）都会生成证明并提交到链上，证明链下的撮合正确无误。

路印协议采用和以太一致的 “账户” 模型，所有的账户的 “状态”（余额）都记录在链下。

所有和状态相关的操作，都是在链下更改，提交 Proof 到链上记录。因为存在链上链下的状态同步，账户的任何操作有三个状态：

Committed （操作已经提交）2/ Verified （该操作已经提供了相应的 Proof）3/ Finalized（之前的所有的操作都已经提交正确的 Proof）

以用户 Deposit “充值” 的操作为例：

用户转账到路印协议的智能合约，转账在链上确认（链上完成充值）。该操作的状态就是 “Committed”。链下的 Relay，监测到 “Committed” 的状态后，更改链下的状态，生成 Proof，并将证明提交到链上，此时该 “充值” 操作的状态为 “Verified” – 链下也已经完成充值。如果之前的所有操作都是 Verified，那该操作的状态就是 Finalized（也就是这个状态是确定的，不会被篡改的）。

链下的状态用三层的四叉 Merkle 树来表示：