Collections

Namespace miden::core::collections contains modules for commonly-used authenticated data structures. This includes:

• A Merkle Mountain range.
• A Sparse Merkle Tree with 64-bit keys.
• A Sparse Merkle Tree with 256-bit keys.

Merkle Mountain Range

Module miden::core::collections::mmr contains procedures for manipulating Merkle Mountain Range data structure which can be used as an append-only log.

The following procedures are available to read data from and make updates to a Merkle Mountain Range.

Procedure	Description
get	Loads the leaf at the absolute position pos in the MMR onto the stack. Valid range for pos is between $0$ and $2^{32} - 1$ (both inclusive). Inputs: [pos, mmr_ptr, ...]. Output: [N, ...]. Where N is the leaf loaded from the MMR whose memory location starts at mmr_ptr.
add	Adds a new leaf to the MMR. This will update the MMR peaks in the VM's memory and the advice provider with any merged nodes. Inputs: [N, mmr_ptr, ...]. Outputs: [...]. Where N is the leaf added to the MMR whose memory locations starts at mmr_ptr.
pack	Computes a commitment to the given MMR and copies the MMR to the Advice Map using the commitment as a key. Inputs: [mmr_ptr, ...]. Outputs: [HASH, ...].
unpack	Writes the MMR who's peaks hash to HASH to the memory location pointed to by mmr_ptr. Inputs: [HASH, mmr_ptr, ...]. Outputs: [...]. Where: HASH is the MMR peak hash, the hash is expected to be padded to an even length and to have a minimum size of 16 elements. The advice map must contain a key with HASH, and its value is [num_leaves, 0, 0, 0] || hash_data, and hash_data is the data used to computed HASH. mmr_ptr is the memory location where the MMR data will be written, starting with the MMR forest (the total count of its leaves) followed by its peaks. The memory location must be word-aligned.

mmr_ptr is a pointer to the mmr data structure, which is defined as:

1. mmr_ptr[0] contains the number of leaves in the MMR
2. mmr_ptr[1..4] are padding and are ignored
3. mmr_ptr[4..8], mmr_ptr[8..12], ... contain the 1st MMR peak, 2nd MMR peak, etc.

Sparse Merkle Tree

Module miden::core::collections::smt contains procedures for manipulating key-value maps with 4-element keys and 4-element values. The underlying implementation is a Sparse Merkle Tree where leaves can exist only at depth 64. Initially, when a tree is empty, it is equivalent to an empty Sparse Merkle Tree of depth 64 (i.e., leaves at depth 64 are set and hash to [ZERO; 4]). When inserting non-empty values into the tree, the most significant element of the key is used to identify the corresponding leaf. All key-value pairs that map to a given leaf are inserted (ordered) in the leaf.

The following procedures are available to read data from and make updates to a Sparse Merkle Tree.

Procedure	Description
get	Returns the value located under the specified key in the Sparse Merkle Tree defined by the specified root. If no values had been previously inserted under the specified key, an empty word is returned. Inputs: [KEY, ROOT, ...] Outputs: [VALUE, ROOT, ...] Fails if the tree with the specified root does not exist in the VM's advice provider.
set	Inserts the specified value under the specified key in a Sparse Merkle Tree defined by the specified root. If the insert is successful, the old value located under the specified key is returned via the stack. If VALUE is an empty word, the new state of the tree is guaranteed to be equivalent to the state as if the updated value was never inserted. Inputs: [VALUE, KEY, ROOT, ...] Outputs: [OLD_VALUE, NEW_ROOT, ...] Fails if the tree with the specified root does not exits in the VM's advice provider.
peek	Emits the miden::core::collections::smt::smt_peek event, which pushes onto the advice stack the value associated with the specified key in a Sparse Merkle Tree defined by the specified root. If no values had been previously inserted under the specified key, an empty word is returned. Inputs: Operand stack: [KEY, ROOT, ...] Advice stack: [] Outputs: Operand stack: [KEY, ROOT, ...] Advice stack: [VALUE] Fails if the tree with the specified root does not exist in the VM's advice provider.

Sorted Array

Module miden::core::collections::sorted_array contains procedures for searching in sorted arrays of words. These procedures use non-deterministic advice to efficiently find values or keys in sorted data structures.

The following procedures are available:

Procedure	Description
find_word	Finds a value in a sorted array of words. Inputs: [VALUE, start_ptr, end_ptr, ...] Outputs: [is_value_found, value_ptr, start_ptr, end_ptr, ...] Where VALUE is the word to search for, start_ptr and end_ptr define the array bounds (word-aligned), is_value_found is 1 if found and 0 otherwise, and value_ptr points to the found value or the insertion point. Requirements: - Words must be sorted in non-decreasing order - start_ptr and end_ptr must be word-aligned - start_ptr <= end_ptr Cycles: 25-286 depending on case
find_key_value	Finds a key in a sorted array of (key, value) word tuples. Inputs: [KEY, start_ptr, end_ptr, ...] Outputs: [is_key_found, key_ptr, start_ptr, end_ptr, ...] Where KEY is the 4-element key to search for. The array contains pairs of words where each pair is (key, value). Requirements: - Keys must be sorted in non-decreasing order - start_ptr must be word-aligned - (end_ptr - start_ptr) must be divisible by 8 (double-word aligned) - start_ptr <= end_ptr Cycles: 25-322 depending on case
find_half_key_value	Finds a half-key in a sorted array of (key, value) word tuples. Only the two most significant elements of the key need to match. Inputs: [key_prefix, key_suffix, start_ptr, end_ptr, ...] Outputs: [is_key_found, key_ptr, start_ptr, end_ptr, ...] Where key_prefix is the most significant element and key_suffix is the second most significant element of the key to match. Same requirements as find_key_value.