In a previous article, I introduced Merklix trees as a way to cryptographically describe an unordered set or map. It is possible to produce proof that an element is contained or absent of the datastructure in o(ln(n)), and use these proof to mutate the structure, even without knowing its full content.
I will now explain how this can be used to help handling the UTXO set in blockchain technologies like Bitcoin.
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: