zkFold / zkfold-base

ZkFold's Base library
https://zkfold.io
MIT License
17 stars 7 forks source link

Improve performance of the polynomial multiplication property test #298

Open TurtlePU opened 1 month ago

TurtlePU commented 1 month ago

Currently, one of the slowest tests in our test suite is the test of correctness of FFT polynomial multiplication:

propMultiplication (p1, p2) = p1 * p2 == p1 `naive` p2

This runs slowly because the naive part runs in $O(|p_1| |p_2|)$. I suggest changing it to:

propMultiplication p q x = evalPoly (p * q) x == evalPoly p x * evalPoly q x

Pros:

  1. The property is more natural: it checks that multiplication of polynomials works like a pointwise multiplication of evaluation functions;
  2. Testing this property is $O(n\log n)$, which is optimal.

Cons:

  1. Before, it was deterministic equality testing of random polynomials; now it's probabilistic equality testing of random polynomials.