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

simplicity/merkle/
mod.rs
