Block–Tiwari FS-FRI · Parano1d Lab

摘要

计算采用两个输入：已证明的 History RBR 界和 Block–Tiwari 猜想 1。两种情况下都在整数查询预算上求得最小值，不使用浮点运算。

在 Block 与 Tiwari 的比较中，每组 FRI 配置对应三个数值：声明的目标、可证明的 Fiat–Shamir 估计，以及采用猜想 1 时的估计。下表前八行来自其论文；最后一行按相同定义和整数位展示方式计算 History B64/B255。

组织	仓库或配置	目标 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	History B64 / B255	128	92	126

如何解读 Parano1d 一行

128 位为目标值。92 位由已证明的 History RBR 界推出；126 位则采用 Block–Tiwari 猜想 1。与原表一致，两项指数均向下取整为整数位；精确证书见后文。

Fiat–Shamir 为何改变安全性计算

在交互式 FRI 中，验证者为一份交互记录抽取新的随机挑战。采用 Fiat–Shamir 后，挑战由随机预言机生成，恶意证明者可以反复查询预言机，寻找有利的交互记录。因此，攻击成本必须按证明者的全部预言机查询预算计算，而不能只看一次证明中的 FRI 查询数。

Block 与 Tiwari 在 On the Concrete Security of Non-interactive FRI 中将这一成本形式化。他们从交互式协议的逐轮（round-by-round，RBR）可靠性误差出发，应用 Fiat–Shamir 编译器界，再对所有查询预算最小化预期的预言机工作量。

设恶意证明者至多向下列随机预言机发出 $Q$ 次经典查询：

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

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

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

第一项把交互式 RBR 误差计入 $Q$ 次预言机尝试。二次项是通过 Fiat–Shamir 编译公币协议所付出的有限代价。外层最小值把成功概率截断在一以内。

定义 2 衡量的是工作量，而不是某个选定预算下一次尝试的成功概率。一次包含 $Q$ 次查询、成功概率为 $\varepsilon_{\mathrm{BT}}(Q,\kappa)$ 的攻击，经重复后要以接近一的概率得到伪造，所需随机预言机查询的期望数为

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

因此，具体安全性指数为

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

按照该定义，协议具有 $\lambda$ 位安全性，当且仅当对每个正整数 $Q$ 都有 $W(Q)\ge2^\lambda$ 。对 $Q$ 的最小化本身就是指标的一部分，不能只选择一个方便的敌手查询预算。

History B64/B255 参数

协议输入已与 Parano1d 版本 2cce53fc31a0bc173661bf5e07efaa56d8dc661b 核对。HistoryStep 是区块从父 State 到子 State 的精确转换所对应的递归证明。B64 与 B255 验证同一转换关系，容量分别覆盖最多 64 页和 255 页用户交易。两类 BaseFold 码字分别包含 $2^{20}$ 和 $2^{21}$ 个位置，但采用相同码率与查询数。

下文计算所用的精确算术、定理说明和回归测试均发布在 Parano1d QROM 研究仓库中。

Block–Tiwari 输入	取值	在计算中的作用
域	GF(2¹²⁸)	猜想 1 中的域大小分支
FRI 码率 $\rho$	1/4	一致率与基于猜想的 RBR 项
FRI 查询数 $\ell$	125	最终查询漏检概率
随机预言机输出长度 $\kappa$	256 位	Fiat–Shamir 编译器项
表中目标	128 位	比较表的目标列
查询前工作量搜索计入	无	该行直接采用 Block–Tiwari 的查询工作量计算

域大小与 $\kappa$ 是两个不同输入。GF(2¹²⁸) 决定下文的 $2^{-128}$ 域大小分支；256 位摘要决定含 $2^{-256}$ 的 Fiat–Shamir 项。Block 与 Tiwari 在比较不同域大小的协议时，同样固定 $\kappa=256$ 。

同一参数集的两种 RBR 前提

已证明的 History RBR 界

History RBR 定理分析 GF(2¹²⁸) 上的公币 IOP，其中承诺已替换为对预言机的直接访问。在相对距离 $2/5$ 下，任何保留到最终查询动作的候选，与初始 32 列预言机的一致位置比例至多为 $3/5$ ；唯一例外是此前某个验证者挑战值落入已明确计数的异常集合。

32 列被打包成固定的 32 次扩域上的一个 Reed–Solomon 码字。重数为 5 的列表译码至多留下 11 个初始候选。列表相关一致性（list-correlated agreement）把后续折叠产生的每个候选追溯到这份固定列表。若在代数挑战处切换候选，界中会计入各候选根集合的并集，而不假设候选始终固定。单个候选的最大代数次数为 127。

RBR 动作类别	B64 界	B255 界
折叠的列表相关异常	28,150,638,096 / 2¹²⁸	56,300,954,059 / 2¹²⁸
代数候选切换	11 · 127 / 2¹²⁸
联合 sidecar 关系	11 · 24 / 2¹²⁸
125 条完整查询路径	(3/5)¹²⁵

对两个类别而言，完整路径项都是这四个量中的最大值。因此，广义 RBR 知识可靠性误差为

\varepsilon_{\mathrm{RBR}}^{\mathrm{proved}} =\max\!\left\{ \frac{U_5(n)}{2^{128}}, \frac{11\cdot127}{2^{128}}, \frac{11\cdot24}{2^{128}}, \left(\frac35\right)^{125} \right\} =\left(\frac35\right)^{125}.

在这些坏响应事件之外，提取器会返回有效的 History 见证。因此，如果验证者接受错误陈述，提取器必然已经失败；同一数值也就可以作为 Block–Tiwari 编译器的 RBR 可靠性前提：

\boxed{ \varepsilon_{\mathrm{RBR}}^{\mathrm{proved}} =\left(\frac35\right)^{125}.}

猜想 1 前提

在基于猜想的列中，Block 与 Tiwari 假定目前已知的最佳信息论 FRI 攻击是最优的。相应的 RBR 前提为

\varepsilon_{\mathrm{RBR}}^{\mathrm{conj}} =\max\!\left\{\frac1{|\mathbb F|},\rho^\ell\right\}.

代入域、码率和查询数，得到

\boxed{ \varepsilon_{\mathrm{RBR}}^{\mathrm{conj}} =\max\!\left\{2^{-128},(1/4)^{125}\right\} =\max\!\left\{2^{-128},2^{-250}\right\} =2^{-128}.}

最大值由域大小分支决定。因此，两类 History 在后续计算中具有相同的已证明取值，也具有相同的猜想取值。

全局优化为何只需检查两个整数

记 $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$ 严格递增。全局最小值必然位于相邻的两个整数之一：未截断误差仍小于一的最大 $Q_0$ ，或首个被截断的点 $Q_1=Q_0+1$ 。

该论证覆盖所有正整数查询预算。用精确整数二分查找定位边界，再做一次有理数比较即可选出两者中的最小值。

两个安全性列的精确计算

可证明 FS-FRI 安全性

对 $a=(3/5)^{125}$ ，定义

D=5^{125}2^{256}, \qquad N(Q)=Q3^{125}2^{256}+3(Q^2+1)5^{125}.

未截断误差精确等于 $N(Q)/D$ 。整数比较给出唯一截断边界：

Q0 = 5,383,859,304,820,033,230,077,561,761   且 N(Q0) < D
Q1 = 5,383,859,304,820,033,230,077,561,762   且 N(Q1) ≥ D

在 $Q_0$ 处，

epsilon_BT(Q0) = 0.999999999999999999999999999827291815635045301984…
W(Q0)          = 5,383,859,304,820,033,230,077,561,761.929836565411835132…

精确有理数比较证明 $W(Q_0)\lt Q_1$ ，并且

2^{92}\le W(Q_0)\lt2^{93}.

因此 $Q_0$ 是全局最小点，经认证的整数位数为 92；其十进制指数为

\boxed{\lambda_{\mathrm{BT}}^{\mathrm{proved}} =92.120699270775770802\ldots\ \text{位}.}

基于猜想的 FS-FRI 安全性

对 $a=2^{-128}$ ，未截断误差具有如下精确整数形式：

\varepsilon_{\mathrm{BT}}^{\mathrm{conj}}(Q) =\frac{Q2^{128}+3(Q^2+1)}{2^{256}}.

截断边界两侧的相邻整数为

Q0 = 147,770,525,858,126,068,760,353,057,306,253,383,503
Q1 = 147,770,525,858,126,068,760,353,057,306,253,383,504

Q0·2^128 + 3(Q0^2+1) <  2^256
Q1·2^128 + 3(Q1^2+1) ≥ 2^256

未截断候选仍给出更小的工作量：

epsilon_BT(Q0) = 0.999999999999999999999999999999999999995931834736…
W(Q0)          = 147,770,525,858,126,068,760,353,057,306,253,383,503.601154920268…

精确比较得到 $W(Q_0)\lt Q_1$ ，并且

2^{126}\le W(Q_0)\lt2^{127}.

经认证的整数位数为 126；其十进制指数为

\boxed{\lambda_{\mathrm{BT}}^{\mathrm{conj}} =126.796626145577656957\ldots\ \text{位}.}

两列数值说明了什么

在 Block 与 Tiwari 的比较中，Parano1d 的可证明数值高于除 lambdaworks 之外的所有数值，包括 Miden 128 位配置的 67。在三组 lambdaworks 参数中，它高于 80 位配置，低于 100 位和 128 位配置。Block 与 Tiwari 特别指出，lambdaworks 是其比较中唯一一个所有可证明数值都接近对应目标的系统族。

Parano1d 基于猜想的指数比 128 位目标低 $1.203373854422\ldots$ 位，向下取整后显示为 126。两个 Parano1d 精确指数之差为

126.796626145577\ldots -92.120699270775\ldots =34.675926874802\ldots\ \text{位}.

在该方法中，这一差值具有明确含义：把已证明的 RBR 前提 $(3/5)^{125}$ 替换为猜想 1 的 $2^{-128}$ 前提时，具体 FS-FRI 安全性增加了这么多。它不是取整造成的误差，也没有被隐藏在目标列中。

复现整数证书

公开仓库中的精确优化器位于 crates/block-tiwari-rom，两项结果均由回归测试验证：

git clone https://github.com/ignotusnemo/parano1d-qrom.git
cd parano1d-qrom

cargo test --release --locked --workspace
cargo run --release --locked -p scenarios -- block-tiwari-rom

两个发布位数的判定均不依赖浮点数。复现只需任意精度整数与四个步骤：

根据选定的 RBR 前提写出未截断误差的分子；
用二分查找求出分子仍小于分母的最大正整数 $Q_0$ ；
以精确有理数比较 $W(Q_0)$ 与 $Q_0+1$ ；
把较小的有理数与相邻的 2 的幂比较。

对已证明的前提，两次二次幂检验无需除法即可写为

2^{92}N(Q_0)\le Q_0D\lt2^{93}N(Q_0).

对基于猜想的前提，把 $D$ 替换为 $2^{256}$ ，把 $N(Q)$ 替换为 $Q2^{128}+3(Q^2+1)$ 。上文给出的边界整数足以作为独立 SageMath、Rust、Python 或其他计算机代数实现的回归向量。作者的 SageMath 仓库提供了其更完整参数研究的参考实现。

主要原始资料

Ignotus Nemo，Parano1d QROM 研究仓库：精确算术、定理说明、参数与回归测试。
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。
Block、Garreta、Tiwari 与 Zając，Fiat–Shamir Security of FRI and Related SNARKs。
这些计算所用的 Parano1d 版本。
行业指标下的 Parano1d 可靠性：采用其他已公开口径研究同一组 History 配置的前一篇文章。

Ignotus Nemo