Merkle tree are awesome. They allow to hash an ordered set of elements and provide a way, known as a Merkle proof, to prove that a given element is at some position in the set without having to provide the whole set. While this is a very useful tool, the fact that it is ordered can be somewhat troublesome. Inserting or removing an element in the middle of the set will require significant work and, more generally, 2 sets containing the same elements, but in a different order will yield 2 radically different trees.
Today, I’d like to introduce a new tool to the software engineer toolbox, which, as far as I know – and that probably tells more about my searching-foo than anything else, hasn’t been proposed before. The goal is to hash an unordered set in such a way that:
- The end result is the same, no matter in what way the tree is created
- Insertion and deletion are ln(n)
- It is possible to produce a proof that an element is contained in the set without producing the set
Continue reading →