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
50impl<const HEIGHT: usize> Default for ChangelogPath<HEIGHT> {
51    fn default() -> Self {
52        Self([None; HEIGHT])
53    }
54}
55
56impl<const HEIGHT: usize> Deref for ChangelogPath<HEIGHT> {
57    type Target = [Option<[u8; 32]>; HEIGHT];
58
59    fn deref(&self) -> &Self::Target {
60        &self.0
61    }
62}
63
64impl<const HEIGHT: usize> DerefMut for ChangelogPath<HEIGHT> {
65    fn deref_mut(&mut self) -> &mut Self::Target {
66        &mut self.0
67    }
68}
69
70#[derive(Clone, Debug, PartialEq, Eq)]
71#[repr(C)]
72pub struct ChangelogEntry<const HEIGHT: usize> {
73    // Path of the changelog.
74    pub path: ChangelogPath<HEIGHT>,
75    // Index of the affected leaf.
76    pub index: u64,
77}
78
79pub type ChangelogEntry22 = ChangelogEntry<22>;
80pub type ChangelogEntry26 = ChangelogEntry<26>;
81pub type ChangelogEntry32 = ChangelogEntry<32>;
82pub type ChangelogEntry40 = ChangelogEntry<40>;
83
84impl<const HEIGHT: usize> ChangelogEntry<HEIGHT> {
85    pub fn new(path: ChangelogPath<HEIGHT>, index: usize) -> Self {
86        let index = index as u64;
87        Self { path, index }
88    }
89
90    pub fn default_with_index(index: usize) -> Self {
91        Self {
92            path: ChangelogPath::default(),
93            index: index as u64,
94        }
95    }
96
97    pub fn index(&self) -> usize {
98        self.index as usize
99    }
100
101    /// Returns an intersection index in the changelog entry which affects the
102    /// provided path.
103    ///
104    /// Determining it can be done by taking a XOR of the leaf index (which was
105    /// directly updated in the changelog entry) and the leaf index we are
106    /// trying to update.
107    ///
108    /// The number of bytes in the binary representations of the indexes is
109    /// determined by the height of the tree. For example, for the tree with
110    /// height 4, update attempt of leaf under index 2 and changelog affecting
111    /// index 4, critbit would be:
112    ///
113    /// 2 ^ 4 = 0b_0010 ^ 0b_0100 = 0b_0110 = 6
114    fn intersection_index(&self, leaf_index: usize) -> usize {
115        let padding = 64 - HEIGHT;
116        let common_path_len = ((leaf_index ^ self.index()) << padding).leading_zeros() as usize;
117        (HEIGHT - 1) - common_path_len
118    }
119
120    pub fn update_proof(
121        &self,
122        leaf_index: usize,
123        proof: &mut BoundedVec<[u8; 32]>,
124    ) -> Result<(), ConcurrentMerkleTreeError> {
125        if leaf_index != self.index() {
126            let intersection_index = self.intersection_index(leaf_index);
127            if let Some(node) = self.path[intersection_index] {
128                proof[intersection_index] = node;
129            }
130        } else {
131            // This case means that the leaf we are trying to update was
132            // already updated. Therefore, the right thing to do is to notify
133            // the caller to sync the local Merkle tree and update the leaf,
134            // if necessary.
135            return Err(ConcurrentMerkleTreeError::CannotUpdateLeaf);
136        }
137
138        Ok(())
139    }
140}
light_concurrent_merkle_tree/changelog.rs

light_concurrent_merkle_tree/
changelog.rs
