antouhou / rs-merkle Goto Github PK

When verifying a proof, we rely on the Prover (a potentially malicious party in our case) to inform the Verifier about the correct number of the leaves in the tree. Trying to verify with an incorrect number causes a panic.

Can be reproduced by modifying a line in this example:

No way to config for sorting pairs/ leaves ?

ethereum merkle trees typically sort leaves and sort pairs

First off I want to thank you for making this crate. I had one potential suggestion to improve the crate. I feel that it would be useful to have a helper function that enables a leaf node in a given tree to be updated. I tried looking in the documentation to see if such functionality already existed but I couldn't find anything.
My current workaround for this issue is to update the set of leaves and create an entirely new MerkleTree from there, however, this is very wasteful especially when dealing with large leaf counts.
Do you have any suggestions for a better way to do something like this, or if a function could be designed to do this?

The use of a Float32 type in src/utils/indices.rs results in the crate not compiling on CosmWasm's WASM VM.
A fix has been proposed on this pull request.

currently tree depth is incorrectly calculated for power-of-two leaf count. it is +1 than what it should be.

pub fn tree_depth(leaves_count: usize) -> usize {
    8 * core::mem::size_of::<usize>() - leaves_count.leading_zeros() as usize
}

e.g. for leaves_count == 4 this will return 3, whereas it should be 2.

This bug doesn't seem to open any exploitable vectors, it only causes to allocate memory for a non-existent layer.
It is still a good idea to fix this.

Hi,

Proof verification does not work for any combination of indices.

Here's what I tried:

let leaves = [
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
    Sha256::hash("c".as_bytes()),
    Sha256::hash("d".as_bytes()),
];

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);

let indices_to_prove = vec![2,0];
let leaves_to_prove = vec![leaves[2], leaves[0]];

let proof = merkle_tree.proof(&indices_to_prove);
let root = merkle_tree.root().unwrap();

assert!(proof.verify(root, &indices_to_prove, &leaves_to_prove, leaves.len()));
// gives `assertion failed: proof.verify(root, &indices_to_prove, &leaves_to_prove, leaves.len())`

Verification works well when indices_to_prove is [0, 2], [1, 0], [1, 2] or even [1, 2, 0] but not when it is [0, 2].
[2, 1], [3, 1] or [3, 0] do not work either.

Is the problem related to the indices' not being sorted?
Examples I've seen from the documentation only use slices as the indices to prove, but no explicit limitation is stated.

I need indices_to_prove to be any subset of 0..leaves_len (in any order, but without duplicates). How can I get the code above to work?

EDIT: Judging by tests/merkle_proof_test.rs, the indices do not have to be sorted in MerkleProof::verify but they must be sorted in MerkleTree::proof. In this case, this should be explained in the documentation.

Hi, currently rs-merkle only supports serializing MerkleProof types.
In our use case we build a MerkleTree and want to store it on disk to generate proofs at a later time. Would you be interested in a PR adding a serialize/deserialize methods to MerkleTree?

only support sha256 and sha384,does not support sha3::keccak256