diem_types/proof/
definition.rs

1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! This module has definition of various proofs.
5
6use super::{
7    accumulator::InMemoryAccumulator, position::Position, verify_transaction_info,
8    MerkleTreeInternalNode, SparseMerkleInternalNode, SparseMerkleLeafNode,
9};
10use crate::{
11    account_state_blob::AccountStateBlob,
12    ledger_info::LedgerInfo,
13    transaction::{TransactionInfoTrait, Version},
14};
15use anyhow::{bail, ensure, format_err, Context, Result};
16#[cfg(any(test, feature = "fuzzing"))]
17use diem_crypto::hash::TestOnlyHasher;
18use diem_crypto::{
19    hash::{
20        CryptoHash, CryptoHasher, EventAccumulatorHasher, TransactionAccumulatorHasher,
21        SPARSE_MERKLE_PLACEHOLDER_HASH,
22    },
23    HashValue,
24};
25#[cfg(any(test, feature = "fuzzing"))]
26use proptest_derive::Arbitrary;
27use serde::{Deserialize, Serialize};
28use std::marker::PhantomData;
29
30/// A proof that can be used authenticate an element in an accumulator given trusted root hash. For
31/// example, both `LedgerInfoToTransactionInfoProof` and `TransactionInfoToEventProof` can be
32/// constructed on top of this structure.
33#[derive(Clone, Serialize, Deserialize)]
34pub struct AccumulatorProof<H> {
35    /// All siblings in this proof, including the default ones. Siblings are ordered from the bottom
36    /// level to the root level.
37    siblings: Vec<HashValue>,
38
39    phantom: PhantomData<H>,
40}
41
42/// Because leaves can only take half the space in the tree, any numbering of the tree leaves must
43/// not take the full width of the total space.  Thus, for a 64-bit ordering, our maximumm proof
44/// depth is limited to 63.
45pub type LeafCount = u64;
46pub const MAX_ACCUMULATOR_PROOF_DEPTH: usize = 63;
47pub const MAX_ACCUMULATOR_LEAVES: LeafCount = 1 << MAX_ACCUMULATOR_PROOF_DEPTH;
48
49impl<H> AccumulatorProof<H>
50where
51    H: CryptoHasher,
52{
53    /// Constructs a new `AccumulatorProof` using a list of siblings.
54    pub fn new(siblings: Vec<HashValue>) -> Self {
55        AccumulatorProof {
56            siblings,
57            phantom: PhantomData,
58        }
59    }
60
61    /// Returns the list of siblings in this proof.
62    pub fn siblings(&self) -> &[HashValue] {
63        &self.siblings
64    }
65
66    /// Verifies an element whose hash is `element_hash` and version is `element_version` exists in
67    /// the accumulator whose root hash is `expected_root_hash` using the provided proof.
68    pub fn verify(
69        &self,
70        expected_root_hash: HashValue,
71        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 the current level.
87                |(hash, index), sibling_hash| {
88                    (
89                        if index % 2 == 0 {
90                            // the current node is a left child.
91                            MerkleTreeInternalNode::<H>::new(hash, *sibling_hash).hash()
92                        } else {
93                            // the current node is a right child.
94                            MerkleTreeInternalNode::<H>::new(*sibling_hash, hash).hash()
95                        },
96                        // The index of the parent at its level.
97                        index / 2,
98                    )
99                },
100            )
101            .0;
102        ensure!(
103            actual_root_hash == expected_root_hash,
104            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
105            actual_root_hash,
106            expected_root_hash
107        );
108
109        Ok(())
110    }
111}
112
113impl<H> std::fmt::Debug for AccumulatorProof<H> {
114    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
115        write!(f, "AccumulatorProof {{ siblings: {:?} }}", self.siblings)
116    }
117}
118
119impl<H> PartialEq for AccumulatorProof<H> {
120    fn eq(&self, other: &Self) -> bool {
121        self.siblings == other.siblings
122    }
123}
124
125impl<H> Eq for AccumulatorProof<H> {}
126
127pub type TransactionAccumulatorProof = AccumulatorProof<TransactionAccumulatorHasher>;
128pub type EventAccumulatorProof = AccumulatorProof<EventAccumulatorHasher>;
129#[cfg(any(test, feature = "fuzzing"))]
130pub type TestAccumulatorProof = AccumulatorProof<TestOnlyHasher>;
131
132/// A proof that can be used to authenticate an element in a Sparse Merkle Tree given trusted root
133/// hash. For example, `TransactionInfoToAccountProof` can be constructed on top of this structure.
134#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
135pub struct SparseMerkleProof<V> {
136    /// This proof can be used to authenticate whether a given leaf exists in the tree or not.
137    ///     - If this is `Some(leaf_node)`
138    ///         - If `leaf_node.key` equals requested key, this is an inclusion proof and
139    ///           `leaf_node.value_hash` equals the hash of the corresponding account blob.
140    ///         - Otherwise this is a non-inclusion proof. `leaf_node.key` is the only key
141    ///           that exists in the subtree and `leaf_node.value_hash` equals the hash of the
142    ///           corresponding account blob.
143    ///     - If this is `None`, this is also a non-inclusion proof which indicates the subtree is
144    ///       empty.
145    leaf: Option<SparseMerkleLeafNode>,
146
147    /// All siblings in this proof, including the default ones. Siblings are ordered from the bottom
148    /// level to the root level.
149    siblings: Vec<HashValue>,
150
151    phantom: PhantomData<V>,
152}
153
154impl<V> SparseMerkleProof<V>
155where
156    V: CryptoHash,
157{
158    /// Constructs a new `SparseMerkleProof` using leaf and a list of siblings.
159    pub fn new(leaf: Option<SparseMerkleLeafNode>, siblings: Vec<HashValue>) -> Self {
160        SparseMerkleProof {
161            leaf,
162            siblings,
163            phantom: PhantomData,
164        }
165    }
166
167    /// Returns the leaf node in this proof.
168    pub fn leaf(&self) -> Option<SparseMerkleLeafNode> {
169        self.leaf
170    }
171
172    /// Returns the list of siblings in this proof.
173    pub fn siblings(&self) -> &[HashValue] {
174        &self.siblings
175    }
176
177    /// If `element_value` is present, verifies an element whose key is `element_key` and value is
178    /// `element_value` exists in the Sparse Merkle Tree using the provided proof. Otherwise
179    /// verifies the proof is a valid non-inclusion proof that shows this key doesn't exist in the
180    /// tree.
181    pub fn verify(
182        &self,
183        expected_root_hash: HashValue,
184        element_key: HashValue,
185        element_value: Option<&V>,
186    ) -> Result<()> {
187        ensure!(
188            self.siblings.len() <= HashValue::LENGTH_IN_BITS,
189            "Sparse Merkle Tree proof has more than {} ({}) siblings.",
190            HashValue::LENGTH_IN_BITS,
191            self.siblings.len(),
192        );
193
194        match (element_value, self.leaf) {
195            (Some(value), Some(leaf)) => {
196                // This is an inclusion proof, so the key and value hash provided in the proof
197                // should match element_key and element_value_hash. `siblings` should prove the
198                // route from the leaf node to the root.
199                ensure!(
200                    element_key == leaf.key,
201                    "Keys do not match. Key in proof: {:x}. Expected key: {:x}.",
202                    leaf.key,
203                    element_key
204                );
205                let hash = value.hash();
206                ensure!(
207                    hash == leaf.value_hash,
208                    "Value hashes do not match. Value hash in proof: {:x}. \
209                     Expected value hash: {:x}",
210                    leaf.value_hash,
211                    hash,
212                );
213            }
214            (Some(_value), None) => bail!("Expected inclusion proof. Found non-inclusion proof."),
215            (None, Some(leaf)) => {
216                // This is a non-inclusion proof. The proof intends to show that if a leaf node
217                // representing `element_key` is inserted, it will break a currently existing leaf
218                // node represented by `proof_key` into a branch. `siblings` should prove the
219                // route from that leaf node to the root.
220                ensure!(
221                    element_key != leaf.key,
222                    "Expected non-inclusion proof, but key exists in proof.",
223                );
224                ensure!(
225                    element_key.common_prefix_bits_len(leaf.key) >= self.siblings.len(),
226                    "Key would not have ended up in the subtree where the provided key in proof \
227                     is the only existing key, if it existed. So this is not a valid \
228                     non-inclusion proof.",
229                );
230            }
231            (None, None) => {
232                // This is a non-inclusion proof. The proof intends to show that if a leaf node
233                // representing `element_key` is inserted, it will show up at a currently empty
234                // position. `sibling` should prove the route from this empty position to the root.
235            }
236        }
237
238        let current_hash = self
239            .leaf
240            .map_or(*SPARSE_MERKLE_PLACEHOLDER_HASH, |leaf| leaf.hash());
241        let actual_root_hash = self
242            .siblings
243            .iter()
244            .zip(
245                element_key
246                    .iter_bits()
247                    .rev()
248                    .skip(HashValue::LENGTH_IN_BITS - self.siblings.len()),
249            )
250            .fold(current_hash, |hash, (sibling_hash, bit)| {
251                if bit {
252                    SparseMerkleInternalNode::new(*sibling_hash, hash).hash()
253                } else {
254                    SparseMerkleInternalNode::new(hash, *sibling_hash).hash()
255                }
256            });
257        ensure!(
258            actual_root_hash == expected_root_hash,
259            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
260            actual_root_hash,
261            expected_root_hash,
262        );
263
264        Ok(())
265    }
266}
267
268/// An in-memory accumulator for storing a summary of the core transaction info
269/// accumulator. It is a summary in the sense that it only stores maximally
270/// frozen subtree nodes rather than storing all leaves and internal nodes.
271///
272/// Light clients and light nodes use this type to store their currently verified
273/// view of the transaction accumulator. When verifying state proofs, these clients
274/// attempt to extend their accumulator summary with an [`AccumulatorConsistencyProof`]
275/// to verifiably ratchet their trusted view of the accumulator to a newer state.
276#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
277pub struct TransactionAccumulatorSummary(InMemoryAccumulator<TransactionAccumulatorHasher>);
278
279impl TransactionAccumulatorSummary {
280    pub fn new(accumulator: InMemoryAccumulator<TransactionAccumulatorHasher>) -> Result<Self> {
281        ensure!(
282            !accumulator.is_empty(),
283            "empty accumulator: we can't verify consistency proofs from an empty accumulator",
284        );
285        Ok(Self(accumulator))
286    }
287
288    pub fn version(&self) -> Version {
289        self.0.version()
290    }
291
292    pub fn root_hash(&self) -> HashValue {
293        self.0.root_hash()
294    }
295
296    /// Verify that this accumulator summary is "consistent" with the given
297    /// [`LedgerInfo`], i.e., they both have the same version and accumulator
298    /// root hash.
299    pub fn verify_consistency(&self, ledger_info: &LedgerInfo) -> Result<()> {
300        ensure!(
301            ledger_info.version() == self.version(),
302            "ledger info and accumulator must be at the same version: \
303             ledger info version={}, accumulator version={}",
304            ledger_info.version(),
305            self.version(),
306        );
307        ensure!(
308            ledger_info.transaction_accumulator_hash() == self.root_hash(),
309            "ledger info root hash and accumulator root hash must match: \
310             ledger info root hash={}, accumulator root hash={}",
311            ledger_info.transaction_accumulator_hash(),
312            self.root_hash(),
313        );
314        Ok(())
315    }
316
317    /// Try to build an accumulator summary using a consistency proof starting
318    /// from pre-genesis.
319    pub fn try_from_genesis_proof(
320        genesis_proof: AccumulatorConsistencyProof,
321        target_version: Version,
322    ) -> Result<Self> {
323        let num_txns = target_version.saturating_add(1);
324        Ok(Self(InMemoryAccumulator::new(
325            genesis_proof.into_subtrees(),
326            num_txns,
327        )?))
328    }
329
330    /// Try to extend an existing accumulator summary with a consistency proof
331    /// starting from our current version. Then validate that the resulting
332    /// accumulator summary is consistent with the given target [`LedgerInfo`].
333    pub fn try_extend_with_proof(
334        &self,
335        consistency_proof: &AccumulatorConsistencyProof,
336        target_li: &LedgerInfo,
337    ) -> Result<Self> {
338        ensure!(
339            target_li.version() >= self.0.version(),
340            "target ledger info version ({}) must be newer than our current accumulator \
341             summary version ({})",
342            target_li.version(),
343            self.0.version(),
344        );
345        let num_new_txns = target_li.version() - self.0.version();
346        let new_accumulator = Self(
347            self.0
348                .append_subtrees(consistency_proof.subtrees(), num_new_txns)?,
349        );
350        new_accumulator
351            .verify_consistency(target_li)
352            .context("accumulator is not consistent with the target ledger info after applying consistency proof")?;
353        Ok(new_accumulator)
354    }
355}
356
357/// A proof that can be used to show that two Merkle accumulators are consistent -- the big one can
358/// be obtained by appending certain leaves to the small one. For example, at some point in time a
359/// client knows that the root hash of the ledger at version 10 is `old_root` (it could be a
360/// waypoint). If a server wants to prove that the new ledger at version `N` is derived from the
361/// old ledger the client knows, it can show the subtrees that represent all the new leaves. If
362/// the client can verify that it can indeed obtain the new root hash by appending these new
363/// leaves, it can be convinced that the two accumulators are consistent.
364///
365/// See [`crate::proof::accumulator::Accumulator::append_subtrees`] for more details.
366#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
367pub struct AccumulatorConsistencyProof {
368    /// The subtrees representing the newly appended leaves.
369    subtrees: Vec<HashValue>,
370}
371
372impl AccumulatorConsistencyProof {
373    /// Constructs a new `AccumulatorConsistencyProof` using given `subtrees`.
374    pub fn new(subtrees: Vec<HashValue>) -> Self {
375        Self { subtrees }
376    }
377
378    pub fn is_empty(&self) -> bool {
379        self.subtrees.is_empty()
380    }
381
382    /// Returns the subtrees.
383    pub fn subtrees(&self) -> &[HashValue] {
384        &self.subtrees
385    }
386
387    pub fn into_subtrees(self) -> Vec<HashValue> {
388        self.subtrees
389    }
390}
391
392/// A proof that is similar to `AccumulatorProof`, but can be used to authenticate a range of
393/// leaves. For example, given the following accumulator:
394///
395/// ```text
396///                 root
397///                /     \
398///              /         \
399///            /             \
400///           o               o
401///         /   \           /   \
402///        /     \         /     \
403///       X       o       o       Y
404///      / \     / \     / \     / \
405///     o   o   a   b   c   Z   o   o
406/// ```
407///
408/// if the proof wants to show that `[a, b, c]` exists in the accumulator, it would need `X` on the
409/// left and `Y` and `Z` on the right.
410#[derive(Clone, Deserialize, Serialize)]
411pub struct AccumulatorRangeProof<H> {
412    /// The siblings on the left of the path from the first leaf to the root. Siblings near the root
413    /// are at the beginning of the vector.
414    left_siblings: Vec<HashValue>,
415
416    /// The sliblings on the right of the path from the last leaf to the root. Siblings near the root
417    /// are at the beginning of the vector.
418    right_siblings: Vec<HashValue>,
419
420    phantom: PhantomData<H>,
421}
422
423impl<H> AccumulatorRangeProof<H>
424where
425    H: CryptoHasher,
426{
427    /// Constructs a new `AccumulatorRangeProof` using `left_siblings` and `right_siblings`.
428    pub fn new(left_siblings: Vec<HashValue>, right_siblings: Vec<HashValue>) -> Self {
429        Self {
430            left_siblings,
431            right_siblings,
432            phantom: PhantomData,
433        }
434    }
435
436    /// Constructs a new `AccumulatorRangeProof` for an empty list of leaves.
437    pub fn new_empty() -> Self {
438        Self::new(vec![], vec![])
439    }
440
441    /// Get all the left siblngs.
442    pub fn left_siblings(&self) -> &Vec<HashValue> {
443        &self.left_siblings
444    }
445
446    /// Get all the right siblngs.
447    pub fn right_siblings(&self) -> &Vec<HashValue> {
448        &self.right_siblings
449    }
450
451    /// Verifies the proof is correct. The verifier needs to have `expected_root_hash`, the index
452    /// of the first leaf and all of the leaves in possession.
453    pub fn verify(
454        &self,
455        expected_root_hash: HashValue,
456        first_leaf_index: Option<u64>,
457        leaf_hashes: &[HashValue],
458    ) -> Result<()> {
459        if first_leaf_index.is_none() {
460            ensure!(
461                leaf_hashes.is_empty(),
462                "first_leaf_index indicated empty list while leaf_hashes is not empty.",
463            );
464            ensure!(
465                self.left_siblings.is_empty() && self.right_siblings.is_empty(),
466                "No siblings are needed.",
467            );
468            return Ok(());
469        }
470
471        ensure!(
472            self.left_siblings.len() <= MAX_ACCUMULATOR_PROOF_DEPTH,
473            "Proof has more than {} ({}) left siblings.",
474            MAX_ACCUMULATOR_PROOF_DEPTH,
475            self.left_siblings.len(),
476        );
477        ensure!(
478            self.right_siblings.len() <= MAX_ACCUMULATOR_PROOF_DEPTH,
479            "Proof has more than {} ({}) right siblings.",
480            MAX_ACCUMULATOR_PROOF_DEPTH,
481            self.right_siblings.len(),
482        );
483        ensure!(
484            !leaf_hashes.is_empty(),
485            "leaf_hashes is empty while first_leaf_index indicated non-empty list.",
486        );
487
488        let mut left_sibling_iter = self.left_siblings.iter().peekable();
489        let mut right_sibling_iter = self.right_siblings.iter().peekable();
490
491        let mut first_pos = Position::from_leaf_index(
492            first_leaf_index.expect("first_leaf_index should not be None."),
493        );
494        let mut current_hashes = leaf_hashes.to_vec();
495        let mut parent_hashes = vec![];
496
497        // Keep reducing the list of hashes by combining all the children pairs, until there is
498        // only one hash left.
499        while current_hashes.len() > 1
500            || left_sibling_iter.peek().is_some()
501            || right_sibling_iter.peek().is_some()
502        {
503            let mut children_iter = current_hashes.iter();
504
505            // If the first position on the current level is a right child, it needs to be combined
506            // with a sibling on the left.
507            if first_pos.is_right_child() {
508                let left_hash = *left_sibling_iter.next().ok_or_else(|| {
509                    format_err!("First child is a right child, but missing sibling on the left.")
510                })?;
511                let right_hash = *children_iter.next().expect("The first leaf must exist.");
512                parent_hashes.push(MerkleTreeInternalNode::<H>::new(left_hash, right_hash).hash());
513            }
514
515            // Next we take two children at a time and compute their parents.
516            let mut children_iter = children_iter.as_slice().chunks_exact(2);
517            while let Some(chunk) = children_iter.next() {
518                let left_hash = chunk[0];
519                let right_hash = chunk[1];
520                parent_hashes.push(MerkleTreeInternalNode::<H>::new(left_hash, right_hash).hash());
521            }
522
523            // Similarly, if the last position is a left child, it needs to be combined with a
524            // sibling on the right.
525            let remainder = children_iter.remainder();
526            assert!(remainder.len() <= 1);
527            if !remainder.is_empty() {
528                let left_hash = remainder[0];
529                let right_hash = *right_sibling_iter.next().ok_or_else(|| {
530                    format_err!("Last child is a left child, but missing sibling on the right.")
531                })?;
532                parent_hashes.push(MerkleTreeInternalNode::<H>::new(left_hash, right_hash).hash());
533            }
534
535            first_pos = first_pos.parent();
536            current_hashes.clear();
537            std::mem::swap(&mut current_hashes, &mut parent_hashes);
538        }
539
540        ensure!(
541            current_hashes[0] == expected_root_hash,
542            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
543            current_hashes[0],
544            expected_root_hash,
545        );
546
547        Ok(())
548    }
549}
550
551impl<H> std::fmt::Debug for AccumulatorRangeProof<H> {
552    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
553        write!(
554            f,
555            "AccumulatorRangeProof {{ left_siblings: {:?}, right_siblings: {:?} }}",
556            self.left_siblings, self.right_siblings,
557        )
558    }
559}
560
561impl<H> PartialEq for AccumulatorRangeProof<H> {
562    fn eq(&self, other: &Self) -> bool {
563        self.left_siblings == other.left_siblings && self.right_siblings == other.right_siblings
564    }
565}
566
567impl<H> Eq for AccumulatorRangeProof<H> {}
568
569pub type TransactionAccumulatorRangeProof = AccumulatorRangeProof<TransactionAccumulatorHasher>;
570#[cfg(any(test, feature = "fuzzing"))]
571pub type TestAccumulatorRangeProof = AccumulatorRangeProof<TestOnlyHasher>;
572
573/// Note: this is not a range proof in the sense that a range of nodes is verified!
574/// Instead, it verifies the entire left part of the tree up to a known rightmost node.
575/// See the description below.
576///
577/// A proof that can be used to authenticate a range of consecutive leaves, from the leftmost leaf to
578/// the rightmost known one, in a sparse Merkle tree. For example, given the following sparse Merkle tree:
579///
580/// ```text
581///                   root
582///                  /     \
583///                 /       \
584///                /         \
585///               o           o
586///              / \         / \
587///             a   o       o   h
588///                / \     / \
589///               o   d   e   X
590///              / \         / \
591///             b   c       f   g
592/// ```
593///
594/// if the proof wants show that `[a, b, c, d, e]` exists in the tree, it would need the siblings
595/// `X` and `h` on the right.
596#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
597pub struct SparseMerkleRangeProof {
598    /// The vector of siblings on the right of the path from root to last leaf. The ones near the
599    /// bottom are at the beginning of the vector. In the above example, it's `[X, h]`.
600    right_siblings: Vec<HashValue>,
601}
602
603impl SparseMerkleRangeProof {
604    /// Constructs a new `SparseMerkleRangeProof`.
605    pub fn new(right_siblings: Vec<HashValue>) -> Self {
606        Self { right_siblings }
607    }
608
609    /// Returns the right siblings.
610    pub fn right_siblings(&self) -> &[HashValue] {
611        &self.right_siblings
612    }
613
614    /// Verifies that the rightmost known leaf exists in the tree and that the resulting
615    /// root hash matches the expected root hash.
616    pub fn verify(
617        &self,
618        expected_root_hash: HashValue,
619        rightmost_known_leaf: SparseMerkleLeafNode,
620        left_siblings: Vec<HashValue>,
621    ) -> Result<()> {
622        let num_siblings = left_siblings.len() + self.right_siblings.len();
623        let mut left_sibling_iter = left_siblings.iter();
624        let mut right_sibling_iter = self.right_siblings().iter();
625
626        let mut current_hash = rightmost_known_leaf.hash();
627        for bit in rightmost_known_leaf
628            .key()
629            .iter_bits()
630            .rev()
631            .skip(HashValue::LENGTH_IN_BITS - num_siblings)
632        {
633            let (left_hash, right_hash) = if bit {
634                (
635                    *left_sibling_iter
636                        .next()
637                        .ok_or_else(|| format_err!("Missing left sibling."))?,
638                    current_hash,
639                )
640            } else {
641                (
642                    current_hash,
643                    *right_sibling_iter
644                        .next()
645                        .ok_or_else(|| format_err!("Missing right sibling."))?,
646                )
647            };
648            current_hash = SparseMerkleInternalNode::new(left_hash, right_hash).hash();
649        }
650
651        ensure!(
652            current_hash == expected_root_hash,
653            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
654            current_hash,
655            expected_root_hash,
656        );
657
658        Ok(())
659    }
660}
661
662/// `TransactionInfo` and a `TransactionAccumulatorProof` connecting it to the ledger root.
663#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
664#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
665pub struct TransactionInfoWithProof<T> {
666    /// The accumulator proof from ledger info root to leaf that authenticates the hash of the
667    /// `TransactionInfo` object.
668    pub ledger_info_to_transaction_info_proof: TransactionAccumulatorProof,
669
670    /// The `TransactionInfo` object at the leaf of the accumulator.
671    pub transaction_info: T,
672}
673
674impl<T: TransactionInfoTrait> TransactionInfoWithProof<T> {
675    /// Constructs a new `TransactionWithProof` object using given
676    /// `ledger_info_to_transaction_info_proof`.
677    pub fn new(
678        ledger_info_to_transaction_info_proof: TransactionAccumulatorProof,
679        transaction_info: T,
680    ) -> Self {
681        Self {
682            ledger_info_to_transaction_info_proof,
683            transaction_info,
684        }
685    }
686
687    /// Returns the `ledger_info_to_transaction_info_proof` object in this proof.
688    pub fn ledger_info_to_transaction_info_proof(&self) -> &TransactionAccumulatorProof {
689        &self.ledger_info_to_transaction_info_proof
690    }
691
692    /// Returns the `transaction_info` object in this proof.
693    pub fn transaction_info(&self) -> &T {
694        &self.transaction_info
695    }
696
697    /// Verifies that the `TransactionInfo` exists in the ledger represented by the `LedgerInfo`
698    /// at specified version.
699    pub fn verify(&self, ledger_info: &LedgerInfo, transaction_version: Version) -> Result<()> {
700        verify_transaction_info(
701            ledger_info,
702            transaction_version,
703            &self.transaction_info,
704            &self.ledger_info_to_transaction_info_proof,
705        )?;
706        Ok(())
707    }
708}
709
710/// The complete proof used to authenticate the state of an account. This structure consists of the
711/// `AccumulatorProof` from `LedgerInfo` to `TransactionInfo`, the `TransactionInfo` object and the
712/// `SparseMerkleProof` from state root to the account.
713#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
714#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
715pub struct AccountStateProof<T> {
716    transaction_info_with_proof: TransactionInfoWithProof<T>,
717
718    /// The sparse merkle proof from state root to the account state.
719    transaction_info_to_account_proof: SparseMerkleProof<AccountStateBlob>,
720}
721
722impl<T: TransactionInfoTrait> AccountStateProof<T> {
723    /// Constructs a new `AccountStateProof` using given `ledger_info_to_transaction_info_proof`,
724    /// `transaction_info` and `transaction_info_to_account_proof`.
725    pub fn new(
726        transaction_info_with_proof: TransactionInfoWithProof<T>,
727        transaction_info_to_account_proof: SparseMerkleProof<AccountStateBlob>,
728    ) -> Self {
729        AccountStateProof {
730            transaction_info_with_proof,
731            transaction_info_to_account_proof,
732        }
733    }
734
735    /// Returns the `transaction_info_with_proof` object in this proof.
736    pub fn transaction_info_with_proof(&self) -> &TransactionInfoWithProof<T> {
737        &self.transaction_info_with_proof
738    }
739
740    /// Returns the `transaction_info_to_account_proof` object in this proof.
741    pub fn transaction_info_to_account_proof(&self) -> &SparseMerkleProof<AccountStateBlob> {
742        &self.transaction_info_to_account_proof
743    }
744
745    /// Verifies that the state of an account at version `state_version` is correct using the
746    /// provided proof. If `account_state_blob` is present, we expect the account to exist,
747    /// otherwise we expect the account to not exist.
748    pub fn verify(
749        &self,
750        ledger_info: &LedgerInfo,
751        state_version: Version,
752        account_address_hash: HashValue,
753        account_state_blob: Option<&AccountStateBlob>,
754    ) -> Result<()> {
755        self.transaction_info_to_account_proof.verify(
756            self.transaction_info_with_proof
757                .transaction_info
758                .state_root_hash(),
759            account_address_hash,
760            account_state_blob,
761        )?;
762
763        self.transaction_info_with_proof
764            .verify(ledger_info, state_version)?;
765
766        Ok(())
767    }
768}
769
770/// The complete proof used to authenticate a contract event. This structure consists of the
771/// `AccumulatorProof` from `LedgerInfo` to `TransactionInfo`, the `TransactionInfo` object and the
772/// `AccumulatorProof` from event accumulator root to the event.
773#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
774#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
775pub struct EventProof<T> {
776    transaction_info_with_proof: TransactionInfoWithProof<T>,
777
778    /// The accumulator proof from event root to the actual event.
779    transaction_info_to_event_proof: EventAccumulatorProof,
780}
781
782impl<T: TransactionInfoTrait> EventProof<T> {
783    /// Constructs a new `EventProof` using given `ledger_info_to_transaction_info_proof`,
784    /// `transaction_info` and `transaction_info_to_event_proof`.
785    pub fn new(
786        transaction_info_with_proof: TransactionInfoWithProof<T>,
787        transaction_info_to_event_proof: EventAccumulatorProof,
788    ) -> Self {
789        EventProof {
790            transaction_info_with_proof,
791            transaction_info_to_event_proof,
792        }
793    }
794
795    /// Returns the `transaction_info_with_proof` object in this proof.
796    pub fn transaction_info_with_proof(&self) -> &TransactionInfoWithProof<T> {
797        &self.transaction_info_with_proof
798    }
799
800    /// Verifies that a given event is correct using provided proof.
801    pub fn verify(
802        &self,
803        ledger_info: &LedgerInfo,
804        event_hash: HashValue,
805        transaction_version: Version,
806        event_version_within_transaction: Version,
807    ) -> Result<()> {
808        self.transaction_info_to_event_proof.verify(
809            self.transaction_info_with_proof
810                .transaction_info()
811                .event_root_hash(),
812            event_hash,
813            event_version_within_transaction,
814        )?;
815
816        self.transaction_info_with_proof
817            .verify(ledger_info, transaction_version)?;
818
819        Ok(())
820    }
821}
822
823/// The proof used to authenticate a list of consecutive transaction infos.
824#[derive(Clone, Debug, Eq, PartialEq, Deserialize, Serialize)]
825#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
826pub struct TransactionInfoListWithProof<T> {
827    pub ledger_info_to_transaction_infos_proof: TransactionAccumulatorRangeProof,
828    pub transaction_infos: Vec<T>,
829}
830
831impl<T: TransactionInfoTrait> TransactionInfoListWithProof<T> {
832    pub fn new(
833        ledger_info_to_transaction_infos_proof: TransactionAccumulatorRangeProof,
834        transaction_infos: Vec<T>,
835    ) -> Self {
836        Self {
837            ledger_info_to_transaction_infos_proof,
838            transaction_infos,
839        }
840    }
841
842    /// Constructs a proof for an empty list of transaction infos. Mostly used for tests.
843    pub fn new_empty() -> Self {
844        Self::new(AccumulatorRangeProof::new_empty(), vec![])
845    }
846
847    /// Verifies the list of transaction infos are correct using the proof. The verifier
848    /// needs to have the ledger info and the version of the first transaction in possession.
849    pub fn verify(
850        &self,
851        ledger_info: &LedgerInfo,
852        first_transaction_info_version: Option<Version>,
853    ) -> Result<()> {
854        let txn_info_hashes: Vec<_> = self
855            .transaction_infos
856            .iter()
857            .map(CryptoHash::hash)
858            .collect();
859        self.ledger_info_to_transaction_infos_proof.verify(
860            ledger_info.transaction_accumulator_hash(),
861            first_transaction_info_version,
862            &txn_info_hashes,
863        )
864    }
865}
866
867/// A proof that first verifies that establishes correct computation of the root and then
868/// returns the new tree to acquire a new root and version.
869#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
870pub struct AccumulatorExtensionProof<H> {
871    /// Represents the roots of all the full subtrees from left to right in the original accumulator.
872    frozen_subtree_roots: Vec<HashValue>,
873    /// The total number of leaves in original accumulator.
874    num_leaves: LeafCount,
875    /// The values representing the newly appended leaves.
876    leaves: Vec<HashValue>,
877
878    hasher: PhantomData<H>,
879}
880
881impl<H: CryptoHasher> AccumulatorExtensionProof<H> {
882    pub fn new(
883        frozen_subtree_roots: Vec<HashValue>,
884        num_leaves: LeafCount,
885        leaves: Vec<HashValue>,
886    ) -> Self {
887        Self {
888            frozen_subtree_roots,
889            num_leaves,
890            leaves,
891            hasher: PhantomData,
892        }
893    }
894
895    pub fn verify(&self, original_root: HashValue) -> anyhow::Result<InMemoryAccumulator<H>> {
896        let original_tree =
897            InMemoryAccumulator::<H>::new(self.frozen_subtree_roots.clone(), self.num_leaves)?;
898        ensure!(
899            original_tree.root_hash() == original_root,
900            "Root hashes do not match. Actual root hash: {:x}. Expected root hash: {:x}.",
901            original_tree.root_hash(),
902            original_root
903        );
904
905        Ok(original_tree.append(self.leaves.as_slice()))
906    }
907}
908
909pub mod default_protocol {
910    use crate::transaction::TransactionInfo;
911
912    pub use super::{
913        AccumulatorConsistencyProof, AccumulatorExtensionProof, AccumulatorProof,
914        AccumulatorRangeProof, EventAccumulatorProof, SparseMerkleProof, SparseMerkleRangeProof,
915        TransactionAccumulatorProof, TransactionAccumulatorRangeProof,
916        TransactionAccumulatorSummary,
917    };
918
919    pub type AccountStateProof = super::AccountStateProof<TransactionInfo>;
920    pub type EventProof = super::EventProof<TransactionInfo>;
921    pub type TransactionInfoListWithProof = super::TransactionInfoListWithProof<TransactionInfo>;
922    pub type TransactionInfoWithProof = super::TransactionInfoWithProof<TransactionInfo>;
923}
diem_types/proof/definition.rs

diem_types/proof/
definition.rs
