merkle_proof.rs

// Copyright 2019. The Tari Project
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
// following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
// disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
// following disclaimer in the documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote
// products derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
// USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

use std::fmt::{self, Display, Formatter};

use digest::Digest;
use log::error;
use serde::{Deserialize, Serialize};
use tari_utilities::hex::Hex;
use thiserror::Error;

use crate::{
    backend::ArrayLike,
    common::{family, family_branch, find_peaks, hash_together, is_leaf, is_left_sibling, node_index, LeafIndex},
    error::MerkleMountainRangeError,
    serde_support,
    Hash,
    HashSlice,
    MerkleMountainRange,
};

/// Merkle proof errors.
#[derive(Clone, Debug, PartialEq, Eq, Error)]
pub enum MerkleProofError {
    #[error("Merkle proof root hash does not match when attempting to verify.")]
    RootMismatch,
    #[error("You tried to construct or verify a Merkle proof using a non-leaf node as the inclusion candidate")]
    NonLeafNode,
    #[error("There was no hash in the merkle tree backend with the given position: `{0}`")]
    HashNotFound(usize),
    #[error("The list of peak hashes provided in the proof has an error")]
    IncorrectPeakMap,
    #[error("Unexpected error")]
    Unexpected,
    #[error("Merkle mountain range error: `{0}`")]
    MerkleMountainRangeError(#[from] MerkleMountainRangeError),
}

/// A Merkle proof that proves a particular element at a particular position exists in an MMR.
#[derive(Serialize, Deserialize, Debug, Eq, PartialEq, Clone, PartialOrd, Ord, Default)]
pub struct MerkleProof {
    /// The size of the MMR at the time the proof was created.
    pub mmr_size: usize,
    /// The sibling path from the leaf up to the final sibling hashing to the local root.
    #[serde(with = "serde_support::hash")]
    pub path: Vec<Hash>,
    /// The set of MMR peaks, not including the local peak for the candidate node
    #[serde(with = "serde_support::hash")]
    pub peaks: Vec<Hash>,
}

impl MerkleProof {
    /// Build a Merkle Proof the given MMR at the given *leaf* position. This is usually the version you'll want to
    /// call, since you'll know the leaf index more often than the MMR index.
    ///
    /// For the difference between leaf node and MMR node indices, see the [mod level](:tari_mmr) documentation.
    ///
    /// See [MerkleProof::for_node] for more details on how the proof is constructed.
    pub fn for_leaf_node<D, B>(
        mmr: &MerkleMountainRange<D, B>,
        leaf_index: LeafIndex,
    ) -> Result<MerkleProof, MerkleProofError>
    where
        D: Digest,
        B: ArrayLike<Value = Hash>,
    {
        let pos = node_index(leaf_index);
        MerkleProof::generate_proof(mmr, pos)
    }

    /// Build a Merkle proof for the candidate node at the given MMR index. If you want to build a proof using the
    /// leaf position, call [MerkleProof::for_leaf_node] instead. The given node position must be a leaf node,
    /// otherwise a `MerkleProofError::NonLeafNode` error will be returned.
    ///
    /// The proof for the MMR consists of two parts:
    /// a) A list of sibling node hashes starting from the candidate node and walking up the tree to the local root
    /// (i.e. the root of the binary tree that the candidate node lives in.
    /// b) A list of MMR peaks, excluding the local node hash.
    /// The final Merkle proof is constructed by hashing all the peaks together (this is slightly different to how
    /// other MMR implementations work).
    pub fn for_node<D, B>(mmr: &MerkleMountainRange<D, B>, pos: usize) -> Result<MerkleProof, MerkleProofError>
    where
        D: Digest,
        B: ArrayLike<Value = Hash>,
    {
        // check this pos is actually a leaf in the MMR
        if !is_leaf(pos) {
            return Err(MerkleProofError::NonLeafNode);
        }

        MerkleProof::generate_proof(mmr, pos)
    }

    fn generate_proof<D, B>(mmr: &MerkleMountainRange<D, B>, pos: usize) -> Result<MerkleProof, MerkleProofError>
    where
        D: Digest,
        B: ArrayLike<Value = Hash>,
    {
        // check we actually have a hash in the MMR at this pos
        mmr.get_node_hash(pos)?.ok_or(MerkleProofError::HashNotFound(pos))?;
        let mmr_size = mmr.len()?;
        let family_branch = family_branch(pos, mmr_size);

        // Construct a vector of sibling hashes from the candidate node's position to the local peak
        let path = family_branch
            .iter()
            .map(|(_, sibling)| {
                mmr.get_node_hash(*sibling)?
                    .ok_or(MerkleProofError::HashNotFound(*sibling))
            })
            .collect::<Result<_, _>>()?;

        let peak_pos = match family_branch.last() {
            Some(&(parent, _)) => parent,
            None => pos,
        };

        // Get the peaks of the merkle trees, which are bagged together to form the root
        // For the proof, we must leave out the local root for the candidate node
        let peaks = find_peaks(mmr_size).ok_or(MerkleMountainRangeError::InvalidMmrSize)?;
        let mut peak_hashes = Vec::with_capacity(peaks.len() - 1);
        for peak_index in peaks {
            if peak_index != peak_pos {
                let hash = mmr
                    .get_node_hash(peak_index)?
                    .ok_or(MerkleProofError::HashNotFound(peak_index))?
                    .clone();
                peak_hashes.push(hash);
            }
        }
        Ok(MerkleProof {
            mmr_size,
            path,
            peaks: peak_hashes,
        })
    }

    pub fn verify_leaf<D: Digest>(
        &self,
        root: &HashSlice,
        hash: &HashSlice,
        leaf_index: LeafIndex,
    ) -> Result<(), MerkleProofError> {
        let pos = node_index(leaf_index);
        self.verify::<D>(root, hash, pos)
    }

    /// Verifies the Merkle proof against the provided root hash, element and position in the MMR.
    pub fn verify<D: Digest>(&self, root: &HashSlice, hash: &HashSlice, pos: usize) -> Result<(), MerkleProofError> {
        let mut proof = self.clone();
        // calculate the peaks once as these are based on overall MMR size (and will not change)
        let peaks = find_peaks(self.mmr_size).ok_or(MerkleMountainRangeError::InvalidMmrSize)?;
        proof.verify_consume::<D>(root, hash, pos, &peaks)
    }

    /// Calculate a merkle root from the given hash, its peak position, and the peak hashes given with the proof
    /// Because of how the proofs are generated, the peak hashes given in the proof will always be an array one
    /// shorter then the canonical peak list for an MMR of a given size. e.g.: For an MMR of size 10:
    /// ```text
    ///       6
    ///    2     5    9
    ///   0 1   3 4  7 8
    /// ```
    /// The peak list is (6,9). But if we have an inclusion proof for say, 3, then we'll calculate 6 from the sibling
    /// data, therefore the proof only needs to provide 9.
    ///
    /// After running [verify_consume], we'll know the hash of 6 and it's position (the local root), and so we'll also
    /// know where to insert the hash in the peak list.
    fn check_root<D: Digest>(&self, hash: &HashSlice, pos: usize, peaks: &[usize]) -> Result<Hash, MerkleProofError> {
        // The peak hash list provided in the proof does not include the local peak determined from the candidate
        // node, so len(peak) must be len(self.peaks) + 1.
        if peaks.len() != self.peaks.len() + 1 {
            return Err(MerkleProofError::IncorrectPeakMap);
        }
        let hasher = D::new();
        // We're going to hash the peaks together, but insert the provided hash in the correct position.
        let peak_hashes = self.peaks.iter();
        let (hasher, _) = peaks
            .iter()
            .fold((hasher, peak_hashes), |(hasher, mut peak_hashes), i| {
                if *i == pos {
                    (hasher.chain_update(hash), peak_hashes)
                } else {
                    let hash = peak_hashes.next().unwrap();
                    (hasher.chain_update(hash), peak_hashes)
                }
            });
        Ok(hasher.finalize().to_vec())
    }

    /// Consumes the Merkle proof while verifying it.
    /// This method works by walking up the sibling path given in the proof. Since the only info we're given in the
    /// proof are the sibling hashes and the size of the MMR, there are a lot of bit-twiddling checks to determine
    /// where we are in the MMR.
    ///
    /// This algorithm works as follows:
    /// First we calculate the "local root" of the MMR by getting to the root of the full binary tree indicated by
    /// `pos` and `self.mmr_size`.
    /// This is done by popping a sibling hash off `self.path`, figuring out if it's on the left or right branch,
    /// calculating the parent hash, and then calling `verify_consume` again using the parent hash and position.
    /// Once `self.path` is empty, we have the local root and position, this data is used to hash all the peaks
    /// together in `check_root` to calculate the final merkle root.
    fn verify_consume<D: Digest>(
        &mut self,
        root: &HashSlice,
        hash: &HashSlice,
        pos: usize,
        peaks: &[usize],
    ) -> Result<(), MerkleProofError> {
        // If path is empty, we've got the hash of a local peak, so now we need to hash all the peaks together to
        // calculate the merkle root
        if self.path.is_empty() {
            let calculated_root = self.check_root::<D>(hash, pos, peaks)?;
            return if root == calculated_root.as_slice() {
                Ok(())
            } else {
                Err(MerkleProofError::RootMismatch)
            };
        }

        let sibling = self.path.remove(0); // FIXME Compare perf vs using a VecDeque
        let (parent_pos, sibling_pos) = family(pos)?;
        if parent_pos > self.mmr_size {
            Err(MerkleProofError::Unexpected)
        } else {
            let parent = if is_left_sibling(sibling_pos) {
                hash_together::<D>(&sibling, hash)
            } else {
                hash_together::<D>(hash, &sibling)
            };
            self.verify_consume::<D>(root, &parent, parent_pos, peaks)
        }
    }
}

impl Display for MerkleProof {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        f.write_str(&format!("MMR Size: {}\n", self.mmr_size))?;
        f.write_str("Siblings:\n")?;
        self.path
            .iter()
            .enumerate()
            .fold(Ok(()), |_, (i, h)| f.write_str(&format!("{:3}: {}\n", i, h.to_hex())))?;
        f.write_str("Peaks:\n")?;
        self.peaks
            .iter()
            .enumerate()
            .fold(Ok(()), |_, (i, h)| f.write_str(&format!("{:3}: {}\n", i, h.to_hex())))?;
        Ok(())
    }
}