Recursion

Having proven the correctness of the $k$ individual shards, we now have $k$ proofs, one for each shard. To reduce the proof-size as well as the verification time, we employ recursion. In a nutshell the idea is use a proof-system to prove the correctness of some small number of shards proofs.

We refer to the original RISC V shards as core shards. Each core shard may have a different "shape", namely contains a different set of tables, we first apply a "normalization" step. The normalize step is a proof-system that proves the correctness of the verification of each core shard, but uses a single uniform shape.

Now, given the $k$ normalized shard proofs, we start to compress them. This is done by a separate "compress" proof-system that take a small (typically 3-4) of shards and proves them jointly, thereby drastically reducing the proof-size and verification time. This is done in a tree like manner until we reach a single "compressed" proof.

The normalize and compress step both utilize a proof-system that is very similar to the core Hypercube proof-system, except that it is circuit based and so only requires a read-only memory argument.

For applications that do not require very short proofs, this concludes the proof-system.

For other applications (e.g., which require on-chain verification) the compressed proof is fed into a Groth16 based proof-system. To do so, first the compressed proof is first fed into another proof-system referred to as "shrink". The goal of this proof-system is to replace the Koalabear field over which the hash function (Poseidon2) is performed, with a field that is compatible with Groth16. After this switch we finally compose with the Groth16 proof-system.