Support for null keys #39

gballet · 2019-09-26T07:08:34Z

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 · 2019-09-26T09:23:56Z

src/lib.rs

+        );
+        assert_eq!(
+            proof.keyvals,
+            vec![[210, 144, 49, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 128]]


I think the leaf with key 11111111111111110000000000000000 should be sent in proof.keyvals. That's the only way the verifier can make sure that the top branch node is pointing only to one leaf, which is not the leaf we're looking for.

If I'm not mistaken, it seems for supporting null keys #25 is a requirement.

Update: For now though we can pass in a list of keys along with the multiproof and assume these keys can be trusted. Then rebuild can check that the leaf's partial key diverges from the expected key and can assume that the leaf we're looking for doesn't exist

yes, 11111111111111110000000000000000 should be present, and that's (part of) the bug.

s1na · 2019-09-26T09:54:51Z

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 · 2019-09-26T16:40:12Z

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 · 2019-09-27T09:11:15Z

Showing off that diagram generator, are we 😎 😄

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.

s1na · 2019-09-27T09:20:17Z

src/lib.rs

-                .to_string());
-            }
+                instructions.push(Instruction::LEAF(keys[0].len()));
+                rlp::encode(&Leaf(keys[0].clone(), vec![]))


yes, 11111111111111110000000000000000 should be present, and that's (part of) the bug.

Well here it could be (similar to above) rlp::encode(&Leaf(leafkey.clone(), leafval.clone())) to include 11..00..

Maybe this if *leafkey == keys[0] { condition is not necessary at all. Whatever the path, we include this leaf fully.

gballet · 2019-10-01T07:15:24Z

Showing off that diagram generator, are we sunglasses smile

You bet, I'm proud 😊

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 · 2019-10-01T10:01:42Z

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 · 2019-10-02T10:54:46Z

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 · 2019-10-24T08:30:48Z

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

This is a rewrite after many discussions, of how make_multiproof handles keys that are not present in the tree. * If a search encounters an EmptySlot then the key is considered missing and an (empty key, empty value) is inserted to point out that the key is not present in the tree. * In the case of an extension where the key and the extension part differ in at least one nibble, the hash of the extension's child is added and the full extension node is added to the proof, so prove that the tree has a different path and therefore not the one pointed by the missing key. If the missing key and extension have the same nibbles, the algorithm recurses. * In the case of a branch node, either the first byte isn't available in which case nothing is done since an EmptySlot clearly indicates that the key is missing. Otherwise, the algorithm recurses. * In the case of a leaf, the leaf that is present is added to prove that the other key is missing. Rebuilding the tree will work like before, except in the case of an empty (key, value): in that case an EmptySlot is inserted instead of raising an error. A function that checks if a key is present in the tree is also added. There is also the start of an implementation of the [] accessor for Node, which currently only works with Branch nodes.

s1na · 2019-12-18T14:21:35Z

src/lib.rs

+                let factor_length = extkey.factor_length(k);
+                // If a key has a prefix that differs from that of the extension,
+                // then it is missing in this tree and is not added to the list
+                // of shortened keys to be recursively passed down. This special


This special case is handled after the loop.

Where? 😄

gballet requested a review from s1na September 26, 2019 07:09

s1na reviewed Sep 26, 2019

View reviewed changes

s1na reviewed Sep 27, 2019

View reviewed changes

gballet added 4 commits November 1, 2019 11:04

Can generate null leaves, but no tree rebuild

ebba71a

Complete unit test + null key in rebuild

7eafa6c

Complete [] accessor

3bc8ee3

gballet force-pushed the null-keys branch from 5a05cf4 to 3bc8ee3 Compare November 1, 2019 10:24

Fix rebase hitch

02af42a

gballet merged commit d2e74a0 into master Nov 1, 2019

s1na reviewed Dec 18, 2019

View reviewed changes

s1na mentioned this pull request Dec 18, 2019

Proving exclusion of an account in the state ewasm/biturbo#53

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Support for null keys #39

Support for null keys #39

gballet commented Sep 26, 2019

s1na Sep 26, 2019

s1na Sep 26, 2019 •

edited

gballet Sep 26, 2019

s1na commented Sep 26, 2019

gballet commented Sep 26, 2019

s1na commented Sep 27, 2019

s1na Sep 27, 2019

gballet commented Oct 1, 2019 •

edited

s1na commented Oct 1, 2019

gballet commented Oct 2, 2019

s1na commented Oct 24, 2019

s1na Dec 18, 2019

Support for null keys #39

Support for null keys #39

Conversation

gballet commented Sep 26, 2019

s1na Sep 26, 2019

Choose a reason for hiding this comment

s1na Sep 26, 2019 • edited

Choose a reason for hiding this comment

gballet Sep 26, 2019

Choose a reason for hiding this comment

s1na commented Sep 26, 2019

gballet commented Sep 26, 2019

s1na commented Sep 27, 2019

s1na Sep 27, 2019

Choose a reason for hiding this comment

gballet commented Oct 1, 2019 • edited

s1na commented Oct 1, 2019

gballet commented Oct 2, 2019

s1na commented Oct 24, 2019

s1na Dec 18, 2019

Choose a reason for hiding this comment

s1na Sep 26, 2019 •

edited

gballet commented Oct 1, 2019 •

edited