Block–Tiwari FS-FRI · Parano1d Lab

摘要

Parano1d 使用 HistoryStep 验证 State 转换；它是附加于每个已接受区块的递归证明。本文将其实际部署安全参数代入 Block–Tiwari Fiat–Shamir 编译器。广义 RBR 界由 Reed–Solomon 码的列表相关接近度界推出，并显式计入候选切换；期望工作量则在全部正整数查询预算上求取最小值。两个精确最小值均位于 127 到 128 位的整数区间内。

Fiat–Shamir 把交互式 FRI 中验证者的随机币替换为随机预言机输出。恶意证明者可以反复查询该预言机以寻找有利的交互记录，因此伪造的具体成本取决于完整的预言机查询预算。Block 与 Tiwari 将这一成本定义为：在全部正整数查询预算中，成功伪造所需期望随机预言机工作量的最小值。

Parano1d 为每个已接受区块附加一个名为 HistoryStep 的递归证明。它证明把该区块应用于此前已验证的 State 会得到新的 State，并在同一关系内验证前一个 HistoryStep 证明。当前证明由此延续已经验证的 State 转换序列。本文按照 Block–Tiwari 指标评估这一递归 State 证明中的 FS-FRI 部分。

下表前八行由 Block 与 Tiwari 发布；Parano1d 一行采用相同公式、相同的 256 位随机预言机设置以及相同的整位表示方式。

组织	仓库或配置	目标 FRI 安全性	可证明 FS-FRI 安全性	基于猜想的 FS-FRI 安全性
Polygon	Plonky2	100	38	99
StarkWare	stone-prover	96	54	99
StarkWare	SHARP Verifier	96	59	95
dYdX	dYdX Protocol	80	52	79
Polygon Miden	Miden-VM	96 / 128	45 / 67	96 / 128
Lambda Class	lambdaworks	80 / 100 / 128	81 / 99 / 127	81 / 101 / 129
RISC Zero	RISC Zero	100	37	99
Matter Labs	era-boojum	100	50	99
Parano1d	Recursive State proof (HistoryStep)	128	127	127

Parano1d 一行

在已证明 RBR 前提下，精确期望工作量指数为 $127.194502224322\ldots$ 位；采用 Block–Tiwari 猜想 1 时为 $127.207518749639\ldots$ 位。两个精确值都位于 $[127,128)$ ，因此两列均显示 127 位。

Block–Tiwari 指标

设经典敌手至多向随机预言机发出 $Q$ 次查询：

H:\{0,1\}^{*}\longrightarrow\{0,1\}^{\kappa}.

若底层交互式协议的逐轮可靠性误差为 $\varepsilon_{\mathrm{RBR}}$ ，Block 与 Tiwari 的引理 1 给出如下自适应非交互式随机预言机证明误差：

\varepsilon_{\mathrm{BT}}(Q) =\min\!\left\{ 1,\; Q\varepsilon_{\mathrm{RBR}} +\frac{3(Q^2+1)}{2^\kappa} \right\}.

第一项把交互式 RBR 误差计入敌手的全部预言机尝试。二次项是 Fiat–Shamir 编译器的有限成本。外层最小值把成功概率截断在一以内。

包含 $Q$ 次查询的一次攻击，其成功概率至多为 $\varepsilon_{\mathrm{BT}}(Q)$ 。重复攻击直至得到一次成功伪造，所需预言机查询的期望数为

W(Q)=\frac{Q}{\varepsilon_{\mathrm{BT}}(Q)}

因此，定义 1 与定义 2 给出的具体安全性指数为

\lambda_{\mathrm{BT}} =\log_2\!\left( \min_{Q\in\mathbb Z_{>0}}W(Q) \right).

最终整位结果是满足下述条件的最大整数 $k$ ：对每个正整数 $Q$ 都有 $W(Q)\ge2^k$ 。对 $Q$ 的最小化本身就是定义的一部分。

实际部署参数

可执行计算已作为 noid_soundness crate 集成在 Parano1d 中。其实际部署参数加载器直接从证明器和验证器所使用的 crates 中导入全部安全输入，并拒绝被破坏的跨组件对应关系。当前主网版本包含同一份与源码直接关联的计算。

整个实际部署区块容量范围使用同一个安全性计算，只有执行轨迹规模随容量改变。在源代码中，B25 表示最多 25 个有效页面位置所使用的几何，B255 表示 26 至 255 个有效页面位置所使用的几何。两者以相同码率、查询数和挑战分布证明 HistoryStep 关系，因此得到同一个 Block–Tiwari 结果。

133 个查询位置以放回方式独立均匀采样。它们访问同一个原子向量响应中互不重叠的窗口，因此所有被查询窗口都留在可接受一致集合中的概率，正是下文使用的 133 次幂。

输入	实际部署值
执行轨迹规模	B25：初始码字为 2¹⁹，定理分层从 2⁷ 至 2¹⁹。B255：初始码字为 2²¹，定理分层从 2⁹ 至 2²¹。
码率 $\rho$	1/4
BaseFold 查询数 $\ell$	133
承诺执行轨迹所在域	GF(2¹²⁸)
代数挑战支撑集	GF(2²⁵⁶) 中迹为 1 的子集，基数为 2²⁵⁵
随机预言机输出长度 $\kappa$	256 位
单个列表候选的最大代数根数	127
单个列表候选的联合 sidecar 根数	36

挑战支撑集与摘要长度是两个不同输入。代数坏响应概率的分母为 $2^{255}$ ，Fiat–Shamir 编译器项的分母为 $2^{256}$ 。最终的工作量证明 nonce 谓词不会降低 RBR 上界。

已证明的 RBR 前提

RBR 定理针对去除 Merkle 承诺与 grinding 的公开随机币 IOP。令 $m\ge3$ 为 Johnson 列表译码的整数重数，并定义

h=m+\frac12, \qquad \gamma=\frac{m-1}{2m}, \qquad s_N=\frac{N-4}{2N}.

对于长度为 $N$ 、码率为四分之一的 Reed–Solomon 分层，在列表相关一致性定理采用的次数约定下，约化码率为

\rho_N=\frac{N/4-1}{N}=\frac14-\frac1N.

直接展开可得 $s_N^2\lt\rho_N$ 。所需重数条件在每个实际部署分层上均成立：

\left\lceil \frac{\sqrt{\rho_N}} {1-\sqrt{\rho_N}-\gamma} \right\rceil\le m.

将严格有理下界 $s_N\lt\sqrt{\rho_N}$ 代入 Ben-Sasson、Carmon、Haböck、Kopparty 与 Saraf 的定理 4.6，可得异常挑战数的整数上界

A_N(m)=\left\lfloor N\frac{2h^5+3h\gamma s_N^2}{3s_N^3} +\frac{h}{s_N} \right\rfloor.

初始码字对应的严格列表大小界为

L_N(m)=\left\lceil\frac{h}{s_N}\right\rceil-1, \qquad L_{\max}(m)=\max\!\left\{ L_{2^{19}}(m),L_{2^{21}}(m) \right\}.

对 133 个独立采样的查询位置，列表译码的查询逃逸项为

E_q(m)=\left(\frac{m+1}{2m}\right)^{133}.

合并查询逃逸、两组分层调度中的全部接近度异常、候选切换以及联合 sidecar 关系，得到

\begin{aligned} \kappa_H(m)=\max\{& E_q(m),\\ &\max_{N\in\mathcal N_{25}\cup\mathcal N_{255}} \frac{A_N(m)}{2^{255}},\\ &\frac{127L_{\max}(m)}{2^{255}}, \frac{36L_{\max}(m)}{2^{255}} \}. \end{aligned}

其中 $\mathcal N_{25}=\{2^7,\ldots,2^{19}\}$ 、 $\mathcal N_{255}=\{2^9,\ldots,2^{21}\}$ ，每个集合都包含其范围内连续的 2 的幂。

候选切换为何已计入

32 行交错的初始数据被打包成固定 32 次扩域上的一个 Reed–Solomon 码字。该打包保持列 Hamming 距离，并产生一份大小至多为 $L_{\max}(m)$ 的固定初始列表。在每个非异常的行批折叠或位置折叠中，列表相关一致性定理把选定的折叠后候选关联到同一加权一致集合上的相关折叠前候选。加性 NTT 蝶形是可逆的，因此 Haböck 给出的加性 FFT BaseFold 归约可用于实际部署的折叠调度。

每个恢复出的候选与已承诺的基域行在超过 $N/2$ 个位置上一致，而其次数低于 $N/4$ 。Frobenius 共轭与多项式唯一性迫使分解后的各行属于嵌入的 GF(2¹²⁸) 子域。后续每个错误恒等式都是下一个验证者挑战上的非零多项式。对完整初始列表取根集合的并，得到上式中的 127 根项与 36 根项。整个论证不假设证明者始终保留同一候选。

分组 Merkle 轮次只会收缩确定性的折叠路径，不引入未经检查的步骤。加权反向图把单次查询剩余的可接受比例限制为 $(m+1)/(2m)$ ；133 个位置的独立性给出 $E_q(m)$ 。

实际部署验证器的完整根数清单如下：

验证器步骤	单个候选的最大根数
公共输入压缩	7
sidecar 多线性点	19
九组联合 sidecar 批处理	36
ragged-walk sumcheck 轮次	8
zerocheck 坐标压缩	18
zerocheck 插值挑战	127
延迟内部坐标	63
其他 sumcheck 轮次	2
联合 lincheck 或 PCS 声明批处理	1

直线提取器对打包后的初始码字进行列表译码，把每个候选分解为 32 行基域数据，执行加性 NTT 的逆变换，并且只在精确 History 关系成立时保留候选。对不可能产生有效见证的交互前缀做反向归纳，可以证明：任何无见证但最终被接受的交互记录，都必须通过 $\kappa_H(m)$ 中四类事件之一离开该集合。因此这里得到的是广义逐轮知识界，而不只是终端接受概率估计。

精确重数优化

随着 $m$ 增大， $E_q(m)$ 递减，而接近度项与列表大小项不递减。两类项只有一次交叉，因此只需比较相邻的两个重数。精确整数二分查找与一次有理数比较选出

m_*=861824, \qquad L_{\max}(m_*)=1723655.

在 $m_*$ 处，四项精确值为：

RBR 项	精确值
查询逃逸	$(861825/1723648)^{133}$
最大分层接近度异常	$5317717993529868433397264455583323037/2^{255}$
候选切换	$218904185/2^{255}$
联合 sidecar	$62051580/2^{255}$

精确比较表明查询逃逸项最大。因此，输入 Block–Tiwari 编译器的已证明 RBR 前提为

\boxed{ \varepsilon_{\mathrm{RBR}}^{\mathrm{provable}} =\left(\frac{861825}{1723648}\right)^{133}.}

猜想 1 前提

在基于猜想的列中，Block 与 Tiwari 假定目前已知的最佳信息论 FRI 攻击是最优的。此处应使用代数挑战支撑集的基数，而不是承诺执行轨迹所在域的名义大小。代入实际部署的码率、查询数与支撑集基数，得到

\begin{aligned} \varepsilon_{\mathrm{RBR}}^{\mathrm{conjectured}} &=\max\!\left\{2^{-255},(1/4)^{133}\right\}\\ &=\max\!\left\{2^{-255},2^{-266}\right\}\\ &=2^{-255}. \end{aligned}

已证明前提与基于猜想的前提是两个不同的精确概率。接下来它们进入同一个 Fiat–Shamir 编译器与同一个期望工作量优化器。

精确全局优化器

记 $a=\varepsilon_{\mathrm{RBR}}$ 、 $b=3/2^{256}$ 。在编译器误差达到截断值之前，

W(Q) =\frac{Q}{aQ+b(Q^2+1)} =\frac1{a+b(Q+1/Q)}.

对正整数 $Q$ ， $Q+1/Q$ 单调不减，所以 $W(Q)$ 在未截断区间单调不增。误差截断为一之后， $W(Q)=Q$ 严格递增。因此全局最小值只能位于最后一个未截断整数或第一个截断整数。精确二分查找确定边界，再用一次有理数比较选出较小者。

可证明 FS-FRI 安全性

最后一个未截断 Q = 194697534987145646766651744479049925879
第一个截断 Q       = 194697534987145646766651744479049925880
全局最小值位于最后一个未截断 Q

代入已证明 RBR 分数并做精确交叉相乘，得到

2^{127} \le \min_{Q\in\mathbb Z_{>0}}W_{\mathrm{provable}}(Q) \lt 2^{128}.

精确有理数最小值的十进制对数为

\boxed{ \lambda_{\mathrm{BT}}^{\mathrm{provable}} =127.194502224322\ldots\ \text{位}.}

基于猜想的 FS-FRI 安全性

最后一个未截断 Q = 196462116142286827589391637123844718210
第一个截断 Q       = 196462116142286827589391637123844718211
全局最小值位于第一个截断 Q

基于猜想的最小值恰好等于第一个截断查询预算。精确整数比较给出

2^{127} \le \min_{Q\in\mathbb Z_{>0}}W_{\mathrm{conjectured}}(Q) \lt 2^{128},

对应的十进制指数为

\boxed{ \lambda_{\mathrm{BT}}^{\mathrm{conjectured}} =127.207518749639\ldots\ \text{位}.}

两项整位结果由精确的 2 的幂不等式认证，而不是由十进制对数的舍入结果决定。

如何解读比较结果

Parano1d 的可证明值与 Block–Tiwari 已发布表格中的最高可证明整位值相同。其基于猜想的值比 Miden 128 位配置低一位，比 lambdaworks 128 位配置低两位。Parano1d 的两项结果都比设定的 128 位目标低一整位。

Parano1d 两列显示相同，并不意味着已证明前提与猜想 1 相同。两者的 RBR 概率和精确期望工作量最小值仍然不同。256 位随机预言机碰撞项使两个最小值落入同一个整位区间。

复现证书

Parano1d 仓库包含与源码关联的参数、定理特化、精确优化器以及回归测试。以下命令可从当前主网版本复现本文：

git clone https://git.parano1d.org/ignotusnemo/parano1d.git
cd parano1d
git checkout v1.0.1
cargo run --release --locked -p noid_soundness
cargo run --release --locked -p noid_soundness -- --exact
cargo test --release --locked -p noid_soundness

普通运行输出三个整位结果。带 --exact 的运行输出两个 RBR 分数、选定重数、两组截断边界、两个最小化查询预算以及两个精确期望工作量分数。测试固定 W65/H133 参数，覆盖两种实际部署执行轨迹规模，拒绝不一致的跨组件参数，并使用任意精度整数或有理数算术检查每一项 2 的幂证书。

完整推导见 noid_soundness/docs/block-tiwari.md。精确实现分为两部分：src/local.rs 实现 RBR 定理，src/block_tiwari.rs 实现 Block–Tiwari 优化器。

主要原始资料

Ignotus Nemo，Parano1d 内置可靠性证书：与实际部署源码关联的参数、定理特化、精确算术与回归测试。
Alexander R. Block 与 Pratyush Ranjan Tiwari，On the Concrete Security of Non-interactive FRI，重点参见定义 1 与定义 2、引理 1、猜想 1、第 4 节和表 1。
Block 与 Tiwari，FRI Parameter Testing in SageMath。
Alexander R. Block、Albert Garreta、Jonathan Katz、Justin Thaler、Pratyush Ranjan Tiwari 与 Michał Zając，Fiat–Shamir Security of FRI and Related SNARKs。
Eli Ben-Sasson、Dan Carmon、Ulrich Haböck、Swastik Kopparty 与 Shubhangi Saraf，On Proximity Gaps for Reed–Solomon Codes，定理 4.6。
Ulrich Haböck，BaseFold in the List Decoding Regime。

Ignotus Nemo