Recursion in Gen 1.0 and Gen 2.0 VMs

Most VMs for validity roll-ups today employ recursion as a means to accelerate proof computations. Recursions enable a parallel prover architecture, where a system of provers forms a binary tree, and each prover node computes proofs attesting to the correctness of the proofs generated by its children. The proof computed by the prover acting as the root node attests to the correctness of the proofs computed by all the leaf nodes. Such a recursive architecture affords massive parallelism but in a Gen 1.0 VM, is limited by the tradeoff between algebraic and non-algebraic hashes. The overheads to computing proofs corresponding to algebraic hashes in a Gen 1.0 VM are significantly lower but computing an algebraic hash like Poseidon on off-the-shelf hardware is at least 100x slower compared to computing a non-algebraic hash like Keccak. Since hash computations are such a central part of SNARKs, this reduces the overall proof computation times at each layer when employed using a Gen 1.0 VM. In the context of Gen 2 VM, such a recursive architecture can be effectively employed using a non-algebraic hash like Keccak, offering massive speed gains.