Create a binary version of hex_patricia_hashed - bin_patricia_hashes #288
Description
hex_patricia_hashed in the commitment package is the implementation of the commitment that is currently used in Ethereum - Hexadecimal Patricia Merkle tree with pre-hashes keys.
hex means that the Merkle tree is hexadecimal (rather than binary), i.e. each node has up to 16 children
patricia means it follows PATRICIA design (Practical Algorithm to Retrieve Information Coded in Alphanumeric). Notable feature is compressing the runs of nodes having just 1 child, into a single node (extension and leaf nodes).
hashed means that state keys are not directly used as paths in the tree (as it would be in a conventional radix tree), but they are first pre-processed by Keccak hash function, to resist the creation of specific structures of node to trigger worst-case performances of radix trees.
We need to create a variant of this called bin_patricia_hashed, with difference that instead of 16, any node may have up to 2 children. This also means that instead of using 4 bits of the hashed key per level of the tree, we need to use 1 bit per level.
Integrating this into prototype and running two variants alongside each other, would give us information about the overhead of binary variant in terms of number of nodes, and consequently, size of commitment files.