nmt_rs/simple_merkle/
db.rs

1use crate::{
2    maybestd::{hash::Hash, vec::Vec},
3    NamespaceId, NamespaceMerkleHasher, NamespacedHash,
4};
5
6use super::tree::MerkleHash;
7
8#[cfg(not(feature = "std"))]
9trait HashType: Eq + Hash + crate::maybestd::cmp::Ord {}
10
11#[cfg(not(feature = "std"))]
12impl<H: Eq + Hash + Ord> HashType for H {}
13
14#[cfg(feature = "std")]
15trait HashType: Eq + Hash {}
16
17#[cfg(feature = "std")]
18impl<H: Eq + Hash> HashType for H {}
19
20/// Maintains a mapping from hash to preimage in memory. Backed by a [`crate::maybestd::hash_or_btree_map::Map<H, Node<H>>`]
21#[derive(Default)]
22pub struct MemDb<H>(crate::maybestd::hash_or_btree_map::Map<H, Node<H>>);
23
24impl<H: HashType> PreimageReader<H> for MemDb<H> {
25    fn get(&self, image: &H) -> Option<&Node<H>> {
26        self.0.get(image)
27    }
28}
29impl<H: HashType> PreimageWriter<H> for MemDb<H> {
30    fn put(&mut self, image: H, preimage: Node<H>) {
31        self.0.insert(image, preimage);
32    }
33}
34
35impl<H: Default + HashType> PreimageDb<H> for MemDb<H> {}
36
37/// The raw data of the leaf, together with its hash under some [`MerkleHash`]er
38#[derive(Clone)]
39pub struct LeafWithHash<H: MerkleHash> {
40    data: Vec<u8>,
41    hash: H::Output,
42}
43
44impl<H: MerkleHash + Default> LeafWithHash<H> {
45    /// Construct a [`LeafWithHash`] by hashing the provided data
46    pub fn new(data: Vec<u8>) -> Self {
47        let hash = H::default().hash_leaf(&data);
48        Self { data, hash }
49    }
50}
51
52impl<H: MerkleHash> LeafWithHash<H> {
53    /// Construct a [`LeafWithHash`] by hashing the provided data
54    pub fn with_hasher(data: Vec<u8>, hasher: &H) -> Self {
55        let hash = hasher.hash_leaf(&data);
56        Self { data, hash }
57    }
58
59    /// Returns the raw data from the leaf
60    pub fn data(&self) -> &[u8] {
61        &self.data
62    }
63
64    /// Returns the hash of the leaf data
65    pub fn hash(&self) -> &H::Output {
66        &self.hash
67    }
68}
69
70impl<
71        M: NamespaceMerkleHasher<NS_ID_SIZE, Output = NamespacedHash<NS_ID_SIZE>>,
72        const NS_ID_SIZE: usize,
73    > LeafWithHash<M>
74{
75    /// Create a new leaf with the provided namespace. Only available if the hasher supports namespacing.
76    pub fn new_with_namespace(
77        data: Vec<u8>,
78        namespace: NamespaceId<NS_ID_SIZE>,
79        ignore_max_ns: bool,
80    ) -> Self {
81        let hasher = M::with_ignore_max_ns(ignore_max_ns);
82        let hash = hasher.hash_leaf_with_namespace(&data, namespace);
83        Self { data, hash }
84    }
85}
86
87/// A node of a merkle tree
88#[derive(PartialEq, Clone, Debug)]
89pub enum Node<H> {
90    /// A leaf node contains raw data
91    Leaf(Vec<u8>),
92    /// An inner node is the concatenation of two child nodes
93    Inner(H, H),
94}
95
96/// The reader trait for a data store that maps hashes to preimages
97pub trait PreimageReader<H> {
98    /// Get the preimage of a given hash
99    fn get(&self, image: &H) -> Option<&Node<H>>;
100}
101
102/// The writer trait for a data store that maps hashes to preimages
103pub trait PreimageWriter<H> {
104    /// Store the preimage of a given hash
105    fn put(&mut self, image: H, preimage: Node<H>);
106}
107
108/// A trait representing read and write access to data store that maps hashes to their preimages
109pub trait PreimageDb<H>: PreimageReader<H> + PreimageWriter<H> + Default {}
110
111/// A PreimageDB that drops all stored items. Should only be used in trees that
112/// do not create proofs (i.e. trees used only for proof verification)
113#[derive(Default)]
114pub struct NoopDb;
115
116impl<H: Eq + Hash> PreimageReader<H> for NoopDb {
117    fn get(&self, _image: &H) -> Option<&Node<H>> {
118        None
119    }
120}
121impl<H: Eq + Hash> PreimageWriter<H> for NoopDb {
122    fn put(&mut self, _image: H, _preimage: Node<H>) {}
123}
124
125impl<H: Default + Eq + Hash> PreimageDb<H> for NoopDb {}
nmt_rs/simple_merkle/db.rs

nmt_rs/simple_merkle/
db.rs
