bloock_smt/

node.rs

//! # Node
//!
//! `Node` is a data structure in charge of storing all information relative to a single node of a tree.
//! It basically contains information about three elements:
//! * The node *key*, which is used to represent the node inside the tree structure.
//! * The node *index*, which represents the set of nodes that can hang from that node's subtree,
//! working as a mask. The index for all nodes (*N*) belonging to the subtree of a node (*n*)
//! must start with exactly the same bits as node *n*'s index does.
//! * The keys of the node's children, necessary to work our way down the tree.
//!
//! We conceive three types of nodes:
//! * `Root`: this type of node has no index. The reason behind it is that it represents the
//! hole tree, and no index can englobe the nodes with index starting with a 0 bit, and also
//! nodes starting at 1.
//! * `Leaf`: this type of node has no children. Hence, their index value is exactly the same
//! as their key value, as they only have to represent themselves.
//! * `Intermediate`: this type of node can have by children leaves and other intermediate
//! nodes, and do have index.
//!
//! ## Datastructure
//!
//! The Node is represented by:
//!
//! * `key` - Key value that represents the node inside the tree structure. It is obtained by merging
//! the child keys. If the node is a leaf, this value is already provided by the user.
//! * `depth` - Index depth of the node. Index depth can be understand as the number of index bits
//! already covered by the node's parent. For a root node type this field is set to 0, although it
//! is theoretically speaking not the fact.
//! * `index_len` - Number of additional bits that would need to be added into a parent node index,
//! for it to be able to represent as precisely as possible the current node's children.
//! * `index` - The index value.
//! * `left_child` - The key value of the left child. Must be *None* in case of a leaf node.
//! * `right_child` - The key value of the right child. Must be *None* in case of a leaf node.

#[derive(Debug)]
pub struct Node<T> {
    key: T,
    depth: u16,
    index_len: u16,
    index: Option<T>,
    left_child: Option<T>,
    right_child: Option<T>,
}

impl<T> Node<T> {
    /// Creates a new node object with the given parameters.
    ///
    /// # Arguments
    /// * `key` - Key value of the node.
    /// * `depth` - Index depth: first useful bit of its index.
    /// * `index_len` - Number of useful index bits. This value is not used for leaves.
    /// * `index` - Index it is representing.
    /// * `left_child` - For nodes it represents the key of its left child and for leaves its own key.
    /// * `right_child` - For nodes it represents the key of its right child and for leaves its own key.
    ///
    pub fn new(
        key: T,
        depth: u16,
        index_len: u16,
        index: Option<T>,
        left_child: Option<T>,
        right_child: Option<T>,
    ) -> Node<T> {
        Node::<T> {
            key: key,
            depth: depth,
            index: index,
            index_len: index_len,
            left_child: left_child,
            right_child: right_child,
        }
    }

    /// Returns a boolean value that tells if it represents a leaf.
    ///
    pub fn is_leaf(&self) -> bool {
        self.left_child.is_none() && self.right_child.is_none()
    }

    /// Returns a boolean value that tells if it represents the root. For a node to be a root it must:
    /// * Have `depth` == 0 &&
    /// * Have `index_len`== 0 &&
    /// * Not be a leaf
    pub fn is_root(&self) -> bool {
        !self.is_leaf() && self.depth == 0 && self.index_len == 0
    }

    /// Returns a boolean value that tells if it represents a intermediate node. For a node to be intermediate it must:
    /// * Not be a leaf.
    /// * Not be a root.
    pub fn is_intermediate(&self) -> bool {
        !self.is_leaf() && !self.is_root()
    }

    /// Returns a reference to the key representing the node calculated by merging its childs.
    ///
    pub fn get_key(&self) -> &T {
        &self.key
    }

    /// Returns the first useful bit of the node index.
    ///
    pub fn get_depth(&self) -> &u16 {
        &self.depth
    }

    /// Sets the first useful bit of the node index.
    ///
    pub fn set_depth(&mut self, depth: u16) {
        self.depth = depth;
    }

    /// Returns the first useful bits of the node index.
    ///
    pub fn get_index_length(&self) -> &u16 {
        &self.index_len
    }

    /// Sets the amount of useful bits of the node index.
    ///
    pub fn set_index_length(&mut self, index_len: u16) {
        self.index_len = index_len;
    }

    /// Returns the node index.
    ///
    pub fn get_index(&self) -> &Option<T> {
        &self.index
    }

    /// Returns the key of the left child. It will be *None* if the node represents a leaf.
    ///
    pub fn get_left_child(&self) -> &Option<T> {
        &self.left_child
    }

    /// Returns the key of the right child. It will be *None* if the node represents a leaf.
    ///
    pub fn get_right_child(&self) -> &Option<T> {
        &self.right_child
    }
}

impl<T> From<Node<T>> for (T, Vec<u8>)
where
    T: AsRef<[u8]> + Copy,
{
    fn from(item: Node<T>) -> Self {
        let mut bytes: Vec<u8> = vec![];
        if item.is_root() {
            bytes.push(0u8);
            bytes.extend(item.get_left_child().unwrap().as_ref());
            bytes.extend(item.get_right_child().unwrap().as_ref());
        } else if item.is_leaf() {
            bytes.push(1u8);
            bytes.extend(&u16::to_be_bytes(*item.get_depth()));
        } else {
            bytes.push(2u8);
            bytes.extend(&u16::to_be_bytes(*item.get_depth()));
            bytes.extend(&u16::to_be_bytes(*item.get_index_length()));
            bytes.extend(
                &item.get_index().unwrap().as_ref()
                    [0..((*item.get_depth() + *item.get_index_length() - 1) / 8 + 1) as usize],
            );
            bytes.extend(item.get_left_child().unwrap().as_ref());
            bytes.extend(item.get_right_child().unwrap().as_ref());
        }
        (*item.get_key(), bytes)
    }
}

pub use crate::error::SmtError;
use std::convert::TryFrom;
use std::convert::TryInto;

impl<T> TryFrom<(T, Vec<u8>)> for Node<T>
where
    T: AsRef<[u8]>
        + Copy
        + std::convert::TryFrom<Vec<u8>>
        + std::convert::Into<Vec<u8>>
        + std::fmt::Debug,
    T::Error: std::fmt::Debug,
{
    type Error = SmtError;
    fn try_from(mut item: (T, Vec<u8>)) -> Result<Self, Self::Error> {
        let t_len = (item.0.into() as Vec<u8>).len();
        let mut second_element = item.1.split_off(1);
        match item.1[0] {
            0u8 => {
                if second_element.len() < t_len {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from("Vector not long enough to obtain left child."),
                    });
                }
                let right = second_element.split_off(t_len);
                let left_key = second_element.try_into(); //cannot be err
                let right_key = right.try_into();
                if right_key.is_err() {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from("Vector not long enough to obtain right child."),
                    });
                }
                Ok(Self::new(
                    item.0,
                    0,
                    0,
                    None,
                    Some(left_key.unwrap()),
                    Some(right_key.unwrap()),
                ))
            }
            1u8 => {
                if second_element.len() < 2 {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from(
                            "Not enough bytes to obtain the depth (at least 3).",
                        ),
                    });
                }
                let depth = u16::from_be_bytes(second_element[0..2].try_into().unwrap());
                Ok(Self::new(
                    item.0,
                    depth,
                    t_len as u16 * 8 - depth,
                    Some(item.0),
                    None,
                    None,
                ))
            }
            2u8 => {
                if second_element.len() < 2 {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from(
                            "Not enough bytes to obtain the depth (at least 3).",
                        ),
                    });
                }
                let depth = u16::from_be_bytes(second_element[0..2].try_into().unwrap());
                if second_element.len() < 4 {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from(
                            "Not enough bytes to obtain the index length (at least 5).",
                        ),
                    });
                }
                let index_len = u16::from_be_bytes(second_element[2..4].try_into().unwrap());
                let first_index_byte: usize = 0;
                let last_index_byte: usize = ((depth + index_len - 1) / 8).into();
                let bytes_len: usize = last_index_byte - first_index_byte + 1;
                second_element.drain(0..4);
                if bytes_len > second_element.len() {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from("Not enough bytes to obtain the index."),
                    });
                }
                let mut left = second_element.split_off(bytes_len);
                if t_len > left.len() {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from("Not enough bytes to obtain the left key."),
                    });
                }
                let right = left.split_off(t_len);
                if t_len > right.len() {
                    return Err(SmtError::CorruptedData {
                        key: format!("{:#?}", item.0),
                        condition: String::from("Not enough bytes to obtain the right key."),
                    });
                }
                second_element.append(&mut vec![0u8; t_len - bytes_len]);
                Ok(Self::new(
                    item.0,
                    depth as u16,
                    index_len as u16,
                    Some(second_element.try_into().unwrap()),
                    Some(left.try_into().unwrap()),
                    Some(right.try_into().unwrap()),
                ))
            }
            _ => Err(SmtError::CorruptedData {
                key: format!("{:#?}", item.0),
                condition: String::from(
                    "Malformed node (node value does not start with 0, 1 or 2).",
                ),
            }),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_new() {
        let node: Node<[u8; 32]> = Node::new(
            [1u8; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.get_key(),
            &[1; 32],
            "The root new node is not the one expected."
        );
        assert_eq!(
            node.get_depth(),
            &3,
            "The index_lenght wasn't correctly assigned."
        );
        assert_eq!(
            node.get_index_length(),
            &10,
            "The index_lenght wasn't correctly assigned."
        );
        assert_eq!(
            node.get_index(),
            &Some([2u8; 32]),
            "The index wasn't correctly assigned."
        );
        assert_eq!(
            node.get_left_child().unwrap(),
            [2u8; 32],
            "The left child wasn't correctly assigned."
        );
        assert_eq!(
            node.get_right_child().unwrap(),
            [3u8; 32],
            "The right child wasn't correctly assigned."
        );
    }

    #[test]
    fn test_new_empty() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 3, 10, None, None, None);
        assert_eq!(
            node.get_key(),
            &[1u8; 32],
            "The root new node is not the one expected."
        );
        assert_eq!(
            node.get_depth(),
            &3,
            "The index_lenght wasn't correctly assigned."
        );
        assert_eq!(
            node.get_index_length(),
            &10,
            "The index_lenght wasn't correctly assigned."
        );
        assert_eq!(
            node.get_index(),
            &None,
            "The index wasn't correctly assigned."
        );
        assert_eq!(
            node.get_left_child(),
            &None,
            "The left child wasn't correctly assigned."
        );
        assert_eq!(
            node.get_right_child(),
            &None,
            "The right child wasn't correctly assigned."
        );
    }

    #[test]
    fn test_get_key() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.get_key(),
            &[1; 32],
            "The root new node is not the one expected."
        );
    }

    #[test]
    fn test_get_key_empty() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 3, 10, None, None, None);
        assert_eq!(
            node.get_key(),
            &[1; 32],
            "The root new node is not the one expected."
        );
    }

    #[test]
    fn test_get_index_length() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.get_index_length(),
            &10,
            "The correct index_length value wasn't returned."
        );
    }

    #[test]
    fn test_get_index_length_empty() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 3, 252, None, None, None);
        assert_eq!(
            node.get_index_length(),
            &252,
            "The correct key value wasn't returned."
        );
    }

    #[test]
    fn test_get_index() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.get_index(),
            &Some([2u8; 32]),
            "The correct index_lenght value wasn't returned."
        );
    }

    #[test]
    fn test_get_index_empty() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 3, 252, None, None, None);
        assert_eq!(
            node.get_index(),
            &None,
            "The correct key value wasn't returned."
        );
    }

    #[test]
    fn test_get_left_child_some() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.get_left_child().unwrap(),
            [2u8; 32],
            "The correct left child value wasn't returned."
        )
    }

    #[test]
    fn test_get_left_child_none() {
        let node: Node<[u8; 32]> =
            Node::new([1; 32], 3, 10, Some([2u8; 32]), None, Some([3u8; 32]));
        assert_eq!(
            node.get_left_child(),
            &None,
            "The correct left child value wasn't returned."
        )
    }

    #[test]
    fn test_get_right_child_some() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.get_right_child().unwrap(),
            [3u8; 32],
            "The correct right child value wasn't returned."
        )
    }

    #[test]
    fn test_get_right_child_none() {
        let node: Node<[u8; 32]> =
            Node::new([1; 32], 3, 10, Some([2u8; 32]), Some([2u8; 32]), None);
        assert_eq!(
            node.get_right_child(),
            &None,
            "The correct right child value wasn't returned."
        )
    }

    #[test]
    fn test_is_leaf() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 3, 10, None, None, None);
        assert_eq!(
            node.is_leaf(),
            true,
            "The return was false although it is a leaf."
        )
    }

    #[test]
    fn test_is_intermediate() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert!(
            !node.is_leaf(),
            "The return was true although it is a full node."
        );
        assert!(
            node.is_intermediate(),
            "The return was true although it is a full node."
        )
    }

    #[test]
    fn test_is_root() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 0, 0, None, Some([2u8; 32]), Some([3u8; 32]));
        assert_eq!(
            node.is_root(),
            true,
            "The return was true although it is a full node."
        )
    }

    #[test]
    fn test_is_not_root_node1() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.is_root(),
            false,
            "The return was true although it is a full node."
        )
    }

    #[test]
    fn test_is_not_root_node2() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 3, 10, None, None, None);
        assert_eq!(
            node.is_root(),
            false,
            "The return was true although it is a full node."
        )
    }

    #[test]
    fn test_is_not_root_leaf() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            3,
            10,
            Some([2u8; 32]),
            Some([2u8; 32]),
            Some([3u8; 32]),
        );
        assert_eq!(
            node.is_root(),
            false,
            "The return was true although it is a full node."
        )
    }

    #[test]
    fn from_root_to_bytes() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 0, 0, None, Some([1u8; 32]), Some([2u8; 32]));
        let (key, result): ([u8; 32], Vec<u8>) = node.into();
        let value: Vec<u8> = vec![
            0u8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2,
        ];
        assert_eq!(
            [1; 32], key,
            "The value of the root should be vec![0u8, [1;32], [2;32]]"
        );
        assert_eq!(
            value, result,
            "The value of the root should be vec![0u8, [1;32], [2;32]]"
        );
    }

    #[test]
    fn from_leaf_to_bytes() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 2, 10, None, None, None);
        let (key, result): ([u8; 32], Vec<u8>) = node.into();
        let value: Vec<u8> = vec![1u8, 0, 2];
        assert_eq!(
            [1; 32], key,
            "The value of the root should be vec![0u8, [1;32], [2;32]]"
        );
        assert_eq!(
            value, result,
            "The value of the root should be vec![0u8, [1;32], [2;32]]"
        );
    }

    #[test]
    fn from_intermediate_to_bytes() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            8,
            8,
            Some([2u8; 32]),
            Some([1u8; 32]),
            Some([2u8; 32]),
        );
        let (key, result): ([u8; 32], Vec<u8>) = node.into();
        let value: Vec<u8> = vec![
            2u8, 0, 8, 0, 8, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        ];
        assert_eq!(
            key, [1; 32],
            "The value of the root should be vec![0u8, [1;32], [2;32]]"
        );
        assert_eq!(
            value, result,
            "The value of the root should be vec![0u8, [1;32], [2;32]]"
        );
    }

    #[test]
    fn from_bytes_to_root() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 0, 0, None, Some([1u8; 32]), Some([2u8; 32]));
        let key = [1u8; 32];
        let value: Vec<u8> = vec![
            0u8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2,
        ];
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index(),
            node.get_index(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_bytes_to_root_not_enough_for_left() {
        let key = [1u8; 32];
        let value: Vec<u8> = vec![
            0u8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1,
        ];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from("Vector not long enough to obtain left child.")
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn from_bytes_to_root_not_enough_for_right() {
        let key = [1u8; 32];
        let value: Vec<u8> = vec![
            0u8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 2,
        ];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from("Vector not long enough to obtain right child.")
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn from_bytes_to_leaf() {
        let node: Node<[u8; 32]> = Node::new([1; 32], 2, 254, Some([1; 32]), None, None);
        let key = [1; 32];
        let value: Vec<u8> = vec![1u8, 0, 2];
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index(),
            node.get_index(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_bytes_to_leaf_not_enough_for_depth() {
        let key = [1; 32];
        let value: Vec<u8> = vec![1u8, 0];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from("Not enough bytes to obtain the depth (at least 3).")
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn from_bytes_to_intermediate_1byte_mod0() {
        let node: Node<[u8; 32]> = Node::new(
            [1; 32],
            8,
            8,
            Some([2u8; 32]),
            Some([1u8; 32]),
            Some([2u8; 32]),
        );
        let key = [1; 32];
        let value: Vec<u8> = vec![
            2u8, 0, 8, 0, 8, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        ];
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();
        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index().unwrap()[0..2],
            node.get_index().unwrap()[0..2],
            "The index length is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_bytes_to_intermediate_1bytes_mod1() {
        let node: Node<[u8; 32]> =
            Node::new([3; 32], 7, 8, Some([64; 32]), Some([1; 32]), Some([2; 32]));
        let key = [3; 32];
        let mut value: Vec<u8> = vec![2u8, 0, 7, 0, 8, 64, 64];
        value.extend([1u8; 32].iter().clone());
        value.extend([2u8; 32].iter().clone());
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index().unwrap()[0..2],
            node.get_index().unwrap()[0..2],
            "The index is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_bytes_to_intermediate_1bytes_mod4() {
        let node: Node<[u8; 32]> =
            Node::new([3; 32], 12, 8, Some([2; 32]), Some([1; 32]), Some([2; 32]));
        let key = [3; 32];
        let mut value: Vec<u8> = vec![2u8, 0, 12, 0, 8, 2, 2, 2];
        value.extend([1u8; 32].iter().clone());
        value.extend([2u8; 32].iter().clone());
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index().unwrap()[0..3],
            node.get_index().unwrap()[0..3],
            "The index is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_value_to_intermediate_multiple_bytes_mod0() {
        let node: Node<[u8; 32]> =
            Node::new([3; 32], 8, 20, Some([2; 32]), Some([1; 32]), Some([2; 32]));
        let key = [3; 32];
        let mut value: Vec<u8> = vec![2u8, 0, 8, 0, 20, 2, 2, 2, 2];
        value.extend([1u8; 32].iter().clone());
        value.extend([2u8; 32].iter().clone());
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index().unwrap()[0..4],
            node.get_index().unwrap()[0..4],
            "The index length is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_value_to_intermediate_multiple_bytes_mod1() {
        let node: Node<[u8; 32]> =
            Node::new([3; 32], 9, 20, Some([2; 32]), Some([1; 32]), Some([2; 32]));
        let key = [3; 32];
        let mut value: Vec<u8> = vec![2u8, 0, 9, 0, 20, 2, 2, 2, 2];
        value.extend([1u8; 32].iter().clone());
        value.extend([2u8; 32].iter().clone());
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index().unwrap()[0..4],
            node.get_index().unwrap()[0..4],
            "The index length is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_value_to_intermediate_multiple_bytes_mod4() {
        let node: Node<[u8; 32]> =
            Node::new([3; 32], 4, 20, Some([2; 32]), Some([1; 32]), Some([2; 32]));
        let key = [3; 32];
        let mut value: Vec<u8> = vec![2u8, 0, 4, 0, 20, 2, 2, 2];
        value.extend([1u8; 32].iter().clone());
        value.extend([2u8; 32].iter().clone());
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index().unwrap()[0..3],
            node.get_index().unwrap()[0..3],
            "The index length is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_value_to_intermediate_multiple_bytes_mod7() {
        let node: Node<[u8; 32]> =
            Node::new([3; 32], 15, 20, Some([2; 32]), Some([1; 32]), Some([2; 32]));
        let key = [3; 32];
        let mut value: Vec<u8> = vec![2u8, 0, 15, 0, 20, 2, 2, 2, 2, 2];
        value.extend([1u8; 32].iter().clone());
        value.extend([2u8; 32].iter().clone());
        let root: Node<[u8; 32]> = (key, value).try_into().unwrap();

        assert_eq!(root.is_root(), node.is_root(), "The node should be root");
        assert_eq!(root.get_key(), node.get_key(), "The key is not correct");
        assert_eq!(
            root.get_depth(),
            node.get_depth(),
            "The depth is not correct"
        );
        assert_eq!(
            root.get_index_length(),
            node.get_index_length(),
            "The index length is not correct"
        );
        assert_eq!(
            root.get_index().unwrap()[0..5],
            node.get_index().unwrap()[0..5],
            "The index is not correct"
        );
        assert_eq!(
            root.get_left_child(),
            node.get_left_child(),
            "The left child is not correct"
        );
        assert_eq!(
            root.get_right_child(),
            node.get_right_child(),
            "The right child is not correct"
        );
    }

    #[test]
    fn from_value_to_intermediate_not_enough_for_depth() {
        let key = [3; 32];
        let value: Vec<u8> = vec![2u8, 0];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from("Not enough bytes to obtain the depth (at least 3).")
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn from_value_to_intermediate_not_enough_for_index_len() {
        let key = [3; 32];
        let value: Vec<u8> = vec![2u8, 0, 1, 0];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from(
                    "Not enough bytes to obtain the index length (at least 5)."
                )
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn from_value_to_intermediate_not_enough_for_index() {
        let key = [3; 32];
        let value: Vec<u8> = vec![2u8, 0, 1, 0, 1];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from("Not enough bytes to obtain the index.")
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn from_value_to_intermediate_not_enough_for_left_key() {
        let key = [3; 32];
        let value: Vec<u8> = vec![2u8, 0, 1, 0, 1, 1, 1, 1, 1];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from("Not enough bytes to obtain the left key.")
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn from_value_to_intermediate_not_enough_for_right_key() {
        let key = [3; 32];
        let value: Vec<u8> = vec![
            2u8, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
        ];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from("Not enough bytes to obtain the right key.")
            }),
            "Error messages do not match"
        );
    }

    #[test]
    fn test_malformed_data() {
        let key = [3; 32];
        let value: Vec<u8> = vec![
            4u8, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
        ];
        assert_eq!(
            Node::<[u8; 32]>::try_from((key, value)).err(),
            Some(SmtError::CorruptedData {
                key: format!("{:#?}", key),
                condition: String::from(
                    "Malformed node (node value does not start with 0, 1 or 2)."
                )
            }),
            "Error messages do not match"
        );
    }
}