6

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.

5

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.

  • 1
    Ah nice, I was thinking a bit about this earlier this morning, but I hadn't thought of tries. While it's not specifically listed as a requirement, I think that @NickODell wanted to maintain the property that "anyone can create a proof that something isn't in the tree". This should perhaps be addressed in the answer. However, this could be done by proving the membership of the internal node that would be the absent element's parent and providing the full list of children, which can be checked against the internal node's hash and shows that the absent element is not included. – Murch Apr 17 '17 at 9:39
  • Perhaps to add to this, something like a bloom filter could be added to this and separate sent. Bloom filters have the occasional false positive when checking if it contains something but seems like the opposite of a bloom filter with no false positives should be possible. There are some proposals out there. – mczarnek Aug 13 '18 at 18:22
0

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

  • 1
    From what I see in the commit messages, Miller appears to be using a left-leaning red-black tree, and the tree is built from traversing the blockchain. Using LLRB with a fixed order of inserts and deletes should be deterministic (as LLRB introduce reliable rules for how to perform inserts and deletes). However, just taking the final set and creating an LLRB from it would not produce the same result. I also saw this related post on crypto.SE. – Murch Apr 17 '17 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.