Welcome to the resource topic for 2023/902
Title:
\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
Abstract: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 .