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

diem_types/proof/
definition.rs
