oasis_core_runtime/consensus/tendermint/
merkle.rs

1//! Merkle proofs used in Tendermint networks
2//!
3//! Rewritten to Rust from:
4//! https://github.com/tendermint/tendermint/blob/main/crypto/merkle/proof.go
5//!
6//! Helper functions copied from:
7//! https://github.com/informalsystems/tendermint-rs/blob/main/tendermint/src/merkle.rs
8
9use std::cmp::Ordering;
10
11use anyhow::{anyhow, Result};
12use rustc_hex::ToHex;
13use sha2::{Digest, Sha256};
14
15use tendermint::merkle::{Hash, HASH_SIZE};
16
17/// Maximum number of aunts that can be included in a Proof.
18/// This corresponds to a tree of size 2^100, which should be sufficient for all conceivable purposes.
19/// This maximum helps prevent Denial-of-Service attacks by limiting the size of the proofs.
20pub const MAX_AUNTS: usize = 100;
21
22/// Proof represents a Merkle proof.
23///
24/// NOTE: The convention for proofs is to include leaf hashes but to
25/// exclude the root hash.
26/// This convention is implemented across IAVL range proofs as well.
27/// Keep this consistent unless there's a very good reason to change
28/// everything.  This also affects the generalized proof system as
29/// well.
30#[derive(Debug, Default, cbor::Encode, cbor::Decode)]
31pub struct Proof {
32    pub total: i64,       // Total number of items.
33    pub index: i64,       // Index of item to prove.
34    pub leaf_hash: Hash,  // Hash of item value.
35    pub aunts: Vec<Hash>, // Hashes from leaf's sibling to a root's child.
36}
37
38impl Proof {
39    /// Verify that the Proof proves the root hash.
40    /// Check index/total manually if needed.
41    pub fn verify(&self, root_hash: Hash, leaf: Hash) -> Result<()> {
42        if self.total < 0 {
43            return Err(anyhow!("proof total must be positive"));
44        }
45        if self.index < 0 {
46            return Err(anyhow!("proof index cannot be negative"));
47        }
48        if self.aunts.len() > MAX_AUNTS {
49            return Err(anyhow!(
50                "expected no more than {} aunts, got {}",
51                MAX_AUNTS,
52                self.aunts.len()
53            ));
54        }
55
56        let leaf_hash = leaf_hash(&leaf);
57        match self.leaf_hash.cmp(&leaf_hash) {
58            Ordering::Equal => (),
59            _ => {
60                return Err(anyhow!(
61                    "invalid leaf hash: wanted {} got {}",
62                    leaf_hash.to_hex::<String>(),
63                    self.leaf_hash.to_hex::<String>(),
64                ));
65            }
66        }
67
68        let computed_hash = self.compute_root_hash().ok_or_else(|| {
69            anyhow!(
70                "invalid root hash: wanted {} got None",
71                root_hash.to_hex::<String>()
72            )
73        })?;
74        match computed_hash.cmp(&root_hash) {
75            Ordering::Equal => (),
76            _ => {
77                return Err(anyhow!(
78                    "invalid root hash: wanted {} got {}",
79                    root_hash.to_hex::<String>(),
80                    computed_hash.to_hex::<String>(),
81                ));
82            }
83        }
84
85        Ok(())
86    }
87
88    /// Compute the root hash given a leaf hash. Does not verify the result.
89    pub fn compute_root_hash(&self) -> Option<Hash> {
90        Self::compute_hash_from_aunts(self.index, self.total, self.leaf_hash, &self.aunts)
91    }
92
93    /// Use the leaf_hash and inner_hashes to get the root merkle hash.
94    /// If the length of the inner_hashes slice isn't exactly correct, the result is None.
95    /// Recursive impl.
96    fn compute_hash_from_aunts(
97        index: i64,
98        total: i64,
99        leaf_hash: Hash,
100        inner_hashes: &[Hash],
101    ) -> Option<Hash> {
102        if index >= total || index < 0 || total <= 0 {
103            return None;
104        }
105        match total {
106            0 => unreachable!("cannot call compute_hash_from_aunts() with 0 total"), // Handled above.
107            1 => {
108                if !inner_hashes.is_empty() {
109                    return None;
110                }
111                Some(leaf_hash)
112            }
113            _ => {
114                if inner_hashes.is_empty() {
115                    return None;
116                }
117                let last_idx = inner_hashes.len() - 1;
118                let last_hash = inner_hashes[last_idx];
119                let inner_hashes = &inner_hashes[..last_idx];
120
121                let num_left = get_split_point(total as usize) as i64;
122                if index < num_left {
123                    if let Some(left_hash) =
124                        Self::compute_hash_from_aunts(index, num_left, leaf_hash, inner_hashes)
125                    {
126                        return Some(inner_hash(&left_hash, &last_hash));
127                    }
128                    return None;
129                }
130                if let Some(right_hash) = Self::compute_hash_from_aunts(
131                    index - num_left,
132                    total - num_left,
133                    leaf_hash,
134                    inner_hashes,
135                ) {
136                    return Some(inner_hash(&last_hash, &right_hash));
137                }
138                None
139            }
140        }
141    }
142}
143
144/// returns the largest power of 2 less than length
145fn get_split_point(length: usize) -> usize {
146    match length {
147        0 => panic!("tree is empty!"),
148        1 => panic!("tree has only one element!"),
149        2 => 1,
150        _ => length.next_power_of_two() / 2,
151    }
152}
153
154/// tmhash(0x00 || leaf)
155fn leaf_hash(bytes: &[u8]) -> Hash {
156    // make a new array starting with 0 and copy in the bytes
157    let mut leaf_bytes = Vec::with_capacity(bytes.len() + 1);
158    leaf_bytes.push(0x00);
159    leaf_bytes.extend_from_slice(bytes);
160
161    // hash it !
162    let digest = Sha256::digest(&leaf_bytes);
163
164    // copy the GenericArray out
165    let mut hash_bytes = [0u8; HASH_SIZE];
166    hash_bytes.copy_from_slice(&digest);
167    hash_bytes
168}
169
170/// tmhash(0x01 || left || right)
171fn inner_hash(left: &[u8], right: &[u8]) -> Hash {
172    // make a new array starting with 0x1 and copy in the bytes
173    let mut inner_bytes = Vec::with_capacity(left.len() + right.len() + 1);
174    inner_bytes.push(0x01);
175    inner_bytes.extend_from_slice(left);
176    inner_bytes.extend_from_slice(right);
177
178    // hash it !
179    let digest = Sha256::digest(&inner_bytes);
180
181    // copy the GenericArray out
182    let mut hash_bytes = [0u8; HASH_SIZE];
183    hash_bytes.copy_from_slice(&digest);
184    hash_bytes
185}
oasis_core_runtime/consensus/tendermint/merkle.rs

oasis_core_runtime/consensus/tendermint/
merkle.rs
