diem_types/proof/
definition.rs

1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4// Copyright 2021 Conflux Foundation. All rights reserved.
5// Conflux is free software and distributed under GNU General Public License.
6// See http://www.gnu.org/licenses/
7
8//! This module has definition of various proofs.
9
10use super::{
11    accumulator::InMemoryAccumulator, position::Position,
12    verify_transaction_info, MerkleTreeInternalNode, SparseMerkleInternalNode,
13    SparseMerkleLeafNode,
14};
15use crate::{
16    ledger_info::LedgerInfo,
17    transaction::{TransactionInfo, Version},
18};
19use anyhow::{bail, ensure, format_err, Result};
20#[cfg(any(test, feature = "fuzzing"))]
21use diem_crypto::hash::TestOnlyHasher;
22use diem_crypto::{
23    hash::{
24        CryptoHash, CryptoHasher, EventAccumulatorHasher,
25        TransactionAccumulatorHasher, SPARSE_MERKLE_PLACEHOLDER_HASH,
26    },
27    HashValue,
28};
29#[cfg(any(test, feature = "fuzzing"))]
30use proptest_derive::Arbitrary;
31use serde::{Deserialize, Serialize};
32use std::marker::PhantomData;
33
34/// A proof that can be used authenticate an element in an accumulator given
35/// trusted root hash. For example, both `LedgerInfoToTransactionInfoProof` and
36/// `TransactionInfoToEventProof` can be constructed on top of this structure.
37#[derive(Clone, Serialize, Deserialize)]
38pub struct AccumulatorProof<H> {
39    /// All siblings in this proof, including the default ones. Siblings are
40    /// ordered from the bottom level to the root level.
41    siblings: Vec<HashValue>,
42
43    phantom: PhantomData<H>,
44}
45
46/// Because leaves can only take half the space in the tree, any numbering of
47/// the tree leaves must not take the full width of the total space.  Thus, for
48/// a 64-bit ordering, our maximumm proof depth is limited to 63.
49pub type LeafCount = u64;
50pub const MAX_ACCUMULATOR_PROOF_DEPTH: usize = 63;
51pub const MAX_ACCUMULATOR_LEAVES: LeafCount = 1 << MAX_ACCUMULATOR_PROOF_DEPTH;
52
53impl<H> AccumulatorProof<H>
54where H: CryptoHasher
55{
56    /// Constructs a new `AccumulatorProof` using a list of siblings.
57    pub fn new(siblings: Vec<HashValue>) -> Self {
58        AccumulatorProof {
59            siblings,
60            phantom: PhantomData,
61        }
62    }
63
64    /// Returns the list of siblings in this proof.
65    pub fn siblings(&self) -> &[HashValue] { &self.siblings }
66
67    /// Verifies an element whose hash is `element_hash` and version is
68    /// `element_version` exists in the accumulator whose root hash is
69    /// `expected_root_hash` using the provided proof.
70    pub fn verify(
71        &self, expected_root_hash: HashValue, element_hash: HashValue,
72        element_index: u64,
73    ) -> Result<()> {
74        ensure!(
75            self.siblings.len() <= MAX_ACCUMULATOR_PROOF_DEPTH,
76            "Accumulator proof has more than {} ({}) siblings.",
77            MAX_ACCUMULATOR_PROOF_DEPTH,
78            self.siblings.len()
79        );
80
81        let actual_root_hash = self
82            .siblings
83            .iter()
84            .fold(
85                (element_hash, element_index),
86                // `index` denotes the index of the ancestor of the element at
87                // the current level.
88                |(hash, index), sibling_hash| {
89                    (
90                        if index % 2 == 0 {
91                            // the current node is a left child.
92                            MerkleTreeInternalNode::<H>::new(
93                                hash,
94                                *sibling_hash,
95                            )
96                            .hash()
97                        } else {
98                            // the current node is a right child.
99                            MerkleTreeInternalNode::<H>::new(
100                                *sibling_hash,
101                                hash,
102                            )
103                            .hash()
104                        },
105                        // The index of the parent at its level.
106                        index / 2,
107                    )
108                },
109            )
110            .0;
111        ensure!(
112            actual_root_hash == expected_root_hash,
113            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
114            actual_root_hash,
115            expected_root_hash
116        );
117
118        Ok(())
119    }
120}
121
122impl<H> std::fmt::Debug for AccumulatorProof<H> {
123    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
124        write!(f, "AccumulatorProof {{ siblings: {:?} }}", self.siblings)
125    }
126}
127
128impl<H> PartialEq for AccumulatorProof<H> {
129    fn eq(&self, other: &Self) -> bool { self.siblings == other.siblings }
130}
131
132impl<H> Eq for AccumulatorProof<H> {}
133
134pub type TransactionAccumulatorProof =
135    AccumulatorProof<TransactionAccumulatorHasher>;
136pub type EventAccumulatorProof = AccumulatorProof<EventAccumulatorHasher>;
137#[cfg(any(test, feature = "fuzzing"))]
138pub type TestAccumulatorProof = AccumulatorProof<TestOnlyHasher>;
139
140/// A proof that can be used to authenticate an element in a Sparse Merkle Tree
141/// given trusted root hash. For example, `TransactionInfoToAccountProof` can be
142/// constructed on top of this structure.
143#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
144pub struct SparseMerkleProof<V> {
145    /// This proof can be used to authenticate whether a given leaf exists in
146    /// the tree or not.
147    ///     - If this is `Some(leaf_node)`
148    ///         - If `leaf_node.key` equals requested key, this is an inclusion
149    ///           proof and `leaf_node.value_hash` equals the hash of the
150    ///           corresponding account blob.
151    ///         - Otherwise this is a non-inclusion proof. `leaf_node.key` is
152    ///           the only key that exists in the subtree and
153    ///           `leaf_node.value_hash` equals the hash of the corresponding
154    ///           account blob.
155    ///     - If this is `None`, this is also a non-inclusion proof which
156    ///       indicates the subtree is empty.
157    leaf: Option<SparseMerkleLeafNode>,
158
159    /// All siblings in this proof, including the default ones. Siblings are
160    /// ordered from the bottom level to the root level.
161    siblings: Vec<HashValue>,
162
163    phantom: PhantomData<V>,
164}
165
166impl<V> SparseMerkleProof<V>
167where V: CryptoHash
168{
169    /// Constructs a new `SparseMerkleProof` using leaf and a list of siblings.
170    pub fn new(
171        leaf: Option<SparseMerkleLeafNode>, siblings: Vec<HashValue>,
172    ) -> Self {
173        SparseMerkleProof {
174            leaf,
175            siblings,
176            phantom: PhantomData,
177        }
178    }
179
180    /// Returns the leaf node in this proof.
181    pub fn leaf(&self) -> Option<SparseMerkleLeafNode> { self.leaf }
182
183    /// Returns the list of siblings in this proof.
184    pub fn siblings(&self) -> &[HashValue] { &self.siblings }
185
186    /// If `element_value` is present, verifies an element whose key is
187    /// `element_key` and value is `element_value` exists in the Sparse
188    /// Merkle Tree using the provided proof. Otherwise verifies the proof
189    /// is a valid non-inclusion proof that shows this key doesn't exist in the
190    /// tree.
191    pub fn verify(
192        &self, expected_root_hash: HashValue, element_key: HashValue,
193        element_value: Option<&V>,
194    ) -> Result<()> {
195        ensure!(
196            self.siblings.len() <= HashValue::LENGTH_IN_BITS,
197            "Sparse Merkle Tree proof has more than {} ({}) siblings.",
198            HashValue::LENGTH_IN_BITS,
199            self.siblings.len(),
200        );
201
202        match (element_value, self.leaf) {
203            (Some(value), Some(leaf)) => {
204                // This is an inclusion proof, so the key and value hash
205                // provided in the proof should match
206                // element_key and element_value_hash. `siblings` should prove
207                // the route from the leaf node to the root.
208                ensure!(
209                    element_key == leaf.key,
210                    "Keys do not match. Key in proof: {:x}. Expected key: {:x}.",
211                    leaf.key,
212                    element_key
213                );
214                let hash = value.hash();
215                ensure!(
216                    hash == leaf.value_hash,
217                    "Value hashes do not match. Value hash in proof: {:x}. \
218                     Expected value hash: {:x}",
219                    leaf.value_hash,
220                    hash,
221                );
222            }
223            (Some(_value), None) => {
224                bail!("Expected inclusion proof. Found non-inclusion proof.")
225            }
226            (None, Some(leaf)) => {
227                // This is a non-inclusion proof. The proof intends to show that
228                // if a leaf node representing `element_key` is
229                // inserted, it will break a currently existing leaf
230                // node represented by `proof_key` into a branch. `siblings`
231                // should prove the route from that leaf node to
232                // the root.
233                ensure!(
234                    element_key != leaf.key,
235                    "Expected non-inclusion proof, but key exists in proof.",
236                );
237                ensure!(
238                    element_key.common_prefix_bits_len(leaf.key) >= self.siblings.len(),
239                    "Key would not have ended up in the subtree where the provided key in proof \
240                     is the only existing key, if it existed. So this is not a valid \
241                     non-inclusion proof.",
242                );
243            }
244            (None, None) => {
245                // This is a non-inclusion proof. The proof intends to show that
246                // if a leaf node representing `element_key` is
247                // inserted, it will show up at a currently empty
248                // position. `sibling` should prove the route from this empty
249                // position to the root.
250            }
251        }
252
253        let current_hash = self
254            .leaf
255            .map_or(*SPARSE_MERKLE_PLACEHOLDER_HASH, |leaf| leaf.hash());
256        let actual_root_hash = self
257            .siblings
258            .iter()
259            .zip(
260                element_key
261                    .iter_bits()
262                    .rev()
263                    .skip(HashValue::LENGTH_IN_BITS - self.siblings.len()),
264            )
265            .fold(current_hash, |hash, (sibling_hash, bit)| {
266                if bit {
267                    SparseMerkleInternalNode::new(*sibling_hash, hash).hash()
268                } else {
269                    SparseMerkleInternalNode::new(hash, *sibling_hash).hash()
270                }
271            });
272        ensure!(
273            actual_root_hash == expected_root_hash,
274            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
275            actual_root_hash,
276            expected_root_hash,
277        );
278
279        Ok(())
280    }
281}
282
283/// A proof that can be used to show that two Merkle accumulators are consistent
284/// -- the big one can be obtained by appending certain leaves to the small one.
285/// For example, at some point in time a client knows that the root hash of the
286/// ledger at version 10 is `old_root` (it could be a waypoint). If a server
287/// wants to prove that the new ledger at version `N` is derived from the
288/// old ledger the client knows, it can show the subtrees that represent all the
289/// new leaves. If the client can verify that it can indeed obtain the new root
290/// hash by appending these new leaves, it can be convinced that the two
291/// accumulators are consistent.
292#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
293pub struct AccumulatorConsistencyProof {
294    /// The subtrees representing the newly appended leaves.
295    subtrees: Vec<HashValue>,
296}
297
298impl AccumulatorConsistencyProof {
299    /// Constructs a new `AccumulatorConsistencyProof` using given `subtrees`.
300    pub fn new(subtrees: Vec<HashValue>) -> Self { Self { subtrees } }
301
302    /// Returns the subtrees.
303    pub fn subtrees(&self) -> &[HashValue] { &self.subtrees }
304}
305
306/// A proof that is similar to `AccumulatorProof`, but can be used to
307/// authenticate a range of leaves. For example, given the following
308/// accumulator:
309///
310/// ```text
311///                 root
312///                /     \
313///              /         \
314///            /             \
315///           o               o
316///         /   \           /   \
317///        /     \         /     \
318///       X       o       o       Y
319///      / \     / \     / \     / \
320///     o   o   a   b   c   Z   o   o
321/// ```
322///
323/// if the proof wants to show that `[a, b, c]` exists in the accumulator, it
324/// would need `X` on the left and `Y` and `Z` on the right.
325#[derive(Clone, Deserialize, Serialize)]
326pub struct AccumulatorRangeProof<H> {
327    /// The siblings on the left of the path from the first leaf to the root.
328    /// Siblings near the root are at the beginning of the vector.
329    left_siblings: Vec<HashValue>,
330
331    /// The sliblings on the right of the path from the last leaf to the root.
332    /// Siblings near the root are at the beginning of the vector.
333    right_siblings: Vec<HashValue>,
334
335    phantom: PhantomData<H>,
336}
337
338impl<H> AccumulatorRangeProof<H>
339where H: CryptoHasher
340{
341    /// Constructs a new `AccumulatorRangeProof` using `left_siblings` and
342    /// `right_siblings`.
343    pub fn new(
344        left_siblings: Vec<HashValue>, right_siblings: Vec<HashValue>,
345    ) -> Self {
346        Self {
347            left_siblings,
348            right_siblings,
349            phantom: PhantomData,
350        }
351    }
352
353    /// Constructs a new `AccumulatorRangeProof` for an empty list of leaves.
354    pub fn new_empty() -> Self { Self::new(vec![], vec![]) }
355
356    /// Get all the left siblngs.
357    pub fn left_siblings(&self) -> &Vec<HashValue> { &self.left_siblings }
358
359    /// Get all the right siblngs.
360    pub fn right_siblings(&self) -> &Vec<HashValue> { &self.right_siblings }
361
362    /// Verifies the proof is correct. The verifier needs to have
363    /// `expected_root_hash`, the index of the first leaf and all of the
364    /// leaves in possession.
365    pub fn verify(
366        &self, expected_root_hash: HashValue, first_leaf_index: Option<u64>,
367        leaf_hashes: &[HashValue],
368    ) -> Result<()> {
369        if first_leaf_index.is_none() {
370            ensure!(
371                leaf_hashes.is_empty(),
372                "first_leaf_index indicated empty list while leaf_hashes is not empty.",
373            );
374            ensure!(
375                self.left_siblings.is_empty() && self.right_siblings.is_empty(),
376                "No siblings are needed.",
377            );
378            return Ok(());
379        }
380
381        ensure!(
382            self.left_siblings.len() <= MAX_ACCUMULATOR_PROOF_DEPTH,
383            "Proof has more than {} ({}) left siblings.",
384            MAX_ACCUMULATOR_PROOF_DEPTH,
385            self.left_siblings.len(),
386        );
387        ensure!(
388            self.right_siblings.len() <= MAX_ACCUMULATOR_PROOF_DEPTH,
389            "Proof has more than {} ({}) right siblings.",
390            MAX_ACCUMULATOR_PROOF_DEPTH,
391            self.right_siblings.len(),
392        );
393        ensure!(
394            !leaf_hashes.is_empty(),
395            "leaf_hashes is empty while first_leaf_index indicated non-empty list.",
396        );
397
398        let mut left_sibling_iter = self.left_siblings.iter().peekable();
399        let mut right_sibling_iter = self.right_siblings.iter().peekable();
400
401        let mut first_pos = Position::from_leaf_index(
402            first_leaf_index.expect("first_leaf_index should not be None."),
403        );
404        let mut current_hashes = leaf_hashes.to_vec();
405        let mut parent_hashes = vec![];
406
407        // Keep reducing the list of hashes by combining all the children pairs,
408        // until there is only one hash left.
409        while current_hashes.len() > 1
410            || left_sibling_iter.peek().is_some()
411            || right_sibling_iter.peek().is_some()
412        {
413            let mut children_iter = current_hashes.iter();
414
415            // If the first position on the current level is a right child, it
416            // needs to be combined with a sibling on the left.
417            if first_pos.is_right_child() {
418                let left_hash = *left_sibling_iter.next().ok_or_else(|| {
419                    format_err!("First child is a right child, but missing sibling on the left.")
420                })?;
421                let right_hash =
422                    *children_iter.next().expect("The first leaf must exist.");
423                parent_hashes.push(
424                    MerkleTreeInternalNode::<H>::new(left_hash, right_hash)
425                        .hash(),
426                );
427            }
428
429            // Next we take two children at a time and compute their parents.
430            let mut children_iter = children_iter.as_slice().chunks_exact(2);
431            while let Some(chunk) = children_iter.next() {
432                let left_hash = chunk[0];
433                let right_hash = chunk[1];
434                parent_hashes.push(
435                    MerkleTreeInternalNode::<H>::new(left_hash, right_hash)
436                        .hash(),
437                );
438            }
439
440            // Similarly, if the last position is a left child, it needs to be
441            // combined with a sibling on the right.
442            let remainder = children_iter.remainder();
443            assert!(remainder.len() <= 1);
444            if !remainder.is_empty() {
445                let left_hash = remainder[0];
446                let right_hash = *right_sibling_iter.next().ok_or_else(|| {
447                    format_err!("Last child is a left child, but missing sibling on the right.")
448                })?;
449                parent_hashes.push(
450                    MerkleTreeInternalNode::<H>::new(left_hash, right_hash)
451                        .hash(),
452                );
453            }
454
455            first_pos = first_pos.parent();
456            current_hashes.clear();
457            std::mem::swap(&mut current_hashes, &mut parent_hashes);
458        }
459
460        ensure!(
461            current_hashes[0] == expected_root_hash,
462            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
463            current_hashes[0],
464            expected_root_hash,
465        );
466
467        Ok(())
468    }
469}
470
471impl<H> std::fmt::Debug for AccumulatorRangeProof<H> {
472    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
473        write!(
474            f,
475            "AccumulatorRangeProof {{ left_siblings: {:?}, right_siblings: {:?} }}",
476            self.left_siblings, self.right_siblings,
477        )
478    }
479}
480
481impl<H> PartialEq for AccumulatorRangeProof<H> {
482    fn eq(&self, other: &Self) -> bool {
483        self.left_siblings == other.left_siblings
484            && self.right_siblings == other.right_siblings
485    }
486}
487
488impl<H> Eq for AccumulatorRangeProof<H> {}
489
490pub type TransactionAccumulatorRangeProof =
491    AccumulatorRangeProof<TransactionAccumulatorHasher>;
492#[cfg(any(test, feature = "fuzzing"))]
493pub type TestAccumulatorRangeProof = AccumulatorRangeProof<TestOnlyHasher>;
494
495/// `TransactionInfo` and a `TransactionAccumulatorProof` connecting it to the
496/// ledger root.
497#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
498#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
499pub struct TransactionInfoWithProof {
500    /// The accumulator proof from ledger info root to leaf that authenticates
501    /// the hash of the `TransactionInfo` object.
502    ledger_info_to_transaction_info_proof: TransactionAccumulatorProof,
503
504    /// The `TransactionInfo` object at the leaf of the accumulator.
505    transaction_info: TransactionInfo,
506}
507
508impl TransactionInfoWithProof {
509    /// Constructs a new `TransactionWithProof` object using given
510    /// `ledger_info_to_transaction_info_proof`.
511    pub fn new(
512        ledger_info_to_transaction_info_proof: TransactionAccumulatorProof,
513        transaction_info: TransactionInfo,
514    ) -> Self {
515        Self {
516            ledger_info_to_transaction_info_proof,
517            transaction_info,
518        }
519    }
520
521    /// Returns the `ledger_info_to_transaction_info_proof` object in this
522    /// proof.
523    pub fn ledger_info_to_transaction_info_proof(
524        &self,
525    ) -> &TransactionAccumulatorProof {
526        &self.ledger_info_to_transaction_info_proof
527    }
528
529    /// Returns the `transaction_info` object in this proof.
530    pub fn transaction_info(&self) -> &TransactionInfo {
531        &self.transaction_info
532    }
533
534    /// Verifies that the `TransactionInfo` exists in the ledger represented by
535    /// the `LedgerInfo` at specified version.
536    pub fn verify(
537        &self, ledger_info: &LedgerInfo, transaction_version: Version,
538    ) -> Result<()> {
539        verify_transaction_info(
540            ledger_info,
541            transaction_version,
542            &self.transaction_info,
543            &self.ledger_info_to_transaction_info_proof,
544        )?;
545        Ok(())
546    }
547}
548
549/// The complete proof used to authenticate a list of consecutive transactions.
550#[derive(Clone, Debug, Eq, PartialEq, Deserialize, Serialize)]
551#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
552pub struct TransactionListProof {
553    /// The accumulator range proof from ledger info root to leaves that
554    /// authenticates the hashes of all `TransactionInfo` objects.
555    ledger_info_to_transaction_infos_proof: TransactionAccumulatorRangeProof,
556
557    /// The `TransactionInfo` objects that correspond to all the transactions.
558    transaction_infos: Vec<TransactionInfo>,
559}
560
561impl TransactionListProof {
562    /// Constructs a new `TransactionListProof` using
563    /// `ledger_info_to_transaction_info_proof` and `transaction_infos`.
564    pub fn new(
565        ledger_info_to_transaction_infos_proof: TransactionAccumulatorRangeProof,
566        transaction_infos: Vec<TransactionInfo>,
567    ) -> Self {
568        Self {
569            ledger_info_to_transaction_infos_proof,
570            transaction_infos,
571        }
572    }
573
574    /// Constructs a proof for an empty list of transactions.
575    pub fn new_empty() -> Self {
576        Self::new(AccumulatorRangeProof::new_empty(), vec![])
577    }
578
579    /// Returns the list of `TransactionInfo` objects.
580    pub fn transaction_infos(&self) -> &[TransactionInfo] {
581        &self.transaction_infos
582    }
583
584    pub fn left_siblings(&self) -> &Vec<HashValue> {
585        self.ledger_info_to_transaction_infos_proof.left_siblings()
586    }
587
588    pub fn unpack(
589        self,
590    ) -> (TransactionAccumulatorRangeProof, Vec<TransactionInfo>) {
591        (
592            self.ledger_info_to_transaction_infos_proof,
593            self.transaction_infos,
594        )
595    }
596
597    /// Verifies the list of transactions are correct using the proof. The
598    /// verifier needs to have the ledger info and the version of the first
599    /// transaction in possession.
600    pub fn verify(
601        &self, ledger_info: &LedgerInfo,
602        first_transaction_version: Option<Version>,
603        transaction_hashes: &[HashValue],
604    ) -> Result<()> {
605        ensure!(
606            self.transaction_infos.len() == transaction_hashes.len(),
607            "The number of TransactionInfo objects ({}) does not match the number of \
608             transactions ({}).",
609            self.transaction_infos.len(),
610            transaction_hashes.len(),
611        );
612
613        itertools::zip_eq(transaction_hashes, &self.transaction_infos)
614            .map(|(txn_hash, txn_info)| {
615                ensure!(
616                    *txn_hash == txn_info.transaction_hash(),
617                    "The hash of transaction does not match the transaction info in proof. \
618                     Transaction hash: {:x}. Transaction hash in txn_info: {:x}.",
619                    txn_hash,
620                    txn_info.transaction_hash(),
621                );
622                Ok(())
623            })
624            .collect::<Result<Vec<_>>>()?;
625
626        let txn_info_hashes: Vec<_> = self
627            .transaction_infos
628            .iter()
629            .map(CryptoHash::hash)
630            .collect();
631        self.ledger_info_to_transaction_infos_proof.verify(
632            ledger_info.transaction_accumulator_hash(),
633            first_transaction_version,
634            &txn_info_hashes,
635        )?;
636        Ok(())
637    }
638}
639
640/// A proof that first verifies that establishes correct computation of the root
641/// and then returns the new tree to acquire a new root and version.
642#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
643pub struct AccumulatorExtensionProof<H> {
644    /// Represents the roots of all the full subtrees from left to right in the
645    /// original accumulator.
646    frozen_subtree_roots: Vec<HashValue>,
647    /// The total number of leaves in original accumulator.
648    num_leaves: LeafCount,
649    /// The values representing the newly appended leaves.
650    leaves: Vec<HashValue>,
651
652    hasher: PhantomData<H>,
653}
654
655impl<H: CryptoHasher> AccumulatorExtensionProof<H> {
656    pub fn new(
657        frozen_subtree_roots: Vec<HashValue>, num_leaves: LeafCount,
658        leaves: Vec<HashValue>,
659    ) -> Self {
660        Self {
661            frozen_subtree_roots,
662            num_leaves,
663            leaves,
664            hasher: PhantomData,
665        }
666    }
667
668    pub fn verify(
669        &self, _original_root: HashValue,
670    ) -> anyhow::Result<InMemoryAccumulator<H>> {
671        let original_tree = InMemoryAccumulator::<H>::new(
672            self.frozen_subtree_roots.clone(),
673            self.num_leaves,
674        )?;
675        // ensure!(
676        //     original_tree.root_hash() == original_root,
677        //     "Root hashes do not match. Actual root hash: {:x}. Expected root
678        // hash: {:x}.",     original_tree.root_hash(),
679        //     original_root
680        // );
681
682        Ok(original_tree.append(self.leaves.as_slice()))
683    }
684}
diem_types/proof/definition.rs

diem_types/proof/
definition.rs
