Disclaimer: This documentation was written on September, 2021. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code. Emulated Field We want to evaluate a modular multiplication of $\mathbb{F}_p$ elements a, b, using constraints over $\mathbb{F}_n$ ($p,n$ are prime). In particular we allow for the case where $n < p$. We will choose integer $t$ such that $2^t\cdot n> p^2$. And also leverage operations mod $2^t$ together with the CRT. In more detail: We will check that as positive integers $$a\cdot b = q\cdot p +r $$ The way we do this at a high level is

By Justin Drake && Ariel Gabizon && Izaak Meckler Let $H\subset F$ be a multiplicative subgroup of order $n=2^t$. In this note, we show a method for proving univariate identities over $H$ hold where the prover runs in $O(n)$ time when the polynomials involved have degree $O(n)$, and the base identity is of constant degree. The most common example of such an identity is the degree 2 identity $XY-Z$; namely, the Hadamard check: $f\cdot g = h$ on $H$. The typical way to do such checks is via computing a quotient, e.g. $T=(f\cdot g -h)/Z_H$ in the Hadamard case. This requires $O(n \log n)$ operations. Comparison to hyperplonk Lately, people have been using sumcheck and multilinear polynomials to get $O(n)$ prover time. Our protocol nearly matches the asymptotic performance of HyperPLONK.

Grand Products PLONK at its technical heart is based on the following primitive - The grand product check: given commitments to polynomials $f,g$ over a finite field $\mathbb{F}$, and a subset $H={x_1,\ldots,x_n}\subset \mathbb{F}$ check that the product of values of $f$ and $g$ over $H$ agree. That is, whether $$\prod_{i\in [n]} a_i \stackrel{?}{=} \prod_{i\in [n]} b_i,$$ where $a_i = f(x_i)$ and $b_i = g(x_i)$. The PLONK paper shows this check can be performed with great efficiency when $H$ is a multiplicative subgroup. Polynomials and Vectors Throughout this post, whenever we discuss a vector $a$ of length $n$, we assume in the actual protocol the prover has sent a commitment to a polynomial $f$ with $f(x_i)=a_i$ as above. Thus, we can allow operations like adding vectors coordinate wise, that will be emulated in the real protocol by applying the same operation on the polynomial commitments.

The purpose of this note is to explain (also to myself) the main idea in the Halo recursive SNARK construction of Bowe, Grigg and Hopwood https://eprint.iacr.org/2019/1021. In fact, my understanding of the protocol heavily relies on the new paper of Bünz, Chiesa, Mishra and Spooner [BCMS] which fills in many details and generalizes the approach to achieve "Proof Carrying Data Via Accumulation Schemes". The starting point is the inner product argument of Bootle et. al and its optimization in the Bullet Proofs paper. It was known that a special case of this inner product argument gave a polynomial commitment scheme (by taking the second vector to be a power vector of the form $(1,x,x^2,\ldots,x^n)$). Let us call this scheme for brevity the BP-PCS. For the purpose of this note it is not needed to understand the inner workings of BP-PCS. Here are its main good and bad properties: