liamsi
commented
1 year ago The only downside I can think of, when incorporating the ordering into the hasher, is that it will have to happen on every inner node (instead of currently every leaf only), which will make proving and verification slower (probs negligible but should be confirmed in a benchmark too).
Not really a downside but sth to keep in mind is that the hasher will need to return an error. This might affect other parts of the API as well.
The NMT guarantees lexicographical ordering and hence generated proofs follow this ordering as well. The verification logic does not enforce this though currently. This might not be a big deal as verification would fail if ordering is different though it makes it harder to reason about this and it is obviously better to enforce ordering there too.
@musalbas suggested to enforce ordering in the hasher directly. While it might seem better to follow the current pattern and fail much earlier (when adding data to the tree and not only later when hashing/creating the root), having the ordering enforced while hashing is better from a consistency perspective. it would also immediately resolve the ordering guarantee during verification as well.