Learning about zero-knowledge proofs, one kind of gets the impression that these systems would have to either

  • encode computations using univariate polynomials and then rely on quotienting techniques or
  • encode computations using multivariate polynomials and then use the sumcheck protocol.

Eg, this talk at 59:00 (over-)simplified: “quotienting only applies to univariates”.

Here, I’d like to go over multivariate quotienting and some of the theory behind it. The recent Boomy paper applies these ideas to PST and is my main point of reference. :+1: Another source is the textbook “Ideals, Varieties and Algorithms” (IVA – later referring to the 4th edition).

Another post talked about univariate sumcheck and how the lines between univariate and multivariate encodings are blurry because univariates can be used to emulate multivariates.

Recap: univariate quotients

Univariate quotients underlie single-point and multi-point KZG proofs as well as Aurora-style rowcheck. The idea is that a univariate polynomial $f(x)$’s vanishing over a set of points $V \subset F$ is equivalent to a single Euclidean division resulting in a zero remainder. Generally, Euclidean division by some polynomial $g(x)$ says that $f$ can always be expressed as $f(x) = r(x) + q(x) g(x)$. Ie, $r$ is the remainder of $f$ mod $g$. This means that $f$ agrees with $r$ on all those points where $g$ is zero. Then, $r$ being the zero polynomial would mean that $f$ vanishes on the points described by $g$. For quotient proofs, take $g$ as the vanishing polynomial of the set $V$.

Gröbner bases

To generalize the univariate remainder theorem to $m$-variate polynomials, we need so-called Gröbner bases. In a nutshell, if $V \subset F^m$ instead of $V \subset F$ like above, then the vanishing polynomial $g(x)$ needs to be replaced with a set of polynomials $g_1(x_1, \dots, x_m), \dots, g_t(x_1, \dots, x_m)$ called a Gröbner basis. Then, we can say that $f(x_1, \dots, x_m)$ vanishes over $V \subset F^m$ if and only if there is a decomposition $f = \sum_{i \in [t]} q_i g_i.$

In what follows, let’s quickly try to address the following questions: What are $g_1, \dots, g_t$ a “basis” of? What are explicit expressions for them? What is $t$? How do they generalize the remainder theorem and the concept of a univariate vanishing polynomial?

Some definitions

  • $F$ is a finite field, so all subsets $V \subset F^m$ are finite, too. $F$ has large characteristic, all polynomials’ degrees will be smaller than $\mathrm{char}(F)$.
  • An (algebraic) variety is the joint zero set of multiple polynomials, so the points where the polynomials all simultaneously vanish.
  • An ideal $J$ is a set of polynomials that is closed under multiplication, so if $f \in J$, then $f q \in J$ for all $q$, and addition, in that if $f_1,f_2 \in J$, then $f_1+f_2 \in J$. An ideal is maximal if no other ideal (besides $F[x_1, \dots, x_m]$) strictly contains it.
  • If the difference of two polynomials lies in an ideal, then the two polynomials are equivalent modulo the ideal.

Basic facts

  • The set of all polynomials vanishing on a variety $V$, denoted $I(V)$, is an ideal (IVA Chapter 1.4, Lemma 6). Vanishing on $V$ is the same as being in $I(V)$.
  • By the Hilbert basis theorem (IVA Chapter 2.5, Theorem 4), all ideals are finitely generated. So given an ideal $J$, it is possible to find $f_1, \dots, f_t$ such that $J = \langle f_1, \dots, f_t \rangle = \left\{\sum_{i \in [t]} f_i q_i \mid q_i \in F[x_1, \dots, x_m]\right\}$.
  • A Gröbner basis of an ideal $J$ is a generating set $g_1, \dots, g_t$ with the property that $f \in J$ if and only if $f$ can be represented as a combination of Gröbner basis elements, $f = \sum_{i \in [t]} g_i q_i$ (IVA Chapter 2.6, Corollary 2).
  • A generating set where all leading monomials are coprime is a Gröbner basis (IVA Chapter 2.9, Theorem 3 and Proposition 4).
  • A Gröbner basis is reduced if all elements have leading coefficient 1 and no element’s monomials are divisible by other elements’ leading terms. Reduced Gröbner bases are unique, unlike other generating sets or Gröbner bases (IVA Chapter 2.7, Theorem 5).
  • For every univariate ideal $J \subset F[x]$, there is always a single polynomial $g(x)$ such that $J = \langle g \rangle$. So $g$ (made monic by dividing by the leading coefficient, if needed) by itself is the unique reduced Gröbner basis. Equivalence modulo $J$ is the same as equivalence modulo $g$.

PST and Boomy

Ok, now, let’s apply the theory described so far to explain multivariate quotienting. First, how to generalize KZG openings to multivariates? Based on the above, a quotient proof for $f(v_1, \dots, v_m)=0$ has to express $f$ as a combination of the elements of the reduced Gröbner basis for the ideal of the single-point variety $V = \{(v_1, \dots, v_m)\}$. To find the Gröbner basis, consider the polynomials $g_1 = x_1 - v_1, \dots, g_m = x_m - v_m$ and put $J = \langle g_1, \dots, g_m \rangle$. Clearly, $J \subseteq I(V)$ because everything in $J$ vanishes on $V$. But $J$ is actually maximal, which implies $J = I(V)$. Since $g_1, \dots, g_m$ are monic with mutually prime leading monomials, they are the reduced Gröbner basis. This is PST. Doing this for multi-point varieties gives Boomy.

For a general variety $V \subset F^m$, the explicit expressions for $I(V)$’s Gröbner basis polynomials $g_1, \dots, g_t$ can get complicated—-and $t$ can be bigger than $m$. The Gröbner basis of the ideal of an arbitrary finite set of points could be constructed using properties of the intersection of ideals (IVA Chapter 4.3, Theorem 11 ff.) or with more efficient methods like Buchberger-Möller (or just Möller?), Farr-Gao, EssGB. But still, it is worth looking for sets of points where the Gröbner basis is particularly simple.

Zerocheck

The Boomy paper mentions two classes of sets of points $V$ whose ideals have “nice” Gröbner bases. One of them is the Cartesian product $V = V_1 \times \cdots \times V_m$ where $V_1, \dots, V_m \subset F$. The reduced Gröbner basis simply consists of $g_1, \dots, g_m$ where $g_i = \prod_{v \in V_i} (x-v)$, so each $g_i$ is the vanishing polynomial of $V_i$. This class is interesting because it includes hypercubes like $\{0,1\}^m$ and $\{\pm 1\}^m$. To show that a polynomial vanishes over the whole hypercube, protocols like Spartan use the sumcheck protocol. We now know how to do the same thing with quotients: show divisibility by the reduced Gröbner basis of $I(V)$.

Conceptually, this generalizes the univariate Aurora Hadamard/rowcheck technique, though it seems computationally more expensive. For example, consider $m$-linear polynomials $f,g,h$ for which we want to show that $fg \equiv h$ over $\{0,1\}^m.$ Equivalently, $f(x)g(x) = h(x) + \sum_{i \in [m]} q_i(x) (x_i^2-x_i)$ for some $q_i$ because $\{x_i^2-x_i\}$ is the reduced Gröbner basis of $I(\{0,1\}^m)$. Because the left-hand side has degree 2 in each $x_i$, $q_i$ cannot depend on $x_i$ at all. Moreoever, it is possible to compute the $q_i$ incrementally, say, starting with $q_m$, so that $q_i$ has degree 2 in $x_1, \dots, x_{i-1}$ and degree 1 in $x_{i+1}, \dots, x_m$. So $q_i$ is described by $3^{i-1} \cdot 2^{m-i}$ coefficients – or can maybe be interpolated from as many evaluations. I do not know what the best computation strategy would be. But it feels like these $3^i$ factors would make it more complex than the univariate case which would cost $O(m 2^m)$ via FFT. :man-shrugging:

Side notes

The Cartesian product case is the same as Alon’s Combinatorial Nullstellensatz, a theorem used in combinatorics. The name is a reference to Hilbert’s Nullstellensatz, a theorem that was originally stated for algebraically closed fields like the complex numbers (covered in IVA Chapter 4.1). Clark’s refinement of Alon gives some insight into how the combinatorial one works for finite fields.

In the textbook “Computational Commutative Algebra 2” by Kreuzer and Robbiano, 2nd edition, chapters 6.2 and 6.3, I found another perspective on the Cartesian product case. Namely, they explain how $I(V_1 \times \cdots \times V_m)$ is a so-called “distraction” of an ideal that is generated only by monomials, specifically $\langle x_1^{|V_1|}, \dots, x_m^{|V_m|} \rangle$ (Proposition 6.3.8).

Last thoughts

  • The other class of nice Gröbner bases described in the Boomy paper is for ideals of sets of points whose entries are distinct in at least one coordinate. I plan to revisit this one in a future post. But are there any other nice classes? :thinking_face:
  • Gröbner basis also have a classical application in cryptanalysis, nowadays often targeting arithmetization-friendly hash functions. There is a recent survey/tutorial paper about these use cases.
  • Recently, Gröbner bases have also been utilized in the formal verification of arithmetic circuits / constraint systems.

In summary, yes, if we really wanted, we could totally do multivariate quotienting similarly to univariate quotienting. :heavy_check_mark: