Nomos block validation must be as light and fast as possible to efficiently sync the chain and reduce the execution cost of Operations. Blocks contain Mantle Transactions whose validation complexity is primarily driven by the verification of Groth16 proofs and KZG proofs for samplings. This document proposes a batch verification method for these proofs, which drastically improves validation efficiency.
The main challenge is the computational cost of verifying each proof individually. A single Groth16 proof verification requires multiple pairing operations, which are computationally expensive. Similarly, KZG proof verification for each sample creates significant overhead, especially as the number of transactions in a block increases.
To speed up the verification process, we batch proofs using a common technique involving random linear combinations. This technique mirrors the approach used in the encoding protocol for DA, where one sample's proof is actually a random linear combination of proofs from the component chunks.
This batching method combines multiple proofs into a single verification operation. Rather than verifying n proofs individually (requiring n separate operations), we create a random linear combination of these proofs and verify them in one operation. This approach maintains security properties while dramatically reducing computational overhead.
Suppose we have a Groth16 circuit with a verification key:
$$ \left( [\alpha]_1,[\beta]_2,[\gamma]2, [\delta]2,\{\Psi_i\}{i=0}^{l} \subset \mathbb{G} 1
\right) $$
$l$ being the number of public inputs of the circuit. The verifier precomputes $e([\alpha]_1,[\beta]2)$ and stores it. The verification of one single Groth16 proof $(\pi_A,\pi_B,\pi_C)$ with public inputs $\{x_i\}{i=1}^{l}$ is done by (with $x_0 = 1$):
$$ e(\pi_A,\pi_B)=e([\alpha]_1,[\beta]2)+e\left( \Psi_0 +\Sigma{i=1}^{l} x_i\Psi_i,[\gamma]_2\right) + e(\pi_C,[\delta]_2) $$
This requires 3 pairings (because one can be precomputed) and $l$ scalar multiplications. The actual implementation uses the Miller Loop algorithm to compute the 4 pairings efficiently.
If we have $k$ proofs $\{\pi_A^{(i)},\pi_B^{(i)}, \pi_C^{(i)}\}{i=1}^k$ of the same circuit with public inputs $\{\{x_j^{(i)}\}{j=1}^{l_i}\}_{i=1}^k$, we can couple the verification through a random linear combination. First, we sample a random value $r \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{F}_p$. These combinations can be computed using MSM:
The verification is then nearly the same:
$$ \sum_{i=1}^k e(r^{i-1}\pi'_A,\pi'_B) = e(r'[\alpha]_1,[\beta]_2)+ e(IC,[\gamma]_2) + e(\pi'_C,[\delta]_2) $$
This approach drastically reduces the verification cost of multiple proofs. MSM provides even greater efficiency gains when dealing with a large number of public inputs. The pairing operation remains the most computationally expensive part of the process and can still use Miller loops.