Remarks on implementation:

[acerone85]

Some remarks and suggestions to improve on the implementation:

1. There are some unnecessary extra allocations, e.g. in the function sha256_32 you allocate a buffer where you move data. In practice, you can move the buffer out of the hasher:

#[inline(always)]
fn sha256_32(data: &[u8]) -> Bytes32 {
    let mut hasher = Sha256::new();
    hasher.update(data);
    let out = hasher.finalize();
    // Avoid an extra allocation/copy  by returning `out`'s internal buffer
    let arr: [u8; 32] = *(out.as_ref());
    arr
}

2. The implementation is fairly low level, which makes it difficult to follow and make the implementation error prone. For example, the function subtree_root_sparse will panic if an empty tree is passed as input. Also, some implementation details are not clear, e.g. why the check if i + 1 < level_nodes.len() && level_nodes[i + 1].0 == (idx ^ 1) { is used to test if the sibling of a node is present.

3. Judging from the implementation, the structure implemented is more a 256-ary sparse merkle tree, rather than a binary one. In general, using a size 256 as the radix of the tree might result in bigger proofs, and a smaller Radix is preferred (for example, many variations of Sparse Merkle trees such as Merkle Patricia Tries(https://ethereum.org/developers/docs/data-structures-and-encoding/patricia-merkle-trie/) and Jellyfish Merkle trees` (https://developers.diem.com/papers/jellyfish-merkle-tree/2021-01-14.pdf) have a radix of 16.

4. In general, when programming in rust it is easier to leverage the NewType pattern (https://rust-unofficial.github.io/patterns/patterns/behavioural/newtype.html) to guarantee strong invariants at compile time. For example, the function stem_bit returns a u8, but in practice one could define its own Bit enum to guarantee that the result is either 0 or 1.

#[repr(u8)] // Will be represented in memory as a u8
pub enum Bit {
Zero, // will be represented in memory as `00000000`
One  // will be represented in memory as `00000001`
}

5. When implementing Sparse Merkle Tries or any variant, it is easier to store all nodes in a HashMap<KeyPrefix, Node>, where KeyPrefix is a sequence from 0 to 32 bytes, which needs to satisfy the trait bounds for HashMap::Key (e.g. Hash), and Node contains a bitmap of which children are defined. If the i-th bit of the bitmap is set, then the node has a child at position i, otherwise it has no child at that position. When traversing the tree from the root to a leaf, it makes sense to define an iterator that helps you select the next node to be traversed, rather than relying on a low-level implementation.

6. Depending on whether a value of 000...000 for a leaf is the same as the leaf not being present, the implementation might not be collision resistant. From what I understand, because h32or64 returns 00...0 when hashing the concatenation of 00...0 and 00...0, the empty tree and a tree whose all leaves have value 00...0 (or just a leaf with that value) will have the same root hash.

Another question from my side, what is the rationale behind the need for Sparse Merkle trees?

[vans163]

Another question from my side, what is the rationale behind the need for Sparse Merkle trees?

(Addressing the other points might be not needed if we change implementations)

The rationale is we need something to prove k/v pairs in the contract_state and this type of tree seems to do 3 things well:

1. support unordered insertions and deletions (delete is setting value to 0::256)
2. update is really fast compared to other trees we tried. singlethreaded update 10k in a 100m size tree is 7ms on 7950x Ryzen.
3. its not complex mathematically like KZG (which does offer same properties but much shorter proofs BUT the shortness of the proofs kinda dies VS solidity as solidity doesn't accept compressed points so even a tiny proof is at least 192bytes)

What is not clear yet is how the DB layout will look like.

Do you think its worth trying jellyfish? or patricia-merkle-trie?

Goals are >

1. Speed of in-slot update so we can hit 500ms slot times

Size of stored tree is fine and proof length is not TOO bad, as STARKS will prob become more standard soon, so deep nodes and short nodes will be same size proof. Also having the extra 10-20nodes is not too bad thats like an extra 320-640bytes + 10-20 hashes, even for solidity its quite cheap.

[vans163]

3. Judging from the implementation, the structure implemented is more a 256-ary sparse merkle tree, rather than a binary one. In general, using a size 256 as the radix of the tree might result in bigger proofs, and a smaller Radix is preferred (for example, many variations of Sparse Merkle trees such as Merkle Patricia Tries(https://ethereum.org/developers/docs/data-structures-and-encoding/patricia-merkle-trie/) and Jellyfish Merkle trees` (https://developers.diem.com/papers/jellyfish-merkle-tree/2021-01-14.pdf) have a radix of 16.

This implementation was mostly written by the help of AI based off https://eips.ethereum.org/EIPS/eip-7864 + optimized for update speed.

and ai responded saying this

3. “256‑ary” vs binary radix and proof size

Reviewer:

This is mostly a terminology mismatch.

What you currently have is:

A binary tree over stems (the first 31 bytes → 248 bits).

At each stem, a binary subtree of height 8 (256 leaves) over the last byte (subindex).

So the radix at every level is 2 (binary). The “256” is the number of leaves in the local subtree for a stem, not the branching factor of the global tree.

Proof size:

Inside the 256‑leaf subtree: 8 siblings (one per level of that 8‑depth binary tree).

Along the stem path: one sibling per internal node from root to stem leaf.
Because you build a compressed tree over stems, this is O(log2(#stems)), not 248.

So total sibling hashes ≈ log2(#stems) + 8.

You can explicitly explain that to the reviewer; you’re not using a 256‑ary trie (which would indeed have very fat nodes and large per‑level proofs).

If you wanted to move closer to a nibble‑radix design (like the 16‑ary Patricia / Jellyfish tries) you’d restructure keys into 4‑bit chunks and store a bitmap over 16 children per node. That’s a different design choice, not a bug in what you currently have.