Deferral Framework

Prerequisites

Familiarity with the continuations design is recommended before reading this page.

Overview

Suppose we have a collection of standalone circuits C_0, C_1, .. each handling diverse computations that may not be a VM architecture. We would like to be able to call these circuits from the main VM.

We model each C_i as a function f_i: Input_i -> Output_i, where Input_i and Output_i are types such that there exist hash functions g_i: Input_i -> Digest and h_i: Output_i -> Digest. Given a raw input_i_raw: Input_i and output_i_raw: Output_i, we call g_i(input_i_raw) and h_i(output_i_raw) the input commit and output commit respectively.

We also define the circuit commit as the def_circuit_commit below.

High Level Summary

• The VM executes some unconstrained block of compute, recording each input and output commit into an accumulator
• Each C_i is proven independently and aggregated into a per-circuit deferral aggregation tree, which is then aggregated into a single internal-recursive proof that exposes the initial and final accumulator Merkle roots
• The root verifier checks that the VM's initial and final memory states match the claims

OpenVM Extension and Guest Library

During guest program execution, we maintain an input_i_accumulator: Digest and output_i_accumulator: Digest for each C_i. These accumulators are stored in order at the beginning of the deferral address space (address space 4), meaning that the accumulators for some C_i will be stored starting at [2 * i * DIGEST_SIZE]_4.

Each accumulator is a hash onion, i.e. the result of folding π (Poseidon2 compression) over the sequence of commits seen so far. input_i_accumulator and output_i_accumulator accumulate the input and output commits for calls to C_i specifically. input_i_accumulator will initially be the def_circuit_commit, and output_i_accumulator all zero — this is required to constrain that the correct deferral circuits were used.

New Opcodes

We introduce two new opcodes as part of the deferral extension: CALL and OUTPUT.

CALL

• Reads an input commit (i.e. input_i_commit: Digest) from memory
• Computes output_i_raw and output_i_commit = h_i(output_i_raw)
• Sets input_i_accumulator = π(input_i_accumulator, input_i_commit) and output_i_accumulator = π(output_i_accumulator, output_i_commit)
• Writes (output_i_commit, output_i_len) to memory, where output_i_len is stored as an 8-byte little-endian integer but is currently constrained to a zero-extended 32-bit byte length. The raw output length must be divisible by DIGEST_SIZE.

OUTPUT

• Reads an output key (i.e. output_i_commit: Digest and output_i_len) from memory
• Writes the corresponding output_i_raw to memory

Opcode Contracts

We provide the following guarantees on the opcodes defined above:

• Reading an invalid input_i_commit or output_i_commit will result in an invalid proof
• Deferred outputs are only supported when output_i_len is divisible by DIGEST_SIZE
• OUTPUT does not ensure the size of allocated write memory

Extension Chips and Constraints

The deferral extension contains several executor and peripheral chips to constrain the opcode functions and contracts above. It is configured with a Vec<Arc<DeferralFn>> defining the f_i functions and a Vec<[u8; 32]> containing the def_circuit_commit for each C_i.

Deferral Circuit

Each deferral circuit C_i must constrain that f_i(input_i_raw) = output_i_raw. Additionally, it must constrain that input_i_commit is the sponge hash of g_i(input_i_raw) and the cached trace commits, and that h_i(output_i_raw) = output_i_commit. Note that if there are no cached trace commits, then input_i_commit = π(g_i(input_i_raw), 0).

input_i_commit and output_i_commit must be exposed as public values.

Aggregation Subcircuit and Tree

The proofs for each C_i are aggregated separately. The leaf, internal-for-leaf, and internal-recursive layers use an aggregation subcircuit that:

• Constrains the validity of each child proof
• At the leaf layer, folds cached trace commits into each child's input_i_commit to produce a folded_input_commit, then compresses (folded_input_commit, output_i_commit) into a single merkle_commit. At internal layers, Merklizes child merkle_commits into a single merkle_commit
• Exposes merkle_commit and num_def_circuit_proofs as public values
• Propagates def_vk_commit, leaf_vk_commit, and internal_for_leaf_vk_commit through the verifier subcircuit

Note that because we are building a Merkle tree of input and output commits, tail proofs are combined with "non-present" proofs. The input and output commit of a non-present proof at a particular depth is the Merkle root of a zeroed tree of that depth.

The final internal-recursive layer is passed to a deferral hook layer, which:

• Constrains its validity
• Reconciles the input and output Merkle commits into the input and output onion hashes
• Computes def_circuit_commit by hashing the VK commit components (cached_commit and vk_pre_hash for each of def_vk_commit, leaf_vk_commit, internal_for_leaf_vk_commit) via hash_slice
• Exposes DeferralPvs containing initial_acc_hash = π(π(def_circuit_commit, 0), π(0, 0)), final_acc_hash = π(π(input_onion, 0), π(output_onion, 0)), and depth = 1
  • Note that initial_acc_hash and final_acc_hash are memory subtree Merkle leaves, with each leaf zero-padded before Merklization

Each deferral hook proof is aggregated using the combined VM-deferral tree, which recursively exposes π(initial_acc_hash_0, initial_acc_hash_1) and π(final_acc_hash_0, final_acc_hash_1). The root verifier constrains that the final initial_acc_hash and final_acc_hash were present in the initial and final memory state respectively.

Verify STARK

STARK proof verification is implemented using the deferral framework. See the Verify STARK guest library for usage details.

• Input_i: Proof
• Output_i: (app_exe_commit, app_vm_commit, user_pvs) tuple
• C_i: a recursion circuit that exposes the compressed final transcript state as input_i_commit and constrains the listed public values against the Proof's claimed public values

The compressed final transcript state serves as input_i_commit because it deterministically binds the entire proof — any change to the proof produces a different transcript, so committing to it is equivalent to committing to the Proof.

Each different guest verifying key corresponds to a different deferral circuit. The Verify STARK guest library is provided for guest developers' convenience.