FROST-GKR 将一整批重复的 Poseidon2b 计算作为一条全局轨迹证明，而不是逐个归约每次置换。整个批次只需承诺为三个多线性列，所有轮次关系与一致性关系最终归约为两次 sumcheck。在公开的 59 次置换测试中，协议在证明同一关系的前提下，将约束 sumcheck 从 472 次降至 2 次，将原始代数证明载荷从 287,712 字节降至 5,568 字节，并将归约证明者的中位时间从 1,605.931 毫秒降至 150.218 毫秒。收益来自跨整个批次复用同一置换结构，而不是削弱被验证的计算。
重复置换问题
基于哈希的证明系统会反复执行同一种密码学置换。输入会变，轮常数、非线性层与线性映射却不会变。传统逐层算术化经常丢弃这种规律。即便五十九个实例执行完全相同的六十六轮计算，每个置换仍会获得独立列和独立归约序列。
Poseidon2b 是本文研究的二元域密码学置换。它通过六十六个固定轮次变换由四个域元素组成的状态，并在 ParanO(1)d 证明栈中反复用于哈希。
Goldwasser–Kalai–Rothblum（GKR）方法提供多线性扩展与 sumcheck 工具，可把大型计算归约为验证者所选点上的少量求值。
FROST-GKR 从另一种对象出发。它为每次独立的 Poseidon2b 执行分配一个槽位，再把整个批次放入同一个布尔乘积域；另外两个坐标分别是轮次与状态通道。协议不沿独立电路层逐层下降；它对全局执行轨迹作出承诺，再把轨迹上的关系归约为同一组承诺列的打开证明。
三个承诺列
对 B 次活动 Poseidon2b 执行，令 L = 2s 为填充后的槽位数。Poseidon2b 宽度为四，有六十六个非线性轮。FROST 预留 128 个轮次位置，并使用四个状态通道位置，因此完整表满足：
见证数据只有三个多线性列：
z存放进入每一轮的状态和最终状态行；s_in存放活动 S-box 的输入；S-box 是置换中的非线性代换映射；s_out存放对应的 S-box 输出。
验证者抽取关系挑战值之前，三个列都已完成承诺。公开选择器标识活动槽位、活动轮次与活动 S-box 通道。七次幂映射直接在 GF(2128) 上求值：Frobenius 平方让 x² 和 x⁴ 成为线性运算，而计算 x³ 与 x⁷ 只需两次通用乘法。这是实现层面的优势；形式上的 sumcheck 次数仍为七。
两次约束归约
协议承担两项代数任务。首先证明每个局部 Poseidon2b 轮次等式；然后证明具体化的下一轮视图与通道投影视图确实来自原始承诺。
零检验（zero-check）判断一个多项式关系是否在编码执行域的每个点上都为零。sumcheck 协议逐个消去布尔变量，把这项全局断言归约为验证者所选点上的少量求值。最后，多项式承诺方案（PCS）把这些求值绑定到挑战值产生之前已经固定的轨迹列。
全局关系
一次次数为九的零检验同时约束每个有效槽位的 S-box、轮常数、完整与部分线性层以及相邻关系。对按槽位填充的批次，主 sumcheck 始终执行 n 轮；有效置换数量只通过对数级槽位维度影响轮数。
终端包含一次对 Z 的直接求值，以及十一次移位视图或通道投影视图的求值。这十一个断言不能直接改写为 S_in、S_out 和 Z 的打开断言：递增二进制轮次索引并不是多线性变量的仿射变换。
移位视图归约
第二次二次 sumcheck 批量合并十一个线性泛函，并把它们归约为三个承诺多项式在新求值点上的直接求值。最终打开接口小而明确：Z 上有两个点断言，S_in 和 S_out 上各有一个。原生支持多点打开的多项式承诺可以直接处理这些断言；论文还描述了通用的三列终端批处理层。
持久对象始终是承诺执行轨迹。关系使用的每个派生视图，都必须在协议结束前归约回该承诺。
协议证明什么
内部关系证明每个活动槽位都是一次正确的 Poseidon2b 执行。应用仍须约束公开的输入行和输出行。它可以固定公开输入、令一个槽位的输出等于下一槽位的输入，或把最终输出绑定到公开摘要。这些端点等式使用同一个承诺状态列，因此顺序链、树和海绵构造可以组合，而无需重复内部置换关系。
FROST-GKR 是代数归约层，以具备求值绑定性的多线性多项式承诺为参数。完整论证结合其内部归约、应用的端点关系以及所选 PCS；可靠性核算把这三项保持分离。
可靠性与精确核算
对于含 n 个变量的轨迹，内部归约的交互式代数误差满足：
在受测实例中，n = 15 且 F = GF(2128)，因此在计入端点关系与多项式承诺的可靠性误差之前，该项低于 2−119。当发送完整的轮多项式系数向量时，通用交互记录使用 22n + 18 个域元素。
| 阶段 | 轮数 | 次数 | 终端结果 |
|---|---|---|---|
| 承诺 | — | — | 三个已固定的见证多项式 |
| 全局关系 | n | 9 | 在 r′ 的 12 次求值 |
| 移位归约 | n | 2 | 在 r″ 的三个直接断言 |
| 通用终端批处理 | 3n | 2 | 每个承诺列一个断言 |
59 次置换测量
配套实现把 FROST-GKR 与乘积链基线进行比较；该基线为每次置换分别运行一条代数归约序列。两种方案都证明同一批五十九次宽度为四的 Poseidon2b 置换。计时前，测试程序会构造诚实证明、验证两套协议、直接检查最终的多线性扩展（MLE）断言，并逐个域元素核对代数证明的大小。
| 指标 | 逐置换链 | FROST-GKR | 缩减倍数 |
|---|---|---|---|
| 约束 sumcheck 轮数 | 4,248 | 30 | 141.60× |
| sumcheck 总轮数 | 4,263 | 75 | 56.84× |
| 原始代数证明 | 287,712 B | 5,568 B | 51.67× |
论文报告的一次全新发布版复测中，旧方案中位数为 1,605.931 毫秒，FROST 为 150.218 毫秒。仓库另行保留了在 Intel Core i7-1365U 上得到的二十样本结果，二者分别为 1,495.629 与 142.475 毫秒。两组数据测量的都是归约层，而不是完整的简洁证明系统。
字节数只计算原始域元素，不含序列化附加字段、PCS 打开证明和 Merkle 认证路径。测试程序中的直接终端检查用于核验这项对比，不被描述为已经部署的承诺层。
论文与可复现实现
FROST-GKR 是 O(1) Lab 的研究成果。论文作者为 Andrew Boyle，内容包括完整轨迹关系、组合定理、完备性与交互式可靠性论证、交互记录的精确核算和参考对比。
阅读完整论文（PDF），或查看可复现测试环境。