trie-db: Fetch the closest merkle value

[lexnv]

This PR adds support for fetching the merkle value directly from the trie-db.

• Adds get_closest_merkle_value on the Trie trait
• TrieDb iterates over the nibbles of the provided key
  • At each iteration DB is queried for the containing node
  • last value encountered on the path from the root to the key is returned
• During trie traversal, the internal recorder is updated with trie actions
  • This should make other trie queries to the key more efficient
• Test with HashedValueNoExtThreshold<1> as trie layout and value update at given key

We could build on this PR to have support for recorded Merkel Value in the cache.

Would love to get your thoughts on this @cheme @arkpar 🙏 (For reference @tomaka to ensure we don't break anything wrt to compatibilities between smoldot and substrate)

Part of https://github.com/paritytech/substrate/issues/14550.

// @paritytech/subxt-team

[arkpar]

After reading the spec more carefully, I think the logic here requires some changes. We need to return the descendant of the provided key, not just the lower bound. Basically this means traversing the tree as usual, but for Leaf, Extension and NibbledBranch nodes if you run out of key, just check if the current node key slice extends the remainder.

if slice.starts_with(&partial) {
  return Ok(Some(hash)))
else
  return Ok(None)
}