Feature or Enhancement?

• (x) New feature
• ( ) Enhancement of existing feature

Description

Currently, the VM supports ops like hash_left and load_right to accommodate the ordinary Merkle tree construction in which the order of joining nodes matters. There is an open issue to create a XOR-hash based tree that removes the requirement to track placement during joins. An alternative simplification is to sort the registers before hashing.

Two new ops, sort_hash_left and sort_hash_final, could be used to implement this. This op will load the left and right registers, deterministically sort the two values into a vals list, then run the node hash operation on vals[0] as the left value and vals[1] as the right value, placing the resultant hash into the left register and clearing the right register. A proof would then be a sequence starting with load_left {leaf} hash_leaf_left, then a sequence with one load_right {hash} sort_hash_left per internal level of the tree, then a final load_right {hash} sort_hash_final {root}.

A new SortedTree class would be needed that makes use of this sorted hashing method to generate the tree structure, calculate the root, and generate proofs.

• sort_hash_left op
• sort_hash_right op
• sort_hash_mid op
• sort_hash_final op
• sort_hash_left_hsize op
• sort_hash_right_hsize op
• sort_hash_mid_hsize op
• sort_hash_final_hsize op
• SortedTree class
• Unit tests
• E2e tests

Additional context

For completeness, two additional ops, sort_hash_right and sort_hash_mid, should probably be included. Also, the _hsize variants should be included for optimization of proof sizes.