Ligero Polynomial Commitment Scheme

References: GLS+21, page 46, AER24.

Prerequisites

• Committed input layers

As described within the committed input layers section, the Ligero polynomial commitment scheme (PCS) consists of a $\text{Commit}$ and an $\text{Eval}$ phase such that

• During $\text{Commit}$, the prover sends a commitment $com$ for the input layer MLE ${\tilde{V}}_d$.
• After running the rest of the GKR claim reduction process, we are left with a claim ${\tilde{V}}_d(r_1,...,r_n)\stackrel{?}{=}{c}_d$.
• During $\text{Eval}$, the prover sends an evaluation proof $\pi$ showing that ${\tilde{V}}_d(r_1,...,r_n)=c_d$.

Short Introduction to Reed-Solomon Codes

We provide a brief introduction to Reed-Solomon codes, as these are prominently featured within the Ligero construction. First, we describe a few properties of general linear codes which will be useful:

• An $[n,k,l{]}_p$-linear code $\mathcal{C}$ is a subspace $\mathcal{C}\subseteq {\mathbb{F}}^n$ of dimension $k$ (i.e. $\mathcal{C}$ is spanned by $k$ linearly independent basis vectors of length $n$ each) where $u\in \mathcal{C}$ implies that $|u{|}_0\ge l$ for all nonzero codewords $u$.
• We define the Hamming weight $|u{|}_0$ is the number of nonzero entries in $u$.
• For all distinct $u\ne v\in \mathcal{C}$ we have that $|u-v{|}_0\ge l$, since the difference of two codewords is itself a codeword.
• The encoding step of a linear code can be described by a matrix-vector multiplication $Gx$, where $x\in {\mathbb{F}}^k$ is the unencoded message and $G\in {\mathbb{F}}^{n\times k}$ is the code's generator matrix. For simplicity we will just use $\text{Enc}$ as the encode function notation.
• We call $\rho =\frac{k}{n}$ the rate of the code, as it describes (the inverse of) how much redundancy the code has. ${\rho }^{-1}=\frac{n}{k}$ is then the "expansion factor", or how much larger the codeword is than the original message.

Next, consider the set of (univariate) polynomials ${\mathbb{F}}^{<d}[X]$ of degree $<d$ and a domain $\mathcal{L}\subseteq \mathbb{F}$. Let $f\in {\mathbb{F}}^d$.

• Let $\bar{f}$ be the restriction of $f$ to $\mathcal{L}\mapsto \mathbb{F}$. Note that $\bar{f}$ can be treated as just a vector of length $|\mathcal{L}|$ by taking its evaluations $\{f(x_1),f(x_2),...,f(x_n)\mid x_i\in \mathcal{L}\}$.
• We define a Reed-Solomon code $\text{RS}[\mathbb{F},\mathcal{L},d]=\{\bar{f}:\mathcal{L}\mapsto \mathbb{F}\mid f\in {\mathbb{F}}^{<d}[X]\}$, i.e. all the restrictions of $f$ to evaluations over $\mathcal{L}$ for degree $<d$ functions $f$.
• If we let $d<|\mathcal{L}|$ and call the evaluation domain size $n$, then an RS code is just an $[n,d,l=(n-d+1){]}_p$ linear code (codewords are the evaluations of $f$ over $\mathcal{L}$, and the un-encoded messages are just polynomials of degree $<d$, which can be specified with $d$ coefficients).
• Note that two polynomials of degree $\le d-1$ agree on at most $d-1$ points, and thus the Hamming distance between codewords is $n-(d-1)=n-d+1$.

The last property of Reed-Solomon codes is extremely useful for the purposes of code-based PCSs such as Ligero and FRI -- if we have that $n=2d$, for example, then for two polynomials $f,g\in {\mathbb{F}}^{<d}[X]$ where $f\ne g$ we have that $|\text{Enc}(f)-\text{Enc}(g){|}_0\ge d+1$, which is over half of the evaluation domain. This intuitively makes it very easy for a verifier to catch a prover who commits to one polynomial's codeword and attempts to evaluate using another's, since sampling even a single random point within $\mathcal{L}$ will reveal the difference with probability $>\frac{1}{2}$.

Vector-Matrix-Vector Product Observation

(Reader's note: the construction described here is identical to that in the Hyrax PCS section.) Let our input layer MLE ${\tilde{V}}_d(X_1,...,X_n)$ have evaluations $a_1,...,a_{2^n}$ over $X_1,...,X_n\in \{0,1{\}}^n$ (for example, $a_1={\tilde{V}}_d(0,...,0)$).

As described in the introduction above, the prover is trying to show that ${\tilde{V}}_d(r_1,...,r_n)=c_d$. As described in the Hyrax PCS section, one way to compute the evaluation is as follows:

$$\left[\begin{array}{cccc}{a}_1& a_2& \dots & a_{2^n}\end{array}\right]\cdot \left[\begin{array}{c}(1-r_1)\cdot (1-r_2)\cdot ...\cdot (1-r_n)\\ (1-r_1)\cdot (1-r_2)\cdot ...\cdot r_n\\ ⋮\\ r_1\cdot r_2\cdot ...\cdot r_n\end{array}\right]$$

The column vector on the right can be viewed as the tensor product ${\otimes }_{i=1}^n(1-r_i,r_i)$ and we will use this shorthand going forward. Just this observation, however, is not enough to motivate our description of Ligero PCS. Instead, we consider an alternative formulation for the evaluation ${\tilde{V}}_d(r_1,...,r_n)$.

Rather than simply linearly arranging the coefficients of ${\tilde{V}}_d$ as above, we can instead arrange them in a square matrix (for now, assume that $n$ is even) of size $2^{n/2}\times 2^{n/2}$ by enumerating the coefficients in row-major order:

$$M=\left[\begin{array}{cccc}{a}_1& a_2& \dots & a_{2^{n/2}}\\ a_{2^{n/2}+1}& a_{2^{n/2}+2}& \dots & a_{2^{n/2+1}}\\ ⋮& ⋮& \ddots & ⋮\\ a_{2^n-2^{n/2}}& a_{2^n-2^{n/2}+1}& \dots & a_{2^n}\end{array}\right]$$

Given the matrix formulation of ${\tilde{V}}_d$ above, we can write the evaluation of ${\tilde{V}}_d(r_1,\dots ,r_n)$ as the following vector-matrix-vector product:

$$[{\otimes }_{i=n/2+1}^n(1-r_i,r_i)]\cdot \left[\begin{array}{cccc}{a}_1& a_2& \dots & a_{2^{n/2}}\\ a_{2^{n/2}+1}& a_{2^{n/2}+2}& \dots & a_{2^{n/2+1}}\\ ⋮& ⋮& \ddots & ⋮\\ a_{2^n-2^{n/2}+1}& a_{2^n-2^{n/2}+2}& \dots & a_{2^n}\end{array}\right]\cdot [{\otimes }_{i=1}^{n/2}(1-r_i,r_i){]}^{\top }$$

We denote the left vector as $L\in {\mathbb{F}}^{2^{n/2}}$ and the right vector as $R\in {\mathbb{F}}^{2^{n/2}}$. This allows us to create the following PCS:

Commitment Phase

The commitment phase of Ligero works as follows:

Let $M_i$ be the $i$'th row of $M$, $1\le i\le 2^{n/2}$. Recall that $M_i\in {\mathbb{F}}^{2^{n/2}}$ since $M$ is a square matrix.

• First, the prover treats the values within $M_i$ as the (monomial basis, i.e. usual) coefficients of a degree-$2^{n/2}-1$ univariate polynomial. They compute ${\tilde{M}}_i=\text{Enc}(M_i)$ using a Reed-Solomon encoding function. Let $\rho$ be the code rate; we then have that $\tilde{M}\in {\mathbb{F}}^{2^{n/2}\times {\rho }^{-1}{2}^{n/2}}$.
• The encoded matrix now looks like the following: $$\tilde{M}=\left[\begin{array}{c}\text{ —— }\text{Enc}(M_1)\text{ —— }\\ \text{ —— }\text{Enc}(M_2)\text{ —— }\\ ⋮\\ \text{ —– }\text{Enc}(M_{2^{n/2}})\text{ —– }\end{array}\right]$$

The prover commits to $\tilde{M}$ as follows:

• Using a cryptographic hash function $H:{\mathbb{F}}^{\ast }\mapsto \mathbb{F}$, the prover first computes a hash over each column:

$${\mathrm{com}}_j=H({\tilde{M}}_{1,j},...,{\tilde{M}}_{{\rho }^{-1}{2}^{n/2},j})$$

• Next, the prover takes the vector of column-wise commitments and computes a Merkle tree using those commitments as the leaves. In other words, the bottom layer of the tree is $[{\mathrm{com}}_1,...,{\mathrm{com}}_{2^{n/2}}]$, with pairs of leaves being hashed, and the root of the tree ${\text{root}}_{\tilde{M}}=\text{Merkleize}([{\mathrm{com}}_1,...,{\mathrm{com}}_{2^{n/2}}])$ is the commitment.
• The (interactive) prover sends $\text{root}$ to the verifier. Note that with this commitment setup, the verifier is able to "open" any column of $\tilde{M}$ and ensure that it is consistent with the commitment ${\text{root}}_{\tilde{M}}$.

Evaluation Phase

The prover wishes to show that $L\cdot M\cdot R=c_d$. It does so by first computing $L\cdot M\in {\mathbb{F}}^{2^{n/2}}$ and sends this to the (interactive) verifier (note that the prover is sending product of $L$ against the unencoded $M$). Since the verifier doesn't (yet) trust this value, we'll denote its view of this prover message as $U\stackrel{?}{=}L\cdot M$.

The verifier asserts that $U\cdot R=c_d$. If the prover is honest and $U=L\cdot M$ then this proves that the evaluation was correct.

The verifier then computes $\tilde{U}=\text{Enc}(U)$, with $\tilde{U}\in {\mathbb{F}}^{{\rho }^{-1}{2}^{n/2}}$. To ensure that the prover computed $U$ correctly, it will check random values in $\tilde{U}$ against $L\cdot \tilde{M}$.

• Note that because $\text{Enc}$ is a linear operation, we have that $\text{Enc}(L\cdot M)=L\cdot \text{Enc}(M)$, where $\text{Enc}(M)$ is the row-wise encoding as described earlier (check this for yourself -- use the intuition that Reed-Solomon encoding is just polynomial evaluation over a domain)

The verifier picks a set of indices $j\in \mathcal{J}$ and "opens" those columns of $\tilde{M}$. For each $j$, the prover sends over ${\tilde{M}}_{\cdot ,j}$, as well as a Merkle path for ${\mathrm{com}}_j$ against ${\text{root}}_{\tilde{M}}$.

The verifier checks that $H({\tilde{M}}_{\cdot ,j})={\mathrm{com}}_j$, and verifies the Merkle path from ${\mathrm{com}}_j$ to the ${\text{root}}_{\tilde{M}}$ it received during the commit phase.

The verifier is now convinced that the columns which the prover sent over are columns of the $\tilde{M}$ which was committed to during the commitment phase.

Finally, the verifier checks that $L\cdot {\tilde{M}}_{\cdot ,j}={\tilde{U}}_j$. This last check ensures that the prover sent $\tilde{U}$ honestly -- if they attempted to cheat by sending $L\cdot M^{\prime }$ for some $M^{\prime }\ne M$, we have that each row of $\text{Enc}(M)$ would differ from each row of $\text{Enc}(M^{\prime })$ in at least $(1-\rho )$ proportion of coordinates (as mentioned earlier, we generally have $\rho \le \frac{1}{2}$), and therefore WHP (using a result from AER24), that $\tilde{U}$ (the honest $L\cdot \text{Enc}(M)$) differs from $\widetilde{U^{\prime }}$ (the dishonest $L\cdot \text{Enc}(M^{\prime })$) in at least $(1-\rho )$ proportion of coordinates as well.

With $|\mathcal{J}|$ queries, the verifier catches a cheating prover at least

$$1-{\rho }^{|\mathcal{J}|}$$

proportion of the time. We set $|\mathcal{J}|$ such that the above probability is at least $1-2^{-\lambda }$, where $\lambda$ is our security parameter.

Costs

Assume that the prover is committing to a multilinear polynomial in $n$ variables. Let our code rate be ${\rho }^{-1}$, and assume that a Reed-Solomon encoding for a message with $2^{n/2}$ coefficients to a codeword with $|\mathcal{L}|={\rho }^{-1}{2}^{n/2}$ evaluations can be computed in time $O(|\mathcal{L}|{\log }_2|\mathcal{L}|)$. Let $\mathcal{J}$ be the set of columns we query during the evaluation phase.

Prover Cost

• During the commitment phase, the prover first computes the encoded matrix of coefficients $\tilde{M}$ by encoding each row of $M$. There are $2^{n/2}$ rows and each row's encoding takes $O(|\mathcal{L}|{\log }_2|\mathcal{L}|)$ time for a total runtime of $O(2^{n/2}|\mathcal{L}|{\log }_2|\mathcal{L}|)$.
• Next, the prover computes hashes of the columns of $\tilde{M}$, and then constructs a Merkle tree comprised of those for the final commitment. This costs $O({\rho }^{-1}{2}^n+{\rho }^{-1}{2}^{n/2})$ hashes.
• During the evaluation phase, the prover first computes $L\cdot M$ and sends the result to the verifier. This takes $O(2^n)$ operations.
• Next, the prover sends over $|\mathcal{J}|$ columns plus associated Merkle proofs to the verifier. The prover doesn't need to compute anything here, so this is free for the prover.
• Assuming the cost of a single hash is $O(h)$, the total prover computation is $$O(2^{n/2}|\mathcal{L}|{\log }_2|\mathcal{L}|+h({\rho }^{-1}{2}^n)+2^n)$$

Proof Size

• The commitment is a single Merkle root, and is thus just one field element.
• The evaluation proof consists of the following for each column $j\in \mathcal{J}$:
  • A column of $\tilde{M}$ with $2^{n/2}$ field elements
  • A Merkle path with ${\log }_2|\mathcal{L}|$ field elements
• Thus the total proof size is $1+|\mathcal{J}|\cdot [2^{n/2}+{\log }_2|\mathcal{L}|]$ field elements.

Verifier Cost

• During the commitment phase, the verifier receives a single Merkle root element and does nothing else.
• During the evaluation phase, the verifier first receives the prover's claimed $U\stackrel{?}{=}L\cdot M$ and computes $\tilde{U}=\text{Enc}(U)$. The encoding step takes $O(|\mathcal{L}|{\log }_2|\mathcal{L}|)$ field operations.
• Next, the verifier computes $U\cdot R$ and checks this against the claimed evaluation value. This requires $O(2^{n/2})$ field operations.
• Next, the verifier receives $|\mathcal{J}|$ columns of $\tilde{M}$ from the prover. For each column, the verifier must
  • Compute a hash over $2^{n/2}$ elements to get the column hash value.
  • Check the Merkle proof over a path of length ${\log }_2|\mathcal{L}|$ against the root received in the commit phase.
• The verifier's runtime for the check phase is $O(|\mathcal{J}|\cdot [2^{n/2}+{\log }_2|\mathcal{L}|])$ hashes.
• The verifier's total runtime is $$O(|\mathcal{L}|{\log }_2|\mathcal{L}|+2^{n/2}+h\cdot |\mathcal{J}|\cdot [2^{n/2}+{\log }_2|\mathcal{L}|])$$