Block–Tiwari FS-FRI · Parano1d Lab

Abstract

Two inputs are evaluated: the proved History RBR bound and Block–Tiwari Conjecture 1. In both cases, the minimum over the integer query budget is found without floating-point arithmetic.

Block and Tiwari's comparison gives each FRI configuration three entries: the stated target, a provable Fiat–Shamir estimate and an estimate under Conjecture 1. Its first eight rows are reproduced below; the last row applies the same definition and whole-bit convention to History B64/B255.

Organization	Repository or configuration	Target FRI security	Provable FS-FRI security	Conjectured FS-FRI security
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

Reading the Parano1d row

The 128-bit entry is the target. The 92-bit entry follows from the proved History RBR bound; the 126-bit entry uses Block–Tiwari Conjecture 1 instead. As in their table, both exponents are floored to whole bits; the exact certificates appear below.

Why Fiat–Shamir changes the calculation

In interactive FRI, the verifier samples fresh challenges for one transcript. After Fiat–Shamir, those challenges come from a random oracle, which a cheating prover can query repeatedly while searching for a favorable transcript. The attack must therefore be priced across the prover's entire oracle-query budget, not only by the FRI queries inside one attempted proof.

Block and Tiwari formalize this cost in On the Concrete Security of Non-interactive FRI. Starting from a round-by-round (RBR) soundness error for the interactive protocol, they apply the Fiat–Shamir compiler bound and minimize expected oracle work over every query budget.

Let a malicious prover make at most $Q$ classical queries to a random oracle

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

If the underlying interactive protocol has RBR soundness error $\varepsilon_{\mathrm{RBR}}$ , Lemma 1 of Block and Tiwari gives the following adaptive non-interactive random-oracle proof (NIROP) error:

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

The first term charges the interactive RBR error across $Q$ oracle attempts. The quadratic term is the finite cost of compiling the public-coin interaction through Fiat–Shamir. The outer minimum keeps the success probability at most one.

Definition 2 measures work rather than the success probability of one selected budget. A $Q$ -query attempt that succeeds with probability $\varepsilon_{\mathrm{BT}}(Q,\kappa)$ requires

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

expected random-oracle queries to obtain a forgery with probability close to one by repetition. The concrete security exponent is therefore

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

A protocol has $\lambda$ bits under this definition exactly when $W(Q)\ge2^\lambda$ for every positive integer $Q$ . The minimization over $Q$ is part of the metric; choosing a convenient adversarial budget is not.

History B64/B255 inputs

The protocol inputs were checked against Parano1d revision 2cce53fc31a0bc173661bf5e07efaa56d8dc661b. HistoryStep is the recursive proof of a block's exact transition from its parent State to its child State. B64 and B255 enforce the same transition relation with capacities for at most 64 and 255 user-transaction pages. Their BaseFold codewords contain $2^{20}$ and $2^{21}$ positions respectively, but both classes use the same rate and query count.

The exact arithmetic, theorem notes and regression tests used below are published in the Parano1d QROM research repository.

Block–Tiwari input	Value	Role in the calculation
Field	GF(2¹²⁸)	Field-size branch in Conjecture 1
FRI code rate $\rho$	1/4	Agreement and conjectured RBR terms
FRI queries $\ell$	125	Final query-miss probability
Random-oracle output $\kappa$	256 bits	Fiat–Shamir compiler term
Displayed target	128 bits	Target column in the comparison table
Proof-of-work credit	None	The row follows the Block–Tiwari query-work calculation directly

The field size and $\kappa$ are distinct inputs. GF(2¹²⁸) determines the $2^{-128}$ field branch below; the 256-bit digest determines the $2^{-256}$ Fiat–Shamir term. Block and Tiwari likewise fix $\kappa=256$ while comparing protocols over fields of different sizes.

Two RBR premises for one parameter set

The proved History RBR bound

The History RBR theorem analyzes the decommitted public-coin IOP over GF(2¹²⁸). At relative distance $2/5$ , every candidate retained for the final query move agrees with the initial 32-column oracle on at most a $3/5$ fraction unless an earlier verifier challenge falls into a counted exceptional set.

The 32 columns are packed into one Reed–Solomon word over a fixed degree-32 extension. Multiplicity-five list decoding leaves at most eleven initial candidates. List-correlated agreement carries every later fold candidate back to that fixed list. If the prover switches candidates at an algebraic challenge, the bound includes the union of their root sets; it does not assume that one candidate remains fixed. The largest per-candidate algebraic degree is 127.

RBR move family	B64 bound	B255 bound
List-correlated fold exception	28,150,638,096 / 2¹²⁸	56,300,954,059 / 2¹²⁸
Algebraic candidate switching	11 · 127 / 2¹²⁸
Joint sidecar relation	11 · 24 / 2¹²⁸
125 complete query paths	(3/5)¹²⁵

The complete-path term is the largest of these four quantities for both classes. The generalized RBR knowledge error is consequently

\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}.

Outside these bad-response events, the extractor returns a valid History witness. Thus, if the verifier accepts a false statement, the extractor must have failed. The same quantity can therefore be used as the RBR soundness premise for the Block–Tiwari compiler:

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

The Conjecture 1 premise

For the conjectured column, Block and Tiwari model the best known information-theoretic FRI attack as optimal. This gives the RBR premise

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

Substituting the field, rate and query count gives

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

The field branch controls this premise. Both History classes therefore enter the remaining calculation with the same proved value and the same conjectured value.

Why the global optimization reduces to two integers

Write $a=\varepsilon_{\mathrm{RBR}}$ and $b=3/2^{256}$ . Before the probability cap is reached,

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

For positive integer $Q$ , the quantity $Q+1/Q$ is nondecreasing. Thus $W(Q)$ is nonincreasing throughout the uncapped region. After the error reaches one, $W(Q)=Q$ and is strictly increasing. The global minimum is therefore one of two adjacent integers: the largest $Q_0$ whose uncapped error is below one, or $Q_1=Q_0+1$ , the first capped point.

This argument covers every positive integer query budget. Exact integer binary search locates the boundary, and one rational comparison selects between the two candidates.

Exact evaluation of the two columns

Provable FS-FRI security

For $a=(3/5)^{125}$ , put

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

The uncapped error is exactly $N(Q)/D$ . Integer comparison gives the unique cap boundary

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

At $Q_0$ ,

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

Exact rational comparisons establish $W(Q_0)\lt Q_1$ and

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

Hence $Q_0$ is the global minimizer, the certified whole-bit value is 92 and the descriptive exponent is

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

Conjectured FS-FRI security

For $a=2^{-128}$ , the uncapped error has the exact integer form

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

The adjacent cap-boundary integers are

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

The uncapped candidate again gives the smaller work:

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

Exact comparison yields $W(Q_0)\lt Q_1$ and

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

The certified whole-bit value is 126, with descriptive exponent

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

What the two columns show

The provable Parano1d value is higher than every non-lambdaworks value in Block and Tiwari's comparison, including 67 for the Miden 128-bit configuration. Among the three lambdaworks rows, it is above the 80-bit configuration and below the 100- and 128-bit configurations. Block and Tiwari singled out lambdaworks as the only family in their comparison whose proved values stayed close to all of its targets.

The conjectured Parano1d exponent is $1.203373854422\ldots$ bits below the 128-bit target, which appears as 126 after flooring. The difference between the two exact Parano1d exponents is

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

That gap has a precise meaning in this methodology: it is the additional concrete FS-FRI security obtained when the proved RBR premise $(3/5)^{125}$ is replaced by Conjecture 1's $2^{-128}$ premise. It is not a rounding artifact and it is not hidden inside the target column.

Reproducing the integer certificates

The public repository contains the exact optimizer in crates/block-tiwari-rom, with regression tests for both results:

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

No floating-point value is used to decide either reported bit. A reproduction needs arbitrary-precision integers and performs four steps:

instantiate the uncapped numerator for the selected RBR premise;
binary-search the largest positive integer $Q_0$ for which that numerator is smaller than its denominator;
compare $W(Q_0)$ and $Q_0+1$ as exact rationals;
compare the winning rational against consecutive powers of two.

For the proved premise, the two power-of-two tests can be written without division as

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

For the conjectured premise, replace $D$ by $2^{256}$ and $N(Q)$ by $Q2^{128}+3(Q^2+1)$ . The boundary integers printed above are sufficient regression vectors for an independent SageMath, Rust, Python or computer-algebra implementation. The authors' SageMath repository supplies the reference implementation of their broader parameter study.

Primary sources

Ignotus Nemo, Parano1d QROM repository: exact arithmetic, theorem notes, parameter values and regression tests.
Alexander R. Block and Pratyush Ranjan Tiwari, On the Concrete Security of Non-interactive FRI, especially Definitions 1–2, Lemma 1, Conjecture 1, Section 4 and Table 1.
Block and Tiwari, FRI Parameter Testing in SageMath.
Block, Garreta, Tiwari and Zając, Fiat–Shamir Security of FRI and Related SNARKs.
Parano1d revision used for these calculations.
Parano1d soundness under industry metrics, the preceding study of the same History configurations under other published conventions.

Ignotus Nemo