Paper 2020/1536

Halo Infinite: Recursive zk-SNARKs from any Additive Polynomial Commitment Scheme

Dan Boneh and Justin Drake and Ben Fisch and Ariel Gabizon

Abstract

A polynomial commitment scheme (PCS) provides the ability to commit to a polynomial over a finite field and prove its evaluation at points. A succinct PCS has commitment and evaluation proof size sublinear in the degree of the polynomial. An efficient PCS has sublinear proof verification. Recently, it has been shown that any efficient and succinct PCS can be used to construct a SNARK with similar security and efficiency characteristics. We define an additive PCS to capture a ``homomorphic" property of commitments over a computational group $\mathbb{G}$ of bounded size. All existing examples of additive schemes (e.g., Bulletproofs, KZG, DARK, Dory) are also what we call $m$-spanning, meaning that commitments to the monomials of degree less than $m$ generate $\mathbb{G}$. Our first technical result is a black-box transformation of any $m$-spanning additive PCS into a hiding PCS with a zero-knowledge evaluation proof. Our second technical result is that every additive succinct PCS supports efficient proof aggregation. PCS proof aggregation reduces the task of proving evaluations of multiple commitments at multiple independent points to the task of proving the evaluation of a single ``aggregate" commitment at a single point. We present two flavors of aggregation: private and public. In private aggregation the prover has a private witness consisting of openings of the input commitments. In public aggregation, the prover/verifier share the same inputs, which includes non-interactive evaluation proofs for each input commitment. Our public aggregation protocol applies to any additive succinct PCS. Our private aggregation protocol applies more broadly to any succinct PCS that supports an efficient $\textit{linear combination scheme}$: a protocol for verifiably aggregating commitments into a new commitment to their linear combination. This includes non-additive schemes such as the post-quantum FRI-based PCS. We apply these results to the Halo proof carrying data (PCD) system. Halo was originally built using the Bulletproofs inner-product argument as the underlying PCS, and was recently generalized to work with the KZG PCS. We show that Halo can be instantiated with any PCS that supports efficient PCS aggregation, private or public. Thus, our results show that efficient (zero-knowledge) SNARKs and PCD can be constructed from any succinct PCS that has an efficient linear combination scheme, even if the PCS itself is inefficient. These results yield new Halo-like PCD systems from PCS constructions beyond Bulletproofs and KZG, including DARK, FRI, and Dory. The post-quantum Halo instantiation from FRI is particularly surprising as FRI is not additive.

Note: This paper expands on results in the manuscript https://eprint.iacr.org/2020/081.pdf and includes content from this prior manuscript in an appendix.