subcoin_crypto/
muhash.rs

1//! https://github.com/bitcoin/bitcoin/blob/6f9db1ebcab4064065ccd787161bf2b87e03cc1f/test/functional/test_framework/crypto/muhash.py#L4
2
3use crate::chacha20_block;
4use num_bigint::{BigUint, ToBigUint};
5use num_traits::One;
6use sha2::{Digest, Sha256};
7use std::fmt::Write;
8
9// Function to hash a 32-byte array into a 3072-bit number using 6 ChaCha20 operations
10fn data_to_num3072(data: &[u8; 32]) -> BigUint {
11    let mut bytes384 = Vec::new();
12    for counter in 0..6 {
13        bytes384.extend(chacha20_block(data, &[0u8; 12], counter));
14    }
15    BigUint::from_bytes_le(&bytes384)
16}
17
18/// A class representing MuHash sets.
19///
20/// https://github.com/bitcoin/bitcoin/blob/6f9db1e/src/crypto/muhash.h#L61
21#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
22pub struct MuHash3072 {
23    numerator: BigUint,
24    denominator: BigUint,
25    modulus: BigUint,
26}
27
28impl Default for MuHash3072 {
29    fn default() -> Self {
30        Self::new()
31    }
32}
33
34impl MuHash3072 {
35    // Create a new [`MuHash3072`] with the appropriate modulus.
36    pub fn new() -> Self {
37        let modulus = (BigUint::one() << 3072) - 1103717u32.to_biguint().unwrap();
38        Self {
39            numerator: BigUint::one(),
40            denominator: BigUint::one(),
41            modulus,
42        }
43    }
44
45    // Insert a byte array into the set
46    pub fn insert(&mut self, data: &[u8]) {
47        let data_hash = Sha256::digest(data);
48        let num3072 = data_to_num3072(&data_hash.into());
49        self.numerator *= num3072;
50        self.numerator %= &self.modulus;
51    }
52
53    // Remove a byte array from the set
54    pub fn remove(&mut self, data: &[u8]) {
55        let data_hash = Sha256::digest(data);
56        let num3072 = data_to_num3072(&data_hash.into());
57        self.denominator *= num3072;
58        self.denominator %= &self.modulus;
59    }
60
61    // Compute the final digest
62    pub fn digest(&self) -> Vec<u8> {
63        let denominator_inv = self
64            .denominator
65            .modpow(&(self.modulus.clone() - 2u32), &self.modulus);
66        let val = (&self.numerator * denominator_inv) % &self.modulus;
67        let mut bytes384 = val.to_bytes_le();
68        bytes384.resize(384, 0); // Ensure it is exactly 384 bytes
69        Sha256::digest(&bytes384).to_vec()
70    }
71
72    /// Returns the value of `muhash` in Bitcoin Core's dumptxoutset output.
73    pub fn txoutset_muhash(&self) -> String {
74        let finalized = self.digest();
75
76        finalized.iter().rev().fold(String::new(), |mut output, b| {
77            let _ = write!(output, "{b:02x}");
78            output
79        })
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    // https://github.com/bitcoin/bitcoin/blob/6f9db1e/test/functional/test_framework/crypto/muhash.py#L48
88    #[test]
89    fn test_muhash() {
90        let mut muhash = MuHash3072::new();
91        muhash.insert(&[0x00; 32]);
92
93        // Insert 32 bytes, first byte 0x01, rest 0x00
94        let mut data = Vec::with_capacity(32);
95        data.push(0x01);
96        data.extend_from_slice(&[0x00; 31]);
97        muhash.insert(&data);
98
99        // Remove 32 bytes, first byte 0x02, rest 0x00
100        let mut data = Vec::with_capacity(32);
101        data.push(0x02);
102        data.extend_from_slice(&[0x00; 31]);
103        muhash.remove(&data);
104
105        let finalized = muhash.digest();
106        assert_eq!(
107            finalized
108                .iter()
109                .rev()
110                .map(|b| format!("{b:02x}"))
111                .collect::<String>(),
112            "10d312b100cbd32ada024a6646e40d3482fcff103668d2625f10002a607d5863"
113        );
114    }
115}