Implement domain separation for compact sparse Merkle tree

[Al-Kindi-0]

As part of the design in #22 for a tiered compact SMT, we need to create domain separation between internal nodes and leaf nodes i.e. each type of node should be hashed differently.
The rule that was proposed by @bobbinth is the following:

1. Internal nodes are hashed as hash(left,right) where right and left are the left and right child, respectively.
2. Leaf nodes are hashed as hash(r,v) where r is the remaining key (i.e. with the prefix leading to the current position removed) and v is the values associated with key. Further, we set one of the capacity registers to the depth i.e. 16, 32, 48 or 64.

At the moment, accessing the capacity registers externally is not possible to realize point 2. The following issue aims at exposing some methods from RPO so that point 2 above can be implemented in the final implementation of our compact SMT #22 .

[bobbinth]

I think the only method we need to support this for (at least for now) is merge(). This would cover the SMT use case as well as the program hashing use case in the VM (where we need to differentiate between JOIN and SPLIT blocks etc.).

I'm thinking the new function could look like this:

pub fn merge_in_domain(values: &[RpoDigest; 2], domain: Felt) -> RpoDigest

The domain element could go into the second element of the capacity section (since the first element is used for padding purposes).

[grjte]

Closed by #40

[hackaugusto]

sorry to hijack the closed issue. can we document why we didn't implement the domain separation in for the compact SMT?

[bobbinth]

We do use it in compact SMT but only for computing leaf nodes, which are computed using merge_in_domain() function.

[hackaugusto]

Aha, I assume you mean for PR #45 , I only checked #27 , thanks! (hahhaa, I mixed this two PRs up because #27 was sitting on next for a while, and in my mind we didn't have a SMT in january, sorry for the confusion!)