Merkle tree formation with odd number of leaves

how is the merkle tree formed when the number of leaves isn’t log base 2?
for example, say you have 110 transactions in a block. the next power of 2 would be 128 - what is put in the last 18 leaves?

the two solutions I see would be having an unbalanced tree, where you hash pairs but don’t hash up the “extra” transactions until later up the tree. branch lengths in this tree would be different. the other solution would be to duplicate the last transaction up until there are 2^n leaves, where n is the number of levels.

in the patricia tree specs, it states that a branch is a 17-item node, so this suggests that every branch has to be the same length, meaning we can’t have an unbalanced tree.

what is the solution ethereum takes? do we duplicate the last transaction, or do we create a tree as per this answer where we duplicate the last leaf to give it a sibling, hash those together, then duplicate the parent to give that a sibling, and so on.


The other natural option is to fill all the remaining leaves with empty data.

You can absolutely do non-binary tree structures like Patricia trees, but IMO they’re uglier, and binary trees are simpler and more efficient.


that makes sense, thanks for the reply. is this what the current implementation does?

Our Sparse Merkle Tree implementation precomputes all leaves with default values:

1 Like

I was asking more specifically about the current implementation for forming merkle trees inside the EVM.

How does ethereum specifically form merkle trees in the EVM?

This seems to be the more efficient solution. It seems easy enough to implement.

Unless someone can tell my why there is any meaningful benefit to repeating hashes and hashing them with themselves, I’m going to implement the bagging the peaks portion of the MMR structure from FlyClient as eluded by peter todd (in the efficient way shown in the link).

(To clarify, mmr is a more complex structure, but it is the 5 “peaks” that are getting put into a binary merkle tree)

1 Like