lambdaworks_crypto/merkle_tree/backends/
field_element_vector.rs

1use core::marker::PhantomData;
2
3use crate::hash::poseidon::Poseidon;
4use crate::merkle_tree::traits::IsMerkleTreeBackend;
5use alloc::vec::Vec;
6use lambdaworks_math::{
7    field::{element::FieldElement, traits::IsField},
8    traits::AsBytes,
9};
10use sha3::{
11    digest::{generic_array::GenericArray, OutputSizeUser},
12    Digest,
13};
14
15#[derive(Clone)]
16pub struct FieldElementVectorBackend<F, D: Digest, const NUM_BYTES: usize> {
17    phantom1: PhantomData<F>,
18    phantom2: PhantomData<D>,
19}
20
21impl<F, D: Digest, const NUM_BYTES: usize> Default for FieldElementVectorBackend<F, D, NUM_BYTES> {
22    fn default() -> Self {
23        Self {
24            phantom1: PhantomData,
25            phantom2: PhantomData,
26        }
27    }
28}
29
30impl<F, D: Digest, const NUM_BYTES: usize> IsMerkleTreeBackend
31    for FieldElementVectorBackend<F, D, NUM_BYTES>
32where
33    F: IsField,
34    FieldElement<F>: AsBytes,
35    [u8; NUM_BYTES]: From<GenericArray<u8, <D as OutputSizeUser>::OutputSize>>,
36    Vec<FieldElement<F>>: Sync + Send,
37{
38    type Node = [u8; NUM_BYTES];
39    type Data = Vec<FieldElement<F>>;
40
41    fn hash_data(input: &Vec<FieldElement<F>>) -> [u8; NUM_BYTES] {
42        let mut hasher = D::new();
43        for element in input.iter() {
44            hasher.update(element.as_bytes());
45        }
46        let mut result_hash = [0_u8; NUM_BYTES];
47        result_hash.copy_from_slice(&hasher.finalize());
48        result_hash
49    }
50
51    fn hash_new_parent(left: &[u8; NUM_BYTES], right: &[u8; NUM_BYTES]) -> [u8; NUM_BYTES] {
52        let mut hasher = D::new();
53        hasher.update(left);
54        hasher.update(right);
55        let mut result_hash = [0_u8; NUM_BYTES];
56        result_hash.copy_from_slice(&hasher.finalize());
57        result_hash
58    }
59}
60
61#[derive(Clone, Default)]
62pub struct BatchPoseidonTree<P: Poseidon + Default> {
63    _poseidon: PhantomData<P>,
64}
65
66impl<P> IsMerkleTreeBackend for BatchPoseidonTree<P>
67where
68    P: Poseidon + Default,
69    Vec<FieldElement<P::F>>: Sync + Send,
70    FieldElement<P::F>: Sync + Send,
71{
72    type Node = FieldElement<P::F>;
73    type Data = Vec<FieldElement<P::F>>;
74
75    fn hash_data(input: &Vec<FieldElement<P::F>>) -> FieldElement<P::F> {
76        P::hash_many(input)
77    }
78
79    fn hash_new_parent(
80        left: &FieldElement<P::F>,
81        right: &FieldElement<P::F>,
82    ) -> FieldElement<P::F> {
83        P::hash(left, right)
84    }
85}
86
87#[cfg(test)]
88mod tests {
89    use lambdaworks_math::field::{
90        element::FieldElement, fields::fft_friendly::stark_252_prime_field::Stark252PrimeField,
91    };
92    use sha2::Sha512;
93    use sha3::{Keccak256, Keccak512, Sha3_256, Sha3_512};
94
95    use crate::merkle_tree::{
96        backends::field_element_vector::FieldElementVectorBackend, merkle::MerkleTree,
97    };
98
99    type F = Stark252PrimeField;
100    type FE = FieldElement<F>;
101
102    #[test]
103    fn hash_data_field_element_backend_works_with_sha3_256() {
104        let values = [
105            vec![FE::from(2u64), FE::from(11u64)],
106            vec![FE::from(3u64), FE::from(14u64)],
107            vec![FE::from(4u64), FE::from(7u64)],
108            vec![FE::from(5u64), FE::from(3u64)],
109            vec![FE::from(6u64), FE::from(5u64)],
110            vec![FE::from(7u64), FE::from(16u64)],
111            vec![FE::from(8u64), FE::from(19u64)],
112            vec![FE::from(9u64), FE::from(21u64)],
113        ];
114        let merkle_tree =
115            MerkleTree::<FieldElementVectorBackend<F, Sha3_256, 32>>::build(&values).unwrap();
116        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
117        assert!(proof.verify::<FieldElementVectorBackend<F, Sha3_256, 32>>(
118            &merkle_tree.root,
119            0,
120            &values[0]
121        ));
122    }
123
124    #[test]
125    fn hash_data_field_element_backend_works_with_keccak256() {
126        let values = [
127            vec![FE::from(2u64), FE::from(11u64)],
128            vec![FE::from(3u64), FE::from(14u64)],
129            vec![FE::from(4u64), FE::from(7u64)],
130            vec![FE::from(5u64), FE::from(3u64)],
131            vec![FE::from(6u64), FE::from(5u64)],
132            vec![FE::from(7u64), FE::from(16u64)],
133            vec![FE::from(8u64), FE::from(19u64)],
134            vec![FE::from(9u64), FE::from(21u64)],
135        ];
136        let merkle_tree =
137            MerkleTree::<FieldElementVectorBackend<F, Keccak256, 32>>::build(&values).unwrap();
138        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
139        assert!(proof.verify::<FieldElementVectorBackend<F, Keccak256, 32>>(
140            &merkle_tree.root,
141            0,
142            &values[0]
143        ));
144    }
145
146    #[test]
147    fn hash_data_field_element_backend_works_with_sha3_512() {
148        let values = [
149            vec![FE::from(2u64), FE::from(11u64)],
150            vec![FE::from(3u64), FE::from(14u64)],
151            vec![FE::from(4u64), FE::from(7u64)],
152            vec![FE::from(5u64), FE::from(3u64)],
153            vec![FE::from(6u64), FE::from(5u64)],
154            vec![FE::from(7u64), FE::from(16u64)],
155            vec![FE::from(8u64), FE::from(19u64)],
156            vec![FE::from(9u64), FE::from(21u64)],
157        ];
158        let merkle_tree =
159            MerkleTree::<FieldElementVectorBackend<F, Sha3_512, 64>>::build(&values).unwrap();
160        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
161        assert!(proof.verify::<FieldElementVectorBackend<F, Sha3_512, 64>>(
162            &merkle_tree.root,
163            0,
164            &values[0]
165        ));
166    }
167
168    #[test]
169    fn hash_data_field_element_backend_works_with_keccak512() {
170        let values = [
171            vec![FE::from(2u64), FE::from(11u64)],
172            vec![FE::from(3u64), FE::from(14u64)],
173            vec![FE::from(4u64), FE::from(7u64)],
174            vec![FE::from(5u64), FE::from(3u64)],
175            vec![FE::from(6u64), FE::from(5u64)],
176            vec![FE::from(7u64), FE::from(16u64)],
177            vec![FE::from(8u64), FE::from(19u64)],
178            vec![FE::from(9u64), FE::from(21u64)],
179        ];
180        let merkle_tree =
181            MerkleTree::<FieldElementVectorBackend<F, Keccak512, 64>>::build(&values).unwrap();
182        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
183        assert!(proof.verify::<FieldElementVectorBackend<F, Keccak512, 64>>(
184            &merkle_tree.root,
185            0,
186            &values[0]
187        ));
188    }
189
190    #[test]
191    fn hash_data_field_element_backend_works_with_sha2_512() {
192        let values = [
193            vec![FE::from(2u64), FE::from(11u64)],
194            vec![FE::from(3u64), FE::from(14u64)],
195            vec![FE::from(4u64), FE::from(7u64)],
196            vec![FE::from(5u64), FE::from(3u64)],
197            vec![FE::from(6u64), FE::from(5u64)],
198            vec![FE::from(7u64), FE::from(16u64)],
199            vec![FE::from(8u64), FE::from(19u64)],
200            vec![FE::from(9u64), FE::from(21u64)],
201        ];
202        let merkle_tree =
203            MerkleTree::<FieldElementVectorBackend<F, Sha512, 64>>::build(&values).unwrap();
204        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
205        assert!(proof.verify::<FieldElementVectorBackend<F, Sha512, 64>>(
206            &merkle_tree.root,
207            0,
208            &values[0]
209        ));
210    }
211}
lambdaworks_crypto/merkle_tree/backends/field_element_vector.rs

lambdaworks_crypto/merkle_tree/backends/
field_element_vector.rs
