commit_verify 0.9.0

// LNP/BP client-side-validation foundation libraries implementing LNPBP
// specifications & standards (LNPBP-4, 7, 8, 9, 42, 81)
//
// Written in 2019-2022 by
//     Dr. Maxim Orlovsky <orlovsky@pandoracore.com>
//
// To the extent possible under law, the author(s) have dedicated all
// copyright and related and neighboring rights to this software to
// the public domain worldwide. This software is distributed without
// any warranty.
//
// You should have received a copy of the Apache 2.0 License along with this
// software. If not, see <https://opensource.org/licenses/Apache-2.0>.

//! Merklization procedures for client-side-validation according to [LNPBP-81]
//! standard.
//!
//! [LNPBP-81]: https://github.com/LNP-BP/LNPBPs/blob/master/lnpbp-0081.md

use std::io;

use bitcoin_hashes::{sha256, Hash, HashEngine};

use crate::{
    commit_encode, CommitEncode, CommitVerify, ConsensusCommit,
    PrehashedProtocol,
};

/// Marker trait for types that require merklization of the underlying data
/// during [`ConsensusCommit`] procedure. Allows specifying custom tag for the
/// tagged hash used in the merklization (see [`merklize`]).
pub trait ConsensusMerkleCommit:
    ConsensusCommit<Commitment = MerkleNode>
{
    /// The tag prefix which will be used in the merklization process (see
    /// [`merklize`])
    const MERKLE_NODE_PREFIX: &'static str;
}

hash_newtype!(
    MerkleNode,
    sha256::Hash,
    32,
    doc = "A hash type for LNPBP-81 Merkle tree leaves, branches and root",
    false // We do not reverse displaying MerkleNodes in hexadecimal
);

impl strict_encoding::Strategy for MerkleNode {
    type Strategy = strict_encoding::strategies::HashFixedBytes;
}

impl commit_encode::Strategy for MerkleNode {
    type Strategy = commit_encode::strategies::UsingStrict;
}

impl<Msg> CommitVerify<Msg, PrehashedProtocol> for MerkleNode
where
    Msg: AsRef<[u8]>,
{
    #[inline]
    fn commit(msg: &Msg) -> MerkleNode { MerkleNode::hash(msg.as_ref()) }
}

impl<A, B> ConsensusCommit for (A, B)
where
    A: CommitEncode,
    B: CommitEncode,
{
    type Commitment = MerkleNode;
}

impl<A, B, C> ConsensusCommit for (A, B, C)
where
    A: CommitEncode,
    B: CommitEncode,
    C: CommitEncode,
{
    type Commitment = MerkleNode;
}

/// Merklization procedure that uses tagged hashes with depth commitments
/// according to [LNPBP-81] standard of client-side-validation merklization
///
/// [LNPBP-81]: https://github.com/LNP-BP/LNPBPs/blob/master/lnpbp-0081.md
pub fn merklize<I>(prefix: &str, data: I) -> (MerkleNode, u8)
where
    I: IntoIterator<Item = MerkleNode>,
    <I as IntoIterator>::IntoIter: ExactSizeIterator<Item = MerkleNode>,
{
    let mut tag_engine = sha256::Hash::engine();
    tag_engine.input(prefix.as_bytes());
    tag_engine.input(":merkle:".as_bytes());

    let iter = data.into_iter();
    let width = iter.len();

    // Tagging merkle tree root
    let (root, height) = merklize_inner(&tag_engine, iter, 0, false, None);
    tag_engine.input("root:height=".as_bytes());
    tag_engine.input(&height.to_string().into_bytes());
    tag_engine.input(":width=".as_bytes());
    tag_engine.input(&width.to_string().into_bytes());
    let tag_hash = sha256::Hash::hash(&sha256::Hash::from_engine(tag_engine));
    let mut engine = MerkleNode::engine();
    engine.input(&tag_hash[..]);
    engine.input(&tag_hash[..]);
    root.commit_encode(&mut engine);
    let tagged_root = MerkleNode::from_engine(engine);

    (tagged_root, height)
}

// TODO: Optimize to avoid allocations
// In current rust generic iterators do not work with recursion :(
fn merklize_inner(
    engine_proto: &sha256::HashEngine,
    mut iter: impl ExactSizeIterator<Item = MerkleNode>,
    depth: u8,
    extend: bool,
    empty_node: Option<MerkleNode>,
) -> (MerkleNode, u8) {
    let len = iter.len() + extend as usize;
    let empty_node = empty_node.unwrap_or_else(|| MerkleNode::hash(&[0xFF]));

    // Computing tagged hash as per BIP-340
    let mut tag_engine = engine_proto.clone();
    tag_engine.input("depth=".as_bytes());
    tag_engine.input(depth.to_string().as_bytes());
    tag_engine.input(":width=".as_bytes());
    tag_engine.input(len.to_string().as_bytes());
    tag_engine.input(":height=".as_bytes());

    let mut engine = MerkleNode::engine();
    if len <= 2 {
        tag_engine.input("0:".as_bytes());
        let tag_hash =
            sha256::Hash::hash(&sha256::Hash::from_engine(tag_engine));
        engine.input(&tag_hash[..]);
        engine.input(&tag_hash[..]);

        let mut leaf_tag_engine = engine_proto.clone();
        leaf_tag_engine.input("leaf".as_bytes());
        let leaf_tag =
            sha256::Hash::hash(&sha256::Hash::from_engine(leaf_tag_engine));
        let mut leaf_engine = MerkleNode::engine();
        leaf_engine.input(&leaf_tag[..]);
        leaf_engine.input(&leaf_tag[..]);

        let mut leaf1 = leaf_engine.clone();
        leaf1.input(
            iter.next()
                .as_ref()
                .map(|d| d.as_ref())
                .unwrap_or_else(|| empty_node.as_ref()),
        );
        MerkleNode::from_engine(leaf1).commit_encode(&mut engine);

        leaf_engine.input(
            iter.next()
                .as_ref()
                .map(|d| d.as_ref())
                .unwrap_or_else(|| empty_node.as_ref()),
        );
        MerkleNode::from_engine(leaf_engine).commit_encode(&mut engine);

        (MerkleNode::from_engine(engine), 1)
    } else {
        let div = len / 2 + len % 2;

        let (node1, height1) = merklize_inner(
            engine_proto,
            // Normally we should use `iter.by_ref().take(div)`, but currently
            // rust compilers is unable to parse recursion with generic types
            iter.by_ref().take(div).collect::<Vec<_>>().into_iter(),
            depth + 1,
            false,
            Some(empty_node),
        );

        let iter = if extend {
            iter.chain(vec![empty_node]).collect::<Vec<_>>().into_iter()
        } else {
            iter.collect::<Vec<_>>().into_iter()
        };

        let (node2, height2) = merklize_inner(
            engine_proto,
            iter,
            depth + 1,
            (div % 2 + len % 2) / 2 == 1,
            Some(empty_node),
        );

        assert_eq!(
            height1,
            height2,
            "merklization algorithm failure: height of subtrees is not equal \
             (width = {}, depth = {}, prev_extend = {}, next_extend = {})",
            len,
            depth,
            extend,
            div % 2 == 1 && len % 2 == 1
        );

        tag_engine.input(height1.to_string().as_bytes());
        tag_engine.input(":".as_bytes());
        let tag_hash =
            sha256::Hash::hash(&sha256::Hash::from_engine(tag_engine));
        engine.input(&tag_hash[..]);
        engine.input(&tag_hash[..]);
        node1.commit_encode(&mut engine);
        node2.commit_encode(&mut engine);

        (MerkleNode::from_engine(engine), height1 + 1)
    }
}

/// The source data for the [LNPBP-81] merklization process.
///
/// [LNPBP-81]: https://github.com/LNP-BP/LNPBPs/blob/master/lnpbp-0081.md
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
pub struct MerkleSource<T>(
    /// Array of the data which will be merklized
    pub Vec<T>,
);

impl<L, I> From<I> for MerkleSource<L>
where
    I: IntoIterator<Item = L>,
    L: CommitEncode,
{
    fn from(collection: I) -> Self { Self(collection.into_iter().collect()) }
}

impl<L> FromIterator<L> for MerkleSource<L>
where
    L: CommitEncode,
{
    fn from_iter<T: IntoIterator<Item = L>>(iter: T) -> Self {
        iter.into_iter().collect::<Vec<_>>().into()
    }
}

impl<L> CommitEncode for MerkleSource<L>
where
    L: ConsensusMerkleCommit,
{
    fn commit_encode<E: io::Write>(&self, e: E) -> usize {
        let leafs = self.0.iter().map(L::consensus_commit);
        merklize(L::MERKLE_NODE_PREFIX, leafs).0.commit_encode(e)
    }
}

impl<L> ConsensusCommit for MerkleSource<L>
where
    L: ConsensusMerkleCommit + CommitEncode,
{
    type Commitment = MerkleNode;

    #[inline]
    fn consensus_commit(&self) -> Self::Commitment {
        MerkleNode::from_slice(&self.commit_serialize())
            .expect("MerkleSource::commit_serialize must produce MerkleNode")
    }

    #[inline]
    fn consensus_verify(&self, commitment: &Self::Commitment) -> bool {
        self.consensus_commit() == *commitment
    }
}

/// Converts given piece of client-side-validated data into a structure which
/// can be used in merklization process.
///
/// This dedicated structure is required since with
/// `impl From<_> for MerkleSource` we would not be able to specify a concrete
/// tagged hash, which we require in [LNPBP-81] merklization and which we
/// provide here via [`ToMerkleSource::Leaf`]` associated type holding
/// [`ConsensusMerkleCommit::MERKLE_NODE_PREFIX`] prefix value.
///
/// [LNPBP-81]: https://github.com/LNP-BP/LNPBPs/blob/master/lnpbp-0081.md
pub trait ToMerkleSource {
    /// Defining type of the commitment produced during merlization process
    type Leaf: ConsensusMerkleCommit;

    /// Performs transformation of the data type into a merkilzable data
    fn to_merkle_source(&self) -> MerkleSource<Self::Leaf>;
}

#[cfg(test)]
mod test {
    use std::collections::BTreeMap;

    use amplify::{bmap, s};
    use bitcoin_hashes::hex::ToHex;
    use bitcoin_hashes::{sha256d, Hash};
    use strict_encoding::{StrictDecode, StrictEncode};

    use super::*;
    use crate::commit_encode::{strategies, Strategy};
    use crate::CommitConceal;

    #[test]
    fn collections() {
        // First, we define a data type
        #[derive(
            Clone,
            PartialEq,
            Eq,
            PartialOrd,
            Ord,
            Hash,
            Debug,
            StrictEncode,
            StrictDecode
        )]
        struct Item(pub String);
        // Next, we say that it should be concealed using some function
        // (double SHA256 hash in this case)
        impl CommitConceal for Item {
            type ConcealedCommitment = sha256d::Hash;
            fn commit_conceal(&self) -> Self::ConcealedCommitment {
                sha256d::Hash::hash(self.0.as_bytes())
            }
        }
        // Next, we need to specify how the concealed data should be
        // commit-encoded: this time we strict-serialize the hash
        impl Strategy for sha256d::Hash {
            type Strategy = strategies::UsingStrict;
        }
        // Now, we define commitment encoding for our concealable type: it
        // should conceal the data
        impl Strategy for Item {
            type Strategy = strategies::UsingConceal;
        }
        // Now, we need to say that consensus commit procedure should produce
        // a final commitment from commit-encoded data (equal to the
        // strict encoding of the conceal result) using `CommitVerify` type.
        // Here, we use another round of hashing, producing merkle node hash
        // from the concealed data.
        impl ConsensusCommit for Item {
            type Commitment = MerkleNode;
        }
        // Next, we need to provide merkle node tags for each type of the tree
        impl ConsensusMerkleCommit for Item {
            const MERKLE_NODE_PREFIX: &'static str = "item";
        }
        impl ConsensusMerkleCommit for (usize, Item) {
            const MERKLE_NODE_PREFIX: &'static str = "usize->item";
        }

        impl ToMerkleSource for BTreeMap<usize, Item> {
            type Leaf = (usize, Item);
            fn to_merkle_source(&self) -> MerkleSource<Self::Leaf> {
                self.iter().map(|(k, v)| (*k, v.clone())).collect()
            }
        }

        let large = vec![Item(s!("none")); 3];
        let vec: MerkleSource<Item> = large.into();
        assert_eq!(
            vec.commit_serialize().to_hex(),
            "71ea45868fbd924061c4deb84f37ed82b0ac808de12aa7659afda7d9303e7a71"
        );

        let large = vec![Item(s!("none")); 5];
        let vec: MerkleSource<Item> = large.into();
        assert_eq!(
            vec.commit_serialize().to_hex(),
            "e255e0124efe0555fde0d932a0bc0042614129e1a02f7b8c0bf608b81af3eb94"
        );

        let large = vec![Item(s!("none")); 9];
        let vec: MerkleSource<Item> = large.into();
        assert_eq!(
            vec.commit_serialize().to_hex(),
            "6cd2d5345a654af4720bdcc637183ded8e432dc88f778b7d27c8d5a0e342c65f"
        );

        let large = vec![Item(s!("none")); 13];
        let vec: MerkleSource<Item> = large.into();
        assert_eq!(
            vec.commit_serialize().to_hex(),
            "3714c08c7c94a4ef769ad2cb7df9aaca1e1252d6599a02aff281c37e7242797d"
        );

        let large = vec![Item(s!("none")); 17];
        let vec: MerkleSource<Item> = large.into();
        assert_eq!(
            vec.commit_serialize().to_hex(),
            "6093dec47e5bdd706da01e4479cb65632eac426eb59c8c28c4e6c199438c8b6f"
        );

        let item = Item(s!("Some text"));
        assert_eq!(&b"\x09\x00Some text"[..], item.strict_serialize().unwrap());
        assert_eq!(
            "6680bbec0d05d3eaac9c8b658c40f28d2f0cb0f245c7b1cabf5a61c35bd03d8e",
            item.commit_serialize().to_hex()
        );
        assert_eq!(
            "3e4b2dcf9bca33400028c8947565c1ff421f6d561e9ec48f88f0c9a24ebc8c30",
            item.consensus_commit().to_hex()
        );
        assert_ne!(item.commit_serialize(), item.strict_serialize().unwrap());
        assert_eq!(
            MerkleNode::hash(&item.commit_serialize()),
            item.consensus_commit()
        );

        let original = bmap! {
            0usize => Item(s!("My first case")),
            1usize => Item(s!("My second case with a very long string")),
            3usize => Item(s!("My third case to make the Merkle tree two layered"))
        };
        let collection = original.to_merkle_source();
        assert_eq!(
            &b"\x03\x00\
             \x00\x00\
             \x0d\x00\
             My first case\
             \x01\x00\
             \x26\x00\
             My second case with a very long string\
             \x03\x00\
             \x31\x00\
             My third case to make the Merkle tree two layered"[..],
            original.strict_serialize().unwrap()
        );
        assert_eq!(
            "d911717b8dfbbcef68495c93c0a5e69df618f5dcc194d69e80b6fafbfcd6ed5d",
            collection.commit_serialize().to_hex()
        );
        assert_eq!(
            "d911717b8dfbbcef68495c93c0a5e69df618f5dcc194d69e80b6fafbfcd6ed5d",
            collection.consensus_commit().to_hex()
        );
        assert_ne!(
            collection.commit_serialize(),
            original.strict_serialize().unwrap()
        );
        assert_eq!(
            MerkleNode::from_slice(&collection.commit_serialize()).unwrap(),
            collection.consensus_commit()
        );

        let original = vec![
            Item(s!("My first case")),
            Item(s!("My second case with a very long string")),
            Item(s!("My third case to make the Merkle tree two layered")),
        ];
        let vec: MerkleSource<Item> = original.clone().into();
        assert_eq!(
            &b"\x03\x00\
             \x0d\x00\
             My first case\
             \x26\x00\
             My second case with a very long string\
             \x31\x00\
             My third case to make the Merkle tree two layered"[..],
            original.strict_serialize().unwrap()
        );
        assert_eq!(
            "fd72061e26055fb907aa512a591b4291e739f15198eb72027c4dd6506f14f469",
            vec.commit_serialize().to_hex()
        );
        assert_eq!(
            "fd72061e26055fb907aa512a591b4291e739f15198eb72027c4dd6506f14f469",
            vec.consensus_commit().to_hex()
        );
        assert_ne!(
            vec.commit_serialize(),
            original.strict_serialize().unwrap()
        );
        assert_eq!(
            MerkleNode::from_slice(&vec.commit_serialize()).unwrap(),
            vec.consensus_commit()
        );
        assert_ne!(vec.consensus_commit(), collection.consensus_commit());
    }
}