Plookup - HackMD

$$ \def\bold#1{\boldsymbol{#1}} \def\stop{{\rlap{\quad.}\hphantom{}}} \def\qed{{\rlap{\quad \tiny\blacksquare}\hphantom{}}} \def\par{{\thinspace {\parallel} \thinspace}} \def\hso{{\hspace{1pt}}} \def\F{{\mathbb{F}}} \def\G{{\mathbb{G}}} \def\Z{{\mathbb{Z}}} $$ # Plookup ## PLONK Proving in Three Acts 1. **Constraint Satisfaction** - proves arithmetic; proves that the witness contains legal inputs and output for each gate. 2. **Permutation Argument** - proves wiring; proves that the witness agrees with the circuit's wiring. 3. **Lookup Arguments** - proves outsourced computation; proves that the witness agrees with public evaluation tables. **Example:** "I know $(a, b, c, h)$ such that $\text{XOR}(a + b, b * c) * h = \textsf{PI}$", where $\textsf{PI}$ is a public input and $\text{XOR}(X_1, X_2) = Y$ is a function that has been outsourced to a lookup table $T_{\Tiny\text{XOR}}$. ![](https://i.imgur.com/mOSJ2Li.png) $$ \begin{array}{|c|c|} \hline \textbf{Constraints} & \textbf{Permutation} & \textbf{Lookups} \\ \hline a + b = e & (b\ d)(i\ j) & (e, f, g) \in T_{\Tiny\text{XOR}} \\ c * d = f & \\ g * h = i \\ j = \textsf{PI} \\ \hline \end{array} $$ ## Plookup Overview 1. We can test array equality using difference arrays 2. We can derive an expression, using difference arrays, for testing subarray-edness 3. We can encode difference arrays as polynomials 4. Transitively, we can test subarray-edness using those polynomial encodings via Schwartz-Zippel 5. We can construct a public table containing the legal inputs and outputs for an expensive circuit subcomputation 6. A prover can prove, using the polynomial expression for testing subarray-edness, that the parts of their witness corresponding to the input and output of the expensive subcomputation are a subset of the subcomputation's input-output table ## Definitions (TODO: clarify) * "ordered multiset" == sorted array * "concatenation" $\bold{a} \parallel \bold{b}$ == sorted insertion * "subarray" $\bold{b} \subset \bold{a}$ == an array whose elements are a subset of, and appear in the same order as, another array. $$ \bold{a} = (1, 2, 3) \\ \eqalign{ (1, 2) &\subset \bold{a} \\ (1, 1, 1, 1, 2, 3) &\subset \bold{a} \\ (3, 1) &\not\subset \bold{a} \\ (1, 2, 3, 4) &\not\subset \bold{a} } $$ ## Subarray Test using Difference Arrays For an array $\bold{a}$ we use $\bold{a'}$ to denote $\bold{a}$'s **difference array**, i.e. the array containing the differences between adjacent elements in $\bold{a}$: $$ \eqalign{ \bold{a} &= (a_1, \dots, a_n) \\ \bold{a'} &= (a_{i + 1} - a_i \mid \forall i \in [n - 1]) \stop } $$ If you know the starting point of two (sorted) arrays and you know their difference arrays, then you know whether the arrays are equal. ![Walking up the Integer Stairs](https://i.imgur.com/pQ6MQPw.png) Stated another way: $$ \eqalign{ \text{if: } & \bold{a} = (a_1, \dots, a_n) \\ \text{then: } & \not\exists \bold{b} = (a_1, \dots, b_n) \neq \bold{a} \text{ such that } \bold{b'} = \bold{a'} \stop } $$ :::spoiler **Side Note:** Peano axioms Peano addition axiom: $a + b = c$ and $a + d = c$ implies $b = d$. Peano axioms 1889 succeeded Group axioms 1830-1870. ::: Duplicating values in an array does not change the array's non-zero differences, it only increments the number of zero differences. $$ \eqalign{ \bold{a} &= (1, 3, 7) \\ \bold{a'} &= (2, 4) \\ \bold{b} &= \bold{a} \par a_2 = (1, 3, \underline{3}, 7) \\ \bold{b'} &= (2, \underline{0}, 4) } $$ For an array $\bold{a}$, if unknown values $\bold{b}$ are inserted into $\bold{a}$, i.e. $\bold{c} = \bold{a} \par \bold{b}$, such that the first element $a_1$ is unchanged, we can determine if $\bold{b} \subset \bold{a}$ by comparing $\bold{a'}$ and $\bold{c'}$. This is because duplicating elements in an array only increases the number of zeros in its difference array. $$ \eqalign{ \bold{c} &= \bold{a} \par \bold{b} \\ \bold{c'} &= \bold{a'} \par 0^{|\bold{b}|} } $$ **Example:** Subarray equality using difference arrays. $$ \eqalign{ \bold{a} &= (1, 3, 6, 10) \\ \bold{b} &= (3, 10) \subset \bold{a} \\ \bold{c} &= \bold{a} \par \bold{b} = (1, 3, \underline{3}, 6, 10, \underline{10}) \quad\quad \text{note: } c_1 = a_1 \\ \bold{a'} &= (2, 3, 4) \\ \bold{c'} &= (2, \underline{0}, 3, 4, \underline{0}) = \bold{a'} \par 0^{|\bold{b}|} } \\~ \\~ \\ \eqalign{ \bold{b} &= (3, 5) \not\subset \bold{a} \\ \bold{c} &= \bold{a} \par \bold{b} = (1, 3, \underline{3}, \underline{5}, 6, 10) \quad\quad \text{note: } c_1 = a_1 \\ \bold{c'} &= (2, \underline{0}, \underline{2}, 3, 4) \neq \bold{a'} \par 0^{|\bold{b}|} } $$ ## Subarray Test using Randomized Difference Arrays We are able to test array equality using differences between adjacent elements when two arrays have the same starting point: $$ \eqalign{ \bold{a} &= (a_1, \dots, a_n) \\ \bold{b} &= (a_1, ?, \dots, ?) \\ \bold{a'} &= \bold{b'} \ \ \Longrightarrow \ \ \bold{a} = \bold{b} } $$ but, can we use this to test array equality without knowing $a_1 = b_1$? Yes, by comparing **randomized difference arrays** $\bold{a'_\gamma}$ and $\bold{b'_\gamma}$ for a random $\gamma$ we can say w.h.p. whether $\bold{a} = \bold{b}$. $$ \eqalign{ \bold{a'_\gamma} &= (a_{i + 1}\gamma - a_i \mid \forall i \in [n - 1]) \\ \bold{b'_\gamma} &= (b_{i + 1}\gamma - b_i \mid \forall i \in [n - 1]) \\ } \\ \bold{a'_\gamma} = \bold{b'_\gamma} \ \ \overset{\text{w.h.p.}}\Longrightarrow \ \ \bold{a} = \bold{b} $$ Given $\bold{a}$, it's not hard to find a $\bold{b} \neq \bold{a}$ such $\bold{a'} = \bold{b'}$, however it is highly improbable that an array $\bold{b} \neq \bold{a}$ could be chosen without prior knowledge of $\gamma$ such that its randomized difference array is the same as $\bold{a}$'s, i.e. $\bold{a'_\gamma} = \bold{b'_\gamma}$. :::spoiler **Proof:** Randomized difference array equality implies array equality. Given two 2-tuples (vectors): $$ \eqalign{ \bold{a} &= (a_1, a_2) \\ \bold{b} &= (b_1, b_2) \neq \bold{a} } $$ if we encode the vectors into unique degree-1 polynomials of the form: $$ a(X) = (a_2X - a_1) \\ b(X) = (b_2X - b_1) $$ then Schwartz-Zippel tells us that each polynomial will (w.h.p.) evaluate uniquely on a random input $\gamma$. $$ a(\gamma) \neq b(\gamma) $$ Equivalently, the vectors' randomized difference arrays will be (w.h.p.) unequal. $$ \eqalign{ a(\gamma) = \bold{a'_\gamma} &= (a_2\gamma - a_1) \\ b(\gamma) = \bold{b'_\gamma} &= (b_2\gamma - b_1) \\ \bold{a'_\gamma} &\neq \bold{b'_\gamma} } $$ Now, if we consider vectors of length $n > 2$: $$ \eqalign{ \bold{b} &= (b_1, \dots, b_n) \neq \bold{a} } $$ and if we encode each pair of adjacent elements as a unique degree-1 polynomial $(a_{i + 1}X - a_i)$, we can uniquely write $\bold{a}$ and $\bold{b}$ as polynomials by taking the product of each's linear terms. $$ a(X) = \prod_{i \in [n - 1]} (a_{i + 1}X - a_i) \\ b(X) = \prod_{i \in [n - 1]} (b_{i + 1}X - b_i) $$ Schwartz-Zippel tells us that each degree-1 polynomial will (w.h.p.) evaluate uniquely on a random input $\gamma$, thus the vector's difference arrays will be (w.h.p.) unequal. $$ \bold{a'_\gamma} \neq \bold{b'_\gamma} \\ \forall i \in [n - 1]: (a_{i + 1}\gamma - a_i) \neq (b_{i + 1}\gamma - b_i) $$ Evaluating $a(\gamma)$ is the same as taking the product of $\bold{a}$'s randomized difference array elements. $$ \eqalign{ a(\gamma) &= \prod \bold{a'_\gamma} \\ b(\gamma) &= \prod \bold{b'_\gamma} } $$ The definition of a group tells us that products are uniformly distributed (i.e. uniqueness of Cayley rows and columns): $$ a_1, a_2, b_1, b_2 \in \F \\ \Pr[a_1a_2 = b_1b_2 \mid (a_1, a_2) \neq (b_1, b_2)] = {1 \over |\F|} $$ thus, for arrays of length $n$ induction tells us that: $$ \Pr[a(\gamma) = b(\gamma) \mid \bold{a} \neq \bold{b}] = {1 \over |\F|} \stop $$ --- ::: We can encode each pair of adjacent elements in $\bold{a}$ uniquely as degree-1 polynomial $(a_{i + 1}X - a_1)$; taking the product of these linear terms uniquely maps $\bold{a}$ to a polynomial. $$ a(X) = \prod_{i \in [n - 1]} (a_{i + 1}X - a_i) $$ :::spoiler **Side Note:** Standard PLONK encodes sets/arrays into polynomials using the same method (the **multiset check**). Plookup's method of encoding arrays into polynomials is the same method used in standard PLONK to encode sets and arrays into polynomials. $$ \begin{array}{rl} \text{Standard PLONK: } & \text{sets } & \{a_1, \dots, a_n\} & & \Longleftrightarrow \ \prod_{i \in [n]}(X - a_i) \\ & \text{arrays } & (a_1, \dots, a_n) \ \ \ \Longleftrightarrow & \{(1, a_1), \dots, (n, a_n)\} & \Longleftrightarrow \ \prod_{i \in [n]} (iX - a_i) \\ \text{Plookup: } & \text{arrays } & (a_1, \dots, a_n) \ \ \ \Longleftrightarrow & \{(a_1, a_2), \dots, (a_{n - 1}, a_n)\} & \Longleftrightarrow \ \prod_{i \in [n - 1]} (a_{i + 1}X - a_i) \end{array} $$ Writing each element of a set/array as a unique degree-1 polynomial maps that set/array to a unique polynomial which is the product of those linear terms (**Fundamental Theorem of Algebra**). Using Schwartz-Zippel, we can (probabilistically) test polynomial equality, which tells us (probabilistically) whether encoded sets/arrays are equal. --- ::: An array containing $n$ repetitions has a difference array containing $n$ zeros because each repetition of an element $a_i$ in $\bold{a}$ adds the element $a_i - a_i = 0$ to $\bold{a'}$, likewise adding the degree-1 polynomial $(a_iX - a_i)$ to $a(X)$, e.g. $$ \eqalign{ \bold{a} &= (1, \underline{3, 3}, \underline{7, 7}) \\ \bold{a'} &= (2, \underline{0}, 4, \underline{0}) \\ a(X) &= (3X - 1)\underline{(3X - 3)}(7X - 3)\underline{(7X - 7)} \stop } $$ If unknown values $\bold{b}$ are inserted into an $\bold{a}$, i.e. $\bold{c} = \bold{a} \par \bold{b}$, we can compare difference arrays pre- and post-insertion to test whether $\bold{b} \subset \bold{a}$. Using our polynomial encoding for an array, we can write the expression for subarray-edness as a polynomial equality, e.g. $$ \eqalign{ \bold{a} &= (1, 3, 7) \\ \bold{b} &= (3, 7) \subset \bold{a} \\ \bold{c} &= \bold{a} \par \bold{b} = (1, 3, \underline{3}, 7, \underline{7}) \\ \bold{a'} &= (2, 4) \\ \bold{c'} &= (2, \underline{0}, 4, \underline{0}) = \bold{a'} \par 0^{|\bold{b}|} \\ a(X) &= (3X - 1)(7X - 3) \\ c(X) &= (3X - 1)\underline{(3X - 3)}(7X - 3)\underline{(7X - 7)} \\ &= a(X) \prod_{i \in [|\bold{b}|]} (b_iX - b_i) \stop } $$ Thus, the subarray check $\bold{c'} = \bold{a'} \par 0^{|\bold{b}|}$ written as a polynomial equality becomes: $$ \eqalign{ c(X) &= a(X)\prod(b_iX - b_i) \\ &= a(X)\bold{b}(X - 1) } $$ which can be checked (probabilistically) using Schwartz-Zippel at a random $\gamma$: $$ c(\gamma) = a(\gamma)\prod_{i \in [|\bold{b}|]}(b_i\gamma - b_i) \ \ \overset{\text{w.h.p.}}\Longrightarrow \ \ \bold{b} \subset \bold{a} \stop $$ ## Plookup If our computation has a subcomputation $f$ which is not amenable to PLONK's arithmetization (proceeds naturally via addition and multiplication, integers are modulo a large prime) we can replace $f$ using a precomputed lookup table $T$ that contains all of $f$'s legal input-output pairs, then instead of arithmetizing $f$, the prover and verifier compute $T$ in its entirety, then the prover proves that the values in their witness corresponding to calls to $f$ are in the table $T$. ![Plookup](https://i.imgur.com/mhO09EV.png) :::spoiler **Example:** XOR-ing 3-bit integers is expensive in R1CS. I know two 3-bit integers $a$ and $b$ where $\text{XOR}(a, b) = c_\text{pub}$. We must allocate a field element for every bit, add a constraint for every bit, and add a constraint for binary decomposition. Note that $\text{lsb_bits}(a) = (a_0, a_1, a_2$), $\text{lsb_bits}(b) = (b_0, b_1, b_2$), and $\text{lsb_bits}(c) = (c_0, c_1, c_2$). $$ \eqalign{ \textsf{public inputs: } & c \\ \textsf{allocations: } & a_0, a_1, a_2, b_0, b_1, b_2, c_0, c_1, c_2, \\ \textsf{constraints: } & a_0 - {a_0}^2 == 0 & a_0 \text{ is binary} \\ & a_1 - {a_1}^2 == 0 & \vdots \\ & a_2 - {a_2}^2 == 0 \\ & b_0 - {b_0}^2 == 0 \\ & b_1 - {b_1}^2 == 0 \\ & b_2 - {b_2}^2 == 0 \\ & 2a_0b_0 - a_0 - b_0 == c_0 & \text{XOR}(a_0, b_0) = c_0 \\ & 2a_1b_1 - a_1 - b_1 == c_1 & \vdots \\ & 2a_2b_2 - a_2 - b_2 == c_2 \\ & 2^0c_0 + 2^1c_1 + 2^2c^2 == c & \text{lsb_bits}(c) = (c_0, c_1, c_2) } $$ ::: The input-output table $T$ for a $u \hso {:} \hso v$ function $f$ can be *compressed* from a set of $(u \hso {+} \hso v)$-tuples into a set of integers $t$, were each tuple $T_i \in T$ is mapped to a unique integer $t_i$ via a random combination using randomness $\gamma$ sampled by the verifier (w.h.p. uniqueness of this mapping can be proven using Schwartz-Zippel). **Example:** Table compression for a 2:1 function $f$. The number of distinct inputs to $f$ is $n = |\mathbb{F}^2|$ . $$ f(A, B) = C \\ \eqalign{ T &= \{(a_i, b_i, c_i) \mid \forall (a_i, b_i) \in \mathbb{F}^2, f(a_i, b_i) = c_i \} \\ t &= \{a_i\gamma^0 + b_i\gamma^1 + c_i\gamma^2 \mid \forall (a_i, b_i, c_i) \in T \} } \\~ \\ \begin{array}{|c|} \hline \boldsymbol{T} \\ \hline (a_1, b_1, c_1) \\ \vdots \\ (a_n, b_n, c_n) \\ \hline \end{array} \ \ \mapsto \ \ \begin{array}{|c|} \hline \boldsymbol{t} \\ \hline t_1 \\ \vdots \\ t_n \\ \hline \end{array} \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \qed $$ Once the PLONK prover and verifier have computed $t$ for $f$, the prover shows that parts of their witness corresponding to calls to $f$ are elements of $t$. Let's say that our general computation outsources an expensive bivariate subcomputation $f(A, B) = C$ which is called $\lambda$ times within our general computation. Then for each $i \in [\lambda]$ call to $f$, there must exist a tuple in the prover's witness $(a_i, b_i, c_i) \subset \bold{u}$ which is also found in $T$. The prover compresses each witnessed input-output tuple into a distinct integer $(a_i, b_i, c_i) \mapsto f_i$ using the same procedure used to compress $T$ into $t$. The set of all witnessed input-output tuples for $f$, which have been compressed, is denoted $\{f_i\}$ which must be proven to be subset $\{f_i\} \subset t$. $$ \{f_i\} = \{a_i\gamma^0 + b_i\gamma^1 + c_i\gamma^2 \mid \forall i \in [\lambda], (a_i, b_i, c_i) \subset \bold{u}\} $$ The subset check $\{f_i\} \overset{?}\subset t$ is performed using the polynomial encodings of $\{f_i\}$ and $t$. First the sets $t$ and $\{f_i\}$ are sorted into arrays $\bold{t}$ and $\bold{f}$ respectively, then $\bold{f}$ is inserted into $\bold{t}$, i.e. $\bold{s} = \bold{t} \par \bold{f}$. Comparing the randomized differences pre- and post-insertion (i.e. comparing $\bold{t'}$ and $\bold{s'}$) at a random $\beta$, tells us (w.h.p.) whether $\bold{f} \subset \bold{t}$. $$ \eqalign{ |\bold{t}| &= n \\ |\bold{f}| &= \lambda \\ \bold{s} &= \bold{t} \par \bold{f} \\ t(X) &= \prod_{i \in [n - 1]}(t_{i + 1}X - t_i) \\ s(X) &= \prod_{i \in [n + \lambda - 1]}(s_{i + 1}X - s_i) \\ & = t(X)\bold{f}(X - 1) \\ s(\beta) &= t(\beta)\prod_{i \in [\lambda]}(f_i\beta - f_i) \ \ \overset{\text{w.h.p.}}\Longrightarrow \ \ \bold{f} \subset \bold{t} } $$ **Example:** Prove that the witness $\bold{u}$ agrees with the publicly known input-output table for $f$? $$ f(A, B) = C \\ T = \{(a_i, b_i, c_i) \mid \forall (a_i, b_i) \in \mathbb{F}^2, f(a_i, b_i) = c_i\} \\ \gamma \leftarrow \mathbb{F} \\ t = \{a_i\gamma^0 + b_i\gamma^1 + c_i\gamma^2 \mid \forall (a_i, b_i, c_i) \in T\} \\ \bold{t} = \textsf{sorted}(t) = (t_1, \dots, t_n) \\ t(X) = \prod_{i \in [n - 1]} (t_{i + 1}X - t_i) \\~ \\ \bold{u} = (u_1, \dots, u_w) \\ \lambda = 2 \\ f(u_2, u_7) = u_3 \\ f(u_5, u_4) = u_8 \\ f_1 = u_2\gamma^0 + u_7\gamma^1 + u_3\gamma^3 \\ f_2 = u_5\gamma^0 + u_4\gamma^1 + u_8\gamma^3 \\ \{f_i\} = \{f_1, f_2\} \\ \bold{f} = \textsf{sorted}(\{f_i\}) = (f_1, f_2) \\ \bold{s} = \bold{t} \par \bold{f} \\ s(X) = t(X)\prod_{i \in [\lambda]}(f_iX - f_i) \\ ~\\ \beta \leftarrow \mathbb{F} \\ s(\beta) = t(\beta)\prod_{i \in [\lambda]}(f_i\beta - f_i) \ \ \overset{\text{w.h.p.}}\Longrightarrow \ \ \bold{f} \subset \bold{t} \qed $$ ## Prime Factorization For a positive integer $a \in \Z_{>0}$ with $n$ distinct prime factors $|\textsf{PF}(a)| = n$, e.g. $$ 210 \in \mathbb{R} \\ \textsf{PF}(210) = \{2, 3, 5, 7\} \\ n = 4 $$ then the number of distinct binary products of positive integers that equal $a$ is: $$ \lambda = \sum_{\ell \in [\lfloor n / 2 \rfloor]} \left(\ell \atop n \right) $$ i.e. there is $\left(1 \atop n \right)$ integers whose prime factorization contains exactly one integer from $\textsf{PF}(a)$, and there are $\left(2 \atop n \right)$ integers whose prime factorization contains exactly two integers from $\textsf{PF}(a)$, and so on until you are choosing integers whose prime factorization contains exactly $\lfloor n / 2 \rfloor$ integers from $\textsf{PF}(a)$, e.g. $$ \left. \eqalign{ (2)(3 * 5 * 7) \\ (3)(2 * 5 * 7) \\ (5)(2 * 3 * 7) \\ (7)(2 * 3 * 5) } \ \ \right\} {\left(1 \atop 4 \right) \over 1} = 4 \\ \left. \eqalign{ (2 * 3)(5 * 7) \\ (2 * 5)(3 * 7) \\ (2 * 7)(3 * 5) \\ } \ \ \right\} {\left(2 \atop 4 \right) \over 2} = 3 $$ Thus, the probability of randomly choosing two real numbers whose product is $a$ is: $$ \Pr[b * c = a \mid b, c \leftarrow \Z_{>0}] = {\lambda \over |\Z_{>0}|} \stop $$ probability of randomly choosing two positive integers $b, c \leftarrow \Z_{>0}$ whose product $b * c = a$ is: $$ \Pr[b * c = a] = (n - 1)! + (n - 2)! + \dots + 1! $$ ## Grand Product Argument **IMOW:** for two equal composite integers $x = y$ it is easy to find more than one set (or arrays) of integers $\{a_1, \dots, a_n\}$ whose product is $\prod a_i = x = y$. $$ \eqalign{ x &= y \\ x &= x_1x_2x_3 \\ y &= y_1y_2y_3 \\ \{x_1, x_2, x_3\} &\neq \{y_1, y_2, y_3\} \\ \textsf{PF}(x) &= \textsf{PF}(y) = \{\alpha, \alpha, \beta, \gamma\} \\ x_1 = \alpha\alpha, \quad x_2 &= \beta, \quad x_3 = \gamma \\ y_1 = \beta\gamma, \quad y_2 &= \alpha, \quad y_3 = \alpha \\ } $$ For an array $\bold{a} = (a_1, a_2)$, taking the product of its elements annihilates ordering: $$ a_1a_2 = a_2a_1 $$ similarly, the product of degree-1 polynomials annihilates ordering: $$ (X - a_1)(X - a_2) = (X - a_2)(X - a_1) \stop $$ For two sets $a = \{a_1, \dots, a_n\}$ and $b = \{b_1, \dots, b_n\}$, we can test equality (i.e. that the sets contain the same elements, indifferent to ordering) $$ \eqalign{ s'(X) &= t'(X)\bold{f}(X - 1)\\ \prod_{i \in [|\bold{t}| + |\bold{f}| - 1]} (s_{i + 1}X - s_i) &= \prod_{i \in [|\bold{t} - 1|]}(t_{i + 1}X - t_i)\prod_{i \in [\lambda]}(f_iX - f_i) } $$ **IMOW 2:** Taking the product of array elements annihilates ordering, i.e. two unequal arrays $\bold{a} = (a_1, a_2)$ and $\bold{b} = (a_2, a_1)$ may have the same product. $$ \forall i \in [n]: a_i \mathbin{\tilde\neq} b_i \\ \prod_{i \in [n]} a_i = \prod_{i \in [n]} b_i $$ It is not until all $n$ elements have been multiplied that we can say whether two arrays might contain the same elements. $$ \prod_{i \in [n - 1]} a_i \neq \prod_{i \in [n - 1]} b_i \ \ \ \ \ \rlap{\Longrightarrow}{\ \ /} \ \ \ \ \ \ \prod_{i \in [n]} a_i \neq \prod_{i \in [n]} b_i $$ Taking the products of array elements tells us definitively whether two arrays are unequal, but does not tell us whether the arrays are equal. $$ \prod_{i \in [n]} a_i \neq \prod_{i \in [n]} b_i \Longrightarrow \bold{a} \neq \bold{b} \\ \prod_{i \in [n]} a_i = \prod_{i \in [n]} b_i \ \rlap{\Longrightarrow}{\ \ /} \quad \bold{a} = \bold{b} $$ We can say w.h.p. whether two arrays contain the same elements by using a random value $\gamma$: $$ \prod_{i \in [n]} (a_i + \gamma) = \prod_{i \in [n]} (b_i + \gamma) \ \ \overset{\text{w.h.p.}}\Longrightarrow \ \ \bold{a} = \bold{b} $$ which follows from Schwartz-Zippel by encoding arrays into polynomials (here we've negated the sign of each root, or array element). $$ a(X) = \prod (X + a_i) \\ b(X) = \prod (X + b_i) \\ \Pr[a(\gamma) = b(\gamma) \mid \gamma \leftarrow \mathbb{F}] \leq {d \over |\mathbb{F}|} $$ A prover can use a **grand product argument** to prove that they know an array $\bold{b} = (b_1, \dots, b_n)$ whose elements are the same as an array $\bold{a} = (a_1, \dots, a_n)$ that known to a verifier. If the two arrays contain the same elements (indifferent of order) then their products will be equal $\prod a_i = \prod b_i$. $$ \{a_i\} = \{b_i\} \ \ \Longrightarrow \ \prod_{i \in [n]} a_i = \prod_{i \in [n]} b_i \ \ \Rightarrow \ {a_1 \dots a_n \over b_1 \dots b_n} = 1 $$ The prover can send to the verifer (hidden) array elements $b_i$ whose product the verifier can compare to their array elements' product $a_1 \dots a_n$. $$ \begin{array}{lcl} \mathcal{P} & \overset{b_1}\longrightarrow & \mathcal{V}& \\ & & t_1 = {a_1 \dots a_n \over b_1} \\ \mathcal{P} & \overset{b_2}\longrightarrow & \mathcal{V} \\ & & t_2 = {t_1 \over b_2} = {a_1 \dots a_n \over b_1b_2} \\ & \vdots & \\ \mathcal{P} & \overset{b_n}\longrightarrow & \mathcal{V} \\ & & t_n = {t_{n - 1} \over b_n} = {a_1 \dots a_n \over b_1 \dots b_n} \\ & & t_n \overset{?}= 1 \end{array} $$ **Question** how do we relate the polynomial encodings to the grand-product? --- **Question:** Why not use standard PLONK's array encoding to test difference polynomial $\bold{a'}(X)$ equality? I.e. why not write $\bold{a'}$ as $a'(X) = \prod_{i \in [n - 1]}(iX - a_{i + 1} - a_i)$, ? **Answer:** Because that encoding doesn't encode $\bold{a}$'s values, specifically its endpoint, only the difference between values. Therefore, two different arrays which start at different values, but which have equal difference arrays will yield the same polynomial encodings. The correct polynomial encoding encodes both the endpoints and differences. $$ \eqalign{ \bold{a} &= (0, 4, 9) \\ \bold{b} &= (10, 14, 19) \\ a_1 &\neq b_1 \\ \bold{a'} &= \bold{b'} = (4, 5) \\ a'(X) &= b'(X) = \prod_{i \in [n - 1]} (iX - a_{i + 1} - a_i) = (1X - 4)(2X - 5) \\ a'(\gamma) &= b'(\gamma), \text{however } \bold{a} \neq \bold{b} } $$