Origami – A Folding Scheme for Halo2 Lookups

Yan X Zhang and Aard Vark

(with thanks to Yi Sun, Jonathan Wang, Lev Soukhanov, Nicolas Mohnblatt)

Halo2 introduced a ZK lookup scheme, building on the ideas of Plookup. Given two vectors of numbers (actually, elements of some large finite field \(\mathbb{F}\)) \(A = (a_1, \ldots, a_m)\) and \(S = (s_1, \ldots, s_n)\), a lookup argument is an argument that

\(A\) does not have to contain every element of \(S\). Also, \(A\) can contain duplicates (as can \(S\)). But every element of \(A\) has to appear somewhere in \(S\).

Nova introduced the idea of folding: a way to aggregate SNARKs (roughly, by taking random linear combinations of witness vectors) so that a large number of incrimental computations can be verified all at once. Nova described an explicit folding scheme for R1CS systems. Sangria gave a folding scheme for PLONKish arithmetizations, but also suggested (under Future Work – Higher Degree Custom Gates) that the same folding technique could work for any polynomial "custom gates".

The purpose of this note is to describe an explicit folding scheme for a Halo2 lookup argument. This is a special case of a general folding scheme for polynomial custom gates.

The Setup

Generally, we use capital letters as vectors, and the matching lower case letters refer to their coordinates. For example, a vector \(S\) would have its entries labeled \((s_1, \ldots, s_n)\).

Imagine we have \(N\) lookup arguments that we want to combine into one. In other words, we have \(N\) vectors \(A^{(1)}, A^{(2)}, \ldots, A^{(N)}\), and \(N\) vectors \(S^{(1)}, S^{(2)}, \ldots, S^{(N)}\). We know that each entry of \(A^{(1)}\) is equal to some entry of \(S^{(1)}\), each entry of \(A^{(2)}\) is equal to some entry of \(S^{(2)}\), and so forth.

(One common use case is evaluating a function by lookup table. In this case, the vectors \(S^{(1)}, S^{(2)}, \ldots, S^{(N)}\) are all equal to some publicly known \(S\) which encodes the values of the function; the vectors \(A^{(1)}, A^{(2)}, \ldots, A^{(N)}\) encode some claimed evaluations of the function at specific points.)

In any case, we have \(N\) lookup arguments that we want to fold together. The main ideas are as follows.

1. Halo2 tells us how to verify a single lookup, using permutations of \(A^{(i)}\) and \(S^{(i)}\) and a number of polynomial constraints.
   In more detail, for each \(i\), the prover finds a permutation \(A'^{(i)}\) of \(A^{(i)}\) and a permutation \(S'^{(i)}\) of \(S^{(i)}\) such that, for each \(j\), either
   • \(a'^{(i)}_j = a'^{(i)}_{j-1}\), or
   • \(a'^{(i)}_j = s'^{(i)}_j\).
2. For each \(i\), the prover and verifier carry out a grand product protocol to prove that \(A'^{(i)}\) is a permutation of \(A^{(i)}\) and \(S'^{(i)}\) is a permutation of \(S^{(i)}\).

• First, the verifier sends the prover random challenges \(\beta^{(i)}\) and \(\gamma^{(i)}\) (for each \(i\)).
• Based on those random challenges, the prover creates two new vectors \(W^{(i)}\) and \(Z^{(i)}\), the "grand product vectors".

4. In order to verify the lookup, the verifier checks a list of polynomial identities involving the vectors \(A^{(i)}\), \(A'^{(i)}\), \(S^{(i)}\), \(S'^{(i)}\), \(W^{(i)}\), and \(Z^{(i)}\), and the random challenge scalars \(\beta^{(i)}\) and \(\gamma^{(i)}\).
5. To fold lookups together, we take a random linear combination of all the associated vectors \(A^{(i)}, A'^{(i)}, S^{(i)}, S'^{(i)}, W^{(i)}, Z^{(i)}\), as well as the challenges \(\beta^{(i)}\) and \(\gamma^{(i)}\).
6. To verify the folded lookup requires a bit of algebra with the polynomial constraints, since nonlinear polynomials do not play well with taking linear combinations.

The Procedure

Relaxed AIRs

To start, we introduce the main object, a relaxed AIR, in the style of Sangria. The main idea of a relaxed AIR, like the relaxed R1CS analogue from Nova, is a polynomial constraint that involves a "slack term." While we can do this for general custom gates following the outline of Sangria, for this presentation we will specialize to lookups.

In the Halo2 setup, the prover \(\mathcal{P}\) starts with \((A, S)\) and ends up with vectors \((A, S, A', S', Z, W)\), using 2 scalars \(\beta\) and \(\gamma\) supplied by the verifier \(\mathcal{V}\) (or Fiat-Shamir) to construct the grand products \(Z\) and \(W\). The prover \(\mathcal{P}\) then needs to prove that the following 7 equations hold:

1. \((1 - Q^{blind} - Q^{last}) \cdot \left ( Z[-1] (A' + \beta) - Z (A + \beta) \right ) = 0\)
2. \((1 - Q^{blind} - Q^{last}) \cdot \left ( W[-1] (S' + \gamma) - W (S + \gamma) \right ) = 0\)
3. \(Q^{last} \cdot (Z^2 - Z) = 0\)
4. \(Q^{last} \cdot (W^2 - W) = 0\)
5. \((1 - Q^{blind} - Q^{last}) (A' - S') (A' - A'[1]) = 0\)
6. \(Q^0 \cdot (A' - S') = 0\)
7. \(Q^0 \cdot (Z - 1) = 0\)
8. \(Q^0 \cdot (W - 1) = 0\).

Call these equations \(f_1 = 0\) through \(f_7 = 0\) respectively. In these equations, the \(Q^*\) vectors are constant and public. Just like in Halo2, they are used to implement zero knowledge.

• Let \(t=2\). (In general, \(t\) is the maximum number of distinct "shifts" that occur in any of the polynomial constraints. Since we have \(Z\) and \(Z[-1]\) in the same constraint – meaning the polynomial \(f_{i, j}\) involves both \(Z_j\) and \(Z_{j-1}\) – we take \(t=2\) for this protocol.)
• To implement zero knowledge, only the first \(n-t\) rows of the vectors \(A, S, \ldots\) will participate in the lookup. The last \(t\) rows will be chosen by the prover \(\mathcal{P}\) at random.
• \(Q^0\): \(q^0_0 = 1\) and \(q^0_i = 1\) for all \(i \neq 0\). (In the Halo2 writeup, this \(Q^0\) is denoted \(\ell_0\) and called a Lagrange basis polynomial – which of course is what \(Q^0\) becomes when you encode a column as a polynomial.)
• \(Q^{blind}\): \(q^{blind}_i = 0\) for \(n-t \leq i \leq n-1\), and \(1\) otherwise (i.e. \(Q^{blind}\) selects the last \(t\) rows).
• \(Q^{last}\): \(q^{last}_i = 1\) for \(i = n-t-1\), and \(0\) otherwise (i.e. \(Q^{last}\) selects the \((n-t-1)\)-st row, the last row before the "blind" rows).

This notation is very compressed. A couple of points:

1. Each polynomial equation \(f_i = 0\) corresponds to \(n\) polynomial equations of the same form
   \[f_{i, j} (a_1, \ldots, a_n, a'_1, \ldots, a'_n, \ldots, w_1, \ldots, w_n, \beta, \gamma) = 0,\]
   where each capital letter \(X \in \{A, A', S, S', Z, W\}\) corresponds to substituting \(x_j\) for \(f_{i, j}\), \(x_j\) being the \(j\)-th coordinate for the vector \(X\). The coordinates of the \(Q^*\) vectors, the \(q^*_i\)'s, do not appear as arguments since they are constants.
2. We use \(Z[\pm 1]\) to mean that when we unpack equation \(f_{i, j}\), instead of substituting \(z_{j}\), we substitute \(z_{j \pm 1}\).
3. For each vector \(X \in \{A, A', S, S', Z, W\}\), each \(f_{i, j}\) will only depend on entries \(X_j\), and possibly \(X_{j-1}\).

In any single \(f_{i, j}\), most of the arguments would not be used. Examples:

1. Consider the third equation \(f_3 = Z^2 - Z = 0.\) This is shorthand for \(n\) constraints of the form \(f_{3, i}(\cdots) = z_i^2 - z_i = 0\) for each \(i\), where \(z_i\) is the \(i\)-th coordinate of \(Z\).
2. In the first equation, \(f_1\) would correspond to \(n\) constraints \(f_{1, j}\), where
   \[f_{i, j} (\cdots) = (1 - Q^{blind}_j - Q^{last}_j)\left ( z_{j-1} (a'_j + \beta) - z_j (a_j + \beta) \right ) = 0.\]

For lookups, we define the following "relaxed versions" of the equations above:

1. \((1 - Q^{blind} - Q^{last}) \cdot \left ( Z([-1]) (A' + \beta) - Z (A + \beta) \right ) = E_1\)
2. \((1 - Q^{blind} - Q^{last}) \cdot \left ( W([-1]) (S' + \gamma) - W (S + \gamma) \right ) = E_2\)
3. \(Q^{last} \cdot (Z^2 - u Z) = E_3\)
4. \(Q^{last} \cdot (W^2 - u W) = E_4\),
5. \((1 - Q^{blind} - Q^{last}) (A' - S') (A' - A'[1]) = E_5\),
6. \(Q^0 \cdot (A' - S') = 0\)
7. \(Q^0 \cdot (Z - u) = 0\)
8. \(Q^0 \cdot (W - u) = 0\).

We define a relaxed lookup instance to be a tuple \((u, \beta, \gamma, A, S, A', S', Z, W, E)\) satisfying the above 8 equations (where \(E\) is shorthand for the four vectors \(E_1, E_2, E_3, E_4, E_5\)). (In contrast to a "standard" lookup instance, which contains only the data \((\beta, \gamma, A, S, A', S', Z, W)\), a relaxed lookup instance also contains the scaling factor \(u\) and slack vectors \(E_i\).)

Whenever we have two instances \((u^{(1)}, \beta^{(1)}, \gamma^{(1)}, A^{(1)}, S^{(1)}, A'^{(1)}, S'^{(1)}, Z^{(1)}, W^{(1)}, E^{(1)})\) and \((u^{(2)}, \beta^{(2)}, \gamma^{(2)}, A^{(2)}, S^{(2)}, A'^{(2)}, S'^{(2)}, Z^{(2)}, W^{(2)}, E^{(2)})\) to fold together, we also define 5 "cross terms"

\begin{eqnarray} B_{1} & = & (1 - Q^{blind} - Q^{last}) \cdot \\ & & \big( (Z^{(1)}[-1] (A'^{(2)} + \beta^{(2)}) + Z^{(2)}[-1] (A'^{(1)} + \beta^{(1)}) \\ & & - Z^{(1)} (A^{(2)} + \beta^{(2)}) - Z^{(2)} (A^{(1)} + \beta^{(1)}) \big) \\ B_{2} & = & (1 - Q^{blind} - Q^{last}) \cdot \\ & & \big( W^{(1)}[-1] (S'^{(2)} + \beta^{(2)}) + W^{(2)}[-1] (S'^{(1)} + \beta^{(1)}) \\ & & - W^{(1)} (S^{(2)} + \beta^{(2)}) - W^{(2)} (S^{(1)} + \beta^{(1)}) \big) \\ B_{3} & = & Q^{last} \cdot (2 Z^{(1)} Z^{(2)} - u^{(1)} Z^{(2)} - u^{(2)} Z^{(1)} \\ B_{4} & = & Q^{last} \cdot (2 W^{(1)} W^{(2)} - u^{(1)} W^{(2)} - u^{(2)} W^{(1)} \\ B_5 & = & (1 - Q^{blind} - Q^{last}) \cdot \\ & & (2 A'^{(1)} A'{(2)} - S'^{(1)} A'{(2)} - S'^{(2)} A'^{(1)} - A'^{(1)} A'{(2)}[1] - A'^{(2)} A'^{(1)}[1] + \\ & & S'^{(1)} A'^{(2)}[1] + S'^{(2)} A'{(1)}[1]) \end{eqnarray}

corresponding to the first \(5\) relaxed equations. (This is because those equations are quadratic and the remainder are linear; we explain this a bit more below)

We now explain the new notation. First, \(u\) is a "homogenizing" scalar \(u\) considered as an additional input to each \(f_j\), so each relaxed \(f_j\) is actually \(n\) constraints of the form
\[f_{j, i} (a_1, \ldots, a_n, a'_1, \ldots, a'_n, \ldots, w_1, \ldots, w_n, u, \beta, \gamma) = e_{j, i},\]
where:

1. each \(E_j\) is a vector \((e_{j, 1}, \ldots, e_{j, n})\);
2. for \(j \geq 6\), we have \(E_j = (0, \ldots, 0)\).

For example, recall that \(f_3\) used to encode \(n\) constraints of form
\[f_{3, i} = q_i^{last} (z_i^2 - z_i) = 0;\]
the new relaxed \(f_3\) would instead encode \(n\) constraints of the form
\[f_{3, i} = q_i^{last} (z_i^2 - z_iu) = e_{3, i}.\]

It remains to understand the roles of the cross terms \(B_i\) and the slack terms \(E_i\), which is the key insight in Nova / Sangria. The main idea here is that we really want the \(f_i\) equations to satisfy constraints of the form

\[f_i(X_1 + rX_2) = f_i(X_1) + r f_i(X_2),\]
where \(X_1\) and \(X_2\) are shorthand meaning "all the arguments." Concretely, this expression is \(n\) equalities of the form

\begin{align} & f_{i, j}(a_{1,1} + ra_{2, 1}, a_{2, 1} + ra_{2,2}, \ldots, z_{n, 1} + rz_{n, 2}, u_1 + ru_2, \beta_1 + r\beta_2, \gamma_1 + r\gamma_2) \\ = & f_{i, j}(a_{1,1}, a_{2, 1}, \ldots, z_{n, 1}, u_1, \beta_1, \gamma_1) + rf_{i, j}(a_{2, 1}, a_{2,2}, \ldots, z_{n, 2}, u_2, \beta_2, \gamma_2), \end{align}

where the two arguments \(X_1\) and \(X_2\) encode \((A_1, S_1, \ldots)\) and \((A_2, S_2, \ldots)\) where, for example, \(A_1 = (a_{1, 1}, \ldots, a_{n, 1})\) and \(A_2 = (a_{1, 2}, \ldots, a_{n, 2})\).

It turns out that the last \(3\) polynomials \(f_5\) through \(f_7\) already satisfy this relationship, because they are linear. Because \(f_1\) through \(f_4\) are not linear, this relationship does not hold. However, we can introduce the cross terms \(B_i\) to get:

\[ f_i(X_1 + rX_2) = f_i(X_1) + r^2 f_i(X_2) + r B_{i}(X_1, X_2).\]

Each \(B_i\) corresponds to \(n\) equations, and take all the inputs from both \(X_1\) and \(X_2\). For example, \(B_3\) corresponds to, as \(j\) runs from \(1\) to \(n\),
\[ B_{3, j}(a_{1, 1}, \ldots, z_{n, 1}, a_{1, 2}, \ldots, z_{n, 2}, u_1, u_2, \beta_1, \beta_2, \gamma_1, \gamma_2) = q^{last}_j (2z_{j, 1}z_{j, 2} - u_1 z_{j, 2} - u_2 z_{j, 1}).\]

To see this explicitly with \(f_3 = Z^2 - uZ,\) we compute

\(\begin{align} f_{3}(X_1 + rX_2) & = (Z_1 + rZ_2)^2 - (u_1 + ru_2) (Z_1 + rZ_2) \\ & = (Z_1^2 + 2r Z_1 Z_2 + r^2Z_2^2) - u_1Z_1 - ru_1Z_2 - ru_2Z_1 - r^2 u_2 Z_2 \\ & = (Z_1^2 - u_1Z_1) + r^2(Z_2^2 - u_2Z_2) + r(2Z_1Z_2 - u_1Z_2 - u_2Z_1) \\ & = f_{3}(X_1) + r^2 f_{3}(X_2) + r B_{3}(X_1, X_2), \end{align}\)

as desired. By doing this, the \(B_i\)'s are acting as an "error term" due to \(f_i\) being nonlinear, and the \(E_i\)'s act as an accumulated error due to all the \(B_i\)'s.

Details of the Protocol (Halo2 lookups)

We first define a "one-round protocol" as follows:

The above encodes a single folding step. We now give the entire protocol:

Comparison with Sangria

Scope

Sangria had outlined an approach to custom gates. Our lookup protocol is almost, but not quite, a special case of that procedure, mainly because of the roles of \(\beta\) and \(\gamma\). Instead, what we have here is a special case of "custom gates with verifier randomness," a concept that's a slight generalization of Sangria's approach to custom gates.

For completeness, we make explicit many of the ideas in Sangria's outline in our writeup of the general folding scheme.

Knowledge soundness

This protocol satisfies knowledge soundness: a cheating prover cannot convince the verifier to accept a folded proof unless the prover actually knows \(N\) satisfying witnesses. We give a proof of knowledge soundness in our writeup.

In outline, the proof (very similar to as done in Sangria and Nova) is as follows. The idea is to imagine an extractor that interacts with the prover. The extractor is allowed to rewind the prover to a previous state. In practice, this means the extractor (playing the role of verifier) can send the prover different challenges \(r\), and see how the prover responds. Like in Nova and Sangria, by testing enough different values \(r\) and doing a bit of algebra, the extractor can recover the witnesses \(N\) that were folded together. Once the extractor can recover the \(N\) folded witnesses, since Halo2 lookups themselves are knowledge sound, we know the prover must know \(N\) valid lookup witnesses.

Our proof of knowledge soundness in the general scheme is only a bit more complicated than that of Sangria, partly due to the polynomials of arbitrary degree (although again Sangria had an outline already in Section 3.3) and partly due to the fact that we have "verifier randomness," as stated above. We have to take care that the verifier-provided randomness \(\beta\) and \(\gamma\) does not mess things up.