Efficient pre-compiles for multisets

General
#1

Background

Previously we already know a few polynomial arguments including multiset-equivalent argument [1], permutation argument [2], lookup argument [3], etc. These polynomial arguments can make the circuit arithemetization more efficient if used properly.

In this article, we want to propose two new polynomial arguments that can perform multiset intersection and union operations.

Fix a field \mathbb F and a root of unity \omega \in \mathbb F of order n. Let \mathcal{L}_i(X) be the Lagrange bases polynomial where \mathcal{L}_i(\omega^j) = 1 if i = j and 0 otherwise.

Representations of Multisets

Consider an n-vector \vec a = (a_0, \ldots, a_{n-1}) \in \mathbb F^n. We identify \vec a with the multi-set \mathcal A = \{a_i\}_{i=0,\ldots, n- 1} and consider two representations of \vec a and A:

  • The standard representation of A is the polynomial
    A(X) = \sum^{n-1}_{i=0} a_i \cdot \mathcal{L}_i(X)
  • The roots representation of the first m element of a A is the polynomial
    Z_{A_m}(X) = \prod_{i=0}^{m-1} (X - a_i) = \prod_{i=0}^{m-1} (X - A(\omega^i))
    We omit writing m when m = n.

Evaluating roots representation at arbitrary points

We can evaluate of Z_{A_m}(X) at any field element using a grand product argument. To prove that Z_{A_m}(\gamma) = y, it suffices to show that for some polynomial Z_1:

  • Z_1(\omega X) = Z_1(X) ( \gamma - A(X))
  • L_0(X) (Z_1(X) - 1) = 0
  • L_{m}(X) (Z_1(X) - y) = 0

Multiset Union Argument

Given polynomials A(X), B(X), C(X) encoding multisets \mathcal A, \mathcal B, \mathcal C of size at most n. We want to show that \mathcal A \cup \mathcal B = \mathcal C as multiset.

Claim: \mathcal A \cup \mathcal B = \mathcal C if and only if there exists polynomial C such that Z_A \cdot Z_B = Z_C.

We remark that this also leads to a multiset inclusion check.

Multiset Intersection Argument

Given multisets \mathcal A, \mathcal B, \mathcal C of size n_A, n_B, n_C, and their standard representation A(X), B(X), C(X). We want to show that \mathcal A \cap \mathcal B = \mathcal C.

Claim: \mathcal A \cap \mathcal B = \mathcal C if and only if there exists polynomials P, Q, C_A, C_B such that

\begin{align*} P\cdot Z_A + Q\cdot Z_B &= Z_C\\ Z_C\cdot C_A &= Z_A \\ Z_C\cdot C_B &= Z_B \;. \end{align*}

The above claim leads to the following natural prover strategy.

  1. Construct polynomials Z_A, Z_B, Z_C encoding the values \{a_i\}, \{b_i\}, \{c_i\} as their roots.
\begin{align} Z_A(X) &= \prod_{0 \leq i < n_A} (X - A(\omega^i)), \\ Z_B(X) &= \prod_{0 \leq i < n_B} (X - B(\omega^i)), \\ Z_C(X) &= \prod_{0 \leq i < n_C} (X - C(\omega^i)). \\ \end{align}

  1. Find polynomials P, Q such that: P\cdot Z_A + Q\cdot Z_B = Z_C.
    By Bézout’s Theorem for univariate polynomials over a field, if Z_C is the greatest common divisor of Z_A and Z_B, then the two polynomicals P and Q must exist.

  2. Further check that Z_C does not contain “extra” elements (that are neither in Z_A or Z_B). This amounts to two multiset inclusion checks, i.e. there exists two polynomials C_A, C_B such that:

\begin{align} Z_C \cdot C_A &= Z_A, \\ Z_C \cdot C_B &= Z_B. \end{align}
3 Likes