I have a merkle tree. The elements of this tree are in sorted order, so that anyone can create a proof that something isn't in the tree. So far, so good.
However, I also want to be able to add and remove elements from the tree. If I use a normal merkle tree, I have to recompute most of the tree. For example, I have the following merkle tree:
395 / \ 85 310 / \ / \ 23 62 137 172 / \ / \ / \ / \ 1 22 23 39 60 77 82 91
(I'm using addition for the hash function, as an example.)
I insert 50 to the middle of the merkle tree.
445 / \ 354 91 / \ \ 85 269 91 / \ / \ \ 23 62 110 159 91 / \ / \ / \ / \ \ 1 22 23 39 50 60 77 82 91
Every merkle branch after the 50 changed. I had to run the hash function 5 times. This would get pretty unwieldy for very big merkle trees.
I'm looking for a merkle tree with these properties:
Fast. I shouldn't need to recompute the entire thing (or half of the entire thing) to insert or remove something from the middle.
Authentic. If I have a merkle root, there should be only one tree that corresponds to that merkle root. Changing any part of the tree should cause the validation to fail.
Deterministic. (Optional) This is essentially the opposite of the previous statement. If I take the elements out of a merkle tree, and build a new merkle tree from those elements, I should get the same root hash.
Proof of existence. Someone with enough of the tree should be able to make a proof that an element is in the tree, if that element is in the tree. This proof should be reasonably small.
Proof of non-existence. Someone with enough of the tree should be able to make a proof that an element is not in the tree, if that element is not in the tree. This proof should be reasonably small.