Nova/Supernova Parallelization
In Nova we have a folding property that given two instances of a relaxed rank one constraint system that we can combine them into a single instance of a relaxed rank one constraint system. In order to do so for a linear execution of a function $n$ times we first prove each instance of the $i$th proof. In the construction of the paper we use the folding property to prove them in a chain:
[ instance 0] -> [folded instance] -> [folded instance] -> ...
[instance 1] |||||||[instance 2]|||||||||||||| [instance 3]
In this case while we can compute the proofs which have not been folded in parallel this is not true of the folded proofs.
In order to fold in parallel we first compute the proofs of the base layer proofs along with their index of execution. Then we fold even and odd indices together, in this folding step we keep the start index of the first proof and the end index of the new proof. After the folding step we will have a proof that the function executed on steps between (left start index, right end index) was valid. In the final step we will have a nova proof that (0, n) were executed properly.