mithril_stm/merkle_tree/
path.rs

1use crate::error::MerkleTreeError;
2use blake2::digest::{Digest, FixedOutput};
3use serde::{Deserialize, Serialize};
4use std::marker::PhantomData;
5
6/// Path of hashes from root to leaf in a Merkle Tree.
7/// Contains all hashes on the path, and the index of the leaf.
8/// Used to verify that signatures come from eligible signers.
9#[derive(Default, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
10pub struct Path<D: Digest> {
11    pub(crate) values: Vec<Vec<u8>>,
12    pub(crate) index: usize,
13    hasher: PhantomData<D>,
14}
15
16impl<D: Digest + FixedOutput> Path<D> {
17    pub(crate) fn new(values: Vec<Vec<u8>>, index: usize) -> Self {
18        Self {
19            values,
20            index,
21            hasher: Default::default(),
22        }
23    }
24
25    /// Convert to bytes
26    /// # Layout
27    /// * Index representing the position in the Merkle Tree
28    /// * Size of the Path
29    /// * Path of hashes
30    pub fn to_bytes(&self) -> Vec<u8> {
31        let mut output = Vec::new();
32        output.extend_from_slice(&u64::try_from(self.index).unwrap().to_be_bytes());
33        output.extend_from_slice(&u64::try_from(self.values.len()).unwrap().to_be_bytes());
34        for value in &self.values {
35            output.extend_from_slice(value)
36        }
37
38        output
39    }
40
41    /// Extract a `Path` from a byte slice.
42    /// # Error
43    /// This function fails if the bytes cannot retrieve path.
44    pub fn from_bytes(bytes: &[u8]) -> Result<Path<D>, MerkleTreeError<D>> {
45        let mut u64_bytes = [0u8; 8];
46        u64_bytes.copy_from_slice(&bytes[..8]);
47        let index = usize::try_from(u64::from_be_bytes(u64_bytes))
48            .map_err(|_| MerkleTreeError::SerializationError)?;
49        u64_bytes.copy_from_slice(&bytes[8..16]);
50        let len = usize::try_from(u64::from_be_bytes(u64_bytes))
51            .map_err(|_| MerkleTreeError::SerializationError)?;
52        let mut values = Vec::with_capacity(len);
53        for i in 0..len {
54            values.push(
55                bytes[16 + i * <D as Digest>::output_size()
56                    ..16 + (i + 1) * <D as Digest>::output_size()]
57                    .to_vec(),
58            );
59        }
60
61        Ok(Path {
62            values,
63            index,
64            hasher: PhantomData,
65        })
66    }
67}
68
69/// Path of hashes for a batch of indices.
70/// Contains the hashes and the corresponding merkle tree indices of given batch.
71/// Used to verify the signatures are issued by the registered signers.
72#[derive(Default, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
73pub struct BatchPath<D: Digest + FixedOutput> {
74    pub(crate) values: Vec<Vec<u8>>,
75    pub(crate) indices: Vec<usize>,
76    pub(crate) hasher: PhantomData<D>,
77}
78
79impl<D: Digest + FixedOutput> BatchPath<D> {
80    pub(crate) fn new(values: Vec<Vec<u8>>, indices: Vec<usize>) -> BatchPath<D> {
81        Self {
82            values,
83            indices,
84            hasher: Default::default(),
85        }
86    }
87
88    /// Convert the `BatchPath` into byte representation.
89    ///
90    /// # Layout
91    /// The layout of a `BatchPath` is
92    /// * Length of values
93    /// * Length of indices
94    /// * Values
95    /// * Indices
96    pub fn to_bytes(&self) -> Vec<u8> {
97        let mut output = Vec::new();
98        let len_v = self.values.len();
99        let len_i = self.indices.len();
100
101        output.extend_from_slice(&u64::try_from(len_v).unwrap().to_be_bytes());
102        output.extend_from_slice(&u64::try_from(len_i).unwrap().to_be_bytes());
103
104        for value in &self.values {
105            output.extend_from_slice(value.as_slice())
106        }
107
108        for &index in &self.indices {
109            output.extend_from_slice(&u64::try_from(index).unwrap().to_be_bytes());
110        }
111        output
112    }
113
114    /// Try to convert a byte string into a `BatchPath`.
115    // todo: We should not panic if the size of the slice is invalid (I believe `bytes[offset + i * 8..offset + (i + 1) * 8]` will panic if bytes is not large enough.
116    pub fn from_bytes(bytes: &[u8]) -> Result<Self, MerkleTreeError<D>> {
117        let mut u64_bytes = [0u8; 8];
118        u64_bytes.copy_from_slice(&bytes[..8]);
119        let len_v = usize::try_from(u64::from_be_bytes(u64_bytes))
120            .map_err(|_| MerkleTreeError::SerializationError)?;
121
122        u64_bytes.copy_from_slice(&bytes[8..16]);
123        let len_i = usize::try_from(u64::from_be_bytes(u64_bytes))
124            .map_err(|_| MerkleTreeError::SerializationError)?;
125
126        let mut values = Vec::with_capacity(len_v);
127        for i in 0..len_v {
128            values.push(
129                bytes[16 + i * <D as Digest>::output_size()
130                    ..16 + (i + 1) * <D as Digest>::output_size()]
131                    .to_vec(),
132            );
133        }
134        let offset = 16 + len_v * <D as Digest>::output_size();
135
136        let mut indices = Vec::with_capacity(len_v);
137        for i in 0..len_i {
138            u64_bytes.copy_from_slice(&bytes[offset + i * 8..offset + (i + 1) * 8]);
139            indices.push(
140                usize::try_from(u64::from_be_bytes(u64_bytes))
141                    .map_err(|_| MerkleTreeError::SerializationError)?,
142            );
143        }
144
145        Ok(BatchPath {
146            values,
147            indices,
148            hasher: PhantomData,
149        })
150    }
151}
mithril_stm/merkle_tree/path.rs

mithril_stm/merkle_tree/
path.rs
