2. Methods

Here we detail the Setup

Setup defines the shared parameters for all other methods


#![allow(unused)]
fn main() {
Setup(max_coeffs: usize, point_sets: Vec<Vec<Scalar>>) -> Parameters
}

max_coeffs is the maximum number of coefficiens we will commit/open to at a time. For most curve choices, this should be a power of 2.
point_sets lists different sets of points where we can open a grid to.
- This is done so we can do ahead-of-time computation that only depends on which set of points we are opening at, and not on the actual contents of the data at those indicies.
Ex: point_sets = [[0, 4], [1, 2]] means I can open any rows of the grid at [0, 4] or [1, 2]. We can only open at both [0, 4] at the same time, and not 0 or 4 individually.

Setup does the following

Samples a random $x \in F, g_{1} \in G_{1}, g_{2} \in G_{2}$
Computes $(g_{1}, g_{1}^{x}, g_{1}^{x^{2}}, \dots g_{1}^{x^{max_coeffs - 1}})$
Computes $(g_{2}, g_{2}^{x}, g_{2}^{x^{2}}, \dots g_{2}^{x^{max_coeffs - 1}})$ ¹
For the $i$ -th set of points in point_sets
- Enumerates the points at the given indicies from the FFT domain. Call them $z_{1}, \dots, z_{k}$ .
- Constructs the unique degree $k - 1$ Lagrange polynomials for each $z_{j}$ $l_{i, j} (X) = \frac{\prod _{l \neq = j} ( X - z _{l} )}{\prod _{l \neq = j} ( z _{j} - z _{l} )}$
  - If the denominator is zero due to a repeated point, setup errors
- Constructs the vanishing polynomial $Z_{i} (X) = j \prod (X - z_{j})$
- Computes $θ_{i} = [Z_{i} (x)]_{2}$

For method 1, we only need as many powers of $g_{2}$ as points we open to. For method 2, we only need $g_{2}, g_{2}^{x}$ .

Commiting is exactly the same as in KZG10


#![allow(unused)]
fn main() {
Commit(p: Parameters, poly: Polynomial) -> Commitment
}

Takes the polynomial $f$ and computes $[f (x)]_{1}$ .

Polynomial Multiproof Spec