Merkle tree formation with odd number of leaves


#1

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.


#2

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.


#3

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


#4

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




#5

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


#6

How does ethereum specifically form merkle trees in the EVM?