simplicity/merkle/
mod.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! # Merkle roots
4//!
5//! Tools for creating Merkle roots.
6//! There exist different Merkle roots for commitment and for redemption.
7
8mod midstate;
9
10pub mod amr;
11pub mod cmr;
12pub mod ihr;
13pub mod tmr;
14
15use self::midstate::MidstateExt;
16use crate::bit_encoding::BitCollector;
17use crate::Value;
18use hashes::{sha256, HashEngine};
19use std::fmt;
20
21/// Trait for types that have a Commitment Merkle Root.
22pub trait HasCmr {
23    /// Access the Commitment Merkle Root.
24    fn cmr(&self) -> cmr::Cmr;
25}
26
27/// 512-bit opaque blob of data used to seed `Fail` nodes
28#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
29pub struct FailEntropy([u8; 64]);
30
31impl FailEntropy {
32    /// The all-zeroes entropy
33    pub const ZERO: Self = FailEntropy([0; 64]);
34
35    /// Construct a [`FailEntropy`] from raw data
36    pub const fn from_byte_array(data: [u8; 64]) -> Self {
37        FailEntropy(data)
38    }
39
40    /// Extract the raw bytes from a [`FailEntropy`].
41    pub const fn to_byte_array(self) -> [u8; 64] {
42        self.0
43    }
44}
45
46impl fmt::Display for FailEntropy {
47    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
48        fmt::Display::fmt(&hex::DisplayHex::as_hex(&self.0[..]), f)
49    }
50}
51
52impl AsRef<[u8]> for FailEntropy {
53    fn as_ref(&self) -> &[u8] {
54        self.0.as_ref()
55    }
56}
57
58/// Helper function to compute the "compact value", i.e. the sha256 hash
59/// of the bits of a given value, which is used in some IHRs and AMRs.
60fn compact_value(value: &Value) -> [u8; 32] {
61    let (mut bytes, bit_length) = value.iter_compact().collect_bits();
62
63    // TODO: Automate hashing once `hashes` supports bit-wise hashing
64    // 1.1 Append single '1' bit
65    if bit_length % 8 == 0 {
66        bytes.push(0x80);
67    } else {
68        let delimiter_index = bit_length % 8;
69        *bytes.last_mut().unwrap() |= 1 << (7 - delimiter_index);
70    }
71
72    // 1.2 Append k '0x00' bytes, where k is minimum number >= 0 such that bytes.len() + k + 8 is multiple of 64
73    let k = if bytes.len() % 64 > 56 {
74        // Not enough space for 64-bit integer
75        // Pad with zeroes until next block is 64 bits short of completion
76        56 + (64 - (bytes.len() % 64))
77    } else {
78        // Pad with zeroes until current block is 64 bits short of completion
79        56 - (bytes.len() % 64)
80    };
81    bytes.resize(bytes.len() + k, 0x00);
82    debug_assert!(bytes.len() % 64 == 56);
83
84    // 1.3 Append bit_length as 64-bit bit-endian integer
85    let bit_length_bytes = (bit_length as u64).to_be_bytes();
86    bytes.extend(bit_length_bytes.iter());
87    debug_assert!(bytes.len() % 16 == 0);
88
89    // 1.4 Compute hash of `value` normally since bytes.len() is multiple of 64
90    let mut consumed = 0;
91    let mut engine = sha256::HashEngine::default();
92    while consumed < bytes.len() {
93        engine.input(&bytes[consumed..(consumed + 16)]);
94        consumed += 16;
95    }
96    debug_assert!(consumed == bytes.len());
97    engine
98        .midstate()
99        .expect("hash input length was a multiple of 64")
100        .to_parts()
101        .0
102}
103
104/// Helper function to concatenate two 32-byte arrays into one 64-byte one.
105#[inline]
106fn concat<MR: AsRef<[u8]>>(mr1: MR, mr2: MR) -> [u8; 64] {
107    core::array::from_fn(|i| {
108        if i < 32 {
109            mr1.as_ref()[i]
110        } else {
111            mr2.as_ref()[i - 32]
112        }
113    })
114}
115
116const fn bip340_iv(tag: &[u8]) -> sha256::Midstate {
117    sha256::Midstate::hash_tag(tag)
118}
119
120/// Convenience macro for wrappers of `[u8; 32]`.
121///
122/// Implements `From` to and from `[u8; 32]`,
123/// `MerkleRoot`, `AsRef<[u8]>`, `Debug` and `Display`
124macro_rules! impl_mr_type {
125    {
126        $(#[$($struct_attr:tt)*])*
127        pub struct $wrapper:ident([u8; 32]);
128    } => {
129        $(#[$($struct_attr)*])*
130        pub struct $wrapper([u8; 32]);
131
132        impl AsRef<[u8]> for $wrapper {
133            fn as_ref(&self) -> &[u8] {
134                self.0.as_ref()
135            }
136        }
137
138        impl std::fmt::Debug for $wrapper {
139            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
140                std::fmt::Display::fmt(&hex::DisplayHex::as_hex(self.as_ref()), f)
141            }
142        }
143
144        impl std::fmt::Display for $wrapper {
145            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
146                std::fmt::Debug::fmt(self, f)
147            }
148        }
149
150        impl std::str::FromStr for $wrapper {
151            type Err = hex::error::DecodeFixedLengthBytesError;
152
153            fn from_str(s: &str) -> Result<Self, Self::Err> {
154                let x: [u8; 32] = hex::decode_to_array(s)?;
155                Ok($wrapper(x))
156            }
157        }
158
159        impl $wrapper {
160            /// Converts the given tagged hash into a byte array
161            pub const fn from_byte_array(data: [u8; 32]) -> Self {
162                $wrapper(data)
163            }
164
165            /// Converts the given tagged hash into a byte array
166            pub const fn to_byte_array(self) -> [u8; 32] {
167                self.0
168            }
169
170            /// Converts the given tagged hash into a byte array
171            pub const fn as_byte_array(&self) -> &[u8; 32] {
172                &self.0
173            }
174        }
175
176        impl_serde_string!($wrapper);
177    };
178}
179use impl_mr_type;
simplicity/merkle/mod.rs

simplicity/merkle/
mod.rs
