Miden VM Program decoder

Miden VM program decoder is responsible for ensuring that a program with a given MAST root is executed by the VM. As the VM executes a program, the decoder does the following:

1. Decodes a sequence of field elements supplied by the prover into individual operation codes (or opcodes for short).
2. Organizes the sequence of field elements into code blocks, and computes the hash of the program according to the methodology described here.

At the end of program execution, the decoder outputs the computed program hash. This hash binds the sequence of opcodes executed by the VM to a program the prover claims to have executed. The verifier uses this hash during the STARK proof verification process to verify that the proof attests to a correct execution of a specific program (i.e., the prover didn't claim to execute program $A$ while in fact executing a different program $B$).

The sections below describe how Miden VM decoder works. Throughout these sections we make the following assumptions:

1. An opcode requires $7$ bits to represent.
2. An immediate value requires one full field element to represent.
3. A NOOP operation has a numeric value of $0$, and thus, can be encoded as seven zeros. Executing a NOOP operation does not change the state of the VM, but it does advance operation counter, and may affect program hash.

Program execution

Miden VM programs consist of a set of code blocks organized into a binary tree. The leaves of the tree contain linear sequences of instructions, and control flow is defined by the internal nodes of the tree.

Managing control flow in the VM is accomplished by executing control flow operations listed in the table below. Each of these operations requires exactly one VM cycle to execute.

Operation	Description
JOIN	Initiates processing of a new Join block.
SPLIT	Initiates processing of a new Split block.
LOOP	Initiates processing of a new Loop block.
REPEAT	Initiates a new iteration of an executing loop.
SPAN	Initiates processing of a new basic block.
RESPAN	Initiates processing of a new operation batch within a basic block.
DYN	Initiates processing of a new Dyn block.
DYNCALL	Initiates processing of a new Dyncall block.
CALL	Initiates processing of a new Call block.
SYSCALL	Initiates processing of a new Syscall block.
END	Marks the end of a program block.
HALT	Marks the end of the entire program.

Let's consider a simple program below:

begin
    <operations1>
    if.true
        <operations2>
    else
        <operations3>
    end
end

Block structure of this program is shown below.

JOIN
    SPAN
        <operations1>
    END
    SPLIT
        SPAN
            <operations2>
        END
        SPAN
            <operations3>
        END
    END
END

Executing this program on the VM can result in one of two possible instruction sequences. First, if after operations in <operations1> are executed the top of the stack is $1$, the VM will execute the following:

JOIN
SPAN
<operations1>
END
SPLIT
SPAN
<operations2>
END
END
END
HALT

However, if after <operations1> are executed, the top of the stack is $0$, the VM will execute the following:

JOIN
SPAN
<operations1>
END
SPLIT
SPAN
<operations3>
END
END
END
HALT

The main task of the decoder is to output exactly the same program hash, regardless of which one of the two possible execution paths was taken. However, before we can describe how this is achieved, we need to give an overview of the overall decoder structure.

Decoder structure

The decoder is one of the more complex parts of the VM. It consists of the following components:

• Main execution trace consisting of $23$ trace columns which contain the state of the decoder at a given cycle of a computation.
• Connection to the hash chiplet, which is used to offload hash computations from the decoder.
• $3$ virtual tables, implemented with typed LogUp messages, which keep track of code blocks and operations executing on the VM.

Decoder trace

Decoder trace columns are grouped as follows:

Columns	Registers	Purpose
$0$	$a$	Block address
$1$--$7$	$b_0, \ldots, b_6$	Opcode bits
$8$--$15$	$h_0, \ldots, h_7$	Hasher state and operation helpers
$16$	$sp$	In-basic-block flag
$17$	$gc$	Remaining operation-group count, or body multiplicity on LOOP rows
$18$	$ox$	Index within the current operation group
$19$	full_batch	Full eight-group batch indicator
$20$	batch_size_code	Short-batch size code ($1$, $-1$, or $0$)
$21$--$22$	$e_0, e_1$	Degree-reduction registers

These registers have the following meanings:

1. Block address register $a$. This register contains the hash-controller row address for the current block. It also serves the role of unique block identifiers. This is convenient, because hasher addresses are guaranteed to be unique.
2. Registers $b_0, ..., b_6$, which encode opcodes for operation to be executed by the VM. Each of these registers can contain a single binary value (either $1$ or $0$). And together these values describe a single opcode.
3. Hasher registers $h_0, ..., h_7$. When control flow operations are executed, these registers are used to provide inputs for the current block's hash computation (e.g., for JOIN, SPLIT, LOOP, SPAN, CALL, SYSCALL operations) or to record the result of the hash computation (i.e., for END operation). However, when regular operations are executed, $2$ of these registers are used to help with op group decoding, and the remaining $6$ can be used to hold operation-specific helper variables.
4. Register $sp$ which contains a binary flag indicating whether the VM is executing instructions inside a basic block. The flag is set to $1$ when the VM executes non-control flow instructions, and is set to $0$ otherwise.
5. Register $gc$ which keeps track of the number of unprocessed operation groups in a given basic block.
6. Register $ox$ which keeps track of a currently executing operation's index within its operation group.
7. Operation batch registers full_batch and batch_size_code, which encode how many operation groups a batch contains. The first is binary, the second is in $\{-1, 0, 1\}$, and each is constrained to zero on every other opcode.
8. Two additional registers $e_0$ and $e_1$ are used primarily for constraint degree reduction.

Program block hashing

To compute program-block hashes, the decoder relies on the hash controller. It performs two related Eidos operations:

1. A two-to-one hash compresses one 8-element block under a domain-specific chaining value and returns a 4-element digest.
2. A sequential hash uses one controller row per 8-element block. The digest of each row becomes the input chaining value of the next row.

Each controller row contains both the compression input and output. A typed compression-link message binds its complete (block, cv_in, cv_out) tuple to one physical 32-row cycle in EidosCompressionAir. Identical tuples may share one provider cycle through multiplicity without removing any decoder/controller request.

Simple two-to-one hash

The decoder initializes the Eidos chaining value from the control-block opcode and places the two child words in the block. At controller address r, it consumes a full-state input message and a digest-return message. Both messages use node index zero and the same row address. The explicit bus domains distinguish the input and output even though they share an address.

Sequential hash

The first block contributes a full-state input message at address r. Each following block contributes a next-block absorption message at the next controller address. The controller AIR constrains that row's input chaining value to equal the previous row's output chaining value.

The final block also supplies the digest-return message at its own address. Thus, for a stream of k blocks, controller addresses run from r through r + k - 1, and the result is returned at r + k - 1. Message reduction and the cross-AIR compression link are described in the hash-chiplet lookup section.

Control flow tables

In addition to the hash chiplet, control-flow operations use three virtual tables: the block stack, block hash, and op group tables. Each table is encoded as a domain-separated typed LogUp relation: insertions contribute with multiplicity $+1$, and removals with multiplicity $-1$. The following sections define their payloads and update rules.

Block stack table

When the VM starts executing a new program block, it adds its block ID together with the ID of its parent block (and some additional info) to the block stack table. When a program block is fully executed, it is removed from the table. In this way, the table represents a stack of blocks which are currently executing on the VM. By the time program execution completes, block stack table must be empty.

The block stack table is also used to ensure that execution contexts are managed properly across the CALL, DYNCALL, and SYSCALL operations.

Each BlockStackTable message has an 11-slot payload. Continuations use

$$[block\_id,parent\_id,is\_loop,0,0,0,0,0,0,0,0],$$

while caller frames use

$$[block\_id,parent\_id,0,ctx,b_0,b_1,fn\_hash_0,\ldots,fn\_hash_3,1].$$

The final slot authenticates the entry kind. It distinguishes a caller frame even when every saved caller-state value is zero. A caller frame saves the caller context, stack depth, overflow address, and function hash for restoration at END. Starting a block adds its message; completing it removes the same message. LogUp closure binds the restored values to those saved on entry.

Block hash table

When the VM starts executing a new program block, it adds hashes of the block's children to the block hash table. And when the VM finishes executing a block, it removes its hash from the block hash table. Thus, by the time program execution completes, block hash table must be empty.

The table can be thought of as consisting of $7$ columns as shown below:

where:

• The first four columns ($t_0,\ldots,t_3$) contain the block hash.
• The next column ($t_4$) contains its parent ID, or $0$ for the program root.
• $t_5$ is $1$ for the first child of a join block.
• $t_6$ is $1$ for the body of a loop.

Each entry is a BlockHashTable message with the payload

$$[child\_hash_0,\ldots,child\_hash_3,parent,is\_first\_child,is\_loop\_body].$$

Unlike other virtual tables, block hash table does not start out in an empty state. Specifically, it is initialized with a single row containing the hash of the program's root block. This needs to be done because the root block does not have a parent and, thus, otherwise it would never be added to the block hash table.

The verifier supplies that root entry as a positive LogUp boundary contribution. The root END row removes the matching message, binding the decoded execution to the public program hash.

Op group table

Op group table is used in decoding of basic blocks, which are leaves in a program's MAST. As described here, a basic block can contain one or more operation batches, each batch containing up to $8$ operation groups.

When the VM starts executing a new batch of operations, it adds all operation groups within a batch, except for the first one, to the op group table. Then, as the VM starts executing an operation group, it removes the group from the table. Thus, by the time all operation groups in a batch have been executed, the op group table must be empty.

The table can be thought of as consisting of $3$ columns as shown below:

The meaning of the columns is as follows:

• The first column ($t_0$) contains operation batch ID. During the execution of the program, each operation batch is assigned a unique ID.
• The second column ($t_1$) contains the position of the group in the basic block (not just in the current batch). The position is $1$-based and is counted from the end. Thus, for example, if a basic block consists of a single batch with $4$ groups, the position of the first group would be $4$, the position of the second group would be $3$ etc. (the reason for this is explained in this section). Note that the group with position $4$ is not added to the table, because it is the first group in the batch, so the first row of the table will be for the group with position $3$.
• The third column ($t_2$) contains the actual values of operation groups (this could include up to $9$ opcodes or a single immediate value).

Each entry is an OpGroupTable message with the payload

$$[batch\_id,group\_pos,group\_value].$$

Batch setup adds every deferred group, while beginning a group or consuming an immediate removes the matching message. The table is empty at completion because the relation's signed LogUp sum must close.

Control flow operation semantics

In this section we describe high-level semantics of executing all control flow operations. The descriptions are not meant to be complete and omit some low-level details. However, they provide good intuition on how these operations work.

JOIN operation

Before a JOIN operation is executed by the VM, the prover populates $h_0, ..., h_7$ registers with hashes of left and right children of the join program block as shown in the diagram below.

In the above diagram, blk is the ID of the join block which is about to be executed. blk is also the hash-controller row address. prnt is the ID of the block's parent.

When the VM executes a JOIN operation, it does the following:

1. Adds a continuation (blk, prnt, 0) to the block stack table.
2. Adds tuples (blk, left_child_hash, 1, 0) and (blk, right_child_hash, 0, 0) to the block hash table.
3. Initiates a 2-to-1 hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and $h_0, ..., h_7$ as input values.

SPLIT operation

Before a SPLIT operation is executed by the VM, the prover populates $h_0, ..., h_7$ registers with hashes of true and false branches of the split program block as shown in the diagram below.

In the above diagram, blk is the ID of the split block which is about to be executed. blk is also the hash-controller row address. prnt is the ID of the block's parent.

When the VM executes a SPLIT operation, it does the following:

1. Adds a continuation (blk, prnt, 0) to the block stack table.
2. Pops the stack and:
   a. If the popped value is $1$, adds a tuple (blk, true_branch_hash, 0, 0) to the block hash table.
   b. If the popped value is $0$, adds a tuple (blk, false_branch_hash, 0, 0) to the block hash table.
   c. If the popped value is neither $1$ nor $0$, the execution fails.
3. Initiates a 2-to-1 hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and $h_0, ..., h_7$ as input values.

LOOP operation

Before a LOOP operation is executed by the VM, the prover populates $h_0, ..., h_3$ registers with hash of the loop's body as shown in the diagram below. The remaining registers $h_4, ..., h_7$ are set to $0$ to complete the 8-element Eidos block.

In the above diagram, blk is the ID of the loop block which is about to be executed. blk is also the hash-controller row address. prnt is the ID of the block's parent.

The LOOP operation has do-while semantics: the body is entered unconditionally for the first iteration, with the condition checked only at the end of each iteration by REPEAT/END. When the VM executes a LOOP operation, it does the following:

1. Adds a continuation (blk, prnt, 1) to the block stack table (the 1 indicates that the loop's body is expected to be executed).
2. Adds the loop-body hash to the block hash table with multiplicity group_count, the number of body executions. Each body END removes one copy.
3. Initiates a 2-to-1 hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and the padded input $[h_0, ..., h_3, 0, 0, 0, 0]$.

The LOOP operation does not read or pop the stack.

SPAN operation

Before a SPAN operation is executed by the VM, the prover populates $h_0, ..., h_7$ registers with contents of the first operation batch of the basic block as shown in the diagram below. The prover also sets the group count register $gc$ to the total number of operation groups in the basic block.

In the above diagram, blk is the ID of the basic block which is about to be executed. blk is also the hash-controller row address. prnt is the ID of the block's parent. g0_op0 is the first operation of the batch, and g_0' is the first operation group of the batch with the first operation removed.

When the VM executes a SPAN operation, it does the following:

1. Adds a tuple (blk, prnt, 0, 0...) to the block stack table.
2. Adds groups of the operation batch, as specified by the batch encoding (see here) to the op group table.
3. Initiates a sequential hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and $h_0, ..., h_7$ as input values.
4. Sets the in_span register to $1$.
5. Decrements group_count register by $1$.
6. Sets the op_index register to $0$.

DYN operation

In the above diagram, blk is the ID of the dyn block which is about to be executed. blk is also the hash-controller row address. p_addr is the ID of the block's parent.

When the VM executes a DYN operation, it does the following:

1. Adds a continuation (blk, p_addr, 0) to the block stack table.
2. Sends a memory read request to the memory chiplet, using s0 as the memory address. The result hash of callee is placed in the decoder hasher trace at $h_0, h_1, h_2, h_3$.
3. Adds the tuple (blk, hash of callee, 0, 0) to the block hash table.
4. Initiates a 2-to-1 hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and [ZERO; 8] as the Eidos input block.
5. Performs a stack left shift
   • The new s15 is pulled from the stack overflow table if present; otherwise it is set to 0.

Note that unlike DYNCALL, the ctx and fn_hash registers are unchanged.

DYNCALL operation

In the above diagram, blk is the ID of the dyn block which is about to be executed. blk is also the hash-controller row address. p_addr is the ID of the block's parent.

When the VM executes a DYNCALL operation, it does the following:

1. Adds a tuple (blk, p_addr, 0, ctx, h_4, h_5, fn_hash) to the block stack table. The $h_4$ and $h_5$ registers hold the caller's post-shift stack depth and overflow address; fn_hash is a four-element word.
2. Sends a memory read request to the memory chiplet, using s0 as the memory address. The result hash of callee is placed in the decoder hasher trace at $h_0, h_1, h_2, h_3$.
3. Sends a memory write request to the memory chiplet to set address FMP_ADDR = 2^32 - 2 to FMP_INIT_VALUE = 2^31 in the new memory context. This initializes the fmp in the new context.
4. Adds the tuple (blk, hash of callee, 0, 0) to the block hash table.
5. Initiates a 2-to-1 hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and [ZERO; 8] as the Eidos input block.
6. Performs a stack left shift
   • The new s15 is pulled from the stack overflow table if present; otherwise it is set to 0.

Similar to CALL, DYNCALL sets up a new ctx, and sets the fn_hash registers to the callee hash.

END operation

Before an END operation is executed by the VM, the prover populates $h_0, ..., h_3$ registers with the hash of the block which is about to end. The prover also sets values in $h_4$ and $h_5$ registers as follows:

• $h_4$ is set to $1$ if the block is a body of a loop block. We denote this value as f0.
• $h_5$ is set to $1$ if the block is a loop block. We denote this value as f1. Under do-while semantics every loop block is entered, so $h_5 = 1$ for every loop's END row.
• $h_6$ is set to $1$ if this END restores a caller frame created by CALL, DYNCALL, or SYSCALL. We denote this value as f2.
• $h_7$ is set to $0$ on every END row. In the diagram below this is f3.

In the above diagram, blk is the ID of the block which is about to finish executing. prnt is the ID of the block's parent.

When the VM executes an END operation, it does the following:

1. Removes a tuple from the block stack table.
   • if f2 is set, we remove a caller-frame row (blk, prnt, 0, ctx_next, b0_next, b1_next, fn_hash_next, 1)
     • in the above, the x_next variables denote the column x in the next row
   • otherwise, we remove a continuation row (blk, prnt, f1, 0, 0, 0, [0; 4], 0)
2. Removes a tuple (prnt, current_block_hash, nxt, f0) from the block hash table, where $nxt=0$ if the next operation is END, REPEAT, RESPAN, or HALT, and $1$ otherwise.
3. Reads the block digest from the hash chiplet (as described here) using blk as the hash-controller row address.
4. If $h_5 = 1$ (i.e., we are exiting a loop block), pops the value off the top of the stack and verifies that the value is $0$.
5. Verifies that group_count register is set to $0$.

HALT operation

Before a HALT operation is executed by the VM, the VM copies values in $h_0, ..., h_3$ registers to the next row as illustrated in the diagram below:

In the above diagram, blk is the ID of the block which is about to finish executing.

When the VM executes a HALT operation, it does the following:

1. Verifies that block address register is set to $0$.
2. If we are not at the last row of the trace, verifies that the next operation is HALT.
3. Copies values of $h_0, ..., h_3$ registers to the next row.
4. Populates all other decoder registers with $0$'s in the next row.

REPEAT operation

REPEAT immediately follows an END whose $h_4$ identifies the completed node as a loop body. The decoder AIR checks that preceding flag and the parent address. The helper values shown on the REPEAT row below are not used to add a block-hash entry.

In the above diagram, blk is the ID of the loop's body and prnt is the ID of the loop.

The REPEAT operation pops a loop condition of $1$ from the operand stack. The next iteration removes another copy of the body hash from the weighted entry created by LOOP.

RESPAN operation

Before a RESPAN operation is executed by the VM, the VM copies the ID of the current block blk and the number of remaining operation groups in the basic block to the next row, and sets the value of in_span column to $0$. The prover also sets the value of $h_1$ register for the next row to the ID of the current block's parent prnt as shown in the diagram below:

In the above diagram, g0_op0 is the first operation of the new operation batch, and g0' is the first operation group of the batch with g0_op0 operation removed.

When the VM executes a RESPAN operation, it does the following:

1. Increments block address by $1$.
2. Removes the tuple (blk, prnt, 0, 0...) from the block stack table.
3. Adds the tuple (blk+1, prnt, 0, 0...) to the block stack table.
4. Absorbs values in registers $h_0, ..., h_7$ into the hasher state of the hash chiplet (as described here).
5. Sets the in_span register to $1$.
6. Adds groups of the operation batch, as specified by the batch encoding (see here) to the op group table using blk+1 as batch ID.

The net result of the above is that we incremented the ID of the current block by $1$ (the next controller row) and added the next set of operation groups to the op group table.

CALL operation

Recall that the purpose of a CALL operation is to execute a procedure in a new execution context. Specifically, this means that the entire memory is zero'd in the new execution context, and the stack is truncated to a depth of 16 (i.e. any element in the stack overflow table is not available in the new context). On the corresponding END instruction, the prover will restore the previous execution context (verified by the block stack table).

Before a CALL operation, the prover populates $h_0, ..., h_3$ registers with the hash of the procedure being called. In the next row, the prover

• sets the context ID to the next row's CLK value
• sets the fn hash registers to the hash of the callee
  • This register is what the caller instruction uses to return the hash of the caller
• resets the stack B0 register to 16 (which tracks the current stack depth)
• resets the overflow address to 0 (which tracks the "address" of the last element added to the overflow table)
  • it is set to 0 to indicate that the overflow table is empty

In the above diagram, blk is the ID of the call block which is about to be executed. blk is also the hash-controller row address. prnt is the ID of the block's parent.

When the VM executes a CALL operation, it does the following:

1. Adds a tuple (blk, prnt, 0, p_ctx, p_b0, p_b1, prnt_fn_hash) to the block stack table.
2. Initiates a 2-to-1 hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and $h_0, ..., h_3$ as input values.
3. Sends a memory write request to the memory chiplet to set address FMP_ADDR = 2^32 - 2 to FMP_INIT_VALUE = 2^31 in the new memory context. This initializes the fmp in the new context.

SYSCALL operation

Similarly to the CALL operation, a SYSCALL changes the execution context. However, it always jumps back to the root context, and executes kernel procedures only.

Before a SYSCALL operation, the prover populates $h_0, ..., h_3$ registers with the hash of the procedure being called. In the next row, the prover

• sets the context ID to 0,
• does NOT modify the fn hash register
  • Hence, the fn hash register contains the procedure hash of the caller, to be accessed by the caller instruction,
• resets the stack B0 register to 16 (which tracks the current stack depth)
• resets the overflow address to 0 (which tracks the "address" of the last element added to the overflow table)
  • it is set to 0 to indicate that the overflow table is empty

In the above diagram, blk is the ID of the syscall block which is about to be executed. blk is also the hash-controller row address. prnt is the ID of the block's parent.

When the VM executes a SYSCALL operation, it does the following:

1. Adds a tuple (blk, prnt, 0, p_ctx, p_b0, p_b1, prnt_fn_hash) to the block stack table.
2. Sends a request to the kernel ROM chiplet indicating that hash of callee is being accessed.
   • this results in a fault if hash of callee does not correspond to the hash of a kernel procedure
3. Initiates a 2-to-1 hash computation in the hash chiplet (as described here) using blk as the hash-controller row address and $h_0, ..., h_3$ as input values.

Program decoding

When decoding a program, we start at the root block of the program. We can compute the hash of the root block directly from hashes of its children. The prover provides hashes of the child blocks non-deterministically, and we use them to compute the program's hash (here we rely on the hash chiplet). We then verify the program hash via boundary constraints. Thus, if the prover provided valid hashes for the child blocks, we will get the expected program hash.

Now, we need to verify that the VM executed the child blocks correctly. We do this recursively similar to what is described above: for each of the blocks, the prover provides hashes of its children non-deterministically and we verify that the hash has been computed correctly. We do this until we get to the leaf nodes (i.e., basic blocks). Hashes of basic blocks are computed sequentially from the instructions executed by the VM.

The sections below illustrate how different types of code blocks are decoded by the VM.

JOIN block decoding

When decoding a join bock, the VM first executes a JOIN operation, then executes the first child block, followed by the second child block. Once the children of the join block are executed, the VM executes an END operation. This is illustrated in the diagram below.

As described previously, when the VM executes a JOIN operation, hashes of both children are added to the block hash table. These hashes are removed only when the END operations for the child blocks are executed. Thus, until both child blocks are executed, the block hash table is not cleared.

SPLIT block decoding

When decoding a split block, the decoder pops an element off the top of the stack, and if the popped element is $1$, executes the block corresponding to the true branch. If the popped element is $0$, the decoder executes the block corresponding to the false branch. This is illustrated on the diagram below.

As described previously, when the VM executes a SPLIT operation, only the hash of the branch to be executed is added to the block hash table. Thus, until the child block corresponding to the required branch is executed, the block hash table is not cleared.

LOOP block decoding

A loop block has do-while semantics: the body is entered unconditionally for the first iteration, and the trailing condition the body leaves on top of the stack determines whether the VM executes another iteration (REPEAT) or exits (END).

When the VM executes a LOOP operation, it adds one weighted body-hash entry whose multiplicity equals the number of body executions. It also adds a row to the block stack table with is_loop set to $1$. The LOOP operation itself does not read or pop the stack.

Each execution of the body ends with an END that removes one unit of the weighted body-hash entry. If the trailing condition is $1$, the VM executes REPEAT and enters the body again; a REPEAT with a trailing condition of $0$ fails. Since REPEAT adds no block-hash entry, each iteration must execute the body that LOOP committed to.

This process is illustrated on the diagram below.

The above steps are repeated until the top of the stack becomes $0$, at which point the VM executes the END operation. Since is_loop is always $1$ for a loop's END row under do-while semantics, the END operation always pops the trailing condition off the stack. If the popped value is not $0$, the operation fails. Thus, the VM can exit the loop block only when the top of the stack is $0$.

DYN block decoding

When decoding a dyn bock, the VM first executes a DYN operation, then executes the child block dynamically specified by the top of the stack. Once the child of the dyn block has been executed, the VM executes an END operation. This is illustrated in the diagram below.

As described previously, when the VM executes a DYN operation, the hash of the child is added to the block hash table. This hash is removed only when the END operation for the child block is executed. Thus, until the child block corresponding to the dynamically specified target is executed, the block hash table is not cleared.

Basic block decoding

As described here, a basic block can contain one or more operation batches, each batch containing up to $8$ operation groups. At the high level, decoding of a basic block is done as follows:

1. At the beginning of the block, we make a request to the hash chiplet which initiates the hasher, absorbs the first operation batch ($8$ field elements) into the hasher, and returns the row address of the hasher, which we use as the unique ID for the basic block (see here).
2. We then add groups of the operation batch, as specified by the batch encoding (but always skipping the first one) to the op group table.
3. We then remove operation groups from the op group table in the FIFO order one by one, and decode them in the manner similar to the one described here.
4. Once all operation groups in a batch have been decoded, we absorb the next batch into the hasher and repeat the process described above.
5. Once all batches have been decoded, we return the hash of the basic block from the hasher.

Overall, three control flow operations are used when decoding a basic block:

1. SPAN operation is used to initialize a hasher and absorbs the first operation batch into it.
2. RESPAN operation is used to absorb any additional batches in the basic block.
3. END operation is used to end the decoding of a basic block and retrieve its hash from the hash chiplet.

Operation group decoding

As described here, an operation group is a sequence of operations which can be encoded into a single field element. For a field element of $64$ bits, we can fit up to $9$ operations into a group. We do this by concatenating binary representations of opcodes together with the first operation located in the least significant position.

We can read opcodes from the group by simply subtracting them from the op group value and then dividing the result by $2^7$. Once the value of the op group reaches $0$, we know that all opcodes have been read. Graphically, this can be illustrated like so:

Notice that despite their appearance, op bits is actually $7$ separate registers, while op group is just a single register.

We also need to make sure that at most $9$ operations are executed as a part of a single group. For this purpose we use the op_index column. Values in this column start out at $0$ for each operation group, and are incremented by $1$ for each executed operation. To make sure that at most $9$ operations can be executed in a group, the value of the op_index column is not allowed to exceed $8$.

Operation batch encoding

Two operation batch registers specify how many operation groups comprise a given operation batch. For most batches, the number of groups will be equal to $8$. However, for the last batch in a block (or for the first batch, if the block consists of only a single batch), the number of groups may be less than $8$. Since processing of new batches starts only on SPAN and RESPAN operations, the encoding is active only for these operations.

To simplify the constraint system, the number of groups in a batch can be only one of the following values: $1$, $2$, $4$, and $8$. If the number of groups in a batch does not match one of these values, the batch is padded with NOOP operations, one per added group. For example, a three-group batch is padded to four groups. Since the numeric value of NOOP is $0$, a zero-valued operation group represents the padding operation.

The pair $(full\_batch, batch\_size\_code)$ encodes the batch size and determines which groups are added to the op group table:

Encoding	Batch size	Groups added to the op group table
$(1, 0)$	$8$	$h_1, \ldots, h_7$
$(0, 1)$	$4$	$h_1, \ldots, h_3$
$(0, -1)$	$2$	$h_1$
$(0, 0)$ on SPAN or RESPAN	$1$	None
$(0, 0)$ otherwise	Inactive	None

Thus, the constrained SPAN/RESPAN selector distinguishes a one-group batch from an inactive row; both use the same two committed values.

Single-batch span

The simplest example of a basic block is a block with a single batch. This batch may contain up to $8$ operation groups (e.g., $g_0, ..., g_7$). Decoding of such a block is illustrated in the diagram below.

Before the VM starts processing this basic block, the prover populates registers $h_0, ..., h_7$ with operation groups $g_0, ..., g_7$. The prover also puts the total number of groups into the group_count register $gc$. In this case, the total number of groups is $8$.

When the VM executes a SPAN operation, it does the following:

1. Initiates hashing of elements $g_0, ..., g_7$ using hash chiplet. The hasher address is used as the block ID blk, and it is inserted into addr register in the next row.
2. Adds a continuation (blk, prnt, 0) to the block stack table.
3. Sets the is_span register to $1$ in the next row.
4. Sets the op_index register to $0$ in the next row.
5. Decrements group_count register by $1$.
6. Sets op bits registers at the next step to the first operation of $g_0$, and also copies $g_0$ with the first operation removed (denoted as $g_0'$) to the next row.
7. Adds groups $g_1, ..., g_7$ to the op group table. Thus, after the SPAN operation is executed, op group table looks as shown below.

Then, with every step the next operation is removed from $g_0$, and by step $9$, the value of $g_0$ is $0$. Once this happens, the VM does the following:

1. Decrements group_count register by $1$.
2. Sets op bits registers at the next step to the first operation of $g_1$.
3. Sets hasher register $h_0$ to the value of $g_1$ with the first operation removed (denoted as $g_1'$).
4. Removes row (blk, 7, g1) from the op group table. This row can be obtained by taking values from registers: addr, group_count, and $h_0' + \displaystyle\sum_{i=0}^6(2^i \cdot b_i')$ for $i \in [0, 7)$, where $h_0'$ and $b_i'$ refer to values in the next row for the first hasher column and op_bits columns respectively.

Note that we rely on the group_count column to construct the row to be removed from the op group table. Since group count is decremented from the total number of groups to $0$, to remove groups from the op group table in correct order, we need to assign group position to groups in the op group table in the reverse order. For example, the first group to be removed should have position $7$, the second group to be removed should have position $6$ etc.

Decoding of $g_1$ is performed in the same manner as decoding of $g_0$: with every subsequent step the next operation is removed from $g_1$ until its value reaches $0$, at which point, decoding of group $g_2$ begins.

The above steps are executed until value of group_count reaches $0$. Once group_count reaches $0$ and the last operation group $g_7$ is executed, the VM executes the END operation. Semantics of the END operation are described here.

Notice that by the time we get to the END operation, all rows are removed from the op group table.

Multi-batch basic block

A basic block may contain an unlimited number of operation batches. As mentioned previously, to absorb a new batch into the hasher, the VM executes a RESPAN operation. The diagram below illustrates decoding of a basic block consisting of two operation batches.

Decoding of such a block will look very similar to decoding of the single-basic block described previously, but there also will be some differences.

First, after the SPAN operation is executed, the op group table will look as follows:

Notice that while the same groups ($g_1, ..., g_7$) are added to the table, their positions now reflect the total number of groups in the basic block.

Second, RESPAN advances the hasher controller address by $1$, because each absorbed batch occupies one controller row.

Advancing the addr register changes the ID of the basic block. The block-stack entry therefore changes from (blk, prnt, 0) to (blk + 1, prnt, 0). The prover sets $h_1$ in the next row to prnt to perform this update.

Executing a RESPAN operation also adds groups $g_9, g_{10}, g_{11}$ to the op group table, which now would look as follows:

Then, the execution of the second batch proceeds in a manner similar to the first batch: we remove operations from the current op group, execute them, and when the value of the op group reaches $0$, we start executing the next group in the batch. Thus, by the time we get to the END operation, the op group table should be empty.

When END executes, it reads the basic-block digest from the final controller row at addr; after one RESPAN, this is blk + 1.

Handling immediate values

Miden VM operations can carry immediate values. Currently, the only such operation is a PUSH operation. Since immediate values can be thought of as constants embedded into program code, we need to make sure that changing immediate values affects program hash.

To achieve this, we treat immediate values in a manner similar to how we treat operation groups. Specifically, when computing hash of a basic block, immediate values are absorbed into the hasher state in the same way as operation groups are. As mentioned previously, an immediate value is represented by a single field element, and thus, an immediate value takes place of a single operation group.

The diagram below illustrates decoding of a basic block with $9$ operations one of which is a PUSH operation.

In the above, when the SPAN operation is executed, immediate value imm0 will be added to the op group table, which will look as follows:

Then, when the PUSH operation is executed, the VM will do the following:

1. Decrement group_count by $1$.
2. Remove a row from the op group table equal to (addr, group_count, s0'), where $s_0'$ is the value of the top of the stack at the next row (i.e., it is the value that is pushed onto the stack).

Thus, after the PUSH operation is executed, the op group table is cleared, and group count decreases to $0$ (which means that there are no more op groups to execute). Decoding of the rest of the op group proceeds as described in the previous sections.

Program decoding example

Let's run through an example of decoding a simple program shown previously:

begin
    <operations1>
    if.true
        <operations2>
    else
        <operations3>
    end
end

Translating this into code blocks with IDs assigned, we get the following:

b0: JOIN
    b1: SPAN
        <operations1>
    b1: END
    b2: SPLIT
        b3: SPAN
            <operations2>
        b3: END
        b4: SPAN
            <operations3>
        b4: END
    b2: END
b0: END

The root of the program is a join block $b_0$. This block contains two children: a basic bock $b_1$ and a split block $b_2$. In turn, the split block $b_2$ contains two children: a basic block $b_3$ and a basic block $b_4$.

When this program is executed on the VM, the following happens:

1. Before the program starts executing, block hash table is initialized with a single row containing the hash of $b_0$.
2. Then, JOIN operation for $b_0$ is executed. It adds hashes of $b_1$ and $b_2$ to the block hash table. It also adds an entry for $b_0$ to the block stack table. States of both tables after this step are illustrated below.
3. Then, basic $b_1$ is executed and a sequential hash of its operations is computed. Also, when SPAN operation for $b_1$ is executed, an entry for $b_1$ is added to the block stack table. At the end of $b_1$ (when END is executed), entries for $b_1$ are removed from both the block hash and block stack tables.
4. Then, SPLIT operation for $b_2$ is executed. It adds an entry for $b_2$ to the block stack table. Also, depending on whether the top of the stack is $1$ or $0$, either hash of $b_3$ or hash of $b_4$ is added to the block hash table. Let's say the top of the stack is $1$. Then, at this point, the block hash and block stack tables will look like in the second picture below.
5. Then, basic $b_3$ is executed and a sequential hash of its instructions is computed. Also, when SPAN operation for $b_3$ is executed, an entry for $b_3$ is added to the block stack table. At the end of $b_3$ (when END is executed), entries for $b_3$ are removed from both the block hash and block stack tables.
6. Then, END operation for $b_2$ is executed. It removes the hash of $b_2$ from the block hash table, and also removes the entry for $b_2$ from the block stack table. The third picture below illustrates the states of block stack and block hash tables after this step.
7. Then, END for $b_0$ is executed, which removes entries for $b_0$ from the block stack and block hash tables. At this point both tables are empty.
8. Finally, a sequence of HALT operations is executed until the length of the trace reaches a power of two.

States of block hash and block stack tables after step 2:

States of block hash and block stack tables after step 4:

States of block hash and block stack tables after step 6: