Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proof verification unexpectedly fails for some combinations of indices #37

Open
E-Mans-Application opened this issue Jun 17, 2024 · 0 comments

Comments

@E-Mans-Application
Copy link

E-Mans-Application commented Jun 17, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant