mithril_stm/merkle_tree/
commitment.rs

1use std::marker::PhantomData;
2
3use blake2::digest::{Digest, FixedOutput};
4use serde::{Deserialize, Serialize};
5
6use crate::error::MerkleTreeError;
7use crate::merkle_tree::{MerkleBatchPath, MerklePath, MerkleTreeLeaf, parent, sibling};
8
9/// `MerkleTree` commitment.
10/// This structure differs from `MerkleTree` in that it does not contain all elements, which are not always necessary.
11/// Instead, it only contains the root of the tree.
12#[derive(Debug, Clone, Serialize, Deserialize)]
13pub struct MerkleTreeCommitment<D: Digest> {
14    /// Root of the merkle commitment.
15    pub root: Vec<u8>,
16    hasher: PhantomData<D>,
17}
18
19impl<D: Digest + FixedOutput> MerkleTreeCommitment<D> {
20    pub(crate) fn new(root: Vec<u8>) -> Self {
21        MerkleTreeCommitment {
22            root,
23            hasher: PhantomData,
24        }
25    }
26
27    /// Check an inclusion proof that `val` is part of the tree by traveling the whole path until the root.
28    /// # Error
29    /// If the merkle tree path is invalid, then the function fails.
30    pub(crate) fn verify_leaf_membership_from_path(
31        &self,
32        val: &MerkleTreeLeaf,
33        proof: &MerklePath<D>,
34    ) -> Result<(), MerkleTreeError<D>>
35    where
36        D: FixedOutput + Clone,
37    {
38        let mut idx = proof.index;
39
40        let mut h = D::digest(val.to_bytes()).to_vec();
41        for p in &proof.values {
42            if (idx & 0b1) == 0 {
43                h = D::new().chain_update(h).chain_update(p).finalize().to_vec();
44            } else {
45                h = D::new().chain_update(p).chain_update(h).finalize().to_vec();
46            }
47            idx >>= 1;
48        }
49
50        if h == self.root {
51            return Ok(());
52        }
53        Err(MerkleTreeError::PathInvalid(proof.clone()))
54    }
55
56    /// Check an inclusion proof that `val` is part of the tree by traveling the whole path until the root.
57    /// # Error
58    /// If the merkle tree path is invalid, then the function fails.
59    #[deprecated(
60        since = "0.5.0",
61        note = "Use `verify_leaf_membership_from_path` instead"
62    )]
63    pub fn check(
64        &self,
65        val: &MerkleTreeLeaf,
66        proof: &MerklePath<D>,
67    ) -> Result<(), MerkleTreeError<D>>
68    where
69        D: FixedOutput + Clone,
70    {
71        Self::verify_leaf_membership_from_path(self, val, proof)
72    }
73
74    /// Serializes the Merkle Tree commitment together with a message in a single vector of bytes.
75    /// Outputs `msg || self` as a vector of bytes.
76    fn concatenate_with_message(&self, msg: &[u8]) -> Vec<u8>
77    where
78        D: Digest,
79    {
80        let mut msgp = msg.to_vec();
81        let mut bytes = self.root.clone();
82        msgp.append(&mut bytes);
83
84        msgp
85    }
86
87    /// Serializes the Merkle Tree commitment together with a message in a single vector of bytes.
88    /// Outputs `msg || self` as a vector of bytes.
89    #[deprecated(since = "0.5.0", note = "Use `concatenate_with_message` instead")]
90    pub fn concat_with_msg(&self, msg: &[u8]) -> Vec<u8>
91    where
92        D: Digest,
93    {
94        Self::concatenate_with_message(self, msg)
95    }
96}
97
98/// Batch compatible `MerkleTree` commitment .
99/// This structure differs from `MerkleTreeCommitment` in that it stores the number of leaves in the tree
100/// as well as the root of the tree.
101/// Number of leaves is required by the batch path generation/verification.
102#[derive(Debug, Clone, Serialize, Deserialize)]
103pub struct MerkleTreeBatchCommitment<D: Digest> {
104    /// Root of the merkle commitment.
105    pub root: Vec<u8>,
106    nr_leaves: usize,
107    hasher: PhantomData<D>,
108}
109
110impl<D: Digest> MerkleTreeBatchCommitment<D> {
111    pub(crate) fn new(root: Vec<u8>, nr_leaves: usize) -> Self {
112        Self {
113            root,
114            nr_leaves,
115            hasher: Default::default(),
116        }
117    }
118
119    #[cfg(test)]
120    /// Used in property test of `tree`: `test_bytes_tree_commitment_batch_compat`
121    pub(crate) fn get_number_of_leaves(&self) -> usize {
122        self.nr_leaves
123    }
124
125    /// Serializes the Merkle Tree commitment together with a message in a single vector of bytes.
126    /// Outputs `msg || self` as a vector of bytes.
127    // todo: Do we need to concat msg to whole commitment (nr_leaves and root) or just the root?
128    pub(crate) fn concatenate_with_message(&self, msg: &[u8]) -> Vec<u8> {
129        let mut msgp = msg.to_vec();
130        let mut bytes = self.root.clone();
131        msgp.append(&mut bytes);
132
133        msgp
134    }
135
136    /// Serializes the Merkle Tree commitment together with a message in a single vector of bytes.
137    /// Outputs `msg || self` as a vector of bytes.
138    // todo: Do we need to concat msg to whole commitment (nr_leaves and root) or just the root?
139    #[deprecated(since = "0.5.0", note = "Use `concatenate_with_message` instead")]
140    pub fn concat_with_msg(&self, msg: &[u8]) -> Vec<u8> {
141        Self::concatenate_with_message(self, msg)
142    }
143
144    /// Check a proof of a batched opening. The indices must be ordered.
145    ///
146    /// # Error
147    /// Returns an error if the proof is invalid.
148    // todo: Update doc.
149    // todo: Simplify the algorithm.
150    // todo: Maybe we want more granular errors, rather than only `BatchPathInvalid`
151    pub(crate) fn verify_leaves_membership_from_batch_path(
152        &self,
153        batch_val: &[MerkleTreeLeaf],
154        proof: &MerkleBatchPath<D>,
155    ) -> Result<(), MerkleTreeError<D>>
156    where
157        D: FixedOutput + Clone,
158    {
159        if batch_val.len() != proof.indices.len() {
160            return Err(MerkleTreeError::BatchPathInvalid(proof.clone()));
161        }
162        let mut ordered_indices: Vec<usize> = proof.indices.clone();
163        ordered_indices.sort_unstable();
164
165        if ordered_indices != proof.indices {
166            return Err(MerkleTreeError::BatchPathInvalid(proof.clone()));
167        }
168
169        let nr_nodes = self.nr_leaves + self.nr_leaves.next_power_of_two() - 1;
170
171        ordered_indices = ordered_indices
172            .into_iter()
173            .map(|i| i + self.nr_leaves.next_power_of_two() - 1)
174            .collect();
175
176        let mut idx = ordered_indices[0];
177        // First we need to hash the leave values
178        let mut leaves: Vec<Vec<u8>> = batch_val
179            .iter()
180            .map(|val| D::digest(val.to_bytes()).to_vec())
181            .collect();
182
183        let mut values = proof.values.clone();
184
185        while idx > 0 {
186            let mut new_hashes = Vec::with_capacity(ordered_indices.len());
187            let mut new_indices = Vec::with_capacity(ordered_indices.len());
188            let mut i = 0;
189            idx = parent(idx);
190            while i < ordered_indices.len() {
191                new_indices.push(parent(ordered_indices[i]));
192                if ordered_indices[i] & 1 == 0 {
193                    new_hashes.push(
194                        D::new()
195                            .chain(values.first().ok_or(MerkleTreeError::SerializationError)?)
196                            .chain(&leaves[i])
197                            .finalize()
198                            .to_vec(),
199                    );
200                    values.remove(0);
201                } else {
202                    let sibling = sibling(ordered_indices[i]);
203                    if i < ordered_indices.len() - 1 && ordered_indices[i + 1] == sibling {
204                        new_hashes.push(
205                            D::new().chain(&leaves[i]).chain(&leaves[i + 1]).finalize().to_vec(),
206                        );
207                        i += 1;
208                    } else if sibling < nr_nodes {
209                        new_hashes.push(
210                            D::new()
211                                .chain(&leaves[i])
212                                .chain(values.first().ok_or(MerkleTreeError::SerializationError)?)
213                                .finalize()
214                                .to_vec(),
215                        );
216                        values.remove(0);
217                    } else {
218                        new_hashes.push(
219                            D::new().chain(&leaves[i]).chain(D::digest([0u8])).finalize().to_vec(),
220                        );
221                    }
222                }
223                i += 1;
224            }
225            leaves.clone_from(&new_hashes);
226            ordered_indices.clone_from(&new_indices);
227        }
228
229        if leaves.len() == 1 && leaves[0] == self.root {
230            return Ok(());
231        }
232
233        Err(MerkleTreeError::BatchPathInvalid(proof.clone()))
234    }
235
236    /// Check a proof of a batched opening. The indices must be ordered.
237    ///
238    /// # Error
239    /// Returns an error if the proof is invalid.
240    // todo: Update doc.
241    // todo: Simplify the algorithm.
242    // todo: Maybe we want more granular errors, rather than only `BatchPathInvalid`
243    #[deprecated(
244        since = "0.5.0",
245        note = "Use `verify_leaves_membership_from_batch_path` instead"
246    )]
247    pub fn check(
248        &self,
249        batch_val: &[MerkleTreeLeaf],
250        proof: &MerkleBatchPath<D>,
251    ) -> Result<(), MerkleTreeError<D>>
252    where
253        D: FixedOutput + Clone,
254    {
255        Self::verify_leaves_membership_from_batch_path(self, batch_val, proof)
256    }
257}
258
259impl<D: Digest> PartialEq for MerkleTreeBatchCommitment<D> {
260    fn eq(&self, other: &Self) -> bool {
261        self.root == other.root && self.nr_leaves == other.nr_leaves
262    }
263}
264
265impl<D: Digest> Eq for MerkleTreeBatchCommitment<D> {}
mithril_stm/merkle_tree/commitment.rs

mithril_stm/merkle_tree/
commitment.rs
