How do you create a merkle tree that lets you insert and delete elements without recomputing the whole thing?

Question

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:

1. Fast. I shouldn't need to recompute the entire thing (or half of the entire thing) to insert or remove something from the middle.

2. 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.

3. 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.

4. 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.

5. 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.

Answer 1

You can use a Merkleized binary trie.

You first hash all the elements of your set individually. In this example, I use a 3-bit hash function rather than 256-bit.

Let's say you have 5 elements in your set, and they hash to: A: 011 B: 101 C: 111 D: 001 E: 010

Now you arrange them in a tree, by using the bits of the key hash as split conditions:

root

• 0
  • 0
    • 1: D
  • 1
    • 0: E
    • 1: A
• 1
  • 0
    • 1: B
  • 1
    • 1: C

Now you associate every leaf node with the full key hash, and every internal node with the hash of its concatenated children.

The resulting root is:

• Fast to update: the number of hash operations for an add or delete is proportional to the number of bits in the hash function (and does not depend on the number of elements in the tree).
• Authentic: the root commits to the entire tree structure, so indirectly to all its leaves.
• Deterministic: the order of insert/delete operations does not affect the tree structure.

A possible optimization is to compact branches constructed from internal nodes with 1 child. This leads to the following structure:

root

• 0
  • 0: D
  • 1
    • 0: E
    • 1: A
• 1
  • 0: B
  • 1: C

Now operations are on average logarithmic in the number of elements, and all other properties remain.

Answer 2

This project satisfies properties 1 and 2, but I don't know if it satisfies property 3.