1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

// Copyright 2020 ChainSafe Systems
// SPDX-License-Identifier: Apache-2.0

//! This module contains traits, structs and utilities of merkle proof

use std::{error::Error, marker::PhantomData};

use crate::*;

/// Merkle proof trait of a single leaf node, for details refer to <https://www.webopedia.com/definitions/merkle-proof/>
pub trait MerkleProof {
    /// Hash type
    type Hash: PartialEq;

    /// Error type
    type Error: Error;

    /// Calculates the root hash
    fn root_hash(&self) -> Result<Self::Hash, Self::Error>;

    /// Verifies if the proof is valid
    fn verify(&self, root_hash: &Self::Hash) -> bool {
        if let Ok(hash) = self.root_hash() {
            &hash == root_hash
        } else {
            false
        }
    }
}

/// Type that represents errors in calculating hashes for a merkle proof
#[derive(thiserror::Error, Debug, Eq, PartialEq)]
pub enum MerkleProofError {
    /// Index of a data node should be positive
    #[error("Index of a data node should be positive")]
    InvalidIndex,
    /// The merkle proof is invalid
    #[error("The merkle proof is invalid")]
    InvalidProof,
    /// Errors occur in hash merger
    #[error("Errors occur in hash merger")]
    MergerFailure,
}

/// Merkle proof implementation of a single leaf node, for details refer to <https://www.webopedia.com/definitions/merkle-proof/>
pub struct DefaultMerkleProof<Item, Hash, Hasher, Merger>
where
    Hash: PartialEq + Clone,
    Hasher: MerkleHasher<Item = Item, Hash = Hash>,
    Merger: MerkleMerger<Hash = Hash>,
{
    ///
    pub index: usize,
    ///
    pub item: Item,
    ///
    pub peer_indices: Vec<usize>,
    ///
    pub peer_hashes: Vec<Option<Hash>>,
    ///
    pub _hasher: PhantomData<Hasher>,
    ///
    pub _merger: PhantomData<Merger>,
}

impl<Item, Hash, Hasher, Merger> DefaultMerkleProof<Item, Hash, Hasher, Merger>
where
    Hash: PartialEq + Clone,
    Hasher: MerkleHasher<Item = Item, Hash = Hash>,
    Merger: MerkleMerger<Hash = Hash>,
{
    /// Creates merkle proof instance
    /// index is the node index counted from root. e.g. index of the root node is 0
    /// Note that index of a data node will always be positive
    pub fn new(
        index: usize,
        item: Item,
        peer_indices: Vec<usize>,
        peer_hashes: Vec<Option<Hash>>,
    ) -> Self {
        assert!(index > 0, "index of a data node should always to positive");
        assert_eq!(
            peer_indices.len(),
            peer_hashes.len(),
            "length of peer_indices and peer_hashes should match"
        );
        assert!(
            !peer_indices.is_empty(),
            "length of peer_indices and peer_hashes should be positive"
        );
        Self {
            index,
            item,
            peer_indices,
            peer_hashes,
            _hasher: Default::default(),
            _merger: Default::default(),
        }
    }
}

impl<Item, Hash, Hasher, Merger> MerkleProof for DefaultMerkleProof<Item, Hash, Hasher, Merger>
where
    Hash: PartialEq + Clone + std::fmt::Debug,
    Hasher: MerkleHasher<Item = Item, Hash = Hash>,
    Merger: MerkleMerger<Hash = Hash>,
{
    type Hash = Hash;
    type Error = MerkleProofError;

    fn root_hash(&self) -> Result<Hash, Self::Error> {
        // index of a data node should always to positive
        if self.index > 0 {
            // 1. Get the index and hash of the data node
            let mut index = self.index;
            let mut hash_opt = Some(Hasher::hash(
                &self.item,
                MerkleTreeNodeMetadata::new(self.index, self.peer_indices.len() as u32),
            ));
            for i in 0..self.peer_indices.len() {
                // 2. Find the hash of its sibling
                let peer_index = self.peer_indices[i];
                let peer_hash_opt = &self.peer_hashes[i];
                // 3 Prepare the input for for the hash merger by ordering the 2 hashes properly
                let hashes =
                    get_ordered_siblings(index, hash_opt, peer_index, peer_hash_opt.clone())?;
                // 4 Calculates the hash of their parent by invoking the associated merkle merger
                let parent_index = get_parent_index(index);
                hash_opt = Merger::merge(
                    hashes,
                    MerkleTreeNodeMetadata::new(parent_index, self.peer_indices.len() as u32),
                );
                // Go back to step 1 and apply the same flow to this parent node
                // until the root hash (of index 0) has been calculated.
                index = parent_index;
            }
            if let Some(hash) = hash_opt {
                Ok(hash)
            } else {
                Err(MerkleProofError::MergerFailure)
            }
        } else {
            Err(MerkleProofError::InvalidIndex)
        }
    }
}

fn get_parent_index(index: usize) -> usize {
    debug_assert!(index > 0);
    (index - 1) / 2
}

fn get_ordered_siblings<Hash>(
    index: usize,
    hash: Option<Hash>,
    sibling_index: usize,
    sibling_hash: Option<Hash>,
) -> Result<[Option<Hash>; 2], MerkleProofError> {
    if index + 1 == sibling_index {
        Ok([hash, sibling_hash])
    } else if index == sibling_index + 1 {
        Ok([sibling_hash, hash])
    } else {
        Err(MerkleProofError::InvalidProof)
    }
}