[TASK] Simple Merkle tree and Path

[lazovicff]

Path:

// Path
#[derive(Clone)]
pub struct Path<F: PrimeField, H: FieldHasher, const N: usize> {
    pub(crate) path: [F; N],
}

impl<F: PrimeField, H: FieldHasher, const N: usize> Path<F, H, N> {
    pub fn check_membership(
      &self,
      root_hash: &F,
      leaf: &F,
      hasher: &H,
    ) -> Result<bool, Error>;
    
    pub fn calculate_root(&self, leaf: &F, hasher: &H) -> Result<F, Error>;
}

Merkle tree:

/// Merkle sparse tree
pub struct SparseMerkleTree<F: PrimeField, H: FieldHasher, const D: [u8; 32], const N: usize> {
    /// data of the tree
    pub tree: BTreeMap<u64, F>,
    empty_hashes: [F: N],
}

impl<F: PrimeField, H: FieldHasher> SparseMerkleTree<F, H> {

    pub fn insert_batch(
        &mut self,
        leaves: &BTreeMap<u32, F>,
        hasher: &H,
    ) -> Result<(), Error>;
    
    pub fn new(
        leaves: &BTreeMap<u32, F>,
        hasher: &H,
    ) -> Result<Self, Error>;
    
    pub fn new_sequential(
        leaves: &[F],
        hasher: &H,
    ) -> Result<Self, Error>;
    
    pub fn root(&self) -> F;
    
    pub fn generate_membership_proof(&self, index: u64) -> Path<F, H, N>;
}

Calculating empty hash:

pub fn gen_empty_hashes<F: PrimeField, H: FieldHasher, const N: usize>(
    hasher: &H
    empty_bytes: [u8; 32]
) -> Result<[F; N], Error> {
    let mut empty_hashes = [F::zero(); N];

    let mut empty_hash = F::from_le_mod_order(&empty_bytes);
    empty_hashes.push(empty_hash.clone());

    for i in 1..=N {
        empty_hash = hasher.hash_two(&empty_hash, &empty_hash)?;
        empty_hashes[i] = empty_hash.clone();
    }
    
    Ok(empty_hashes)
}

[drewstone]

For default empty element, I wonder if something like this will work. impl<F: PrimeField, H: FieldHasher> SparseMerkleTree<F, H, const D: F> or SparseMerkleTree<F, H, const D: [u8; 32]>

// when implementing
const DefaultZero = F::from([1u8; 32])
SparseMerkleTree<ark_bn254::Fr, H, DefaultZero>