light_indexed_merkle_tree/
reference.rs

1use std::marker::PhantomData;
2
3use light_bounded_vec::{BoundedVec, BoundedVecError};
4use light_concurrent_merkle_tree::light_hasher::{errors::HasherError, Hasher};
5use light_merkle_tree_reference::{MerkleTree, ReferenceMerkleTreeError};
6use light_utils::bigint::bigint_to_be_bytes_array;
7use num_bigint::BigUint;
8use num_traits::{CheckedAdd, CheckedSub, Num, ToBytes, Unsigned};
9use thiserror::Error;
10
11use crate::{
12    array::{IndexedArray, IndexedElement},
13    errors::IndexedMerkleTreeError,
14    HIGHEST_ADDRESS_PLUS_ONE,
15};
16
17#[derive(Debug, Error)]
18pub enum IndexedReferenceMerkleTreeError {
19    #[error(transparent)]
20    Indexed(#[from] IndexedMerkleTreeError),
21    #[error(transparent)]
22    Reference(#[from] ReferenceMerkleTreeError),
23    #[error(transparent)]
24    Hasher(#[from] HasherError),
25}
26
27#[derive(Debug, Clone)]
28#[repr(C)]
29pub struct IndexedMerkleTree<H, I>
30where
31    H: Hasher,
32    I: CheckedAdd + CheckedSub + Copy + Clone + PartialOrd + ToBytes + TryFrom<usize> + Unsigned,
33{
34    pub merkle_tree: MerkleTree<H>,
35    _index: PhantomData<I>,
36}
37
38impl<H, I> IndexedMerkleTree<H, I>
39where
40    H: Hasher,
41    I: CheckedAdd + CheckedSub + Copy + Clone + PartialOrd + ToBytes + TryFrom<usize> + Unsigned,
42    usize: From<I>,
43{
44    pub fn new(
45        height: usize,
46        canopy_depth: usize,
47    ) -> Result<Self, IndexedReferenceMerkleTreeError> {
48        let mut merkle_tree = MerkleTree::new(height, canopy_depth);
49
50        // Append the first low leaf, which has value 0 and does not point
51        // to any other leaf yet.
52        // This low leaf is going to be updated during the first `update`
53        // operation.
54        merkle_tree.append(&H::zero_indexed_leaf())?;
55
56        Ok(Self {
57            merkle_tree,
58            _index: PhantomData,
59        })
60    }
61
62    /// Initializes the reference indexed merkle tree on par with the
63    /// on-chain indexed concurrent merkle tree.
64    /// Inserts the ranges 0 - BN254 Field Size - 1 into the tree.
65    pub fn init(&mut self) -> Result<(), IndexedReferenceMerkleTreeError> {
66        let mut indexed_array = IndexedArray::<H, I>::default();
67        let init_value = BigUint::from_str_radix(HIGHEST_ADDRESS_PLUS_ONE, 10).unwrap();
68        let nullifier_bundle = indexed_array.append(&init_value)?;
69        let new_low_leaf = nullifier_bundle
70            .new_low_element
71            .hash::<H>(&nullifier_bundle.new_element.value)?;
72
73        self.merkle_tree.update(&new_low_leaf, 0)?;
74        let new_leaf = nullifier_bundle
75            .new_element
76            .hash::<H>(&nullifier_bundle.new_element_next_value)?;
77        self.merkle_tree.append(&new_leaf)?;
78        Ok(())
79    }
80
81    pub fn get_path_of_leaf(
82        &self,
83        index: usize,
84        full: bool,
85    ) -> Result<BoundedVec<[u8; 32]>, BoundedVecError> {
86        self.merkle_tree.get_path_of_leaf(index, full)
87    }
88
89    pub fn get_proof_of_leaf(
90        &self,
91        index: usize,
92        full: bool,
93    ) -> Result<BoundedVec<[u8; 32]>, BoundedVecError> {
94        self.merkle_tree.get_proof_of_leaf(index, full)
95    }
96
97    pub fn root(&self) -> [u8; 32] {
98        self.merkle_tree.root()
99    }
100
101    // TODO: rename input values
102    pub fn update(
103        &mut self,
104        new_low_element: &IndexedElement<I>,
105        new_element: &IndexedElement<I>,
106        new_element_next_value: &BigUint,
107    ) -> Result<(), IndexedReferenceMerkleTreeError> {
108        // Update the low element.
109        let new_low_leaf = new_low_element.hash::<H>(&new_element.value)?;
110        self.merkle_tree
111            .update(&new_low_leaf, usize::from(new_low_element.index))?;
112
113        // Append the new element.
114        let new_leaf = new_element.hash::<H>(new_element_next_value)?;
115        self.merkle_tree.append(&new_leaf)?;
116
117        Ok(())
118    }
119
120    // TODO: add append with new value, so that we don't need to compute the lowlevel values manually
121    pub fn append(
122        &mut self,
123        value: &BigUint,
124        indexed_array: &mut IndexedArray<H, I>,
125    ) -> Result<(), IndexedReferenceMerkleTreeError> {
126        let nullifier_bundle = indexed_array.append(value).unwrap();
127        self.update(
128            &nullifier_bundle.new_low_element,
129            &nullifier_bundle.new_element,
130            &nullifier_bundle.new_element_next_value,
131        )?;
132
133        Ok(())
134    }
135
136    pub fn get_non_inclusion_proof(
137        &self,
138        value: &BigUint,
139        indexed_array: &IndexedArray<H, I>,
140    ) -> Result<NonInclusionProof, IndexedReferenceMerkleTreeError> {
141        let (low_element, _next_value) = indexed_array.find_low_element_for_nonexistent(value)?;
142        let merkle_proof = self
143            .get_proof_of_leaf(usize::from(low_element.index), true)
144            .unwrap();
145        let higher_range_value = indexed_array
146            .get(low_element.next_index())
147            .unwrap()
148            .value
149            .clone();
150        Ok(NonInclusionProof {
151            root: self.root(),
152            value: bigint_to_be_bytes_array::<32>(value).unwrap(),
153            leaf_lower_range_value: bigint_to_be_bytes_array::<32>(&low_element.value).unwrap(),
154            leaf_higher_range_value: bigint_to_be_bytes_array::<32>(&higher_range_value).unwrap(),
155            leaf_index: low_element.index.into(),
156            next_index: low_element.next_index(),
157            merkle_proof,
158        })
159    }
160
161    pub fn verify_non_inclusion_proof(
162        &self,
163        proof: &NonInclusionProof,
164    ) -> Result<(), IndexedReferenceMerkleTreeError> {
165        let array_element = IndexedElement::<usize> {
166            value: BigUint::from_bytes_be(&proof.value),
167            index: proof.leaf_index,
168            next_index: proof.next_index,
169        };
170        let leaf_hash =
171            array_element.hash::<H>(&BigUint::from_bytes_be(&proof.leaf_higher_range_value))?;
172        self.merkle_tree
173            .verify(&leaf_hash, &proof.merkle_proof, proof.leaf_index)
174            .unwrap();
175        Ok(())
176    }
177}
178
179// TODO: check why next_index is usize while index is I
180/// We prove non-inclusion by:
181/// 1. Showing that value is greater than leaf_lower_range_value and less than leaf_higher_range_value
182/// 2. Showing that the leaf_hash H(leaf_lower_range_value, leaf_next_index, leaf_higher_value) is included in the root (Merkle tree)
183#[derive(Debug)]
184pub struct NonInclusionProof {
185    pub root: [u8; 32],
186    pub value: [u8; 32],
187    pub leaf_lower_range_value: [u8; 32],
188    pub leaf_higher_range_value: [u8; 32],
189    pub leaf_index: usize,
190    pub next_index: usize,
191    pub merkle_proof: BoundedVec<[u8; 32]>,
192}
light_indexed_merkle_tree/reference.rs

light_indexed_merkle_tree/
reference.rs
