flookup: Fractional Decomposition-Based Lookups in Quasi-Linear Time Independent of Table Size

Abstract

We present a protocol for checking the values of a committed polynomial \phi(X) \in \mathbb{F}_{\leq m}[X] over a multiplicative subgroup \mathbb{H} \subset \mathbb{F} of size m are contained in a table T \in \mathbb{F}^N. After an O(N \log^2 N) preprocessing step, the prover algorithm runs in quasi-linear time O(m \log^2 m). We improve upon the recent breakthrough results Caulk [ZBK+22] and Caulk+ [PK22], which were the first to achieve the complexity sublinear in the full table size N with prover time being O(m^2 + m \log N) and O(m^2), respectively. We pose further improving this complexity to O(m \log m) as the next important milestone for efficient zk-SNARK lookups.

Keywords: lookup arguments, zk-SNARKs, polynomial commitments, pairings

1. Introduction

The lookup problem is fundamental to the efficiency of modern zk-SNARKs. Somewhat informally, it asks for a protocol to prove the values of a committed polynomial \phi(X) \in \mathbb{F}_{\leq m}[X] are contained in a table T of size N of predefined legal values. When the table T corresponds to an operation without an efficient low-degree arithmetization in \mathbb{F}, such a protocol produces significant savings in proof construction time for programs containing the operation. Building on previous work of [BCG+18], plookup [GW20] was the first to explicitly describe a solution to this problem in the polynomial-IOP context. plookup described a protocol with prover complexity quasilinear in both m and N. This left the intriguing question of whether the dependence on N could be made sublinear after performing a preprocessing step for the table T. Caulk [ZBK+22] answered this question in the affirmative by leveraging bi-linear pairings, achieving a run time of O(m^2 + m \log N). Caulk+ [PK22] improved this to O(m^2) getting rid of the dependence on table size completely.

However, the quadratic dependence on m of these works makes them impractical for a circuit with many lookup gates. We resolve this issue by giving a protocol called flookup that is quasi-linear in m and has no dependence on N after the preprocessing step.

1.1 Usefulness of the Result

When is it worth it to use Flookup instead of plookup? The plookup prover runs in time O(N \log N) and the Flookup prover requires time O(m \log^2 m) with small constants in the O(). Hence, Flookup is worth it roughly when the table is larger than the number of lookups by a logarithmic factor; i.e. when m \ll N / \log N.

The authors note several trade-offs. Verification requires a pairing with a prover-defined \mathbb{G}_2 point (as do Caulk and Caulk+), which makes recursive aggregation of proofs less smooth. Another inconvenience is that Flookup does not have the nice linearity properties of plookup or Caulk, and so reducing a tuple lookup to a single element lookup is less efficient. For “simple” tables like T = 0, \ldots, 2^t - 1 for a range check, one can decompose into limbs and use a much smaller table. A better use case involves complex “SNARK-unfriendly” operations on large ranges, such as those arising inside SHA-256.

1.2 Organization of the Paper

Section 2 covers required preliminaries. Section 3 defines the notion of a bi-linear polynomial IOP which models protocols that use pairings in addition to polynomial commitment schemes. Section 4 reviews a method of [PK22] to extract a commitment to the vanishing polynomial of a subtable using pairings, extended to work with arbitrary sets. Section 5 gives a lookup protocol given a commitment to the vanishing polynomial of the table. Section 6 combines the table extraction and subtable lookup protocols to give the final result.

2. Terminology and Conventions

We assume our field \mathbb{F} is of prime order. We denote by \mathbb{F}_{< d}[X] the set of univariate polynomials over \mathbb{F} of degree smaller than d. All algorithms receive the security parameter \lambda as an implicit parameter.

An “object generator” \mathcal{O} is run with input \lambda before all protocols, and returns all fields and groups used. Specifically, \mathcal{O}(\lambda) = (\mathbb{F}, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, e, g_1, g_2, g_t) where:

• \mathbb{F} is a prime field of super-polynomial size r = \lambda^{\omega(1)}.
• \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t are groups of size r, and e is an efficiently computable non-degenerate pairing e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_t.
• g_1, g_2 are uniformly chosen generators such that e(g_1, g_2) = g_t.

We write \mathbb{G}_1 and \mathbb{G}_2 additively. We use the notations [x]_1 := x \cdot g_1 and [x]_2 := x \cdot g_2. We often denote by [n] the integers \{1, \ldots, n\}. We use the acronym e.w.p for “except with probability”.

Protocols are public-coin interactive protocols between a prover and verifier. The SRS can be derived from an “SRS of monomials” of the form \{[x^i]_1\}_{a \leq i \leq b}, \{[x^i]_2\}_{c \leq i \leq d} for uniform x \in \mathbb{F}. It follows from Bowe et al. [BGM17] that the required SRS can be derived in a universal and updatable setup requiring only one honest participant.

2.1 Analysis in the AGM Model

For security analysis the authors use the Algebraic Group Model of Fuchsbauer, Kiltz and Loss [FKL18]. An algebraic adversary \mathcal{A} in an SRS-based protocol is a \mathsf{poly}(\lambda)-time algorithm which, for i \in \{1, 2\}, whenever it outputs an element A \in \mathbb{G}_i, also outputs a vector v over \mathbb{F} such that A = \langle v, \mathsf{srs}_i \rangle.

Proof. Let \gamma be the difference between the satisfiability of the real and ideal check. An adversary \mathcal{A}^* for the Q-DLOG problem is described that succeeds with probability \gamma, implying \gamma = \mathsf{negl}(\lambda). \mathcal{A}^* receives the challenge, constructs the SRS, runs the protocol with \mathcal{A}, and if the real check passes but the ideal check fails, computes R := (R_1 \cdot T_1)(T_2 \cdot R_2). Since R \in \mathbb{F}_{< 2Q}[X] is a non-zero polynomial with R(x) = 0, \mathcal{A}^* can factor R and find x.

The paper then defines Knowledge Soundness in the Algebraic Group Model: a protocol \mathscr{P} has this property if there exists an efficient extractor E such that the probability of any algebraic adversary winning a game where it chooses input x, plays the prover role, and E outputs \omega with (x, \omega) \notin \mathcal{R} while the verifier accepts, is \mathsf{negl}(\lambda).

2.2 KZG-like Polynomial Commitment Schemes

2.3 Other Notational Conventions

Given a polynomial f \in \mathbb{F}[X] and a subset I \subset \mathbb{F}, we define f|_I to be the set \{f(v)\}_{v \in I}. Given a set T \subset \mathbb{F}, the vanishing polynomial of T is:

3. Bi-linear Polynomial IOPs

While most recent works on zk-SNARKs have leveraged the power of polynomial commitment schemes [KZG10], [ZBK+22] has additionally leveraged the power of pairings to essentially take products of commitments. This enables checking degree two identities between polynomials without needing to compute the polynomials themselves, but only their commitments — which can be much faster when they are a small linear combination of preprocessed polynomials.

3.1 From BLIOPs to Protocols Against Algebraic Adversaries

We wish to “compile” BLIOPs to protocols against algebraic adversaries. Several terms are defined to track compilation efficiency: D_1(\mathscr{P}, \mathsf{x}, \omega) counts the total degree contribution of prover polynomials sent to \mathbb{G}_1; D_2 counts \mathbb{G}_2 scalar multiplications; and E(\mathscr{P}, \mathsf{x}, \omega) is the total number of summands in all bi-linear queries.

Proof sketch. The SRS of \mathscr{P}^* consists of [1]_1, \ldots, [x^{d-1}]_1, [1]_2, \ldots, [x^{d-1}]_2 plus commitments to preprocessed polynomials. When P_{\mathsf{poly}} sends a message (f, i) to \mathcal{I}, the compiled prover sends [f]_i to the verifier. Evaluation queries use the PCS opening protocol, and bi-linear queries become pairing checks \prod_{i \in [k]} e([f_i(x)]_1, [h_i(x)]_2)^{c_i} = 1. Knowledge soundness follows by defining three events A, B, C corresponding to PCS failure, pairing failure, and extraction failure, each shown to have \mathsf{negl}(\lambda) probability.

3.2 Conventions for Describing BLIOPs and PIOPs

Several shorthand conventions are established: (1) A BLIOP without bi-linear checks is called a PIOP; (2) “Checks the identity P(f_1(X), \ldots, f_k(X))” means querying at random \alpha and checking the evaluation; (3) “Checks the identity on \mathbb{H}” means checking divisibility by Z_{\mathbb{H}}(X); (4) Efficiency descriptions implicitly use the compilation lemma; (5) Input polynomials are added to A_1 like preprocessed polynomials.

4. Protocol for Subtable Extraction

The protocol in this section is similar to one implicit in Caulk+ [PK22]. Based on the innovation of Caulk, Caulk+ uses fractional decomposition to efficiently “extract” a vanishing polynomial Z_I of a subset I \subset T from Z_T. In [PK22], the large set T is always a multiplicative subgroup. The main innovation in this section is an algorithm that computes all subtable commitments of size |T| - 1 efficiently, ensuring that when T is an arbitrary set, the preprocessing remains quasilinear rather than quadratic.

Proof. The proof uses a divide-and-conquer approach. The key idea is to express the matrix of subtable polynomial coefficients Z_{T \setminus *} in terms of halves T_1, T_2 of T:

The algorithm proceeds as follows: (1) Compute coefficients of Z_T(X) and its tree of subproducts in O(N \log^2 N) time. (2) Split T into halves and retrieve Z_{T_1}, Z_{T_2}. (3) Compute Toeplitz matrix-vector products in O(N \log N) time. (4) Apply recursively. This yields the recurrence C_1(N) = 2C_1(N/2) + O(N \log N), giving C_1(N) = O(N \log^2 N).

The paper then describes the IsVanishingSubtable protocol.

IsVanishingSubtable_T(g(X))

Preprocessed polynomials: Let P_1 = \{Z_T\}. For each i \in T insert into P_2 the polynomial Z_{T \setminus \{i\}}.

Inputs: g(X) \in \mathbb{F}_{< d}[X]. The prover also has the S \subset T such that g(X) = Z_S(X).

Protocol: P_{\mathsf{poly}} sends (Z_{T \setminus S}, 2) to \mathcal{I}. V_{\mathsf{poly}} makes the bi-linear query g \cdot Z_{T \setminus S} \stackrel{?}{=} Z_T and outputs \mathsf{acc} iff it returns true.

Proof. Correctness and soundness are immediate: the check passes if and only if g divides Z_T, which happens if and only if g = Z_S for some S \subseteq T. For efficiency, the key observation is that

where coefficients c_i = 1 / Z'_S(i) are computed via the derivative Z'_S(X) in O(m \log^2 m) time. Thus [Z_{T \setminus S}(x)]_2 can be computed with m \mathbb{G}_2 scalar multiplications from the preprocessed elements.

5. A PIOP for Lookups When Given the Table in Vanishing Form

The previous section gives a way to extract the vanishing polynomial of the subtable. Rather than converting to evaluation form and using plookup, the authors give a protocol that works directly with the vanishing form of the table. It requires roughly 3m \mathbb{G}_1-scalar multiplications when both witness and table are of size m, compared to plookup’s 5m.

Unnormalized rational Lagrange functions. Fix a set T \subset \mathbb{F}. For v \in \mathbb{F}, define the rational function:

Note that \Gamma_v^T is a polynomial exactly when v \in T.

Proof. The first item is obvious. For the second, write R(X) = R_1(X) + R_2(X) where R_1 sums over polynomial terms (indices outside S) and R_2 sums over potentially non-polynomial terms. If R_2 \in \mathbb{F}[X], then multiplying denominators yields Z_T(X) Q'(X) = R_2(X) Q(X) where Q(X) = \prod_{j \in S} (X - v_j) and Q'(X) = \sum_{j \in S} a_j \prod_{i \in S \setminus \{j\}} (X - v_i). The case R_2 \equiv 0 is ruled out since the leading coefficient of Q' is \sum_{j \in S} a_j \neq 0. For R_2 \not\equiv 0, since no factor of Q divides Z_T, we need Q | Q', but \deg(Q') < \deg(Q), a contradiction.

The above lemma suggests the following protocol. Let \mathbb{H} = \{\mathbf{g}, \mathbf{g}^2, \ldots, \mathbf{g}^m = 1\} \subset \mathbb{F} be a multiplicative subgroup of size m with generator \mathbf{g}. Given \phi(X), define R_{T, \phi}(X) := \sum_{v \in \mathbb{H}} \Gamma_{\phi(v)}^T(X). The protocol commits to R_{T, \phi}(X) and proves correctness, showing it is a polynomial and therefore \phi|_{\mathbb{H}} \subset T.

IsInVanishing_{\mathbb{H}, T}(\phi)

Preprocessed polynomials: P_1 = \{Z_T\}. Input: \phi \in \mathbb{F}_{\leq d}[X].

Protocol: (1) P_{\mathsf{poly}} sends the polynomial g(X) := R_{T, \phi}(X). (2) V_{\mathsf{poly}} chooses random \beta and queries z := g(\beta). (3) P_{\mathsf{poly}} computes and sends Z(X) \in \mathbb{F}_{\leq m}[X] defined by Z(\mathbf{g}^i) = \sum_{j=1}^{i} \Gamma_{\phi(\mathbf{g}^j)}^T(\beta) for each i \in [m]. (4) V_{\mathsf{poly}} queries Z_T(\beta). (5) V_{\mathsf{poly}} checks on \mathbb{H} the identities:

Proof. Assume \phi \notin \mathcal{L}. Let E be the event that g(\beta) = R_{T, \phi}(\beta). When \phi(X) \notin \mathcal{L}, Lemma 5.1 implies R_{T, \phi(X)} \notin \mathbb{F}[X]. As g \in \mathbb{F}_{\leq d}[X], E has probability \mathsf{negl}(\lambda).

The checks in step 5 imply that R_{T, \phi}(\beta) = g(\beta): check (a) establishes the base case Z(\mathbf{g}) = \Gamma_{\phi(\mathbf{g})}^T(\beta); check (b) establishes the inductive step; and check (c) connects Z(\mathbf{g}^m) = z = g(\beta). For prover runtime, the heaviest component is computing R_{T, \phi}’s values on T in time O(m \log^2 m). The key identity is

where a_v counts the multiplicity of v in \phi|_{\mathbb{H}}, c_v = \prod_{v \neq i \in T}(v - i), and \tau_v is the Lagrange basis of T. The constants \{c_v\} are evaluations of Z'_T(X) at T, computable in the required time. The “additionally” part follows by precomputing S_v := [\Gamma_v^T(x)]_1 for all v \in T using Lemma 4.1.

6. Putting It All Together

IsInVanishingTable_{\mathbb{H}, T}(\phi)

Preprocessed polynomials: P_1 = \{Z_T\}. Input: \phi \in \mathbb{F}_{< d}[X].

Protocol: (1) P_{\mathsf{poly}} computes the set I \subseteq T such that I = \phi|_{\mathbb{H}}. (2) P_{\mathsf{poly}} computes and sends Z_I. (3) Run IsVanishingSubtable_T(Z_I). (4) Run IsInVanishing_{\mathbb{H}, Z_I}(\phi).

Proof. The only thing left to address is that the computation of Z_I in the second step can be done in time O(m \log^2 m). This follows from algorithm 10.3 in [vzGG].

Acknowledgements

The first author thanks Aztec Network for support of this work. The authors thank Mary Maller and Arantxa Zapico for helpful discussions. The construction in Section 5 is inspired by a construction of Carla Ràfols and Arantxa Zapico for a similar problem. They also thank Piotr Mikołajczyk and Yuncong Zhang for corrections.

References

1. [BCG+18] J. Bootle, A. Cerulli, J. Groth, S. K. Jakobsen, and M. Maller. “Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution”. In: ASIACRYPT 2018, Part I. Vol. 11272. LNCS. Springer, 2018, pp. 595–626.
2. [BGM17] S. Bowe, A. Gabizon, and I. Miers. “Scalable Multi-Party Computation for zk-SNARK Parameters in the Random Beacon Model”. Cryptology ePrint Archive, Report 2017/1050, 2017. eprint.iacr.org/2017/1050.
3. [Dra] J. Drake. Talk recording. youtu.be/tbnaud5wgxm?t=2251.
4. [FKL18] G. Fuchsbauer, E. Kiltz, and J. Loss. “The Algebraic Group Model and Its Applications”. In: CRYPTO 2018, Part II. 2018, pp. 33–62.
5. [Gro16] J. Groth. “On the Size of Pairing-Based Non-Interactive Arguments”. In: EUROCRYPT 2016, Part II. 2016, pp. 305–326.
6. [GVL13] Gene H. Golub and Charles F. Van Loan. Matrix Computations. JHU Press, 2013.
7. [GW20] A. Gabizon and Z. J. Williamson. “plookup: A Simplified Polynomial Protocol for Lookup Tables”. IACR Cryptol. ePrint Arch., page 315, 2020.
8. [GWC19] A. Gabizon, Z. J. Williamson, and O. Ciobotaru. “PLONK: Permutations over Lagrange-Bases for Oecumenical Noninteractive Arguments of Knowledge”. IACR Cryptology ePrint Archive, 2019:953, 2019.
9. [KZG10] A. Kate, G. M. Zaverucha, and I. Goldberg. “Constant-Size Commitments to Polynomials and Their Applications”. 2010, pp. 177–194.
10. [PK22] J. Posen and A. A. Kattis. “Caulk+: Table-Independent Lookup Arguments”. 2022.
11. [TAB+20] A. Tomescu, I. Abraham, V. Buterin, J. Drake, D. Feist, and D. Khovratovich. “Aggregatable Subvector Commitments for Stateless Cryptocurrencies”. In: SCN 2020. Vol. 12238. LNCS. Springer, 2020, pp. 45–64.
12. [vzGG] J. von zur Gathen and J. Gerhard. “Fast Polynomial Evaluation and Interpolation”. Modern Computer Algebra, chapter 10, pp. 295–310.
13. [ZBK+22] A. Zapico, V. Buterin, D. Khovratovich, M. Maller, A. Nitulescu, and M. Simkin. “Caulk: Lookup Arguments in Sublinear Time”. IACR Cryptol. ePrint Arch., page 621, 2022.