FROST-GKR

FROST-GKR 是 Parano1d Lab 的研究成果：一种面向 GF(2^128) 上批量 Poseidon2b 执行的全局承诺执行轨迹协议。

FROST 是 Frobenius Reduction over Shifted Tables 的缩写。该协议将整批 四通道 Poseidon2b 执行归约为三个已承诺多线性多项式的打开。

阅读论文 · 阅读 Parano1d Lab 研究文章 · 查看参考实现

重复计算问题

基于哈希的证明系统会反复计算同一个置换。输入虽各不相同，轮常量、S-box 和线性映射却保持不变。若将每次执行都表示为独立电路，同一结构便会反复占用 列并重复执行 sumcheck。

FROST-GKR 将整批计算视为一个对象。每个置换槽位、轮次和置换状态通道都成为 同一布尔乘积域中的一个坐标。协议持久承诺的是整条执行轨迹；全局关系直接归约 为对该承诺的打开。

一条承诺执行轨迹

对于 B 个实际置换，令 L = 2^s >= B 为补齐后的槽位数。Poseidon2b 有四个通道和 66 个非线性轮。FROST-GKR 预留 128 个轮位置，得到布尔域

(slot, round, lane) in {0,1}^s x {0,1}^7 x {0,1}^2。

该域包含 n = s + 9 个变量和 N = 2^n = 512L 个单元。见证数据仅包含 三列：

列	含义
z	每轮入口处的置换状态，包括终止行
s_in	每个有效 x^7 S-box 的输入
s_out	每个有效 x^7 S-box 的输出

在采样任何关系挑战值之前，证明者先对这三列作出承诺。公开选择器标记实际 槽位、有效轮次和有效 S-box 通道。

两次结构归约

一套关系即可约束整批置换：

阶段	轮数	多项式次数	结果
承诺	—	—	固定三个见证多项式
全局关系	n	9	将所有有效轮方程归约为 12 个求值
移位归约	n	2	将 11 个派生视图的断言归约回三个原始承诺列
通用终端批处理	3n	2	为每个承诺列生成一个打开断言

全局 zero-check 同时覆盖 S-box 关系、轮常量、完整与部分线性层以及相邻轮次 之间的关系。其终端值包含原始列的求值，以及按轮次移位和按通道投影后的视图。

二进制轮索引加一并不是多线性变量上的仿射变换，因此 FROST-GKR 显式证明 这些移位视图。一次次数为二的 sumcheck 将全部 11 个派生求值合并，再归约为新点上 对 S_in、S_out 和 Z 的直接断言。

两次归约完成后，只剩四个点值断言：两个属于 Z，另外两个分别属于两列 S-box。支持原生多点打开的承诺方案可以直接打开这些值；论文同时给出了通用的 三列终端批处理层。

二进制域的作用

协议实例化在 GF(2^128) 上。在特征二中，Frobenius 平方映射是线性的，并且

x^7 = x^4 * x^3，其中 x^3 = x^2 * x。

因此，实现只需两次通用域乘法和专门的平方运算即可计算直接 S-box。这是实现 层面的优势；sumcheck 的形式次数仍为七，掩码后的全局关系对每个变量的次数为九。

端点组合

z 列公开每个置换槽位的输入行和输出行。应用使用内部关系所依赖的同一承诺 来约束这些端点。线性端点方程可以表达：

• 相互独立的哈希调用；
• 连续置换链；
• Merkle 树；
• 海绵结构；
• 状态转换图。

这就是协议的集成接口。FROST-GKR 一次性认证整批 Poseidon2b 执行，端点关系 再将已认证槽位连接成应用图。求值绑定性保证两套关系不能使用彼此不同的执行轨迹。

可靠性与成本

若多线性多项式承诺具有求值绑定性，且交互式挑战值彼此独立采样，则通用协议 的代数可靠性误差满足

对于论文中 $\mathbb{F}=\mathrm{GF}(2^{128})$ 上的 15 变量实例，该值小于 $2^{-119}$；此后还需计入端点关系和多项式承诺的可靠性误差项。论文列出了 完整的失败事件账本，其中包括主 zero-check、移位归约和终端批处理。

当 Poseidon2b 的宽度和轮次安排固定时，证明者的工作量为 $O(N)$ 次域运算， 承诺见证包含 $3N$ 个域元素。两次结构约束归约共使用 $2n$ 轮 sumcheck。 采用完整的轮系数向量和通用终端批处理时，在加入承诺打开和序列化封装之前， 代数交互记录包含 $22n+18$ 个域元素。

参考实现结果

公开实验实现使用同一组包含 59 次连续置换的工作负载，在相同底层域、原生置换 实现和交互记录通道上，将 FROST-GKR 与保留的逐置换乘积链归约进行比较。

指标	乘积链	FROST-GKR	变化
约束 sumcheck 数量	472	2	减少 236.00 倍
约束轮数	4,248	30	减少 141.60 倍
sumcheck 总轮数	4,263	75	减少 56.84 倍
代数交互记录	287,712 B	5,568 B	缩小 51.67 倍
归约阶段证明者耗时中位数	1,605.931 ms	150.218 ms	加速 10.69 倍
归约阶段验证者耗时中位数	984.269 ms	66.499 ms	加速 14.80 倍

测量使用 Intel Core i7-1365U、发布模式的原生 CPU 代码、三次预热和 20 组 交错样本。交互记录大小按未压缩域元素统计。多项式承诺打开与序列化封装均未 计入两列数据，因此该比较只衡量论文所述的归约部分。

在 Parano1d 中的作用

这项研究源自 Parano1d 的证明系统。协议在共享二进制证明栈内部承担整批 Poseidon2b 执行的归约；应用关系将其承诺端点连接到钱包授权、Merkle 计算和 State 计算，外围 FRI-Binius/BaseFold 层则在无需可信设置的情况下闭合所得 多线性断言。

因此，FROST-GKR 既是一项可复用的研究成果，也是 Parano1d 证明架构的具体 组成部分。论文作者为 Andrew Boyle；FROST-GKR 是 Parano1d Lab 的研究成果。