Titan: Efficient Polynomial Commitments from IOPs over Groups

In this paper, we proposeTitan, an efficient polynomial commitment scheme (PCS) with transparent setup. It achieves commitment time of $0(n)$, evaluation time of$O(\sqrt{n})$ while the proof size and verification scales as $O(\sqrt[4]{n})$. Titanfeatures an order of magnitude smaller proof sizes than hash based PCS, while featuring a significantly more efficient prover and verifier com- pared to state of the art group based schemes like Dory and Hyrax. To achieve this balance,Titan borrows two-tiered commitments from Dory, and realizes outer commitment using interactive protocols of proximity (IOPP) over groups, such as Basefold and WHIR, instead of expensive bi- linear pairings. This allowsTitanto be instantiated over general curves with discrete-log hard- ness such as Pasta Curves, instead of requiring pairing friendly curves. We compile a variant of Spartan protocol for R1CS withTitanPCS to realize a new SNARK, which we callTitanSnark. Our constructionTitanSnarkpreserves the prover efficiency of the existing Spartan protocol, while improving proof size and verification quadratically from $O(\sqrt{n})$ to $O(\sqrt[4]{n})$. Concretely, for circuits of size $\geq 2^{22}$ this results in around 3×more efficient proof size and verification. Our blueprint of combining IOPPs over groups with Pedersen style inner commitments is of independent interest, as are several optimizations towards efficiently realizing WHIR IOPP over prime-order groups.