IO operations
Miden assembly provides a set of instructions for moving data between the operand stack and several other sources. These sources include:
- Program code: values to be moved onto the operand stack can be hard-coded in a program’s source code.
- Environment: values can be moved onto the operand stack from environment variables. These include current clock cycle, current stack depth, and a few others.
- Advice provider: values can be moved onto the operand stack from the advice provider by popping them from the advice stack (see more about the advice provider here). The VM can also inject new data into the advice provider via advice injector instructions.
- Memory: values can be moved between the stack and random-access memory. The memory is word-addressable, meaning, four elements are located at each address, and we can read and write elements to/from memory in batches of four. Memory can be accessed via absolute memory references (i.e., via memory addresses) as well as via local procedure references (i.e., local index). The latter approach ensures that a procedure does not access locals of another procedure.
Constant inputs¶
| Instruction | Stack_input | Stack_output | Notes |
|---|---|---|---|
| push.a - (1-2 cycles) push.a.b push.a.b.c… |
[ … ] | [a, … ] [b, a, … ] [c, b, a, … ] |
Pushes values \(a\), \(b\), \(c\) etc. onto the stack. Up to \(16\) values can be specified. All values must be valid field elements in decimal (e.g., \(123\)) or hexadecimal (e.g., \(0x7b\)) representation. |
The value can be specified in hexadecimal form without periods between individual values as long as it describes a full word (\(4\) field elements or \(32\) bytes). Note that hexadecimal values separated by periods (short hexadecimal strings) are assumed to be in big-endian order, while the strings specifying whole words (long hexadecimal strings) are assumed to be in little-endian order. That is, the following are semantically equivalent:
push.0x00001234.0x00005678.0x00009012.0x0000abcd
push.0x341200000000000078560000000000001290000000000000cdab000000000000
push.4660.22136.36882.43981
Environment inputs¶
| Instruction | Stack_input | Stack_output | Notes |
|---|---|---|---|
| clk - (1 cycle) |
[ … ] | [t, … ] | \(t \leftarrow clock\_value()\) Pushes the current value of the clock cycle counter onto the stack. |
| sdepth - (1 cycle) |
[ … ] | [d, … ] | \(d \leftarrow stack.depth()\) Pushes the current depth of the stack onto the stack. |
| caller - (1 cycle) |
[A, b, … ] | [H, b, … ] | \(H \leftarrow context.fn\_hash()\) Overwrites the top four stack items with the hash of a function which initiated the current SYSCALL. Executing this instruction outside of SYSCALL context will fail. |
| locaddr.i - (2 cycles) |
[ … ] | [a, … ] | \(a \leftarrow address\_of(i)\) Pushes the absolute memory address of local memory at index \(i\) onto the stack. |
Nondeterministic inputs¶
As mentioned above, nondeterministic inputs are provided to the VM via the advice provider. Instructs which access the advice provider fall into two categories. The first category consists of instructions which move data from the advice stack onto the operand stack and/or memory.
| Instruction | Stack_input | Stack_output | Notes |
|---|---|---|---|
| adv_push.n - (n cycles) |
[ … ] | [a, … ] | \(a \leftarrow stack.pop()\) Pops \(n\) values from the advice stack and pushes them onto the operand stack. Valid for \(n \in \{1, ..., 16\}\). Fails if the advice stack has fewer than \(n\) values. |
| adv_loadw - (1 cycle) |
[0, 0, 0, 0, … ] | [A, … ] | \(A \leftarrow stack.pop(4)\) Pop the next word (4 elements) from the advice stack and overwrites the first word of the operand stack (4 elements) with them. Fails if the advice stack has fewer than \(4\) values. |
| adv_pipe - (1 cycle) |
[C, B, A, a, … ] | [E, D, A, a’, … ] | \([D, E] \leftarrow [adv\_stack.pop(4), adv\_stack.pop(4)]\) \(a' \leftarrow a + 2\) Pops the next two words from the advice stack, overwrites the top of the operand stack with them and also writes these words into memory at address \(a\) and \(a + 1\). Fails if the advice stack has fewer than \(8\) values. |
Note: The opcodes above always push data onto the operand stack so that the first element is placed deepest in the stack. For example, if the data on the stack is
a,b,c,dand you use the opcodeadv_push.4, the data will bed,c,b,aon your stack. This is also the behavior of the other opcodes.
The second category injects new data into the advice provider. These operations are called advice injectors and they affect only the advice provider state. That is, the state of all other VM components (e.g., stack, memory) are unaffected. Executing advice injectors does not consume any VM cycles (i.e., these instructions are executed in \(0\) cycles).
Advice injectors fall into two categories: (1) injectors which push new data onto the advice stack, and (2) injectors which insert new data into the advice map.
| Instruction | Stack_input | Stack_output | Notes |
|---|---|---|---|
| adv.push_mapval adv.push_mapval.s |
[K, … ] | [K, … ] | Pushes a list of field elements onto the advice stack. The list is looked up in the advice map using word \(K\) as the key. If offset \(s\) is provided, the key is taken starting from item \(s\) on the stack. |
| adv.push_mapvaln adv.push_mapvaln.s |
[K, … ] | [K, … ] | Pushes a list of field elements together with the number of elements onto the advice stack. The list is looked up in the advice map using word \(K\) as the key. If offset \(s\) is provided, the key is taken starting from item \(s\) on the stack. |
| adv.push_mtnode | [d, i, R, … ] | [d, i, R, … ] | Pushes a node of a Merkle tree with root \(R\) at depth \(d\) and index \(i\) from Merkle store onto the advice stack. |
| adv.push_u64div | [b1, b0, a1, a0, …] | [b1, b0, a1, a0, …] | Pushes the result of u64 division \(a / b\) onto the advice stack. Both \(a\) and \(b\) are represented using 32-bit limbs. The result consists of both the quotient and the remainder. |
| adv.push_ext2intt | [osize, isize, iptr, … ] | [osize, isize, iptr, … ] | Given evaluations of a polynomial over some specified domain, interpolates the evaluations into a polynomial in coefficient form and pushes the result into the advice stack. |
| adv.push_sig.kind | [K, M, …] | [K, M, …] | Pushes values onto the advice stack which are required for verification of a DSA with scheme specified by kind against the public key commitment \(K\) and message \(M\). |
| adv.smt_get | [K, R, … ] | [K, R, … ] | Pushes values onto the advice stack which are required for successful retrieval of a value under the key \(K\) from a Sparse Merkle Tree with root \(R\). |
| adv.smt_set | [V, K, R, …] | [V, K, R, …] | Pushes values onto the advice stack which are required for successful insertion of a key-value pair \((K, V)\) into a Sparse Merkle Tree with root \(R\). |
| adv.smt_peek | [K, R, … ] | [K, R, … ] | Pushes value onto the advice stack which is associated with key \(K\) in a Sparse Merkle Tree with root \(R\). |
| adv.insert_mem | [K, a, b, … ] | [K, a, b, … ] | Reads words \(data \leftarrow mem[a] .. mem[b]\) from memory, and save the data into \(advice\_map[K] \leftarrow data\). |
| adv.insert_hdword adv.insert_hdword.d |
[B, A, … ] | [B, A, … ] | Reads top two words from the stack, computes a key as $K \leftarrow hash(A |
| adv.insert_hperm | [B, A, C, …] | [B, A, C, …] | Reads top three words from the stack, computes a key as \(K \leftarrow permute(C, A, B).digest\), and saves data into \(advice\_mpa[K] \leftarrow [A, B]\). |
Random access memory¶
As mentioned above, there are two ways to access memory in Miden VM. The first way is via memory addresses using the instructions listed below. The addresses are absolute - i.e., they don’t depend on the procedure context. Memory addresses can be in the range \([0, 2^{32})\).
Memory is guaranteed to be initialized to zeros. Thus, when reading from memory address which hasn’t been written to previously, zero elements will be returned.
| Instruction | Stack_input | Stack_output | Notes |
|---|---|---|---|
| mem_load - (1 cycle) mem_load.a - (2 cycles) |
[a, … ] | [v, … ] | \(v \leftarrow mem[a][0]\) Reads a word (4 elements) from memory at address a, and pushes the first element of the word onto the stack. If \(a\) is provided via the stack, it is removed from the stack first. Fails if \(a \ge 2^{32}\) |
| mem_loadw - (1 cycle) mem_loadw.a - (2 cycles) |
[a, 0, 0, 0, 0, … ] | [A, … ] | \(A \leftarrow mem[a]\) Reads a word from memory at address \(a\) and overwrites top four stack elements with it. If \(a\) is provided via the stack, it is removed from the stack first. Fails if \(a \ge 2^{32}\) |
| mem_store - (2 cycles) mem_store.a - (3-4 cycles) |
[a, v, … ] | [ … ] | \(v \rightarrow mem[a][0]\) Pops the top element off the stack and stores it as the first element of the word in memory at address \(a\). All other elements of the word are not affected. If \(a\) is provided via the stack, it is removed from the stack first. Fails if \(a \ge 2^{32}\) |
| mem_storew - (1 cycle) mem_storew.a - (2-3 cycles) |
[a, A, … ] | [A, … ] | \(A \rightarrow mem[a]\) Stores the top four elements of the stack in memory at address \(a\). If \(a\) is provided via the stack, it is removed from the stack first. Fails if \(a \ge 2^{32}\) |
| mem_stream - (1 cycle) |
[C, B, A, a, … ] | [E, D, A, a’, … ] | \([E, D] \leftarrow [mem[a], mem[a+1]]\) \(a' \leftarrow a + 2\) Read two sequential words from memory starting at address \(a\) and overwrites the first two words in the operand stack. |
The second way to access memory is via procedure locals using the instructions listed below. These instructions are available only in procedure context. The number of locals available to a given procedure must be specified at procedure declaration time, and trying to access more locals than was declared will result in a compile-time error. The number of locals per procedure is not limited, but the total number of locals available to all procedures at runtime must be smaller than \(2^{32}\).
| Instruction | Stack_input | Stack_output | Notes |
|---|---|---|---|
| loc_load.i - (3-4 cycles) |
[ … ] | [v, … ] | \(v \leftarrow local[i][0]\) Reads a word (4 elements) from local memory at index i, and pushes the first element of the word onto the stack. |
| loc_loadw.i - (3-4 cycles) |
[0, 0, 0, 0, … ] | [A, … ] | \(A \leftarrow local[i]\) Reads a word from local memory at index \(i\) and overwrites top four stack elements with it. |
| loc_store.i - (4-5 cycles) |
[v, … ] | [ … ] | \(v \rightarrow local[i][0]\) Pops the top element off the stack and stores it as the first element of the word in local memory at index \(i\). All other elements of the word are not affected. |
| loc_storew.i - (3-4 cycles) |
[A, … ] | [A, … ] | \(A \rightarrow local[i]\) Stores the top four elements of the stack in local memory at index \(i\). |
Unlike regular memory, procedure locals are not guaranteed to be initialized to zeros. Thus, when working with locals, one must assume that before a local memory address has been written to, it contains “garbage”.
Internally in the VM, procedure locals are stored at memory offset stating at \(2^{30}\). Thus, every procedure local has an absolute address in regular memory. The locaddr.i instruction is provided specifically to map an index of a procedure’s local to an absolute address so that it can be passed to downstream procedures, when needed.