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(bytes.get(8..16).ok_or(MerkleTreeError::SerializationError)?);
52        let len = usize::try_from(u64::from_be_bytes(u64_bytes))
53            .map_err(|_| MerkleTreeError::SerializationError)?;
54        let mut values = Vec::with_capacity(len);
55        for i in 0..len {
56            values.push(
57                bytes
58                    .get(
59                        16 + i * <D as Digest>::output_size()
60                            ..16 + (i + 1) * <D as Digest>::output_size(),
61                    )
62                    .ok_or(MerkleTreeError::SerializationError)?
63                    .to_vec(),
64            );
65        }
66
67        Ok(MerklePath {
68            values,
69            index,
70            hasher: PhantomData,
71        })
72    }
73}
74
75/// Path of hashes for a batch of indices.
76/// Contains the hashes and the corresponding merkle tree indices of given batch.
77/// Used to verify the signatures are issued by the registered signers.
78#[derive(Default, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
79pub struct MerkleBatchPath<D: Digest + FixedOutput> {
80    pub(crate) values: Vec<Vec<u8>>,
81    pub(crate) indices: Vec<usize>,
82    pub(crate) hasher: PhantomData<D>,
83}
84
85impl<D: Digest + FixedOutput> MerkleBatchPath<D> {
86    pub(crate) fn new(values: Vec<Vec<u8>>, indices: Vec<usize>) -> MerkleBatchPath<D> {
87        Self {
88            values,
89            indices,
90            hasher: Default::default(),
91        }
92    }
93
94    /// Convert the `BatchPath` into byte representation.
95    ///
96    /// # Layout
97    /// The layout of a `BatchPath` is
98    /// * Length of values
99    /// * Length of indices
100    /// * Values
101    /// * Indices
102    pub fn to_bytes(&self) -> Vec<u8> {
103        let mut output = Vec::new();
104        let len_v = self.values.len();
105        let len_i = self.indices.len();
106
107        output.extend_from_slice(&u64::try_from(len_v).unwrap().to_be_bytes());
108        output.extend_from_slice(&u64::try_from(len_i).unwrap().to_be_bytes());
109
110        for value in &self.values {
111            output.extend_from_slice(value.as_slice())
112        }
113
114        for &index in &self.indices {
115            output.extend_from_slice(&u64::try_from(index).unwrap().to_be_bytes());
116        }
117        output
118    }
119
120    /// Try to convert a byte string into a `BatchPath`.
121    pub fn from_bytes(bytes: &[u8]) -> Result<Self, MerkleTreeError<D>> {
122        let mut u64_bytes = [0u8; 8];
123        u64_bytes.copy_from_slice(&bytes[..8]);
124        let len_v = usize::try_from(u64::from_be_bytes(u64_bytes))
125            .map_err(|_| MerkleTreeError::SerializationError)?;
126
127        u64_bytes.copy_from_slice(&bytes[8..16]);
128        let len_i = usize::try_from(u64::from_be_bytes(u64_bytes))
129            .map_err(|_| MerkleTreeError::SerializationError)?;
130
131        let mut values = Vec::with_capacity(len_v);
132        for i in 0..len_v {
133            values.push(
134                bytes[16 + i * <D as Digest>::output_size()
135                    ..16 + (i + 1) * <D as Digest>::output_size()]
136                    .to_vec(),
137            );
138        }
139        let offset = 16 + len_v * <D as Digest>::output_size();
140
141        let mut indices = Vec::with_capacity(len_v);
142        for i in 0..len_i {
143            u64_bytes.copy_from_slice(&bytes[offset + i * 8..offset + (i + 1) * 8]);
144            indices.push(
145                usize::try_from(u64::from_be_bytes(u64_bytes))
146                    .map_err(|_| MerkleTreeError::SerializationError)?,
147            );
148        }
149
150        Ok(MerkleBatchPath {
151            values,
152            indices,
153            hasher: PhantomData,
154        })
155    }
156}
mithril_stm/merkle_tree/path.rs

mithril_stm/merkle_tree/
path.rs
