Multivariate lookups based on logarithmic derivatives

Abstract

Logarithmic derivatives translate products of linear factors into sums of their reciprocals, turning zeroes into simple poles of same multiplicity. Based on this simple fact, we construct an interactive oracle proof for lookups over the boolean hypercube, which makes use of a single multiplicity function instead of working with a rearranged union of table and witnesses, as Plookup [GW20] does. For single-column lookups the performance is comparable to Plookup, taken to the multivariate setting by Hyperplonk+ [CBBZ22]. However, the real power of our argument unfolds in the case of “batch-column” lookups, where multiple columns are subject to the same table lookup: While the number of field operations is comparable to the Plookup strategy, the oracles provided by our prover are significantly fewer. For example, given M = 20 columns of length between 2^{12} and 2^{18}, and assuming a commitment scheme over an elliptic curve with a 256 bit large base field, our paper-pencil operation counts indicate that the logarithmic derivative lookup is more than 3.9 times faster.

Keywords: lookup arguments, logarithmic derivatives, sumcheck protocol, multivariate polynomials, zero-knowledge proofs

1. Introduction

Lookup arguments prove a sequence of values being member of an, often prediscribed, table. They are an essential tool for improving the efficiency of arguments for statements which are otherwise quite expensive to arithmetize. Main applications are (1) lookups for relations of high algebraic complexity, and (2) lookups for interval ranges, the latter of which are extensively used by zero-knowledge virtual machines. Although closely related to permutation (or shuffle) arguments [BG12], a first explicit occurence of lookups dates back to the Arya paper [BCG+18], to the best of our knowledge. While their argument handles multiplicities directly in a quite costly manner, Plookup [GW20] greatly improved over [BCG+18] using a rather geometric approach. Since then Plookup (and variants of it) is the general purpose lookup argument used in practical applications.

In this paper we describe a lookup argument which is based on logarithmic derivatives. As in classical calculus, the formal logarithmic derivative turns products \prod_{i=1}^{N} (X - z_i) into sums of their reciprocals,

having poles with the same multiplicity as the zeros of the product. Working with poles instead of zeros is extremely useful for lookup arguments. While the treatment of multiplicities is quite indirect and therefore costly in the product approach [BCG+18, GW20], it turns straight-forward when using logarithmic derivatives: Given a sequence of field elements (a_i)_{i=1}^N and another sequence (t_j)_{j=1}^M, then \{a_i: i=1,\ldots,N\} \subseteq \{t_j: j=1,\ldots,M\} as sets, if and only if there exists a sequence of field elements (m_j)_{j=1}^M (the multiplicities) such that

(This holds under quite mild conditions on the field, see Lemma 5 for details.) Based on this fractional identity we construct a lookup argument which is more efficient than Plookup, which argues via a sorted union of witness and table sequence. This is particularly true in the case of batch-column lookups, where several sequences (“columns”) are subject to the same table lookup, a situation that often arises in zero-knowledge virtual machines, enforcing execution trace elements being valid machine words.

The paper also notes that Bulletproof++ [Eag22] already uses logarithmic derivatives for range proofs, and concurrently, Flookup [GK22] describes an oracle proof for the radical of a witness sequence which is almost identical to the logarithmic derivative approach. Logarithmic derivatives are also directly used in large-table lookups, yielding the currently most efficient argument Cached Quotients [EFG22].

The document focuses on batch-column lookups in the multivariate setting. Section 2 gathers the preliminaries: the Lagrange kernel over the boolean hypercube, the formal logarithmic derivative, and the multivariate sumcheck argument. Section 3 describes the lookup argument based on the logarithmic derivative. Section 4 outlines batch-column lookups using the Plookup strategy for comparison, and Section 5 provides the comparison.

2. Preliminaries

2.1 The Lagrange kernel of the boolean hypercube

Let \mathbb{F} denote a finite field, and \mathbb{F}^* its multiplicative group. Throughout the document we regard the boolean hypercube H = \{\pm 1\}^n as a multiplicative subgroup of (\mathbb{F}^*)^n. The Lagrange kernel of H is the multilinear polynomial

Proof. Since p(\vec{y}) = \sum_{\vec{z} \in H} f(\vec{z}) \cdot L_H(\vec{X}, \vec{z}), it suffices to show the claim for p(\vec{X}) = L_H(\vec{X}, \vec{z}), with \vec{z} \in H. By the property of the Lagrange kernel we have \langle L_H(\cdot, \vec{z}), L_H(\cdot, \vec{y}) \rangle_H = L_H(\vec{y}, \vec{z}), which by symmetry equals L_H(\vec{X}, \vec{y}) at \vec{X} = \vec{z}.

For any \vec{y} \in \mathbb{F}^n, the domain evaluation of L_H(\vec{X}, \vec{y}) over H can be computed in \mathcal{O}(|H|) field operations, by recursively computing partial products. Each recursion step costs |H_{k-1}| field multiplications and the same number of additions, yielding overall cost bounded by |H| \cdot (\mathsf{M} + \mathsf{A}).

2.2 The formal derivate

Given a univariate polynomial p(X) = \sum_{k=0}^{d} c_k \cdot X^k over a general (possibly infinite) field \mathbb{F}, its derivative is defined as

As in calculus, the derivative is linear and satisfies the product rule. For a function \frac{p(X)}{q(X)} from the rational function field \mathbb{F}(X), the derivative is the rational function

Proof. If q(X) is a constant, then the assertion follows from the corresponding statement for polynomials. Assuming \deg q(X) > 0, polynomial division gives \frac{p(X)}{q(X)} = m(X) + \frac{r(X)}{q(X)}. By linearity we obtain

Comparing degrees, we conclude m'(X) = 0, and since \deg m(X) < p we have m(X) = c for some constant. If r(X) \neq 0 the leading term of the left hand side would not vanish, so r(X) = 0.

2.3 The logarithmic derivative

The logarithmic derivative of a polynomial p(X) over a (general) field \mathbb{F} is the rational function \frac{p'(X)}{p(X)}. The logarithmic derivative of a product p_1(X) \cdot p_2(X) equals the sum of their logarithmic derivatives, since by the product rule

In particular the logarithmic derivative of a product p(X) = \prod_{i=1}^{n} (X + z_i) is equal to the sum

Proof. If p_a(X) = \prod_{i=1}^n (X + a_i) and p_b(X) = \prod_{i=1}^n (X + b_i) coincide, so do their logarithmic derivatives. For the converse, assume \frac{p_a'(X)}{p_a(X)} = \frac{p_b'(X)}{p_b(X)}. Then \left(\frac{p_a(X)}{p_b(X)}\right)' = 0. By Lemma 2, \frac{p_a(X)}{p_b(X)} = c for some constant. Since both polynomials are monic, c = 1.

Remark 1. Lemma 3 also applies when \mathbb{F} is the function field \mathbb{F}_p(Y_1, \ldots, Y_k) over a finite field \mathbb{F}_p. This observation is useful when generalizing the permutation argument to the case where a_i and b_i are multilinear polynomials.

Proof. Suppose the fractional decompositions are equal. Then \sum_{z \in \mathbb{F}} \frac{m_1(z) - m_2(z)}{X - z} = 0, and therefore

In particular, p(z) = (m_1(z) - m_2(z)) \cdot \prod_{w \in \mathbb{F} \setminus \{z\}} (z - w) = 0 for every z \in \mathbb{F}. Since \prod_{w \in \mathbb{F} \setminus \{z\}} (z - w) \neq 0, we must have m_1(z) = m_2(z).

Proof. Suppose \{a_i\} \subseteq \{b_i\}. Set the (m_i) as the normalized multiplicities m_i = \frac{m_a(b_i)}{m_b(b_i)}. This choice obviously satisfies the identity. Conversely, if the identity holds, collecting fractions with the same denominator and applying Lemma 4 shows that each z \in \{a_i\} must occur in \{b_i\}.

2.4 Lagrange interactive oracle proofs

A Lagrange interactive oracle proof (Lagrange IOP) over the boolean hypercube H = \{\pm 1\}^n is an interactive protocol between a prover and a verifier. In each round, the verifier sends a message (typically a random challenge) and the prover computes one or several functions over the boolean hypercube, and gives the verifier oracle access to them. The verifier is allowed to query the oracles for their inner products with the Lagrange kernel L_H(\cdot, \vec{y}) associated with an arbitrary vector \vec{y} \in \mathbb{F}^n.

Lagrange IOPs are turned into arguments by instantiating the Lagrange oracles by a Lagrange commitment scheme. This includes inner product arguments [BCC+16] and the multilinear variant [PST13] of the [KZG10] commitment scheme.

2.5 The sumcheck protocol

Given a multivariate polynomial p(X_1, \ldots, X_n) \in \mathbb{F}[X_1, \ldots, X_n], a prover wants to convince a verifier that

This is done by a random folding procedure which stepwise reduces a claim on the sum over H^i = \{\pm 1\}^{n-i} to one over a hypercube of half the size. Eventually, one ends up with a claim over a single-point sum, which is the value of p at a random point (r_1, \ldots, r_n) \in \mathbb{F}^n.

The sumcheck protocol is easily extended to a batch of polynomials p_i(X_1, \ldots, X_n) by sampling a random linear combination. The soundness error increases only slightly.

Computational cost. For the case that p(\vec{X}) = Q(w_1(\vec{X}), \ldots, w_\nu(\vec{X})) with each w_i multilinear and Q having absolute degree d, the overall prover cost is bounded by the simplified formula

3. Lookups based on the logarithmic derivative

Assume that \mathbb{F} is a finite field, and that f_1, \ldots, f_M and t: H \to \mathbb{F} are functions over the Boolean hypercube H = \{\pm 1\}^n. By Lemma 5, it holds that \bigcup_{i=1}^M \{f_i(\vec{x})\}_{\vec{x} \in H} \subseteq \{t(\vec{x})\}_{\vec{x} \in H} as sets, if and only if there exists a function m: H \to \mathbb{F} such that

assuming the characteristic of \mathbb{F} is larger than M times the size of the hypercube. If t is injective, then m is the multiplicity function, counting the number of occurrences for each value. Otherwise, the normalized multiplicity function is defined as

Given a random challenge x \leftarrow \mathbb{F} from the verifier, the prover shows the rational identity holds at X = x. To apply the sumcheck protocol, the fractional expression must be turned into a polynomial one. The prover splits the sum into partial sums of roughly the same number of terms \ell, and provides multilinear helper functions for each sum, subject to domain identities of algebraic degree essentially equal to the number of reciprocal terms.

3.1 The protocol

Let \ell be the chosen sum size, [0, M] = \bigcup_{k=1}^{K} I_k the decomposition into K = \lceil \frac{M+1}{\ell} \rceil subintervals. Let

be the respective partial sums, where m_0(\vec{x}) = m(\vec{x}), \varphi_0(\vec{x}) = x + t(\vec{x}), m_i(\vec{x}) = -1, and \varphi_i(\vec{x}) = x + f_i(\vec{x}) for i = 1, \ldots, M.

Remark 3. The condition x \notin \{-t(\vec{x})\} is imposed for completeness. Omitting it gives an overwhelmingly complete protocol with completeness error at most \frac{|H|}{|\mathbb{F}|}. Alternatively, one may modify the domain identity to multiply by an extra \varphi_0 factor.

3.2 Soundness

The soundness analysis is a straight-forward application of the Schwartz-Zippel lemma and the Lagrange-query to point-query correspondence stated by Lemma 1. The rational identity is turned into a polynomial identity of degree at most |H| \cdot (M+1) - 1 by multiplying with the common denominator.

3.3 Computational cost and optimal sum size

The polynomial Q from Protocol 2 has \nu = M + K + 3 variables and absolute degree d = \ell + 2. The paper describes a domain evaluation strategy using batch inversion. Assuming inverses of \varphi_i are given (except for one distinct element in each group), the domain identity terms in Q can be evaluated via fractional representations, yielding evaluation costs of K \cdot (\ell + 2) \cdot \mathsf{M} + K \cdot (\ell + 1) \cdot \mathsf{A}.

The total costs of the oracle prover are:

• Arithmetic costs of
  |H| \cdot (K+5+(\ell+3) \cdot (4 \cdot M + 3 + \ell \cdot K)) \cdot \mathsf{M},
  neglecting field additions and subtractions.
• Oracle costs of
  K + 1 = \left\lceil \frac{M+1}{\ell} \right\rceil + 1
  oracles of size |H|.

The optimal choice of \ell. If \ell = 1, each reciprocal gets a helper function, resulting in M+1 additional commitments but a very low degree d = 3. Increasing \ell reduces commitments but increases degree. The most extreme case \ell = M+1 gives a single additional commitment with degree d = M+3. The optimal choice depends on the polynomial commitment scheme. The paper provides benchmark-based estimates using elliptic curve commitments in the Pallas curve.

3.4 Vector-valued lookups

Protocol 2 generalizes to functions with multilinear values,

without changing the soundness error bound from Theorem 4. Since \mathbb{F}[X, Y_1, \ldots, Y_k] is a unique factorization domain and the polynomials of the form X - \sum c_{i_1, \ldots, i_k} \cdot Y_1^{i_1} \cdots Y_k^{i_k} are irreducible, Lemma 5 applies in the rational function field \mathbb{F}(X, Y_1, \ldots, Y_k). The only change is that the verifier now samples x from \mathbb{F} and \vec{y} = (y_1, \ldots, y_k) from \mathbb{F}^k.

4. Multivariate Plookup

This section sketches batch-column lookups using the Plookup strategy and the multivariate time shift introduced by Hyperplonk [CBBZ22]. The time shift T: H \to H on the boolean hypercube H = \{\pm 1\}^n is derived from the multiplication by a primitive root in \text{GF}(2^n),

where the c_i \in \{0, 1\} are coefficients of a primitive polynomial over \text{GF}(2). The time shift acts transitively on the punctuated hypercube H' = H \setminus \{\vec{1}\}.

4.1 Batch-column Plookup

Let t: H' \to \mathbb{F} be the lookup table, and f_i: H' \to \mathbb{F}, i = 1, \ldots, M, the functions subject to the lookup. The prover provides the ordered union via additional functions s_i: H' \to \mathbb{F}, i = 1, \ldots, M+1. The Plookup identity is

The identity is reduced to a grand product over H' by random samples \alpha, \beta \leftarrow \mathbb{F}, yielding

where

As in Protocol 2, the product is split into K = \lceil \frac{M+1}{\ell} \rceil partial products. For each k = 1, \ldots, K, the prover computes cumulative products \phi_k along the orbit of the time shift T on H'. Correctness is proven by domain identities and point identities, all reduced to sumchecks. The resulting sumcheck polynomial Q has absolute degree d = \ell + 2 (same as Protocol 2) but about double the variables: \nu = 2(M + 1 + K) + 3.

4.2 Computational cost and optimal product size

The total costs of the oracle prover for the Plookup strategy are:

• Arithmetic costs of
  |H| \cdot \left( (2\ell^2 + 13\ell + 18) \left\lceil \frac{M+1}{\ell} \right\rceil + \ell \cdot (2M + 7) + 8(M+3) \right) \cdot \mathsf{M},
  neglecting field additions.
• Oracle costs of
  M + K + 1 = M + \left\lceil \frac{M+1}{\ell} \right\rceil + 1
  functions of size |H|.

The partial product size \ell determines the trade-off between algebraic degree and the number of commitments. The paper provides benchmark-based estimates for the optimal choice using multi-scalar multiplication over the Pallas curve.

4.3 Bounded multiplicity encoding

The Polygon MidenVM [Mid] uses an improvement of Plookup that reduces the number of commitments for the sorted union by arranging it as runs of at most B = 2^b occurrences, b \ge 1. The length m of each run (reduced by one) is given bitwise,

and the power of the corresponding term Z in the lookup product is selected by the expression

The commitment costs for s are reduced by the factor \frac{R \cdot (1 + \log_2 B)}{M + 1} \approx \frac{1 + \log_2 B}{B}, whereas the absolute degree of the lookup identity increases only by the factor approximately 1 + \frac{\log_2 B}{B}.

5. Comparison

The significant advantage of the logarithmic derivative lookup over Plookup is the lower oracle costs. While the Plookup strategy demands M+1 oracles for the sorted union of the M witness columns and the table, the logarithmic derivative approach demands only a single one for the multiplicities. The two strategies are compared by their computational cost per column when running with the optimal sum/product size \ell.

The paper provides a rough comparison with the bounded multiplicity improvement. For a quadratic overall domain identity (cubic sumcheck polynomial Q):

• The logarithmic derivative approach needs overall M+1 oracles: one for the multiplicity function and M helper functions.
• Plookup demands overall 2(M+1) oracles: M+1 for the sorted union and M+1 for cumulative products.
• With multiplicity encoding using b bits, Plookup improves down to M + 1 + \lceil \frac{M}{2^b} + 1 \rceil \cdot 3b oracles. In the extreme setting 2^b = M, this gives M + 1 + 6 \log_2(M) oracles.

Multiplicity encoding seems beneficial only for quite large batches of columns. Below M = 32 columns it performs even worse than Plookup. For M = 64 and M = 128, it consumes 78% and 66% of Plookup’s commitments respectively, which is still about 55% and 30% more than the logarithmic derivative approach.

Acknowledgements

The author would like to thank Rayan Matovu and Morgan Thomas for giving me the space and time to dwell on batch-column lookups during my employment at Orbis Labs. Special thanks to Marcin Bugaj for helping out with the Pippenger benchmarks. Furthermore, I would like to thank Ariel Gabizon for his feedback and useful discussions.

Appendix A: The flookup proof of radical

Section 5 of [GK22] describes a polynomial IOP for lookups which is almost identical to the logarithmic derivative approach. Let \mathbb{F} be an FFT-friendly finite field, having a multiplicative subgroup H = \{x \in \mathbb{F} : x^n = 1\} of order n, and let g be a generator. For showing that the ranges of witness functions f_i : H \to \mathbb{F}, i = 0, \ldots, M-1, are contained in the range of a table t : H \to \mathbb{F}, the logarithmic derivative identity is turned into the polynomial identity

by multiplying with the precomputed table polynomial v_T(X) = \prod_{x \in H} (X + t(x)). Instead of the multiplicity function m, the prover explicitly provides the polynomial

and engages in an IOP for showing

The verifier queries v_T(X) and R_T(X) at a random challenge \alpha \leftarrow_\$ \mathbb{F}, and both parties run a sumcheck for

where \varphi_i(x) = \alpha + f_i(x). The prover provides the Lagrange representation of the sumcheck polynomial \phi(X) subject to the domain identity

The overall identity has the form Q(\varphi_0(X), \ldots, \varphi_{M-1}(X), \phi(X), \phi(g \cdot X)) = 0 \mod v_H(X), with Q having \nu = M + 2 variables and absolute degree d = M + 1.

References

1. [BCC+16] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. “Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting.” In: EUROCRYPT 2016, Vol. 9666 of LNCS. Springer, 2016. Full paper: eprint.iacr.org/2016/263.
2. [BCG+18] Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen, and Mary Maller. “Arya: Nearly linear-time zero-knowledge proofs for correct program execution.” In: ASIACRYPT 2018, Vol. 11272 of LNCS, 2018. Full paper: eprint.iacr.org/2018/380.
3. [BFS20] Benedikt Bünz, Ben Fisch, and Alan Szepieniec. “Transparent SNARKs from DARK compilers.” In: EUROCRYPT 2020, 2020. Full paper: eprint.iacr.org/2019/1229.
4. [BG12] Stephanie Bayer and Jens Groth. “Efficient zero-knowledge argument for correctness of a shuffle.” In: EUROCRYPT 2012, Vol. 7237 of LNCS. Springer, 2012.
5. [BSBHR18] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. “Scalable, transparent, and post-quantum secure computational integrity.” In: IACR ePrint Archive 2018/046, 2018. eprint.iacr.org/2018/046.
6. [BSCS16] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. “Interactive oracle proofs.” In: TCC 2016, pages 31–60, 2016.
7. [CBBZ22] Binyi Chen, Benedikt Bünz, Dan Boneh, and Zhenfei Zhang. “Hyperplonk: PLONK with a linear-time prover and high-degree custom gates.” In: IACR ePrint Archive 2022/1355, 2022. eprint.iacr.org/2022/1355.
8. [Eag22] Liam Eagen. “Bulletproofs++.” In: IACR ePrint Archive 2022/510, 2022. eprint.iacr.org/2022/510.
9. [EFG22] Liam Eagen, Dario Fiore, and Ariel Gabizon. “cq: Cached quotients for fast lookups.” In: IACR ePrint Archive 2022/1763, 2022. eprint.iacr.org/2022/1763.
10. [Gab22] Ariel Gabizon. “Multiset checks in PLONK and Plookup.” hackmd.io, 2022. hackmd.io/@arielg/ByFgSDA7D.
11. [GK22] Ariel Gabizon and Dmitry Khovratovich. “flookup: Fractional decomposition-based lookups in quasi-linear time independent of the table size.” In: IACR ePrint Archive 2022/1447, 2022. eprint.iacr.org/2022/1447. [page on this site]
12. [GW20] Ariel Gabizon and Zachary J. Williamson. “Plookup: A simplified polynomial protocol for lookup tables.” In: IACR ePrint Archive 2020/315, 2020. eprint.iacr.org/2020/315. [page on this site]
13. [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. “PLONK: Permutations over Lagrange-bases for oecumenical non-interactive arguments of knowledge.” In: IACR ePrint Archive 2019/953, 2019. eprint.iacr.org/2019/953. [page on this site]
14. [KZG10] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. “Constant-size commitments to polynomials and their applications.” In: ASIACRYPT 2010, Vol. 6477 of LNCS. Springer, 2010.
15. [Lab] Avi Dessauer (Orbis Labs). tiny-ram-halo2. github.com/Orbis-Tertius/tiny-ram-halo2.
16. [LFKN92] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. “Algebraic methods for interactive proof systems.” In: Journal of the Association for Computing Machinery, Vol. 39, pages 859–868, 1992. Full paper: eprint.iacr.org/2017/1066.
17. [Mid] Polygon Miden: A STARK-based virtual machine. github.com/maticnetwork/miden.
18. [PK22] Jim Posen and Assimakis A. Kattis. “Caulk+: Table-independent lookup arguments.” In: IACR ePrint Archive 2022/957, 2022. eprint.iacr.org/2022/957. [page on this site]
19. [Pol] Polygon Zero Team: plonky2. github.com/mir-protocol/plonky2.
20. [PST13] Charalampos Papamanthou, Elaine Shi, and Roberto Tamassia. “Signatures of correct computation.” In: TCC 3, Vol. 7785 of LNCS. Springer, 2013.
21. [RDJH22] Gyumin Roh, Wei Dai, Maria Jabbour, and Andrew He. “New lookup argument.” zkResearch, 2022. zkresear.ch/t/new-lookup-argument/32.
22. [Tha13] Justin Thaler. “Time-optimal interactive proofs for circuit evaluation.” In: CRYPTO 2013, Vol. 8043 of LNCS, 2013. Full paper: eprint.iacr.org/2013/351.
23. [ZBK+22] Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, and Mark Simkin. “Caulk: Lookup arguments in sublinear time.” In: IACR ePrint Archive 2022/621, 2022. eprint.iacr.org/2022/621.