Multi-proofs is supported on the crate?

[wdcs-pc]

rs-merkle/README.md

Lines 7 to 11 in ae7bc91

	`rs-merkle` is the most advanced Merkle tree library for Rust. Basic features
	include building a Merkle tree, creation, and verification of Merkle proofs for
	single and several elements, i.e. multi-proofs. Advanced features include making
	transactional changes to the tree and rolling back to any previously committed
	tree state, similarly to Git.

As per the readme description I am unable to find the interfaces for multiproof !
Is it already there? or there will be on new versions?

[E-Mans-Application]

Hi, type MerkleProof already has support for multi-proofs:

MerkleTree::proof takes a (sorted) slice of leaf indices, and MerkleProof::verify takes a slice of leaf indices and hashes.

[wdcs-pc]

@E-Mans-Application
I have looked into this.
I think the generated proofs can only be verified with the current crate only.
Like what if I want to verify the multiproof in a different location.
Where I don't want to send the indexes and total size etc.

[antouhou]

@E-Mans-Application I have looked into this. I think the generated proofs can only be verified with the current crate only. Like what if I want to verify the multiproof in a different location. Where I don't want to send the indexes and total size etc.

Hi! What do you mean exactly by "I don't want to send indexes"? In order to verify Merkle proof, you need to know indexes, otherwise you wouldn't know where the hashes you're trying to verify should fit into the proof

[wdcs-pc]

@E-Mans-Application I have looked into this. I think the generated proofs can only be verified with the current crate only. Like what if I want to verify the multiproof in a different location. Where I don't want to send the indexes and total size etc.

Hi! What do you mean exactly by "I don't want to send indexes"? In order to verify Merkle proof, you need to know indexes, otherwise you wouldn't know where the hashes you're trying to verify should fit into the proof

@antouhou
https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/MerkleProof.sol#L351-L398
I want to verify it on evm chain with the right-to-left approach.
I think for that I can utilise the partial tree to create the proofs with flag with some custom implementation.

[antouhou]

@E-Mans-Application I have looked into this. I think the generated proofs can only be verified with the current crate only. Like what if I want to verify the multiproof in a different location. Where I don't want to send the indexes and total size etc.

Hi! What do you mean exactly by "I don't want to send indexes"? In order to verify Merkle proof, you need to know indexes, otherwise you wouldn't know where the hashes you're trying to verify should fit into the proof

@antouhou https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/MerkleProof.sol#L351-L398 I want to verify it on evm chain with the right-to-left approach. I think for that I can utilise the partial tree to create the proofs with flag with some custom implementation.

In the implementation above you still have to pass indexes, they're just in a form of bitflags. Converting indexes to bitflags and back is pretty staightforward, I just never needed this code for my usecase, so I never wrote the conversion. Here's a simple snippet on how to do that:

fn indices_to_bitflags_vec(indices: &[usize], num_leaves: usize) -> Vec<u8> {
    let num_bytes = (num_leaves + 7) / 8; // Calculate the number of bytes needed
    let mut bitflags = vec![0u8; num_bytes];

    for &index in indices {
        if index < num_leaves {
            let byte_index = index / 8;
            let bit_index = index % 8;
            bitflags[byte_index] |= 1 << bit_index;
        }
    }
    bitflags
}

Note, it should work, but I haven't really tested it