BrakingBase - A Linear Prover, Poly-Logarithmic Verifier, Field Agnostic Polynomial Commitment Scheme
摘要
We propose a Polynomial Commitment Scheme (PCS), called \(\textsf{BrakingBase}\) , which allows a prover to commit to multilinear (or univariate) polynomials with n coefficients in O(n) time. The evaluation protocol of \(\textsf{BrakingBase}\) operates with an O(n) time-complexity for the prover, while the verifier time-complexity and proof-complexity are \(O(\lambda \log ^2 n)\) , where \(\lambda \) is the security parameter. Notably, \(\textsf{BrakingBase}\) is field-agnostic, meaning it can be instantiated over any field of sufficiently large size. Additionally, \(\textsf{BrakingBase}\) can be combined with the Polynomial Interactive Oracle Proof (PIOP) from Spartan (Crypto 2020) to yield a Succinct Non-interactive ARgument of Knowledge (SNARK) with a linear-time prover, as well as poly-logarithmic complexity for both the verifier runtime and the proof size. We obtain our PCS by combining the Brakedown and Basefold PCS. The commitment protocol of \(\textsf{BrakingBase}\) is similar to that of Brakedown. The evaluation protocol of \(\textsf{BrakingBase}\) improves upon Brakedown’s verifier work by reducing it through multiple instances of the sum-check protocol. Basefold PCS is employed to commit to and later evaluate the multilinear extension (MLE) of the witnesses involved in the sum-check protocol at random points. This includes the MLE corresponding to the parity-check matrix of the linear-time encodable code used in Brakedown. We show that this matrix is sparse and use the Spark compiler from Spartan to evaluate its multilinear extension at a random point. We implement \(\textsf{BrakingBase}\) and compare its performance to Brakedown and Basefold over a 128 bit prime field.