mithril_stm/merkle_tree/
path.rs

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

mithril_stm/merkle_tree/
path.rs
