aPlonk: Aggregated Plonk

Introduction to aPlonk

ZKPs are helpful for applications such as blockchain rollup and zkEVM, which aim to improve the scalability and privacy of blockchain transactions. However, one of the most critical challenges is the Prover complexity (i.e., 𝑂(𝑛𝑙𝑜𝑔𝑛)). For security and scalability purposes, we are interested in schemes that can aggregate proofs of any circuits into one. Namely, 𝑛 provers with 𝑛 statements can create proofs that can be aggregated into one single proof. This is particularly useful in scenarios where many computations need to be performed and proven, such as blockchains, where many transactions need validation.

The first aggregated proposal is SnarkPack, which uses Groth16 (the first presented zkSNARK construction verifying the correctness of computations without revealing any details about them). However, it is unsuitable for applications needing universal zkSNARKs, such as blockchain execution layers. In other words, in SnarkPack, one can combine n proofs into one where the circuit has to be the same for all because Groth16 is not universal.

aPlonK is a variant of PlonK that is universal and a type of ZKP system. aPlonk is mainly SnarkPack for Plonk but supports aggregation of proofs of multi statements simultaneously. This is done by constructing a single polynomial that combines multiple polynomials used in different computations (i.e., different circuits), and then using this polynomial to generate the succinct proof. Furthermore, the main advantage of aPlonK is that it can aggregate multiple proofs into one, reducing the size and verification time of the proofs, in particular, combining 𝑛 proofs into one single aggregated proof of 𝑂(log 𝑛) size and also 𝑂(log 𝑛) verification time. Hence, the resulting proof is much smaller and more efficient than generating individual proofs for each computation. The verification is also quite cheap compared to the others, making it a valuable tool in Layer 2s.

The fundamental approach involves validating multiple proofs of different circuits by evaluating a random linear combination of polynomial commitments and the FFT algorithm. Here below, we first present the Group Commitment Scheme, which is the main ingredient of SnarkPack, and the KZG-based multi-linear polynomial commitment scheme, which is the main ingredient of aPlonk, discuss how they are utilized in aPlonk to enhance the performance significantly.