bsv_spv/
merkle_path.rs

1//! Merkle path (BUMP) types and verification.
2//!
3//! Ported from the Go SDK's `merklepath.go`. Implements BRC-74 binary format.
4
5use bsv_primitives::chainhash::Hash;
6use bsv_primitives::util::{BsvReader, BsvWriter, VarInt};
7use serde::{Deserialize, Serialize};
8use std::collections::HashMap;
9
10use crate::error::SpvError;
11use crate::merkle_tree_parent::merkle_tree_parent;
12
13/// A single element in a Merkle path level.
14#[derive(Clone, Debug, Serialize, Deserialize)]
15pub struct PathElement {
16    /// Position offset within this tree level.
17    pub offset: u64,
18    /// Hash value at this position (absent when `duplicate` is set).
19    #[serde(skip_serializing_if = "Option::is_none")]
20    pub hash: Option<Hash>,
21    /// When `Some(true)`, indicates this element is the target transaction ID.
22    #[serde(skip_serializing_if = "Option::is_none")]
23    pub txid: Option<bool>,
24    /// When `Some(true)`, the sibling hash is a duplicate of its pair (odd leaf count).
25    #[serde(skip_serializing_if = "Option::is_none")]
26    pub duplicate: Option<bool>,
27}
28
29/// A Merkle path (BUMP) associating a transaction with a block via a
30/// sequence of hashes at each tree level.
31#[derive(Clone, Debug, Serialize, Deserialize)]
32#[serde(rename_all = "camelCase")]
33pub struct MerklePath {
34    /// Block height at which the transaction was mined.
35    pub block_height: u32,
36    /// Path levels from leaf (index 0) to root, each containing one or more elements.
37    pub path: Vec<Vec<PathElement>>,
38}
39
40/// Indexed path for efficient offset lookups with recursive computation.
41struct IndexedPath(Vec<HashMap<u64, PathElement>>);
42
43impl IndexedPath {
44    fn from_merkle_path(mp: &MerklePath) -> Self {
45        let mut indexed = Vec::with_capacity(mp.path.len());
46        for level in &mp.path {
47            let mut map = HashMap::new();
48            for elem in level {
49                map.insert(elem.offset, elem.clone());
50            }
51            indexed.push(map);
52        }
53        IndexedPath(indexed)
54    }
55
56    fn get_offset_leaf(&self, layer: usize, offset: u64) -> Option<PathElement> {
57        if let Some(leaf) = self.0[layer].get(&offset) {
58            return Some(leaf.clone());
59        }
60        if layer == 0 {
61            return None;
62        }
63        let prev_offset = offset * 2;
64        let left = self.get_offset_leaf(layer - 1, prev_offset)?;
65        let right = self.get_offset_leaf(layer - 1, prev_offset + 1)?;
66        let left_hash = left.hash.as_ref()?;
67        let parent_hash = if right.duplicate == Some(true) {
68            merkle_tree_parent(left_hash, left_hash)
69        } else {
70            let right_hash = right.hash.as_ref()?;
71            merkle_tree_parent(left_hash, right_hash)
72        };
73        Some(PathElement {
74            offset,
75            hash: Some(parent_hash),
76            txid: None,
77            duplicate: None,
78        })
79    }
80}
81
82impl MerklePath {
83    /// Create a new MerklePath.
84    pub fn new(block_height: u32, path: Vec<Vec<PathElement>>) -> Self {
85        MerklePath { block_height, path }
86    }
87
88    /// Parse a MerklePath from a hex string (BRC-74 binary format).
89    pub fn from_hex(hex_data: &str) -> Result<Self, SpvError> {
90        let bin = hex::decode(hex_data)?;
91        Self::from_bytes(&bin)
92    }
93
94    /// Parse a MerklePath from binary data (BRC-74).
95    pub fn from_bytes(data: &[u8]) -> Result<Self, SpvError> {
96        if data.len() < 37 {
97            return Err(SpvError::InvalidMerklePath(
98                "BUMP bytes do not contain enough data to be valid".to_string(),
99            ));
100        }
101        let mut reader = BsvReader::new(data);
102        Self::from_reader(&mut reader)
103    }
104
105    /// Parse a MerklePath from a BsvReader.
106    pub fn from_reader(reader: &mut BsvReader) -> Result<Self, SpvError> {
107        let block_height_vi = reader
108            .read_varint()
109            .map_err(|e| SpvError::InvalidMerklePath(format!("reading block height: {}", e)))?;
110        let block_height = block_height_vi.value() as u32;
111
112        let tree_height = reader
113            .read_u8()
114            .map_err(|e| SpvError::InvalidMerklePath(format!("reading tree height: {}", e)))?;
115
116        let mut path = Vec::with_capacity(tree_height as usize);
117
118        for _ in 0..tree_height {
119            let n_leaves = reader
120                .read_varint()
121                .map_err(|e| SpvError::InvalidMerklePath(format!("reading leaf count: {}", e)))?;
122
123            let mut level = Vec::with_capacity(n_leaves.value() as usize);
124            for _ in 0..n_leaves.value() {
125                let offset_vi = reader
126                    .read_varint()
127                    .map_err(|e| SpvError::InvalidMerklePath(format!("reading offset: {}", e)))?;
128                let offset = offset_vi.value();
129
130                let flags = reader
131                    .read_u8()
132                    .map_err(|e| SpvError::InvalidMerklePath(format!("reading flags: {}", e)))?;
133
134                let dup = (flags & 1) != 0;
135                let is_txid = (flags & 2) != 0;
136
137                let mut elem = PathElement {
138                    offset,
139                    hash: None,
140                    txid: None,
141                    duplicate: None,
142                };
143
144                if dup {
145                    elem.duplicate = Some(true);
146                } else {
147                    let hash_bytes = reader
148                        .read_bytes(32)
149                        .map_err(|e| SpvError::InvalidMerklePath(format!("reading hash: {}", e)))?;
150                    elem.hash = Some(Hash::from_bytes(hash_bytes).map_err(|e| {
151                        SpvError::InvalidMerklePath(format!("invalid hash: {}", e))
152                    })?);
153                }
154
155                if is_txid {
156                    elem.txid = Some(true);
157                }
158
159                level.push(elem);
160            }
161
162            // Sort by offset for consistency
163            level.sort_by_key(|e| e.offset);
164            path.push(level);
165        }
166
167        Ok(MerklePath { block_height, path })
168    }
169
170    /// Serialize to BRC-74 binary format.
171    pub fn to_bytes(&self) -> Vec<u8> {
172        let mut writer = BsvWriter::new();
173        writer.write_varint(VarInt(self.block_height as u64));
174        let tree_height = self.path.len();
175        writer.write_u8(tree_height as u8);
176
177        for level in &self.path {
178            writer.write_varint(VarInt(level.len() as u64));
179            for leaf in level {
180                writer.write_varint(VarInt(leaf.offset));
181                let mut flags = 0u8;
182                if leaf.duplicate == Some(true) {
183                    flags |= 1;
184                }
185                if leaf.txid == Some(true) {
186                    flags |= 2;
187                }
188                writer.write_u8(flags);
189                if (flags & 1) == 0 {
190                    if let Some(ref hash) = leaf.hash {
191                        writer.write_bytes(hash.as_bytes());
192                    }
193                }
194            }
195        }
196
197        writer.into_bytes()
198    }
199
200    /// Serialize to hex string (BRC-74).
201    pub fn to_hex(&self) -> String {
202        hex::encode(self.to_bytes())
203    }
204
205    /// Clone by serializing and deserializing.
206    pub fn deep_clone(&self) -> Self {
207        Self::from_bytes(&self.to_bytes()).unwrap()
208    }
209
210    /// Compute the Merkle root given a transaction ID.
211    /// If `txid` is None, uses the first available hash from level 0.
212    pub fn compute_root(&self, txid: Option<&Hash>) -> Result<Hash, SpvError> {
213        let txid = match txid {
214            Some(t) => *t,
215            None => {
216                let mut found = None;
217                for l in &self.path[0] {
218                    if let Some(ref h) = l.hash {
219                        found = Some(*h);
220                        break;
221                    }
222                }
223                found.ok_or_else(|| {
224                    SpvError::InvalidMerklePath("no hash found at level 0".to_string())
225                })?
226            }
227        };
228
229        // Special case: single tx in block
230        if self.path.len() == 1 && self.path[0].len() == 1 {
231            return Ok(txid);
232        }
233
234        let indexed_path = IndexedPath::from_merkle_path(self);
235
236        // Find the leaf matching this txid
237        let tx_leaf = self.path[0]
238            .iter()
239            .find(|l| l.hash.as_ref().is_some_and(|h| *h == txid))
240            .ok_or_else(|| {
241                SpvError::InvalidMerklePath(format!("the BUMP does not contain the txid: {}", txid))
242            })?;
243
244        let mut working_hash = tx_leaf.hash.unwrap();
245        let index = tx_leaf.offset;
246
247        for height in 0..self.path.len() {
248            let offset = (index >> height) ^ 1;
249            let leaf = indexed_path
250                .get_offset_leaf(height, offset)
251                .ok_or_else(|| {
252                    SpvError::InvalidMerklePath(format!(
253                        "we do not have a hash for this index at height: {}",
254                        height
255                    ))
256                })?;
257
258            if leaf.duplicate == Some(true) {
259                working_hash = merkle_tree_parent(&working_hash, &working_hash);
260            } else {
261                let leaf_hash = leaf.hash.ok_or_else(|| {
262                    SpvError::InvalidMerklePath(format!(
263                        "missing hash at height {} offset {}",
264                        height, offset
265                    ))
266                })?;
267                if (offset % 2) != 0 {
268                    working_hash = merkle_tree_parent(&working_hash, &leaf_hash);
269                } else {
270                    working_hash = merkle_tree_parent(&leaf_hash, &working_hash);
271                }
272            }
273        }
274
275        Ok(working_hash)
276    }
277
278    /// Compute root from hex txid string.
279    pub fn compute_root_hex(&self, txid_str: Option<&str>) -> Result<String, SpvError> {
280        let txid = match txid_str {
281            Some(s) => Some(
282                Hash::from_hex(s)
283                    .map_err(|e| SpvError::InvalidMerklePath(format!("invalid txid hex: {}", e)))?,
284            ),
285            None => None,
286        };
287        let root = self.compute_root(txid.as_ref())?;
288        Ok(root.to_string())
289    }
290
291    /// Combine another MerklePath into this one.
292    /// Both must have the same block height and same root.
293    pub fn combine(&mut self, other: &MerklePath) -> Result<(), SpvError> {
294        if self.block_height != other.block_height {
295            return Err(SpvError::InvalidMerklePath(
296                "cannot combine MerklePaths with different block heights".to_string(),
297            ));
298        }
299
300        let root1 = self.compute_root_hex(None)?;
301        let root2 = other.compute_root_hex(None)?;
302        if root1 != root2 {
303            return Err(SpvError::InvalidMerklePath(
304                "cannot combine MerklePaths with different roots".to_string(),
305            ));
306        }
307
308        // Build combined indexed path
309        let max_len = self.path.len().max(other.path.len());
310        let mut combined: Vec<HashMap<u64, PathElement>> = Vec::with_capacity(max_len);
311        for h in 0..max_len {
312            let mut map = HashMap::new();
313            if h < self.path.len() {
314                for elem in &self.path[h] {
315                    map.insert(elem.offset, elem.clone());
316                }
317            }
318            if h < other.path.len() {
319                for elem in &other.path[h] {
320                    map.insert(elem.offset, elem.clone());
321                }
322            }
323            combined.push(map);
324        }
325
326        // Rebuild path, trimming nodes whose children are both present
327        self.path = Vec::with_capacity(combined.len());
328        for h in (0..combined.len()).rev() {
329            let mut level = Vec::new();
330            for (&offset, elem) in &combined[h] {
331                if h > 0 {
332                    let child_offset = offset * 2;
333                    let has_left = combined[h - 1].contains_key(&child_offset);
334                    let has_right = combined[h - 1].contains_key(&(child_offset + 1));
335                    if has_left && has_right {
336                        continue;
337                    }
338                }
339                level.push(elem.clone());
340            }
341            level.sort_by_key(|e| e.offset);
342            // Insert at front since we're iterating in reverse
343            self.path.insert(0, level);
344        }
345
346        Ok(())
347    }
348
349    /// Find a PathElement at the given offset in the specified level.
350    pub fn find_leaf_by_offset(&self, level: usize, offset: u64) -> Option<&PathElement> {
351        if level >= self.path.len() {
352            return None;
353        }
354        self.path[level].iter().find(|l| l.offset == offset)
355    }
356
357    /// Add a PathElement to the specified level, growing the path if needed.
358    pub fn add_leaf(&mut self, level: usize, element: PathElement) {
359        while self.path.len() <= level {
360            self.path.push(Vec::new());
361        }
362        self.path[level].push(element);
363    }
364
365    /// Compute missing intermediate hashes from level 0 upward.
366    pub fn compute_missing_hashes(&mut self) {
367        if self.path.len() < 2 {
368            return;
369        }
370
371        for level in 1..self.path.len() {
372            let mut new_elements = Vec::new();
373
374            // Collect left leaves from prev level
375            let prev_level = &self.path[level - 1];
376            for left_leaf in prev_level {
377                if left_leaf.hash.is_none() || (left_leaf.offset & 1) != 0 {
378                    continue;
379                }
380                let right_offset = left_leaf.offset + 1;
381                let parent_offset = left_leaf.offset >> 1;
382
383                // Check if parent already exists at current level
384                let parent_exists = self.path[level].iter().any(|e| e.offset == parent_offset);
385                if parent_exists {
386                    continue;
387                }
388
389                // Find right leaf
390                let right_leaf = prev_level.iter().find(|e| e.offset == right_offset);
391
392                if let Some(right) = right_leaf {
393                    let left_hash = left_leaf.hash.as_ref().unwrap();
394                    let parent_hash = if right.duplicate == Some(true) {
395                        merkle_tree_parent(left_hash, left_hash)
396                    } else if let Some(ref right_hash) = right.hash {
397                        merkle_tree_parent(left_hash, right_hash)
398                    } else {
399                        continue;
400                    };
401                    new_elements.push(PathElement {
402                        offset: parent_offset,
403                        hash: Some(parent_hash),
404                        txid: None,
405                        duplicate: None,
406                    });
407                }
408            }
409
410            self.path[level].extend(new_elements);
411        }
412
413        // Sort each level by offset
414        for level in &mut self.path {
415            level.sort_by_key(|e| e.offset);
416        }
417    }
418}
419
420#[cfg(test)]
421mod tests {
422    use super::*;
423
424    const BRC74_HEX: &str = "fe8a6a0c000c04fde80b0011774f01d26412f0d16ea3f0447be0b5ebec67b0782e321a7a01cbdf7f734e30fde90b02004e53753e3fe4667073063a17987292cfdea278824e9888e52180581d7188d8fdea0b025e441996fc53f0191d649e68a200e752fb5f39e0d5617083408fa179ddc5c998fdeb0b0102fdf405000671394f72237d08a4277f4435e5b6edf7adc272f25effef27cdfe805ce71a81fdf50500262bccabec6c4af3ed00cc7a7414edea9c5efa92fb8623dd6160a001450a528201fdfb020101fd7c010093b3efca9b77ddec914f8effac691ecb54e2c81d0ab81cbc4c4b93befe418e8501bf01015e005881826eb6973c54003a02118fe270f03d46d02681c8bc71cd44c613e86302f8012e00e07a2bb8bb75e5accff266022e1e5e6e7b4d6d943a04faadcf2ab4a22f796ff30116008120cafa17309c0bb0e0ffce835286b3a2dcae48e4497ae2d2b7ced4f051507d010a00502e59ac92f46543c23006bff855d96f5e648043f0fb87a7a5949e6a9bebae430104001ccd9f8f64f4d0489b30cc815351cf425e0e78ad79a589350e4341ac165dbe45010301010000af8764ce7e1cc132ab5ed2229a005c87201c9a5ee15c0f91dd53eff31ab30cd4";
425    const BRC74_ROOT: &str = "57aab6e6fb1b697174ffb64e062c4728f2ffd33ddcfa02a43b64d8cd29b483b4";
426    const BRC74_TXID1: &str = "304e737fdfcb017a1a322e78b067ecebb5e07b44f0a36ed1f01264d2014f7711";
427    const BRC74_TXID2: &str = "d888711d588021e588984e8278a2decf927298173a06737066e43f3e75534e00";
428    const BRC74_TXID3: &str = "98c9c5dd79a18f40837061d5e0395ffb52e700a2689e641d19f053fc9619445e";
429
430    #[test]
431    fn test_parse_from_hex() {
432        let mp = MerklePath::from_hex(BRC74_HEX).unwrap();
433        assert_eq!(BRC74_HEX, mp.to_hex());
434    }
435
436    #[test]
437    fn test_compute_root() {
438        let mp = MerklePath::from_hex(BRC74_HEX).unwrap();
439        let root = mp.compute_root_hex(Some(BRC74_TXID1)).unwrap();
440        assert_eq!(BRC74_ROOT, root);
441    }
442
443    #[test]
444    fn test_compute_root_txid2() {
445        let mp = MerklePath::from_hex(BRC74_HEX).unwrap();
446        let root = mp.compute_root_hex(Some(BRC74_TXID2)).unwrap();
447        assert_eq!(BRC74_ROOT, root);
448    }
449
450    #[test]
451    fn test_compute_root_txid3() {
452        let mp = MerklePath::from_hex(BRC74_HEX).unwrap();
453        let root = mp.compute_root_hex(Some(BRC74_TXID3)).unwrap();
454        assert_eq!(BRC74_ROOT, root);
455    }
456
457    #[test]
458    fn test_serialize_to_hex() {
459        let mp = MerklePath::from_hex(BRC74_HEX).unwrap();
460        assert_eq!(BRC74_HEX, mp.to_hex());
461    }
462
463    #[test]
464    fn test_clone() {
465        let original = MerklePath::from_hex(BRC74_HEX).unwrap();
466        let mut cloned = original.deep_clone();
467        assert_eq!(original.block_height, cloned.block_height);
468        cloned.block_height = 999999;
469        assert_ne!(original.block_height, cloned.block_height);
470    }
471
472    #[test]
473    fn test_combine() {
474        let mp = MerklePath::from_hex(BRC74_HEX).unwrap();
475
476        // Split into path A and B
477        let mut path0a = mp.path[0][..2].to_vec();
478        path0a.extend_from_slice(&mp.path[0][4..]);
479        let path0b = mp.path[0][2..].to_vec();
480        let path1a = mp.path[1][1..].to_vec();
481        let path1b = mp.path[1][..mp.path[1].len() - 1].to_vec();
482
483        let mut path_a_levels = vec![path0a, path1a];
484        path_a_levels.extend_from_slice(&mp.path[2..]);
485        let mut path_a = MerklePath::new(mp.block_height, path_a_levels);
486
487        let mut path_b_levels = vec![path0b, path1b];
488        path_b_levels.extend_from_slice(&mp.path[2..]);
489        let path_b = MerklePath::new(mp.block_height, path_b_levels);
490
491        // Path A can compute root for TXID2 but not TXID3
492        let root_a = path_a.compute_root_hex(Some(BRC74_TXID2)).unwrap();
493        assert_eq!(root_a, BRC74_ROOT);
494        assert!(path_a.compute_root_hex(Some(BRC74_TXID3)).is_err());
495
496        // Path B can compute root for TXID3 but not TXID2
497        let root_b = path_b.compute_root_hex(Some(BRC74_TXID3)).unwrap();
498        assert_eq!(root_b, BRC74_ROOT);
499        assert!(path_b.compute_root_hex(Some(BRC74_TXID2)).is_err());
500
501        // After combining, both work
502        path_a.combine(&path_b).unwrap();
503        let root = path_a.compute_root_hex(Some(BRC74_TXID2)).unwrap();
504        assert_eq!(root, BRC74_ROOT);
505        let root = path_a.compute_root_hex(Some(BRC74_TXID3)).unwrap();
506        assert_eq!(root, BRC74_ROOT);
507    }
508
509    #[test]
510    fn test_add_leaf_and_compute_missing_hashes() {
511        let leaf0 =
512            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000001")
513                .unwrap();
514        let leaf1 =
515            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000002")
516                .unwrap();
517        let leaf2 =
518            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000003")
519                .unwrap();
520        let leaf3 =
521            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000004")
522                .unwrap();
523
524        let h01 = merkle_tree_parent(&leaf0, &leaf1);
525        let h23 = merkle_tree_parent(&leaf2, &leaf3);
526        let root = merkle_tree_parent(&h01, &h23);
527
528        let mut mp = MerklePath::new(1000, vec![]);
529        mp.add_leaf(
530            0,
531            PathElement {
532                offset: 0,
533                hash: Some(leaf0),
534                txid: None,
535                duplicate: None,
536            },
537        );
538        mp.add_leaf(
539            0,
540            PathElement {
541                offset: 1,
542                hash: Some(leaf1),
543                txid: None,
544                duplicate: None,
545            },
546        );
547        mp.add_leaf(
548            0,
549            PathElement {
550                offset: 2,
551                hash: Some(leaf2),
552                txid: Some(true),
553                duplicate: None,
554            },
555        );
556        mp.add_leaf(
557            0,
558            PathElement {
559                offset: 3,
560                hash: Some(leaf3),
561                txid: None,
562                duplicate: None,
563            },
564        );
565
566        // Add empty levels
567        mp.add_leaf(
568            1,
569            PathElement {
570                offset: 0,
571                hash: None,
572                txid: None,
573                duplicate: None,
574            },
575        );
576        mp.add_leaf(
577            2,
578            PathElement {
579                offset: 0,
580                hash: None,
581                txid: None,
582                duplicate: None,
583            },
584        );
585        mp.path[1].clear();
586        mp.path[2].clear();
587
588        mp.compute_missing_hashes();
589
590        assert_eq!(mp.path[1].len(), 2);
591        let found01 = mp.find_leaf_by_offset(1, 0).unwrap();
592        assert_eq!(found01.hash.unwrap().to_string(), h01.to_string());
593        let found23 = mp.find_leaf_by_offset(1, 1).unwrap();
594        assert_eq!(found23.hash.unwrap().to_string(), h23.to_string());
595
596        assert_eq!(mp.path[2].len(), 1);
597        let found_root = mp.find_leaf_by_offset(2, 0).unwrap();
598        assert_eq!(found_root.hash.unwrap().to_string(), root.to_string());
599    }
600
601    #[test]
602    fn test_duplicate_handling() {
603        let leaf0 =
604            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000001")
605                .unwrap();
606        let leaf1 =
607            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000002")
608                .unwrap();
609        let leaf2 =
610            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000003")
611                .unwrap();
612
613        let mut mp = MerklePath::new(1000, vec![Vec::new(), Vec::new(), Vec::new()]);
614        mp.add_leaf(
615            0,
616            PathElement {
617                offset: 0,
618                hash: Some(leaf0),
619                txid: None,
620                duplicate: None,
621            },
622        );
623        mp.add_leaf(
624            0,
625            PathElement {
626                offset: 1,
627                hash: Some(leaf1),
628                txid: None,
629                duplicate: None,
630            },
631        );
632        mp.add_leaf(
633            0,
634            PathElement {
635                offset: 2,
636                hash: Some(leaf2),
637                txid: None,
638                duplicate: None,
639            },
640        );
641        mp.add_leaf(
642            0,
643            PathElement {
644                offset: 3,
645                hash: None,
646                txid: None,
647                duplicate: Some(true),
648            },
649        );
650
651        mp.compute_missing_hashes();
652
653        let h01 = merkle_tree_parent(&leaf0, &leaf1);
654        let found01 = mp.find_leaf_by_offset(1, 0).unwrap();
655        assert_eq!(found01.hash.unwrap().to_string(), h01.to_string());
656
657        let h23 = merkle_tree_parent(&leaf2, &leaf2);
658        let found23 = mp.find_leaf_by_offset(1, 1).unwrap();
659        assert_eq!(found23.hash.unwrap().to_string(), h23.to_string());
660    }
661
662    #[test]
663    fn test_grow_path() {
664        let mut mp = MerklePath::new(1000, vec![]);
665        let leaf =
666            Hash::from_hex("0000000000000000000000000000000000000000000000000000000000000001")
667                .unwrap();
668        mp.add_leaf(
669            5,
670            PathElement {
671                offset: 0,
672                hash: Some(leaf),
673                txid: None,
674                duplicate: None,
675            },
676        );
677        assert_eq!(mp.path.len(), 6);
678        assert_eq!(mp.path[5].len(), 1);
679    }
680
681    // Test vectors from Go SDK
682    #[test]
683    fn test_valid_bumps() {
684        let valid = vec![
685            "fed79f0c000c02fd3803029b490d9c8358ff11afaf45628417c9eb52c1a1fd404078a101b4f71dbba06aa9fd390300fe82f2768edc3d0cfe4d06b7f390dcb0b7e61cca7f70117d83be0f023204d8ef01fd9d010060893ac65c8a8e6b9ef7ed5e05dc3bd25aa904812c09853c5dbf423b58a75d0e01cf0012c3c76d9c332e4701b27bfe7013e7963b92d1851d59c56955b35aecabbc8bae0166000894384f86a5c4d0d294f9b9441c3ee3d13afa094cca4515d32813b3fa4fdf3601320002aac507f74c9ff2676705eee1e70897a8baeecaf30c5f49bb22a0c5ce5fda9a01180021f7e27a08d61245be893a238853d72340881cbd47e0a390895231fa1cc44db9010d004d7a12738a1654777867182ee6f6efc4d692209badfa5ba9bb126d08da18ed880107004f8e96b4ee6154bd44b7709f3fb4041bf4426d5f5a594408345605e254af7cdd010200ec7d8b185bc7c096b9b88de6f63ab22baf738d5fc4cbc328f2e00644749acf520100007fd48b1d2b678907ba045b07132003db8116468cd6a3d4764e0df4a644ea0a220101009bb8ffc1a6ed2ba80ea1b09ff797387115a7129d19e93c003a74e3a20ed6ce590101001106e6ece3f70a16de42d0f87b459c71a2440201728bd8541334933726807921",
686            "feb39d0c000c02fd340700ed4cb1fdd81916dabb69b63bcd378559cf40916205cd004e7f5381cc2b1ea6acfd350702957998e38434782b1c40c63a4aca0ffaf4d5d9bc3385f0e9e396f4dd3238f0df01fd9b030012f77e65627c341a3aaea3a0ed645c0082ef53995f446ab9901a27e4622fd1cc01fdcc010074026299a4ba40fbcf33cc0c64b384f0bb2fb17c61125609a666b546539c221c01e700730f99f8cf10fccd30730474449172c5f97cde6a6cf65163359e778463e9f2b9017200a202c78dee487cf96e1a6a04d51faec4debfad09eea28cc624483f2d6fa53d54013800b51ecabaa590b6bd1805baf4f19fc0eae0dedb533302603579d124059b374b1e011d00a0f36640f32a43d790bb4c3e7877011aa8ae25e433b2b83c952a16f8452b6b79010f005d68efab62c6c457ce0bb526194cc16b27f93f8a4899f6d59ffffdddc06e345c01060099f66a0ef693d151bbe9aeb10392ac5a7712243406f9e821219fd13d1865f569010200201fa17c98478675a96703ded42629a3c7bf32b45d0bff25f8be6849d02889ae010000367765c2d68e0c926d81ecdf9e3c86991ccf5a52e97c49ad5cf584c8ab030427010100237b58d3217709b6ebc3bdc093413ba788739f052a0b5b3a413e65444b146bc1",
687        ];
688        for hex_str in valid {
689            MerklePath::from_hex(hex_str)
690                .expect(&format!("should parse valid bump: {}", &hex_str[..20]));
691        }
692    }
693
694    #[test]
695    fn test_invalid_bumps() {
696        let invalid = vec![
697            "feb39d0c000c01fd9b030012f77e65627c341a3aaea3a0ed645c0082ef53995f446ab9901a27e4622fd1cc01fdcc010074026299a4ba40fbcf33cc0c64b384f0bb2fb17c61125609a666b546539c221c01e700730f99f8cf10fccd30730474449172c5f97cde6a6cf65163359e778463e9f2b9017200a202c78dee487cf96e1a6a04d51faec4debfad09eea28cc624483f2d6fa53d54013800b51ecabaa590b6bd1805baf4f19fc0eae0dedb533302603579d124059b374b1e011d00a0f36640f32a43d790bb4c3e7877011aa8ae25e433b2b83c952a16f8452b6b79010f005d68efab62c6c457ce0bb526194cc16b27f93f8a4899f6d59ffffdddc06e345c01060099f66a0ef693d151bbe9aeb10392ac5a7712243406f9e821219fd13d1865f569010200201fa17c98478675a96703ded42629a3c7bf32b45d0bff25f8be6849d02889ae010000367765c2d68e0c926d81ecdf9e3c86991ccf5a52e97c49ad5cf584c8ab030427010100237b58d3217709b6ebc3bdc093413ba788739f052a0b5b3a413e65444b146bc1",
698        ];
699        for hex_str in invalid {
700            assert!(
701                MerklePath::from_hex(hex_str).is_err(),
702                "should reject invalid bump"
703            );
704        }
705    }
706}
bsv_spv/merkle_path.rs

bsv_spv/
merkle_path.rs
