# CIRCOM in zkProver

Although CIRCOM is mainly used to convert a STARK proof into its respective Arithmetic circuit, it is implemented in varied ways within the zkProver, specifically during the STARK recursion process.

Info

This document gives further elaboration on the Proving architecture by focusing on the CIRCOM Arithmetic circuits, while highlighting CIRCOM’s pivotal role in the STARK Recursion process.

## zkEVM batch prover¶

The first step in proving computational integrity starts with the zkEVM batch prover.

It is a circuit that proves correctness of the state transition from an *oldStateRoot* to a *newStateRoot*.

The zkEVM batch prover takes as inputs; the *oldStateRoot*, *oldAccInputHash*, *oldBatchNum*, *chainID* and *forkID*. And its outputs are; the *newStateRoot*, *newAccInputHash*, *localExitRoot*, and *newBatchNum*,

The *localExitRoot* is the Merkle root of the *ExitTree* used in the bridge to transfer information from the L2 to the Ethereum L1.

The *oldBatchNum* indicates which batch is being processed, and in each transition the numbering increments by \(1\), such that *newBatchNum = oldBatchNum + 1*.

All transactions being processed are encoded into the batch via the *oldAccInputHash*, read “old accumulated input hash”.

Although built in a smart contract, the encoding of transactions resembles a blockchain, where transactions are chained together with the Keccak hash function. See figure below depicting this encoding.

The main idea, when proving validity of a batch, is for the *oldAccInputHash* and its corresponding *newAccInputHash* to match accordingly.

The resultant STARK proof denoted by \(\mathtt{\pi_{batch}}\), which involves \(669\) committed polynomials each of degree \(2^{23}\), is \(1.9\) Megabytes big.

Such a validity proof is not ideal in view of its storage cost in Ethereum.

The Polygon zkEVM’s strategy to reducing the size of the ultimate validity proof is by implementing a recursive aggregation of many batch proofs into one.

## CIRCOM circuits¶

As outlined in the Proving architecture subsection, the recursive aggregation of many STARK proofs (aimed at reducing the size of the validity proof) is accomplished in five stages;

- Compression stage using the
*c12a*CIRCOM circuit, - Normalization stage using the \(\mathtt{recursive_1}\ \mathtt{prover}\) CIRCOM template,
- Aggregation stage using the \(\mathtt{recursive_2}\ \mathtt{prover}\) CIRCOM template,
- Final stage using the \(\mathtt{recursive_f}\ \mathtt{prover}\) CIRCOM template,
- SNARK stage using the \(\mathtt{final}\ \mathtt{prover}\) CIRCOM template.

In terms of code, the three CIRCOM templates used in the middle stages (Normalization stage, Aggregation stage and Final stage) are identical except for their public inputs which are; the root constants *RootC* and the respective input proofs.

As previously mentioned,

- The \(\mathtt{recursive_1}\ \mathtt{prover}\) only takes \(\mathtt{\pi_{\texttt{c12a}}}\)-type proofs as input,
- The \(\mathtt{recursive_2}\ \mathtt{prover}\) only takes any pair of \(\mathtt{\pi_{\texttt{rec1}}}\)-type or \(\mathtt{\pi_{\texttt{rec2}}}\)-type proofs as input,
- The \(\mathtt{recursive_f}\ \mathtt{prover}\) only takes a pair of \(\mathtt{\pi_{\texttt{rec2}}}\)-type proofs as input.

Since the underlying proof scheme is PIL-STARK, there is a built-in \(\mathtt{Verifier}\) CIRCOM circuit in each of these prover circuits. Therefore, for any index \(\mathtt{x} \in \{1,2,f\}\), the proof \(\mathtt{\pi_{x}}\) output by any of the \(\mathtt{recursive_x}\ \mathtt{provers}\), is in fact a verified proof because PIL-STARK automatically verifies it.

A typical \(\mathtt{recursive_x}\ \mathtt{verifier}\) CIRCOM template, for any \(\texttt{x} \in \{1, 2, f\}\), looks like the circuit shown below.

## Proof-size reductions¶

The below table displays \(\text{4}:\text{1}\) reduction in proof sizes as one progresses from one stage of the STARK recursion to the next.

The numbers presented below were first publicised by the Polygon zkEVM Technical Lead, Jordi Baylina, during the StarkWare Sessions held in February 2023. The video recording can be found here.