[Resource Topic] 2023/902: $\mathcal{S}\mathfrak{ublon}\mathcal{K}$: Sublinear Prover $\mathcal{P} \mathfrak{lon}\mathcal{K}$

Welcome to the resource topic for 2023/902

\mathcal{S}\mathfrak{ublon}\mathcal{K}: Sublinear Prover \mathcal{P} \mathfrak{lon}\mathcal{K}

Authors: Arka Rai Choudhuri, Sanjam Garg, Aarushi Goel, Sruthi Sekar, Rohit Sinha


We propose \mathcal{S}\mathfrak{ublon}\mathcal{K}- a new zero-knowledge succinct non-interactive argument of knowledge (zkSNARK). \mathcal{S}\mathfrak{ublon}\mathcal{K} builds on \mathcal{P}\mathfrak{lon}\mathcal{K} [EPRINT’19], a popular state-of-the-art practical zkSNARK. Our new construction preserves all the great features of \mathcal{P}\mathfrak{lon}\mathcal{K}, 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, \mathcal{S}\mathfrak{ublon}\mathcal{K} achieves improved prover running time over \mathcal{P}\mathfrak{lon}\mathcal{K}. In \mathcal{P}\mathfrak{lon}\mathcal{K}, the prover runtime grows with circuit size. Instead, in \mathcal{S}\mathfrak{ublon}\mathcal{K}, 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 \mathcal{S}\mathfrak{ublon}\mathcal{K} 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 \mathcal{P}\mathfrak{lon}\mathcal{K} involves proving a circuit of size n\cdot k code segments. In \mathcal{S}\mathfrak{ublon}\mathcal{K}, the prover costs are close to proving a \mathcal{P}\mathfrak{lon}\mathcal{K} 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}\ldots 2^{16}\}, the \mathcal{S}\mathfrak{ublon}\mathcal{K} prover is approximately 4.6\times faster than the \mathcal{P}\mathfrak{lon}\mathcal{K} prover. Proofs in \mathcal{S}\mathfrak{ublon}\mathcal{K} are 2.4KB, and can be verified in under 50ms.

ePrint: https://eprint.iacr.org/2023/902

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .