October 2025

More efficient Lattice Folding via ℓ₂-Norm Checks

Increase the efficiency of LatticeFold+ [BC25b] by replacing range-checks with ℓ₂-norm checks from Rok and Roll [KLNO25] and SALSAA [KLOT25].

Introduction

Imagine you're running a Layer 2 blockchain, processing thousands of transactions every second. When it's time to move those transactions to the main (L1) chain, they all need a cryptographic proof to ensure their validity. The traditional approach? Generate a massive proof for all transactions at once, but this requires keeping everything in memory, which quickly becomes impractical. Furthermore, the prover can only start the proof generation after receiving all transactions. What if instead, you could "fold" instances together incrementally, combining two instances into one, then folding that result with another, and so on? That's the magic of folding schemes.

Folding schemes are cryptographic protocols that compress multiple instances of a problem into fewer instances. Think of it like folding a piece of paper: each fold makes it smaller and more compact, but the paper is still there, nothing is lost.

In real-world applications, processing proofs incrementally (without loading everything into memory at once) becomes crucial for scalability and parallelization - whether proving correct execution of cross-chain transfers, verifying machine learning model training on sensitive data, authenticating media content against tampering, or demonstrating computational work for delay functions.

Traditional SNARKs (Succinct Non-interactive Arguments of Knowledge) produce wonderfully short proofs, but they require the prover to process the entire computation at once. If you're streaming data - say, processing blockchain transactions as they arrive - you'd need to store everything until you're ready to prove. This is expensive and slow.

Folding schemes solve this by allowing incremental proving: fold two instances together, fold the result with another, and keep going. At each step, you only need to remember a constant amount of state. You can even fold the verification itself into the computation, creating what's called Incremental Verifiable Computation (IVC), i.e. proofs that verify themselves recursively.

Lattice-based folding

Recent work by Boneh & Chen [BC25b] and others has shown that lattice-based cryptography is particularly well-suited for folding schemes. Lattices offer two key advantages:

1. Post-quantum security: unlike many current systems, they're believed to resist attacks from quantum computers
2. Efficiency: with the right techniques, they can be surprisingly fast

However, there's a catch. All current lattice folding schemes rely on range-checks (technically, \( \ell_\infty \)-norm checks) to ensure that numbers don't grow too large during the folding process. These range-checks are computationally expensive and they're the bottleneck.

Our contribution

In this blog post, we show how to replace expensive range-checks with more efficient \( \ell_2 \)-norm checks, inspired by techniques from Rok and Roll [KLNO25]. Whilst we focus on improving Boneh & Chen's LatticeFold+ [BC25b], the techniques are general and could benefit other lattice-based folding schemes.

More concretely? Faster provers, same security guarantees, and a step towards making post-quantum folding schemes practical for real-world applications.

Idea explored here should be viewed as an expansion of the framework from [BC25a] and [BC25b] with more efficient norm checks from [KLNO25] and [KLOT25].

Now, let's dive into the technical details. Don't worry, we'll build up the concepts gradually.

Notation

We denote by \( [n] \) the set \( \{0, 1, \ldots, n-1\} \). Throughout the post, we use boldface letters to denote vectors and matrices, which are further denoted by lowercase and uppercase, respectively. We assume that vectors are column vectors. We write \( ||\cdot|| \) to denote the norm of a vector, where the specific norm (e.g. \( \ell_\infty \) or \( \ell_2 \)) is specified explicitly when needed. For concatenation of vectors, we use the notation \( [\mathbf{a} || \mathbf{b}] \) to denote the concatenation of vectors \( \mathbf{a} \) and \( \mathbf{b} \).

We use \( \mathcal{R}_q \) to denote the ring of integer polynomials modulo \( X^N + 1 \) with coefficients in \( \mathbb{Z}_q \) for some integer modulus \( q \) and degree \( N = 2^k \). For simplicity, one could set \( \mathcal{R}_q = \mathbb{Z}_q \) (i.e. \( N = 1 \)) to obtain standard integer vectors, which is mainly sufficient for our discussion. We use the notation \( \otimes \) to denote the Kronecker product and \( \odot \) to denote the Hadamard product.

Given a vector \( \mathbf{v} \in \mathcal{R}_q^{2^{\mu}} \), its multi-linear extension is defined as the unique multi-linear polynomial \( \mathsf{MLE}[\mathbf{v}](X_0, \ldots, X_{\mu-1}) \) such that \( \mathsf{MLE}[\mathbf{v}](\mathbf{b}) = v_{\mathbf{b}} \) for every \( \mathbf{b} \in \{0,1\}^{\mu} \). If vector has a structured form, i.e. it is a product of lower-dimensional vectors, then its multi-linear extension can be computed efficiently. We write \( \mathcal{R}_q^{2^{\otimes \mu}} \) to denote the set of vectors \( \mathbf{v} \in \mathcal{R}_q^{2^{\mu}} \) such that \( \mathbf{v} = \mathbf{v}_0 \otimes \mathbf{v}_1 \otimes \ldots \otimes \mathbf{v}_{\mu-1} \) for some vectors \( \mathbf{v}_i \in \mathcal{R}_q^{2} \).

We define a general (NP) relation \( \Xi \) as a triple:

so that \( \mathsf{pp} \) is the public parameter (fixed throughout the execution of the protocol), \( \mathsf{stmt} \) is the statement and \( \mathsf{wtn} \) is the witness. The relation holds if the predicate \( R_{\Xi} : \mathcal{P} \times \mathcal{S} \times \mathcal{W} \to \{0,1\} \) evaluates to 1 and write \( (\mathsf{stmt}, \mathsf{wtn}) \in \Xi \) to denote that the instance-witness pair is valid.

A particular relation of interest is the Rank-1 Constraint System (R1CS). R1CS is a widely used relation in the context of SNARKs and folding schemes, as many NP statements (including evaluations of arithmetic circuits) can be efficiently reduced to R1CS.

We remark that this arithmetisation is considered here and also in [BC25b] for the simplicity of the exposition, but with some generic modifications (as in [BC25a]) we are ready to extend our construction to supports more advanced arithmetisations, e.g. customisable constraint system [STW23], which further generalises other arithmetisations such as AIR or Plonkish.

Boneh & Chen's Framework for Lattice-based Folding Schemes

Reductions of Knowledge

Informally, a reduction of knowledge is an interactive algorithm (between prover and verifier) that takes an instance of a relation and produces another instance of a (possibly different) relation. We write \( \Pi: \Xi_0 \rightarrow \Xi_1 \) to denote a reduction from relation \( \Xi_0 \) to relation \( \Xi_1 \).

We say that reduction of knowledge is correct (perfectly or statically) if for every valid instance-witness pair \( (\mathsf{stmt}_0, \mathsf{wtn}_0) \in \Xi_0 \), the output instance-witness pair \( (\mathsf{stmt}_1, \mathsf{wtn}_1) = \Pi(\mathsf{stmt}_0, \mathsf{wtn}_0) \) is also valid, i.e. \( (\mathsf{stmt}_1, \mathsf{wtn}_1) \in \Xi_1 \).

We also say that reduction of knowledge is knowledge-sound if for every statement \( \mathsf{stmt}_0 \in \Xi_0 \) and for every valid witness \( \mathsf{wtn}_1 \) for the output instance \( (\mathsf{stmt}_1, \mathsf{wtn}_1) = \Pi(\mathsf{stmt}_0, \mathsf{wtn}_0) \), there exists an efficient extractor algorithm that can extract a valid witness \( \mathsf{wtn}_0 \) for the input instance \( \mathsf{stmt}_0 \). The extractor is allowed to rerun the prover algorithm multiple times with the same input instance \( \mathsf{stmt}_0 \) but different randomness.

The LatticeFold+ [BC25b] framework consists of the composition of reductions of knowledge.

Generalised Committed Linear Relation

Before proceeding to the description of the folding schemes, we also define the notion of generalised committed linear relation, which will be useful in the construction.

In words, the public parameters consist of a matrix \( \mathbf{A} \), which shall be viewed as an Ajtai-type commitment (binding under the ring variant of the short integer solution problem) and a set of matrices \( (\mathbf{M}_i)_{i \in [t]} \), which form additional constraints on the witness. The statement consists of vectors \( \mathbf{y} \) and \( (v_i)_{i \in [t]} \) forming the right-hand side of the linear system. Further, the matrices \( (\mathbf{M}_i)_{i \in [t]} \) are ''batched'' via vector \( \mathbf{r} \) so that the right-hand side remains succinctly represented. The witness \( \mathbf{w} \) is required to satisfy the linear system and also to be of short norm (in the context of [BC25b], the \( \ell_\infty \)-norm is used).

Folding Scheme for R1CS Relation

Eventually, we are ready to describe the folding scheme.

The folding scheme for the R1CS relation is obtained with two main ingredients:

• linearisation reduction from the R1CS relation to the generalised committed linear relation; and

• folding scheme for the generalised committed linear relation.

The latter, in turn, is obtained via the composition of the following reductions of knowledge:

• Norm check reduction that forms a ''checkpoint'' on the norm of the witness so that the extracted witness has the correct norm.

• Homogenisation that uniforms the left-hand side of the relations (i.e. same vector \( \mathbf{r} \) across all instances).

  • Random linear combination of witnesses and right-hand sides to reduce the number of instances from \( L \) to \( 1 \).

  • Decomposition that reduces the norm of the witness by splitting it into two parts, forming two new instances of the linear relation.

  The objective of this complex sequence of reductions is to obtain a folding scheme that reduces the number of instances from \( L \) to \( 2 \) whilst keeping the norm of the witness under control. In more detail, we expect that during folding (i.e. in the correctness direction) and during extraction (i.e. in the knowledge-soundness direction), the norm of the witness does not grow. This restriction is extremely important, as otherwise, after a few folding steps, the norm of the witness would become too large for the Ajtai-style commitments to remain binding.

  In the correctness direction, the norm of the witness grows during the combination step, but it is reduced back via the decomposition step. In the knowledge-soundness direction, the norm of the witness grows during the decomposition step. In the folding step, the norm of the witness does not only grow, but also the witness is augmented with a ''short denominator'' (also known as slack). Such a relation, often denoted as relaxed, remains still binding with a significant degradation of parameters. This temporary growth of the norm needs to be controlled, which is achieved via the norm-check step. The norm-check step ensures that the norm of the extracted witness is precisely the same as the norm of the original witness.

  Norm-check Reduction

  The norm-check reduction is a reduction of knowledge from the generalised committed linear relation to itself. The reduction serves as a ''checkpoint'' on the norm of the witness. In the extraction direction, it ensures that the extracted witness has the same norm as the original witness.

  In a nutshell, the reduction works as follows: the witnesses of the input relation are decomposed into monomials, i.e. for each witness \( \mathbf{w} \in \mathcal{R}_q^{m} \), we write \( \mathbf{w} = \sum_{j} \mathbf{w}^{(j)} X^j \). Then, the prover commits to each monomial vector via Ajtai-style commitments and proves consistency between the committed monomials and the original witness. Therefore, since the degree of the polynomial is bounded, the prover argues that the norm of the original witness is bounded via the \( \ell_\infty \) norm.

  To save communication, the prover does not send the commitments to all monomials, but instead employs a "double-commitment" technique. Nevertheless, the computational overhead remains significant. To compute the commitments to all monomials, the prover needs to perform \( L \cdot n \cdot m \cdot N \cdot \log_N \beta \) additions of cyclotomic ring elements, where \( L \) is the number of instances, \( n \times m \) is the dimension of the commitment matrix and \( N \) is the degree of the ring. This overhead might be prohibitive in practice.

Homogenisation Reduction

The homogenisation reduction is a reduction of knowledge from the generalised committed linear relation to itself. The reduction ensures that the left-hand side of the relation is uniform across all instances, i.e. the vector \( \mathbf{r} \) is the same for all instances.

The prover and verifier express all linear relations in terms of sumcheck claims, i.e., for each instance \( j \in [L] \), they express the relation as \[ \sum_{\mathbf{b} \in \{0,1\}^{\mu}} \mathsf{MLE}[\mathbf{r}_i](\mathbf{b}) \cdot \mathsf{MLE}[\mathbf{M}_i \mathbf{w}_j](\mathbf{b}) = y_{i, j} \] for each \( i \in [t] \). Then, the prover and verifier engage in a sumcheck protocol (batching all claims) to reduce the claims to a single random point \( \mathbf{r}^* \in \mathcal{R}_q^{\mu} \), obtaining the following set of equations:

where \( y_{i, j}^* \) are the appropriately defined linear combinations of the original right-hand sides. These can be expressed in matrix-vector form as:

so that the new relation has uniform left-hand side \( \mathbf{r}^* \) across all instances. Claims over \( \mathsf{MLE}[\mathbf{r}_i](\mathbf{r}^*) \) are verified by the verifier directly.

Replacing Range-Check with 𝓁₂-Norm-Check

To mitigate the overhead of the norm-check reduction, we propose to replace the \( \ell_\infty \)-norm check with \( \ell_2 \)-norm check.

Johnson-Lindenstrauss Lemma

The Johnson-Lindenstrauss lemma states that a small set of points in a high-dimensional space can be embedded into a lower-dimensional space such that the distances between the points are nearly preserved. Cryptographers enjoy a simpler formulation of the lemma, which is more suitable for our purposes. Following [BS23], we state the lemma as follows:

In words, the lemma states that by projecting a high-dimensional vector onto a lower-dimensional space using a random matrix with entries from the specified distribution, we can ensure that the \( \ell_2 \)-norm of the projected vector is concentrated around the \( \ell_2 \)-norm of the original vector scaled by certain factors, with overwhelming probability.

Attempt I: [BS23]-style 𝓁₂-Norm-Check

We first consider a straightforward adaptation of the norm-check reduction from [BS23], which employs the Johnson-Lindenstrauss lemma to perform \( \ell_2 \)-norm checks.

We consider the following reduction of knowledge from generalised committed linear relation to a similar relation with additional constraints:

• Verifier samples a random matrix \( \Pi \leftarrow C^{256 \times m} \) from the distribution specified in Lemma 4.1. We implicitly lift the matrix \( \Pi \) from integers to cyclotomic ring elements by embedding each entry as a constant polynomial.
• Prover computes the projected witness \( \mathbf{v}_j = \Pi \mathbf{w}_j \bmod q \) for each instance \( j \in [L] \) and sends it to the verifier.
• The verifier checks that the projected witness satisfies the norm constraints. The verifier sends a challenge \( \mathbf{c} \in \mathcal{R}_q^{256} \) to the prover.
• Later, in the homogenisation step, both the prover and verifier express the relations as a sumcheck claim for each instance \( j \in [L] \):

Those relations are homogenised similarly as before. This approach comes with two main disadvantages:

• The verifier needs to sample a new random matrix \( \Pi \) and further compute evaluations of \( \mathsf{MLE}[\mathbf{c}^{\mathtt{T}} \Pi](\mathbf{b}) \) during the homogenisation step. This introduces significant overhead for the verifier, which is now linear in the dimension of the witness \( m \), and is typically prohibitive.
• The extraction guarantee is weakened. Although the Johnson-Lindenstrauss lemma ensures that with overwhelming probability the norm of the projected witness is concentrated around the norm of the original witness, the bound holds only up to a (very small) constant factor. This means that during extraction, the norm of the extracted witness can be larger than the original witness by a constant factor. Repeated application of this reduction during multiple folding steps can lead to unbounded growth of the witness norm, eventually breaking the binding property of the commitments.

Attempt II: [KLNO25]-style 𝓁₂-Norm-Check

To address the issues identified in the previous approach, we propose an alternative \( \ell_2 \)-norm check reduction inspired by the techniques from [KLNO25].

The idea is very simple: instead of projecting the witness using a single projection matrix, we use multiple projections (with shared randomness). In other words, we project the witness in small blocks, so that each block is projected independently. Then, instead of sending a single projected witness, the prover commits to all projected blocks. In more detail, we consider the following reduction of knowledge from the generalised committed linear relation to a similar relation:

Assume \( L = 2^{e}\) is a power of two and let \( b = 256 \cdot L \) be the block size.

• The verifier samples a random matrix \( \Pi \leftarrow C^{256 \times b} \) from the distribution specified in Lemma 4.1, where \( b \) is the block size. We implicitly lift the matrix \( \Pi \) from integers to cyclotomic ring elements by embedding each entry as a constant polynomial.
• The prover splits the witness \( \mathbf{w} \in \mathcal{R}_q^{m} \) into \( m / b \) blocks of size \( b \), i.e. \( \mathbf{w}_j = [\mathbf{w}_j^{(0)} || \mathbf{w}_j^{(1)} || \ldots || \mathbf{w}_j^{(m/b - 1)}] \). The prover computes the projected blocks \( \mathbf{v}_j^{(i)} = \Pi \mathbf{w}_j^{(i)} \bmod q \) for each block. It combines the projected blocks into a single vector \( \mathbf{v}_j = [\mathbf{v}_j^{(0)} || \mathbf{v}_j^{(1)} || \ldots || \mathbf{v}_j^{(m/b - 1)}] \) and further \( \mathbf{v} = [\mathbf{v}_0 || \mathbf{v}_1 || \ldots || \mathbf{v}_{L-1}] \). The prover commits to the vector \( \mathbf{v} \) and sends the commitment to the verifier.
• The verifier sends a challenge \( \mathbf{c} \in \mathcal{R}_q^{\mu^{\otimes \mu}} \) to the prover, which is split into \( \mathbf{c}^{(0)} \in \mathcal{R}_q^{2^{\otimes \mu - e}} \) and \( \mathbf{c}^{(1)} \in \mathcal{R}_q^{2^{\otimes e}} \) so that \( \mathbf{c} = \mathbf{c}^{(0)} \otimes \mathbf{c}^{(1)} \).
• The prover sends \( s \in \mathcal{R}_q \) and \( \mathbf{t} \in \mathcal{R}^L_q \) so that

• The verifier checks that \( \sum_{j \in [L]} c_{0,j} t_j = s \).
• Later, in the homogenisation step, both the prover and verifier express the relations as a sumcheck claim for each instance \( j \in [L] \), where \( t_j \) are the appropriately defined right-hand sides:

We further modify the protocol. To use the newly-appended witness \( \mathbf{v} \) in the extraction, we need to ensure that this image is low-norm. If this is not the case, the extraction might fail to extract a valid witness for the original relation. In other words, the relation corresponding to \( \mathbf{v} \) must not be relaxed. To achieve this, we consider a slightly different variant of folding, which does not involve the projection witness. Therefore, the folding step randomly combines only \( L \) out of \( L + 1 \) instances, leaving the relation corresponding to \( \mathbf{v} \) untouched. This way, during extraction, the projected witness \( \mathbf{v} \) is available to the extractor without any slack, and the extractor can use it to recover the original witness \( \mathbf{w} \).

The output of folding is now a pair of two instances: the first instance corresponds to the randomly combined \( L \) instances, whilst the second instance corresponds to the relation for \( \mathbf{v} \). After decomposition, each of these is further split into two instances, obtaining in total four instances, serving as an accumulator for the next folding step.

The suggested protocol comes with better efficiency, but it leaves the extraction guarantee still (slightly) open. Indeed, we managed to "upgrade" the norm of the extracted witness from relaxed to almost the same as the original witness. However, the presented projection technique still leaves a small constant factor gap between the norm of the original witness and the extracted witness. Repeated application of this reduction during multiple folding steps can lead to unbounded growth of the witness norm, eventually breaking the binding property of the commitments.

Final Attempt: From Shortish to Short Witnesses

To completely close the extraction guarantee gap, we propose to combine the \( \ell_2 \)-norm check with a final "shortening" step, which transforms a shortish witness into a short witness. This idea has been originally explored in [KLOT25] in the context of SNARKs and folding schemes, but for a restrictive setting of low-norm linear relation satisfiability.

This time, we exploit the fact that the witness is already known to be shortish, i.e. its \( \ell_2 \)-norm is bounded by \( \alpha \beta \), where \( \beta \) is the original witness norm and \( \alpha \) is the factor by which the norm is increased during folding.

We make the following observation that the \( \ell_2 \)-norm of a vector is closely related to the inner product of the vector with itself. In more detail, we write

where \( \overline{\mathbf{w}} \) is the coordinate-wise complex conjugate of \( \mathbf{w} \). In the case of power-of-two cyclotomic rings, complex conjugation corresponds to the automorphism \( X \mapsto -X^{N-1} \). For further details, we refer the reader to [KLNO24]. We write \( \mathsf{ct} : \mathcal{R}_q \to \mathbb{Z}_q \) to denote the constant term of the cyclotomic ring element. We note that since \( \| \mathbf{w} \|_2^2 \) is already known to be small (i.e. less than \( \alpha^2 \beta^2 \)), the equality above holds over the integers (i.e. without \( \bmod q \)) for a sufficiently large modulus.

Therefore, to ensure that the witness is exactly of the desired norm, it suffices to show that \( \mathsf{ct} (\langle \mathbf{w}, \overline{\mathbf{w}} \rangle) \leq \beta^2 \).

To achieve this, we consider the following reduction of knowledge from the generalised committed linear relation to a similar relation with additional constraints:

• The prover computes the inner product \( u_j = \langle \mathbf{w}_j, \overline{\mathbf{w}_j} \rangle \) for each \( j \in [L]\) and sends it to the verifier.
• The verifier checks that \( \mathsf{ct} (u_j) \leq \beta^2 \) for each \( j \in [L]\).
• The prover and verifier express the relations as a sumcheck claim for each instance \( j \in [L] \), where \( u_j \) are the right-hand sides:

• The prover and verifier engage in a sumcheck protocol and reduce the claims to a single random point \( \mathbf{r}^* \in \mathcal{R}_q^{\mu} \), obtaining the following set of equations:

• The prover splits the equations into two linear equations and sends \( u'_j \) and \( u''_j \) so that for each \( j \in [L]\):

• The verifier checks that \( u'_j \cdot \overline{u''_j} = u_j^* \) for each \( j \in [L]\).
• Later, in the homogenisation step, both the prover and verifier express the relations as a sumcheck claim for each instance \( j \in [L] \) and combine them similarly as before with the other relations.

The aforementioned reduction ensures that during extraction, the extracted witness has exactly the same norm as the original witness, when the extracted witness is already guaranteed to be shortish. Therefore, by combining this reduction with the Johnson-Lindenstrauss-based \( \ell_2 \)-norm check, we obtain a complete \( \ell_2 \)-norm check reduction with the exact extraction guarantee.

Concrete Parameters and Efficiency

From an efficiency perspective, the proposed \( \ell_2 \)-norm check reduction is significantly more efficient from the prover's perspective than the original \( \ell_\infty \)-norm check from [BC25b]. The reason is that now the "heavy step" is the computation of the Johnson-Lindenstrauss projections, which requires "only" \( L \cdot m \cdot 256 \) additions of ring elements, which is by the order of magnitude more efficient than the monomial commitments from [BC25b], where the number of additions was \( L \cdot n \cdot m \cdot N \cdot \log_N \beta \) (for concrete parameters \( n \) is typically set as \( \log m / \log \lambda \)). Furthermore, these additions are performed over low-norm elements. Therefore, these additions happen with no modular reductions and could be efficiently vectorised due to the short bit-length of the coefficients.

The proof size has been estimated for the following parameters: \( L = 8 \), \( q = 2^{64} \), \( N = 128 \), \( m = 2^{20} \), \( B = 2^{25} \) and \( n = 12 \). For these parameters, the proof size is estimated to be around 175 KB. The settings are set to almost match those from [BC25b], with the exception of a smaller modulus \( q \) and norm set larger (since we are using \( \ell_2 \)-norms). Further, in [BC25b], the number of instances \( L \) is set to 3, which corresponds to two instances for the accumulator and one instance for the new relation. Here, we set \( L = 8 \) as we have 4 instances for the accumulator and we assume 4 instances of the new relation, which is more convenient as now \( L \) is a power of two. Upon adjusting \( L=5 \) parameters to match those from [BC25b] (4 instances for the accumulator and 1 instance for the new relation), we obtain a proof size around 110 KB, which matches the proof size from [BC25b].

Caveats

In this blog post, for the simplicity of exposition, we omitted some details regarding the precise parameter selection and security analysis.

1. We ignored the impact of the union bound on the soundness of the proof, i.e. we did not account for the number of times the Johnson-Lindenstrauss lemma is applied during multiple folding steps. This can be easily fixed by adjusting the parameters of the lemma accordingly, which might lead to a slight increase in the proof size. Careful analysis is available in [KLNO25]
2. For the efficiency analysis, we considered only the dominating terms of the prover's computation, i.e. the computation of the Johnson-Lindenstrauss projections. In practice, other steps, mainly homogenisation might also contribute significantly to the overall computation. The complexity of homogenisation is \( O(L \cdot m ) \) ring elements multiplication, where \( O(\cdot) \) notation hides small constant factor (practically, it should be around 6). Further, multiplication (involving modular reduction) is around 5 times more expensive (in our specific parameters regime) than addition. Also, we do not take advantage of shortness (i.e. small coefficients) of the elements during homogenisation, as we could during the Johnson-Lindenstrauss projections. In total, homogenisation might contribute around 30-40% of the overall prover's computation. Those estimates are rough, and we leave a more careful analysis for future work.
3. We limited our discussion to the case where the cyclotomic ring is a power-of-two cyclotomic ring. This assumption simplifies the discussion of complex conjugation and automorphisms. However, the techniques can be extended to general cyclotomic rings with some additional technical overhead.
4. We limited our discussion to the ring variant of the R1CS relation. However, the techniques can be extended to the field variant of the R1CS relation with some additional technical overhead, as shown in [NS24]. Further, on an orthogonal note, the techniques can be extended to other relations, such as the CCS relation, as shown in [BC25a].

Acknowledgements

I thank Binyi Chen (Stanford University) and Russell W. F. Lai (Aalto University) and David Balbás (IOHK) for comments on an earlier version of this blog post.

References

• [BS23]
  W. Beullens, G. Seiler; LaBRADOR: Compact Proofs for R1CS from Module-SIS; Eurocrypt 2023.
• [BC25a]
  D. Boneh, B. Chen; LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems; Asiacrypt 2025.
• [BC25b]
  D. Boneh, B. Chen; LatticeFold+: LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems; Crypto 2025.
• [GHL21]
  C. Gentry, S. Halevi, V. Lyubashevsky; Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties; Eurocrypt 2022.
• [KLNO24]
  M. Klooß, R. W. F. Lai, N. K. Nguyen, M. Osadnik; RoK, Paper, SISsors - Toolkit for Lattice-based Succinct Arguments; Asiacrypt 2024.
• [KLNO25]
  M. Klooß, R. W. F. Lai, N. K. Nguyen, M. Osadnik; RoK and Roll - Verifier-Efficient Random Projection for \( \tilde{O}(\lambda) \)-size Lattice Arguments; Asiacrypt 2025.
• [KLOT25]
  S. Kuriyama, R. W. F. Lai, M. Osadnik, L. Tucci; SALSAA - Sumcheck-Aided Lattice-based Succinct Arguments and Application.
• [NS24]
  W. Nguyen, S. Setty; Neo: Lattice-based folding scheme for CCS over small fields and pay-per-bit commitments.
• [STW23]
  S. Setty, J. Thaler, R. Wahby; Customizable constraint systems for succinct arguments

For citation purposes, please use the following BibTeX entry: