unified_bridge/local_exit_tree/
mod.rs

1use agglayer_primitives::{keccak::keccak256_combine, Digest};
2use agglayer_tries::utils::empty_hash_array_at_height;
3use serde::{Deserialize, Serialize};
4use serde_with::serde_as;
5use thiserror::Error;
6
7pub mod proof;
8
9/// Represents a local exit tree as defined by the LxLy bridge.
10#[serde_as]
11#[derive(Clone, Debug, Serialize, Deserialize)]
12pub struct LocalExitTree<const TREE_DEPTH: usize = 32> {
13    /// The number of inserted (non-empty) leaves.
14    pub leaf_count: u32,
15
16    /// The frontier, with hashes from bottom to top, only of the rightmost
17    /// non-empty node. This is not a path in the tree, and only contains
18    /// full subtrees.
19    ///
20    /// It contains meaningful values only up to the current root of the tree,
21    /// computed by log2(leaf_count). After that, all values are zeroed out.
22    #[serde_as(as = "[_; TREE_DEPTH]")]
23    pub frontier: [Digest; TREE_DEPTH],
24}
25
26#[derive(Clone, Debug, Error, Serialize, Deserialize, PartialEq, Eq)]
27pub enum LocalExitTreeError {
28    #[error("Leaf index overflow")]
29    LeafIndexOverflow,
30
31    #[error("Index out of bounds")]
32    IndexOutOfBounds,
33
34    #[error("Frontier index out of bounds")]
35    FrontierIndexOutOfBounds,
36}
37
38impl<const TREE_DEPTH: usize> Default for LocalExitTree<TREE_DEPTH> {
39    #[inline]
40    fn default() -> Self {
41        Self {
42            leaf_count: 0,
43            frontier: [Digest::default(); TREE_DEPTH],
44        }
45    }
46}
47
48impl<const TREE_DEPTH: usize> LocalExitTree<TREE_DEPTH> {
49    const MAX_NUM_LEAVES: u32 = ((1u64 << TREE_DEPTH) - 1) as u32;
50
51    /// Creates a new empty [`LocalExitTree`].
52    #[inline]
53    pub fn new() -> Self {
54        Self::default()
55    }
56
57    #[inline]
58    pub fn leaf_count(&self) -> u32 {
59        self.leaf_count
60    }
61
62    #[inline]
63    pub fn frontier(&self) -> [Digest; TREE_DEPTH] {
64        self.frontier
65    }
66
67    /// Creates a new [`LocalExitTree`] and populates its leaves.
68    #[inline]
69    pub fn from_leaves(leaves: impl Iterator<Item = Digest>) -> Result<Self, LocalExitTreeError> {
70        let mut tree = Self::new();
71
72        for leaf in leaves {
73            tree.add_leaf(leaf)?;
74        }
75
76        Ok(tree)
77    }
78
79    /// Creates a new [`LocalExitTree`] from its parts: leaf count, and
80    /// frontier.
81    #[inline]
82    pub fn from_parts(leaf_count: u32, frontier: [Digest; TREE_DEPTH]) -> Self {
83        Self {
84            leaf_count,
85            frontier,
86        }
87    }
88    /// Appends a leaf to the tree.
89    #[inline]
90    pub fn add_leaf(&mut self, leaf: Digest) -> Result<u32, LocalExitTreeError> {
91        if self.leaf_count >= Self::MAX_NUM_LEAVES {
92            return Err(LocalExitTreeError::LeafIndexOverflow);
93        }
94        // the index at which the new entry will be inserted
95        let frontier_insertion_index: usize = {
96            let leaf_count_after_insertion = self.leaf_count + 1;
97
98            leaf_count_after_insertion.trailing_zeros() as usize
99        };
100
101        // the new entry to be inserted in the frontier
102        let new_frontier_entry = {
103            let mut entry = leaf;
104            for frontier_ele in &self.frontier[0..frontier_insertion_index] {
105                entry = keccak256_combine([frontier_ele, &entry]);
106            }
107
108            entry
109        };
110
111        // update tree
112        self.frontier[frontier_insertion_index] = new_frontier_entry;
113        self.leaf_count = self
114            .leaf_count
115            .checked_add(1)
116            .ok_or(LocalExitTreeError::LeafIndexOverflow)?;
117
118        Ok(self.leaf_count)
119    }
120
121    /// Computes and returns the root of the tree.
122    #[inline]
123    pub fn get_root(&self) -> Digest {
124        // `root` is the hash of the node we’re going to fill next.
125        // Here, we compute the root, starting from the next (yet unfilled) leaf hash.
126        let mut root = Digest::default();
127
128        for (height, empty_hash_at_height) in empty_hash_array_at_height::<TREE_DEPTH>()
129            .iter()
130            .enumerate()
131        {
132            if get_bit_at(self.leaf_count, height) == 1 {
133                root = keccak256_combine([&self.frontier[height], &root]);
134            } else {
135                root = keccak256_combine([&root, empty_hash_at_height]);
136            }
137        }
138
139        root
140    }
141}
142
143/// Returns the bit value at index `bit_idx` in `target`
144#[inline]
145fn get_bit_at(target: u32, bit_idx: usize) -> u32 {
146    (target >> bit_idx) & 1
147}
148
149#[cfg(test)]
150mod tests {
151    use agglayer_primitives::{Address, Hashable, U256};
152
153    use crate::{bridge_exit::BridgeExit, local_exit_tree::LocalExitTree, token_info::LeafType};
154
155    #[test]
156    fn test_deposit_hash() {
157        let mut deposit = BridgeExit::new(
158            LeafType::Transfer,
159            0.into(),
160            Address::ZERO,
161            1.into(),
162            Address::ZERO,
163            U256::default(),
164            vec![],
165        );
166
167        let amount_bytes = hex::decode("8ac7230489e80000").unwrap_or_default();
168        deposit.amount = U256::try_from_be_slice(amount_bytes.as_slice()).unwrap();
169
170        let dest_addr = hex::decode("c949254d682d8c9ad5682521675b8f43b102aec4").unwrap_or_default();
171        deposit.dest_address.as_mut().copy_from_slice(&dest_addr);
172
173        let leaf_hash = deposit.hash();
174        assert_eq!(
175            "22ed288677b4c2afd83a6d7d55f7df7f4eaaf60f7310210c030fd27adacbc5e0",
176            hex::encode(leaf_hash)
177        );
178
179        let mut dm = LocalExitTree::<32>::new();
180        dm.add_leaf(leaf_hash).unwrap();
181        let dm_root = dm.get_root();
182        assert_eq!(
183            "5ba002329b53c11a2f1dfe90b11e031771842056cf2125b43da8103c199dcd7f",
184            hex::encode(dm_root.as_slice())
185        );
186    }
187}
unified_bridge/local_exit_tree/mod.rs

unified_bridge/local_exit_tree/
mod.rs
