Thanks

感谢SecbitLabs @郭宇前两个月分享的Spartan Overview (尽管当时也没太理解)，以及@even 在研究方向上的指引(据说Hyrax 不太好啃)，不至于走太多弯路。

Motivation

缘于folding，缘于NOVA，缘于Setty，了解到了Spartan，但并不认识它，所以才有了本篇及接下来的关于它的一切(预备知识)……

关于Spartan，在ZK领域可能时间上相对也有点儿远了，暂且不考虑它在某些方面的争议，它的一些思想其实已经影响到其它比较热门的方向了，比如当下的热点Lasso & Jolt，所以它的研究意义仍然很大。

Overview

本篇文章主要参考Hyrax 论文后半部分5-6节，即Hyrax 基于GKR with ZK Argument的contribution。

主要分为两部分，前半部分Reduced Sumcheck Verification主要针对GKR with ZK Argument的Step Two做的优化，对应Hyrax 论文中的Part 5。

后半部分Reduced Witness Evaluation 主要针对GKR with ZK Argument的Final Step做的优化，对应Hyrax 论文中的Part 6。

为了方便对照原始论文理解，本文中的notion尽量与Hyrax 原始论文对齐。

Reduced Sumcheck Verification

仍然以这个图为例， $N = 2$ ，则 $b_{N} = 1$ ；第0层， $G = 2$ ，则 $b_{G} = 1$ ；第1层， $G = 4$ ，则 $b_{G} = 2$ ；第2层， $G = 4$ ，则 $b_{G} = 2$ 。

Number of Sumcheck Commitments

为了简单起见，上一篇GKR with ZK Argument 中Sumcheck 协议每次round prover 发送给verifier 的多项式系数的commitment的个数我们固定都是4，也就是说多项式的degree全为3。其实prover 需要commit的多项式的degree是有变化的。

$V_{0} (q^{'}, q) = h^{'} \in {0, 1}^{b_{N}} \sum h_{L} \in {0, 1}^{b_{G}} \sum h_{R} \in {0, 1}^{b_{G}} \sum P_{q^{'}, q, 1} (h^{'}, h_{L}, h_{R}) = h^{'} \in {0, 1}^{b_{N}} \sum h_{L} \in {0, 1}^{b_{G}} \sum h_{R} \in {0, 1}^{b_{G}} \sum e q_{1} (q^{'}, h^{'}) \cdot [m u l_{1} (q, h_{L}, h_{R}) (V_{1} (h^{'}, h_{L}) * V_{1} (h^{'}, h_{R})) + a dd_{1} (q, h_{L}, h_{R}) (V_{1} (h^{'}, h_{L}) + V_{1} (h^{'}, h_{R}))]$

当round $i <= b_{N}$ 时，prover commit的多项式的degree为3，也就是说commitment的个数为4：

当round $i > b_{G}$ 时，prover commit的多项式的degree为2，也就是说commitment的个数为3:

Sumcheck Verifications

我们试图把verifier sumcheck 协议中所有round的校验等式且一个矩阵点乘运算表示：

$M \cdot π = ? Q$

其中每个round prover发送的message 为：

$π_{1} π_{2} π_{3} π_{4} π_{5} π_{last} = (c_{0, 1}, c_{1, 1}, c_{2, 1}, c_{3, 1}) = (c_{0, 2}, c_{1, 2}, c_{2, 2}) = (c_{0, 3}, c_{1, 3}, c_{2, 3}) = (c_{0, 4}, c_{1, 4}, c_{2, 4}) = (c_{0, 5}, c_{1, 5}, c_{2, 5}) = (V_{1} (r^{'}, r_{L}), V_{1} (r^{'}, r_{R}), V_{1} (r^{'}, r_{L}) \cdot V_{1} (r^{'}, r_{R}))$

把它们聚合到一个向量里：

$π = c_{0, 1} c_{1, 1} c_{2, 1} c_{3, 1} c_{0, 2} c_{1, 2} c_{2, 2} c_{0, 3} c_{1, 3} c_{2, 3} c_{0, 4} c_{1, 4} c_{2, 4} c_{0, 5} c_{1, 5} c_{2, 5} V_{1} (r^{'}, r_{L}) V_{1} (r^{'}, r_{R}) V_{1} (r^{'}, r_{L}) \cdot V_{1} (r^{'}, r_{R})$

其中每个round verifier 需要验证时用的参数：

$M_{1} M_{2} M_{3} M_{4} M_{5} M_{last} = (2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) = (- 1, - r_{1}, - r_{1}^{2}, - r_{1}^{3}, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) = (0, 0, 0, 0, - 1, - r_{2}, - r_{2}^{2}, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0) = (0, 0, 0, 0, 0, 0, 0, - 1, - r_{3}, - r_{3}^{2}, 2, 1, 1, 0, 0, 0, 0, 0, 0) = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 1, - r_{4}, - r_{4}^{2}, 2, 1, 1, 0, 0, 0) = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 1, - r_{5}, - r_{5}^{2}, e q (2, r^{'}) \cdot a dd (4, r_{L}, r_{R}), e q (2, r^{'}) \cdot a dd (4, r_{L}, r_{R}), e q (2, r^{'}) \cdot m u l (4, r_{L}, r_{R}))$

把它们聚合到一个矩阵里：

$M = M_{1} M_{2} M_{3} M_{4} M_{5} M_{last}$

每一个round verifier 校验的结果：

$Q = s_{0} 00000$

备注：其中， $s_{0}$ 是第1个round 需要校验的sumcheck 值，是verifier 随机采样的第0层电路编码的evaluation值，也是prover 第1个round要证明的值。

汇总一下就是：

$M \cdot π = M_{1} M_{2} M_{3} M_{4} M_{5} M_{last} \cdot c_{0, 1} c_{1, 1} c_{2, 1} c_{3, 1} c_{0, 2} c_{1, 2} c_{2, 2} c_{0, 3} c_{1, 3} c_{2, 3} c_{0, 4} c_{1, 4} c_{2, 4} c_{0, 5} c_{1, 5} c_{2, 5} V_{1} (r^{'}, r_{L}) V_{1} (r^{'}, r_{R}) V_{1} (r^{'}, r_{L}) \cdot V_{1} (r^{'}, r_{R}) = ? s_{0} 00000$

矩阵 $M$ 需要verifier 自行计算，用红色标记的向量 $π$ 和向量 $Q$ 都是需要prover 进行commit。如果说仍然是一个field对应一个commitment,那么commit之后的校验就变成了:

$M \cdot δ = M_{1} M_{2} M_{3} M_{4} M_{5} M_{last} \cdot δ_{0, 1} δ_{1, 1} δ_{2, 1} δ_{3, 1} δ_{0, 2} δ_{1, 2} δ_{2, 2} δ_{0, 3} δ_{1, 3} δ_{2, 3} δ_{0, 4} δ_{1, 4} δ_{2, 4} δ_{0, 5} δ_{1, 5} δ_{2, 5} X Y Z = ? C_{0} 00000$

有没有觉得向量 $π$ size太大了(19个commitment)？是的，它直接影响着协议过程中的communication cost，所以需要进行压缩处理。

Reducing Sumcheck Commitments

一个field 对应一个commitment: $c_{f_{i}} = [f_{i}]_{g} + [r_{f_{i}}]_{h}$ 每次commit的时候还需要一个blind factor $r_{f_{i}}$ .

这样的话Sumcheck 协议中的commitment个数就会与要commit的多项式的degree成线性关系。如果把一个多项式所有参数的commitment压缩成一个commitment： $c_{f} = i = 1 \sum n [f_{i}]_{g_{i}} + [r_{f}]_{h}$

这样的话就需要多个generator $g_{i}$ 了，但blind factor 变成了一个 $r_{f}$ 。

我们用矩阵第一行的校验为例： $⟨ M_{1}, δ_{, 1} ⟩ = 2 \cdot δ_{0, 1} + δ_{1, 1} + δ_{2, 1} + δ_{3, 1} = C_{0}$

如果把commitment $δ_{i, 1}$ 压缩成一个commitment $δ_{1}$ ，verifier 就无法直接通过上面的等式来进行校验。这其实就转换成了大家所熟知的IPA 证明，即Inner Product Argument verification。接下来简单描述一下IPA协议的执行过程

IPA Protocol Overview

prover 要证明query 向量 $y$ 满足: $⟨ u, y ⟩ = ? v$

Step One

prover 生成多项式的commitment，并发送给verifier

$C_{u} C_{v} = i \sum [u_{i}]_{g_{i}} + [r_{u}]_{h} = [v]_{g} + [r_{v}]_{h}$

Step Two

prover 采样一个与向量 $u$ 等长的向量 $d$ ，对它进行commit；同样也与query 向量 $y$ 交互，结果也进行commit，最后同样也发送给verifier

$C_{d} w C_{w} = i \sum [d_{i}]_{g_{i}} + [r_{1}]_{h} = ⟨ d, y ⟩ = [w]_{g} + [r_{2}]_{h}$

Step Three

verifier 发送一个challenge factor $e$ 给prover，prover 计算 $u^{'} r_{u^{'}} r_{v^{'}} = e \cdot u + d = e \cdot r_{u} + r_{1} = e \cdot r_{v} + r_{2}$

并把它们全部发送给verifier。

Step Four

根据commitment 同态性质，verifier 验证：

$i \sum [u_{i}^{'}]_{g_{i}} + [r_{u^{'}}]_{h} [⟨ u^{'}, y ⟩]_{g} + [r_{v^{'}}]_{h} = e \cdot i \sum [u_{i}]_{g_{i}} + e \cdot [r_{u}]_{h} + i \sum [d_{i}]_{g_{i}} + [r_{1}]_{h} = ? e \cdot C_{u} + C_{d} = e \cdot [⟨ u, y ⟩]_{g} + [⟨ d, y ⟩]_{g} + [r_{v^{'}}]_{h} = ? e \cdot C_{v} + C_{w} + [r_{v^{'}}]_{h}$

Reducing Sumcheck into IPA

最后我们看看Hyrax 中Sumcheck 协议被reduced成IPA 协议后的执行过程：

Step One

把多个verification fold成一个： $J ⟹ ⟨ J, π ⟩ = i = 1 \sum 6 ρ_{i} \cdot M_{i} = (2 ρ_{1} - ρ_{2}) (ρ_{1} - r_{1} ρ_{2}) (ρ_{1} - r_{1}^{2} ρ_{2}) (ρ_{1} - r_{1}^{3} ρ_{2}) (2 ρ_{2} - ρ_{3}) (ρ_{2} - r_{2} ρ_{3}) (ρ_{2} - r_{2}^{2} ρ_{3}) (2 ρ_{3} - ρ_{4}) (ρ_{3} - r_{3} ρ_{4}) (ρ_{3} - r_{3}^{2} ρ_{4}) (2 ρ_{4} - ρ_{5}) (ρ_{4} - r_{4} ρ_{5}) (ρ_{4} - r_{4}^{2} ρ_{5}) (2 ρ_{5} - ρ_{6}) (ρ_{5} - r_{5} ρ_{6}) (ρ_{5} - r_{5}^{2} ρ_{6}) ρ_{6} \cdot (e q (2, r^{'}) \cdot a dd (4, r_{L}, r_{R})) ρ_{6} \cdot (e q (2, r^{'}) \cdot a dd (4, r_{L}, r_{R})) ρ_{6} \cdot (e q (2, r^{'}) \cdot m u l (4, r_{L}, r_{R}))^{T} = ? i = 1 \sum 6 ρ_{i} \cdot Q_{i} = ρ_{0} \cdot s_{0}$

对 $π$ 进行commit： $α_{1} α_{2} α_{3} α_{4} α_{5} X Y Z = i = 1 \sum 4 [c_{i, 1}]_{g_{i}} + [r_{α_{1}}]_{h} = i = 1 \sum 3 [c_{i, 2}]_{g_{i}} + [r_{α_{2}}]_{h} = i = 1 \sum 3 [c_{i, 3}]_{g_{i}} + [r_{α_{3}}]_{h} = i = 1 \sum 3 [c_{i, 4}]_{g_{i}} + [r_{α_{4}}]_{h} = i = 1 \sum 3 [c_{i, 5}]_{g_{i}} + [r_{α_{5}}]_{h} = [v_{0}]_{g} + [r_{X}]_{h} = [v_{1}]_{g} + [r_{Y}]_{h} = [v_{0} \cdot v_{1}]_{g} + [r_{Z}]_{h}$

对 $Q$ 进行commit： $C_{0} = [s_{0}]_{g} + [r_{C_{0}}]_{h}$

commit 之后，prover要证明的变成了： $⟨ J, (α, X, Y, Z)⟩ = ? ρ_{0} \cdot C_{0}$

把两组commitment $α = (α_{1}, α_{2}, α_{3}, α_{4}, α_{5}, X, Y, Z)$ 和 $C_{0}$ 全部发送给verifier。

定义 $J^{*} = J [: - 3]$ ， $π^{*} = π [: - 3]$ ，即剔除掉最后三个元素，则： $⟨ J^{*}, α ⟩ + ⟨ J_{X}, X ⟩ + ⟨ J_{Y}, Y ⟩ + ⟨ J_{Z}, Z ⟩ = ρ_{0} \cdot C_{0} ⇓ i = 1 \sum 5 J_{i} \cdot r_{α_{i}} = ρ_{0} \cdot r_{C_{0}} - J_{X} \cdot r_{X} - J_{Y} \cdot r_{Y} - J_{Z} \cdot r_{Z}$

Step Two

prover 随机生成一个与 $π^{*}$ 等长的向量 $d$ ，同 $π^{*}$ 一样计算它的commitment，及 $⟨ J^{*}, d ⟩$ 的commitment： $δ_{1} δ_{2} δ_{3} δ_{4} δ_{5} C = i = 1 \sum 4 [d_{i, 1}]_{g_{i}} + [r_{δ_{1}}]_{h} = i = 1 \sum 3 [d_{i, 2}]_{g_{i}} + [r_{δ_{2}}]_{h} = i = 1 \sum 3 [d_{i, 3}]_{g_{i}} + [r_{δ_{3}}]_{h} = i = 1 \sum 3 [d_{i, 4}]_{g_{i}} + [r_{δ_{4}}]_{h} = i = 1 \sum 3 [d_{i, 5}]_{g_{i}} + [r_{δ_{5}}]_{h} = [⟨ J^{*}, d ⟩]$

把两组 commitment $δ = (δ_{1}, δ_{2}, δ_{3}, δ_{4}, δ_{5})$ 和 $C$ 全部发送给verifier。

Step Three

verifier 发送一个challenge factor $e$ 给prover，prover 计算： $\overset{◯}{1} \overset{◯}{2} \overset{◯}{3} z_{C} z = ⎩ ⎨ ⎧ z_{1} z_{2} z_{3} z_{4} z_{5} = e \cdot [c_{0, 1}, c_{1, 1}, c_{2, 1}, c_{3, 1}] + [d_{0, 1}, d_{1, 1}, d_{2, 1}, d_{3, 1}] = e \cdot [c_{0, 2}, c_{1, 2}, c_{2, 2}] + [d_{0, 2}, d_{1, 2}, d_{2, 2}] = e \cdot [c_{0, 3}, c_{1, 3}, c_{2, 3}] + [d_{0, 3}, d_{1, 3}, d_{2, 3}] = e \cdot [c_{0, 4}, c_{1, 4}, c_{2, 4}] + [d_{0, 4}, d_{1, 4}, d_{2, 4}] = e \cdot [c_{0, 5}, c_{1, 5}, c_{2, 5}] + [d_{0, 5}, d_{1, 5}, d_{2, 5}] ⎩ ⎨ ⎧ z_{δ_{1}} z_{δ_{2}} z_{δ_{3}} z_{δ_{4}} z_{δ_{5}} = e \cdot r_{α_{1}} + r_{δ_{1}} = e \cdot r_{α_{2}} + r_{δ_{2}} = e \cdot r_{α_{3}} + r_{δ_{3}} = e \cdot r_{α_{4}} + r_{δ_{4}} = e \cdot r_{α_{5}} + r_{δ_{5}} = e \cdot i = 1 \sum 5 J_{i}^{*} \cdot r_{α_{i}} + r_{C} = e \cdot (ρ_{0} \cdot r_{C_{0}} - J_{X} \cdot r_{X} - J_{Y} \cdot r_{Y} - J_{Z} \cdot r_{Z}) + r_{C}$

Step Four

verifier 验证： $\overset{◯}{1} \overset{◯}{2} ⎩ ⎨ ⎧ \sum_{i = 1}^{4} [z_{i, 1}]_{g_{i}} + [z_{δ_{1}}]_{h} = ? e \cdot α_{1} + δ_{1} \sum_{i = 1}^{3} [z_{i, 2}]_{g_{i}} + [z_{δ_{2}}]_{h} = ? e \cdot α_{2} + δ_{2} \sum_{i = 1}^{3} [z_{i, 3}]_{g_{i}} + [z_{δ_{3}}]_{h} = ? e \cdot α_{3} + δ_{3} \sum_{i = 1}^{3} [z_{i, 4}]_{g_{i}} + [z_{δ_{4}}]_{h} = ? e \cdot α_{4} + δ_{4} \sum_{i = 1}^{3} [z_{i, 5}]_{g_{i}} + [z_{δ_{5}}]_{h} = ? e \cdot α_{5} + δ_{5} [⟨ J^{*}, z ⟩]_{g} + [z_{C}]_{h} = ? e \cdot (ρ_{0} \cdot C_{0} - J_{X} \cdot X - J_{Y} \cdot Y - J_{Z} \cdot Z) + C$

到此为止多个round 的Sumcheck verification就被转换成了一个IPA verification，proof size(commitments) 也被进一步压缩。

Reduced Witness Evaluation

Recall

GKR with ZK Argument协议的Final Step是要对最下面一层(input + witness) 的某个evaluation 进行证明，我们仍然用GKR with ZK Argument中的例子： $V_{2} (2, (3, 4)) = ? 2$

需要verifier基于Step ZERO发送过来的每个witness对应的commitment 计算witness MLE上的evaluation值对应的commitment： $w (x_{2}, x_{3}) commit (w (x_{2}, x_{3})) = 2 \cdot (1 - x_{2}) (1 - x_{3}) + 3 \cdot (1 - x_{2}) x_{3} + 2 \cdot x_{2} (1 - x_{3}) + 4 \cdot x_{2} x_{3} ⇓ = commit (2) \cdot (1 - x_{2}) (1 - x_{3}) + commit (3) \cdot (1 - x_{2}) x_{3} + commit (2) \cdot x_{2} (1 - x_{3}) + commit (4) \cdot x_{2} x_{3}$

它的问题在于，需要对每个witness进行commit(上面红色标记的部分)，导致communication cost 和 verification cost都会比较高，与witness的长度成线性关系 $O (∣ w ∣)$ ，Hyrax 对其进行了压缩，变成了子线性关系 $O (∣ w ∣)$ 。

Square-root commitment scheme

Hyrax 在这里的整体思路是，把上面witness evaluation 的commitment的计算代理给了prover，prover 提供计算结果的同时需要提供相应的proof给verifier 验证，当然了verifier 验证的成本肯定要低于自己计算的成本，满足succinct 特性： $O (∣ w ∣) < O (∣ w ∣)$

把witness evaluation 的commitment的证明最终变成了一个IPA 的证明。

实例中 $∣ w ∣ = 2^{l} = 4, l = 2$ 。

Evaluation and Proof

prover 把witness 向量 $w$ 转换成一个矩阵 $T$ 表示， $T_{i + 2^{l /2} \cdot j}$ 其中 $i 、 j$ 分别代表行和列： $T = [w_{0} w_{1} w_{2} w_{3}]$

按行进行commit： $T_{1} = [w_{0}]_{g_{1}} + [w_{2}]_{g_{2}} + [r_{T_{1}}]_{h} T_{2} = [w_{1}]_{g_{1}} + [w_{3}]_{g_{2}} + [r_{T_{2}}]_{h}$

把witness的commitment $T_{1} 、 T_{2}$ 连同evaluation 的commitment $ω$ 一起发送给verifier。

Compressed Lagrange Basis

基于MLE 多项式： $w (r_{1}, r_{2}, \dots, r_{l}) = b \in {0, 1}^{l} \sum w (b) \cdot k \in {1, 2, \dots, l} \prod χ_{b_{k}} (r_{k})$

我们把Lagrange Basis Polynomial $χ_{b}$ 一拆为二： $\overset{χ}{ˇ}_{b} \overset{χ}{ˆ}_{b} L R = k = 1 \prod l /2 χ_{b_{k}} (r_{k}) = k = l /2 + 1 \prod l χ_{b_{k}} (r_{k}) = (\overset{χ}{ˇ}_{0}, \overset{χ}{ˇ}_{1}, \dots, \overset{χ}{ˇ}_{2^{l /2} - 1}) = (\overset{χ}{ˆ}_{0}, \overset{χ}{ˇ}_{w^{l /2}}, \dots, \overset{χ}{ˇ}_{2^{l /2} \cdot (2^{l /2} - 1)})$

结合上面的witness 矩阵 $T$ ，一定有： $L \cdot T \cdot R = b \in {0, 1}^{l} \sum w (b) \cdot k \in {1, 2, \dots, l} \prod χ_{b_{k}} (r_{k}) = w (r_{1}, r_{2}, \dots, r_{l})$

通过两组 $n$ 的子向量来represent 长度为 $n$ 的整个向量，这里应该是一种很常见的succinct 做法。比如protostar 论文中3.5 节compressed verification也是采用了这种技巧，细节可以参考 https://learnblockchain.cn/article/6503

所以verifier 需要自己计算拿到两个向量(为了简化，实例中 $∣ w ∣ = 4$ ，所以 $2 ∣ w ∣ = 4$ 其实是没有起到compress作用的，如果 $∣ w ∣ > 4$ compress 效果就出来了，读者可以自行举例)： $L = (\overset{χ}{ˇ}_{0}, \overset{χ}{ˇ}_{1}) R = (\overset{χ}{ˇ}_{2}, \overset{χ}{ˇ}_{3})$

并计算得到： $T^{'} = k = 1 \sum L_{k} \cdot T_{k}$ 其中 $T_{k}$ 为commitment， $L_{k}$ 为verifier 刚计算好的scalar，最终verifier 拿到一个commitment $T^{'}$ 。

IPA for Evaluation Verification

最终verifier 需要对prover 提供的evaluation的commitment进行验证，这时的验证就变成了标准的IPA 验证： $⟨ T^{'}, R ⟩ = ? ω$

关于IPA 的执行过程这里就不再赘述了，可以参考上面的IPA Protocol Overview。

Summary

到此，Hyrax 协议也就完整了。简单总结一下，Hyrax 本质就是一套GKR 协议，它在proof size 和 verification 方面做了一些工作。

References

【1】Hyrax 论文：https://eprint.iacr.org/2017/1132.pdf

【2】PAZK by Thaler：https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

【3】protostar compressed verification: https://learnblockchain.cn/article/6503

World of Z2O-K7E