Paper 2023/902
SublonK: Sublinear Prover PlonK
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)
- 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
-
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} }