fflonK: a Fast-Fourier inspired verifier efficient version of PlonK
1. 引言
为Aztec团队2021年11月论文《fflonK: a Fast-Fourier inspired verifier efficient version of PlonK》，视频分享见：fflonk: a Fast-Fourier inspired verifier efficient version of PlonK [Ariel Gabizon, Aztec]，slide见：fflonk：cheaply opening many polynomials using the fast-fourier equation。
fflonk为KZG多项式承诺（[KZG10]）的变种，其设计初衷为节约以太坊上的gas费。当对ddd个多项式open point为ddd’th power 时，Verifier所需的group运算与ddd无关。fflonk将 “open multiple polynomials at a single point xxx” 通过 “类似FFT identity的方法” reduce为 “opening a single polynomial at many points”。本文展示了某Plonk应用，大幅改进了Verifier性能，代价是将Prover time提高为约3倍。除2次pairing运算之外，fflonk的Verifier仅需要执行5次scalar multiplication运算，而不是Plonk论文中的16或18次scalar multiplication运算。
多项式承诺方案（PCS）已成为近期构建的succinct arguments（SNARKs）的核心组件，根据某具有上限degree的固定多项式，“force” Prover 答复 Verifier 查询请求。
对于以太坊上的类似zk-rollups应用来说，精确评估验证zk-SNARK proof的gas开销 将直观重要。链上验证proof的开销可进一步简化为，PCS “open”流程的验证开销。在“open”流程中，Verifier在已知直接Prover给的多项式承诺值的前提下，可验证Prover给的evaluations的正确性。本文，在open多个多项式承诺的情况下，可降低Verifier开销。