simplicity-lang 0.9.0

// SPDX-License-Identifier: CC0-1.0

//! # Merkle roots
//!
//! Tools for creating Merkle roots.
//! There exist different Merkle roots for commitment and for redemption.

mod midstate;

pub mod amr;
pub mod cmr;
pub mod ihr;
pub mod tmr;

use self::midstate::MidstateExt;
use crate::bit_encoding::BitCollector;
use crate::Value;
use hashes::{sha256, HashEngine};
use std::fmt;

/// Trait for types that have a Commitment Merkle Root.
pub trait HasCmr {
    /// Access the Commitment Merkle Root.
    fn cmr(&self) -> cmr::Cmr;
}

/// 512-bit opaque blob of data used to seed `Fail` nodes
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
pub struct FailEntropy([u8; 64]);

impl FailEntropy {
    /// The all-zeroes entropy
    pub const ZERO: Self = FailEntropy([0; 64]);

    /// Construct a [`FailEntropy`] from raw data
    pub const fn from_byte_array(data: [u8; 64]) -> Self {
        FailEntropy(data)
    }

    /// Extract the raw bytes from a [`FailEntropy`].
    pub const fn to_byte_array(self) -> [u8; 64] {
        self.0
    }
}

impl fmt::Display for FailEntropy {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(&hex::DisplayHex::as_hex(&self.0[..]), f)
    }
}

impl AsRef<[u8]> for FailEntropy {
    fn as_ref(&self) -> &[u8] {
        self.0.as_ref()
    }
}

/// Helper function to compute the "compact value", i.e. the sha256 hash
/// of the bits of a given value, which is used in some IHRs and AMRs.
fn compact_value(value: &Value) -> [u8; 32] {
    let (mut bytes, bit_length) = value.iter_compact().collect_bits();

    // TODO: Automate hashing once `hashes` supports bit-wise hashing
    // 1.1 Append single '1' bit
    if bit_length % 8 == 0 {
        bytes.push(0x80);
    } else {
        let delimiter_index = bit_length % 8;
        *bytes.last_mut().unwrap() |= 1 << (7 - delimiter_index);
    }

    // 1.2 Append k '0x00' bytes, where k is minimum number >= 0 such that bytes.len() + k + 8 is multiple of 64
    let k = if bytes.len() % 64 > 56 {
        // Not enough space for 64-bit integer
        // Pad with zeroes until next block is 64 bits short of completion
        56 + (64 - (bytes.len() % 64))
    } else {
        // Pad with zeroes until current block is 64 bits short of completion
        56 - (bytes.len() % 64)
    };
    bytes.resize(bytes.len() + k, 0x00);
    debug_assert!(bytes.len() % 64 == 56);

    // 1.3 Append bit_length as 64-bit bit-endian integer
    let bit_length_bytes = (bit_length as u64).to_be_bytes();
    bytes.extend(bit_length_bytes.iter());
    debug_assert!(bytes.len() % 16 == 0);

    // 1.4 Compute hash of `value` normally since bytes.len() is multiple of 64
    let mut consumed = 0;
    let mut engine = sha256::HashEngine::default();
    while consumed < bytes.len() {
        engine.input(&bytes[consumed..(consumed + 16)]);
        consumed += 16;
    }
    debug_assert!(consumed == bytes.len());
    engine
        .midstate()
        .expect("hash input length was a multiple of 64")
        .to_parts()
        .0
}

/// Helper function to concatenate two 32-byte arrays into one 64-byte one.
#[inline]
fn concat<MR: AsRef<[u8]>>(mr1: MR, mr2: MR) -> [u8; 64] {
    core::array::from_fn(|i| {
        if i < 32 {
            mr1.as_ref()[i]
        } else {
            mr2.as_ref()[i - 32]
        }
    })
}

const fn bip340_iv(tag: &[u8]) -> sha256::Midstate {
    sha256::Midstate::hash_tag(tag)
}

/// Convenience macro for wrappers of `[u8; 32]`.
///
/// Implements `From` to and from `[u8; 32]`,
/// `MerkleRoot`, `AsRef<[u8]>`, `Debug` and `Display`
macro_rules! impl_mr_type {
    {
        $(#[$($struct_attr:tt)*])*
        pub struct $wrapper:ident([u8; 32]);
    } => {
        $(#[$($struct_attr)*])*
        pub struct $wrapper([u8; 32]);

        impl AsRef<[u8]> for $wrapper {
            fn as_ref(&self) -> &[u8] {
                self.0.as_ref()
            }
        }

        impl std::fmt::Debug for $wrapper {
            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                std::fmt::Display::fmt(&hex::DisplayHex::as_hex(self.as_ref()), f)
            }
        }

        impl std::fmt::Display for $wrapper {
            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                std::fmt::Debug::fmt(self, f)
            }
        }

        impl std::str::FromStr for $wrapper {
            type Err = hex::error::DecodeFixedLengthBytesError;

            fn from_str(s: &str) -> Result<Self, Self::Err> {
                let x: [u8; 32] = hex::decode_to_array(s)?;
                Ok($wrapper(x))
            }
        }

        impl $wrapper {
            /// Converts the given tagged hash into a byte array
            pub const fn from_byte_array(data: [u8; 32]) -> Self {
                $wrapper(data)
            }

            /// Converts the given tagged hash into a byte array
            pub const fn to_byte_array(self) -> [u8; 32] {
                self.0
            }

            /// Converts the given tagged hash into a byte array
            pub const fn as_byte_array(&self) -> &[u8; 32] {
                &self.0
            }
        }

        impl_serde_string!($wrapper);
    };
}
use impl_mr_type;