Univariate KZG multiproofs (in eval form)

[ggutoski]

We're currently missing the ability to make multiproofs (aka batch proofs). Specifically, given a list $(x_1,y_1),\dots,(x_k,y_k)$ of input-output pairs and a polynomial $p$ we want a single succinct proof that simultaneously proves $p(x_i)=y_i$ for all $i=1,\dots,k$.

The algo appears in Section 3.5 of the original KZG paper and also in the "multiproofs" section of Dankrad's blog post

We need support for this in evaluation form. See #339 .

What we have:

• multi-open: open a single polynomial at n points, giving n proofs.
• batch-open: open n polynomials, each at 1 point, giving n proofs. (Current implementation is naive: just call open n times.)

What we need:

• multiproof: open a single polynomial at n points, giving 1 proof.

More detail

• Computing the interpolation polynomial $I(x)$ is easy in eval form: it's just a naive MSM of group elements from the KZG setup.
• Computing the zero polynomial $Z(x)$ is harder. There's an easy quadratic-time algorithm. But if you want something sub-quadratic (quasi-linear, like n polylog(n)) then you can use this algorithm.

[chancharles92]

@ggutoski The state-of-the-art is Appendix C.4 of https://eprint.iacr.org/2020/1536.pdf (which might be similar to the above references you had)

What's the context of this feature? Do we usually need n (i.e. the number of eval points) to be large? E.g., the above paper assumes that the number of eval points is relatively small (e.g., <100), thus the computation of the zero polynomial Z_T(X) is not a bottleneck.

[ggutoski]

Thanks @chancharles92 . Context: we need this to provide a light-client proof for an individual tx. Tx bytes are encoded into field elements, which are viewed as output points of a polynomial. If a tx is large then the number of eval points is large. I don't know what to expect on average but if we get rickrolled with a multi-megabyte tx then yes we need to support large n.

[chancharles92]

Thanks @chancharles92 . Context: we need this to provide a light-client proof for an individual tx. Tx bytes are encoded into field elements, which are viewed as output points of a polynomial. If a tx is large then the number of eval points is large. I don't know what to expect on average but if we get rickrolled with a multi-megabyte tx then yes we need to support large n.

In this application, is it the case that the set of evaluation points can be chosen by ourselves? Seems that the tx bytes are only the evaluation values. If so, we can choose the set of points as roots-of-unities, and the zero polynomial Z_T(X) can be much easier to compute. Or did I miss anything?

[ggutoski]

You are correct that the input points can be roots-of-unity. But in general the zero polynomial Z_T(X) is only over a subset of these roots-of-unity, so there's still nontrivial work here. The best algorithm I know to compute Z_T(X) over a subset of roots-of-unity is Vitalik's proposal mentioned above. ([link] search for "Calculating Z in $O(n*log^2(n))$ time".) Do you know of anything better?

Note that we have an extra guarantee: we know that the subset of roots-of-unity is contiguous. ie. $r_i,\dots,r_{i+k}$. Perhaps there's a trick to exploit this guarantee for improved perf. That said, such a question is low priority and any additional benefit might be negligible.

[chancharles92]

You are correct that the input points can be roots-of-unity. But in general the zero polynomial Z_T(X) is only over a subset of these roots-of-unity, so there's still nontrivial work here. The best algorithm I know to compute Z_T(X) over a subset of roots-of-unity is Vitalik's proposal mentioned above. ([link] search for "Calculating Z in O(n∗log2(n)) time".) Do you know of anything better?

That makes sense. Thanks. I think the O(nlog^2n) algorithm is fine. Basically, we need to compute the poly (X-a1)(X-a2)...(X-an), we can recursively compute the polys (X-a1)...(X-a_{n/2}) and (X-a_{n/2+1})...(X-an), and then do a poly multiplication using FFTs. The implementation should be easy.

[chancharles92]

@ggutoski @jbearer
There is a simple approach to optimize the complexity to O(nlogn).
Recall our goal is to prove f(i) = yi for i = L+1, ..., L+m.
This reduces to prove the polynomial relation:
f(X) - r(X) = H(X) * (X-L-1) * ... * (X-L-m), where r(X) is the deg-(m-1) polynomial s.t. r(i) = yi for i = L+1, ..., L+m.

The bottleneck before is to compute the polynomial $Z_{L,m} := (X-L-1) .... (X-L-m)$, which has complexity O(m*log^2(m)). But what we can do is preprocess the polynomials:
$Z_{0, 0} = 1$,
$Z_{0, 1} = (X-1)$, ...,
$Z_{0,i} = Z_{0, i-1} * (X-i)$, ...,
$Z_{0, 1000} = Z_{0,999} * (X-1000) = (X-1)...(X-1000)$,
which can be done in time $O(1000^2)$.
Similarly, we can preprocess $Z_{i * 1000, j}$ where $0 \le j \le 1000$ and $i=0,1,2,...$

Assume $m \le 1000$ for simplicity (we can also handle the more general case with a few tricks), then $Z_{L,m}$ can be computed by a single polynomial division (that has complexity O(mlogm)):
$Z_{L,m} = Z_{i \cdot 1000, t+m} / Z_{i \cdot 1000, t}$ where $L = i * 1000 + t$ and $1000 i \le L &lt; 1000 \cdot (i+1)$.
(It is possible that [L+1,..., L+m] goes across two intervals (i.e., L+m > 1000(i+1)), but it can still be easily handled by adding one more poly multiplication)

Though the set of preprocessed polynomials Zs are quite a lot, they can be global public parameters that are independent of the data. So we can assume that they were computed before the start of the system and the prover can query those from a database or a local file system.

[chancharles92]

• Computing the interpolation polynomial $I(x)$ is easy in eval form: it's just a naive MSM of group elements from the KZG setup.

@ggutoski Is it the case only if the evaluation points are roots-of-unities rather than arbitrary points? In that case, shall we just restrict the evaluation points to be roots-of-unities?
Also do we already have the API for generating SRS $g^{Li(s)}$ (where Li is the ith Lagrange polynomial) in the code?

[ggutoski]

@ggutoski Is it the case only if the evaluation points are roots-of-unities rather than arbitrary points? In that case, shall we just restrict the evaluation points to be roots-of-unities?

I can't remember what I was thinking when I wrote that, and perhaps I was mistaken. I think you are correct: it's "easy" only when the points are roots of unity. In that case, I agree we should restrict eval points to roots of unity.

I think when I wrote "easy MSM" I was referring only to the verifier's task of computing $[I(s)]$.

Also do we already have the API for generating SRS $gLi(s)$ (where Li is the ith Lagrange polynomial) in the code?

I believe the answer is no. This is a one-time computation that is done in the trusted setup. Alex posted today about loading an external SRS---if that SRS already has the setup in eval form then there's nothing left to do. But I haven't investigated.

[alxiong]

if that SRS already has the setup in eval form then there's nothing left to do. But I haven't investigated.

no, Aztec's KZG ceremony is done over the coeff form, not eval form. @ggutoski