Introduction In STARK-based proof systems, execution traces of computations are typically represented as structured arrays over a finite field. Specifically, we consider a trace matrix $M \in \mathbb{F}^{T \times w}$, where each row corresponds to the state of a virtual machine (VM) at a given timestep, and each column represents one of the $w$ registers of the machine. A fundamental aspect of STARK proofs is verifying that this execution trace satisfies a predefined set of constraints. These constraints are typically expressed as a collection of multivariate polynomials, $\mathcal{P} = { P(x_1, ..., x_w, y_1, ..., y_w) }$, which enforce relations between successive rows of the trace. Formally, the prover must convince the verifier that for all $P \in \mathcal{P}$, the constraints hold across adjacent rows, i.e., $P(\vec{m}t, \vec{m}{t+1}) = 0$, where $\vec{m}_t$ denotes the state of the machine at timestep $t$. However, polynomial constraints between adjacent rows are just one type of constraint that STARKs can enforce. These protocols also support boundary constraints and polynomial relations that extend beyond immediate row adjacency, enabling more flexible and expressive proof systems. Extending STARKs with lookup arguments While STARK protocols efficiently verify computations by enforcing polynomial constraints over an execution trace, they are inherently limited to operating on a single trace. This constraint introduces several challenges:

This document aims to list some potential risks/fears we have around post quantum signature aggregation for the beam chain so that we keep them in mind for the future. This could help to quantify the risks and impacts. An attack on Poseidon2 emerges. There's a loss of confidence in it and doubling the number of rounds is insufficient to appease cryptanalysts. Implementation complexity is too high to fully formally verify the verifier. An attack on fiat-shamir (eg diagonalisation 2.0) is found. An attack on recursion is found. [parametrisation] The industry standardises on binary fields and the fastest hardened hash function is significantly slower than Poseidon2. [parametrisation] The way we compile WHIR to Whirlaway is buggy and we suffer a significant performance penalty when reparametrising. [parametrisation] A mistake in the WHIR security proof is found. We fallback to FRI and suffer a ~2x cost? [parametrisation] The proximity gaps conjecture we rely on is found to be false. We suffer a ~2x cost?

In this technical note, we unpack and explain the recent note Logup: faster, cheaper logup argument for small-table indexed lookups by Lev Soukhanov (May 2025). The paper proposes a new technique to perform indexed lookup arguments in zero-knowledge proof systems more efficiently when the lookup tables are small. We will build up the background, provide intuition, and carefully walk through the mathematics involved. Introduction: The Lookup Argument In many zero-knowledge proof systems, we often need to check that a list $X$ of witness elements is contained within some table $T$. This is called a lookup argument and arises, for example, when constraining values to be in a valid range or when using precomputed tables. For arrays $X, T$ over a large field $F$, we want to prove $$

This note is an informal proposal for structuring the early chapters of a future zkEVM book. The goal is to identify and draft foundational material that could serve as a reference for people interested in the zkEVM project — its motivations, design considerations, and long-term vision. These sections are not yet about technical implementation. Instead, they aim to capture high-level framing, open questions, and shared context that will help guide the development of the book over time. Why zkEVM? This chapter should articulate the core motivations behind zkEVM. While there are many perspectives within the community, we propose including discussion around the following: What are we trying to achieve with zkEVM? Why can't we increase the gas limit? State proof and execution proof

Beam Chain context In the Beam Chain, validators play a crucial role in attesting the validity of Ethereum blocks using their cryptographic signatures. Each validator possesses a key pair (private and public key), and their signatures collectively ensure the integrity of the blockchain. However, storing every validator’s signature on-chain for each block is prohibitively expensive in terms of both cost and data storage. To address this, we need an efficient method to aggregate these signatures before committing them on-chain. image Currently, Ethereum’s Beacon Chain relies on BLS signatures using the BLS12-381 elliptic curve. These signatures are compact and, thanks to the pairing properties of BLS, can be efficiently aggregated—making them well-suited for consensus. However, a critical drawback of BLS signatures is their vulnerability to quantum attacks. Since they rely on elliptic curve cryptography and the discrete logarithm problem, a sufficiently powerful quantum computer could break their security. This presents a long-term risk to Ethereum’s consensus model in a post-quantum world. Our goal is to develop a post-quantum multi-signature scheme—one that enables both individual signatures and efficient aggregation—ensuring Ethereum remains secure against quantum threats while maintaining scalability and efficiency.

Offline memory checking is a technique for verifying that memory was accessed correctly, even when the memory is untrusted. First introduced in a 1995 paper by Blum et al., this method forms the backbone of many modern zero-knowledge virtual machines (zkVMs), such as zkMIPS or Jolt. Unlike online methods that check memory correctness during execution (e.g., using Merkle trees), offline memory checking allows efficient batch verification after execution has finished. In this post, we unpack the theoretical foundations and practical constructions of offline memory checking, and how it is applied in SNARK/STARK-based zkVMs. Motivation: Programs with Side Effects Traditional program checkers assume pure functions: given an input, is the output correct? But real-world programs manipulate state via memory reads and writes. For example, a virtual machine executing RISC-V code updates RAM over time. The challenge: can a verifier confirm that each memory read returns the latest value written to that address, without storing the entire memory history? Offline memory checking solves this by asking the prover to produce a trace of memory operations that can be compactly verified for correctness.

Introduction Our proof system is designed to perform signature aggregation of the Beam Chain efficiently. The underlying protocols are interactive, requiring a prover and verifier to exchange a sequence of messages. However, in a high-throughput, decentralized environment like ours, interactive rounds are impractical and introduce unnecessary overhead. The Fiat-Shamir (FS) transform provides an elegant and rigorous way to eliminate this interaction. By replacing the verifier’s random challenges with the output of a cryptographic hash function, the prover can simulate the entire protocol transcript in a non-interactive way. This enables the construction of compact, self-contained proofs that can be verified without back-and-forth communication. Why Fiat-Shamir works In a public-coin protocol, the verifier’s messages consist only of random challenges. Instead of requiring the verifier to generate these challenges interactively, the FS transform derives them deterministically by hashing the current transcript. Specifically, at each step, the prover computes: \begin{equation} c_i = H(x, m_1, m_2, \dots, m_{i-1})

Introduction WHIR is a new cryptographic protocol that drastically speeds up verification in interactive proofs. It achieves this by offering a super-efficient IOP of proximity for constrained Reed–Solomon codes. Unlike existing protocols such as FRI, STIR, or BaseFold, WHIR enables verification in just a few hundred microseconds—orders of magnitude faster than traditional approaches that take several milliseconds or more. At its core, WHIR enables fast and succinct proofs for statements expressed via polynomial IOPs (poly-IOPs). These are interactive protocols where the prover's messages are evaluations of low-degree polynomials over a finite field. Poly-IOPs are widely used to construct SNARGs (Succinct Non-interactive Arguments), which are cryptographic proofs that are short and easy to verify. WHIR significantly improves this landscape by reducing the verifier time without sacrificing prover efficiency or increasing proof size. Context: SNARGs and Poly-IOPs SNARGs are compact proofs used in many applications, from blockchain to cloud computing, where both proof size and verification time matter. A common way to build SNARGs is through poly-IOPs, where the prover is restricted to polynomial messages, and then compile these into SNARGs using polynomial commitment schemes like KZG or inner-product-based schemes. This pipeline has led to highly efficient SNARG systems. image

Introduction: why and how WHIR could be used for Ethereum in the future? For Ethereum, proof size and verification time are crucial.We want validators to run on very small devices (ultimately Raspberry pi pico 2 as highlighted by Justin Drake during ethproofs call #2) in order to improve decentralization of the network. Signature aggregation for the beam chain will be considered as the main example during all this post without loss of generality. Recently, we have seen a wave of switches from traditional univariate polynomial techniques to multilinear settings for zk proofs. Jagged PCS is a very good example of this because it marks this very important switch, achieving real time proving for the first time using multilinear pcs. In univariate settings, the prover must commit to, and provide evaluation proofs of each of the column polynomials of the trace. As we often have a huge number of columns, these operations dominate the verifier's runtime in modern hash-based systems such as SP1. Justin Thaler has long emphasized the beauty, simplicity and importance that sumcheck should have in future proof systems.

Repository: rust-eth-kzg This report summarizes the main improvements made during the internal audit of the KZG Ethereum repository. While this is not a formal audit report, it’s intended to give an organized and clear overview of the work done, grouped by theme, with representative pull requests (PRs). Observations Overview Overall the codebase is very well-documented. For further resources: Reference implementation in Python:EIP4844 → https://github.com/ethereum/consensus-specs/blob/017a849/specs/deneb/polynomial-commitments.md EIP7594 → https://github.com/ethereum/consensus-specs/blob/13ac373/specs/_features/eip7594/polynomial-commitments-sampling.md

Why linear accumulation matters Distributed systems often need to prove that many individual checks are all correct without re-examining every witness, that is the case for the application we target: post-quantum signature aggregation for the beam chain. Proof-carrying data (PCD) solves this, but until now its key sub-component—an accumulation scheme—forced the prover to do more than linear work. image The WARP protocol changes that: its prover runs in time proportional to the size of the data it really touches, while the verifier touches only a logarithmic fraction. A faster accumulation scheme speeds up every application that stacks many proofs together. How Incremental Verifiable Computation (IVC) connects To understand why linear accumulation matters, it helps to first look at incremental verifiable computation (IVC), introduced by Val08.

A linear code is one of the most fundamental tools in coding theory. It allows us to add redundancy to a message in a structured way, so that errors introduced during transmission can be detected and even corrected. Definition Let $\mathbb{F}_p$ be a finite field with $p$ elements. An $[n, k, \ell]_p$ linear code $\mathcal{C}$ is a linear subspace of $\mathbb{F}_p^n$ with dimension $k$, such that every nonzero codeword has Hamming weight at least $\ell$: \begin{equation} \mathcal{C} \subseteq \mathbb{F}_p^n \quad \text{is a $k$-dimensional subspace}, \quad \text{with } |u|_0 \geq \ell \text{ for all } 0 \ne u \in \mathcal{C} \end{equation} Since $\mathcal{C}$ is a $k$-dimensional subspace over $\mathbb{F}_p$, it contains exactly $|\mathcal{C}| = p^k$ codewords.

Why Succinct needs another Polynomial Commitment? Modern SNARKs almost always rely on a polynomial commitment scheme (PCS). A PCS lets a prover commit to a huge polynomial $P$ in one short hash-like value and later prove statements of the form “$P(x)=y$’’ without revealing $P$ itself. Inside a zkVM, the usual workflow is: Represent the whole CPU trace as many rectangular tables—one per instruction. Encode every column of every table into its own low-degree polynomial. Commit to those polynomials individually with a PCS and prove all the required row-wise constraints. Committing column-by-column is easy conceptually but hurts performance:

This note explains a recursive and parallelizable method for in-place transposition of a square matrix stored in a 1D array. The matrix is assumed to be of size $2^{\ell} \times 2^{\ell}$ for some integer $\ell$. Memory layout and indexing The square matrix is stored in a 1D row-major array arr. The matrix location $M[i, j]$ is stored at: \begin{equation} \text{index} = ((i + x) \ll lb_{stride}) + (j + x) \end{equation} Here:

Standard Case Let’s begin with a concrete example, similar to the one used for the univariate skip case, and fully covered by a test: https://github.com/tcoratger/whir-p3/blob/818cc85716518a365d765ba66b818e2e7cfe7792/src/sumcheck/sumcheck_single.rs#L1813 We define a multilinear polynomial via hardcoded coefficients: \begin{aligned} f(X_0, X_1, X_2) &= 1 + 2X_2 + 3X_1 + 4X_1X_2 + 5X_0 + 6X_0X_2 + 7X_0X_1 + 8X_0X_1X_2 \end{aligned}

Overview A Reed-Solomon code is a method for encoding a message (i.e., a polynomial) as a redundant sequence of values (a codeword) such that missing values (erasures) can be recovered—so long as they don't exceed a threshold. In our Rust implementation: Encoding uses an FFT over a multiplicative subgroup of a finite field. Decoding leverages a vanishing polynomial $Z(X)$ to nullify known erasure positions. Recovery solves for the original polynomial using division and interpolation. Polynomial encoding via FFT

Context The Sumcheck protocol is a fundamental interactive proof protocol used to verify that the sum of a multivariate polynomial over all points of the Boolean hypercube is equal to a claimed value. Let us suppose that the prover $\mathcal{P}$ knows a multivariate polynomial function $\hat{f}(X_0, \dots, X_{n-1})$, and wants to convince the verifier $\mathcal{V}$ that the following sum is correct: \begin{equation} v = \sum_{\mathbf{x} \in {0,1}^n} \hat{f}(\mathbf{x}) \end{equation} Here, $\mathbf{x}$ denotes a binary vector in the Boolean hypercube ${0,1}^n$. That is, $\mathbf{x} = (x_0, x_1, \dots, x_{n-1})$ where each $x_i \in {0,1}$.

The SNARK designer's dilemma: small-field arithmetic vs. large-field commitments For those of us deep in the trenches of SNARK design and implementation, the pursuit of prover efficiency is relentless. We're constantly seeking ways to reduce cryptographic overhead and make zero-knowledge proofs more practical for increasingly complex computations. One of the most effective strategies on this front has been the adoption of tiny fields for the arithmetization phase of a SNARK. The quest for prover speed via tiny fields When we represent a computation as an arithmetic circuit or a system of polynomial equations, the choice of the underlying finite field K for this representation has profound performance implications. Using "tiny" fields – such as the prime field F_2 (especially relevant for binary circuits) or other small prime fields F_p (e.g., 32-bit or 64-bit primes like Goldilocks or Baby Bear) – drastically reduces the bit-length of operands. This, in turn, speeds up the polynomial arithmetic (NTTs/FFTs, multiplications, additions) that forms the backbone of most prover algorithms. The benefits are clear: faster provers, lower computational costs, and increased throughput. The Polynomial Commitment Scheme (PCS) challenge While tiny fields are a boon for arithmetization, the cryptographic heart of many SNARKs – the Polynomial Commitment Scheme (PCS) – often presents a different set of requirements. Many powerful and efficient PCS for multilinear polynomials (MLPs), which are a common choice for modern arithmetizations, are naturally constructed or achieve optimal properties (like succinctness or pairing-friendliness for KZG-based schemes, or concrete efficiency for FRI-based schemes) when operating over larger extension fields L of our tiny arithmetization field K. This creates a fundamental tension:

Introduction: Folding schemes made simple A folding scheme is a cryptographic tool that helps compress multiple checks into one. Instead of verifying two computations separately—say, that C(w₁, x₁) = 1 and C(w₂, x₂) = 1—a folding scheme reduces this to checking a single pair (w, x). This idea is surprisingly powerful. When applied recursively, it becomes the backbone for advanced techniques like: Incrementally verifiable computation (IVC): Verifying long computations in small, constant time. Proof-carrying data (PCD): Chaining together many computations with trustable proofs. The Problem with traditional SNARKs Most SNARKs today use a combination of:

Introduction This report focuses on the evaluation of proof systems suitable for signature aggregation, based on our current assumptions and early design explorations. At the moment, we are working with the signature scheme proposed in Hash-Based Multi-Signatures for Post-Quantum Ethereum. While alternative schemes (e.g., lattice-based signatures) are being discussed both internally and externally, we use this hash-based scheme as a reference point to guide our initial evaluations of proof systems. A change in the underlying signature scheme could impact the proof system design, but the current setup offers a concrete baseline for early investigation. From the start of the project, the "minimal VM" approach has been presented as the preferred path forward. The rationale for this direction includes: Encapsulating the proving logic within the VM to reduce the cryptographic complexity for client teams. Providing a clean and centralized specification at the VM level for the beam chain. Improving security by reducing the need for teams to write and verify their own circuits.