lambdaworks_crypto/merkle_tree/backends/
field_element.rs

1use crate::hash::poseidon::Poseidon;
2
3use crate::merkle_tree::traits::IsMerkleTreeBackend;
4use core::marker::PhantomData;
5use lambdaworks_math::{
6    field::{element::FieldElement, traits::IsField},
7    traits::AsBytes,
8};
9use sha3::{
10    digest::{generic_array::GenericArray, OutputSizeUser},
11    Digest,
12};
13
14#[derive(Clone)]
15pub struct FieldElementBackend<F, D: Digest, const NUM_BYTES: usize> {
16    phantom1: PhantomData<F>,
17    phantom2: PhantomData<D>,
18}
19
20impl<F, D: Digest, const NUM_BYTES: usize> Default for FieldElementBackend<F, D, NUM_BYTES> {
21    fn default() -> Self {
22        Self {
23            phantom1: PhantomData,
24            phantom2: PhantomData,
25        }
26    }
27}
28
29impl<F, D: Digest, const NUM_BYTES: usize> IsMerkleTreeBackend
30    for FieldElementBackend<F, D, NUM_BYTES>
31where
32    F: IsField,
33    FieldElement<F>: AsBytes + Sync + Send,
34    [u8; NUM_BYTES]: From<GenericArray<u8, <D as OutputSizeUser>::OutputSize>>,
35{
36    type Node = [u8; NUM_BYTES];
37    type Data = FieldElement<F>;
38
39    fn hash_data(input: &FieldElement<F>) -> [u8; NUM_BYTES] {
40        let mut hasher = D::new();
41        hasher.update(input.as_bytes());
42        hasher.finalize().into()
43    }
44
45    fn hash_new_parent(left: &[u8; NUM_BYTES], right: &[u8; NUM_BYTES]) -> [u8; NUM_BYTES] {
46        let mut hasher = D::new();
47        hasher.update(left);
48        hasher.update(right);
49        hasher.finalize().into()
50    }
51}
52
53#[derive(Clone, Default)]
54pub struct TreePoseidon<P: Poseidon + Default> {
55    _poseidon: PhantomData<P>,
56}
57
58impl<P> IsMerkleTreeBackend for TreePoseidon<P>
59where
60    P: Poseidon + Default,
61    FieldElement<P::F>: Sync + Send,
62{
63    type Node = FieldElement<P::F>;
64    type Data = FieldElement<P::F>;
65
66    fn hash_data(input: &FieldElement<P::F>) -> FieldElement<P::F> {
67        P::hash_single(input)
68    }
69
70    fn hash_new_parent(
71        left: &FieldElement<P::F>,
72        right: &FieldElement<P::F>,
73    ) -> FieldElement<P::F> {
74        P::hash(left, right)
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use alloc::vec::Vec;
81    use lambdaworks_math::field::{
82        element::FieldElement, fields::fft_friendly::stark_252_prime_field::Stark252PrimeField,
83    };
84    use sha3::{Keccak256, Keccak512, Sha3_256, Sha3_512};
85
86    use crate::merkle_tree::{backends::field_element::FieldElementBackend, merkle::MerkleTree};
87
88    type F = Stark252PrimeField;
89    type FE = FieldElement<F>;
90
91    #[test]
92    fn hash_data_field_element_backend_works_with_keccak_256() {
93        let values: Vec<FE> = (1..6).map(FE::from).collect();
94        let merkle_tree =
95            MerkleTree::<FieldElementBackend<F, Keccak256, 32>>::build(&values).unwrap();
96        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
97        assert!(proof.verify::<FieldElementBackend<F, Keccak256, 32>>(
98            &merkle_tree.root,
99            0,
100            &values[0]
101        ));
102    }
103
104    #[test]
105    fn hash_data_field_element_backend_works_with_sha3_256() {
106        let values: Vec<FE> = (1..6).map(FE::from).collect();
107        let merkle_tree =
108            MerkleTree::<FieldElementBackend<F, Sha3_256, 32>>::build(&values).unwrap();
109        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
110        assert!(proof.verify::<FieldElementBackend<F, Sha3_256, 32>>(
111            &merkle_tree.root,
112            0,
113            &values[0]
114        ));
115    }
116
117    #[test]
118    fn hash_data_field_element_backend_works_with_keccak_512() {
119        let values: Vec<FE> = (1..6).map(FE::from).collect();
120        let merkle_tree =
121            MerkleTree::<FieldElementBackend<F, Keccak512, 64>>::build(&values).unwrap();
122        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
123        assert!(proof.verify::<FieldElementBackend<F, Keccak512, 64>>(
124            &merkle_tree.root,
125            0,
126            &values[0]
127        ));
128    }
129
130    #[test]
131    fn hash_data_field_element_backend_works_with_sha3_512() {
132        let values: Vec<FE> = (1..6).map(FE::from).collect();
133        let merkle_tree =
134            MerkleTree::<FieldElementBackend<F, Sha3_512, 64>>::build(&values).unwrap();
135        let proof = merkle_tree.get_proof_by_pos(0).unwrap();
136        assert!(proof.verify::<FieldElementBackend<F, Sha3_512, 64>>(
137            &merkle_tree.root,
138            0,
139            &values[0]
140        ));
141    }
142}
lambdaworks_crypto/merkle_tree/backends/field_element.rs

lambdaworks_crypto/merkle_tree/backends/
field_element.rs
