# Prover

Vessel's application supports a range of operations that modify user information and current market status. During execution, the sequencer validates user operations and updates information accordingly, such as adjusting user balances or market liquidity. To ensure the sequencer's correctness, Vessel's prover represents the logic as a circuit and employs zk-SNARK technology.

## ZK-SNARK

ZK-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) is a cryptographic technique that ensures the integrity of circuit computation. It enables the service provider to generate a proof of the computation result, allowing the verifier to verify it with minimal computational resources.&#x20;

In Vessel's architecture, the operation logic is represented as a circuit, and the prover generates proofs of the circuit computation using the witnesses provided by the sequencer. These proofs are generated in parallel to maximize throughput but are committed and verified on-chain in the same logical order as the sequencer processes requests. Once the execution and state changes of a request are encapsulated in a SNARK proof and verified by the on-chain verifier, the request is considered finalized.

## Vessel Exchange Circuit

The Vessel exchange circuit functions as a state machine. It compresses the storage of user information and market status using a specialized type of Merkle tree to represent the application's state. At each step, the circuit selects an operation, such as a deposit request or a limit order match, validates the trigger condition, updates the storage, and generates the new state accordingly.

### Compressed Merkle Tree

To efficiently maintain the state and verify changes, key-value storage is encoded into a [Merkle Tree](https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/). The primary advantage of this structure is that the on-chain verifier only needs to store the tree root to represent the storage state, rather than the entire key-value table, to verify a proof's validity. This approach allows for recalculating the root for single-state updates with logarithmic costs.

Vessel’s storage is further optimized using a modified Merkle tree called the Compressed Merkle Tree (CMT). Unlike a "full binary tree" initialized with the entire index space, this tree gradually splits nodes and increases depth based on actual usage. This CMT structure significantly reduces resource consumption for proof generation by up to 10 times, given that the entire key space is 256-bit while the practical depth is typically around 20 levels.

## Proof Aggregation

Proof aggregation is a technique that consolidates multiple SNARK proofs into a single proof. Given hardware constraints and the gas consumption of on-chain verification, the capacity of a single SNARK proof cannot grow indefinitely. This necessitates the inclusion of proof aggregation mechanisms in the prover’s tech stack.

Proof aggregation offers several benefits:

* It reduces the gas consumption of the on-chain verifier by decreasing both the number and size of proofs.
* It allows smaller proofs to be computed in parallel on commodity hardware.

Proof aggregation is an active area of research, with techniques such as recursion and hybrid SNARK & STARK aggregation being explored. Vessel Lab continues to investigate enhanced aggregation schemes for practical applications.
