miden_crypto/merkle/smt/large_forest/
root.rs

1//! This module contains utility types for working with roots and trees as part of the forest.
2
3use miden_serde_utils::{
4    ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable,
5};
6
7#[cfg(test)]
8use crate::rand::Randomizable;
9use crate::{
10    Word,
11    merkle::smt::{LeafIndex, SMT_DEPTH},
12};
13
14// TYPES
15// ================================================================================================
16
17/// A root for a tree in the forest.
18pub type RootValue = Word;
19
20/// An identifier for the version of a tree in a given lineage
21pub type VersionId = u64;
22
23// LINEAGE ID
24// ================================================================================================
25
26/// An identifier for a lineage of trees.
27///
28/// This is an arbitrary, user-provided identifier that is used to disambiguate cases where trees in
29/// distinct lineages are otherwise identical and have the same root.
30#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
31pub struct LineageId([u8; 32]);
32
33impl LineageId {
34    /// Constructs a new lineage ID from the provided bytes.
35    pub fn new(bytes: [u8; 32]) -> Self {
36        Self(bytes)
37    }
38
39    /// Returns the raw bytes of the lineage ID.
40    ///
41    /// This is primarily useful for [`Backend`](super::backend::Backend) implementations that
42    /// need to persist lineage identifiers.
43    pub fn as_bytes(&self) -> &[u8; 32] {
44        &self.0
45    }
46}
47
48impl core::fmt::Display for LineageId {
49    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
50        write!(f, "[")?;
51        for i in 0..4 {
52            let byte = self.0[i];
53            write!(f, "{byte:x}, ")?;
54        }
55        write!(f, "...]")
56    }
57}
58
59impl Serializable for LineageId {
60    fn write_into<W: ByteWriter>(&self, target: &mut W) {
61        target.write_bytes(&self.0)
62    }
63
64    fn get_size_hint(&self) -> usize {
65        size_of_val(&self.0)
66    }
67}
68
69impl Deserializable for LineageId {
70    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
71        Ok(Self(source.read_array()?))
72    }
73}
74
75#[cfg(test)]
76impl Randomizable for LineageId {
77    const VALUE_SIZE: usize = size_of::<Self>();
78
79    fn from_random_bytes(source: &[u8]) -> Option<Self> {
80        let bytes = Randomizable::from_random_bytes(source)?;
81        Some(Self::new(bytes))
82    }
83}
84
85// TREE IDENTIFIER
86// ================================================================================================
87
88/// An identifier that is capable of uniquely referring to a tree in the forest.
89#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
90pub struct TreeId {
91    lineage: LineageId,
92    version: VersionId,
93}
94
95/// The base API of the identifier.
96impl TreeId {
97    /// Constructs a new tree identifier for the tree with the specified `version` in the specified
98    /// `lineage`.
99    pub fn new(lineage: LineageId, version: VersionId) -> Self {
100        Self { lineage, version }
101    }
102
103    /// Gets the tree's lineage from the identifier.
104    pub fn lineage(&self) -> LineageId {
105        self.lineage
106    }
107
108    /// Gets the tree's version from the identifier.
109    pub fn version(&self) -> VersionId {
110        self.version
111    }
112}
113
114impl core::fmt::Display for TreeId {
115    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
116        write!(f, "TreeId(lineage = {}, version = {})", self.lineage, self.version)
117    }
118}
119
120#[cfg(test)]
121impl Randomizable for TreeId {
122    const VALUE_SIZE: usize = size_of::<Self>();
123
124    fn from_random_bytes(source: &[u8]) -> Option<Self> {
125        const LINEAGE_SIZE: usize = size_of::<LineageId>();
126        const VERSION_SIZE: usize = size_of::<VersionId>();
127        let domain = Randomizable::from_random_bytes(source.get(..LINEAGE_SIZE)?)?;
128        let version = Randomizable::from_random_bytes(
129            source.get(LINEAGE_SIZE..LINEAGE_SIZE + VERSION_SIZE)?,
130        )?;
131        Some(Self::new(domain, version))
132    }
133}
134
135// UNIQUE ROOT
136// ================================================================================================
137
138/// A root in the forest that is anchored to a lineage.
139#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
140pub struct UniqueRoot {
141    lineage: LineageId,
142    value: RootValue,
143}
144
145impl UniqueRoot {
146    /// Constructs a new unique root with the provided `value` and `lineage`.
147    pub fn new(lineage: LineageId, value: RootValue) -> Self {
148        Self { lineage, value }
149    }
150
151    /// Gets the lineage in which the root is found.
152    pub fn lineage(&self) -> LineageId {
153        self.lineage
154    }
155
156    /// Gets the value of the tree root itself.
157    pub fn value(&self) -> RootValue {
158        self.value
159    }
160}
161
162// TREE ID WITH ROOT
163// ================================================================================================
164
165/// The unique identifier for a given tree, along with the value of its root.
166#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
167pub struct TreeWithRoot {
168    id: TreeId,
169    root: RootValue,
170}
171
172impl TreeWithRoot {
173    /// Constructs a new tree identifier from the provided `lineage`, `version`, and `root`.
174    pub fn new(lineage: LineageId, version: VersionId, root: RootValue) -> Self {
175        let id = TreeId::new(lineage, version);
176        Self { id, root }
177    }
178
179    /// Gets the tree's lineage.
180    pub fn lineage(&self) -> LineageId {
181        self.id.lineage
182    }
183
184    /// Gets the tree's version.
185    pub fn version(&self) -> VersionId {
186        self.id.version
187    }
188
189    /// Gets the tree's root value.
190    pub fn root(&self) -> RootValue {
191        self.root
192    }
193}
194
195impl From<TreeWithRoot> for TreeId {
196    fn from(value: TreeWithRoot) -> Self {
197        value.id
198    }
199}
200
201impl From<TreeWithRoot> for UniqueRoot {
202    fn from(value: TreeWithRoot) -> Self {
203        UniqueRoot::new(value.id.lineage, value.root)
204    }
205}
206
207// ROOT INFO
208// ================================================================================================
209
210/// Information about the role that a queried root plays in the forest.
211#[derive(Copy, Clone, Debug, Eq, PartialEq)]
212pub enum RootInfo {
213    /// The queried root corresponds to a tree that is the latest version of a given tree in the
214    /// forest.
215    LatestVersion(RootValue),
216
217    /// The queried root corresponds to a tree that is _not_ the latest version of a given tree in
218    /// the forest.
219    HistoricalVersion(RootValue),
220
221    /// The queried root does not belong to any tree that the forest knows about.
222    Missing,
223}
224
225// TREE ENTRY
226// ================================================================================================
227
228/// An entry in a given tree.
229#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
230pub struct TreeEntry {
231    pub key: Word,
232    pub value: Word,
233}
234impl TreeEntry {
235    pub fn index(&self) -> LeafIndex<SMT_DEPTH> {
236        LeafIndex::from(self.key)
237    }
238}
miden_crypto/merkle/smt/large_forest/root.rs

miden_crypto/merkle/smt/large_forest/
root.rs
