理解 Lasso (二)：稀疏向量与 Tensor 结构

作者: Yu Guo@Secbit(郭宇): Founder of Secbit, https://github.com/sec-bit

本文我们介绍一个基于 Sumcheck 的「稀疏多项式承诺方案」 Spark，这个方案最早出自 [Spartan] 证明系统。Spark 利用了稀疏向量的结构，可以大幅提升 Prover 的效率。Lasso 是在 Spark 的基础上的进一步拓展了对稀疏向量的处理。理解 Spark 是理解 Lasso 的关键。

普通的多项式承诺方案包括两个阶段，一个是承诺（Commitment）阶段，另一个是求值证明（Evaluation Argument）阶段。对于一个 MLE 多项式 $g \in F [X_{0}, X_{1}, \dots, X_{n - 1}]^{⪯ 1}$ ，求值点 $u \in F^{n}$ ，以及运算结果 $v = g (u)$ ，那么多项式承诺计算如下：

$cm (g) \leftarrow PCS.Commit (\tilde{g})$

在求值证明阶段，Prover 可以向 Verifier 证明多项式 $\tilde{g}$ 在某一个指定点 $u$ 的运算结果为 $v$ ：

$π_{g, v} \leftarrow PCS.Eval (cm (g), u, v; \tilde{g})$

Verifier 可以验证求值证明 $π_{g, v}$ ：

$Accept / Reject \leftarrow PCS.Verify (cm (g), u, v, π_{v})$

如果 $\tilde{g}$ 是一个稀疏的多项式，意味着它在 Boolean HyperCube 上的运算结果中多数的值都为零，那么我们能否利用这个特点，来设计一个针对稀疏多项式更高效的多项式承诺方案？

下面我们演示如何构造 Spark 多项式承诺。不过请记住，Spark 仍然需要基于一个普通的多项式承诺方案。换句话说，Spark 协议是将一个稀疏的 MLE 多项式的求值证明「归约」到多个普通的 MLE 多项式的求值证明，但后者这些 MLE 多项式的大小被大幅减少。

1. 稀疏向量的编码

我们考虑一个长度为 $N = 2^{n}$ 的稀疏向量 $g = (g_{0}, g_{1}, \dots, g_{N - 1})$ 是一个 MLE 多项式 $\tilde{g} (X)$ 在 Boolean HyperCube ${0, 1}^{n}$ 上的取值。记住 $g$ 是一个稀疏的向量，其中除了 $m$ 个非零元素之外其余值都为零。

先回忆下 MLE 多项式 $\tilde{g} (X)$ 的定义：

$g (X) = i = 0 \sum N - 1 g_{i} \cdot e q_{i} (X)$

其中 $e q_{i} (X) = e q (bits (i), X)$ 是 MLE Lagrange 多项式。 $\tilde{e q} (X, Y)$ 定义如下：

$\tilde{e q} (X, Y) = i = 0 \prod n - 1 (X_{i} Y_{i} + (1 - X_{i}) (1 - Y_{i}))$

如果直接使用一个普通的 MLE 多项式承诺方案来证明多项式求值， $g (u) = v$ ，由于 $g (X)$ 是一个关于 $N$ 项的求和公式，那么很显然 Prover 要至少花费 $O (N)$ 的计算量来遍历每一个求和项。

如果给定一个求值点 $X = u = (u_{0}, u_{1}, \dots, u_{n - 1})$ ，那么所有的 $\tilde{e q}_{i} (u), i \in [0, N)$ 就构成了一个长度为 $N$ 的向量，记为 $λ$ ：

$λ = (e q_{0} (u), e q_{1} (u), e q_{2} (u), \dots, e q_{N - 1} (u))$

别忘记稀疏向量 $g$ 中仅有 $m$ 个非零元素。举个例子，比如 $N = 16, n = 4, m = 4$ ，即 $g$ 向量中仅有四个非零值：

$g = (0, 0, g_{2}, 0, 0, 0, 0, g_{7}, 0, g_{9}, 0, 0, 0, 0, g_{14}, 0)$

那么我们可以换用一种稠密的方式来表示 $g$ ：

$DenseRepr (g) = ((2, g_{2}), (7, g_{7}), (9, g_{9}), (14, g_{14}))$

可以看出，向量 $g$ 的稠密表示是一个长度仅为 $m$ 的向量，其每一个元素为非零元素位置和非零元素值的二元组。我们再把上面二元组向量中的位置值单独记为 $k = (k_{0}, k_{1}, \dots, k_{m - 1})$ 向量，把元组中非零的 $g_{i}$ 记为 $h = (h_{0}, h_{1}, \dots, h_{m - 1})$ 向量：

$h k = (g_{2}, g_{7}, g_{9}, g_{14}) = (2, 7, 9, 14)$

那么 $g$ 的稠密表示可以写成：

$DenseRepr (g) = ((k_{0}, h_{0}), (k_{1}, h_{1}), \dots, (k_{m - 1}, h_{m - 1}))$

然后 MLE 多项式 $\tilde{g} (X)$ 在 $u$ 点的求值等式可以改写为：

$g (u) = i = 0 \sum m - 1 h_{i} \cdot e q_{k_{i}} (u) = i = 0 \sum m - 1 h_{i} \cdot λ_{k_{i}}$

注意上面这个等式中的求和项的个数仅为 $m$ 。这意味着在给定 $h$ 和 $λ$ 的情况下，我们成功地把 $\tilde{g} (X)$ 的求值运算从 $O (N)$ 降到了 $O (m)$ 。接下来的问题是 Prover 如何向 Verifier 证明求值过程用到了正确的 $h_{i}$ 和 $λ_{k_{i}}$ ？

对于一个多项式承诺方案，求值证明的公开输入里面包括了 $g$ 向量的承诺，但是上面的求和式需要用到辅助向量 $h$ ， $k$ 和 $λ$ 。其中 $λ$ 向量可以通过求值点 $u$ 计算得到，其中每个元素为 $λ_{i} = \tilde{e q}_{i} (u)$ ，而求值点 $u$ 为公开输入，因此 Verifier 可以公开计算 $λ$ 向量或者公开验证。但 Verifier 并不能由 $g$ 向量的承诺来直接得到 $h$ 和 $k$ 这两个向量的信息。因此，我们需要把 $h$ 和 $k$ 的承诺来替代公开输入中的 $g$ 向量的承诺。

换句话说，我们采用 $h$ 和 $k$ 来作为稀疏向量的 $g$ 的编码，并利用一个普通的多项式承诺方案来计算 $cm (h)$ 和 $cm (k)$ ，并把它们作为多项式求值证明的承诺（做为公开输入）。

2. 借助 $e$ 的 Sumcheck

我们需要引入一个长度为 $m$ 的辅助向量 $e = (e_{0}, e_{1}, \dots, e_{m - 1})$ ，它的每一个元素 $e_{i} = λ_{k_{i}}$ ：

$e = (e q_{k_{0}} (u), e q_{k_{1}} (u), \dots, \tilde{e q}_{k_{m - 1}} (u))$

这样 $\tilde{g} (X)$ 在 $u$ 点的求值等式等价于下面的求和等式:

$g (u) = i = 0 \sum m - 1 h (bits (i)) \cdot \tilde{e} (bits (i))$

其中 $e (X)$ 是一个编码了 $e$ 的 MLE 多项式， $h (X)$ 是关于 $h$ 的 MLE 多项式

$e (X) = i = 0 \sum m - 1 e_{i} \cdot e q_{i} (X) h (X) = i = 0 \sum m - 1 h_{i} \cdot e q_{i} (X)$

如果 Prover 要证明上面的求和式，首先提供 $e$ 的承诺 $cm (e)$ 给 Verifier，然后通过接下来的两部分来完成证明。

第一部分证明是 Prover 利用 Sumcheck 协议，把 $\tilde{g} (u)$ 的求值证明规约到下面的等式

$v^{'} = ? h (ρ) \cdot e (ρ)$

其中 $v^{'}$ 为 Sumcheck 协议对 $m$ 个求和项进行折叠运算后的结果，而 $ρ$ 为 Sumcheck 运行过程中 Verifier 产生的随机折叠因子。因为 Sumcheck 过程需要 $lo g m$ 轮，所以 $ρ$ 的长度为 $lo g m$ 。

接下来 Prover 怎么证明上面的等式呢？在求值证明之前，Verifier 已经从公开输入中得到了 $h$ , $e$ 两个向量的承诺，分别为 $cm (h)$ 与 $cm (e)$ ，那么到这一步，Prover 和 Verifier 可以再利用普通的 MLE 多项式承诺方案来完成两个 Evaluation Argument，即分别证明： $h (ρ) = v_{h}$ 与 $e (ρ) = v_{e}$ 的正确性，因为这两个向量长度均为 $m$ ，因此 Prover 产生这两个 Evaluation Argument 的计算量为 $O (m)$ 。最后 Verifier 验证 $v = ? v_{h} \cdot v_{e}$ 完成第一部分的证明。

第二部分证明是 Prover 证明 $e$ 向量关于 $λ$ , $u$ 与 $k$ 的正确性，这就需要用到前文介绍过的 Offline Memory Checking 方法：Prover 只要证明 $e$ 向量中的每一个元素都是从 $λ$ 向量（看成是内存）中读取出来的即可。这样 Prover 总的计算量为 $O (m + N)$ 。

3. 使用 Memory Checking 证明 $e$ 的正确性

辅助向量 $e$ 的正确性证明正是 Indexed Lookup Argument：

$\forall i \in [0, m), e_{i} = λ_{k_{i}}$

借助 Memory Checking 协议，我们把整个 $λ$ 向量（公开向量）看成是一段内存，Prover 证明 $e$ 向量依次读取自内存 $λ$ ，读取的位置为 $k$ 。Prover 可以在 $O (m + N)$ 的计算量内完成上面的证明。

$MemChecking (cm (e), cm (λ), cm (k); e, λ, k_{i})$

结合前文的定义，这里 $e$ 为查询向量 $f$ ， $λ$ 为表格向量 $t$ ，而 $k$ 为位置向量 $a$ 。

但还有一个问题， $λ$ 的承诺 $cm (λ)$ 怎么产生？向量元素 $λ_{i} = e q_{i} (u)$ ，其定义中含有一个求值阶段才出现的公开输入 $u$ ，因此不能在 $g$ 的承诺阶段中出现，也无法出现在 $g (X)$ 求值证明的公开输入中，一般情况多项式承诺方案的公开输入为 $(cm (g), u, g (u))$ 。如果由 Prover 计算 $cm (λ)$ 的话，那么 Prover 需要额外证明承诺的正确性。

幸运的是， $λ$ 向量具有一定内部的结构，虽然它的长度为 $N$ ，但在给定 $u$ 的情况下，它的插值多项式 $λ (X)$ 可以在 $O (lo g N)$ 的时间内进行求值计算，于是这样一来 Prover 可以不需要提供 $cm (λ)$ ，而是让 Verifier 在验证过程中自行计算 $λ (X)$ 在某一点的取值。我们观察下 $\tilde{λ} (X)$ 的定义：

$λ (X) = e q (X, u)$

容易检验，对于任意的 $i \in [0, N)$ ，

$λ_{i} = λ (bits (i)) = e q (bits (i), u) = j = 0 \prod l o g N - 1 (i_{j} u_{j} + (1 - i_{j}) (1 - u_{j}))$

上面等式最右边是一个 $lo g N$ 项的乘积，其中每一个因子只需要常数次的加法和乘法。接下来我们稍微修改下前文中的 Offline Memory Checking 协议，把公开输入中的 $cm (λ)$ 替换为 $u$ ，并且让 Verifier 自行计算 $\tilde{λ} (X)$ 的值。

Memory Checking 协议描述

公共输入：

$C_{e} = cm (e)$ ， $∣ e ∣ = m$
$C_{k} = cm (k)$ ， $∣ k ∣ = m$
$u$ , $∣ u ∣ = n = lo g N$

第一轮

Prover 计算 $S_{m}$ , ${R_{j}}_{j \in [m]}$ ， ${W_{j}}_{j \in [m]}$

$S_{m} R_{j} W_{j} = {(i, λ_{i}, c_{i}^{final})}_{i \in [m]} = (k_{j}, e_{j}, c_{j}), j \in [m] = (k_{j}, e_{j}, c_{j} + 1), j \in [m]$

Prover 计算并发送计数器的承诺 $C_{c} = cm ({c_{j}})$ ， $C_{c}^{final} = cm ({c_{i}^{final}})$

第二轮

Verifier 发送挑战数 $β, γ$

Prover 计算 ${R_{j}}$ , ${W_{j}}$ ,

$R_{j} W_{j} = k_{j} + β \cdot e_{j} + β^{2} \cdot c_{j} - γ = k_{j} + β \cdot e_{j} + β^{2} \cdot (c_{j} + 1) - γ$

Prover 计算 ${S_{i}^{init}}$ 与 ${S_{i}^{final}}$

$S_{i}^{init} S_{i}^{final} = i + β \cdot λ_{i} + β^{2} \cdot 0 - γ = i + β \cdot λ_{i} + β^{2} \cdot c_{i}^{final} - γ$

Prover 和 Verifier 利用基于 Sumcheck 的 Grand Product Argument 来证明下面的等式：

$(i = 0 \prod N - 1 S_{i}^{init}) \cdot (j = 0 \prod m - 1 R_{j}) = (i = 0 \prod N - 1 S_{i}^{final}) \cdot (j = 0 \prod m - 1 W_{j})$

Grand Product Argument 证明最后会归约到对多个 MLE 多项式的求值证明，也就是对 $S^{init} (X)$ ， $S^{final} (X)$ ， $R (X)$ ， $W (X)$ 的求值证明。这些证明可以归约到 $I (X), k (X), e (X), c (X), c^{final} (X)$ 与 $λ (X)$ 的求值证明。注意我们前面提到过， Verifier 不需要 $λ (X)$ 的承诺求值证明，他可以自行计算 $λ (X)$ 在任意点的求值。因为该多项式的求值计算量仅为 $O (lo g N)$ ，不影响 Verifier 的简洁性（Succinctness）。

进一步，任何计算过程仅为 $O (lo g N)$ 的 MLE 多项式，Prover 也不必要一定计算它们的承诺，只要把计算任务交给 Verifier 就好。这样 Verifier 仍然保持 SNARK 的特性，同时也提高了 Prover 的效率，省去了计算承诺和产生求值证明的工作量。前提是，这一类 MLE 多项式需要具有一种特殊的内部结构，我们后文会把它们归到一个特殊的分类：MLE-Structured Vector。

对于 Prover 而言，仍然需要在证明过程中构造 $λ$ ，通过动态规划算法，这需要 $O (N)$ 的计算量。

$λ = (e q_{0} (r), e q_{1} (r), e q_{2} (r), \dots, e q_{N - 1} (r))$

4. 求值证明协议细节

1. 承诺阶段：

Prover 要计算下面两个承诺：

$cm (h)$ ：稀疏向量 $g$ 中的非零元素向量 $h$ 的承诺
$cm (k)$ ： $g$ 中的所有非零元素在 $g$ 中的位置向量 $k$ 的承诺

2. 求值证明阶段：

公共输入：

多项式的承诺 $(cm (h), cm (k))$
求值点 $u$ ，以及运算结果 $v = \tilde{g} (u)$

第一轮：

Prover 计算 $λ$ ，作为内存模拟
Prover 计算 $e$ ，并发送承诺 $cm (e)$ ，作为 memory 顺序读取出的内容

第二轮：Prover 与 Verifier 执行 Offline Memory Checking 协议，证明

$e_{i} = λ_{k_{i}}, \forall i \in [m]$

第三轮：Prover 与 Verifier 执行 Sumcheck 协议，证明

$v = i \in [0, m) \sum h_{i} \cdot e_{i}$

并把上面的求和等式归约到

$v^{'} = h (ρ) \cdot e (ρ)$

其中 $ρ$ 为 Verifier 在 Sumcheck 过程中发送的挑战向量。

第四轮：Prover 发送 $(v_{h}, v_{e}, π_{h}, π_{e})$

$v_{h} = \tilde{h} (ρ)$ ，求值证明为 $π_{h}$
$v_{e} = \tilde{e} (ρ)$ ，求值证明为 $π_{e}$

验证： Verifier 验证 $π_{h}$ 与 $π_{e}$ 的有效性，并验证下面的等式：

$v^{'} = ? v_{h} \cdot v_{e}$

性能分析

Prover 在 Memory-checking 协议中的性能开销为 $O (m + N)$ ，因为内存的大小为 $N$ ，读取序列长度为 $m$ ；在 Sumcheck 协议中为 $O (m)$ 。因此 Prover 总的计算开销为 $O (m + N)$ 。

这样一个稀疏多项式承诺方案其实并不理想，因为 Prover 的计算量仍然与 $N$ 线性有关。我们希望能够进一步减少 Prover 的计算量，这就需要进一步探索 $λ$ 的内部结构。

5. 向量 $e$ 二维分解

为何 $\tilde{λ} (X)$ 的求值计算量仅为 $O (lo g N)$ ? 因为向量 $λ$ 具有一种特殊的结构——Tensor Structure，也就是它可以拆分成多个短向量的 Tensor Product。简化起见，我们试着把 $λ_{i}$ 按照下面的方法拆分成两部分的乘积：

$λ_{i} = e q (bits (i), u) = j = 0 \prod n - 1 (bits (i)_{j} \cdot u_{j} + (1 - bits (i)_{j}) \cdot (1 - u_{j})) = j = 0 \prod n /2 (bits (i)_{j} \cdot u_{j} + (1 - bits (i)_{j}) \cdot (1 - u_{j})) \cdot j = n /2 + 1 \prod n - 1 (bits (i)_{j} \cdot u_{j} + (1 - bits (i)_{j}) \cdot (1 - u_{j})) = e q (bits^{(high)} (i), (u_{0}, u_{1}, \dots, u_{n /2})) \cdot \tilde{e q} (bits^{(low)} (i), (u_{n /2 + 1}, \dots, u_{n - 1}))$

这里 $i_{0} = bits^{(high)} (i)$ 和 $i_{1} = bits^{(low)} (i)$ 是把 $i$ 的二进制位拆分成相等的两段所表示的数值。举个例子，比如 $i = (13)_{10}$ 是一个十进制数，它的二进制表示为 $bits (i) = (1101)_{2}$ 。我们可以把它拆成高二位与低二位，分别为 $i_{0} = (11)_{2}$ 和 $i_{1} = (01)_{2}$ ，那么 $i_{0} = 3, i_{1} = 1$ 。我们引入一个新的「拼接记号」， $i = i_{0} ∥ i_{1}$ 表示 $i$ 的二进制位为其高位和低位两个数的二进制位的拼接，按照 Big-endian 的方式。比如 $(1101)_{2} = (11)_{2} ∥ (01)_{2}$ 。不难验证，拼接操作满足性质： $i ∥ j = i + N \cdot j$ 。

按照上面的分解方法，我们可以分解 $λ_{13}$ 为两个值的乘积：

$λ_{13} = e q ((11)_{2}, (u_{0}, u_{1})) \cdot e q ((01)_{2}, (u_{2}, u_{3}))$

对于长度为 $N$ 的 $λ$ 向量中的所有元素 $λ_{i}$ ，我们可以把其中每一个元素都按照相同拆分方式进行分解：

$λ_{0} λ_{1} λ_{2} λ_{3} ⋮ λ_{15} = e q ((00)_{2}, (u_{0}, u_{1})) \cdot e q ((00)_{2}, (u_{2}, u_{3})) = e q ((00)_{2}, (u_{0}, u_{1})) \cdot e q ((01)_{2}, (u_{2}, u_{3})) = e q ((00)_{2}, (u_{0}, u_{1})) \cdot e q ((10)_{2}, (u_{2}, u_{3})) = e q ((00)_{2}, (u_{0}, u_{1})) \cdot e q ((11)_{2}, (u_{2}, u_{3})) = e q ((11)_{2}, (u_{0}, u_{1})) \cdot e q ((11)_{2}, (u_{2}, u_{3}))$

我们进而把这 16 个元素排成一个 $4 \times 4$ 的矩阵，每一个单元格的值 $λ_{i}$ 都等于它对应的行向量元素和列向量元素的乘积。

$e q_{0} (u_{2}, u_{3}) e q_{1} (u_{2}, r_{3}) e q_{2} (u_{2}, u_{3}) e q_{3} (u_{2}, u_{3}) e q_{0} (u_{0}, u_{1}) e q_{0 ∥ 0} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{0 ∥ 1} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{0 ∥ 2} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{0 ∥ 3} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{1} (u_{0}, u_{1}) e q_{1 ∥ 0} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{1 ∥ 1} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{1 ∥ 2} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{1 ∥ 3} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{2} (u_{0}, u_{1}) e q_{2 ∥ 0} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{2 ∥ 1} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{2 ∥ 2} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{2 ∥ 3} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{3} (u_{0}, u_{1}) e q_{3 ∥ 0} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{3 ∥ 1} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{3 ∥ 2} (u_{0}, u_{1}, u_{2}, u_{3}) e q_{3 ∥ 3} (u_{0}, u_{1}, u_{2}, u_{3})$

如果把上面表格的第一行的元素组成向量，记为 $λ^{(x)}$ ，第一列记为 $λ^{(y)}$ ：

$λ^{(x)} λ^{(y)} = (e q_{0} (u_{0}, u_{1}), e q_{1} (u_{0}, u_{1}), e q_{2} (u_{0}, u_{1}), e q_{3} (u_{0}, u_{1})) = (e q_{0} (u_{2}, u_{3}), e q_{1} (u_{2}, u_{3}), e q_{2} (u_{2}, u_{3}), e q_{3} (u_{2}, u_{3}))$

那么 $λ$ 向量看成是两个长度为 $N$ 的向量的 Tensor Product：

$λ = λ^{(x)} \otimes λ^{(y)}$

回到我们关注的向量 $e$ ，其中每一个元素 $e_{i}$ 也就可以看成是两个数值的乘积 $e_{i} = e_{i}^{(x)} \cdot e_{i}^{(y)}$ ，其中 $e_{i}^{(x)}$ 来自于 $λ^{(x)}$ ，另一个 $e_{i}^{(y)}$ 来自于 $λ^{(y)}$ 。

这相当于我们把整个 $e$ 向量分解到了一个二维空间中，它的值等于横坐标和纵坐标值的乘积。那么我们可以继续采用 Offline Memory Checking 的思路来证明 $e$ 的正确性，这次我们需要采用二维的 Offline Memory Checking 协议。更直白点说，我们需要采用两次 Offline Memory Checking 协议来证明 $e$ 的正确性，每一个 $e_{i}$ 对应到两个值的乘积，它们分别读取自 $λ^{(x)}$ 和 $λ^{(y)}$ ：

$MemChecking (cm (e^{(x)}), λ^{(x)}, cm (k^{(x)}); e^{(x)}, k^{(x)}) MemChecking (cm (e^{(y)}), λ^{(y)}, cm (k^{(y)}); e^{(x)}, k^{(y)})$

于是稀疏多项式 $\tilde{g} (X)$ 的求值等式可以改写为：

$g (u) = g (u_{0}, u_{1}) = i = 0 \sum m - 1 h (bits (i)) \cdot e^{(x)} (bits (i)) \cdot \tilde{e}^{(y)} (bits (i))$

其中

$e^{(x)} e^{(y)} = (e q_{k_{0}^{(x)}} (u_{0}), e q_{k_{1}^{(x)}} (u_{0}), \dots, e q_{k_{m - 1}^{(x)}} (u_{0})) = (e q_{k_{0}^{(y)}} (u_{1}), e q_{k_{1}^{(y)}} (u_{1}), \dots, e q_{k_{m - 1}^{(y)}} (u_{1}))$

其中 $k_{i}^{(x)}, k_{i}^{(y)} \in (0, 1, \dots, lo g N /2)$ 为非零元素 $h_{i}$ 在二维矩阵中的行列坐标。这样我们可以把求值协议中的 Offline Memory Checking 子协议调用两次，但是内存的大小被大幅缩小到了 $N = 2^{n /2}$ 。看下前面的例子， $N = 16, n = 4, m = 4$ ， $g$ 向量中仅有四个非零值：

$g = (0, 0, g_{2}, 0, 0, 0, 0, g_{7}, 0, g_{9}, 0, 0, 0, 0, g_{14}, 0)$

向量 $h$ 为非零向量：

$h = (g_{2}, g_{7}, g_{9}, g_{14})$

这时候，我们可以采用二维坐标 $(k_{i}^{(x)}, k_{i}^{(y)})$ 来标记 $h_{i}$ 在 $g$ 矩阵中的位置，标记矩阵中的行和列：

$(k_{0}^{(x)}, k_{0}^{(y)}) (k_{1}^{(x)}, k_{1}^{(y)}) (k_{2}^{(x)}, k_{2}^{(y)}) (k_{3}^{(x)}, k_{3}^{(y)}) = (2, 0) = (3, 1) = (1, 2) = (2, 3)$

我们把其中行坐标向量记为 $k^{(x)}$ ，列坐标向量记为 $k^{(y)}$ ，那么 $\tilde{g} (u)$ 可以表示为

$g (u_{0}, u_{1}, u_{2}, u_{3}) = 0 \leq i < 4 \sum h_{i} \cdot e q (bits (k_{i}^{(x)})), (u_{0}, u_{1})) \cdot \tilde{e q} (bits (k_{i}^{(y)}), (u_{2}, u_{3})) = 0 \leq i < 4 \sum h_{i} \cdot e_{i}^{(x)} \cdot e_{i}^{(y)}$

经过 Sumcheck 协议之后，上述等式可以被归约到：

$v^{'} = h (ρ) \cdot e^{(x)} (ρ) \cdot \tilde{e}^{(y)} (ρ)$

然后 Prover 再提供三个 MLE 多项式在 $ρ$ 点的取值， $(v_{h}, v_{x}, v_{y})$ 的求值证明。

在这个二维的求值协议中，Prover 的计算开销就从上一节的 $O (m + N)$ 降低到了 $O (m + 2 N)$ 。

下面我们给出完整的二维稀疏多项式承诺方案。

6. 二维稀疏多项式承诺 Spark

利用上面的思路，我们把稀疏向量 $g$ 重新排列成一个 $N \times N$ 的二维矩阵 $G$ 。为了排版清晰，我们引入符号 $l = N$ ：

$G = g_{0} g_{l} g_{2 l} ⋮ g_{(l - 1) l} g_{1} g_{l + 1} g_{2 l + 1} ⋮ g_{(l - 1) l + 1} g_{2} g_{l + 2} g_{2 l + 2} ⋮ g_{(l - 1) l + 2} \dots \dots \dots ⋱ \dots g_{l - 1} g_{2 l - 1} g_{3 l - 1} ⋮ g_{l^{2} - 1}$

6.1. 承诺阶段：

Prover 要计算下面两个承诺：

$C_{h} = cm (h)$ ：稀疏向量 $g$ 中的非零元素向量 $h$ 的承诺
$C_{x} = cm (k^{(x)})$ ： $h$ 中的所有非零元素在矩阵 $G$ 中的行坐标构成的向量 $k^{(x)}$ 的承诺
$C_{y} = cm (k^{(y)})$ ： $h$ 中的所有非零元素在矩阵 $G$ 中的列坐标构成的向量 $k^{(y)}$ 的承诺

令 $Spark.Commit (g) \to cm_{g}^{(spark)} = (C_{h}, C_{x}, C_{y})$ ，这个三元组承诺我们用符号 $cm_{g}^{(spark)}$ 表示。

6.2. 求值证明阶段：

$π_{g}^{(spark)} \leftarrow Spark.Eval ((C_{h}, C_{x}, C_{y}), u, v; (h, x, y))$ ：

公共输入：

多项式的承诺 $cm_{g}^{(spark)} = (C_{h}, C_{x}, C_{y})$
求值点 $u$ ，这个点可以拆分为两个子向量 $u = u_{x} ∥ u_{y}$ ，其中 $∣ u_{x} ∣ = ∣ u_{y} ∣ = n /2$
以及运算结果 $v = \tilde{g} (u)$

第一轮：

Prover 计算 $λ^{(x)} = {e q_{i} (u_{x})}_{i \in [0, l)}$ ，作为 $mem_{x}$ 内存
Prover 计算 $λ^{(y)} = {e q_{i} (u_{y})}_{i \in [0, l)}$ ，作为 $mem_{y}$ 内存
Prover 计算 $e^{(x)}$ 与 $e^{(y)}$ ，作为分别从内存 $mem_{x}$ 与 $mem_{y}$ 读取出的内容，并发送承诺 $cm (e^{(x)})$ 与 $cm (e^{(y)})$

第二轮：Prover 与 Verifier 执行两次 Offline Memory Checking 协议，证明 $cm (e^{(x)})$ 与 $cm (e^{(y)})$ 的正确性：

$MemChecking (cm (e^{(x)}), u_{x}, cm (k^{(x)}); e^{(x)}, k^{(x)}) MemChecking (cm (e^{(y)}), u_{y}, cm (k^{(y)}); e^{(x)}, k^{(y)})$

第三轮：Prover 与 Verifier 执行 Sumcheck 协议，证明下面的等式求和

$v = i \in [0, m) \sum h_{i} \cdot e_{i}^{(x)} \cdot e_{i}^{(y)}$

并把求和等式归约到

$v^{'} = h (ρ) \cdot e^{(x)} (ρ) \cdot \tilde{e}^{(y)} (ρ)$

其中 $ρ$ 为 Verifier 在 Sumcheck 过程中发送的挑战向量，其长度为 $lo g m$ 。

第四轮：Prover 发送 $(v_{t}, v_{x}, v_{y}, π_{t}, π_{x}, π_{y})$

$v_{h} = \tilde{h} (ρ)$ ，求值证明为 $π_{h} = PCS.Eval (C_{h}, ρ, v_{h}; h)$
$v_{x} = \tilde{e}^{(x)} (ρ)$ ，求值证明为 $π_{x} = PCS.Eval (C_{x}, ρ, v_{x}; k^{(x)})$
$v_{y} = \tilde{e}^{(y)} (ρ)$ ，求值证明为 $π_{y} = PCS.Eval (C_{y}, ρ, v_{y}; k^{(y)})$

验证： Verifier 验证 $π_{h}$ ， $π_{x}$ 与 $π_{y}$ 的有效性，并验证下面的等式：

$v^{'} = ? v_{h} \cdot v_{x} \cdot v_{y}$

6.3. 性能分析

8. Tensor 结构 (TODO)

如果我们可以把 $e$ 分解到二维空间，那么能否分解到更高维的空间？比如 $f$ 的长度为 $2^{30}$ ，那么把它排成二维矩阵，比如 $2^{15} \times 2^{15}$ ，矩阵的长宽还是较大。如果把 $f$ 重新排列成一个立方体，然后同样把 $\tilde{e q}_{i} (r)$ 拆分成三段，这样我们可以把 Offline Memory Checking 的 Prover 开销进一步降低到 $O (N^{1/3})$ ，也就是 $2^{10}$ 。这个分解的灵活性来源于 $λ$ 的结构特性，即一个具有 Tensor Structure 的向量可以用不同的 Tensor Product 分解方式。理论上，我们可以把 $f$ 分解成 $lo g N$ 个长度为 $2$ 的短向量的 Tensor Product。不过实践中，我们只需要将其分解到 $N^{1/ c}$ 即可处理超长的向量。

例如当 $N = 16$ 时， $λ$ 即可以排列成一个 $4 \times 4$ 的二维矩阵，也可以排列成 $2 \times 2 \times 2 \times 2$ 的四维矩阵：

$λ = (r_{0}, 1 - r_{0}) \otimes (r_{1}, 1 - r_{1}) \otimes (r_{2}, 1 - r_{2}) \otimes (r_{3}, 1 - r_{3}) = ((r_{0}, 1 - r_{0}) \otimes (r_{1}, 1 - r_{1})) \otimes ((r_{2}, 1 - r_{2}) \otimes (r_{3}, 1 - r_{3})) = ((r_{0} r_{1}, (1 - r_{0}) r_{1}, r_{0} (1 - r_{1}), (1 - r_{0}) (1 - r_{1}))) \otimes ((r_{2} r_{3}, (1 - r_{2}) r_{3}, r_{2} (1 - r_{3}), (1 - r_{2}) (1 - r_{3})))$

我们可以根据 Tensor Product 逐步来推导下：

$(r_{0}, (1 - r_{0})) \otimes (r_{1}, (1 - r_{1})) = r_{1} (1 - r_{1}) r_{0} r_{0} r_{1} r_{0} (1 - r_{1}) (1 - r_{0}) (1 - r_{0}) r_{1} (1 - r_{0}) (1 - r_{1})$

再利用上面的计算结果来计算 $(r_{0}, (1 - r_{0})) \otimes (r_{1}, (1 - r_{1})) \otimes (r_{2}, (1 - r_{2}))$

$r_{0} r_{1} (1 - r_{0}) r_{1} r_{0} (1 - r_{1}) (1 - r_{0}) (1 - r_{1}) r_{2} r_{0} r_{1} r_{2} (1 - r_{0}) r_{1} r_{2} r_{0} (1 - r_{1}) r_{2} (1 - r_{0}) (1 - r_{1}) r_{2} (1 - r_{2}) r_{0} r_{1} (1 - r_{2}) (1 - r_{0}) r_{1} (1 - r_{2}) r_{0} (1 - r_{1}) (1 - r_{2}) (1 - r_{0}) (1 - r_{1}) (1 - r_{2})$

其实，许多常见的向量也具备 Tensor Structure，比如 $(1, α, α^{2}, \dots, α^{2^{n} - 1})$ ：

$(1, α, α^{2}, \dots, α^{2^{n} - 1}) = (1, α) \otimes (1, α^{2}) \otimes (1, α^{4}) \otimes \dots \otimes (1, α^{2^{(n - 1)}})$

7. 小结

本文介绍了 Tensor Structure 的概念，利用这个结构，我们可以把稀疏向量映射到一个二维空间中进行编码，然后我们基于这个结构，可以构造一个稀疏向量的多项式承诺方案。

References

[Spartan] Spartan: Efficient and general-purpose zkSNARKs without trusted setup by Srinath Setty.
[Lasso] Unlocking the lookup singularity with Lasso by Srinath Setty, Justin Thaler and Riad Wahby.
[Jolt] Jolt: SNARKs for Virtual Machines via Lookups by Arasu Arun, Srinath Setty and Justin Thaler.
[PLONK] PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge by Ariel Gabizon, Zachary J. Williamson and Oana Ciobotaru.
[Plookup] plookup: A simplified polynomial protocol for lookup tables by Ariel Gabizon and Zachary J. Williamson.
[Caulk] Caulk: Lookup Arguments in Sublinear Time by Arantxa Zapico, Vitalik Buterin,Dmitry Khovratovich, Mary Maller, Anca Nitulescu and Mark Simkin
[Caulk+] Caulk+: Table-independent lookup arguments by Jim Posen and Assimakis A. Kattis.
[Baloo] Baloo: Nearly Optimal Lookup Arguments by Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller and Carla Ràfols.
[CQ] cq: Cached quotients for fast lookups by Liam Eagen, Dario Fiore and Ariel Gabizon.

ZKPunk's ZKPedia