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.

This PR prepares the ground for supporting several tree formats. This addresses #10 and supersedes #42 and #43

• It adds a Tree trait that supports operations like insertion and iteration over the set of child nodes, then re-implements Node in terms of this trait.
• This trait is parameterized by another trait, describing the key and value formats by requiring the definition of the Key and Value types, making is easier to switch between a nibble-/byte-/binary-based key type.
• The Multiproof structure is parameterized by the tree type, to be able to reconstruct different types of trees from a single proof type.
• It makes rebuild a method of Multiproof, which is the first step in supporting different proof types (the end goal is to support proofs that use instructions and proofs that do not)
• It also effectively deprecates the use of the LEAF(i) operand i as expressed in #19

This is preparation work for the support of binary trees.

• It introduces a Key trait that will have to be implemented by all objects that can be used as keys;
• It introduces BinaryKey that implements Key and represents a bit-wise string;
• It rewrites ByteKey and NibbleKey as an implementation of Key; and
• it moves ByteKey, NibbleKey and BinaryKey to their own modules.

A series of changes to clean the code up:

• Remove the use for NibbleKey::new since From<Vec<u8>> has been implemented;
• Rely on hex::decode instead of having a custom function
• Change the implementation of display to write the regular data, instead of writing its "debug" version
• Remove some comments

I realize that the reason @sina created a custom hex conversion function might have been done with the hope of reducing the size of the final binary. Is that so?

This is preparation work for #28

So far it wasn't possible to insert a key into an empty node. This now makes it possible (by replacing the empty node with a leaf), and is closer to the behavior of geth. It is also going to be necessary in order to insert null entries for proofs.

If a tree includes embedded nodes (those with encoding < 32), the computed hash() is wrong. This is due to the fact that rlp.encode([[1, 2], [3, 4]]) != rlp.encode([[1, 2], rlp.encode([3, 4]]). I.e. the parent node shouldn't serialize the encoding of the embedded node, but the embedded node in raw form (array).

Edit: the expected root was generated by the js merkle-patricia-tree library.

This PR prepares the ground for supporting several tree formats. This addresses #10 and supersedes #42

As a result, it adds a trait Tree that supports operations like insertion and iteration over the set of child nodes, then re-implements Node in terms of this trait.

This is in preparation for supporting several tree formats (which is the basis for subsequently supporting several instruction & proof formats).

• It makes insert act on a mutable self reference, instead of using the insert_leaf global function.
• It declares a Tree trait, that implements functions are a tree structure needs to implement to be able to work with this algorithm.

insert_leaf is still part of the current API, although it will be removed at a later time, when other tree structures are fully supported.

In make_multiproof I think the goal had been to truncate keys of keyvals when parsing an Extension, but the key is simply being cloned:

https://github.com/gballet/multiproof-rs/blob/269211ec3dee159bb46314390e6d8cbda40381e1/src/lib.rs#L492-L499

The current hexary Patricia Tree structure used in Ethereum poses some challenges and dropping it for another more manageable structure like binary or balanced trees is often discussed.

As a result, we want to abstract all tree interactions through a trait to be able to easily change the underlying tree implementation.

rustfmt is not available on ARM, so I can't run it. Now that the code is going to become a bit more stable, the linter in circle CI needs to be re-enabled and cargo fmt needs to be run in nightly mode.

The way binary keys are being implemented is making it impossible to implement Index<Range<usize>>. This approach uses an iterator and currently only implements it on BinaryTree.

Left to do:

• [ ] Use IntoIterator
• [ ] Use FromIterator
• [x] Get rid of rewind

This PR needs to be rebased, only applies iterators to Extension nodes and is only here for discussing the following points:

• [ ] Index's index -> &[u8] makes it impossible to make bit keys and nibble keys as simple Vec<u8>: the data needs to be expanded in another Vec<u8> in which each byte represents one bit/nibble
• [ ] the need for rewind
• [ ] the general API and code of chop_common

This is a tracker for @s1na's question on #44

These new_* methods seem to be specific to the MPT tree. Is there maybe a way in Rust to only define them on Node and then cast a Tree to a Node when these methods are needed?

AFAIK, there isn't. This being said, indeed a difference should be made, e.g. by introducing an inherited TreeWithExtension : Tree trait.

This is more related to an EE wanting to do token transfers using this multiproof algorithm. I'm not sure if it makes sense to merge it in the repo.

EE receives an array of txes which include among other things a signature from sender and the address of the recipient. The EE also receives a multiproof. In order to make sure addresses of the sender and recipient of the tx corresponds to the leaves sent in the multiproof, the EE needs to re-construct the path to those leaves when it's verifying the multiproof. Here's my attempt at how one could do this:

• Initialize an array of addrs with same length as leaves
• When a leaf is read in via LEAF add its partial path to corresponding index of addrs, and add this index to the leaf node being pushed on stack
• In BRANCH, EXTENSION or ADD:
  • if the node popped from stack is a leaf, read its index and prepend a partial path to its addrs entry. Also add its addrs index (for the leaf) to the node being pushed on stack
  • else, read list of indices for all leaves this node is pointing to and prepend their paths with the partial path (e.g. branch idx, or extkey)
• After verification is done, all these paths need to be encoded form their nibbles form to get the addresses

Right now rebuild returns the root Node. In order to compute the root hash, the partial trie has to be walked down and up once. To improve the efficiency of verifiers we could either add a new opcode or change the semantic of the existing ones to allow the verifier to produce the correct hash once every instruction has been processed.

LEAF and EXTENSION opcodes could be modified to directly hash the node and push the hash on the stack. HASHER just reads in a hash from the sequence and doesn't need to be modified. The only question is how to handle branches, because it's not exactly clear when all the children have been added to the branch. One simple option is to introduce a HASH opcode which expects a branch node on top of stack and hashes it. There are other options too.