spl_concurrent_merkle_tree/
changelog.rs

1use crate::{
2    hash::hash_to_parent,
3    node::{Node, EMPTY},
4};
5
6/// Stores the path of nodes changed in a tree by a Merkle tree operation
7#[derive(Copy, Clone, Debug, PartialEq, Eq)]
8#[repr(C)]
9pub struct ChangeLog<const MAX_DEPTH: usize> {
10    /// Historical root value before Path was applied
11    pub root: Node,
12    /// Nodes of off-chain merkle tree
13    pub path: [Node; MAX_DEPTH],
14    /// Bitmap of node parity (used when hashing)
15    pub index: u32,
16    pub _padding: u32,
17}
18
19impl<const MAX_DEPTH: usize> Default for ChangeLog<MAX_DEPTH> {
20    fn default() -> Self {
21        Self {
22            root: EMPTY,
23            path: [EMPTY; MAX_DEPTH],
24            index: 0,
25            _padding: 0,
26        }
27    }
28}
29
30impl<const MAX_DEPTH: usize> ChangeLog<MAX_DEPTH> {
31    pub fn new(root: Node, path: [Node; MAX_DEPTH], index: u32) -> Self {
32        Self {
33            root,
34            path,
35            index,
36            _padding: 0,
37        }
38    }
39
40    /// Returns the leaf value modified when the change log was recorded
41    pub fn get_leaf(&self) -> Node {
42        self.path[0]
43    }
44
45    /// Sets all change log values from a leaf and valid proof
46    pub fn replace_and_recompute_path(
47        &mut self,
48        index: u32,
49        mut node: Node,
50        proof: &[Node],
51    ) -> Node {
52        self.index = index;
53        for (i, sibling) in proof.iter().enumerate() {
54            self.path[i] = node;
55            hash_to_parent(&mut node, sibling, self.index >> i & 1 == 0);
56        }
57        self.root = node;
58        node
59    }
60
61    /// Fast forwards the given proof and corresponding leaf by applying an
62    /// update from the current change log
63    pub fn update_proof_or_leaf(
64        &self,
65        leaf_index: u32,
66        proof: &mut [Node; MAX_DEPTH],
67        leaf: &mut Node,
68    ) {
69        let padding: usize = 32 - MAX_DEPTH;
70        if leaf_index != self.index {
71            // This bit math is used to identify which node in the proof
72            // we need to swap for a corresponding node in a saved change log
73            let common_path_len = ((leaf_index ^ self.index) << padding).leading_zeros() as usize;
74            let critbit_index = (MAX_DEPTH - 1) - common_path_len;
75            proof[critbit_index] = self.path[critbit_index];
76        } else {
77            *leaf = self.get_leaf();
78        }
79    }
80}
spl_concurrent_merkle_tree/changelog.rs

spl_concurrent_merkle_tree/
changelog.rs
