SimpleSmt: distinguish between depth of tree and depth of insertions

[plafer]

I propose we add the ability to instantiate a tree which has depth D, but where all insertions are done at depth d, where d < D.

Background

The "created notes" tree is currently constructed as:

• Each batch has a tree of depth 12 of all created notes in all transactions (i.e. up to $2^{12}$ created notes per batch)
• A block creates a tree of depth 8, containing all the created note roots from the batches it contains (i.e. up to $2^{20}$ created notes per block)

The natural way to think of the "notes created" tree in a block is a tree of depth 20, which contains the $2^8$ subtrees of depth 12 (one per batch, where the tree is padded with empty trees if there are not enough batches). A tree where no notes were created would have root E20 (i.e. the root of the empty tree of depth 20).

To allow us to create such a tree, we need to be able to create a tree of depth 20, where all leaves are inserted at depth 8 (the leaves are the roots of the batches' created notes trees). Note that the current MASM mtree_set already supports this behavior; this issue is about allowing Rust code to easily build such a tree.

In comparison, the current API forces us to create a tree of depth 8. There are a few drawbacks:

1. A transaction batch with no created notes (i.e. with root E12) modifies the root of the block created notes tree
2. Transaction batches with no created notes incur a cost in the block kernel (derives from 1.)
3. Unintuitive: the root of an empty block's created notes tree is not E20. In fact, it isn't even E8, because each transaction batch modifies its root.

[bobbinth]

I wonder if we could achieve the same goal by adding set_subtree() method to the current SimpleSmt. This method could look like so:

pub fn set_subtree(&mut self, index: u64, subtree: SimpleSmt) -> Result<Word, MerkleError>

This method would compute the insertion depth based on depth difference between the subtree and the SMT being updated.

Then, we can use this method to manipulate the note tree as follows:

• We instantiate an empty SimpleSmt of depth 21.
• Then, we set subtrees of depth 13, which will be inserted at depth 8.

[plafer]

Great idea, this results in a much cleaner API.

[plafer]

Closed with #232