Comparing Ligerito and WHIR

Ligerito is a freshly released multilinear polynomial commitment scheme that combines ideas from Ligero with the Sumcheck protocol. It is based on error-correcting codes and is proven secure in the pure random oracle model (pure ROM)¹.

These properties are very similar to those of WHIR: error-correcting codes, pure ROM, partial Sumcheck rounds. Naturally one might ask: how does Ligerito compare to WHIR?

I’ll give a few points of similarity, explaining why many people have suggested that these protocols are closely tied; then discuss the main differences and what we can learn from them. Along the way, I show that some known ideas like code-switching have implicitly made their way into Ligerito.

This article assumes some familiarity with Reed-Solomon codes and proximity tests such as FRI, BaseFold, STIR or WHIR.

Similarities

Recursively fixing variables. The first similarity between Ligerito and WHIR is that they both follow a recursive structure. At the $i$-th iteration, both protocols reduce a problem in $m_i$ variables, to a problem in $m_i - k_i$ variables. The protocol then continues for $m_{i+1} := m_i-k_i$.

WHIR sets $k_i := 4$ for all iterations in their benchmarks. Ligerito however ran a grid search to find optimal values for the $k_i$ parameters and number of iterations. For example, for a polynomial in $28$ variables, the parameters are set to: $$ k_1 :=6, \quad k_2:=3, \quad k_3 := 3, \quad k_4 := 3, \quad k_5 := 3. $$ These iterations will reduce the problem to a $10$-variate multilinear polynomial, which gets sent in full to the verifier.

Sumcheck constraints. The second similarity is that both protocols keep track of a running Sumcheck instance. In an iteration of WHIR or Ligerito, the verifier needs to assert that a random linear combination of vectors has been performed correctly. Rather than checking the whole vectors, the verifier performs spot checks: it opens random positions and checks the sum is locally satisfied. Since the constraints associated with these spot checks verify a summation, both protocols naturally batch this constraint into the running Sumcheck instance.

The running Sumcheck instance is also a point of difference for these protocols as discussed in the next section.

Differences

The main difference between WHIR and Ligerito is the codes that they work with. While WHIR is only defined for Reed-Solomon codes, Ligerito is defined for any sequence of linear codes that work over the same field. This difference is then expressed in how the running Sumcheck instance is used and in the verifier complexity as we will see below.

WHIR: foldable codes and rate improvement. WHIR is defined for Reed-Solomon codes and makes extensive use of their properties. Firstly, WHIR uses the fact that RS codes are “foldable”. These are codes for which:

• (i) a codeword can be broken into constituent parts such that each part is a codeword of a smaller RS code, and
• (ii) taking a random linear combination of words preserves their distance to the relevant RS code.

The existence of this split-and-fold operation enables the recursive reduction in problem size.

Secondly, WHIR uses a variant of the rate-improving technique introduced in STIR. Although a WHIR iteration reduces a problem in $m_i$ variables to a problem in $m_i - k_i$ variables, the prover artificially blows up the size of the RS code’s evaluation domain. This results in a smaller rate, allowing the verifier to make fewer queries as the protocol progresses. To ensure that this operation was performed correctly, the verifier requests an out-of-domain sample, effectively binding the prover to a unique polynomial no matter which domain it is evaluated on (or in the language of RS codes, a unique message). Finally, the validity of the out-of-domain sample is enforced by batching a new constraint into the running Sumcheck.

Ligerito: interleaved codes and code switching. In comparison, Ligerito allows to use unrelated codes between different iterations and does not require them to be foldable.

Rather than using foldable codes, Ligerito works with interleaved codes. A codeword $u$ in an interleaved code $\mathcal{C}^\ell$ is, by definition, a collection of $\ell$ codewords $u_1, \dots, u_\ell$ in a smaller code $\mathcal{C}$. This results in a similar effect to property (i): $u$ can be broken into constituent parts. The individual parts $u_1, \dots, u_\ell$ can also be combined into a single codeword $u_\mathsf{comb}$ in $\mathcal{C}$ by taking a random linear combination. Just like the folding operator, this operation is distance-preserving (property (ii)).

The Ligerito verifier uses the running Sumcheck instance to enforce the fact that $u_\mathsf{comb}$ is indeed the valid encoding of a linear combination of the unique messages corresponding to $u_1, \dots, u_\ell$ (see the Ligerito verifier algorithm point 4.1, second bullet point). Here, uniqueness is guaranteed by running many queries rather than relying on out-of-domain samples as in WHIR.

This method of changing codes between iterations and enforcing consistency within the protocol itself is known as code-switching. While not mentioned in the paper, I find it a lot easier to think of Ligerito in that sense.

Comparison

Summary. WHIR and Ligerito rely on the same core elements. Both verify properties of multilinear polynomials by recursively reducing the size of the problem (i.e., the number of free variables). During these reductions, the prover and verifier keep track of a running Sumcheck instance that enforces additional constraints on the prover’s IOP messages.

Codes. In both cases, the constraints allow some form of code-switching: in WHIR, we switch from one RS code to a different RS defined on a smaller domain and with a smaller rate; in Ligerito, we switch between arbitrary linear codes. In this sense, we can view WHIR and Ligerito (and BaseFold fold those familiar) as protocols from the same family, where WHIR uses RS codes — and associated tricks — while Ligerito is almost completely generalized.

Verifier. The fact that the codes used in WHIR are closely related to each other allow for a cheaper code-switching operation and a succinct verifier. Ligerito’s code-switching requires the verifier to evaluate a few rows of every code’s generator matrix. For an initial polynomial of size $2^m$ (an $m$-variate multilinear) and first folding parameter $k_1$ (meaning we split the initial polynomial into $2^{k_1}$ constituents), the Ligerito verifier evaluates a polynomial of size $2^{m-k_1}$ without assistance from the prover. For a constant $k_1$, this operation is asymptotically linear in the size of the initial polynomial. This difference explains why the Ligerito verifier is slower and is not succinct in the strict sense of the term.

Prover. On the other hand, using arbitrary codes means that Ligerito is compatible with linear-time encodable codes and therefore can be implemented with a linear-time prover.

Proof size. Both papers show similar numbers for proof sizes within their proven security parameter regimes when using RS codes. However, WHIR uses the rate improving technique that Ligerito doesn’t, and Ligerito uses more optimized folding parameters than WHIR. I suspect that with equally optimized folding parameters, WHIR should yield smaller proofs.

Bonus: comparison with Blaze

Since we have mentioned code-switching, I think it is also interesting to compare Ligerito, WHIR and Blaze. Blaze starts with one iteration of something like Ligerito: uses a large folding factor and an arbitrary code. The protocol then code-switches to RS codes and proceeds using BaseFold (or optionally WHIR). In some way, we can see Blaze as a hybrid protocol on the WHIR-Ligerito spectrum, with the potential to hit a sweet-spot on the prover-verifer tradeoff curve.

Importantly, Blaze incorporates a succinct IOP for code-switching in order to avoid the linear(ish) verifier asymptotics we see in Ligerito. This is possible because Blaze is described for a concrete code, rather than the full generality of Ligerito.

Acknowledgements

I would like to thank Andrija Novakovic, Guillermo Angeris and Ron Rothblum for many enlightening conversations on the topic.