<p><a href="https://github.com/amiller/redblackmerkle" rel="nofollow noreferrer">This project</a> satisfies properties 1 and 2, but I don't know if it satisfies property 3.</p>

CC BY-SA 3.0
2017-04-17T08:30:50.847Z
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](https://crypto.stackexchange.com/q/22669/8801).
Murch
CC BY-SA 3.0
2017-02-16T04:34:46.073Z
2017-02-16T04:34:46.073Z
Nick ODell
<p>You can use a Merkleized binary trie.</p>

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

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

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

<p>root</p>

<ul>
<li>0

<ul>
<li>0

<ul>
<li>1: D</li>
</ul></li>
<li>1

<ul>
<li>0: E</li>
<li>1: A</li>
</ul></li>
</ul></li>
<li>1

<ul>
<li>0

<ul>
<li>1: B</li>
</ul></li>
<li>1

<ul>
<li>1: C</li>
</ul></li>
</ul></li>
</ul>

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

<p>The resulting root is:</p>

<ul>
<li>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).</li>
<li>Authentic: the root commits to the entire tree structure, so indirectly to all its leaves.</li>
<li>Deterministic: the order of insert/delete operations does not affect the tree structure.</li>
</ul>

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

<p>root</p>

<ul>
<li>0

<ul>
<li>0: D</li>
<li>1

<ul>
<li>0: E</li>
<li>1: A</li>
</ul></li>
</ul></li>
<li>1

<ul>
<li>0: B</li>
<li>1: C</li>
</ul></li>
</ul>

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

CC BY-SA 3.0
2017-04-17T09:39:15.913Z
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
CC BY-SA 4.0
2018-08-13T18:22:16.950Z
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
CC BY-SA 3.0
2017-04-17T08:50:11.280Z
2017-04-17T09:28:23.073Z
2017-04-17T09:28:23.073Z
Pieter Wuille
<p>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.</p>

<p>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:</p>

<pre><code>                    395
          /                     \
        85                       310
    /        \               /        \
  23          62          137          172
 /  \        /  \        /   \        /   \
1    22    23    39    60     77    82     91
</code></pre>

<p>(I'm using addition for the hash function, as an example.)</p>

<p>I insert 50 to the middle of the merkle tree.</p>

<pre><code>                               445
                       /                  \
                    354                    91
          /                     \           \
        85                       269         91
    /        \               /        \       \
  23          62          110          159     91
 /  \        /  \        /   \        /   \     \
1    22    23    39    50     60    77     82    91
</code></pre>

<p>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.</p>

<p>I'm looking for a merkle tree with these properties:</p>

<ol>
<li><p><strong>Fast.</strong> I shouldn't need to recompute the entire thing (or half of the entire thing) to insert or remove something from the middle.</p></li>
<li><p><strong>Authentic.</strong> 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.</p></li>
<li><p><strong>Deterministic.</strong> (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.</p></li>
<li><p><strong>Proof of existence.</strong> 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.</p></li>
<li><p><strong>Proof of non-existence.</strong> 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.</p></li>
</ol>

<merkle-tree>
How do you create a merkle tree that lets you insert and delete elements without recomputing the whole thing?
Nick ODell
# How do you create a merkle tree that lets you insert and delete elements without recomputing the whole thing?

(Asked by: username_0 on 2017-02-16)

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.

**Tags:** merkle-tree


---

## 2 answers

### Answer by username_2 on 2017-04-17. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_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 @username_0 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.  
> **username_3**: 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.  

---

### Answer by username_0 on 2017-02-16. Score: 0

[This project](https://github.com/amiller/redblackmerkle) satisfies properties 1 and 2, but I don't know if it satisfies property 3.

> **Comments:**
> **username_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](https://crypto.stackexchange.com/q/22669/8801).  

---

