light_concurrent_merkle_tree/
changelog.rs

1use std::ops::{Deref, DerefMut};
2
3use light_bounded_vec::BoundedVec;
4
5use crate::errors::ConcurrentMerkleTreeError;
6
7#[derive(Clone, Debug, PartialEq, Eq)]
8#[repr(transparent)]
9pub struct ChangelogPath<const HEIGHT: usize>(pub [Option<[u8; 32]>; HEIGHT]);
10
11impl<const HEIGHT: usize> ChangelogPath<HEIGHT> {
12    pub fn from_fn<F>(cb: F) -> Self
13    where
14        F: FnMut(usize) -> Option<[u8; 32]>,
15    {
16        Self(std::array::from_fn(cb))
17    }
18
19    /// Checks whether the path is equal to the provided [`BoundedVec`].
20    ///
21    /// [`ChangelogPath`] might contain `None` nodes at the end, which
22    /// mean that it does not define them, but the following changelog
23    /// paths are expected to overwrite them.
24    ///
25    /// Therefore, the comparison ends on the first encountered first
26    /// `None`. If all `Some` nodes are equal to the corresponding ones
27    /// in the provided vector, the result is `true`.
28    pub fn eq_to(&self, other: BoundedVec<[u8; 32]>) -> bool {
29        if other.len() != HEIGHT {
30            return false;
31        }
32
33        for i in 0..HEIGHT {
34            let changelog_node = self.0[i];
35            let path_node = other[i];
36            match changelog_node {
37                Some(changelog_node) => {
38                    if changelog_node != path_node {
39                        return false;
40                    }
41                }
42                None => break,
43            }
44        }
45
46        true
47    }
48
49    pub fn eq_to_vec(&self, other: Vec<[u8; 32]>) -> bool {
50        if other.len() != HEIGHT {
51            return false;
52        }
53
54        for (i, path_node) in other.iter().enumerate() {
55            let changelog_node = self.0[i];
56            match changelog_node {
57                Some(changelog_node) => {
58                    if changelog_node != *path_node {
59                        return false;
60                    }
61                }
62                None => break,
63            }
64        }
65
66        true
67    }
68}
69
70impl<const HEIGHT: usize> Default for ChangelogPath<HEIGHT> {
71    fn default() -> Self {
72        Self([None; HEIGHT])
73    }
74}
75
76impl<const HEIGHT: usize> Deref for ChangelogPath<HEIGHT> {
77    type Target = [Option<[u8; 32]>; HEIGHT];
78
79    fn deref(&self) -> &Self::Target {
80        &self.0
81    }
82}
83
84impl<const HEIGHT: usize> DerefMut for ChangelogPath<HEIGHT> {
85    fn deref_mut(&mut self) -> &mut Self::Target {
86        &mut self.0
87    }
88}
89
90#[derive(Clone, Debug, PartialEq, Eq)]
91#[repr(C)]
92pub struct ChangelogEntry<const HEIGHT: usize> {
93    // Path of the changelog.
94    pub path: ChangelogPath<HEIGHT>,
95    // Index of the affected leaf.
96    pub index: u64,
97}
98
99pub type ChangelogEntry22 = ChangelogEntry<22>;
100pub type ChangelogEntry26 = ChangelogEntry<26>;
101pub type ChangelogEntry32 = ChangelogEntry<32>;
102pub type ChangelogEntry40 = ChangelogEntry<40>;
103
104impl<const HEIGHT: usize> ChangelogEntry<HEIGHT> {
105    pub fn new(path: ChangelogPath<HEIGHT>, index: usize) -> Self {
106        let index = index as u64;
107        Self { path, index }
108    }
109
110    pub fn default_with_index(index: usize) -> Self {
111        Self {
112            path: ChangelogPath::default(),
113            index: index as u64,
114        }
115    }
116
117    pub fn index(&self) -> usize {
118        self.index as usize
119    }
120
121    /// Returns an intersection index in the changelog entry which affects the
122    /// provided path.
123    ///
124    /// Determining it can be done by taking a XOR of the leaf index (which was
125    /// directly updated in the changelog entry) and the leaf index we are
126    /// trying to update.
127    ///
128    /// The number of bytes in the binary representations of the indexes is
129    /// determined by the height of the tree. For example, for the tree with
130    /// height 4, update attempt of leaf under index 2 and changelog affecting
131    /// index 4, critbit would be:
132    ///
133    /// 2 ^ 4 = 0b_0010 ^ 0b_0100 = 0b_0110 = 6
134    fn intersection_index(&self, leaf_index: usize) -> usize {
135        let padding = 64 - HEIGHT;
136        let common_path_len = ((leaf_index ^ self.index()) << padding).leading_zeros() as usize;
137        (HEIGHT - 1) - common_path_len
138    }
139
140    pub fn update_proof(
141        &self,
142        leaf_index: usize,
143        proof: &mut BoundedVec<[u8; 32]>,
144    ) -> Result<(), ConcurrentMerkleTreeError> {
145        if leaf_index != self.index() {
146            let intersection_index = self.intersection_index(leaf_index);
147            if let Some(node) = self.path[intersection_index] {
148                proof[intersection_index] = node;
149            }
150        } else {
151            // This case means that the leaf we are trying to update was
152            // already updated. Therefore, the right thing to do is to notify
153            // the caller to sync the local Merkle tree and update the leaf,
154            // if necessary.
155            return Err(ConcurrentMerkleTreeError::CannotUpdateLeaf);
156        }
157
158        Ok(())
159    }
160}
light_concurrent_merkle_tree/changelog.rs

light_concurrent_merkle_tree/
changelog.rs
