Block–Tiwari FS-FRI · Parano1d Lab

Abstract

Parano1d validates State transitions with HistoryStep, the recursive proof attached to every accepted block. Its production security parameters are instantiated under the Block–Tiwari Fiat–Shamir compiler. A generalized RBR bound is derived from list-correlated Reed–Solomon proximity bounds with candidate switching included explicitly, and the expected-work minimum is solved over every positive integer query budget. Both exact minima lie in the whole-bit interval from 127 to 128.

Fiat–Shamir turns the verifier coins of interactive FRI into random-oracle outputs. A malicious prover may query that oracle repeatedly while searching for a favorable transcript, so the concrete cost of a forgery depends on the complete oracle-query budget. Block and Tiwari define this cost as the minimum expected random-oracle work of a successful forgery over every positive integer query budget.

Parano1d attaches a recursive proof called HistoryStep to every accepted block. It proves that applying the block to the previously validated State produces the new State, and it verifies the preceding HistoryStep proof inside the same relation. The current proof therefore carries the verified sequence of State transitions forward. This article evaluates the FS-FRI component of that recursive State proof under the Block–Tiwari metric.

The first eight rows below are the configurations reported by Block and Tiwari. The Parano1d row uses the same equations, the same 256-bit random-oracle setting and the same whole-bit presentation.

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	Recursive State proof (HistoryStep)	128	127	127

The Parano1d row

The exact expected-work exponents are $127.194502224322\ldots$ for the proved RBR premise and $127.207518749639\ldots$ under Block–Tiwari Conjecture 1. Both exact values lie in $[127,128)$ , so both columns display 127 bits.

The Block–Tiwari metric

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

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

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

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

The first term carries the interactive RBR error across the adversary's oracle attempts. The quadratic term is the finite Fiat–Shamir compiler cost. The outer minimum caps the success probability at one.

A $Q$ -query attempt succeeds with probability at most $\varepsilon_{\mathrm{BT}}(Q)$ . Repeating the attempt until one forgery succeeds requires

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

expected oracle queries. Definitions 1 and 2 therefore give the concrete security exponent

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

The whole-bit result is the largest integer $k$ such that $W(Q)\ge2^k$ for every positive integer $Q$ . The minimization over $Q$ is part of the definition.

Production parameters

The executable calculation is integrated into Parano1d as the noid_soundness crate. Its production parameter loader imports every security input directly from the crates used by the prover and verifier and rejects a broken cross-component correspondence. The current mainnet release contains the same source-linked calculation.

The security calculation is identical across the full production block-capacity range. Only the trace size changes. B25 covers up to 25 effective page positions, while B255 covers 26 through 255. Both prove the HistoryStep relation with the same code rate, query count and challenge distribution, so they produce one Block–Tiwari result.

The 133 query positions are sampled independently and uniformly with replacement. They address disjoint windows of one atomic vector response, so the probability that every queried window remains inside the accepting agreement set is the 133rd power used below.

Input	Production value
Trace size	B25: initial codeword 2¹⁹, theorem layers 2⁷ through 2¹⁹. B255: initial codeword 2²¹, theorem layers 2⁹ through 2²¹.
Code rate $\rho$	1/4
BaseFold queries $\ell$	133
Committed trace field	GF(2¹²⁸)
Algebraic challenge support	Trace-one subset of GF(2²⁵⁶), cardinality 2²⁵⁵
Random-oracle output $\kappa$	256 bits
Maximum algebraic roots per list candidate	127
Joint sidecar roots per list candidate	36

The challenge support and digest length are separate inputs. Algebraic bad-response probabilities have denominator $2^{255}$ ; the Fiat–Shamir compiler term has denominator $2^{256}$ . The final proof-of-work nonce predicate contributes no RBR credit.

The provable RBR premise

The RBR theorem is stated for the de-Merkleized and de-grinded public-coin IOP. Let $m\ge3$ be an integer Johnson multiplicity and define

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

At a rate-one-quarter Reed–Solomon layer of length $N$ , the reduced rate in the degree convention of the list-correlated theorem is

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

Direct expansion gives $s_N^2\lt\rho_N$ . The required multiplicity condition holds on every production layer:

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

Instantiating Theorem 4.6 of Ben-Sasson, Carmon, Haböck, Kopparty and Saraf, with the strict rational lower bound $s_N\lt\sqrt{\rho_N}$ , gives the integral exceptional-challenge envelope

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

The corresponding strict list-size bound for an initial codeword is

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

For 133 independently sampled query positions, the list-decoding escape term is

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

Combining query escape, every proximity exception in the two layer schedules, candidate switching and the joint sidecar relation gives

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

Here $\mathcal N_{25}=\{2^7,\ldots,2^{19}\}$ and $\mathcal N_{255}=\{2^9,\ldots,2^{21}\}$ , with consecutive powers of two in each set.

Why candidate switching is included

The 32 interleaved initial rows are packed into one Reed–Solomon word over a fixed degree-32 extension. Packing preserves column Hamming distance and produces one initial list of size at most $L_{\max}(m)$ . At every nonexceptional row-batch or position fold, list-correlated agreement restores a selected post-fold candidate to correlated pre-fold candidates on the same weighted agreement set. The additive-NTT butterfly is invertible, so the additive-FFT BaseFold reduction of Haböck applies to the production fold schedule.

Every restored candidate agrees with the committed base-field rows on more than $N/2$ positions while its degree is below $N/4$ . Frobenius conjugation and polynomial uniqueness force the decomposed rows into the embedded GF(2¹²⁸) subfield. Later false identities are nonzero polynomials in the next verifier challenge. Taking the union of their roots over the complete initial list yields the 127-root and 36-root terms above. No step assumes that the prover keeps one candidate fixed.

Grouped Merkle epochs only contract deterministic fold paths and introduce no unchecked move. A weighted backward graph bounds the remaining accepting fraction for one query by $(m+1)/(2m)$ ; independence of the 133 positions gives $E_q(m)$ .

The complete production root inventory is:

Verifier move	Maximum roots for one candidate
Public-input compression	7
Sidecar multilinear point	19
Joint nine-group sidecar batch	36
Ragged-walk sumcheck round	8
Zerocheck coordinate compression	18
Zerocheck interpolation challenge	127
Deferred inner coordinate	63
Other sumcheck rounds	2
Joint lincheck or PCS claim batching	1

A straight-line extractor list-decodes the packed initial word, decomposes every candidate into 32 base-field rows, inverts the additive NTT and retains a candidate only when the exact History relation succeeds. Backward induction over doomed prefixes shows that an accepting transcript without a witness must leave the doomed set through one of the four events in $\kappa_H(m)$ . This establishes a generalized RBR knowledge bound, not only a terminal acceptance estimate.

Exact multiplicity optimization

As $m$ grows, $E_q(m)$ decreases while the proximity and list-size terms do not decrease. Their unique crossing leaves two adjacent multiplicities to compare. Exact integer binary search and one rational comparison select

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

The four terms at $m_*$ are:

RBR term	Exact value
Query escape	$(861825/1723648)^{133}$
Maximum layer proximity exception	$5317717993529868433397264455583323037/2^{255}$
Candidate switching	$218904185/2^{255}$
Joint sidecar	$62051580/2^{255}$

Exact comparison makes the query-escape term the maximum. The proved RBR input to the Block–Tiwari compiler is therefore

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

The Conjecture 1 premise

For the conjectured column, Block and Tiwari model the best known information-theoretic FRI attack as optimal. The relevant floor is the algebraic challenge support rather than the nominal committed-trace field size. Substituting the production rate, query count and support gives

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

The proved and conjectured premises are different exact probabilities. They now enter the same Fiat–Shamir compiler and expected-work optimizer.

The exact global optimizer

Write $a=\varepsilon_{\mathrm{RBR}}$ and $b=3/2^{256}$ . Before the compiler error reaches its cap,

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

For positive integral $Q$ , $Q+1/Q$ is nondecreasing, so $W(Q)$ is nonincreasing throughout the uncapped region. Once the error is capped at one, $W(Q)=Q$ is strictly increasing. The global minimum is therefore either the final uncapped integer or the first capped integer. Exact binary search locates the boundary; one rational comparison selects the winner.

Provable FS-FRI security

last uncapped Q = 194697534987145646766651744479049925879
first capped Q  = 194697534987145646766651744479049925880
global minimizer = last uncapped Q

Substitution of the proved RBR fraction and exact cross-multiplication give

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

The descriptive logarithm of the exact rational minimum is

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

Conjectured FS-FRI security

last uncapped Q = 196462116142286827589391637123844718210
first capped Q  = 196462116142286827589391637123844718211
global minimizer = first capped Q

The conjectured minimum is the first capped query budget itself. Exact integer comparison gives

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

with descriptive exponent

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

The power-of-two inequalities, rather than the decimal logarithms, certify the two displayed whole-bit values.

Reading the comparison

The Parano1d provable value matches the highest provable whole-bit value in the published Block–Tiwari table. Its conjectured value is one bit below the Miden 128-bit configuration and two bits below the lambdaworks 128-bit configuration. Both Parano1d values are one whole bit below the assigned 128-bit target.

Equality of the displayed Parano1d columns does not identify the proved premise with Conjecture 1. Their RBR probabilities and exact expected-work minima remain different. The 256-bit random-oracle collision term places both minima in the same whole-bit interval.

Reproducing the certificate

The Parano1d repository contains the source-linked parameters, theorem specialization, exact optimizer and regression tests. Reproduce the calculation from the current mainnet release with:

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

The ordinary run prints the three whole-bit entries. The --exact run prints both RBR fractions, the selected multiplicity, both cap boundaries, both minimizing query budgets and both exact expected-work fractions. The test suite pins the W65/H133 parameters, covers both production trace sizes, rejects inconsistent cross-component parameters and checks every power-of-two certificate with arbitrary-precision integer or rational arithmetic.

The complete derivation is available in noid_soundness/docs/block-tiwari.md. The exact implementation is split between src/local.rs for the RBR theorem and src/block_tiwari.rs for the Block–Tiwari optimizer.

Primary sources

Ignotus Nemo, integrated Parano1d soundness certificate: source-linked production parameters, theorem specialization, exact arithmetic 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.
Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari and Michał Zając, Fiat–Shamir Security of FRI and Related SNARKs.
Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty and Shubhangi Saraf, On Proximity Gaps for Reed–Solomon Codes, Theorem 4.6.
Ulrich Haböck, BaseFold in the List Decoding Regime.

Ignotus Nemo