Paper 2026/2790

Vector Commit-and-Reduce Schemes

Abstract

Hash-based argument systems are seeing increasing adoption in practice, owing to their ease of deployment, fast provers, and plausible post-quantum security. However, they still lag behind elliptic-curve counterparts due to their large proof sizes and (comparatively more) expensive verifiers. Attempts to optimize these metrics have focused on one of the two ingredients underlying these arguments, namely Interactive Oracle Reductions, leaving the other ingredient, Vector Commitments (VC) schemes largely ignored. This is in part because Merkle trees are the best known hash-based VC scheme to date. To make progress on this front, we introduce Vector Commit-and-Reduce (VCR) schemes. These generalize VC schemes by allowing both the commitment and opening algorithms to be interactive protocols, and moreover by allowing the opening algorithm to be a reduction instead of an argument. By requiring VCR schemes to satisfy strong round-by-round knowledge soundness notions, we show how they can be used to construct hash-based reductions from IORs. Our transformation extends prior work which used (non-interactive) VC schemes. We also provide a construction of a VCR scheme, Canopy, that greatly reduces proof size and verifier time by reducing the vector opening claims to proximity claims about certain (committed) codewords. This latter feature enables us to use a wide variety of techniques for proving, batching, and accumulating these claims, and indeed we use these to obtain both concrete and asymptotic improvements for hash-based arguments and reductions. For SNARKs based on the Bolt code [CRYPTO 2026], we reduce proof sizes by 50\% and verifier hashes by $3\times$ with only a 5-15$\%$ prover overhead. For SNARKs based on the Reed-Solomon code, we reduce proof sizes by 20$\%$, and verifier hashes by $1.5\times$ with only a 20$\%$ prover overhead. We also construct hash-based Proof-Carrying Data where the recursion overhead is $O(\lambda \sqrt{\log N})$ hashes; in comparison, the state-of-the-art requires $\Omega(\lambda {\log N})$ hashes.