概览

logUp 是一种高效的查表论证方案，其核心是证明一个“分数和”为零：

$$ \sum_{\vec{x}} \left( \frac{m(\vec{x})}{\alpha - t(\vec{x})} - \sum_{i=1}^M \frac{1}{\alpha - w_i(\vec{x})} \right) = 0 $$

  • 表示表值 $t(\vec{x})$ 在所有见证列 $w_i(\vec{x})$ 中出现了 $m(\vec{x})$ 次
  • 传统做法：为了将分数和转换为多项式求和，需要为每个分数项引入辅助列 $h_i(\vec{x})=\frac{1}{\alpha - w_i(\vec{x})}$，为每一列单独生成承诺，并额外证明满足约束 $(\alpha - w_i(\vec{x}))\cdot h_i(\vec{x})=1$
  • 痛点：M 个见证列需要 O(M) 个额外的辅助列承诺。

作者引入 GKR 协议来直接证明上述分数和，无需生成任何辅助列。

  • 电路构造：将分数和的计算建模为一个分层电路（Layer 0 到 Layer n），每层进行射影坐标下的分数加法 $(a,b)+ (c,d)=(ad+bc,bd)$
  • 成本对比： 传统 logUp：需承诺 M+1 个辅助列， GKR logUp：仅需承诺 1 个额外列（即 multiplicity 列 $m(X)$）
  • 优势：虽然算术运算翻倍，但省去了大量昂贵的承诺操作（尤其是在基于椭圆曲线或哈希的承诺方案中），预计可带来 2 到 10 倍 的证明者性能提升。

GKR 分数和检查的构造

问题重构：从分数和到电路求值

1. 原始目标

证明者需要证明以下等式在随机点 α 处成立：

$$ \sum_{\vec{x} \in H_n} \frac{m(\vec{x})}{\alpha - t(\vec{x})} - \sum_{i=1}^M \frac{1}{\alpha - w_i(\vec{x})} = 0 $$

2. 射影表示（Projective Representation）

为了在电路中处理分数，我们不再将 $\frac{1}{(α−w)}$视为一个域元素，而是将其表示为一对域元素 $(p,q)$，满足 $\frac{q}{p}=\frac{1}{(α−w)}$。即：

  • 分子 $p=1$
  • 分母 $q=α−w$

3. 分数加法规则

电路的核心操作是合并两个分数。给定两个分数 (a,b)和 (c,d)，它们的和定义为：

$$ (a, b) + (c, d) = (a \cdot d + c \cdot b,\ b \cdot d) $$

这恰好对应了通分相加的规则：$\frac{b}{a}+\frac{d}{c}=\frac{ad+cb}{bd}$。

电路构造：分层合并分数

GKR 分数和检查构造了一个深度为 n（$∣H_n∣=2^n$）的二叉树状电路。$H_n$ 表示 n 维布尔超立方体 $\{±1\}^n$

1. 输入层（第 n层）

  • 每个叶子节点对应超立方体 $H_n$ 上的一个点 $\vec{x}$
  • 每个节点存储一个分数对 $(p_n(\vec{x}),q_n(\vec{x}))$

  • 对于 logUp 问题，该层的值直接由查表约束定义：

    • 对于表侧（左侧）：$p_n(\vec{x})=m(\vec{x})$, $q_n(\vec{x})=α−t(\vec{x}) $
    • 对于见证侧（右侧）：$p_n(\vec{x})=1$, $q_n(\vec{x})=α−w_i(\vec{x}) $（需适当处理多个见证列）

2. 中间层（第 k层，0<k<n）

电路从第 n 层（叶子）开始，逐层向上合并，每一层的节点数是上一层的一半。对于第 k 层的任意节点 $\vec{x}∈\{0,1\}^k$，其值由其两个子节点 $\vec{x_0}$ 和 $\vec{x_1}$通过分数加法规则计算：

$$ \begin{aligned} p_k(\vec{x}) &= p_{k+1}(\vec{x_0}) \cdot q_{k+1}(\vec{x_1}) + p_{k+1}(\vec{x_1}) \cdot q_{k+1}(\vec{x_0}) \\ q_k(\vec{x}) &= q_{k+1}(\vec{x_0}) \cdot q_{k+1}(\vec{x_1}) \end{aligned} $$

其中，$\vec{x_0}=(\vec{x}, -1), \vec{x_1}=(\vec{x}, +1)$，表示将 ±1 追加到 $\vec{x}$

3. 输出层（第 0层）

  • 最终只剩下一个根节点，其值为 $(p_0,q_0)$

  • 根据递归构造，这个根节点存储的值正是整个超立方体上所有分数之和的通分结果：

    $$ \frac{p_0}{q_0}=\sum_{x∈H_n}\frac{p_n(\vec{x})}{q_n(\vec{x})} $$

  • 验证者只需检查 $p_0=0$（且 $q_0\ne0$）即可验证原分数和为零。

递归 Sumcheck

当前层的 claim

假设 verifier 当前有：

$$ p_k(\vec r_k)=a $$

为了合并两个 claim，verifier 采样随机数：

$$ \lambda_k\leftarrow \mathbb F $$

然后只证明一个随机线性组合：

$$ p_k(\vec r_k)+\lambda_k q_k(\vec r_k) = a+\lambda_k b $$

如果 prover 能骗过这个随机线性组合，那么除非两个 claim 的错误刚好被 $\lambda_k$ 抵消，否则概率很小。

把 $p_k,q_k$ 写成关于下一层的 sum

因为：

$$ p_k(\vec X) = \sum_{\vec y\in H_k} L_k(\vec X,\vec y) \left( p_{k+1}(\vec y,+1)q_{k+1}(\vec y,-1) + p_{k+1}(\vec y,-1)q_{k+1}(\vec y,+1) \right) $$

所以：

$$ p_k(\vec r_k)+\lambda_k q_k(\vec r_k) $$

等于：

$$ \sum_{\vec y\in H_k} L_k(\vec r_k,\vec y) \Big( p_{k+1}(\vec y,+1)q_{k+1}(\vec y,-1) + p_{k+1}(\vec y,-1)q_{k+1}(\vec y,+1) + \lambda_k q_{k+1}(\vec y,+1)q_{k+1}(\vec y,-1) \Big) $$

这就是一个普通 sumcheck：

$$ \sum_{\vec y\in H_k} F_k(\vec y)=c_k $$

其中：

$$ F_k(\vec y) = L_k(\vec r_k,\vec y) \Big( p_{k+1}(\vec y,+1)q_{k+1}(\vec y,-1) + p_{k+1}(\vec y,-1)q_{k+1}(\vec y,+1) + \lambda_k q_{k+1}(\vec y,+1)q_{k+1}(\vec y,-1) \Big) $$

Sumcheck 结束后得到什么

对第 $k$ 层做完 sumcheck 后，verifier 会得到一个随机点：

$$ \vec \rho_k\in \mathbb F^k $$

并需要检查下一层在两个点上的值：

$$ p_{k+1}(\vec \rho_k,+1), \quad q_{k+1}(\vec \rho_k,+1) $$

也就是说，一个 sumcheck 把第 $k$ 层 claim 变成了第 $k+1$ 层的 two-point claims。

但如果每一层都保留两个点，claim 数量会爆炸。

所以 GKR 要再做一次随机合并。

two-point claim 如何合并成 single-point claim

论文里 verifier 采样：

$$ \mu_k\leftarrow \mathbb F $$

然后令：

$$ \vec r_{k+1} = (\vec \rho_k,\ 1-\mu_k) $$

因为 $p_{k+1}$ 和 $q_{k+1}$ 对最后一个变量是 multilinear，所以如果知道：

$$ p_{k+1}(\vec \rho_k,+1) $$

和：

$$ p_{k+1}(\vec \rho_k,-1) $$

就可以线性插值得到任意点：

$$ p_{k+1}(\vec \rho_k,z) $$

特别是：

$$ z=1-\mu_k $$

同理对 $q_{k+1}$。

于是两个点的 claim 被压缩成一个随机点 claim：

$$ p_{k+1}(\vec r_{k+1}), \quad q_{k+1}(\vec r_{k+1}) $$

这一步就是递归的关键：

$$ \text{第 }k\text{ 层 single-point claim} \Rightarrow \text{第 }k+1\text{ 层 single-point claim} $$

参考

Improving logarithmic derivative lookups using GKR

DeepSeek

ChatGPT