International Association
for Cryptologic Research

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.