pub fn check_batched(
        &self,
        batch_val: &[Vec<u8>],
        proof: &BatchPath<D>,
    ) -> Result<(), MerkleTreeError> {
        if batch_val.len() != proof.indices.len() {
            return Err(MerkleTreeError::InvalidPath);
        }
        let mut ordered_indices: Vec<usize> = proof.indices.clone();
        ordered_indices.sort_unstable();

        if ordered_indices != proof.indices {
            return Err(MerkleTreeError::InvalidPath);
        }

        let nr_nodes = self.nr_leaves + self.nr_leaves.next_power_of_two() - 1;

        ordered_indices = ordered_indices
            .into_iter()
            .map(|i| i + self.nr_leaves.next_power_of_two() - 1)
            .collect();

        let mut idx = ordered_indices[0];
        // First we need to hash the leave values
        let mut leaves: Vec<Vec<u8>> = batch_val
            .iter()
            .map(|val| D::digest(val).to_vec())
            .collect();

        let mut values = proof.values.clone();

        while idx > 0 {
            let mut new_hashes = Vec::with_capacity(ordered_indices.len());
            let mut new_indices = Vec::with_capacity(ordered_indices.len());
            let mut i = 0;
            idx = parent(idx);
            while i < ordered_indices.len() {
                new_indices.push(parent(ordered_indices[i]));
                if ordered_indices[i] & 1 == 0 {
                    new_hashes.push(
                        D::new()
                            .chain(&values.get(0).ok_or(MerkleTreeError::InvalidPath)?)
                            .chain(&leaves[i])
                            .finalize()
                            .to_vec(),
                    );

                    values.remove(0);
                } else {
                    let sibling = sibling(ordered_indices[i]);
                    if i < ordered_indices.len() - 1 && ordered_indices[i + 1] == sibling {
                        new_hashes.push(
                            D::new()
                                .chain(&leaves[i])
                                .chain(&leaves[i + 1])
                                .finalize()
                                .to_vec(),
                        );
                        i += 1;
                    } else if sibling < nr_nodes {
                        new_hashes.push(
                            D::new()
                                .chain(&leaves[i])
                                .chain(&values.get(0).ok_or(MerkleTreeError::InvalidPath)?)
                                .finalize()
                                .to_vec(),
                        );
                        values.remove(0);
                    } else {
                        new_hashes.push(
                            D::new()
                                .chain(&leaves[i])
                                .chain(&D::digest(&[0u8]))
                                .finalize()
                                .to_vec(),
                        );
                    }
                }
                i += 1;
            }
            leaves = new_hashes.clone();
            ordered_indices = new_indices.clone();
        }

        if leaves.len() == 1 && leaves[0] == self.value {
            return Ok(());
        }

        Err(MerkleTreeError::InvalidPath)
    }
/// Check a proof of a batched opening. The indices must be ordered.
///
/// # Error
/// Returns an error if the proof is invalid.
///
/// # Example
/// ```
/// # use rand_core::{OsRng, RngCore};
/// # use atms::merkle_tree::MerkleTree;
/// # use blake2::Blake2b;
/// # fn main() {
/// let mut rng = OsRng::default();
/// // We generate the keys.
/// let mut keys = Vec::with_capacity(32);
/// for _ in 0..32 {
///     let mut leaf = [0u8; 32];
///     rng.fill_bytes(&mut leaf);
///     keys.push(leaf.to_vec());
/// }
/// // Compute the Merkle tree of the keys.
/// let mt = MerkleTree::<Blake2b>::create(&keys);
/// // Compute the path of keys in position [1, 3, 7, 11].
/// let indices = vec![1, 3, 7, 11];
/// let values = indices.iter().map(|i| keys[*i].clone()).collect::<Vec<_>>();
/// let path = mt.get_batched_path(indices);
/// // Verify the proof of membership with respect to the merkle commitment.
/// assert!(mt.to_commitment().check_batched(&values, &path).is_ok());
///
/// # }
Check a proof of a batched opening. The indices must be ordered.
Check a proof of a batched opening . The indices must be ordered .
pub fn check_batched(
        &self,
        batch_val: &[Vec<u8>],
        proof: &BatchPath<D>,
    ) -> Result<(), MerkleTreeError> {
        if batch_val.len() != proof.indices.len() {
            return Err(MerkleTreeError::InvalidPath);
        }
        let mut ordered_indices: Vec<usize> = proof.indices.clone();
        ordered_indices.sort_unstable();
        if ordered_indices != proof.indices {
            return Err(MerkleTreeError::InvalidPath);
        }
        let nr_nodes = self.nr_leaves + self.nr_leaves.next_power_of_two() - 1;
        ordered_indices = ordered_indices
            .into_iter()
            .map(|i| i + self.nr_leaves.next_power_of_two() - 1)
            .collect();
        let mut idx = ordered_indices[0];
        // First we need to hash the leave values
        let mut leaves: Vec<Vec<u8>> = batch_val
            .iter()
            .map(|val| D::digest(val).to_vec())
            .collect();
        let mut values = proof.values.clone();
        while idx > 0 {
            let mut new_hashes = Vec::with_capacity(ordered_indices.len());
            let mut new_indices = Vec::with_capacity(ordered_indices.len());
            let mut i = 0;
            idx = parent(idx);
            while i < ordered_indices.len() {
                new_indices.push(parent(ordered_indices[i]));
                if ordered_indices[i] & 1 == 0 {
                    new_hashes.push(
                        D::new()
                            .chain(&values.get(0).ok_or(MerkleTreeError::InvalidPath)?)
                            .chain(&leaves[i])
                            .finalize()
                            .to_vec(),
                    );
                    values.remove(0);
                } else {
                    let sibling = sibling(ordered_indices[i]);
                    if i < ordered_indices.len() - 1 && ordered_indices[i + 1] == sibling {
                        new_hashes.push(
                            D::new()
                                .chain(&leaves[i])
                                .chain(&leaves[i + 1])
                                .finalize()
                                .to_vec(),
                        );
                        i += 1;
                    } else if sibling < nr_nodes {
                        new_hashes.push(
                            D::new()
                                .chain(&leaves[i])
                                .chain(&values.get(0).ok_or(MerkleTreeError::InvalidPath)?)
                                .finalize()
                                .to_vec(),
                        );
                        values.remove(0);
                    } else {
                        new_hashes.push(
                            D::new()
                                .chain(&leaves[i])
                                .chain(&D::digest(&[0u8]))
                                .finalize()
                                .to_vec(),
                        );
                    }
                }
                i += 1;
            }
            leaves = new_hashes.clone();
            ordered_indices = new_indices.clone();
        }
        if leaves.len() == 1 && leaves[0] == self.value {
            return Ok(());
        }
        Err(MerkleTreeError::InvalidPath)
    }
pub fn check_batched ( & self , batch_val : & [ Vec < u8 > ] , proof : & BatchPath < D > , ) -> Result < ( ) , MerkleTreeError > { if batch_val . len ( ) != proof . indices . len ( ) { return Err ( MerkleTreeError :: InvalidPath ) ; } let mut ordered_indices : Vec < usize > = proof . indices . clone ( ) ; ordered_indices . sort_unstable ( ) ; if ordered_indices != proof . indices { return Err ( MerkleTreeError :: InvalidPath ) ; } let nr_nodes = self . nr_leaves + self . nr_leaves . next_power_of_two ( ) - 1 ; ordered_indices = ordered_indices . into_iter ( ) . map ( | i | i + self . nr_leaves . next_power_of_two ( ) - 1 ) . collect ( ) ; let mut idx = ordered_indices [ 0 ] ; // First we need to hash the leave values let mut leaves : Vec < Vec < u8 > > = batch_val . iter ( ) . map ( | val | D :: digest ( val ) . to_vec ( ) ) . collect ( ) ; let mut values = proof . values . clone ( ) ; while idx > 0 { let mut new_hashes = Vec :: with_capacity ( ordered_indices . len ( ) ) ; let mut new_indices = Vec :: with_capacity ( ordered_indices . len ( ) ) ; let mut i = 0 ; idx = parent ( idx ) ; while i < ordered_indices . len ( ) { new_indices . push ( parent ( ordered_indices [ i ] ) ) ; if ordered_indices [ i ] & 1 == 0 { new_hashes . push ( D :: new ( ) . chain ( & values . get ( 0 ) . ok_or ( MerkleTreeError :: InvalidPath ) ? ) . chain ( & leaves [ i ] ) . finalize ( ) . to_vec ( ) , ) ; values . remove ( 0 ) ; } else { let sibling = sibling ( ordered_indices [ i ] ) ; if i < ordered_indices . len ( ) - 1 && ordered_indices [ i + 1 ] == sibling { new_hashes . push ( D :: new ( ) . chain ( & leaves [ i ] ) . chain ( & leaves [ i + 1 ] ) . finalize ( ) . to_vec ( ) , ) ; i += 1 ; } else if sibling < nr_nodes { new_hashes . push ( D :: new ( ) . chain ( & leaves [ i ] ) . chain ( & values . get ( 0 ) . ok_or ( MerkleTreeError :: InvalidPath ) ? ) . finalize ( ) . to_vec ( ) , ) ; values . remove ( 0 ) ; } else { new_hashes . push ( D :: new ( ) . chain ( & leaves [ i ] ) . chain ( & D :: digest ( & [ 0u8 ] ) ) . finalize ( ) . to_vec ( ) , ) ; } } i += 1 ; } leaves = new_hashes . clone ( ) ; ordered_indices = new_indices . clone ( ) ; } if leaves . len ( ) == 1 && leaves [ 0 ] == self . value { return Ok ( ( ) ) ; } Err ( MerkleTreeError :: InvalidPath ) }
Check a proof of a batched opening.
Check a proof of a batched opening .
&self
batch_val
&[Vec<u8>]
proof
&BatchPath<D>
error
Returns an error if the proof is invalid.
Returns an error if the proof is invalid .
example
None
use rand_core::{osrng, rngcore};
None
use atms::merkle_tree::merkletree;
None
use blake2::blake2b;
None
fn main() {
let mut rng = OsRng::default();
We generate the keys.
let mut keys = Vec::with_capacity(32);
for _ in 0..32 {
let mut leaf = [0u8; 32];
rng.fill_bytes(&mut leaf);
keys.push(leaf.to_vec());
}
Compute the Merkle tree of the keys.
let mt = MerkleTree::::create(&keys);
Compute the path of keys in position [1, 3, 7, 11].
let indices = vec![1, 3, 7, 11];
let values = indices.iter().map(|i| keys[*i].clone()).collect::>();
let path = mt.get_batched_path(indices);
Verify the proof of membership with respect to the merkle commitment.
assert!(mt.to_commitment().check_batched(&values, &path).is_ok()).
let mut rng = OsRng :: default () ; We generate the keys . let mut keys = Vec :: with_capacity ( 32 ) ; for _ in 0 .. 32 { let mut leaf = [ 0u8 ; 32 ] ; rng . fill_bytes ( &mut leaf ) ; keys . push ( leaf . to_vec () ) ; } Compute the Merkle tree of the keys . let mt = MerkleTree :::: create ( &keys ) ; Compute the path of keys in position [ 1 3 7 11 ] . let indices = vec! [ 1 3 7 11 ] ; let values = indices . iter () . map ( |i| keys [ * i ] . clone () ) . collect :: > () ; let path = mt . get_batched_path ( indices ) ; Verify the proof of membership with respect to the merkle commitment . assert! ( mt . to_commitment () . check_batched ( &values &path ) . is_ok () ) .
}
None