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?