cloud_mmr/
merkle_proof.rs

1// Copyright 2021 The Grin Developers
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Merkle Proofs
16
17use crate::hash::Hash;
18use crate::pmmr;
19use crate::ser::{self, PMMRIndexHashable, Readable, Reader, Writeable, Writer};
20
21/// Merkle proof errors.
22#[derive(Clone, Debug, PartialEq)]
23pub enum MerkleProofError {
24    /// Merkle proof root hash does not match when attempting to verify.
25    RootMismatch,
26}
27
28/// A Merkle proof that proves a particular element exists in the MMR.
29#[derive(Serialize, Deserialize, Debug, Eq, PartialEq, Clone, PartialOrd, Ord)]
30pub struct MerkleProof {
31    /// The size of the MMR at the time the proof was created.
32    pub mmr_size: u64,
33    /// The sibling path from the leaf up to the final sibling hashing to the
34    /// root.
35    pub path: Vec<Hash>,
36}
37
38impl Writeable for MerkleProof {
39    fn write<W: Writer>(&self, writer: &mut W) -> Result<(), ser::Error> {
40        writer.write_u64(self.mmr_size)?;
41        writer.write_u64(self.path.len() as u64)?;
42        self.path.write(writer)?;
43        Ok(())
44    }
45}
46
47impl Readable for MerkleProof {
48    fn read<R: Reader>(reader: &mut R) -> Result<MerkleProof, ser::Error> {
49        let mmr_size = reader.read_u64()?;
50        let path_len = reader.read_u64()?;
51        let mut path = Vec::with_capacity(path_len as usize);
52        for _ in 0..path_len {
53            let hash = Hash::read(reader)?;
54            path.push(hash);
55        }
56
57        Ok(MerkleProof { mmr_size, path })
58    }
59}
60
61impl Default for MerkleProof {
62    fn default() -> MerkleProof {
63        MerkleProof::empty()
64    }
65}
66
67impl MerkleProof {
68    /// The "empty" Merkle proof.
69    pub fn empty() -> MerkleProof {
70        MerkleProof {
71            mmr_size: 0,
72            path: Vec::default(),
73        }
74    }
75
76    /// Serialize the Merkle proof as a hex string (for api json endpoints)
77    pub fn to_hex(&self) -> String {
78        let mut vec: Vec<u8> = Vec::new();
79        ser::serialize_default(&mut vec, &self).expect("serialization failed");
80        hex::encode(&vec)
81    }
82
83    /// Convert hex string representation back to a Merkle proof instance
84    pub fn from_hex(hex: &str) -> Result<MerkleProof, String> {
85        let bytes = hex::decode(hex).unwrap();
86        let res = ser::deserialize_default(&mut &bytes[..])
87            .map_err(|_| "failed to deserialize a Merkle Proof".to_string())?;
88        Ok(res)
89    }
90
91    /// Verifies the Merkle proof against the provided
92    /// root hash, element and position in the MMR.
93    pub fn verify(
94        &self,
95        root: Hash,
96        element: &dyn PMMRIndexHashable,
97        node_pos: u64,
98    ) -> Result<(), MerkleProofError> {
99        let mut proof = self.clone();
100        // calculate the peaks once as these are based on overall MMR size
101        // (and will not change)
102        let peaks_pos = pmmr::peaks(self.mmr_size);
103        proof.verify_consume(root, element, node_pos, &peaks_pos)
104    }
105
106    /// Consumes the Merkle proof while verifying it.
107    /// The proof can no longer be used by the caller after dong this.
108    /// Caller must clone() the proof first.
109    fn verify_consume(
110        &mut self,
111        root: Hash,
112        element: &dyn PMMRIndexHashable,
113        node_pos0: u64,
114        peaks_pos0: &[u64],
115    ) -> Result<(), MerkleProofError> {
116        let node_hash = if node_pos0 >= self.mmr_size {
117            element.hash_with_index(self.mmr_size)
118        } else {
119            element.hash_with_index(node_pos0)
120        };
121
122        // handle special case of only a single entry in the MMR
123        // (no siblings to hash together)
124        if self.path.is_empty() {
125            if root == node_hash {
126                return Ok(());
127            } else {
128                return Err(MerkleProofError::RootMismatch);
129            }
130        }
131
132        let sibling = self.path.remove(0);
133        let (parent_pos0, sibling_pos0) = pmmr::family(node_pos0);
134
135        if let Ok(x) = peaks_pos0.binary_search(&(node_pos0)) {
136            let parent = if x == peaks_pos0.len() - 1 {
137                (sibling, node_hash)
138            } else {
139                (node_hash, sibling)
140            };
141            self.verify(root, &parent, parent_pos0)
142        } else if parent_pos0 >= self.mmr_size {
143            let parent = (sibling, node_hash);
144            self.verify(root, &parent, parent_pos0)
145        } else {
146            let parent = if pmmr::is_left_sibling(sibling_pos0) {
147                (sibling, node_hash)
148            } else {
149                (node_hash, sibling)
150            };
151            self.verify(root, &parent, parent_pos0)
152        }
153    }
154}
cloud_mmr/merkle_proof.rs

cloud_mmr/
merkle_proof.rs
