pub fn verify(
        mut self,
        hasher: &dyn HashTree,
        tree_depth: u8,
        prev_output: Option<BatchOutput>,
        entries: &[TreeEntry],
        read_keys: &[H256],
    ) -> anyhow::Result<MerkleTreeView> {
        let Some(prev_output) = prev_output else {
            return self.verify_for_empty_tree(hasher, tree_depth, entries, read_keys);
        };

        anyhow::ensure!(
            self.operations.len() == entries.len(),
            "Unexpected operations length"
        );
        anyhow::ensure!(
            self.read_operations.len() == read_keys.len(),
            "Unexpected read operations length"
        );
        if let Some((max_idx, _)) = self.sorted_leaves.iter().next_back() {
            anyhow::ensure!(*max_idx < prev_output.leaf_count, "Index is too large");
        }

        if self.operations.is_empty() && self.read_operations.is_empty() {
            // Degenerate case: there are no operations to be proven.
            return Ok(MerkleTreeView {
                root_hash: prev_output.root_hash,
                read_entries: HashMap::new(),
            });
        }

        let mut read_entries = HashMap::with_capacity(read_keys.len());
        for (&operation, read_key) in self.read_operations.iter().zip(read_keys) {
            self.verify_operation(&prev_output, operation, read_key)
                .with_context(|| format!("reading {read_key:?}"))?;

            read_entries.insert(
                *read_key,
                match operation {
                    TreeOperation::Hit { index } => {
                        // We've verified the existence of the proven leaf above.
                        Some(self.sorted_leaves[&index].value)
                    }
                    TreeOperation::Miss { .. } => None,
                },
            );
        }

        let mut index_by_key: BTreeMap<_, _> = self
            .sorted_leaves
            .iter()
            .map(|(idx, leaf)| (leaf.key, *idx))
            .collect();

        let mut next_tree_index = prev_output.leaf_count;
        for (&operation, entry) in self.operations.iter().zip(entries) {
            self.verify_operation(&prev_output, operation, &entry.key)
                .with_context(|| format!("update / insert {entry:?}"))?;

            if matches!(operation, TreeOperation::Miss { .. }) {
                index_by_key.insert(entry.key, next_tree_index);
                next_tree_index += 1;
            }
        }

        let restored_prev_hash = Self::zip_leaves(
            hasher,
            tree_depth,
            prev_output.leaf_count,
            self.sorted_leaves.iter().map(|(idx, leaf)| (*idx, leaf)),
            self.hashes.iter(),
        )?;
        anyhow::ensure!(
            restored_prev_hash == prev_output.root_hash,
            "Mismatch for previous root hash: prev_output={prev_output:?}, restored={restored_prev_hash:?}"
        );

        if self.operations.is_empty() {
            // No updates or inserts, so we can exit early
            return Ok(MerkleTreeView {
                root_hash: restored_prev_hash,
                read_entries,
            });
        }

        // Expand `leaves` with the newly inserted leaves and update the existing leaves.
        for (&operation, entry) in self.operations.iter().zip(entries) {
            match operation {
                TreeOperation::Hit { index } => {
                    // We've checked the key correspondence already.
                    self.sorted_leaves.get_mut(&index).unwrap().value = entry.value;
                }
                TreeOperation::Miss { .. } => {
                    let mut it = index_by_key.range(entry.key..);
                    let (_, &this_index) = it.next().unwrap();
                    // `unwrap()`s below are safe: at least the pre-existing next index is greater, and the pre-existing prev index is lesser.
                    let (_, &next_index) = it.next().unwrap();
                    let (_, &prev_index) = index_by_key.range(..entry.key).next_back().unwrap();

                    self.sorted_leaves.insert(
                        this_index,
                        Leaf {
                            key: entry.key,
                            value: entry.value,
                            next_index,
                        },
                    );

                    // Prev / next leaves may be missing if they are inserted in the batch as well;
                    // in this case, prev / next index will be set correctly once the leaf is created.
                    if let Some(prev_leaf) = self.sorted_leaves.get_mut(&prev_index) {
                        prev_leaf.next_index = this_index;
                    }
                }
            }
        }

        let new_root_hash = Self::zip_leaves(
            hasher,
            tree_depth,
            next_tree_index,
            self.sorted_leaves.iter().map(|(idx, leaf)| (*idx, leaf)),
            self.hashes.iter(),
        )?;
        Ok(MerkleTreeView {
            root_hash: new_root_hash,
            read_entries,
        })
    }
Returns the restored view of the tree on success.
core/lib/zk_os_merkle_tree/src/hasher/proofs.rs