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 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.
Funding Information
  • Institute of Information and Communications Technology Planning and Evaluation
  • Korean Government [Ministry of Science and ICT (MSIT)] (RS-2021-II210727 (90%))
  • Culture, Sports and Tourism Research and Development Program through Korea Creative Content Agency
  • Ministry of Culture, Sports and Tourism (RS-2024-00332210 (10%))