merkle_tree_db/
tree.rs

1use super::{DBValue, HashMap, Hasher, Node, NodeHash, TreeError};
2
3// TRAITS
4// ================================================================================================
5
6type Proof<H> = (Option<DBValue>, <H as Hasher>::Out, Vec<DBValue>);
7
8/// A immutable key-value datastore implemented as a database-backed sparse merkle tree.
9pub trait KeyedTree<H: Hasher, const D: usize> {
10    /// Returns the root of the tree.
11    fn root(&self) -> &H::Out;
12
13    /// Returns the depth of the tree.
14    fn depth(&self) -> usize {
15        D * 8
16    }
17
18    /// Returns the value at the provided key.
19    fn value(&self, key: &[u8]) -> Result<Option<DBValue>, TreeError>;
20
21    /// Returns the leaf at the provided key.
22    fn leaf(&self, key: &[u8]) -> Result<Option<H::Out>, TreeError>;
23
24    /// Returns an inclusion proof of a value a the specified key.
25    fn proof(&self, key: &[u8]) -> Result<Proof<H>, TreeError>;
26
27    /// Verifies an inclusion proof of a value at the specified key.
28    fn verify(
29        key: &[u8],
30        value: &[u8],
31        proof: &[DBValue],
32        root: &H::Out,
33    ) -> Result<bool, TreeError>;
34}
35
36/// A mutable key-value datastore implemented as a database-backed sparse merkle tree.
37pub trait KeyedTreeMut<H: Hasher, const D: usize> {
38    /// Returns the root of the tree.
39    fn root(&mut self) -> &H::Out;
40
41    /// Returns the depth of the tree.
42    fn depth(&self) -> usize {
43        D * 8
44    }
45
46    /// Returns the value at the provided key.
47    fn value(&self, key: &[u8]) -> Result<Option<DBValue>, TreeError>;
48
49    /// Returns the leaf at the provided key.
50    fn leaf(&self, key: &[u8]) -> Result<Option<H::Out>, TreeError>;
51
52    /// Returns an inclusion proof of a value a the specified key.
53    fn proof(&self, key: &[u8]) -> Result<Proof<H>, TreeError>;
54
55    /// Inserts a value at the provided key.
56    fn insert(&mut self, key: &[u8], value: DBValue) -> Result<Option<DBValue>, TreeError>;
57
58    /// Removes a value at the provided key.
59    fn remove(&mut self, key: &[u8]) -> Result<Option<DBValue>, TreeError>;
60
61    /// Verifies an inclusion proof of a value at the specified key.
62    fn verify(
63        key: &[u8],
64        value: &[u8],
65        proof: &[DBValue],
66        root: &H::Out,
67    ) -> Result<bool, TreeError>;
68}
69
70/// A immutable index-value datastore implemented as a database-backed sparse merkle tree.
71pub trait IndexTree<H: Hasher, const D: usize> {
72    /// Returns the root of the tree.
73    fn root(&self) -> &H::Out;
74
75    /// Returns the depth of the tree.
76    fn depth(&self) -> usize {
77        D * 8
78    }
79
80    /// Returns the value at the provided index.
81    fn value(&self, index: &u64) -> Result<Option<DBValue>, TreeError>;
82
83    /// Returns the leaf at the provided index.
84    fn leaf(&self, index: &u64) -> Result<Option<H::Out>, TreeError>;
85
86    /// Returns an inclusion proof of a value a the specified index.
87    fn proof(&self, index: &u64) -> Result<Proof<H>, TreeError>;
88
89    /// Verifies an inclusion proof of a value at the specified index.
90    fn verify(
91        index: &u64,
92        value: &[u8],
93        proof: &[DBValue],
94        root: &H::Out,
95    ) -> Result<bool, TreeError>;
96}
97
98/// A mutable index-value datastore implemented as a database-backed sparse merkle tree.
99pub trait IndexTreeMut<H: Hasher, const D: usize> {
100    /// Returns the root of the tree.
101    fn root(&mut self) -> &H::Out;
102
103    /// Returns the depth of the tree.
104    fn depth(&self) -> usize {
105        D * 8
106    }
107
108    /// Returns the value at the provided index.
109    fn value(&self, index: &u64) -> Result<Option<DBValue>, TreeError>;
110
111    /// Returns the leaf at the provided key.
112    fn leaf(&self, index: &u64) -> Result<Option<H::Out>, TreeError>;
113
114    /// Returns an inclusion proof of a value a the specified index.
115    fn proof(&self, index: &u64) -> Result<Proof<H>, TreeError>;
116
117    /// Inserts a value at the provided index.
118    fn insert(&mut self, index: &u64, value: DBValue) -> Result<Option<DBValue>, TreeError>;
119
120    /// Removes a value at the provided index.
121    fn remove(&mut self, index: &u64) -> Result<Option<DBValue>, TreeError>;
122
123    /// Verifies an inclusion proof of a value at the specified index.
124    fn verify(
125        index: &u64,
126        value: &[u8],
127        proof: &[DBValue],
128        root: &H::Out,
129    ) -> Result<bool, TreeError>;
130}
131
132/// A trait that allows recording of tree nodes.
133pub trait TreeRecorder<H: Hasher> {
134    fn record(&mut self, node: &Node<H>);
135}
136
137// Helpers
138// ================================================================================================
139
140/// Return the HashMap hashing node hash to Node for null nodes of a tree of depth D
141pub fn null_nodes<H: Hasher>(depth: usize) -> (HashMap<H::Out, Node<H>>, H::Out) {
142    let mut hashes = HashMap::with_capacity(depth);
143    let mut current_hash = H::hash(&[]);
144
145    hashes.insert(
146        current_hash,
147        Node::Value {
148            hash: current_hash,
149            value: vec![],
150        },
151    );
152
153    for _ in 0..depth {
154        let next_hash = H::hash(&[current_hash.as_ref(), current_hash.as_ref()].concat());
155        hashes.insert(
156            next_hash,
157            Node::Inner {
158                hash: next_hash,
159                left: NodeHash::Default(current_hash),
160                right: NodeHash::Default(current_hash),
161            },
162        );
163        current_hash = next_hash;
164    }
165
166    (hashes, current_hash)
167}
merkle_tree_db/tree.rs

merkle_tree_db/
tree.rs
