Cryptographic operations
Miden assembly provides a set of instructions for performing common cryptographic operations. These instructions are listed in the table below.
Hashing and Merkle trees¶
Rescue-Prime Optimized is the native hash function of Miden VM. The parameters of the hash function were chosen to provide 128-bit security level against preimage and collision attacks. The function operates over a state of 12 field elements, and requires 7 rounds for a single permutation. However, due to its special status within the VM, computing Rescue Prime Optimized hashes can be done very efficiently. For example, applying a permutation of the hash function can be done in a single VM cycle.
| Instruction | Stack_input | Stack_output | Notes |
|---|---|---|---|
| hash - (20 cycles) |
[A, …] | [B, …] | \(\{B\} \leftarrow hash(A)\) where, \(hash()\) computes a 1-to-1 Rescue Prime Optimized hash. |
| hperm - (1 cycle) |
[C, B, A, …] | [F, E, D, …] | \(\{D, E, F\} \leftarrow permute(A, B, C)\) Performs a Rescue Prime Optimized permutation on the top 3 words of the operand stack, where the top 2 words elements are the rate (words C and B), the deepest word is the capacity (word A), the digest output is the word E. |
| hmerge - (16 cycles) |
[B, A, …] | [C, …] | \(C \leftarrow hash(A,B)\) where, \(hash()\) computes a 2-to-1 Rescue Prime Optimized hash. |
| mtree_get - (9 cycles) |
[d, i, R, …] | [V, R, …] | Fetches the node value from the advice provider and runs a verification equivalent to mtree_verify, returning the value if succeeded. |
| mtree_set - (29 cycles) |
[d, i, R, V’, …] | [V, R’, …] | Updates a node in the Merkle tree with root \(R\) at depth \(d\) and index \(i\) to value \(V'\). \(R'\) is the Merkle root of the resulting tree and \(V\) is old value of the node. Merkle tree with root \(R\) must be present in the advice provider, otherwise execution fails. At the end of the operation the advice provider will contain both Merkle trees. |
| mtree_merge - (16 cycles) |
[R, L, …] | [M, …] | Merges two Merkle trees with the provided roots R (right), L (left) into a new Merkle tree with root M (merged). The input trees are retained in the advice provider. |
| mtree_verify - (1 cycle) |
[V, d, i, R, …] | [V, d, i, R, …] | Verifies that a Merkle tree with root \(R\) opens to node \(V\) at depth \(d\) and index \(i\). Merkle tree with root \(R\) must be present in the advice provider, otherwise execution fails. |
Last update:
January 17, 2024
Authors: