No way to config for sorting pairs/ leaves ?

[ethereumdegen]

No way to config for sorting pairs/ leaves ?

ethereum merkle trees typically sort leaves and sort pairs

[evd0kim]

@ethereumdegen you have to override Hasher trait as suggested in the comments of this library. Working code is here

use rs_merkle::Hasher as RsHasher;
use rs_merkle::{
    MerkleProof, MerkleTree,
};

use rs_merkle::Hasher;
use sha2::{Digest, Sha256};
use std::mem;

#[derive(Clone)]
pub struct CustomSha256Hasher;

impl Hasher for CustomSha256Hasher {
    type Hash = [u8; 32];

    fn hash(data: &[u8]) -> Self::Hash {
        let mut hasher = Sha256::new();
        hasher.update(data);
        let result = hasher.finalize();
        let mut hash = [0u8; 32];
        hash.copy_from_slice(&result);
        hash
    }

    fn concat_and_hash(left: &Self::Hash, right: Option<&Self::Hash>) -> Self::Hash {
        match right {
            Some(right_node) => {
                let mut left_vec: Vec<u8> = left.to_vec();
                let mut right_vec: Vec<u8> = right_node.to_vec();

                // **Sort before concatenation**
                if right_vec < left_vec {
                    mem::swap(&mut left_vec, &mut right_vec);
                }

                let mut concatenated = left_vec;
                concatenated.extend_from_slice(&right_vec);

                Self::hash(&concatenated)
            }
            None => *left, // If no right node, return left hash
        }
    }
}

fn main() {
    // Helper function to print bytes as hex
    fn print_hex(label: &str, bytes: &[u8]) {
        print!("{}: 0x", label);
        for byte in bytes {
            print!("{:02x}", byte);
        }
        println!();
    }

    let leaf_values = ["a", "b", "c", "d", "e", "f"];
    let leaves: Vec<[u8; 32]> = leaf_values
        .iter()
        .map(|x| CustomSha256Hasher::hash(x.as_bytes()))
        .collect();

    for (i, l) in leaves.clone().into_iter().enumerate() {
        //println!("{:?}", l);
        let label = format!("leave {}", i);
        print_hex(&label, &l);
    };

    let merkle_tree = MerkleTree::<CustomSha256Hasher>::from_leaves(&leaves);
    let indices_to_prove = vec![1];
    let leaves_to_prove = leaves.get(1..2).expect("can't get leaves to prove");
    let merkle_proof = merkle_tree.proof(&indices_to_prove);
    let merkle_root = merkle_tree.root().expect("couldn't get the merkle root");
    print_hex("Rs-Merkle lib root: ", &merkle_root);
    // Serialize proof to pass it to the client
    let proof_bytes = merkle_proof.to_bytes();
    print_hex("Rs-Merkle lib proof: ", &proof_bytes);
    // Parse proof back on the client
    let proof = MerkleProof::<CustomSha256Hasher>::try_from(proof_bytes).expect("Proof Ok");

    assert!(proof.verify(merkle_root, &indices_to_prove, leaves_to_prove, leaves.len()));

    /*
    Merkly a30ba95a1a5dc397fe45ea20105363b08d682b864a28f4940419a29349a28325
    [Node(3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d, Side.RIGHT), Node(800e03ddb2432933692401d1631850c0af91953fd9c8f3874488c0541dfcf413, Side.RIGHT), Node(0163e88f03670301d757e64f17f9d99fa3e7567a5f3ce69d58eb72ee0bbb3662, Side.RIGHT)]
    Input: a
    SHA-256: ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb
     */
}