search

a16z / jolt

The simplest and most extensible zkVM. Fast and fully open source from a16z crypto and friends. ⚡
https://jolt.a16zcrypto.com
MIT License
587 stars 106 forks source link

Optimize Eq Poly Construction during Grand Products #352

Closed sragss closed 1 month ago

sragss commented 2 months ago

During each layer of grand products we compute a progressively larger multilinear lagrange basis polynomial EqPolynomial_0(r_0), EqPolynomial_1(r_0, r_1), ... EqPolynomial_n(r_0, r_1, ... r_n).

The polynomial is computed fresh every time but can take as input the previous layer's EqPolynomial. EqPolynomial_n(EqPolynomial_{n-1}) to accelerate by O(n/2).

sragss commented 2 months ago

Looks like 50% of the largest layer's Eq evals is unsafe_alloc_zero_vec so probably not worth doing. Maybe worthwhile for Spartan's sumchecks.

moodlezoup commented 1 month ago

after discussion with Justin we decided that this is not actually possible