Support for null keys

[gballet]

This addresses #28 and adds the possibility to provide make_multiproof with keys that are not present in the tree. The result will be a leaf with no value, meant to represent a null key. The tree will be rebuilt by replacing that key with an EmptySlot.

There are currently two problems with this PR, which is created for discussion purposes:

• [ ] It doesn't generate all the keys, as evidenced by the failing unit test
• [ ] It is only looking at the leaf level, so it could generate things like extension node > branch node with only empty slots. This is actually a valid representation, yet it's not the most efficient one.

[s1na]

It is only looking at the leaf level, so it could generate things like extension node > branch node with only empty slots.

I didn't get this part, can you maybe re-phrase?

[gballet]

It is only looking at the leaf level, so it could generate things like extension node > branch node with only empty slots.

I didn't get this part, can you maybe re-phrase?

Let's assume that you have two keys key in the tree: 0x11110000 and 0x11112222, and that they both have the same extension node.

You want to prove that 0x11111111 isn't in the tree, make_multiproof would go along the 0x1111, and get no key except the one that isn't in the tree. So it will create a proof that will generate the following tree after calling rebuild:

when it could have created this tree:

[s1na]

Showing off that diagram generator, are we :sunglasses: :smile:

Hm, in my opinion both of those last two diagrams are invalid (i.e. verifier can't verify non-existence of 0x11111111 with them). I think the rebuilt trie should include the branch node and hashes for 0x11110000 and 0x11112222.

[gballet]

Showing off that diagram generator, are we sunglasses smile

You bet, I'm proud :blush:

Hm, in my opinion both of those last two diagrams are invalid (i.e. verifier can't verify non-existence of 0x11111111 with them).

The first one is a simplification, with the idea that 0x1111 yields an EmptyNode and therefore, that the key isn't present. Indeed it should be Extension(1,1,1,1) -> Branch(EmptyNode, EmptyNode, some hash, EmptyNode...). For the second diagram, it is a poor representation of a full node with only hashes.

I think the rebuilt trie should include the branch node and hashes for 0x11110000 and 0x11112222.

Well that's already what it does in the current state (more accurately: this is what it should be doing if it wasn't buggy) but why would you want to increase the proof size by adding some extra info? Is there something I'm missing on the verification side?

[s1na]

but why would you want to increase the proof size by adding some extra info?

So for example in this case of this rebuilt trie, the root hash will be different than expected by the verifier:

The verifier should have the branch node and see for itself that there's no child with nibble 1, and that the hashes also match (i.e. this is the valid trie).

[gballet]

I think I get the argument on why you should add all the data, however in the case of this example we can't use the EmptySlot because indeed the root hash would be different from that of the valid tree. i.e. this original tree:

Then it has a different root than that of

In fact, in that case the original tree is the correct proof (if you assume that ... translates to "hash of every child node except the extension node that is shown").

In the case of terminal nodes in which the value is missing (so in that case, if 11111 wasn't the common prefix to an actual value), however, Leaf(differentiated suffix, empty value) is the correct value for the proof. I am writing several unit tests to cover all these use cases and I will come up with more diagrams.

[s1na]

Hey I was tinkering with this and saw you've added a lot of good stuff!

I think rebuilding the trie and then querying to see that a key is null was a good trick. Without that the verification gets harder and it is full of edge cases... I'll have to prototype a version of turbo-token which simply rebuilds the trie and queries the keys and see how that performs