The Ligero Protocol

For the Curious Reader

This section dives into the mathematical and technical foundations of the Ligero protocol. If you're here to build applications with Ligetron, feel free to skip ahead—you don't need to understand these details to write zero-knowledge programs.

But if you're curious about the cryptographic magic under the hood, we invite you to explore! The protocol combines elegant ideas from coding theory and multi-party computation in surprisingly creative ways to achieve post-quantum security with sublinear proof sizes.

Zero-Knowledge Proofs: Background

Zero-knowledge is a cryptographic object that enables one party to prove the validity of a mathematical statement without revealing the underlying information. Example: one can prove they're over 18 without showing their birthdate, or prove they have enough money for a transaction without showing their full bank account. More formally, a zero-knowledge proof (ZKP) is an interactive or non-interactive protocol between a prover and a verifier where the prover convinces the verifier that a statement is true. ZKPs are designed with three properties:

• Completeness – If the claim is valid and both parties follow the protocol, the verifier will be convinced.

• Soundness – If the claim is false, no cheating prover can trick the verifier (except with negligible probability). Soundness is typically achieved through random challenges from the verifier (forcing the prover to commit before knowing the challenge), algebraic checks like polynomial commitments, or cryptographic assumptions (e.g., hardness of discrete log or hash functions).

• Zero-Knowledge – The verifier learns nothing else beyond the fact that the claim is valid. This property is achieved by designing an efficient simulator that produces a "similar-looking" proof without accessing the prover's secret state.

The efficiency of an interactive proof is typically measured along a few key parameters: communication complexity (how many bits are exchanged between prover and verifier), round complexity (how many back-and-forth interactions are required), and prover/verifier time (how much computation each side performs). For practical systems, especially zero-knowledge proofs, these directly determine scalability: a proof may be theoretically sound, but if it requires dozens of rounds, heavy prover computation, or large transcripts, it becomes unusable. The sweet spot is protocols with low communication, minimal rounds (often constant), fast verification, and prover time that scales linearly or nearly linearly in the statement size.

The MPC-in-the-Head Paradigm

The Ligero proof system is an interactive PCP designed for efficient zero-knowledge proofs that do not rely on heavy cryptographic machinery. It is based on coding-theoretic techniques and hash functions, and achieves sublinear verification time and quasilinear prover time. The protocol encodes the witness using error-correcting codes and allows the verifier to check consistency through three tests, making it particularly efficient for large arithmetic circuits. Ligero stands out for its transparency (no trusted setup), post-quantum security, and prover efficiency.

At the core of Ligero is the MPC-in-the-Head (introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai in 2007) paradigm that transforms secure multi-party computation (MPC) into a zero-knowledge proof. Instead of actually running MPC among multiple parties, the prover locally simulates the execution in their "head," committing to all virtual parties' views. To verify, the prover opens a subset of these views, and the verifier checks consistency. This approach is highly flexible, black-box over underlying primitives, and yields simple, lightweight zero-knowledge proofs.

In this paradigm, both soundness and privacy are inherited directly from the correctness and privacy guarantees of the underlying MPC protocol. Soundness follows from correctness: if the function output is incorrect, then in any honestly executed MPC, at least one party's view must reveal inconsistency. Since the prover commits to all views before the verifier's challenge, opening a random subset ensures that any deviation from a correct execution is detected with high probability. Privacy follows from the privacy of the MPC: by construction, the view of any strict subset of the parties leaks nothing about the private inputs. Thus, when the verifier inspects only a randomly chosen subset of views, the unopened views preserve the secrecy of the witness, ensuring that no additional information is revealed beyond the validity of the statement.

A key advantage of the MPC-in-the-Head paradigm is its flexibility: one can plug in different MPC protocols as the underlying engine, and the resulting zero-knowledge proof inherits their efficiency and security characteristics. For example, using a protocol with a small number of parties yields a larger soundness error, while protocols with more parties allow for reducing the soundness error. Similarly, the corruption threshold of the MPC directly dictates the zero-knowledge leakage bound: if privacy holds against any coalition of up to $t$ parties, then revealing $t$ views in the proof preserves zero-knowledge. This modularity means that by choosing different MPC instantiations, optimized for arithmetic circuits, Boolean circuits, or specific adversarial models, one obtains a whole spectrum of zero-knowledge protocols with varying trade-offs in proof size, prover time, and verifier time.

Ligero can be viewed as instantiating MPC-in-the-Head with an honest-majority MPC protocol secure against malicious adversaries. The prover simulates parties executing a secret-sharing–based protocol where both correctness and privacy are guaranteed under an honest majority. Malicious security is crucial for the analysis: it ensures that even if the prover attempts to cheat by misreporting the views of up to $t$ parties, the MPC protocol still enforces consistency, and any deviation beyond that threshold will be detected with noticeable probability. This stronger guarantee enables a sharper soundness analysis than in the weaker semi-honest setting, where the misbehavior of even a single party can invalidate the execution.

Ligero can also be understood through the lens of an Interactive Oracle Proof (IOP). In this model, the prover sends messages that can be viewed as oracles, large, encoded objects that the verifier queries at random locations rather than reading in full. This framework generalizes both interactive proofs and PCPs, offering the efficiency of a few rounds with the scalability of oracle access. Ligero's use of codeword encodings and Merkle commitments makes it a direct instantiation of an IOP: the prover commits to an oracle (the encoded matrix) and the verifier inspects only a few queried positions.

The Ligero Proof System

High-Level Overview

The novelty in the analysis of Ligero lies in achieving the first sublinear proof sizes by tightening the soundness argument through the use of adaptive malicious security. Unlike semi-honest or static-security settings, here the adversary (the prover) can adaptively decide which parties to "corrupt" after seeing the verifier's challenge, corresponding to which views will be opened. The new analysis ensures that the underlying MPC protocol is secure even under such adaptive corruptions. By leveraging this stronger guarantee, the analysis rules out such strategies and shows that the probability of consistent cheating drops rapidly, allowing Ligero to compress the proof size below linear for the first time in the MPC-in-the-head paradigm.

At a high level, the Ligero proof system works as follows: the prover encodes the witness into a structured matrix and convinces the verifier of correctness through three checks. It has five main steps:

1. Matrix Preparation – The prover first encodes the witness (the satisfying assignment to the circuit), together with the internal values of the circuit, into a two-dimensional matrix of codewords, denoted by $U$, so that each row is an evaluation of a low-degree polynomial. This encoding enables both redundancy (for error-checking) and algebraic structure (for enforcing circuit relations).

2. Commitment Phase – The prover commits to the entire matrix by hashing its columns into a Merkle tree and sending the root to the verifier. This ensures binding: once the root is fixed, the prover cannot change individual entries without being caught.

3. Challenge Phase I – The verifier samples random vectors that define random linear combinations of the rows of $U$. This process "folds" the matrix into three aggregated codewords, each representing a weighted sum of the original rows. The degree, linear, and quadratic tests are then applied to these folded codewords instead of the full matrix, reducing communication and verification complexity.

4. Opening Phase – To ensure that the folded codeword is consistent with the committed matrix, the verifier performs a spot-check: it randomly selects a small subset of columns $Q \subseteq [n]$ and asks the prover to open those columns of $U$, together with their corresponding Merkle authentication paths.

5. Challenge Phase II – Finally, the verifier performs a consistency check to ensure that the folded codewords correspond to the committed matrix $U$. To do so, it samples a small random subset of columns and requests the prover to open the corresponding entries in $U$, together with their Merkle authentication paths. For each opened column, the verifier checks that the value of the folded codeword equals the same random linear combination of the opened entries from $U$.

The Three Core Tests

The Ligero proof system applies three core tests to enforce soundness:

1. Degree Test – Ensures that the prover’s committed vectors correspond to evaluations of low-degree polynomials (or codewords of a Reed–Solomon–type code). This test prevents the prover from providing non-codewords.

2. Linear Test – Verifies that linear constraints between committed values hold correctly. For example, if the circuit specifies $z = x + y$, then the encodings of $x, y,$ and $z$ must satisfy the same relation in the code domain.

3. Quadratic Test – Enforces correctness of multiplication gates by checking that encodings of $x, y,$ and $z$ are consistent with the relation $z = x \cdot y$.

Together, these three tests ensure that the prover’s encoding is simultaneously a valid low-degree assignment and that it satisfies all circuit constraints. We continue with more details.

The Technical Details of Ligero

Building Blocks

Ligero is built upon two fundamental cryptographic tools: error-correcting codes and hash functions. It employs Reed–Solomon codes to encode the prover's witness into structured codewords corresponding to low-degree polynomials, and uses Merkle trees to commit to the encoded matrix while enabling efficient selective verification. Together, these primitives enable the prover to commit to a large computation trace and allow the verifier to check correctness by examining only a small random sample.

Reed–Solomon Codes

Reed–Solomon codes interpret $k$ data points as evaluations of a degree $<k$ polynomial and evaluate this polynomial over a domain of size $n$. Formally, the Reed–Solomon code $RS(\mathbb{F}, D, k)$ consists of all evaluations of polynomials in $\mathbb{F}[x]$ of degree strictly less than $k$ on domain $D$, where $|D| = n$. This creates a $k$-dimensional subspace of $\mathbb{F}^n$ with rate $\rho = k/n$.

RS codes are particularly well-suited for Ligero because they are highly parallelizable and rely on fast Fourier transform (FFT) techniques that are efficiently optimized. These properties enable efficient encoding and verification of the prover's witness.

Why Reed–Solomon codes enable fast verification: Any two distinct polynomials of degree $<k$ differ on at least $n - k + 1$ points (the minimum distance property). This means that if a prover attempts to cheat with invalid data, the corrupted encoding will be far from any valid codeword in Hamming distance. Random sampling detects such deviations with overwhelming probability, allowing the verifier to check correctness by examining only a small subset of positions instead of inspecting all values.

Merkle Trees

A Merkle tree is a cryptographic commitment scheme that allows the prover to commit to a large dataset while enabling efficient selective verification. The prover organizes the data as leaves of a binary tree, where each internal node stores a cryptographic hash of its two children. The root hash serves as a compact commitment to the entire dataset.

To open a specific value at position $j$, the prover reveals the value together with an authentication path: the sequence of sibling hashes along the path from the leaf to the root. The verifier recomputes the root hash from this path and checks that it matches the committed root. This allows verification of individual positions in $O(\log n)$ time and space, instead of requiring the verifier to process the entire dataset.

In Ligero, the prover commits to the encoded matrix $U$ by hashing each column and building a Merkle tree over these column hashes. This commitment is binding: once the root is fixed, the prover cannot change individual entries without being detected. During verification, when the verifier requests specific columns at random indices, the prover opens those columns along with their Merkle authentication paths, proving consistency with the committed root.

Defining the Matrix $U$

• Given the secret witness (or the secret state) $w$, the prover first extends it to an extended witness $\hat{w}$ by computing the values of all internal wires in the circuit (so $\hat{w}$ has length equal to the total number of internal wires and the inputs).

• The extended witness $\hat{w}$ is then partitioned into blocks: the prover arranges these wire values into an $m \times \ell$ matrix, where each row corresponds to a block of wires and each column corresponds to one of the $\ell$ parallel "slots."

• Each row of this matrix is then encoded as a Reed–Solomon codeword: the prover interprets the $\ell$ entries of row $i$ as evaluations of a low-degree polynomial at $\ell$ points, interpolates this polynomial, and then evaluates it at a larger set of $n$ points. More formally, each row $u_i \in \mathbb{F}^\ell$ is viewed as evaluations of a polynomial $p_i(z)$ of degree $< \ell$ on a set of $\ell$ "message points" $\zeta_1, \dots, \zeta_\ell$. The polynomial is then evaluated on a larger set of $n$ "codeword points" $\eta_1, \dots, \eta_n$, producing an extended row of length $n$.

• Collecting all rows after encoding yields the final matrix $U \in \mathbb{F}^{m \times n}$.

The Degree Test

The degree test ensures that each row of the prover’s committed matrix $U$ corresponds to a valid low-degree polynomial, that is, that all codewords in $U$ lie within the Reed–Solomon code of prescribed degree. This test enforces the fundamental algebraic structure of the proof system, guaranteeing that the prover’s encodings are consistent with the polynomial code and preventing the use of arbitrary or inconsistent data that could satisfy later tests by chance.

Recall that in Ligero, the prover encodes its extended witness into a matrix $U \in \mathbb{F}^{m \times n}$, where each row $U_i$ is intended to represent the evaluations of a polynomial $p_i(X)$ of degree $<k$ on a fixed set of evaluation points $\eta_1, \dots, \eta_n$. The verifier’s task is to check that every row indeed corresponds to such a low-degree polynomial, without having to interpolate each one in full.

High-Level Idea

The parties perform a randomized folding of the matrix $U$ into a single aggregated polynomial, and the verifier verifies that the aggregate has degree $<k$. This is accomplished by choosing a random linear combination of the rows of $U$, effectively compressing all degree constraints into a single one. Intuitively, if any row of $U$ deviates significantly from the code, the random combination will inherit these errors, causing the test to fail.

In more detail:

The verifier samples a random vector $r \in \mathbb{F}^m$ and sends it to the prover.

The prover computes the aggregated codeword

$$U_r = \sum_{i=1}^{m} r_i U_i,$$

which represents the evaluation vector of the aggregated polynomial

$$p_r(X) = \sum_{i=1}^{m} r_i p_i(X),$$

and sends it to the verifier. Because each $p_i(X)$ should have a degree $<k$, a valid $p_r(X)$ must also have a degree $<k$.

To check consistency with the commitment, the verifier challenges the prover with a small random subset of columns $Q \subseteq [n]$ of size $t$ (typically $t = O(\kappa)$ where $\kappa$ is the security parameter). The prover then decommits the corresponding columns of $U$, providing the column values and their Merkle authentication paths to the verifier.

For each opened column index $j \in Q$, the verifier checks that the revealed values are consistent with a single low-degree polynomial, namely, that the polynomial $p_r(X)$ satisfies

$$p_r(\eta_j) = \sum_{i=1}^{m} r_i U[i,j].$$

If any discrepancy arises, the verifier rejects.

The security analysis of the degree test considers the distance of the prover’s matrix $U$ from the valid code subspace. There are two cases. If $U$ is close to a valid code, specifically, if every row differs from a proper Reed–Solomon codeword by fewer than half the code’s minimum distance, then the folded codeword produced by any random linear combination will also be close to a valid codeword with high probability, and the verifier will accept only if the encoding is essentially correct. Conversely, if $U$ is far from the code, meaning that at least one row deviates by more than half the minimum distance, this deviation will manifest in the folded codeword with high probability, causing the verifier’s low-degree check to fail. Thus, the degree test ensures that either the committed matrix is already near a valid low-degree encoding, or the inconsistency propagates to the folded codeword and is detected with overwhelming probability. We note that Ligero does not rely on any unproven proximity gap conjectures.

The Linear Test

In Ligero, all linear constraints of the circuit (additions, scalar multiplications, copy / wiring constraints, and boundary conditions) are encoded in a sparse linear system $Ax = b$, where $x$ represents an assignment to all the wires in the circuit. The linear test verifies that the prover holds a satisfying assignment without the verifier checking every constraint explicitly. Instead, the verifier checks a random linear combination of the constraints. Because the prover commits to its encoding before learning the randomizer, any inconsistency in $Ax = b$ is detected with high probability.

Concretely, let $A \in \mathbb{F}^{m\ell \times m\ell}$ be the sparse constraint matrix encoding the circuit. The verifier samples a random vector $r \in \mathbb{F}^{m\ell}$ and sends it to the prover. Both parties compute the linear combination $r^\top A$. The prover claims to hold an $x \in \mathbb{F}^{m\ell}$ satisfying $Ax = b$. The verifier checks whether $r^\top A x = r^\top b$ using $U$ (the encoding of $x$) without obtaining $x$ directly.

To perform this check, the prover reshapes $r^\top A$ (a vector of length $m\ell$) into an $m \times \ell$ matrix:

$$R' := r^\top A = \begin{bmatrix} r_{11} & r_{12} & \dots & r_{1\ell} \\ \vdots & \vdots & \ddots & \vdots \\ r_{i1} & r_{i2} & \dots & r_{i\ell} \\ \vdots & \vdots & \ddots & \vdots \\ r_{m1} & r_{m2} & \dots & r_{m\ell} \\ \end{bmatrix}.$$

The prover then forms the following $<k + \ell - 1$ degree polynomial, and sends it to the verifier:

$$q(\cdot) = \sum_{i=1}^m r_{i}(\cdot)\, p_i(\cdot)\;,$$

where:

• $r_i(\cdot)$ is the $<\ell$ degree polynomial obtained by interpolating the $i^\text{th}$ row of $R'$ (i.e.: the points $r_{i1}, r_{i2}, \dots, r_{i\ell}$); and
• $p_i(\cdot)$ is the $<k$ degree polynomial obtained by interpolating the $i^\text{th}$ row of $U$, the encoding of the extended witness.

As above, to verify consistency with the committed matrix, the verifier challenges the prover with a subset of columns that the prover then decommits. For each opened column $U[j]$, the verifier checks that $\langle R[j], U[j] \rangle = q(\eta_j)$, where $U[j]$ denotes the $j$-th column of $U$, and

$$R[j] = \begin{bmatrix} r_1(\eta_j) \\ \vdots \\ r_i(\eta_j) \\ \vdots \\ r_m(\eta_j) \end{bmatrix}.$$

Conditioned on the degree test passing, the soundness of the linear test follows from two complementary cases. In the first case, the prover sends the correct polynomial, one that truly represents the encoded linear relations. However, if the committed matrix does not actually satisfy these relations, the test will reject with high probability. In the second case, the prover tries to cheat by sending an incorrect polynomial that does not correspond to the committed data. This inconsistency is detected in the subsequent spot checks, where the verifier opens a few random columns to compare the polynomial values with the committed entries.

This test is also the only component that prevents the Ligero verifier from achieving a fully sublinear runtime with respect to circuit size. The verifier must explicitly evaluate the linear relations, which introduces a linear dependence on the circuit description. However, this limitation can be avoided with a preprocessing phase: the prover can precompute the necessary linear constraint combinations and prove their correctness using an additional, simpler proof (since this computation is uniform). Incorporating this preprocessing step, which is being integrated into the Ligero framework, will allow the verifier’s work to become fully sublinear.

The Quadratic Test

The quadratic test verifies that the prover’s committed encoding matrix $U$ correctly enforces all multiplication constraints in the circuit. While the linear test ensures that additive and scalar relations between encoded variables hold, the quadratic test guarantees that for each multiplication gate ($z = x \cdot y$), the corresponding rows in $U$ represent encodings consistent with that relation.

In the commit phase, the prover rearranges the rows of $U$ so that for every multiplication gate, the three rows representing the left input $x$, right input $y$, and output $z$ appear consecutively. We denote these groups of rows as $U_x, U_y, U_z$. Each of these rows is an evaluation of a low-degree polynomial over the same set of codeword points, and the verifier’s goal is to check that rows satisfy the quadratic relation.

The verifier samples a random vector $r \in \mathbb{F}^m$ and sends it to the prover. Using this vector, both parties form the polynomial

$$p_Q(X) = \sum_{i=1}^m r_i \cdot (p_{x,i}(X) \cdot p_{y,i}(X) - p_{z,i}(X)),$$

where $p_{x,i}, p_{y,i},$ and $p_{z,i}$ are the degree-bounded polynomials corresponding to the $i$-th rows of $U_x, U_y, U_z$, respectively. If all multiplication constraints hold, then for every point $\zeta_j$ in the witness domain (where $j = 1, \dots, \ell$),

$$p_{x,i}(\zeta_j)\cdot p_{y,i}(\zeta_j) = p_{z,i}(\zeta_j),$$

and therefore $p_Q(\zeta_j) = 0$ for all $j \in \{1, \dots, \ell\}$.

Similarly to the linear test, to verify consistency, the verifier selects a random subset of columns $Q \subseteq [n]$ of size $t$. The prover opens those columns of $U_x, U_y, U_z$ together with the Merkle authentication paths. For each opened column $j \in Q$, the verifier checks that

$$p_Q(\eta_j) = \sum_{i = 1}^m r_i(U_x[i,j] \cdot U_y[i,j] - U_z[i,j])$$

where $\eta_j$ is the evaluation point corresponding to column $j$.

The soundness analysis follows a similar approach to the analysis of the linear test.

Achieving Zero-Knowledge

Ligero achieves zero-knowledge by masking all prover messages with carefully chosen randomness before commitment. The prover adds random low-degree polynomials to each encoded row so that the committed matrix hides the actual witness while preserving the structure needed for verification. During the tests, the verifier only sees a few randomly sampled positions, each masked by these randomizers and protected by the Merkle commitment. As a result, the verifier learns nothing beyond the validity of the statement, ensuring full zero-knowledge without relying on encryption or additional assumptions.

Proof Size and Matrix Dimensions

The proof size in Ligero is determined by the communication between prover and verifier across all three tests. Understanding this relationship helps explain why certain matrix dimensions lead to smaller proofs.

Matrix Structure and Encoding

Starting with a circuit, the extended witness is arranged into an $m \times \ell$ matrix, where $\ell$ is the packing parameter. Before encoding, each row is padded with random field elements to length $k$, where $k$ is the smallest power of 2 satisfying $k \geq \ell$. This padding serves dual purposes: it enables efficient FFT-based Reed-Solomon encoding (which requires power-of-2 dimensions) and provides additional randomness for zero-knowledge. After Reed-Solomon encoding (4× expansion), the final committed matrix has dimensions $m \times n$, where $n = 4k$.

Communication Pattern

During the protocol, the prover sends two types of messages:

1. Row-sized messages: In the linear and quadratic tests, the prover sends polynomials computed from random linear combinations of rows. These messages have size proportional to $n = 4k$.

2. Column-sized messages: In all three tests, the verifier randomly samples $t$ column indices and the prover opens the corresponding columns of the committed matrix $U$. Each opening includes both the column values and Merkle authentication paths. The size of these messages is proportional to $m \cdot t$, where $m$ is the number of rows.

For a circuit with $N$ original witness elements and $s$ multiplication gates, the extended witness requires $m \cdot \ell > N + 3s$ field elements. The factor of 3 accounts for the multiplication gate structure: each gate contributes three values (two inputs and one output), and wire values may appear multiple times if they connect different gates.

The Square Matrix Principle

Given a fixed circuit size, the proof size is minimized when the encoded matrix is approximately square: $m \approx n = 4k$.

Why? If the matrix is too tall ($m \gg n$), the column-sized messages dominate the proof size. If the matrix is too wide ($n \gg m$), the row-sized messages dominate. When $m \approx n$, these two contributions are balanced, minimizing total proof size.

However, the optimal balance is not exactly square in practice. Since the prover typically sends 3 row-sized messages (from the linear and quadratic tests) but $t$ column-sized messages (where $t$ is the number of sampled columns), and $t$ may be larger than 3, the optimal matrix may favor being slightly wider than it is tall.

This analysis motivates the rule of thumb: choose packing $\ell$ such that after padding to $k$ (the next power of 2), we have $m \approx 4k$. For a circuit of size $m \cdot \ell$, this gives approximately $\ell \approx \sqrt{\text{circuit size} / 4}$, rounded to a convenient value. The actual optimal packing depends on circuit structure and protocol parameters and should be determined through experimentation.