ZKSwap 团队详细解读——Halo2 原理

2019 年，Zcash 研发团队推出了一个新的 ZKP 算法————Halo。在目前已使用中的 ZKP 算法中，要么需要 Trust Setup，比如 Groth16、Plonk 等；要么 Proof Size 过于庞大，比如 ZK-Starks。

Fractal 是一个基于 LDT 技术的 Recursive ZKP Protocol，它完全满足 ZKP 的简洁性，且是抗量子的。Halo 虽然不满足简洁性，但是它的 Recursive Proof Size 始终保持在 3.5 KiB 左右，相比于 Fractal 的至少 120 KiB proof size，降低了不少；而且，Halo 的 Verify 操作（与 Circuit Size 呈线性关系）只需要在 Recursive 的最后执行一次，这归功于该算法的创新技术：基于 Accumulation schemes 的 Nested Amortization 算法。

Halo 的 Arithmetization 过程与 Sonic 算法，基于 R1CS 的 circuit 设计，然后进行 Polynomial IOP。然而，事实证明 Plonk 里描述的 Arithmetization 过程和 Polynomial IOP 方案更高效；因此，基于以上改动，Zcash 团队推出了 Halo2 ZKP 算法。

Halo VS Halo2

用一张简单的图来表示下两个 ZKP 算法的过程及异同点，如下如所示：

ZKSwap 团队详细解读——Halo2 原理

Halo 采用了 Sonic 里的 Polynomial IOP 技术描述了一种 Recursive Proof Composition 算法，并且同样采用了 Bulletproof 里的 Inner Product argument 技术替换了算法里的 Polynomial Commitment Scheme，这消除了对 Trust Setup 的依赖。

Halo2 进行了进一步的优化，主要是 Polynomial IOP 方向。近年来，研究学者发现了比 Sonic 里更高效的 Polynomial IOP Scheme，比如 Marlin 和 Plonk。相比之下，由于 Plonk 支持更灵活的电路设计，而最终被选中。

Halo2 Arithmetization

Halo 里用 R1CS 来表述 Circuit，模式如下：

 

A * B = C

 

Halo2 里用 Plonk Arithmetization 来表示 Circuit，模式如下：

 

q L *X a + q R * X b + q O * X c + q M * X a X b + q C = 0

 

其中，q* 为 Selector Polynomial, 不同的取值，代表不同的 Gate，如下表所示：

ZKSwap 团队详细解读——Halo2 原理

标准的 Plonk Arithmetization 是由 Add-gate 和 Multi-gate 组成，事实上，我们还可以针对实际的应用场景自定义 Gate，即 Custom-gate，比如，当我们需要实现约束 x c_i = x a_i x b_i xc _i-1 时 (running product，出现在置换论证里)，可以这么设计 :

ZKSwap 团队详细解读——Halo2 原理

而 Plonk Arithmetization 可以表示为：

 

q L * X a + q R * X b + q O * X c + q M * X a X b + q p * (X c - X a X b X(xw -1 )) + q C = 0

 

Commitment Scheme

和 Bulletproof 算法类似，Halo2 里采用了基于 Inner Product Argument 的 Polynomial Commitment Scheme，并且做了一些优化。其计算 Guochen 给如下图所示：

ZKSwap 团队详细解读——Halo2 原理

关于 Inner Product Argument 的原理细节剖析，可参考：

  1. Bulletproof--range proof 1
  2. Bulletproof--range proof 2
  3. Bulletproof--range proof 3

简单来说，Inner Product Argument 把 Polynomial Commitment 的交互复杂度由 O(n) 降低到 O(log(n))。但是， Verifier 需要对每一个 Commitment Proof 都要进行一个 0(n) 级别的操作，即计算 b 和 G。Halo2 里推出了一个新的解决方案，对于 b 的计算，可以利用 Laurent Polynomial 去解决，它是一个特殊的多项式，可以在对数时间内完成 b 的计算；对于 G 的计算，刚好可以用到前面讲到的基于 Inner Product Argument 的 Polynomial Commitment, 但是如前面所说，每个 Commitment proof 都需要一个 O(n) 级的操作，因此 Halo2 里提出了一个 Accumulation Scheme，即把这些 0(n) 级别的操作进行 Accumulate，把多个验证 Proof 的 O(n) 操作累加到的一个 Proof 上，在 Recursive 的最后，进行一次 O(n) 的计算，这样，多个 Proof 摊销了一个 O(n) 的计算时间，在 Halo2 里，定义为 Nested Amortization。

Recursive zk-snakes & Accumulation Scheme

Halo2 采用 Pasta curves: Pallas 和 Vesta 实现 Recursive ZK-Snarks 证明系统，Mina 也采用了这个 Cycle Curves，关于 Recursive ZK-Snarks 的设计原理，可以参考 ZKSwap 团队浅析 L2 扩容关键技术：递归零知识证明剖析 。

由于 Halo2 采用了 Inner Product Argument 论证，因此 Verify 的复杂度是 O(n) 的，这破坏了 Snaks 的简洁性。因此，Halo2 提出一种新的技术 Nested Amortization，是一种 Accumulation Scheme 聚合技术。具体如下：

  1. 在 Verification Circuit 中，不实现 G 的运算，这个运算是 O(n) 的，而是由 Prover 提供 G 以及相关计算参数，作为 Circuit 的 Witness，即对于 Verification Circuit 来讲，已经默认了 G 的正确性，而实际上 G 的正确性仍然需要 Verifier 去做，只不过这一步可以聚合，即采用 Accumulation Scheme 方案；

  2. 第 1 点提到，关于 G 的正确性验证，仍然需要 Verifier 去做，但是我们可以 Accumulate 多个 Proof Instance 的 G，以及相关参数，迭代到最后一步，由 Verifier 一次完成验证，这实际上完成了验证成本的摊销，即 Nested Amortization 的核心。

End

Halo2 是一种基于 UltraPlonk Atithmetization 技术并建立在 Pasta 曲线上的 Recursive ZK-Snarks 算法，它消除了 Trust Setup。它的许多优化都是值得深究并且借鉴的地方，包括本文中没有提到的 Lookup （类似于 Plookup 协议）友好的 Pedersen-like hash 算法，Sinsemilla。在后续的工作中，我们将持续对其进行研究，并用以改善可能的一些工作。