Regarding Merkle sparse prefix tree vs. Merkle self-balancing search tree

[weikengchen]

In some applications, we need non-membership proofs, which would be based on Merkle prefix tree (e.g., in CONIKS and Google Key Transparency) or self-balancing search tree (e.g., AVL tree).

Preliminarily, it seems that a search tree is better than a prefix tree because its height no longer depends on the security parameters.

But, note that for a self-balancing search tree to work, it requires a few changes to the tree:

• Middle nodes need to store data, instead of just the left nodes.
• Some self-balancing data needs to be stored, too.

This would mean that the overhead of CRH for each layer is higher, roughly 1.5x for Pedersen and 2x for Poseidon.

This means that, if the number of elements is large enough (e.g., supposedly 2^32), then the prefix tree (assuming the height is 2^80), which is much easier to implement, may not be too bad compared with the search tree.