darkfi/blockchain/monero/
merkle_proof.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 std::io::{self, Cursor, Error, Read, Write};
20
21#[cfg(feature = "async-serial")]
22use darkfi_serial::{
23    async_trait, AsyncDecodable, AsyncEncodable, AsyncRead, AsyncReadExt, AsyncWrite,
24};
25use darkfi_serial::{Decodable, Encodable, ReadExt};
26use monero::{
27    consensus::{Decodable as XmrDecodable, Encodable as XmrEncodable},
28    Hash,
29};
30
31use super::utils::cn_fast_hash2;
32
33const MAX_MERKLE_TREE_PROOF_SIZE: usize = 32;
34
35/// The Monero Merkle proof
36#[derive(Debug, Clone)]
37pub struct MerkleProof {
38    branch: Vec<Hash>,
39    path_bitmap: u32,
40}
41
42impl Encodable for MerkleProof {
43    fn encode<S: Write>(&self, s: &mut S) -> io::Result<usize> {
44        let mut n = 0;
45
46        let len = self.branch.len() as u8;
47        n += len.encode(s)?;
48
49        for hash in &self.branch {
50            n += (*hash).consensus_encode(s)?;
51        }
52
53        n += self.path_bitmap.encode(s)?;
54
55        Ok(n)
56    }
57}
58
59#[cfg(feature = "async-serial")]
60#[async_trait]
61impl AsyncEncodable for MerkleProof {
62    async fn encode_async<S: AsyncWrite + Unpin + Send>(&self, s: &mut S) -> io::Result<usize> {
63        let mut n = 0;
64
65        let len = self.branch.len() as u8;
66        n += len.encode_async(s).await?;
67
68        for hash in &self.branch {
69            let mut buf = [0u8; 32];
70            (*hash).consensus_encode(&mut &mut buf[..])?;
71            n += buf.encode_async(s).await?;
72        }
73
74        n += self.path_bitmap.encode_async(s).await?;
75
76        Ok(n)
77    }
78}
79
80impl Decodable for MerkleProof {
81    fn decode<D: Read>(d: &mut D) -> io::Result<Self> {
82        let len: u8 = d.read_u8()?;
83        let mut branch = Vec::with_capacity(len as usize);
84
85        for _ in 0..len {
86            branch.push(Hash::consensus_decode(d).map_err(|_| Error::other("Invalid XMR hash"))?);
87        }
88
89        let path_bitmap: u32 = Decodable::decode(d)?;
90
91        Ok(Self { branch, path_bitmap })
92    }
93}
94
95#[cfg(feature = "async-serial")]
96#[async_trait]
97impl AsyncDecodable for MerkleProof {
98    async fn decode_async<D: AsyncRead + Unpin + Send>(d: &mut D) -> io::Result<Self> {
99        let len: u8 = d.read_u8_async().await?;
100        let mut branch = Vec::with_capacity(len as usize);
101
102        for _ in 0..len {
103            let buf: [u8; 32] = AsyncDecodable::decode_async(d).await?;
104            let mut buf = Cursor::new(buf);
105            branch.push(
106                Hash::consensus_decode(&mut buf).map_err(|_| Error::other("Invalid XMR hash"))?,
107            );
108        }
109
110        let path_bitmap: u32 = AsyncDecodable::decode_async(d).await?;
111
112        Ok(Self { branch, path_bitmap })
113    }
114}
115
116impl MerkleProof {
117    pub fn try_construct(branch: Vec<Hash>, path_bitmap: u32) -> Option<Self> {
118        if branch.len() >= MAX_MERKLE_TREE_PROOF_SIZE {
119            return None
120        }
121
122        Some(Self { branch, path_bitmap })
123    }
124
125    /// Returns the Merkle proof branch as a list of Monero hashes
126    #[inline]
127    pub fn branch(&self) -> &[Hash] {
128        &self.branch
129    }
130
131    /// Returns the path bitmap of the proof
132    pub fn path(&self) -> u32 {
133        self.path_bitmap
134    }
135
136    /// The coinbase must be the first transaction in the block, so
137    /// that you can't have multiple coinbases in a block. That means
138    /// the coinbase is always the leftmost branch in the Merkle tree.
139    /// This tests that the given proof is for the leftmost branch in
140    /// the Merkle tree.
141    pub fn check_coinbase_path(&self) -> bool {
142        if self.path_bitmap == 0b00000000 {
143            return true;
144        }
145        false
146    }
147
148    /// Calculates the Merkle root hash from the provided Monero hash
149    pub fn calculate_root_with_pos(&self, hash: &Hash, aux_chain_count: u8) -> (Hash, u32) {
150        let root = self.calculate_root(hash);
151        let pos = self.get_position_from_path(u32::from(aux_chain_count));
152        (root, pos)
153    }
154
155    pub fn calculate_root(&self, hash: &Hash) -> Hash {
156        if self.branch.is_empty() {
157            return *hash;
158        }
159
160        let mut root = *hash;
161        let depth = self.branch.len();
162        for d in 0..depth {
163            if (self.path_bitmap >> (depth - d - 1)) & 1 > 0 {
164                root = cn_fast_hash2(&self.branch[d], &root);
165            } else {
166                root = cn_fast_hash2(&root, &self.branch[d]);
167            }
168        }
169
170        root
171    }
172
173    pub fn get_position_from_path(&self, aux_chain_count: u32) -> u32 {
174        if aux_chain_count <= 1 {
175            return 0
176        }
177
178        let mut depth = 0;
179        let mut k = 1;
180
181        while k < aux_chain_count {
182            depth += 1;
183            k <<= 1;
184        }
185
186        k -= aux_chain_count;
187
188        let mut pos = 0;
189        let mut path = self.path_bitmap;
190
191        for _i in 1..depth {
192            pos = (pos << 1) | (path & 1);
193            path >>= 1;
194        }
195
196        if pos < k {
197            return pos
198        }
199
200        (((pos - k) << 1) | (path & 1)) + k
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use rand::RngCore;
207    use std::{iter, str::FromStr};
208
209    use super::{
210        super::utils::{create_merkle_proof, tree_hash},
211        *,
212    };
213
214    #[test]
215    fn test_empty_hashset_has_no_proof() {
216        assert!(create_merkle_proof(&[], &Hash::null()).is_none());
217    }
218
219    #[test]
220    fn test_single_hash_is_its_own_proof() {
221        let tx_hashes =
222            &[Hash::from_str("fa58575f7d1d377709f1621fac98c758860ca6dc5f2262be9ce5fd131c370d1a")
223                .unwrap()];
224        let proof = create_merkle_proof(&tx_hashes[..], &tx_hashes[0]).unwrap();
225        assert_eq!(proof.branch.len(), 0);
226        assert_eq!(proof.calculate_root(&tx_hashes[0]), tx_hashes[0]);
227
228        assert!(create_merkle_proof(&tx_hashes[..], &Hash::null()).is_none());
229    }
230
231    #[test]
232    fn test_two_hash_proof_construction() {
233        let tx_hashes = &[
234            "d96756959949db23764592fea0bfe88c790e1fd131dabb676948b343aa9ecc24",
235            "77d1a87df131c36da4832a7ec382db9b8fe947576a60ec82cc1c66a220f6ee42",
236        ]
237        .iter()
238        .map(|hash| Hash::from_str(hash).unwrap())
239        .collect::<Vec<_>>();
240
241        let expected_root = cn_fast_hash2(&tx_hashes[0], &tx_hashes[1]);
242        let proof = create_merkle_proof(tx_hashes, &tx_hashes[0]).unwrap();
243        assert_eq!(proof.branch()[0], tx_hashes[1]);
244        assert_eq!(proof.branch.len(), 1);
245        assert_eq!(proof.branch[0], tx_hashes[1]);
246        assert_eq!(proof.path_bitmap, 0b00000000);
247        assert_eq!(proof.calculate_root(&tx_hashes[0]), expected_root);
248
249        let proof = create_merkle_proof(tx_hashes, &tx_hashes[1]).unwrap();
250        assert_eq!(proof.branch()[0], tx_hashes[0]);
251        assert_eq!(proof.calculate_root(&tx_hashes[1]), expected_root);
252
253        assert!(create_merkle_proof(tx_hashes, &Hash::null()).is_none());
254    }
255
256    #[test]
257    fn test_simple_proof_construction() {
258        //        { root }
259        //      /        \
260        //     h01       h2345
261        //   /    \     /    \
262        //  h0    h1    h23   h45
263        //            /  \    /  \
264        //          h2    h3 h4   h5
265
266        let hashes = (1..=6).map(|i| Hash::from([i - 1; 32])).collect::<Vec<_>>();
267        let h23 = cn_fast_hash2(&hashes[2], &hashes[3]);
268        let h45 = cn_fast_hash2(&hashes[4], &hashes[5]);
269        let h01 = cn_fast_hash2(&hashes[0], &hashes[1]);
270        let h2345 = cn_fast_hash2(&h23, &h45);
271        let expected_root = cn_fast_hash2(&h01, &h2345);
272
273        // Proof for h0
274        let proof = create_merkle_proof(&hashes, &hashes[0]).unwrap();
275        assert_eq!(proof.calculate_root(&hashes[0]), expected_root);
276        assert_eq!(proof.branch().len(), 2);
277        assert_eq!(proof.branch()[0], hashes[1]);
278        assert_eq!(proof.branch()[1], h2345);
279        assert_eq!(proof.path_bitmap, 0b00000000);
280
281        // Proof for h2
282        let proof = create_merkle_proof(&hashes, &hashes[2]).unwrap();
283        assert_eq!(proof.calculate_root(&hashes[2]), expected_root);
284        assert_eq!(proof.path_bitmap, 0b00000001);
285        let branch = proof.branch();
286        assert_eq!(branch[0], hashes[3]);
287        assert_eq!(branch[1], h45);
288        assert_eq!(branch[2], h01);
289        assert_eq!(branch.len(), 3);
290
291        // Proof for h5
292        let proof = create_merkle_proof(&hashes, &hashes[5]).unwrap();
293        assert_eq!(proof.calculate_root(&hashes[5]), expected_root);
294        assert_eq!(proof.branch.len(), 3);
295        assert_eq!(proof.path_bitmap, 0b00000111);
296        let branch = proof.branch();
297        assert_eq!(branch[0], hashes[4]);
298        assert_eq!(branch[1], h23);
299        assert_eq!(branch[2], h01);
300        assert_eq!(branch.len(), 3);
301
302        // Proof for h4
303        let proof = create_merkle_proof(&hashes, &hashes[4]).unwrap();
304        assert_eq!(proof.calculate_root(&hashes[4]), expected_root);
305        assert_eq!(proof.branch.len(), 3);
306        assert_eq!(proof.path_bitmap, 0b00000011);
307        let branch = proof.branch();
308        assert_eq!(branch[0], hashes[5]);
309        assert_eq!(branch[1], h23);
310        assert_eq!(branch[2], h01);
311        assert_eq!(branch.len(), 3);
312    }
313
314    #[test]
315    fn test_complex_proof_construction() {
316        let tx_hashes = &[
317            "d96756959949db23764592fea0bfe88c790e1fd131dabb676948b343aa9ecc24",
318            "77d1a87df131c36da4832a7ec382db9b8fe947576a60ec82cc1c66a220f6ee42",
319            "c723329b1036e4e05313c6ec3bdda3a2e1ab4db17661cad1a6a33512d9b86bcd",
320            "5d863b3d275bacd46dbe8a5f3edce86f88cbc01232bd2788b6f44684076ef8a8",
321            "16d945de6c96ea7f986b6c70ad373a9203a1ddd1c5d12effc3c69b8648826deb",
322            "ccec8f06c5bab1b87bb9af1a3cba94304f87dc037e03b5d2a00406d399316ff7",
323            "c8d52ed0712f0725531f8f72da029201b71e9e215884015f7050dde5f33269e7",
324            "4360ba7fe3872fa8bbc9655486a02738ee000d0c48bda84a15d4730fea178519",
325            "3c8c6b54dcffc75abff89d604ebf1e216bfcb2844b9720ab6040e8e49ae9743c",
326            "6dc19de81e509fba200b652fbdde8fe2aeb99bb9b17e0af79d0c682dff194e08",
327            "3ef031981bc4e2375eebd034ffda4e9e89936962ad2c94cfcc3e6d4cfa8a2e8c",
328            "9e4b865ebe51dcc9cfb09a9b81e354b8f423c59c902d5a866919f053bfbc374e",
329            "fa58575f7d1d377709f1621fac98c758860ca6dc5f2262be9ce5fd131c370d1a",
330        ]
331        .iter()
332        .map(|hash| Hash::from_str(hash).unwrap())
333        .collect::<Vec<_>>();
334
335        let expected_root = tree_hash(tx_hashes).unwrap();
336
337        let hash =
338            Hash::from_str("fa58575f7d1d377709f1621fac98c758860ca6dc5f2262be9ce5fd131c370d1a")
339                .unwrap();
340        let proof = create_merkle_proof(tx_hashes, &hash).unwrap();
341
342        assert_eq!(proof.path_bitmap, 0b00001111);
343
344        assert_eq!(proof.calculate_root(&hash), expected_root);
345
346        assert!(!proof.branch().contains(&hash));
347        assert!(!proof.branch().contains(&expected_root));
348    }
349
350    #[test]
351    fn test_big_proof_construction() {
352        // 65536 txs is beyond what is reasonable to fit in a block
353        let mut thread_rng = rand::thread_rng();
354        let tx_hashes = iter::repeat_n((), 0x10000)
355            .map(|_| {
356                let mut buf = [0u8; 32];
357                thread_rng.fill_bytes(&mut buf[..]);
358                Hash::from_slice(&buf[..])
359            })
360            .collect::<Vec<_>>();
361
362        let expected_root = tree_hash(&tx_hashes).unwrap();
363
364        let hash = tx_hashes.last().unwrap();
365        let proof = create_merkle_proof(&tx_hashes, hash).unwrap();
366
367        assert_eq!(proof.branch.len(), 16);
368        assert_eq!(proof.path_bitmap, 0b1111_1111_1111_1111);
369
370        assert_eq!(proof.calculate_root(hash), expected_root);
371
372        assert!(!proof.branch().contains(hash));
373        assert!(!proof.branch().contains(&expected_root));
374    }
375
376    // Test that both sync and async serialization formats match.
377    // We do some hacks because Monero lib doesn't do async.
378    #[test]
379    fn test_monero_merkleproof_serde() {
380        let tx_hashes = &[
381            "d96756959949db23764592fea0bfe88c790e1fd131dabb676948b343aa9ecc24",
382            "77d1a87df131c36da4832a7ec382db9b8fe947576a60ec82cc1c66a220f6ee42",
383        ]
384        .iter()
385        .map(|hash| Hash::from_str(hash).unwrap())
386        .collect::<Vec<_>>();
387
388        let proof = create_merkle_proof(tx_hashes, &tx_hashes[0]).unwrap();
389
390        let local_ex = smol::LocalExecutor::new();
391
392        let ser_sync = darkfi_serial::serialize(&proof);
393        let ser_async = smol::future::block_on(
394            local_ex.run(async { darkfi_serial::serialize_async(&proof).await }),
395        );
396
397        assert_eq!(ser_sync, ser_async);
398
399        let de_sync: MerkleProof = darkfi_serial::deserialize(&ser_async).unwrap();
400        let de_async: MerkleProof = smol::future::block_on(
401            local_ex.run(async { darkfi_serial::deserialize_async(&ser_sync).await.unwrap() }),
402        );
403
404        assert_eq!(de_sync.branch, proof.branch);
405        assert_eq!(de_async.branch, proof.branch);
406        assert_eq!(de_sync.path_bitmap, proof.path_bitmap);
407        assert_eq!(de_async.path_bitmap, proof.path_bitmap);
408    }
409}
darkfi/blockchain/monero/merkle_proof.rs

darkfi/blockchain/monero/
merkle_proof.rs
