Hobbit: Space-Efficient zkSNARK with Optimal Prover Time

Zero-knowledge succinct non-interactive arguments (zkSNARKs) are notorious for their large prover space requirements, which almost prohibits their use for really large instances. Space-efficient zk-SNARKs aim to address this by limiting the prover space usage, without critical sacrifices to its runtime. In this work, we introduce HOBBIT, the only existing space-efficient zkSNARK that achieves optimal prover time O(|C|) for an arithmetic circuit C. At the same time, HOBBIT is the first transparent and plausibly post-quantum secure construction of its kind. Moreover, our experimental evaluation shows that HOBBIT outperforms all prior general-purpose space-efficient zkSNARKs in the literature across four different applications (arbitrary arithmetic circuits, inference of pruned Multi-Layer Perceptron, batch AES128 evaluation, and select-and-aggregate SQL query) by ×8-×56 in terms or prover time while requiring up to ×23 less total space. At a technical level, we introduce two new building blocks that may be of independent interest: (i) the first sumcheck protocol for products of polynomials with optimal prover time in the streaming setting, and (ii) a novel multi-linear plausibly post-quantum polynomial commitment that outperforms all prior works in prover time (and can be tuned to work in a space-efficient manner). We build HOBBIT by combining the above with a modified version of HyperPlonk, providing an explicit routine to stream access to the circuit evaluation.