darkfi/blockchain/monero/
utils.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2026 Dyne.org foundation
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as
7 * published by the Free Software Foundation, either version 3 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
17 */
18
19use monero::{Hash, VarInt};
20use primitive_types::U256;
21use sha2::{Digest, Sha256};
22
23use super::{MerkleProof, MerkleTreeParameters, MoneroPowData};
24use crate::{blockchain::HeaderHash, Error, Result};
25
26/// Returns the Keccak 256 hash of the byte input
27pub fn cn_fast_hash(data: &[u8]) -> Hash {
28    Hash::new(data)
29}
30
31/// Returns the Keccak 256 hash of 2 hashes
32pub fn cn_fast_hash2(hash1: &Hash, hash2: &Hash) -> Hash {
33    let mut tmp = [0u8; 64];
34    tmp[..32].copy_from_slice(hash1.as_bytes());
35    tmp[32..].copy_from_slice(hash2.as_bytes());
36    cn_fast_hash(&tmp)
37}
38
39/// Round down to power of two.
40/// Should error for count < 3 or if the count is unreasonably large
41/// for tree hash calculations.
42#[allow(unused)]
43fn tree_hash_count(count: usize) -> Result<usize> {
44    if count < 3 {
45        return Err(Error::MoneroHashingError(format!(
46            "Cannot calculate tree hash root. Expected count to be >3 but got {count}"
47        )));
48    }
49
50    if count > 0x10000000 {
51        return Err(Error::MoneroHashingError(format!(
52            "Cannot calculate tree hash root. Expected count to be less than 0x10000000 but got {count}"
53        )));
54    }
55
56    // Essentially we are doing 1 << floor(log2(count))
57    let mut pow: usize = 2;
58    while pow < count {
59        pow <<= 1;
60    }
61
62    Ok(pow >> 1)
63}
64
65/// Tree hash algorithm in Monero
66#[allow(unused)]
67pub fn tree_hash(hashes: &[Hash]) -> Result<Hash> {
68    if hashes.is_empty() {
69        return Err(Error::MoneroHashingError(
70            "Cannot calculate Merkle root, no hashes".to_string(),
71        ));
72    }
73
74    match hashes.len() {
75        1 => Ok(hashes[0]),
76        2 => Ok(cn_fast_hash2(&hashes[0], &hashes[1])),
77        n => {
78            let mut cnt = tree_hash_count(n)?;
79            let mut buf = vec![Hash::null(); cnt];
80
81            // c is the number of elements between the number of hashes
82            // and the next power of 2.
83            let c = 2 * cnt - hashes.len();
84
85            buf[..c].copy_from_slice(&hashes[..c]);
86
87            // hash the rest of the hashes together
88            let mut i: usize = c;
89            for b in &mut buf[c..cnt] {
90                *b = cn_fast_hash2(&hashes[i], &hashes[i + 1]);
91                i += 2;
92            }
93
94            if i != hashes.len() {
95                return Err(Error::MoneroHashingError(
96                    "Cannot calculate the Merkle root, hashes not equal to count".to_string(),
97                ));
98            }
99
100            while cnt > 2 {
101                cnt >>= 1;
102                let mut i = 0;
103                for j in 0..cnt {
104                    buf[j] = cn_fast_hash2(&buf[i], &buf[i + 1]);
105                    i += 2;
106                }
107            }
108
109            Ok(cn_fast_hash2(&buf[0], &buf[1]))
110        }
111    }
112}
113
114/// Creates a Merkle proof for the given hash within the set of hashes.
115/// This function returns None if the hash is not in hashes.
116/// This is a port of Monero's tree_branch function.
117#[allow(clippy::cognitive_complexity)]
118#[allow(unused)]
119pub fn create_merkle_proof(hashes: &[Hash], hash: &Hash) -> Option<MerkleProof> {
120    match hashes.len() {
121        0 => None,
122        1 => {
123            if hashes[0] != *hash {
124                return None;
125            }
126            MerkleProof::try_construct(vec![], 0)
127        }
128        2 => hashes.iter().enumerate().find_map(|(pos, h)| {
129            if h != hash {
130                return None
131            }
132            let i = usize::from(pos == 0);
133            MerkleProof::try_construct(vec![hashes[i]], u32::from(pos != 0))
134        }),
135        len => {
136            let mut idx = hashes.iter().position(|node| node == hash)?;
137            let mut count = tree_hash_count(len).ok()?;
138
139            let mut ints = vec![Hash::null(); count];
140
141            let c = 2 * count - len;
142            ints[..c].copy_from_slice(&hashes[..c]);
143
144            let mut branch = vec![];
145            let mut path = 0u32;
146            let mut i = c;
147            for (j, val) in ints.iter_mut().enumerate().take(count).skip(c) {
148                // Left or right
149                if idx == i || idx == i + 1 {
150                    let ii = if idx == i { i + 1 } else { i };
151                    branch.push(hashes[ii]);
152                    path = (path << 1) | u32::from(idx != i);
153                    idx = j;
154                }
155                *val = cn_fast_hash2(&hashes[i], &hashes[i + 1]);
156                i += 2;
157            }
158
159            debug_assert_eq!(i, len);
160
161            while count > 2 {
162                count >>= 1;
163                let mut i = 0;
164                for j in 0..count {
165                    if idx == i || idx == i + 1 {
166                        let ii = if idx == i { i + 1 } else { i };
167                        branch.push(ints[ii]);
168                        path = (path << 1) | u32::from(idx != i);
169                        idx = j;
170                    }
171                    ints[j] = cn_fast_hash2(&ints[i], &ints[i + 1]);
172                    i += 2;
173                }
174            }
175
176            if idx == 0 || idx == 1 {
177                let ii = usize::from(idx == 0);
178                branch.push(ints[ii]);
179                path = (path << 1) | u32::from(idx != 0);
180            }
181
182            MerkleProof::try_construct(branch, path)
183        }
184    }
185}
186
187/// Creates a hex-encoded Monero blockhashing_blob
188pub fn create_blockhashing_blob(
189    header: &monero::BlockHeader,
190    merkle_root: &monero::Hash,
191    transaction_count: u64,
192) -> Vec<u8> {
193    let mut blockhashing_blob = monero::consensus::serialize(header);
194    blockhashing_blob.extend_from_slice(merkle_root.as_bytes());
195    let mut count = monero::consensus::serialize(&VarInt(transaction_count));
196    blockhashing_blob.append(&mut count);
197    blockhashing_blob
198}
199
200#[allow(unused)]
201fn check_aux_chains(
202    monero_data: &MoneroPowData,
203    merge_mining_params: VarInt,
204    aux_chain_merkle_root: &monero::Hash,
205    darkfi_hash: HeaderHash,
206    darkfi_genesis_hash: HeaderHash,
207) -> bool {
208    let df_hash = monero::Hash::from_slice(darkfi_hash.as_slice());
209
210    if merge_mining_params == VarInt(0) {
211        // Interpret 0 as only 1 chain
212        if df_hash == *aux_chain_merkle_root {
213            return true
214        }
215    }
216
217    let merkle_tree_params = MerkleTreeParameters::from_varint(merge_mining_params);
218    if merkle_tree_params.number_of_chains() == 0 {
219        return false
220    }
221
222    let hash_position = U256::from_little_endian(
223        &Sha256::new()
224            .chain_update(darkfi_genesis_hash.as_slice())
225            .chain_update(merkle_tree_params.aux_nonce().to_le_bytes())
226            .chain_update((109_u8).to_le_bytes())
227            .finalize(),
228    )
229    .low_u32() %
230        u32::from(merkle_tree_params.number_of_chains());
231
232    let (merkle_root, pos) = monero_data
233        .aux_chain_merkle_proof
234        .calculate_root_with_pos(&df_hash, merkle_tree_params.number_of_chains());
235
236    if hash_position != pos {
237        return false
238    }
239
240    merkle_root == *aux_chain_merkle_root
241}
darkfi/blockchain/monero/utils.rs

darkfi/blockchain/monero/
utils.rs
