Hi @vbuterin, thanks for going through the paper.

The construction here indeed is different from a normal sparse Merkle tree.

The idea is to place every key in it’s correct subtree. To achieve that I calculate a parameter called **distance** which is defined as the binary separation between two keys. This parameter will tell us whether incoming key will lie in either of the subtrees or will lie in it’s own subtree. For e.g, we have values **1** and **3** in the left and right node so our tree looks some thing like this.

```
h(h(1)+h(3))
/ \
/ \
h(1) h(3)
```

Now consider an incoming key 2, for left subtree distance(1,2) is 2 while for right subtree distance(3,2) is 1. So the key 2 lies in right subtree.

An incoming key 4 will have distance(1,4) and distance(3,4) equal to 3. So in this case the key 4 does not lie in either of the subtree. And as 4 is greater than max-key 3, the root will become the left child and 4 will become the right child. For a key 0, the reverse will happen.

The parameter key for leaf node is the actual key. For inner nodes, the key parameter is max of it’s children’s keys. I have used the same parameter to make it more succinct.

No case occurs where one of the subtrees is empty, it’s either a leaf node, or a completer inner node so either 2 children or 0.

The tree gets nearly balanced as the hash function SHA256 behaves as an ideal hash function. The hash function SHA256 will take an input and output a value in the range of 0 to

2^256. This assumption is called random oracle model in cryptography.

The following explaination is taken from here.

The random oracle model is a model where all parties (e.g. algorithms, adversaries) have oracle access to a (uniformly) random function

RO : \{0, 1\}^∗ → \{0, 1\}^n

(we can be flexible about the output length, but for now let’s just insist on n bits.)

We can think of this as whenever a fresh value x is queried, the oracle chooses a random

output y. The next time that x is queried, the oracle gives back the same y as previously.

Hope this answers your questions. Please let me know if you have any other comments, I’ll appreciate that.