This blog-post is a short introduction to our new work: “WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification”. This is joint work with Gal Arnon, Alessandro Chiesa, and Eylon Yogev, and the full version is available on ePrint . Code is also available at WizardOfMenlo/whir.

WHIR 🌪️

We present WHIR (Weights Help Improving Rate), a concretely efficient IOPP for constrained Reed–Solomon codes¹.

WHIR is both an IOPP for Reed–Solomon codes and a multilinear polynomial commitment scheme (PCS), and achieves the fastest verification speed of any such scheme, even including univariate PCS with trusted setup. It does so while mantaining state-of-the-art argument size and verifier hash complexity for hash-based schemes, requiring only transparent setup and guaranteeing post-quantum security.

As a multilinear and univariate PCS, WHIR achieve by far the smallest verification time across all scheme that we tested. Taking $d = 2^{24}$ as an example:

• At the 100-bit security level, a WHIR proof verification takes between 610μs (with $\rho = 1/2$) to 290μs (with $\rho = 1/16$). This is a speedup of between 5700×-12000× against Brakedown, 1200×- 2500× against Ligero, 164×-345× against Hyrax, 13×-27× against PST and 4.0×-8.3× against KZG.
• At the 128-bit security level, a WHIR proof verification takes between 1.4ms to 700μs achieving a speedup of between 2600×-5300× against Brakedown, 535×-1100× against Ligero, 93×-186× against Greyhound, 108×-216× against Hyrax, 7×-14× against PST and 2.6×-5.2× against KZG.

As a hash-based multilinear PCS, WHIR compares favourably to BaseFold in (i) argument size (ii) verifier time (iii) verifier hashes.

Taking $d = 2^{24}$ and $\rho = 1/2$ as an example, at the 100-bit security level:

• WHIR’s arguments are 101 KiB vs BaseFold’s 7.95 MiB (74× better).
• WHIR’s verifier runs in 610μs vs BaseFold’s 24ms (39× better).

As a low-degree test, WHIR achieves best-in-class verifier time, while mantaining state-of-the-art argument size and verifier hash complexity. Taking $d = 2^{24}$ and $\rho = 1/2$ as an example, at the 128-bit security level:

• WHIR’s arguments occupy 157 KiB vs STIR’s 160 KiB and FRI’s 306 KiB (1.95× better).
• WHIR’s verifier perform 2.7k hashes vs STIR’s 2.6k and FRI’s 5.6k (2.1× better).
• WHIR’s verifier runs in 1.0ms vs STIR’s 3.8ms and FRI’s 3.9ms (3.8× better).

Applications

We present a few applications that we believe WHIR is a natural candidate for.

Ethereum on chain verification

Currently, most onchain verification is done with Groth16 over a BN254 curve. The benefits of such verification is that the proof is constant size and verification is supposed to cheap, keeping both data availability (DA) costs and compute costs low. Currently, this verification costs ~280k gas . We believe that, WHIR can offer significantly competitive compute costs for onchain proof verification (and we are working on a Solidity verifier to confirm this thesis). A rough back-of-the-envelope calculation follows. On the compute side: a WHIR verifier for a polynomial of size $2^{24}$ and rate $1/2$ performs around 1.5k hashes (using 100-bits of security to compare with BN254). Assuming the hash used is Keccak, and that each of these hashes is for Merkle tree verification (and thus hashes together 64 bytes), each of these hashes costs 48 gas. Thus, the cost of hash-verification is around 96k gas. Estimating the cost of the field operations is harder, but they tend account for a much smaller portion of the verification costs (on native experiments) compared to the hashing. Increasing the rate to $1/16$ this cost can be reduced even further, to around 53k gas. On the data side, calldata is currently priced at 16 gas per non-zero byte. A WHIR proof for $2^{24}$ variables is between 101 KiB to 48 KiB, resulting in between 1.6m gas and 790k gas.
Overall then, the cost for a WHIR proof verification can be as low as 850k gas (while still using a not excessively small rate, this can be reduced further), all while not requiring a trusted setup and providing post-quantum security. Further, the cost can be ammortized by aggregation, which WHIR is also very suitable for (next).

Recursive verification

Due to the small number of hashes, WHIR’s verifier (as STIR’s was) is a natural candidate for recursion. Again, let’s do some back-of-the-envelope calculation. At the 128-bit security level, for a computation of size $2^{28}$, starting with rate $1/2$, WHIR’s recursive circuit performs $3.4$k hashes. Assuming both use Poseidon hashing and that each hash contributes ~400 R1CS constraints, the WHIR’s recursive circuit size is approximately of size $2^{20}$. Then, running WHIR with even a large rate is a negligible cost (compared to the initial computation), leading to a tiny final proof. For example, running a computation of that size with rate $1/32$ gives a 64KiB proof in less than 3s (on my M1 Macbook), that verifies in less that $350µ$s while performing only 800 hashes.

zkLogin

Various blockchains such as Sui and Aptos have new onboarding and login strategy which make heavy use of zero-knowledge proofs. Currently, taking Sui’s zkLogin as an example, the final circuit is around the size of a million of constraints and is currently proven by using a Groth16 proof system. WHIR could be used instead, reducing both proving time and verification time (which now is native!).

Bitcoin verification

There are efforts to bringing verification of STARKs on Bitcoin. In that setting, field operations are much expensive than hashing (say 5000-2500x). Since WHIR has both extremely small arithmetic and hashing complexity, WHIR’s verifier can significantly reduce the cost of verification on Bitcoin compared to FRI and STIR.

High-level overview

We first introduce constrained Reed–Solomon codes, then we describe the main protocol and sketch its complexity.

Constrained Reed–Solomon codes

WHIR is an expressive IOPP for a generic class of codes, that we call constrained Reed–Solomon codes. Recall that the Reed–Solomon code over field $\mathbb{F}$, domain $L \subseteq \mathbb{F}$ and rate $\rho = 2^m/|L|$ is defined as $\mathsf{RS}[\mathbb{F}, L, m] = \{ f: L \to \mathbb{F}: \exists \hat{p} \in \mathbb{F}^{< 2^m}[X] : \hat{p}(L) = f(L)\}$. Equivalently, one can view a univariate polynomial of degree $2^m$ as a multilinear polynomial over $m$ variables, and one can recover evaluations of the former from the evaluations of the latter on points of the form $(x, x^2, \dots, x^{2^{m-1}})$. Thus, we rewrite $\mathsf{RS}[\mathbb{F}, L, m] = \{ f: L \to \mathbb{F}: \exists \hat{p} \in \mathbb{F}^{< 2}[X_1, …, X_m] \text{ s.t. } \forall x \in L ; \hat{p}(x, \dots, x^{2^{m-1}}) = f(x) \}$. For any codeword $f \in \mathsf{RS}[\mathbb{F}, L, m]$, we let $\hat{f}$ denote the corresponding multilinear polynomial.

Constrained Reed–Solomon codes are defined by a constraint, which consists of a weight polynomial $\hat{w}\in \mathbb{F}[Z, X_1, \dots, X_m]$ and of a target $\sigma \in \mathbb{F}$:

$$ \mathsf{CRS}[\mathbb{F}, L, m, \hat{w}, \sigma] := \{ f \in \mathsf{RS}[\mathbb{F}, L, m] : \sum_{\mathbf{b}} \hat{w}(\hat{f}(\mathbf{b}), \mathbf{b}) = \sigma \} $$

Note, for example, that by setting $\hat{w}(Z, X_1, \dots, X_m) = Z \cdot \mathsf{eq}(\mathbf{z}, X_1, \dots, X_m)$² for some $\mathbf{z} \in \sigma$ the constrained code exactly captures Reed–Solomon codewords whose corresponding polynomial evaluates to $\sigma$ at $\mathbf{z}$.

WHIR

WHIR is an IOPP of proximity for constrained Reed–Solomon codes. WHIR makes use of both the sumcheck techniques introduced in [ZFC24]³ and of the rate improvement techniques in [ACFY24]⁴.

Let $k$ be a folding parameter, $\delta \in (0, 1 - \rho)$⁵ a proximity parameter and $t$ a repetition parameter. A WHIR iteration reduces testing that $$ f \in \mathsf{CRS}[\mathbb{F}, L, m, \hat{w}, \sigma] $$ to testing that $$ g \in \mathsf{CRS}[\mathbb{F}, L^2, m - k, \hat{w}’, \sigma’],$$ for related $g, \hat{w}’, \sigma’$.

Further, if $f$ was $\delta$-far from the original code, then, unless with probability approximately $(1 - \delta)^t$, $g$ will be $(1 - \rho’)$-far from the smaller code, where $\rho’ = 2^{1 - k} \cdot \rho$ is the code of this new code.

The iteration consists of the following steps:

1. Sumcheck rounds. The prover and the verifier engage in $k$ rounds of the sumcheck protocol for the claim $$ \sum_{\mathbf{b}} \hat{w}(\hat{f}(\mathbf{b}), \mathbf{b}) = \sigma $$ where $\hat{f}$ is the multilinear polynomial associated with $f$. At the end of the interaction, the prover will have sent quadratic $(\hat{h}_1, \dots, \hat{h}_k)$ while the verifier will have sampled randomness $(\alpha_{1},\dots,\alpha_{k})\in \mathbb{F}^k$. This reduces the initial claim to the simpler claim $$ \sum_{\mathbf{b}} \hat{w}(\hat{f}(\alpha_1, \dots, \alpha_k, \mathbf{b}), \alpha_1, \dots, \alpha_k, \mathbf{b}) = \sigma $$
2. Claimed codeword. The prover sends a function $g: L^2 \to \mathbb{F}$. In the honest case, $g$ is the codeword associated to the $(m - k)$-variate multilinear polynomial $\hat{f}(\alpha_1, \dots, \alpha_k, \cdot)$.
3. Out-of-domain sample. The verifier samples and sets $z_0 \gets \mathbb{F}$. We let $\mathbf{z}_0 := (z_0, \dots, z_0^{2^{m-1}})$.
4. Out-of-domain answer. The prover replies with $y_0$. In the honest case $y_0 := \hat{g}(\mathbf{z}_0)$.
5. Shift queries and combination randomness. For every $i \in [t]$, the verifier samples $z_i \gets L^{2^k}$, computes $y_i := \mathsf{Fold}(f, (\alpha_1, \dots, \alpha_k))(z_i)$ by querying $f$⁶, and sets $\mathbf{z}_i := (z_i, \dots, z_i^{2^{m-1}})$. It then samples $\xi \gets \mathbb{F}$ and sends $z_1, \dots, z_t, \xi$ to the prover.
6. Recursive claim. Prover and verifier set: $$ \hat{w}’(Z, \mathbf{X}) := \hat{w}(Z, \alpha_1, \dots, \alpha_k, \mathbf{X}) + Z \cdot \sum_{i = 0}^t \xi^{i + 1} \cdot \mathsf{eq}(\mathbf{X}, \mathbf{z}_i) $$ and $$ \sigma’ := \hat{h}_k(\alpha_k) + \sum_{i = 0}^t \xi^{i + 1} y_i $$

At each iteration, the verifier performs exactly $t$ queries to the function being tested each of which reads $2^k$ field elements, performs $O(k)$ field operations to check the sumcheck claims and $O(t \cdot 2^k)$ fops to compute the folds⁷. Additionally, in the final iteration the verifier will have to evaluate a final weight polynomial $\hat{w}$ which contains $O(\sum_i t_i)$ equality polynomials over at most $m$ variables (plus the initial weight).

The soundness analysis relies on a new property of Reed–Solomon codes, that we call mutual correlated agreement. This is a strenghtening of correlated agreement [BCIKS20]⁸, which we show holds in the unique decoding regime. We are confident to conjecture that it also holds in the list-decoding regime. Further, we believe that WHIR can be proven sound from weaker assumptions still. We refer the reader to the paper for more details.

Benchmarks

We implemented WHIR in Rust, and evaluated its performance. Our code can be found at WizardOfMenlo/whir . We thank in particular Remco Bloemen for his invaluable help in optimizing the prover performance of WHIR.

We present some of our comparisons here, and refer the reader to Section 6 of the paper for full details.

Comparison with BaseFold

WHIR achieves significantly smaller argument size compared to BaseFold[ZFC24]³, while achieving significantly faster proving and verification. In part, this is due to WHIR having a more optimized implementation.

Comparison with other PCSes

WHIR achieves the fastest verification time of any PCS know thus far. In particular, this includes schemes such as PST and KZG which rely on both a trusted setup and on pairings of elliptic curves.

Comparision with LDTs

Finally, WHIR achieves state-of-the-art argument size, verifier hash-complexity among low-degree tests, while not compromising prover performance and achieving best-in-class verifier performance.

Citation

G. Arnon, A. Chiesa, G. Fenzi, E. Yogev. “WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification”. Cryptology ePrint Archive, Paper 2024/1586. Available at: https://ia.cr/2024/1586 .

@misc{ArnonCFY,
	author       = {Gal Arnon and Alessandro Chiesa and Giacomo Fenzi and Eylon Yogev},
	title        = {WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification},
	howpublished = {Cryptology ePrint Archive, Paper 2024/1586},
	year         = {2024},
	note         = {\url{https://eprint.iacr.org/2024/1586}},
	url          = {https://eprint.iacr.org/2024/1586}
}

Related material

This blog-post is a short introduction to our new work: “zkSNARKs in the ROM with Unconditional UC-Security”. This is joint work with Alessandro Chiesa, and the full version is available on ePrint.

The Universal Composability (UC) [Can01]¹ framework is a “gold-standard” for security in cryptography. UC-secure protocols achieve strong security guarantees against powerful adaptive adversaries, and retain these guarantees when used as part of larger protocols. Zero knowledge succinct non-interactive arguments of knowledge are often used within larger protocols deployed in dynamic environments, and so UC-security is a highly desirable, if not necessary, goal.

In this work, we show that widely studied and deployed zkSNARKs in the ROM are UC-secure without modifications. Our main theorem states that:

zkSNARKs constructed by instantiating the [BCS]² construction with a suitable IOP are unconditionally UC-secure

Above, suitable IOPs are those that zero-knowledge and (state-restoration) knowledge sound, which are the same conditions required for the BCS construction to yield zero-knowledge and knowledge sound arguments in the ROM. So, achieving UC-secure zkSNARKs require no additional strengthening of the building blocks used to construct those zkSNARKs.

Unconditional in our setting refers to the fact that our zkSNARKs are secure in the pure random oracle model, and the security is statistical and depends only on the number of queries the environment makes to the random oracle. Further, we also show that the zkSNARKs that we consider are UC-secure in the face of adaptive corruptions.

Finally, all our results come with concrete security bounds, which inform how to set parameters in real systems.

Modelling

We consider UC-security in the UC with global subroutines framework [BCHTZ20]³, and the global subroutine that we consider is that of the restricted observable programmable global random oracle model [CDGLN18]⁴. This GROM has an interface consisting of four methods: a query method, a programming method, a observe method and a is-programmed method. The query method models a standard random oracle query. The programming method allows every party in the security experiment to program the GROM, and this power is kept “in check” by the is-programmed method, which allows honest parties to detect whether a point was programmed or not. By this, the simulator is the only party that is allowed to program the GROM undetectably. Finally, the observe method allows gathering the queries made to the GROM by parties outside of the session. Roughly, in Micali and BCS, programming is required for zero-knowledge, while observability for knowledge soundness. Since in our setting we target unconditional UC-security, we slightly modify the UC-framework to account for environments that are computationally unbounded and whose only limits are in the number of time they can access “resources”. To do so, we introduce a mechanism of budgets. In our main experiment, the budgets will reflect GROM queries and programming queries and queries to the proving and verification interface.

UC-friendly properties

Our UC-security proof is modular. We show that any argument (in the ROM) that satisfies three strong security properties yields a UC-secure argument. The three properties we define are:

1. UC-friendly completeness
2. UC-friendly zero knowledge
3. UC-friendly knowledge soundness

We further show that these properties are in fact necessary for UC-security, giving us confidence that they really are the “right ones”.

In each setting we consider adversaries that have adaptive access to random, programming, prover and verifier oracles. Each property then reflects a corresponding property in the ROM that should be upheld in the face of this strong adversarial model.

1. UC-friendly completeness states that such an adversary cannot cause the prover oracle to output proofs that are not subsequently accepted. Since the adversary has access to a programming oracle, perfect completeness of the underlying argument is in fact not sufficient, and we show a separation. We further puth forth a set of convenient properties that, together with perfect completeness, imply UC-friendly completeness.
2. UC-friendly zero knowledge states that the adversary cannot distinguish between two security experiments, in the first of which the prover oracle returns honestly generated proofs and in the latter those proofs are in fact generated by a simulator (which has no access to the witness). Again, we show that adaptive zero knowledge in the ROM does not suffice for achieving this UC-friendly security notion.
3. UC-friendly knowledge soundness states that an adversary cannot produce instance-proof pairs that validate successfully but from which an extractor is unable to extract a valid witness (for the corresponding instance). This is a strengthening of simulation extractability to our strong adversarial model. In fact, here we do not know of a separation, and we leave figuring out if one exists to future work.

Micali and BCS security

In light of the previous section, to show that the Micali and BCS construction are UC-secure showing that the satisfy these UC-friendly properties suffices. We focus on Micali for simplicity here, but the case for BCS is entirely analogous.

1. UC-friendly completeness follows from perfect completeness of Micali and by showing that it satisfy two properties that we call monotone proofs and unpredictable queries. Roughly, since the prover queries will be unpredictable and the verifier only queries what the prover has previously queried, the adversary cannot use programming to influence verification.
2. UC-friendly zero knowledge follows by a careful analysis of the Micali zero knowledge simulator (which requires zero knowledge of the underlying PCP) and by showing that Merkle trees satisfy a notion of UC-friendly hiding.
3. UC-friendly knowledge soundness was harder to prove, but ultimately comes down to reducing to straightline state-restoration knowledge soundness of the underlying PCP (which is implied by knowledge soundness of the PCP) and an analysis of Merkle trees that show that they satisfy a notion of UC-friendly extraction suitable for this reduction.

We note that, by restricting the adversarial capabilities, our work also shows a full end-to-end proof that Micali and BCS are perfectly complete, adaptive zero knowledge and (straightline) simulation knowledge sound.

Adaptive corruptions

Finally, we strengthen each of the properties to show that Micali and BCS in fact satisfy a stronger still notion of UC-security: they are secure in the face of adversaries that can adaptively corrupt parties in the security experiment and force them to reveal the randomness used thus far. This requires a strengthening of the underlying information theoretical building blocks, and we both show PCPs that satisfy this notion and by inspection conclude that common zero knowledge IOPs already satisfy this strengthening.

Citation

A. Chiesa, G. Fenzi. “zkSNARKs in the ROM with Unconditional UC-Security”. Cryptology ePrint Archive, Paper 2024/724. Available at: https://ia.cr/2024/724 .

@misc{ChiesaFenzi24,
	author       = {Alessandro Chiesa and Giacomo Fenzi},
	title        = {zkSNARKs in the ROM with Unconditional UC-Security},
	howpublished = {Cryptology ePrint Archive, Paper 2024/724},
	year         = {2024},
	note         = {\url{https://eprint.iacr.org/2024/724}},
	url          = {https://eprint.iacr.org/2024/724}
}

Related material

This blog-post is a short introduction to our new work: “STIR: Reed-Solomon Proximity Testing with Fewer Queries”. This is joint work with Gal Arnon , Alessandro Chiesa , and Eylon Yogev , and the full version is available on ePrint . Code is also available at WizardOfMenlo/stir . Here are also some slides that might be helpful, the recording of the talk at zkSummit11 , and our episode on zkPodcast . This paper won Best Paper Award 🥇 at CRYPTO 2024!

Denote by $\mathsf{RS}[\mathbb{F}, \mathcal{L}, d]$ the Reed-Solomon (RS) code¹ over the field $\mathbb{F}$ of rate $\rho = d/|\mathcal{L}|$. Testing proximity to a RS code is the problem of, given oracle access to $f: \mathcal{L} \to \mathbb{F}$, determining whether

• $f \in \mathsf{RS}[\mathbb{F}, \mathcal{L}, d]$ i.e., $f$ is a RS codeword.
• $\Delta(f, \mathsf{RS}[\mathbb{F}, \mathcal{L}, d]) > \delta$ i.e., $f$ is $\delta$-far (in terms of Hamming distance) from any RS codeword.

In this work, we consider Interactive Oracle Proofs of Proximity (IOPP) for RS codes, i.e., interactive protocols between a prover and a verifier that aims to test proximity to a RS code in which the prover sends oracle messages.

The FRI protocol [BBHR18, BCIKS20]^{2 3} is one such IOPP, and underlies many SNARK-based real-world systems which offer state-of-the-art technology that protects billions of dollars’ worth of transactions in blockchains.

STIR 🥣

We present STIR (Shift To Improve Rate), a concretely efficient IOPP for RS codes that achieves the best known query complexity of any concretely efficient IOPP for this problem.

When compiled into an argument, STIR compares favourably to FRI in (i) argument size (ii) verifier time (iii) verifier hashes.

Taking $d = 2^{24}$ and $\rho = 1/2$ as an example:

• STIR arguments’ have size 160 KiB compared to FRI’s 306 KiB (1.8x better).
• STIR verifier’s perform 2600 hashes compared to FRI’s 5600 (2.13x better).
• STIR verifier’s runtime is 3.8ms compared to FRI’s 3.9ms (1.03x better).

High-level overview

The core intuition behind STIR is that decreasing rate makes proximity testing easier. Intuitively, the lower the rate the more redundant the code is, and thus the verifier can make use of more structure in its testing.

Fix $k$ a “folding parameter”, a proximity parameter $\delta$, and a repetition parameter $t$.

Let $\mathcal{C} := \mathsf{RS}[\mathbb{F}, \mathcal{L}, d]$ and $\mathcal{C’} := \mathsf{RS}[\mathbb{F}, \mathcal{L}’, d/k]$ with $|\mathcal{L}’| = |\mathcal{L}|/2$ be two RS codes, and let $\rho, \rho’$ be their rates.

A STIR iteration performs $t$ queries while fulfilling two roles:

1. Reduces testing proximity of $f$ to $\mathcal{C}$ to testing proximity of a new (virtual) function $f’$ to $\mathcal{C’}$.
2. Amplifies distance. Roughly, if $f$ is $\delta$-far from $\mathcal{C}$, then $f’$ is $(1 - \sqrt{\rho’})$-far⁵ from $\mathcal{C’}$ (except with probability roughly $(1 - \delta)^t$, we dub this a “bad event”).

Testing proximity to $\mathcal{C}’$ is now easier. First, the polynomial has had its degree reduced by a factor of $k$. Second, note that $\rho’ = (2/k) \cdot \rho$, so if $k > 2$ then $\rho’ < \rho$, so the rate has improved.

Imagine now applying $M$ STIR iterations. Let $f_i, t_i$, $\mathcal{L}_i$ be the functions tested, repetition parameters and domains at each round. Let also $\rho_i := (2/k)^i \cdot \rho$ and $d_i = d/k^i$. At the end of those iterations, the (honest) prover will send a polynomial $\hat{p}$ of degree $d_M$. The verifier then checks at $t_M$ points of $\mathcal{L}_M$ that $f_M(x) = \hat{p}(x)$.

Let’s analyse soundness of this protocol. First, we bound the probability of a bad event happening at each iteration. At the first round, this probability is $(1 - \delta)^{t_0}$. In later rounds, since the distance was amplified the probability is now: $$ (1 - (1 - \sqrt{\rho_i}))^{t_i} = \rho_i^{t_i/2} $$ If none of these bad events happen, then the polynomial $\hat{p}$ must be at distance $(1 - \sqrt{\rho_M})$ from $\mathcal{C}_M$, and so the final check will detect this with probability at least $1 - \rho_M^{t_M/2}$.

The overall soundness error of this protocol is then: $$ \varepsilon \leq (1 - \delta)^{t_0} + \sum_{i = 1}^M \rho_i^{t_i/2}. $$

Aiming each term in the above sum to be $\leq 2^{-\lambda}$ so that $\varepsilon \leq (M+1) \cdot 2^{-\lambda}$, leads to setting $t_0 = \frac{\lambda}{- \log (1 - \delta)}$ and $t_i = \frac{\lambda}{- \log \sqrt{\rho_i}}$.

The improved rate, translates in a decrease in the values of $t_i$ (apart from the first iteration). This is where STIR gains its efficiency.

In FRI, for example, the rate is unchanged between iterations, so each round (apart from the first) will query its corresponding oracle at least $\frac{\lambda}{- \log \sqrt{\rho}}$ times. In fact, since FRI does correlated queries, the number of queries will be the same at each round as the first one, and at least $\max \left\{\frac{\lambda}{-\log (1 - \delta)}, \frac{\lambda}{- \log \sqrt{\rho}}\right\}$. Roughly then, the total number of queries of the FRI protocol is: $$ O\left(\lambda \log d \cdot \max \left\{ \frac{1}{-\log (1-\delta)}, \frac{1}{-\log \sqrt{\rho}} \right\}\right) $$

STIR instead can perform only: $$ O\left(\frac{\lambda}{-\log (1 - \delta)} + \log d + \lambda \cdot \log \left(\frac{\log d}{-\log \sqrt{\rho}}\right)\right) $$

Techniques

A STIR iteration roughly consists of the combination of two steps:

Folding

As in FRI, folding is the process of reducing the degree of a polynomial from $d$ to $d/k$ by decomposing it into $k$ polynomials of degree $d/k$ and taking a random combination of them. We rely mainly on two properties of folding:

1. Folding preserves distance (except with probability at most $1 - \mathrm{poly}(|\mathcal{L}|)/\mathbb{F}$, which, assuming a large field, is very small).
2. Folding is local. Given oracle access to $f$, computing the value of the fold $f$ at a point in the folded domain is efficient (and involves querying $f$ at exactly $k$ locations).

Quotienting

The quotient of a function $f$ w.r.t to a function $p: S \to \mathbb{F}$ is the function of $X$ defined as: $$ \frac{f(X) - \hat{p}(X)}{\prod_{a \in S} (X - a)} $$ where $\hat{p}$ is the polynomial interpolating $p$ over $S$. We rely on two properties of quotients:

1. If all low-degree polynomials close to $f$ disagree with $p$, then the quotient is far from the RS code.
2. Quotienting is local. Given oracle access to $f$, computing the value of the quotient at a point is efficient (and involves querying $f$ at a single location).

The STIR iteration

We describe, at a high level, an iteration of STIR. Let $\mathcal{L}^k = \{ x^k : x \in \mathcal{L} \}$.

1. Folding-randomness: The verifier samples and sends $\alpha \gets \mathbb{F}$.
2. Fold: The prover sends $g$, the evaluation of the folding $\hat{g}$ of $f$ around $\alpha$ over $\mathcal{L}’$. (Note, the folding would be a function $\mathcal{L}^k \to \mathbb{F}$ where $|\mathcal{L}^k| = |\mathcal{L}|/k$, while here $\mathcal{L’}$ is a domain of size $|\mathcal{L}|/2$.)
3. Out-of-domain sample: The verifier samples and sends $x \gets \mathbb{F}$.
4. Out-of-domain reply: The prover sends $y = \hat{g}(x)$.
5. Shift-queries: The verifier samples $v_1, \dots, v_t \gets \mathcal{L^k}$ and queries $f$ to compute the value of the folding of $f$ at these points (using the local mapping). Denote these values as $y_1, \dots, y_t$.
6. New-oracle: The verifier sets $p$ to be the function $p(x) = y$, $p(v_i) = y_i$. The new function $f’$ to be tested is then the quotient of $g$ w.r.t $p$.

Roughly, the soundness analysis is the following:

1. The folding step preserves distance (except with small probability).
2. The out-of-domain sample guarantees that there is at most one codeword $u$ within $1 - \sqrt{\rho’}$ distance of $g$ which has $\hat{u}(x) = y$ (except with small probability).

Now, if there is no such codeword, then $f$ will be $1 - \sqrt{\rho’}$ far from the RS code, since it is a quotient and $p(x) = y$. If instead such a codeword exists, by the first point $\hat{u}$ can agree with the fold on at most a $1 - \delta$ fraction of the domain (since the fold preserves distance). If any of the sampled points $v_i$ are in the disagreement portion, then again the quotient will be $1 - \sqrt{\rho’}$ far from the RS code. Thus this happens unless with probability $(1 - \delta)^t$.

Benchmarks

We implemented STIR and FRI in Rust and compared their performance. Our code can be found at WizardOfMenlo/stir . Below, we present the results of our benchmarks when $\rho = 1/2$

Comparison of FRI and STIR. FRI is red, STIR is blue.

STIR obtains better argument size and verifier hash complexity than FRI for all tested parameters. The overall verifier runtime is also faster then FRI, especially for large degrees. Taking $d = 2^{24}$ and $\rho = 1/2$ as an example:

• STIR arguments’ have size 160 KiB compared to FRI’s 306 KiB (1.8x better).
• STIR verifier’s perform 2600 hashes compared to FRI’s 5600 (2.13x better).
• STIR verifier’s runtime is 3.8ms compared to FRI’s 3.9ms (1.03x better).

For a more detailed comparison, see Section 6 of the paper.

Practical considerations

We consider the prover costs of STIR. In practice, FRI is run in a heavily batched context i.e., instead of testing proximity of a single polynomial to a RS code, a random linear combination of a list of polynomials $f_1, \dots, f_\ell$ is tested. The dominating prover cost is then that of committing to the polynomials, which involves performing $\ell$ FFTs to compute the evaluations of the $f_i$s over $\mathcal{L}$ and then committing to said evaluation. This cost is shared by both FRI and STIR, and, especially in this batch setting, comes to dominate. The rest of the proximity test, which is where STIR is slower than FRI, is independent of the number of polynomials committed. So, changing from FRI to STIR should have an almost negligible effect on prover runtime.

Further, STIR’s improvement in query complexity enable new parameter tradeoffs in which one can achieve better prover time, argument sizes and verifier hash complexity than FRI. For example, [ethSTARK]⁶ uses FRI with $d = 2^{22}$ and $\rho = 1/4$. In our experiments, FRI’s prover runs in 11s, yields arguments of size 154 KiB which can be verified by performing $\approx 2800$ hashes. Instead, running STIR with $d = 2^{22}$ and $\rho = 1/2$ yields a prover which runs in 10s, has arguments of size 143 KiB and a verifier which performs $\approx 2200$ hashes. More generally, in the batched setting, we expect the dominating costs of both FRI and STIR to be proportional to $\ell \cdot d/\rho$. If the improvements in argument size/verifier hash allow to set a larger rate (say by a factor of 2), the dominating cost of the STIR prover would as well decrease by that factor.

Citation

G. Arnon, A. Chiesa, G. Fenzi, E. Yogev. “STIR: Reed–Solomon Proximity Testing with Fewer Queries”. Cryptology ePrint Archive, Paper 2024/390. Available at: https://ia.cr/2024/390 .

@misc{ArnonCFY,
	author       = {Gal Arnon and Alessandro Chiesa and Giacomo Fenzi and Eylon Yogev},
	title        = {STIR: Reed–Solomon Proximity Testing with Fewer Queries},
	howpublished = {Cryptology ePrint Archive, Paper 2024/390},
	year         = {2024},
	note         = {\url{https://eprint.iacr.org/2024/390}},
	url          = {https://eprint.iacr.org/2024/390}
}

Related material

This blog-post is a short introduction to our new work: “A Time-Space Tradeoff for the Sumcheck Prover”. This is joint work with Alessandro Chiesa, Elisabetta Fedele, Andrew Zitek-Estrada, and the full version is available on ePrint. Code accompanying this work can be found at space-efficient-sumcheck.

The sumcheck protocol [LFKN92]¹ is an interactive protocol between a prover and a verifier that allows a verifier to succinctly check claims of the form $$ \sum_{\mathbf{b} \in \{0, 1\}^n} p(\mathbf{b}) = \gamma \enspace. $$

In this note, we consider the case where $p \in \mathbb{F}[X_1, \dots, X_n]$ is a multi-linear polynomial, and write $N = 2^n$ for the size of the prover input. For concrete deployments, maximising the prover’s efficiency is paramount, as both its time and space complexity can be bottlenecks. Previous to this work, two main algorithms to efficiently implement the sumcheck prover were known

• [CTY11]²: which runs in time $O(N \log N)$ and uses space $O(\log N)$.
• [VSBW13]³: which runs in time $O(N)$ and uses space $O(N)$.

Blendy 🍹

We introduce Blendy, a new family of algorithms for the sumcheck prover which run in time $O(k N)$ and use space $O(N^{1/k})$. Before, $k$ is a parameter that regulates the Time-Space tradeoff of our algorithms.

Our algorithms, at an high level, divides the $n$ rounds of sumcheck into $k$ stages. At the start of each stage, it performs a precomputation to populate a table of size $O(N^{1/k})$, which is then used to compute the polynomials related to that particular stage.

We implement our algorithms (which is made available at space-efficient-sumcheck ) and observe that our algorithm has a similar time-complexity to the state-of-the-art ([VSBW13]³) while using much less memory. Concretely, for $n = 28$, [VSBW] runs in 20.4s while using 5.2 GiB of memory, while Blendy (with $k = 2$) runs in 21.8s while using 1MiB of memory: a 0.93x slowdown traded for a 650x improvement in memory usage.

Citation

A. Chiesa, E. Fedele, G. Fenzi, A. Zitek-Estrada. “A Time-Space Tradeoff for the Sumcheck Prover”. Cryptology ePrint Archive, Paper 2024/524. Available at: https://ia.cr/2024/524 .

@misc{ChiesaFFZ24,
	author       = {Alessandro Chiesa and Elisabetta Fedele and Giacomo Fenzi and Andrew Zitek-Estrada},
	title        = {A Time-Space Tradeoff for the Sumcheck Prover},
	howpublished = {Cryptology ePrint Archive, Paper 2024/524},
	year         = {2024},
	note         = {\url{https://eprint.iacr.org/2024/524}},
	url          = {https://eprint.iacr.org/2024/524}
}

Related material

This blog-post is a short introduction to our new work: “SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions”. This is joint work with Martin Albrecht, Oleksandra Lapiha and Ngoc Khanh Nguyen, and the full version is available on ePrint . Here are also some slides that might be helpful.

In our previous paper , we looked at the problem of constructing efficient lattice-based polynomial commitments, to be used in as a drop-in replacement to non-post-quantum secure schemes such as KZG. In doing so we constructed two schemes making use of the techniques in [WW23]¹ to obtain succinct verification and extractability. The schemes that we came up two came with a number of caveats namely:

• a common reference string of quadratic size in the degree of the polynomial to commit
• reliance on a non-standard assumption: powerBASIS.
• one of our schemes achieves polylogarithmic verification time, but has non-negligible (inverse polynomial) soundness error.
• the other scheme instead has negligible soundness error, but only quasi-polylogarithmic verification time.

In this work, we address all of these issues and obtain a lattice-based polynomial commitment scheme with:

• polylogarithmic common reference string size
• quasi-linear commitment time
• polylogarithmic verification time
• negligible soundness error (without parallel repetition)
• security that reduces to the hardness of Module-SIS, a standard lattice assumption.

Roadmap

Refer to the previous blog post for a refresher on polynomial commitment schemes and more.

Construction of a polynomial commitment scheme is a two-step process:

1. Construction of a commitment scheme
2. Designing of a proof system for the statement “$f(u) = z$ and $\mathbf{t}$ is a commitment to $f$”.

We take a brief look at both of these steps.

Merkle-PRISIS commitment

In order to achieve succinct verification, we require that the first commitment is compressing. Further, we would like the scheme to be binding for arbitrary vectors in $\mathcal{R}_q$.

Our starting point is a “toy” 2-to-1 commitment scheme. Below, for some fixed $w, \mathbf{A}$, and denoting by $\mathbf{G}$ the “gadget matrix” let $$ \mathbf{B} = \begin{bmatrix} \mathbf{A} & & - \mathbf{G} \\ & w\mathbf{A}& -\mathbf{G} \end{bmatrix} \enspace. $$

• $\mathsf{Setup}(1^\lambda) \to (\mathsf{pk}, \mathsf{vk})$ samples $\mathbf{A}, w$ and uses [MP12]² sampling to construct a trapdoor $\mathbf{T}$ of $\mathbf{B}$. The verification key consists of $\mathbf{A}, \mathbf{W}$ and the proving key additionally contains $\mathbf{T}$.
• $\mathsf{Com}(\mathsf{pk}, f_0, f_1) \to (\sigma, \mathsf{aux})$ sets $\mathbf{t}_b := f_b \cdot \mathbf{e}_1$. It then uses $\mathbf{T}$ to sample short $\mathbf{s}_0, \mathbf{s}_1$ and $\hat{\mathbf{t}}$ such that $\mathbf{B}[\mathbf{s}_0, \mathbf{s}_1, \hat{\mathbf{t}}]^\top = [-\mathbf{t}_0, -\mathbf{t}_1]^\top$, it then outputs $\mathbf{t} := \mathbf{G}\hat{\mathbf{t}}$ and $(\mathbf{s}_b)_b$ as decommitment.
• $\mathsf{Open}(\mathsf{vk}, f, \sigma, \mathsf{aux})$ checks that the openings are indeed short, and that the equations are all satisfied: namely it checks that, for $b \in \{0,1\}$, $$w^b \mathbf{A}\mathbf{s}_b + \mathbf{t} = \mathbf{t}_b \enspace.$$

This scheme is binding under a 2-arity version of the PRISIS assumption introduced in our previous work, which we had shown to Module-SIS! With this observation, the natural next step is to use this “toy” scheme recursively, and construct a “Merkle tree”-like structure. To do so, we sample a matrix and a trapdoor for each layer of the tree, and commit to the commitments originating for the bottom layer. Note that this achieves already the efficiency goals that we had set for ourselves, as building a Merkle tree only requires a linear number of invokations of the inner commitment scheme. Does this overall scheme satisfy the binding property? Well, in fact if you look at the commitment that is used in the inner nodes of the tree, that is not by itself binding. However, we show that the overall construction is binding under a multi-instance version of the PRISIS assumption of arity 2! We then provide a reduction of this multi-instance assumption to the single instance version, which combined with our previous observation reduces binding to Module-SIS. We further show a direct tighter reduction from multi-instance arity 2 PRISIS to Module-SIS, which we use for parameters later on.

Evaluation protocol

The evaluation protocol that we design is conceptually very similar to the one that we developed in our previous work. We take inspiration from FRI and Bulletproofs. In each round of the protocol, the prover splits the polynomial in $2^k$ components (when $k=1$, components correspond to the odd and even coefficients). It sends evaluations of these polynomials and partial opening corresponding to the $k$-th layer of the tree. and receives randomness from the verifier, that it uses to compute a new polynomial, of degree roughly $d/2^k$, that corresponds to the random linear combination of those components. Prover and verifier then can efficiently update the common reference string, instance and witness and recurse on the claim.

By itself, this protocol achieves polylogarithmic verifier and communication complexity, but inherits many of the drawbacks of the previous protocol, namely the inverse polynomial soundness error. To improve, while avoiding parallel repetition, we make use of the techniques of [BHRRS21]³, combined with the amortization techniques that we had talked about in our previous work. Our new protocol (as our old) has efficient proof aggregation, in the sense that proving many statements of the form $\{ f_i(u) = z_i \}_{i \in [r]}$ has cost roughly equivalent to proving a single claim. To amplify soundness, we prove the same claim multiple times, and use the aggregation techniques in order to mantain efficiency. An appropriate setting of parameters then enables us to have an evaluation protocol that has polylogarithmic verifier and communication complexity, and negligible knowledge soundness error. In particular, this means that we can compile the protocol to a non-interactive argument using the Fiat-Shamir transform, and achieve a sound non-interactive polynomial commitment scheme with polylogarithmic proof sizes, common reference string, and quasi-linear time prover.

The scheme here presented is for proving evaluations of polynomials over polynomial rings, while most uses of polynomial commitments in the wild are concerned with finite fields. While we could make use of the techniques in the previous work to obtain such a scheme, we also present a new generic transformation that could be of independent interest.

Instantiations

We performed an evaluation of the concrete efficiency of our scheme, details of which you can find in the full version. Concretely, proof sizes for a polynomial of degree $d = 2^{20}$ are around 36 MB, which makes the scheme concretely inefficient. Some of these inefficiencies are inherent in the [MP12]² trapdoor sampling techniques that we make use of, some from the high number of repetitions that our techniques require. Reaching concrete efficiency is left for, ambitious, future work.

Citation

M. R. Albrecht, G. Fenzi, O. Lapiha, N. K. Nguyen. “SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions”. In: Proceedings of the 43rd Annual International Conference on Theory and Application of Cryptographic Techniques. EUROCRYPT ‘24. 2024.

@inproceedings{AlbrechtFNL23,
  author    = {Martin R. Albrecht and Giacomo Fenzi and Ngoc Khanh Nguyen and Oleksandra Lapiha},
  title     = {SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions},
  booktitle = {Proceedings of the 43rd Annual International Conference on Theory and Application of Cryptographic Techniques},
  series    = {EUROCRYPT~'24},
  year      = {2024},
}

Related material

In this blog-post, I will be taking a look at my recent work with Hossein Moghaddas and Ngoc Khanh Nguyen, full version . We extend the vector commitment scheme of [WW23]¹ with an evaluation proof, and achieve a lattice-based polynomial commitment scheme with polylogarithmic proof size and verifier complexity. We further investigate the applicability of our techniques to the Polynomial IOP of [Marlin]², show that our scheme is easily batchable and more!

Polynomial Commitments

A polynomial commitment scheme is a natural generalization of a vector commitment scheme, in which a party is able to commit to a polynomial $f$, and later engage in a evaluation protocol to show that $f(u) = z$. In this work, we consider polynomials of bounded degree $d$ with coefficients over the polynomial ring $\mathcal{R}_q$ (we also show to adapt this construction for polynomials in $\mathbb{F}^{\leq d}[X]$, but details are left for the full version).

The interface of a polynomial commitment scheme follows partially that of standard commitmentscheme:

• $\mathsf{Setup}(1^\lambda) \to (\mathsf{pk}, \mathsf{vk})$ takes a security parameter and outputs a proving and a verification key.
• $\mathsf{Com}(\mathsf{pk}, f) \to (\sigma, \mathsf{aux})$ takes a proving key and a polynomial $f$ and outputs a commitment $\sigma$ and auxiliary decommitment information $\mathsf{aux}$.
• $\mathsf{Open}(\mathsf{vk}, f, \sigma, \mathsf{aux})$ checks whether $(\sigma, \mathsf{aux})$ are a valid commitment-opening pair for $f$.

Furthermore, we extend the interface with an evaluation protocol between a prover and a verifier $\mathbf{P}, \mathbf{V}$. We denote the protocol as $\langle \mathbf{P}(\mathsf{pk}, f, \mathsf{aux}), \mathbf{V}(\mathsf{vk}) \rangle(\sigma, u, v)$.

The properties that we require from a polynomial commitment scheme are:

1. Completeness of the commitment scheme: If $\mathsf{pk}, \mathsf{vk}, \sigma, \mathsf{aux} $ are honestly generated (w.r.t to $f$), then $\mathsf{Open}(\mathsf{vk}, f, \sigma, \mathsf{aux}) = 1$.
2. Binding of the commitment scheme: The probability that an efficient adversary can find $\sigma, f,g, \mathsf{aux}_f, \mathsf{aux_g}$ such that $\mathsf{Open}(\mathsf{vk}, f, \sigma, \mathsf{aux}_f) = 1 = \mathsf{Open}(\mathsf{vk}, g, \sigma, \mathsf{aux}_g)$ is negligible.
3. Evaluation completeness: If $f(u) = z$, the evaluation protocol will accept.
4. Evaluation knowledge-soundness: There exists an efficient extractor that, if a malicous prover is able to make the verifier accept with non-negligible probability, is able to extract a polynomial $f$ and an opening $\mathsf{aux}$ such that $f(u) = z$ and $\mathsf{Open}(\mathsf{vk}, f, \sigma, \mathsf{aux}_f) = 1$.

In the paper, we also consider hiding, but in the interest of space we avoid this here.

WeeWu Commitments

Our starting point is the commitment scheme introduced in [WW23]¹. Their commitments relies on the BASIS assumption (Basis-Augmented Short Integer Solution). It roughly states that an adversary that is given access to a random matrix $\mathbf{A}$, should not be able to find a short vector $\mathbf{v}$ such that $\mathbf{A}\mathbf{v} = 0$ even when given access to a trapdoor to sample short preimages of a matrix $\mathbf{B}$ related to $\mathbf{A}$. In their work, the matrix $\mathbf{B}$ is defined as $$\begin{bmatrix}\mathbf{A}_0 &&& - \mathbf{G}\\ & \ddots & & \\ & & \mathbf{A}_d & - \mathbf{G} \end{bmatrix}$$ where $\mathbf{A}_i = \mathbf{W}_i \mathbf{A}$ for $\mathbf{W_i}$ random invertible matrices and $\mathbf{G}$ the gadget matrix of [MP12]³. We extend this to two new assumptions, the powerBASIS and PRISIS assumptions. Roughly, we introduce more structure in the $\mathbf{W}_i$. In powerBASIS, we let $\mathbf{W}_i = \mathbf{W}^{i}$, while in PRISIS we set $\mathbf{W}_i = w^{i} \mathbf{I}$. With this added structure, the commitment scheme that we construct is exactly as in [WW23] (here we present the powerBASIS version). Namely:

• $\mathsf{Setup}(1^\lambda) \to (\mathsf{pk}, \mathsf{vk})$ samples $\mathbf{A}, \mathbf{W}$ and uses [MP12]³ sampling to construct a trapdoor $\mathbf{T}$ of $\mathbf{B}$. The verification key consists of $\mathbf{A}, \mathbf{W}$ and the proving key additionally contains $\mathbf{T}$.
• $\mathsf{Com}(\mathsf{pk}, f) \to (\sigma, \mathsf{aux})$ uses $\mathbf{T}$ to sample short $\mathbf{z_i}$ and $\hat{\mathbf{c}}$ such that $\mathbf{B}[\mathbf{z}_0, \dots, \mathbf{z}_d, \hat{\mathbf{c}}]^\top = [-f_0 \mathbf{W}^0 \mathbf{e}_1, \dots, - f_d \mathbf{W}^d \mathbf{e}_1]^\top$, it then outputs $\mathbf{c} := \mathbf{G}\hat{\mathbf{c}}$ and $(\mathbf{z}_i)$ as decommitment.
• $\mathsf{Open}(\mathsf{vk}, f, \sigma, \mathsf{aux})$ checks that the openings are indeed short, and that the equations are all satisfied: namely it checks that $$\mathbf{A}\mathbf{z}_i + f_i \mathbf{e}_1 = \mathbf{W}^{-i}\mathbf{c} \enspace.$$

We then show that this commitment scheme is binding (even with respect to relaxed openings, as customary in the lattice-world).

Evaluation Proofs

Now, our evaluation protocols are inspired partly by FRI (even though the setting and analysis are completely different). Suppose we aim to show that $f(u) = z$. We take our polynomial $f$ and write it as an odd an even part i.e.: $$f(X) = f_0(X^2) + Xf_1(X^2)$$ The prover then sends evaluations $z_0, z_1$ of $f_0, f_1$ on $u^2$. The verifier checks that $z_0 + u z_1 = z$ and sends a random challenge $\alpha$ to the prover, and computes an updated commitment $\mathbf{c}’ = (1 + \alpha \mathbf{W}^{-1}) \mathbf{c}$ and a new verification key where $\mathbf{W}’ = \mathbf{W}^2$. The prover computes a new folded polynomial $g$ and updated opening as follows: $$g(X) = f_0(X) + \alpha f_1(X), \mathbf{s}_i = \mathbf{z}_{2i} + \alpha \mathbf{z}_{2i+1}\enspace.$$ The crucial observation is that the parties now can recurse on the claim that $g(u^2) = z_0 + \alpha z_1$, which is about a polynomial of degree $d/2$. We recurse thus $\log d$ times, until the prover can just send a constant sized opening. Note in particular that the additional structure of the powerBASIS construction allowed the verifier to efficiently construct a commitment to $g$ from one to $f$. In particular, note that $$\mathbf{A}\mathbf{s}_i + g_i \mathbf{e}_1 = \mathbf{A}\mathbf{z}_{2i} + f_{2i}\mathbf{e}_1 + \alpha \cdot ( \mathbf{A}\mathbf{z}_{2i+1} + f_{2i+1}\mathbf{e}_1)$$ $$ = \mathbf{W}^{-2i}\mathbf{c} + \alpha \mathbf{W}^{-2i - 1}\mathbf{c} = (\mathbf{W}^2)^{-i} (1 + \alpha \mathbf{W}^{-1})\mathbf{c}$$

Crucially, compared to other protocols like lattice-bulletproofs, the extraction keeps the norm growth more manageable (at the cost of trusted setup), which should lead to more concretely efficient protocols. The details are in the paper, due to the requirement of a flurry of notation.

Now, what is left to do is to manage the norm growth. We do this in two ways, which leads to two different protocols (with different tradeoff).

• By selecting the challenge $\alpha$ to be a (signed) monomial, we can ensure that the norm (here and in extraction) remains polynomial throught the $\log d$ rounds of the protocol. This achieves a protocol with polylogarithmic communication and verifier complexity. However, since the challenge set is of size $\mathrm{poly}(\lambda)$, we obtain a non-negligible soundness error, which needs to be mitigated by parallel repetition, making the protocol unsuitable to be made non-interactive via Fiat-Shamir.
• Instead of folding the polynomial halfway, we can aim to fold it in $k$-parts, and sample from an exponentially sized set. The norm growth is then much higher, only making it affordable to run the protocol $\log \log d$ iterations. Choosing $k$ appropriately, we are able to obtain a protocol with negligible knowledge soundness error and verifier and communication complexity “quasi-polylogarithmic” $d^{1/\log \log d}$⁴.

Instantiations

We then looked at how the scheme could perform concretely. The repetition needed to achieve 128 bits of security in the monomial protocol yields very large proof sizes, in the order of hundred of MBs. The other protocol strikes much closer to concrete efficiency, achieving proof sizes around 6 MBs. We also looked at applying the two protocols in Marlin, making also use of some natural ways to aggregate our protocols. With this, we obtain a post-quantum zkSNARK for R1CS with proof size roughly 26 MBs. While this is still rather large, we are confident that further work will follow the asymptotic improvement to yield concretely efficient zkSNARKs from lattices.

Drawbacks

We inherit many of the drawbacks of [WW23]¹, namely:

• The size of the proving key is quadratic in $d$.
• We could not reduce powerBASIS (or original BASIS) to standard assumptions.
• We require a trusted setup.

Furthermore, we our evaluations proof come with their own drawbacks:

• The concrete proof sizes are rather large.
• We could not achieve a fully polylogarithmic protocol with negligible soundness error.

We are confident that these drawbacks can be overcome in future work (wink 😉 ).

Conclusion

Find the full version for the gory details!

Citation

G. Fenzi, H. Moghaddas, N. K. Nguyen. “Lattice-Based Polynomial Commitments: Towards Concrete and Asymptotical Efficiency”. Cryptology ePrint Archive, Paper 2023/846. Available at: https://ia.cr/2023/846 .

@misc{FenziMN23,
	author       = {Giacomo Fenzi and Hossein Moghaddas and Ngoc Khanh Nguyen},
	title        = {Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency},
	howpublished = {Cryptology ePrint Archive, Paper 2023/846},
	year         = {2023},
	note         = {\url{https://eprint.iacr.org/2023/846}},
	url          = {https://eprint.iacr.org/2023/846}
}

Related material

This post looks at Plonky3 and combining Mixed Matrix Commitment Schemes with STIR 🥣 and WHIR 🌪️ as the low-degree test.

As far as I understand, the problem that we are aiming to solve is the following: The prover has committed to a matrix of functions (note the possibly different number of columns in each row) $$ \begin{bmatrix} f_{1, 1}, \dots, f_{1, n_1} \\ \vdots \\ f_{m, 1}, \dots, f_{m, n_m} \end{bmatrix} $$

where $f_{i, j}: \mathcal{L}_i \to \mathbb{F}$ for a list of domains $\mathcal{L}_1, \dots, \mathcal{L}_m \subseteq \mathbb{F}$.¹

The prover wants to show that each $f_{i, j} \in \mathsf{RS}[\mathbb{F}, \mathcal{L}_i, d/2^{i-1}]$.

Suppose that we want to run an iteration of STIR or WHIR to check this. An important parameter to keep in mind here is the folding factor $k$, typically $4$.² A STIR or WHIR iteration at each step reduces testing that $f \in \mathsf{RS}[\mathbb{F}, \mathcal{L}, d]$ to testing that $f’ \in \mathsf{RS}[\mathbb{F}, \mathcal{L}’, d/2^k]$³.

Denote by $\mathcal{L}^{(1)} = \mathcal{L}_1, \mathcal{L}^{(2)}, …, \mathcal{L}^{(M)}$ the domains appearing in the STIR iteration⁴.

Easy case

The easy case is the one in which $\mathcal{L}_1, …, \mathcal{L}_k = \mathcal{L}^{(1)}$, $\mathcal{L}_{k+1}, …, \mathcal{L}_{2k} = \mathcal{L}^{(2)}$ and so on. In this case, the committer is aware of what STIR will do, and it choses the domain to simplify the accumulation.

In the first iteration, the prover simply tests a random linear combination of $$ \sum_{j \in [n_1]} \epsilon_1^{j - 1} f_{1, j} + \epsilon_1^{n_1} \cdot \sum_{j \in [n_2]} \epsilon_1^{j - 1} \mathsf{Cor}(f_{2, j}, d) + \dots + \epsilon_i^{n_k} \cdot \sum_{j \in [n_k]} \epsilon_1^{j - 1} \mathsf{Cor}(f_{k, j}, d)$$ ($\mathsf{Cor}(f, d)$ is just some notation for degree correction up to degree $d$ as in the STIR paper.) This will define a new virtual function $g^{(1)}: \mathcal{L}^{(2)} \to \mathbb{F}$ to be tested.

In the next round, the prover instead of just testing $g^{(1)}$, it will test instead

$$g^{(1)} + \epsilon_2 \cdot \left( \sum_{j \in [n_{k+1}]} \epsilon_2^{j - 1} f_{k+1, j} + \dots + \epsilon_2^{n_{2k}} \cdot \sum_{j \in [n_{2k}]} \epsilon_2^{j - 1} \mathsf{Cor}(f_{2k, j}, d/2^k) \right)$$ and so on.

Soundness follows quite easily, if any of the functions do not satisfy the proximity claim, the sum will be far from low-degree by proximity gaps.

Harder case

In the harder case, there is no relation between the domains that STIR chooses and the ones that the MMCS has committed to. To solve this, we have to do a domain shift. Conveniently, STIR is exactly a protocol for doing domain shifts.

The prover first does a STIR iteration on $$ \sum_{j \in [n_1]} \epsilon_1^{j - 1} f_{1, j} $$ which defines a function $g^{(1, 1)}: \mathcal{L}^{(2)} \to \mathbb{F}$. Then, it does a STIR iteration with folding factor $k - 1$⁵ on $$ \sum_{j \in [n_2]} \epsilon_1^{j - 1} f_{2, j} $$ which defines a function $g^{(1, 2)}: \mathcal{L}^{(2)} \to \mathbb{F}$ and so on. At the end you will have $k$ functions $g^{(1, 1)}, \dots, g^{(1, k)}$ over the same domain $\mathcal{L}^{(2)}$.

Then, first run a STIR iteration on a random linear combination of these functions (obtaining a new function $g^{(2, 0)}: \mathcal{L}^{(3)} \to \mathbb{F}$). Then, do $k$ STIR iteration as above on each row of the matrix, obtaining new functions $ g^{(2, 1)}, \dots, g^{(2, k)}: \mathcal{L}^{(3)} \to \mathbb{F}$.

Iterating the protocol yields a low-degree test for MMCS. Soundness should follow as above. Of course, if at any point the domains match one can use the same strategy as in the easier case to efficiently reduce the number of running accumulators.

Just some spare thoughts on LDPC codes and RS codes (for IOPP based SNARKs), as an answer to Dev’s questions .

TLDR; LDPC are an amazing avenue of research, that I hope to explore more, but I am bit skeptical on the current maturity of prover and verifier performance that they bring to the table.

I think it makes sense to consider the question on two parts: prover time and verifier complexity. This might be a bit simplistic, and I am hoping to learn more about these codes (soon).

Prover time

On the prover side, I like breaking down the complexity into two buckets: (i) arithmetic complexity and; (ii) hashing complexity. The first is time devoted to FFTs, encodings, anything that involves fops, while the latter is mostly dominated by the hashing to commit to oracles. Linear time encodable codes based SNARKs, such as Brakedown and Blaze, mainly improve on (i). Depending on how fast your hash is, I have seen this hashing cost to be the main chunk of the prover’s work (accounting for anything between 40%-60% in e.g. WHIR’s prover and the Polygon zkEVM). It is a very parallelizable chunk of work, but a large one at that. Typically, the size of (ii) is linear in the oracles being committed to i.e. $O(n/\rho)$ (where $n$ is the instance size and $\rho$ the rate of the code).

LDPC codes improve (i), while either leaving (ii) unchanged or slightly worsening it (because the code have bad distance, typically a smaller rate is required, more on this on the verifier side).

Now, how much can the improvement on (i) be? Asymptotically, moving from $O(n \log n)$ to $O(n)$ can be a factor of 30x, which is very notable. However, the LDPC codes encoding is now competing against heavily optimized FFTs. Further, these FFTs are very parallel and running (typically) over small fields. And they are fast. While I think that the RAA codes encoding, when properly optimized, will leave FFTs behind, I can’t confidently say how much quicker we can feasibly get them. My gut feeling is that moving a RS based implementation to a small field is a much larger improvement gain (at a smaller engineering effort) than moving to a LDPC code.

Just to give some datapoints on this, I was comparing the Blaze and Brakedown numbers with some of our measurements in WHIR. Take this comparison with a bunch of grains of salts: (i) the fields are different; (ii) the machines are different; (iii) we optimized our implementation a fair bit; and (iv) different number of cores (also unclear where the memory bandwidth bottleneck occur, so cannot just divide). WHIR on 2^28 variables (on 32 threads) produces a proof in 42s. Blaze (on 192 cores) takes 21s, and Brakedown (on 64 threads) takes similar time. So, the 28x theoretical speed-up only results in around a 2x concrete speed-up, at the moment. I am excited to see this reducing further, as I am sure it will, but that’s why I’m a bit lukewarm on it now.

Verifier complexity

Regarding verifier complexity, the term to really consider is (in the soundness error) $(1 - \delta)^t \leq 2^{-\lambda}$, where $\delta$ is the distance the system operates on and $t$ the number of queries to the initial oracle. WHIR and STIR basically show that this $t$ is the bottleneck on the verifier side, as with domain shifting the latter rounds are basically “free”. Note that $t$ is the bottleneck for both native verification and recursive verification. LDPC codes suffer from two factors: (i) not amazing initial distance to start with (ii) weak generic proximity gaps results (up to $\delta_\mathsf{C}/3$). This effectively limits how large of a distance $\delta$ the prover can run at, making the verifier perform around 1000 queries¹ (to this initial oracle). In comparison, for Reed-Solomon codes one can set $\delta = 1 - \sqrt{\rho}$ or even $1- \rho$ (depending on your religious belief) which can lead to as few as 50 or 25 queries to the initial oracle.

Since the verifier needs to verify $t$ authentication paths (roughly $t \cdot \log n$) hashes, and this typically is its bottleneck (70% of the verifier runtime in WHIR), I don’t really expect that currently LDPC codes can give super competitive verifiers.

Improving the distance of the LDPC code and getting stronger proximity gaps results would of course completely change this section, but if I said I understood what is going on in both these areas I would lie.

Our recent work, WHIR 🌪️ (See 2024/1586 and blog-post. ) is an IOPP for constrained RS codes with exceptionally fast verification. In this blog we explain in detail one of the optimization that we used to achieve a faster verifier, with applications to schemes such as FRI and STIR as well. Verifier complexity usually consists of two components: (i) an algebraic component and; (ii) computing hashes. Reducing the second load (ii) usually involves reducing the IOPP query complexity, which is the main objective of STIR and WHIR. The technique we describe next aims to reduce the other component of verifier cost.

Folding

One of the main components of FRI, STIR, and WHIR is the folding operation. For $L \subseteq \mathbb{F}$¹, define $L^{2^k} = \{ z^{2^k} : z \in L \}$ and, for $z \in L^{2^k}$, let $\mathcal{B}_z = \{y \in L : y^{2^k} = z \}$. We define $\mathsf{Interpol}$ to be the function that interpolates a polynomial given a list of evaluations, i.e. $\hat{p} := \mathsf{Interpol}(\{1, …, n\}, (y_1, \dots, y_n))$ is the minimal univariate polynomial such that, for $i \in [n]$, $\hat{p}(i) = y_i$.

Given a function $f: L \to \mathbb{F}$, the $k$-wise folding of $f$ at $\alpha \in \mathbb{F}$ is defined as the function $\mathsf{Fold}(f, \alpha): L^{2^k} \to \mathbb{F}$ that maps $$ z^{2^k} \mapsto \mathsf{Interpol}(\mathcal{B}_z, f(\mathcal{B}_z))(\alpha) $$

We also define the $k$-multilinear folding to be the function $\mathsf{Fold}^{(k)}(f, (\alpha_1, \dots, \alpha_k)): L^{2^k} \to \mathbb{F}$ obtained by applying the $2$-wise folding $k$ times.

Typically:

• FRI uses $1$-wise folding, possibly $k$-wise folding.
• STIR uses $k$-wise folding, with $k > 1$.
• WHIR uses $k$-multilinear folding, with $k > 1$.

In each of these schemes, the prover will commit to a function $f: L \to \mathbb{F}$ by sending a function $\tilde{f}: L^{2^k} \to \mathbb{F}^{2^k}$ such that $\tilde{f}(z^{2^k}) = f(\mathcal{B}_z)$. The verifier will sample (a single or many) challenges $\alpha$, and the verifier will require to compute the folding with respect to $\alpha$ at some randomly sampled element of $L^{2^k}$.

Optimizing folding

The verifier can use the definition of folding to evaluate it. Naively, this is a quadratic cost, but in fact since $\mathcal{B}_z$ is a smooth coset of $L$, the verifier can use an FFT to evaluate it in time $O(k \cdot 2^k)$. In fact, since the verifier needs only to evaluate the polynomial at a single point, this can in fact be done in linear time $O(2^k)$ via some version of barycentric evaluation for such subsets. (See E.2 in SNARKs for C for example). Concretely, this seems to require $2 \cdot (2^k - 1)$ multiplications.

We suggest the following optimization. Instead of committing to $f: L \to \mathbb{F}$ as beforehand:

• In the univariate folding case the prover will commit to a related function $\tilde{f}: L^{2^k} \to \mathbb{F}^{<2^k}[X]$ where $\tilde{g}(z^{2^k}) = \mathsf{Interpol}(\mathcal{B}_z, f(\mathcal{B_z}))$.
• In the multilinear folding case the prover will commit to a related function $\tilde{f}: L^{2^k} \to \mathbb{F}^{< 2}[X_1, \dots, X_k]$ where $\tilde{g}(z^{2^k}) = \mathsf{Interpol}(\mathcal{B}_z, f(\mathcal{B_z}))$ (interpreted as a $k$-variate multilinear polynomial).

Now, when computing the fold, the verifier can simply read the corresponding polynomial and evaluate it at the point $\alpha$, which takes exactly $2^k$ multiplications, roughly a 2x improvement. Soundness holds since the prover is sending the same exactly information (as the two representations can be recovered from one-another).

Experimentally, this gives around a 20% saving in the WHIR verification.

Our recent work, STIR 🥣 (See 2024/390 and blog-post. ) is an IOPP for RS codes with improved query complexity compared to the state-of-the art, FRI. Compared to FRI, STIR has a few more parameters that one can tweak, which can have a rather large impact on prover time, verifier time and argument size. This short blurb details what these parameters are, and how they translate, concretely, in the resulting argument. I won’t be completely formal here, details worked out are in Subsection 5.3, Section 6 and Appendix C of the STIR paper.

Parameters

In this note, we focus on a single iteration of STIR. We assume that the following parameters are given:

• A security parameter$\lambda \in \mathbb{N}$.
• The Reed-Solomon code being tested, this includes:
  • A field $\mathbb{F}$¹.
  • A smooth evaluation domain $\mathcal{L} \subseteq \mathbb{F}$.
  • A degree bound $d \in \mathbb{N}$.
  • An initial rate $\rho := \frac{d}{|\mathcal{L}|}$.

We assume that the proximity bound to be tested from here on is $\delta := 1 - \rho$ (i.e. we are assuming the conjecture and ignoring $\eta$.) If instead $\delta$ is in unique decoding range, the protocol can be made simpler by removing the OOD samples. We do not discuss this here.

A parametrization for a STIR iteration consists of the following:

• An evaluation domain $\mathcal{L}^\star \subseteq \mathbb{F}$.
• A folding parameter $k$.
• The number of OOD-samples $s$.
• The number of queries $t$.
• The PoW bits $\lambda_b$.

We note that the parameters of each STIR iteration can be chosen independently.

Setting parameters

This is not the place to precisely tell people how to set the parameters for soundness to hold, that’s what the paper is for. Here I just want to give some intuition on how one would go about doing this. First, I suppose that you would pick evaluation domain $\mathcal{L}^\star$ and folding parameter $k$. Letting $c := \frac{|\mathcal{L}|}{|\mathcal{L}^\star|}$, note that the rate of the new code being tested is $\rho^\star := (c/k) \cdot \rho$. The key observation of STIR is that a lower rate makes testing easier, so the smaller the value $c/k$ is the fewer queries we require in latter iterations. In the paper, we set $c = 2$ to keep a linear proof length, but this is by no means necessary. You can even pick $c < 1$. The tradeoff in chosing $\mathcal{L}^\star$ is that:

• Large $\mathcal{L}^\star$ drives the rate down and thus the number of queries in the next iteration quicker.
• However, the prover is then less efficient (as an FFT over $\mathcal{L}^\star$ must be performed).

Regarding the folding parameter $k$:

• A larger folding parameter $k$ reduces both the degree of the polynomial quicker and decreases the rate of the next iteration, also driving down the number of queris.
• On the other end, the verifier now needs to (at least) compute larger folds, each of which has cost at least linear in $k$, and also needs to read more field elements.

Once those two parameters are set, the OOD-samples should be set so that they reach $\lambda$ bits of security. In general, for most sane configurations $s = 1$ or $s = 2$ should suffice.

Finally, $t$ and $\lambda_b$ should be set so that $(1 - \delta)^t < 2^{\lambda - \lambda_b}$. Here there are also some tradeoffs:

• A larger value of $\lambda_b$ drives down verifier time and argument size, at the cost of increased prover time.
• Further, larger $t$ not only increases the argument size but also the verifier running time, as it requires to compute more folds (and the virtual functions become more expensive to compute).

Prover time

Prover time in a STIR iteration is easy to estimate. We assume that the prover has access to the message $\hat{f} \in \mathbb{F}[X]$ of degree $d$ for the codeword $f: \mathcal{L} \to \mathbb{F}$ being tested. The STIR prover does the following:

1. Derives $\alpha \in \mathbb{F}$ by FS.
2. Computes $\hat{g} := \mathsf{PolyFold}(\hat{f}, \alpha, k) \in \mathbb{F}[X]$ of degree $d/k$.
3. Evaluates $\hat{g}$ on $\mathcal{L}^\star $ via a FFT to compute a vector of evaluations $g: \mathcal{L}^\star \to \mathbb{F}$.
4. Commits to $g$ using a Merkle tree.
5. Derives $x_1, \dots, x_s \in \mathbb{F}$ by FS.
6. Evaluates $g$ at $x_1, \dots, x_s$ using Horner’s rule.
7. Derives $v_1, \dots, v_t \in \mathcal{L}^k$ by FS.
8. Computes a new function $\hat{f}^\star \in \mathbb{F}[X]$ of degree $d/k$ by quotienting $\hat{g}$ at $s + t$ points, and degree correcting.

All summed up, the prover does:

1. Squeeze $1 + s + t$ elements out of the FS sponge.
2. Computes $2 \cdot |\mathcal{L}^\star|$ hashes for the Merkle commitment.
3. Computes an FFT of size $|\mathcal{L}^\star|$ for polynomial of size $d/k$, resulting in $O(|\mathcal{L}^\star| \cdot \log d/k)$ fops.
4. Does an additional $O(d)$ fops to compute the folds and $O(d/k)$ fops to compute the quotient and the degree correction.

So the prover costs are: $$ (1 + s + t) \cdot \mathsf{FS} + 2 \cdot |\mathcal{L}^\star| \cdot \mathsf{H} + \mathsf{FFT}(\mathcal{L}^\star , d/k) + O(d + d/k) \cdot \mathbb{F} $$

Argument size

Argument size is also easy to estimate, it consists of:

1. A single Merkle root (for $g: \mathcal{L}^\star \to \mathbb{F}$).
2. $s$ elements of $\mathbb{F}$ (for OOD-samples).
3. $t$ authentication paths, for a Merkle tree of $|\mathcal{L}|/k$ leaves, where each leaf is in $\mathbb{F}^k$.

Assuming that the digest size of the Merkle hash is $2\lambda$ bits, and not accounting for path pruning (which in practice has a large impact), the argument size in bits is then: $$ (1 + t \cdot \log(|\mathcal{L}|/k)) \cdot 2\lambda + (s + t \cdot k) \cdot \log |\mathbb{F}| \enspace. $$

Verifier time

The verifier performs the following operations:

1. Derives $\alpha \in \mathbb{F}$ by FS.
2. Derives $x_1, \dots, x_s \in \mathbb{F}$ by FS.
3. Derives $v_1, \dots, v_t \in \mathcal{L}^k$ by FS.
4. Queries $f$ at $t$ locations:
   • Each query involves reading $k$ fields element and verify a Merkle authentication path of a Merkle tree with $|L|/k$ leaves.
   • Derive the value of $f$ at those $t \cdot k$ locations.
     • In the first iteration, this requires no additional field operations.
     • In latter rounds, the function $f$ is defined as $$ f(x) = \mathsf{DegCorr}\left(\frac{g’(x) - \mathsf{Ans}(x)}{V(x)}\right) $$ where $g’$ is the oracle sent in the previous round, $\mathsf{Ans}, V$ are polynomials of degree $< t’ + s’$ (where $t’, s’$ are the queries and OOD repetition of the last iterations).
     • The degree correction is a (small) constant number of field operations.
     • The two polynomials can be computed by interpolation (or with prover assistance, more on this soon™️) at the beginning of the iteration and so the cost is ammortised across each queries.
     • Thus, each of these queries only requires evaluating these polynomials at a random point, which costs $O(t’ + s’)$ fops.
   • Once the value of $f$ is computed, the verifier computes the Fold which costs $O(k)$ fops (or $O(k \cdot \log k)$ fops if using an IFFT for this interpolation, the latter seems asymptotically worse but concretely more efficient in my experiments).

So, in the first iteration the verifier cost is: $$ (1 + s + t) \cdot \mathsf{FS} + t \cdot \log(|L|/k) \cdot \mathsf{H} + O(t \cdot k) \cdot \mathbb{F} \enspace. $$ In the latter iterations instead it is $$ (1 + s + t) \cdot \mathsf{FS} + t \cdot \log(|L|/k) \cdot \mathsf{H} + O\left(t \cdot k \cdot (t’ + s’ + 1) \right) \cdot \mathbb{F} \enspace. $$

There are additional tricks that can be done to further drive down the verifier costs. For example, instead of quotienting by $t + s$ points to define the next function to be tested, one can define $t$ functions, each of them consisting of quotients of $1 + s$ points, and test a (degree corrected) random linear combination of them.