Paper 2023/902

SublonK: Sublinear Prover PlonK

Arka Rai Choudhuri, NTT Research
Sanjam Garg, University of California, Berkeley, NTT Research
Aarushi Goel, NTT Research
Sruthi Sekar, University of California, Berkeley
Rohit Sinha, Swirlds Labs.
Abstract

We propose SublonK - a new zero-knowledge succinct non-interactive argument of knowledge (zkSNARK). SublonK builds on PlonK [EPRINT'19], a popular state-of-the-art practical zkSNARK. Our new construction preserves all the great features of PlonK, i.e., it supports constant size proofs, constant time proof verification, a circuit-independent universal setup, as well as support for custom gates and lookup gates. Moreover, SublonK achieves improved prover running time over PlonK. In PlonK, the prover runtime grows with circuit size. Instead, in Sublonk, the prover runtime grows with the size of the "active part" of the circuit. For instance, consider circuits encoding conditional execution, where only a fraction of the circuit is exercised by the input. For such circuits, the prover runtime in SublonK grows only with the exercised execution path. As an example, consider the zkRollup circuit. This circuit involves executing one of n code segments k times. For this case, using PlonK involves proving a circuit of size n.k code segments. In SublonK, the prover costs are close to proving a PlonK proof for a circuit of size roughly k code segments. Concretely, based on our implementation, for parameter choices derived from rollup contracts on Ethereum, n = 8, k = {2^{10},...,2^{16}}, the SublonK prover is approximately 4.6 times faster than the PlonK prover. Proofs in SublonK are 2.4KB, and can be verified in under 50ms.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zkSNARKslookup protocolszkRollupsImplementation
Contact author(s)
arkarai choudhuri @ ntt-research com
sanjamg @ berkeley edu
aarushi goel @ ntt-research com
sruthi sekar1 @ gmail com
sinharo @ gmail com
History
2023-08-11: last of 2 revisions
2023-06-10: received
See all versions
Short URL
https://ia.cr/2023/902
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/902,
      author = {Arka Rai Choudhuri and Sanjam Garg and Aarushi Goel and Sruthi Sekar and Rohit Sinha},
      title = {{SublonK}: Sublinear Prover {PlonK}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/902},
      year = {2023},
      url = {https://eprint.iacr.org/2023/902}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.