lambdaworks_crypto/merkle_tree/
proof.rs

1use alloc::vec::Vec;
2#[cfg(feature = "alloc")]
3use lambdaworks_math::traits::Serializable;
4use lambdaworks_math::{errors::DeserializationError, traits::Deserializable};
5
6use super::traits::IsMerkleTreeBackend;
7
8/// Stores a merkle path to some leaf.
9/// Internally, the necessary hashes are stored from root to leaf in the
10/// `merkle_path` field, in such a way that, if the merkle tree is of height `n`, the
11/// `i`-th element of `merkle_path` is the sibling node in the `n - 1 - i`-th check
12/// when verifying.
13#[derive(Debug, Clone)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15pub struct Proof<T: PartialEq + Eq> {
16    pub merkle_path: Vec<T>,
17}
18
19impl<T: PartialEq + Eq> Proof<T> {
20    /// Verifies a Merkle inclusion proof for the value contained at leaf index.
21    pub fn verify<B>(&self, root_hash: &B::Node, mut index: usize, value: &B::Data) -> bool
22    where
23        B: IsMerkleTreeBackend<Node = T>,
24    {
25        let mut hashed_value = B::hash_data(value);
26
27        for sibling_node in self.merkle_path.iter() {
28            if index.is_multiple_of(2) {
29                hashed_value = B::hash_new_parent(&hashed_value, sibling_node);
30            } else {
31                hashed_value = B::hash_new_parent(sibling_node, &hashed_value);
32            }
33
34            index >>= 1;
35        }
36
37        root_hash == &hashed_value
38    }
39}
40
41#[cfg(feature = "alloc")]
42impl<T> Serializable for Proof<T>
43where
44    T: Serializable + PartialEq + Eq,
45{
46    fn serialize(&self) -> Vec<u8> {
47        self.merkle_path
48            .iter()
49            .flat_map(|node| node.serialize())
50            .collect()
51    }
52}
53
54impl<T> Deserializable for Proof<T>
55where
56    T: Deserializable + PartialEq + Eq,
57{
58    fn deserialize(bytes: &[u8]) -> Result<Self, DeserializationError>
59    where
60        Self: Sized,
61    {
62        let mut merkle_path = Vec::new();
63        for elem in bytes[0..].chunks(8) {
64            let node = T::deserialize(elem)?;
65            merkle_path.push(node);
66        }
67        Ok(Self { merkle_path })
68    }
69}
70#[cfg(test)]
71mod tests {
72
73    #[cfg(feature = "alloc")]
74    use super::Proof;
75    use alloc::vec::Vec;
76    use lambdaworks_math::field::{element::FieldElement, fields::u64_prime_field::U64PrimeField};
77    #[cfg(feature = "alloc")]
78    use lambdaworks_math::traits::{Deserializable, Serializable};
79
80    use crate::merkle_tree::{merkle::MerkleTree, test_merkle::TestBackend};
81
82    /// Small field useful for starks, sometimes called min i goldilocks
83    /// Used in miden and winterfell
84    // This field shouldn't be defined inside the merkle tree module
85    pub type Ecgfp5 = U64PrimeField<0xFFFF_FFFF_0000_0001_u64>;
86    pub type Ecgfp5FE = FieldElement<Ecgfp5>;
87    pub type TestMerkleTreeEcgfp = MerkleTree<TestBackend<Ecgfp5>>;
88    #[cfg(feature = "alloc")]
89    pub type TestProofEcgfp5 = Proof<Ecgfp5FE>;
90
91    const MODULUS: u64 = 13;
92    type U64PF = U64PrimeField<MODULUS>;
93    type FE = FieldElement<U64PF>;
94
95    #[test]
96    #[cfg(feature = "alloc")]
97    fn serialize_proof_and_deserialize_using_be_it_get_a_consistent_proof() {
98        let merkle_path = [Ecgfp5FE::new(2), Ecgfp5FE::new(1), Ecgfp5FE::new(1)].to_vec();
99        let original_proof = TestProofEcgfp5 { merkle_path };
100        let serialize_proof = original_proof.serialize();
101        let proof: TestProofEcgfp5 = Proof::deserialize(&serialize_proof).unwrap();
102
103        for (o_node, node) in original_proof.merkle_path.iter().zip(proof.merkle_path) {
104            assert_eq!(*o_node, node);
105        }
106    }
107
108    #[test]
109    #[cfg(feature = "alloc")]
110    fn serialize_proof_and_deserialize_using_le_it_get_a_consistent_proof() {
111        let merkle_path = [Ecgfp5FE::new(2), Ecgfp5FE::new(1), Ecgfp5FE::new(1)].to_vec();
112        let original_proof = TestProofEcgfp5 { merkle_path };
113        let serialize_proof = original_proof.serialize();
114        let proof: TestProofEcgfp5 = Proof::deserialize(&serialize_proof).unwrap();
115
116        for (o_node, node) in original_proof.merkle_path.iter().zip(proof.merkle_path) {
117            assert_eq!(*o_node, node);
118        }
119    }
120
121    #[test]
122    // expected | 8 | 7 | 1 | 6 | 1 | 7 | 7 | 2 | 4 | 6 | 8 | 10 | 10 | 10 | 10 |
123    fn create_a_proof_over_value_that_belongs_to_a_given_merkle_tree_when_given_the_leaf_position()
124    {
125        let values: Vec<FE> = (1..6).map(FE::new).collect();
126        let merkle_tree = MerkleTree::<TestBackend<U64PF>>::build(&values).unwrap();
127        let proof = &merkle_tree.get_proof_by_pos(1).unwrap();
128        assert_merkle_path(&proof.merkle_path, &[FE::new(2), FE::new(1), FE::new(1)]);
129        assert!(proof.verify::<TestBackend<U64PF>>(&merkle_tree.root, 1, &FE::new(2)));
130    }
131
132    #[test]
133    #[cfg(feature = "alloc")]
134    fn merkle_proof_verifies_after_serialization_and_deserialization() {
135        let values: Vec<Ecgfp5FE> = (1..6).map(Ecgfp5FE::new).collect();
136        let merkle_tree = TestMerkleTreeEcgfp::build(&values).unwrap();
137        let proof = merkle_tree.get_proof_by_pos(1).unwrap();
138        let serialize_proof = proof.serialize();
139        let proof: TestProofEcgfp5 = Proof::deserialize(&serialize_proof).unwrap();
140        assert!(proof.verify::<TestBackend<Ecgfp5>>(&merkle_tree.root, 1, &Ecgfp5FE::new(2)));
141    }
142
143    #[test]
144    fn create_a_merkle_tree_with_10000_elements_and_verify_that_an_element_is_part_of_it() {
145        let values: Vec<Ecgfp5FE> = (1..10000).map(Ecgfp5FE::new).collect();
146        let merkle_tree = TestMerkleTreeEcgfp::build(&values).unwrap();
147        let proof = merkle_tree.get_proof_by_pos(9349).unwrap();
148        assert!(proof.verify::<TestBackend<Ecgfp5>>(&merkle_tree.root, 9349, &Ecgfp5FE::new(9350)));
149    }
150
151    fn assert_merkle_path(values: &[FE], expected_values: &[FE]) {
152        for (node, expected_node) in values.iter().zip(expected_values) {
153            assert_eq!(node, expected_node);
154        }
155    }
156
157    #[test]
158    fn verify_merkle_proof_for_single_value() {
159        const MODULUS: u64 = 13;
160        type U64PF = U64PrimeField<MODULUS>;
161        type FE = FieldElement<U64PF>;
162
163        let values: Vec<FE> = vec![FE::new(1)]; // Single element
164        let merkle_tree = MerkleTree::<TestBackend<U64PF>>::build(&values).unwrap();
165
166        // Update the expected root value based on the actual logic of TestBackend
167        // For example, in this case hashing a single `1` results in `2`
168        let expected_root = FE::new(2); // Assuming hashing a `1`s results in `2`
169        assert_eq!(
170            merkle_tree.root, expected_root,
171            "The root of the Merkle tree does not match the expected value."
172        );
173
174        // Verify the proof for the single element
175        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
176        assert!(
177            proof.verify::<TestBackend<U64PF>>(&merkle_tree.root, 0, &values[0]),
178            "The proof verification failed for the element at position 0."
179        );
180    }
181}
lambdaworks_crypto/merkle_tree/proof.rs

lambdaworks_crypto/merkle_tree/
proof.rs
