# 概览

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](https://eprint.iacr.org/2023/1284)

DeepSeek

ChatGPT

表示表值 t(x⃗)t(\vec{x})t(x) 在所有见证列 wi(x⃗)w_i(\vec{x})wi​(x) 中出现了 m(x⃗)m(\vec{x})m(x) 次

LogUp GKR

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

算法

区块链

GKRlogUp方案通过分数和证明优化查表论证，采用射影坐标表示分数并构建分层电路进行加法运算。相比传统方法需要O(M)辅助列承诺，GKRlogUp仅需1个额外列，显著降低证明成本。该方案通过二叉树结构逐层合并分数，最终验证根节点值实现高效验证，预计可提升2-10倍证明性能。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

LogUp GKR-腾讯云开发者社区-腾讯云

LogUp GKR

LogUp GKR

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐