Paper 2024/616 Original: eprint.iacr.org/2024/616 ↗

$\mathsf{Cougar}$: Cubic Root Verifier Inner Product Argument under Discrete Logarithm Assumption

Abstract

An inner product argument (IPA) is a cryptographic proof system that serves as a fundamental building block for various applications, such as zero knowledge proofs and verifiable computation. Bulletproofs (IEEE S&P 2018), a well-known IPA under the discrete logarithm (DL) assumption, features a short, logarithmically-sized proof, making it suitable for blockchain applications. However, its major drawback is the linear verifier cost ($O(N)$), which presents a significant bottleneck in settings like verifiable computation. To address this, recent advancements have successfully reduced the verification complexity to square-root order ($O(\sqrt{N})$) under the same assumption (e.g., Asiacrypt 2022, IEEE TIFS). In this work, we propose $\textsf{Cougar}$, a novel IPA that breaks this square-root barrier to achieve an unprecedented cubic-root verifier complexity ($O(\sqrt[3]{N})$)}, while strictly maintaining the compact logarithmic proof size ($O(\log N)$) characteristic of Bulletproofs. To achieve this, $\textsf{Cougar}$ introduces a generalized two-tier commitment framework combined with a \textit{disjoint interpolation} strategy for efficient consistency checks. We implemented $\textsf{Cougar}$ in Rust and performed a comprehensive benchmarking against Bulletproofs and $\textsf{Leopard}$ (IEEE TIFS). Our evaluation demonstrates that while $\textsf{Cougar}$ incurs a moderate increase in prover overhead, its verification time scales significantly better for large instances. Concretely, for a witness size of $N = 2^{20}$, $\textsf{Cougar}$ achieves a $50\times$ verification speed-up over Bulletproofs and exhibits a superior asymptotic growth rate compared to existing sublinear IPAs.