First, two desired properties for the binary tree structure and merkleization rule. Then, claims that neither M1, M2, M3, nor M4 satisfy both of these desired properties.
Property: Access list-witness correspondence. For a given state tree, each access list uniquely determines a minimal witness. In particular, minimal witnesses are independent of block execution.
Property: Efficiently computable. The cost to merkleize a tree is less than 50n hashes in practical (i.e. average tree depth<50) cases, where n is the number of leaves to be merkleized.
Claim. Binary radix trees like M1, M2, and M3 don’t satisfy the access list-witness correspondence property.
Proof sketch: Consider an access list from a binary radix state tree. When a leaf in the access list is deleted from state after block execution, if the deleted leaf’s parent node has an extension (“prefix”, “edge label of length >1”) as its remaining child, then the extension is extended to preserve the radix property. Information about whether this remaining child is an extension is needed in a witness. Any leaves can be removed, and the access list does not specify which leaves are removed, so a witness must include this extra extension info for all hash nodes which may be extensions and may be extended due to leaf deletions. This extra data makes witnesses non-minimal. So M1, M2, and M3 don’t satisfy the access list-witness correspondence property.
Claim. Sparse trees like M4 don’t satisfy the efficiently computable property.
Proof sketch: In a sparse tree, a leaf requires 256 hashes to merkleize. And n leaves require ~256n hashes to merkleize. And ~256n>50n. So sparse trees are not efficiently computable.
Are there any proposals for a tree structure and merkleization rule which satisfy both of these desired properties?