Polymath: Groth16 Is Not The Limit

Helger Lipmaa

Paper 2024/916

Polymath: Groth16 Is Not The Limit

Helger Lipmaa

, University of Tartu

Abstract

Shortening the argument (three group elements or 1536 / 3072 bits over the BLS12-381/BLS24-509 curves) of the Groth16 zk-SNARK for R1CS is a long-standing open problem. We propose a zk-SNARK Polymath for the Square Arithmetic Programming constraint system using the KZG polynomial commitment scheme. Polymath has a shorter argument (1408 / 1792 bits over the same curves) than Groth16. At 192-bit security, Polymath's argument is nearly half the size, making it highly competitive for high-security future applications. Notably, we handle public inputs in a simple way. We optimized Polymath's prover through an exhaustive parameter search. Polymath's prover does not output $\mathbb{G}_{2}$ elements, aiding in batch verification, SNARK aggregation, and recursion. Polymath's properties make it highly suitable to be the final SNARK in SNARK compositions.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in CRYPTO 2024
Keywords: Batch verification Groth16 KZG polynomial commitment SAP zk-SNARK
Contact author(s): helger lipmaa @ gmail com
History: 2024-06-10: approved; 2024-06-08: received; See all versions
Short URL: https://ia.cr/2024/916
License: CC BY

BibTeX

@misc{cryptoeprint:2024/916,
      author = {Helger Lipmaa},
      title = {Polymath: Groth16 Is Not The Limit},
      howpublished = {Cryptology ePrint Archive, Paper 2024/916},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/916}},
      url = {https://eprint.iacr.org/2024/916}
}