Cairo Continuations
TL;DR: This is a deep technical post. Here’s a gist. Generating a zero-knowledge proof for a large computation is expensive: it demands enormous memory and time from a single machine. Continuations solve this by splitting one long execution into sequential chunks, proving each chunk independently on separate machines in parallel, and then aggregating those proofs back into a single one. The tricky part is guaranteeing that the chunks connect: that where one left off is exactly where the next picked up, with no gaps or contradictions. Think of it like a relay race where each runner covers one leg, but you also need cryptographic proof that every baton handoff was clean. This is how Herodotus in collaboration with StarkWare enables proving at scale: what once required a single massive machine can now be distributed across many smaller ones, paving the way for cutting both cost and latency.
Introduction
Continuation is a feature we see in most zkVMs, but what is it exactly? It refers to the mechanism of soundly splitting proof generation into independent processes. Therefore, not only does continuation build N separate shards, but it also provides a way to soundly stitch these N proofs into a single one through aggregation.
Simply put, a zkVM enforces constraints on the transition from one VM state to another, a state being the combination of both a set of registers (pc, fp, ap for Cairo 1) and a memory M. Continuation splits the execution into N continuous segment Sᵢ . Proving each of these segments independently guarantees that for all i the transition from the initial to the final state of Sᵢ is valid. The main challenge behind continuation is proving that the final state of Sᵢ is the initial state of Sᵢ+₁ .
An E2E proving flow with continuation
Let’s go through an end-to-end proving flow of a Cairo program using Stwo-Cairo featuring continuation.
- Run Cairo Program: As with any regular proof generation, we start by running the Cairo program on the executor, and we fetch the output made up of both the VM’s step log (i.e. the trace) and the full relocated memory.
- Trace splitting: Then the trace is split into N continuous traces (Chunk #1, Chunk #2, etc. on the diagram). Each trace chunk is mapped to the corresponding portion of used memory. As opposed to the trace chunks, the memory chunks can overlap. For instance, step 0 in chunk #1 could read at address 3 and step 74 of chunk #2 could read the same cell (see overlap on the diagram below).
- Independently prove each shard (trace chunk and its associated memory): As mentioned in the introduction, this guarantees that each chunk respects the Cairo rules as a sequence of legal state transitions.
- Aggregate the proofs: The prover needs to add some proving logic in order to prove that the N proofs refer to a unique program execution with a continuous state evolution. Concretely, this implies:
- checking that the final registers (pc, fp, ap) of shard i are identical to the initial ones of shard i+1;
- checking that, for all i the memory of shard i does not conflict with the memory of shard j with j≠i. In other words, checking that the memory is not different from one shard to another and that it is consistent over all chunks.
To prove memory consistency, zkVMs commit to the memory. The most common way of doing so is by building a Merkle tree from the boundary memory states. This means that the prover has a chip to build a Merkle tree for both the initial and final memory (each leaf is typically a memory cell). The memory commitment is then part of the zkVM’s AIR and is challenge-independent, as only the roots are made public. It is easy for the verifier to check that the final root of shard i coincides with the initial root of shard i+1. This method is well suited for read-write memories (RWM) as it keeps the number of leaves bounded. On a read-only memory (ROM), however, such a commitment is made impossible in practice as memory sizes grow much faster than for read-write memories.
Concretely, proving fibonacci(n) on a RWM produces a memory containing the program and a small frame for the fibonacci computation (the content of this frame is overwritten at each fibonacci iteration bounding its length). This yields a memory commitment in O(1). On the other hand, for ROMs, frames cannot be overwritten so they get piled up, growing the size of the memory proportionally to n, making the commitment costly: O(n).
Why continuation makes a difference
Decrease memory requirements
Proving large programs (i.e. billion-step-long traces) requires a lot of memory on the prover side — sometimes hundreds of gigabytes of RAM. Continuation addresses this problem, as the sub-traces fed into the prover have their sizes bounded by the maximum number of steps allowed per segment.
Get Herodotus’s stories in your inbox
Join Medium for free to get updates from this writer.
This means that proving a large program can be done without hitting hardware constraints. In practice, this allows us to compute proofs on smaller instances, and, in cloud environments, it makes horizontal scaling straightforward, thus reducing costs.
Parallelize proof generation
Another benefit of continuation is that each chunk can be proven independently, enabling parallel proof generation. Since the trace chunks are built as a continuous succession of states that conform to the Cairo transition rules, multiple instances can work on different shards simultaneously without interference.
For large programs, the setup overhead (preprocessed column commitments, twiddle computation, etc.) is negligible compared to the proof generation cost, so there is an overall latency improvement with parallelization. This performance boost also comes from the Stwo design, which works best in a certain configuration.
Use Stwo at its best
Say that we have an AIR constraining a large trace represented by a simple table of 2^log_size rows and N_CELLS/2^log_size columns. Then benchmarks reveal that the parameter log_size matters. In other words, the shape of the trace matters to get the best proving frequency (number of cells proven per second). Take, for example a 500M-cell trace, it turns out that reshaping the trace from (N_CELLS/2¹⁷, 2¹⁷) to (N_CELLS/2²⁰, 2²⁰) (i.e. making it 8 times longer and 8 times narrower) leads to a 60% frequency boost!
So how can we leverage continuation to benefit from this performance increase? Although a Cairo 1 trace is actually ~60 smaller traces (each with a static number of columns and a program-dependent number of rows), the same applies: by tweaking the number of clock cycles per continuation chunk, we can target a trace shape that is closer to optimal and benefit from the performance boost.
Insights on aggregation
Continuation refers to the process of splitting the trace and provides a design that enables a sound stitching of two proofs. There are, however, multiple ways of gluing the resulting N proofs together. But firstly, what is “proof aggregation”? A proof aggregator is a program that takes two or more sub-proofs — that is, proofs corresponding to a single program execution — and that outputs a single proof such that verifying this proof validates the correct execution of the initial program. There are two main ways of performing aggregation: linear and recursive aggregation. Both methods imply proving the execution of a verifier.
Linear Aggregation
The naïve and easier way of aggregating proofs is linear aggregation. For this method, the aggregator takes the N sub-proofs once they are all issued by the provers and it generates a proof for the following claim: “the N sub-proofs are valid and form a continuous chain of VM states”. In this method, all proofs are verified with a single program typically written in a provable language so that it can itself be verified. The main benefit from this approach is its simplicity but it requires waiting for each prover to finish its proof generation to start aggregating.
Recursive aggregation
Another solution is to go for recursive aggregation. Here, a first “sub-aggregator” takes two proofs and proves that these two proofs are valid — that is, that they successfully get verified and that their states correctly link (literally linear aggregation with N=2). This first sub-aggregator yields a proof that “contains” the original ones (this is 2-to-1 recursion). By repeating this process for all N proofs (leaf proofs), the aggregator is left with N/2 proofs to prove.
A second sub-aggregator is then in charge of proving the validity of these new proofs (the inner proofs). The process is similar to the first sub-aggregator with a slight twist regarding the claim that now becomes: “the two input proofs are a valid execution of the first sub-aggregator and the VM states of the leaf proofs are continuous”. This second sub-aggregator yields N/4 new proofs. By repeating this pattern, the aggregating program builds a recursion tree up to the root proof.
With a large enough number of machines that yield all N proofs at once, there is no need for recursive aggregation. Indeed, this approach only gets interesting when computing resources are limited and when proofs arrive in batch, in which case the main benefit of recursive aggregation comes in: aggregation can start before all leaf proofs are generated, reducing latency.
Conclusion
Recent applications featuring continuations include real-time proving of the EVM, where proofs of “sub-blocks” are generated in parallel on ~10 5090 GPUs, then aggregated in no more than 10 seconds! With recursion taking up to 2/3 of the proving time, many design decisions are made to make zkVMs more recursion-friendly. Continuations are a powerful way to extend the capabilities of zkVMs, and at Herodotus, we are making sure to deliver this state-of-the-art technology in our products.
Follow us on Twitter for the latest updates and join our Telegram community to engage with other developers building with Herodotus solutions.
