Complexity Comparison: zeromorph-fri vs. basefold Protocols

[wenjin1997]

Compare the complexity of the zeromorph-fri and basefold protocols, including prover complexity, proof size, and verifier complexity.

[wenjin1997]

You can find the detailed analysis document here.

zeromorph-fri

Analysis document: zeromorph-fri-analysis

Prover's Cost:

Proof size:

Verifier's Cost:

basefold

Analysis document: basefold-analysis

Prover's cost:

Proof size:

$$ ((2l + 3)d + \mathcal{R}) ~ \mathbb{F} + \left( \frac{l}{2} \cdot d^2 + \left(\frac{1}{2} \cdot l + \log \mathcal{R} \cdot l + 1\right) \cdot d \right) ~ H $$

Verifier's cost:

Compare

Conclusion: The basefold protocol is superior to the zeromorph-fri protocol in all aspects except for the verifier's finite field multiplication, where it is approximately $2N$ more than the zeromorph-fri protocol.