Lots of people like to sort the leaves of their Merkle tree as a way to prove *non*-membership.
In this blog post, I give 3 reasons why this is sub-optimal and try to convince you to almost always use a Merkle tr*i*e (prefix tree):
alinush.github.io/2023/02/05/Why-you-should-probably-never-sort-your-Merkle-trees-leaves.html
tl;dr: Merkle trees with sorted leaves are *in*secure when the digest is produced adversarially (see screenshot). Such adversarial settings actually arise in real applications like Certificate Transparency (CT).
Such mis-ordering completely breaks security: a malicious server can prove that element 8 *is NOT in* the tree while *at the same time* also proving that 8 *is in* the tree. This makes any Merkle proof meaningless to any client.
e.g., here's an evil non-membership proof for 8:
...and here's an evil membership proof 8 too. Not good :)
Not all hope is lost though. In some settings, it is safe to assume the Merkle tree (and thus the Merkle root) is computed correctly and thus this attack cannot happen. e.g., in BFT systems or "blockchains."
But not in key transparency, where there's a single malicious server.
Even so, Merkle trees with sorted leaves have other problems and should likely be avoided: (1) they cannot be updated efficiently and (2) they have sub-optimal proof sizes.
To avoid all these pains, use Merkle tr*i*es! They are simple & secure, even with adversarial digests.
alin.apt
@alinush407
I put the "crypto" in "cryptocurrency" | Founding Team & Head of Cryptography at @AptosLabs