DeepFold: Efficient Multilinear Polynomial Commitment from Reed-Solomon Code and Its Application to Zero-knowledge Proofs

This work presents DeepFold, a novel multilinear polynomial commitment scheme (PCS) based on Reed-Solomon code that offers optimal prover time and a more concise proof size. For the first time, DeepFold adapts the FRI-based multilinear PCS to the list decoding radius setting, requiring significantly fewer query repetitions and thereby achieving a 3× reduction in proof size compared to BaseFold (Crypto'24), while preserving its advantages in prover time. Compared with PolyFRIM (USENIX Security'24), DeepFold achieves a 2× improvement in prover time, verifier time, and proof size. Another contribution of this work is a batch evaluation scheme, which enables the FRI-based multilinear PCS to handle polynomials whose size is not a power of two more efficiently. Our scheme has broad applications in zk-SNARKs, since PCS is a key component in modern zk-SNARK constructions. For example, when replacing the PCS component of Virgo (S&P'20) with DeepFold, our scheme achieves a 2.5× faster prover time when proving the knowledge of a Merkle tree with 256 leaves, while maintaining the similar proof size. When replacing the PCS component of HyperPlonk (Eurocrypt'23) with DeepFold, our scheme has about 3.6× faster prover time. Additionally, when applying our arbitrary length input commitment to verifiable matrix multiplications for matrices of size 1200 × 768 and 768 × 2304, which are actual use cases in GPT-2 model, the performance showcases a 2.4× reduction in prover time compared to previous approaches. To prove ሚ 𝑓 𝑧 1 , ⋯ , 𝑧 𝜇 , ሚ 𝑓 𝛼 0 , 𝛼 0 2 , ⋯ , 𝛼 0 2 𝜇-1