Overview

The Polynomial Multiproof (PMP) scheme is a polynomial commitment scheme that allows for efficiently creating/verifying opening proofs for multiple polynomials at multiple points.

Here's why this project is cool: Opening gets faster the more points we open a polynomial at.

This is a huge deal for data availability systems, which are bottlenecked by opening time.

For some sample numbers, here are times opening/verifying degree 32768 - 1 polynomials using BLS12-381¹ on a single core of an M1 Macbook Pro:

This specification outlines implementation requirements for the polynomial multiproof (PMP) scheme. This builds on previous methods such as KZG10², and is derived entirely from BDFG21³. It should be seen as choosing a special case of BDFG21 which allows for significant optimizations that make the protocol more viable for use in applications like Data Availability.

The scheme consists of four methods:

1. Setup which sets up a structured reference string for the curve and does some
2. Commit which commits to a polynomial
3. M1Open/M2Open which computes a single opening proof that a set of polynomials are equal to specific values at a set of points
4. M1Verify/M2Verify which verify an opening proof against commitments and evaluations

API

The API is designed around two traits, the first looks roughly like

#![allow(unused)]
fn main() {
/// A curve-agnostic trait for a BDFG commitment scheme *without precomputation*
pub trait PolyMultiProofNoPrecomp<E: Pairing>: Sized {
    /// The output proof type
    type Proof: Clone;

    /// Creates a proof of the given polynomials and evals at the given points
    fn open(
        &self,
        transcript: &mut Transcript,
        evals: &[impl AsRef<[E::ScalarField]>],
        polys: &[impl AsRef<[E::ScalarField]>],
        points: &[E::ScalarField],
    ) -> Result<Self::Proof, Error>;

    /// Verifies a proof against the given set of commitments and points
    fn verify(
        &self,
        transcript: &mut Transcript,
        commits: &[Commitment<E>],
        points: &[E::ScalarField],
        evals: &[impl AsRef<[E::ScalarField]>],
        proof: &Self::Proof,
    ) -> Result<bool, Error>;
}
}

This takes a Merlin transcript for the Fiat-Shamir transform, some points $x_j$, some polynomials $f_i$ and the evaluations of each polynomial at each point $f_i(x_j)$.

This API is the most flexible, but not the most efficient.

The second trait is more efficient, but requires knowledge of which points are being opened to beforehand.

#![allow(unused)]
fn main() {
/// A curve-agnostic trait for a BDFG commitment scheme *with precomputation*
pub trait PolyMultiProof<E: Pairing>: Sized {
    /// The output proof type
    type Proof: Clone;

    /// Creates a of the given polynomials at the given point set index
    fn open(
        &self,
        transcript: &mut Transcript,
        evals: &[impl AsRef<[E::ScalarField]>],
        polys: &[impl AsRef<[E::ScalarField]>],
        point_set_index: usize,
    ) -> Result<Self::Proof, Error>;

    /// Verifies a proof against the given set of commitments and points
    fn verify(
        &self,
        transcript: &mut Transcript,
        commits: &[Commitment<E>],
        point_set_index: usize,
        evals: &[impl AsRef<[E::ScalarField]>],
        proof: &Self::Proof,
    ) -> Result<bool, Error>;
}
}

When creating this object, there will be some way to specify the points, or they will be predetermined by the implementation. The API is largely the same.

Applications to Data Availability

Data availability systems can benefit greatly from PMP, since polynomial commitment-based DA systems are tremendously constrained by opening time. Even with very fast KZG implementations, opening is too slow, and constrains the amount of data which can be processed through the system

Opening to a degree 255 BLS12-381 scalar field polynomial takes at best ~3-6ms, which means opening to every cell of 256 of those polynomials will take >200s.

Because PMP allows many cells to be opened to at once, the data availability grid can be chunked into a smaller grid, allowing for a faster, more secure system, with far higher througput ⁴. This allows polynomial commitment-based DA systems scale up in size without taking more compute.

Curve selection

The protocol depends on the selection of a pairing based curve. Attributes of an ideal curve for this protocol are, in order of importance,

1. Security
2. Fast G1 scalar multiplication
3. Large scalar field size
4. Fast G2 scalar multiplication
5. Small compressed G1 scalar size

BLS12-381 satisfies the first two critera well, and while other curves likely could satisfy more requirements, they are currently not as well audited. Hence BLS12-381 is a reasonable choice to start with.

The scheme given in BDFG21 is interactive, so Merlin transcripts are used to do the Fiat-Shamir transform.

Optimizations made from BDFG21 are outlined in Optimizations

2. Methods

Here we detail the Setup

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

1. Samples a random $x\in \mathbb{F},g_1\in {\mathbb{G}}_1,g_2\in {\mathbb{G}}_2$
2. Computes $(g_1,g_1^x,g_1^{x^2},\dots g_1^{x^{max\_coeffs-1}})$
3. Computes $(g_2,g_2^x,g_2^{x^2},\dots g_2^{x^{max\_coeffs-1}})$ ¹
4. 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\ne j}(X-z_l)}{{\prod }_{l\ne j}(z_j-z_l)}$$
     • If the denominator is zero due to a repeated point, setup errors
   • Constructs the vanishing polynomial $$Z_i(X)=\prod _j(X-z_j)$$
   • Computes ${\theta }_i=[Z_i(x){]}_2$

Commit

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$.

3. Method 1

This method biases towards a faster opening time, and requires roughly half the compute of FastVerify. See A. Optimizations for more details.

For the following, the notation of BDFG21 is followed, namely

• $[k]=\{1,\dots ,k\}$
• For a set of points $(x_1,\dots ,x_k)$ and a polynomial $f_i$, $r_i$ is the unique degree $k-1$ polynomial such that $\forall j{r}_i(x_j)=f_i(x_j)$

M1Open

#![allow(unused)]
fn main() {
M1Open(transcript: Transcript, 
       evals: Vec<Vec<Scalar>>, 
       polys: Vec<Polynomial>, 
       point_set_index: usize) -> Proof
}

Let the polynomials be $(f_1,\dots ,f_t)$ and the points be $(x_1,\dots x_k)$

1. Check that evals has length $t$ and each element of evals has length $k$
2. Transcribes the following to the Merlin transcript
   • each of the evals row by row with the utf-8 message open evals
   • each of the points in order with the utf-8 message open points
3. Constructs $\gamma \in \mathbb{F}$ by
   • Reading SCALAR_SIZE bytes from transcript with utf-8 message open gamma
   • Intepreting the bytes as an integer in big endian modded by the modulus of the scalar field
4. Computing $$f_{\mathtt{sum}}=\sum _{i\in [t]}{\gamma }^{i-1}{f}_i$$
5. Polynomial divide to get $q=f_{\mathtt{sum}}/Z_{point\_set\_index}$, discarding the remainer
6. Compute $[q(x){]}_1$ and serialize in compressed form.

M1Verify

#![allow(unused)]
fn main() {
M1Verify(transcript: Transcript, 
         commits: Vec<Commitment>, 
         evals: Vec<Vec<Scalar>>,
         proof: Proof,
         point_set_index: usize) -> bool
}

Let the evals be $((y_{1,1},\dots y_{1,k}),\dots (y_{t,1},\dots y_{t,k}))$, commits be $(c_1,\dots ,c_t)$, and the points be $(z_1,\dots z_k)$. Commit $c_i$ must be for the polynomial that evaluates to $(y_{i,1},\dots ,y_{i,k})$ at points $(z_1,\dots ,z_k)$.

This method

1. Checks that each element has the correct length
   • Commits has length $t$
   • Each element of evals has length $k$
2. Transcribes the points/evals the same as in the opening
3. Reads $\gamma$ same is in the opening
4. For each $j\in [k]$, computes $$a_j=\sum _{i\in [t]}{\gamma }^{j-1}{y}_{i,j}$$ $a_j$ represents the value of ${\sum }_{i\in [t]}{\gamma }^{i-1}{r}_i(z_j)$
5. Use the $a_j$ to interpolate $\varphi ={\sum }_{i\in [t]}{\gamma }^{i-1}{r}_i$ using the previously computed lagrange polynomials $l_{i,j}$ as $$\varphi =\sum _{i\in [t]}{\gamma }^{i-1}{r}_i=\sum _{j\in [k]}{a}_j{l}_{\text{point\_set\_index},j}$$
6. Compute $\alpha =[\varphi (x){]}_1$
7. Compute $\beta ={\sum }_{i\in [t]}{\gamma }^{i-1}{c}_i$
8. Return true if $$e(\beta -\alpha ,g_2)=e(\text{proof},{\theta }_{\text{point\_set\_index}})$$

4. Method 2

This method biases towards a faster verifying time, and is roughly twice as slow to open on. The API is exactly the same as in method 1. See A. Optimizations for more details.

M2Open

#![allow(unused)]
fn main() {
M2Open(transcript: Transcript, 
       evals: Vec<Vec<Scalar>>, 
       polys: Vec<Polynomial>, 
       point_set_index: usize) -> Proof
}

This method

1. Transcribes the following (all points serialized compressed if possible)
   • each of the evals row by row with the utf-8 message open evals
   • each of the points in order with the utf-8 message open points
2. Constructs $\gamma \in \mathbb{F}$ by
   • Reading SCALAR_SIZE bytes from transcript with utf-8 message open gamma
   • Intepreting the bytes as an integer in big endian modded by the modulus of the scalar field
3. Computing, for each polynomial $f_1,\dots ,f_t$ $$f_{\mathtt{sum}}=\sum _{i\in [t]}{\gamma }^{i-1}{f}_i$$
4. Polynomial divide to get $h=f_{\mathtt{sum}}/Z_{point\_set\_index}$, with remainder $v$.
5. Compute $W_1=[q(x){]}_1$
6. Serialize $W_1$ in compressed form and transcribe with the message open W1.
7. Construct $z$ in the same way as we did $\gamma$, reading with message open z.
8. Compute $s={\sum }_{i\in [t]}{\gamma }^{i-1}{r}_i(z)$ by computing $(Z_{\text{point\_set\_index}}\cdot v)(z)$. ¹
9. Comupute $f_z=-s+{\sum }_{i\in [t]}{f}_i$
10. Compute $l=f_z-h{Z}_{point\_set\_index}$
11. Compute $b=l/(X-z)$
12. Compute $W_2=[b(x){]}_1$
13. Return $(W_1,W_2)$ and serialize in compressed form

M2Verify

#![allow(unused)]
fn main() {
M2Verify(transcript: Transcript, 
         commits: Vec<Commitment>, 
         evals: Vec<Vec<Scalar>>,
         (w_1, w_2): Proof,
         point_set_index: usize) -> bool
}

Let the evals be $((y_{1,1},\dots y_{1,k}),\dots (y_{t,1},\dots y_{t,k}))$, commits be $(c_1,\dots ,c_t)$, and the points be $(z_1,\dots z_k)$. Commit $c_i$ must be for the polynomial that evaluates to $(y_{i,1},\dots ,y_{i,k})$ at points $(z_1,\dots ,z_k)$.

This method

1. Transcribes the points/evals the same as in the opening
2. Reads $\gamma$ same is in the opening
3. Transcribes $W_1$
4. Reads $z$ same is in opening
5. Lagrange interpolate $\varphi ={\sum }_{i\in [t]}{\gamma }^{i-1}{r}_i$ using the given evaluations, same as in method 1.
6. Compute $\alpha =g_1^{\varphi (z)}$
7. Compute $\beta ={\sum }_{i\in [t]}{\gamma }^{i-1}{c}_i$
8. Compute $F=\beta -\alpha -W_1^{Z_{\text{proof\_set\_index}}(z)}$
9. Compute $g_2^x{g}_2^{-z}=g_2^{x-z}$
10. Return true if $$e(F,g_2)=e(W_1,g_2^{x-z})$$

A. Optimizations

This contains all the optimizations made from the methods of BDFG21 and why they are correct. Please read the paper first 😘.

Method 1

This method is the fastest method for opening, and slightly slower for verification than Method 2. But, as written in the paper, verification is impractically slow for any appreciable number of polynomials/points. So here, we make an assumption to make the computation reasonable: each polynomial in $F=\{f_1,\dots ,f_N\}$ is opened at all the same points, that is (using the notation from the paper) $S_i=S_j=T\forall i,j\in [k]$. We also assume each polynomial $f_i$ is the same degree, $d$.

Method 1, Opening

Let $T=\{z_1,z_2,\dots z_t\}$. For brevity, assume sums over $i$ are done as ${\sum }_{i\in [k]}$

The prover has to compute, $[h(x){]}_1$, which means they must compute the coefficients of $h$ and then do $d+1-|T|$ ${\mathbb{G}}_1$ scalar multiplications and some addition. $h$ is defined as $$h(X):=\sum _i{\gamma }^{i-1}\frac{f_i(X)-r_i(X)}{Z_{S_i}(X)}=\frac{{\sum }_i{\gamma }^{i-1}\left(f_i(X)-r_i(X)\right)}{Z_T(X)}$$ Here, $r_i$ is the unique degree $|T|$ polynomial such that $r_i(z_j)=f_i(z_j)$. Note that polynomial fraction divides cleanly, because $f_i(z_j)-r_i(z_j)=0$ for all $j\in [t]$, meaning it has factors of $(X-z_j)$, and so does $Z_T(X)$.

The $r_i$ term is just the unique minimal degree polynomial you need to subtract from $f_i$ to allow $Z_T$ to cleanly divide it. But, this also means that $r_i$ is simply the remainder of dividing $f_i$ and $Z_T$. And the same applies for ${\sum }_i{\gamma }^{i-1}{f}_i$: ${\sum }_i{\gamma }^{i-1}{r}_i$ is just the remainder you get when you divide the sum of $f_i$s by $Z_T$! So all they need to do in order to compute $h$ is to

1. Compute ${\sum }_i{\gamma }^{i-1}{f}_i$
2. Use a polynomial division algorithm to divide by $Z_T$
3. Take the result and throw away the remainder

This makes opening very fast, because no interpolation is needed.

Method 1, Verification

For verification, the verifier needs to do a little more legwork than the prover. Let the commitment to the $i$-th polynomial be $c_i$

First, the verifier needs to compute $$Z_i:=[Z_{T\setminus S_i}(x){]}_2=[Z_{\varnothing }(x){]}_2=[1{]}_2=g_2$$ That's simple enough, now they have to compute $$\begin{array}{rl}F:& =\prod _{i}e({\gamma }^{i-1}(c_i[r_i(x){]}_1),Z_i)\\ & =e\left(\sum {\gamma }^{i-1}(c_i-[r_i(x){]}_1),g_2\right)\\ & =e\left(\sum {\gamma }^{i-1}{c}_i-{\left[\sum _i{\gamma }^{i-1}{r}_i(x)\right]}_1,g_2\right)\end{array}$$ Constraining the points lets them compute a single pairing instead of $k$! Now let's look at each side of pairing. To compute the LHS, they need to compute ${\sum }_i{\gamma }^{i-1}{r}_i$. Sadly, there's no nice way around this here, it must be interpolated, but they can interpolate ${\sum }_i{\gamma }^{i-1}{r}_i$ once rather than interpolate each $r_i$. That leaves us with

• $\sum {\gamma }^{i-1}{c}_i\to$ $N$ ${\mathbb{G}}_1$ scalar mults

• ${\left[{\sum }_i{\gamma }^{i-1}{r}_i(x)\right]}_1\to$ $|T|+1$ ${\mathbb{G}}_1$ scalar mults

Then all they're left with is the single pairing. Next they have to compute $e(W,[Z_T(x){]}_2)$. Computing $Z_T$ is pretty straightforward, and all they are left to do is the $d$ ${\mathbb{G}}_2$ scalar multiplications. If you already know your $T$ ahead of time, the $Z_T$ term can be cached.

This leaves us with the following amount of operations (other operations impact runtime fairly little)

Interestingly, the opening time gets smaller as the size of $T$ grows, due to the growing degree of the vanishing polynomial.

Method 2

Method 2 is an equally secure way to generate blocked openings, which biases computation slightly more to the opener than the verifer. They use the same assumptions as in Method 1.

Method2, Opening

The prover computes $h(X)=f(X)/Z_T(X)$ for $$f(X):=\sum _i{\gamma }^{i-1}{Z}_{T\setminus S_i}(X)(f_i(X)-r_i(X))=\sum _i{\gamma }^{i-1}(f_i(X)-r_i(X))$$ since $T\setminus S_i=\varnothing$ so $Z_{T\setminus S_i}=1$. This looks very familiar from method 1! Here they just compute $Z_T$ then compute the quotient $f/Z_T$ and for now, ignore the remainder. Then they compute $W:=[h(x){]}_1$. This is $\mathrm{deg}(h)+1=d-|T|+1$ ${\mathbb{G}}_1$ scalar multiplications.

This method has additional challenge other than $\gamma$, called $z$ which must take into account $W$. After seeing $W$, the verifier sends a $z\in \mathbb{F}$. In reality this should be abstracted away using a Fiat-Shamir transform.

The prover then computes $L(X):=f_z(X)-Z_T(z)h(X)$ for $$\begin{array}{rl}{f}_z(X):& =\sum _i{\gamma }^{i-1}{Z}_{T\setminus S_i}(z)(f_i(X)-r_i(z))\\ & =\sum _i{\gamma }^{i-1}{f}_i(X)-\sum _i{\gamma }^{i-1}{r}_i(z)\end{array}$$

Here we notice that we have already computed ${\sum }_i{\gamma }^{i-1}{r}_i(X)$ when we computed the remainder of $f/Z_T$. All they have to do is take this remainder, evaluate it at $z$, and then subtract it from ${\sum }_i{\gamma }^{i-1}{f}_i(X)$. They then evaluate $Z_T(z)$, compute $L(X):=f_z(X)-Z_T(z)h(X)$, then compute the polynomial $\frac{L(X)}{x-z}$ and evaluate $W^{\prime }:={\left[\frac{L(X)}{x-z}\right]}_1$.

Here, $L(X)$ is of degree $d$, so computing $W^{\prime }$ involves $d$ ${\mathbb{G}}_1$ scalar multiplications.

The proof then consists of $(W,W^{\prime })$.

Method 2, Verification

The verifier receives $W,W^{\prime }$, the commitments $c_i$, the evaluations of the $f_i$ at each $z_j\in T$ and computes $$\begin{array}{rl}F:& =-Z_T(z)W+\sum _i{\gamma }^{i-1}{Z}_{T\setminus S_i}(z)(c_i-[r_i(z){]}_1)\\ & =-Z_T(z)W+\sum _i{\gamma }^{i-1}(c_i-[r_i(z){]}_1)\\ & =-Z_T(z)W+\sum _i{\gamma }^{i-1}{c}_i-{\left[\sum _i{\gamma }^{i-1}{r}_i(z)\right]}_1)\end{array}$$ To do this, they do lagrange interpolation of ${\sum }_i{\gamma }^{i-1}{r}_i(X)$, evaluate it at $z$, then do the single ${\mathbb{G}}_1$ scalar multiplication. Computing ${\sum }_i{\gamma }^{i-1}{c}_i$ is $N$ ${\mathbb{G}}_1$ scalar multiplications, and one more for computing $-Z_T(z)W$. Next the verifier checks $e(F,g_2)=e(W^{\prime },[x-z{]}_2)$ Which involves 2 pairings, and 2 ${\mathbb{G}}_2$ scalar multiplications, yielding

Comparing the two methods, we get