s3p_core/
merkle.rs

1use crate::errors::*;
2use sha2::{Digest, Sha256};
3
4pub fn leaf_hash(data: &[u8]) -> [u8; 32] {
5    let mut h = Sha256::new();
6    h.update(data);
7    h.finalize().into()
8}
9
10pub fn merkle_root(mut leaves: Vec<[u8; 32]>) -> Result<[u8; 32]> {
11    if leaves.is_empty() {
12        return Err(S3pError::Merkle("no leaves".into()));
13    }
14    while leaves.len() > 1 {
15        // ceil(len / 2)
16        let mut next = Vec::with_capacity(leaves.len().div_ceil(2));
17        for i in (0..leaves.len()).step_by(2) {
18            let a = leaves[i];
19            let b = if i + 1 < leaves.len() {
20                leaves[i + 1]
21            } else {
22                a
23            };
24            let mut h = Sha256::new();
25            h.update(a);
26            h.update(b);
27            next.push(h.finalize().into());
28        }
29        leaves = next;
30    }
31    Ok(leaves[0])
32}
33
34pub fn merkle_proof(leaves: &[[u8; 32]], index: usize) -> Result<Vec<[u8; 32]>> {
35    if leaves.is_empty() {
36        return Err(S3pError::Merkle("no leaves".into()));
37    }
38    let mut idx = index;
39    let mut level = leaves.to_vec();
40    let mut proof = Vec::new();
41
42    while level.len() > 1 {
43        let sibling = if (idx ^ 1) < level.len() {
44            level[idx ^ 1]
45        } else {
46            level[idx]
47        };
48        proof.push(sibling);
49
50        // следующий уровень
51        let mut next = Vec::with_capacity(level.len().div_ceil(2));
52        for i in (0..level.len()).step_by(2) {
53            let a = level[i];
54            let b = if i + 1 < level.len() { level[i + 1] } else { a };
55            let mut h = Sha256::new();
56            h.update(a);
57            h.update(b);
58            next.push(h.finalize().into());
59        }
60        level = next;
61        idx /= 2;
62    }
63
64    Ok(proof)
65}
66
67pub fn merkle_verify(
68    root: &[u8; 32],
69    leaf: &[u8; 32],
70    proof: &[[u8; 32]],
71    mut index: usize,
72) -> bool {
73    let mut hash = *leaf;
74
75    for sibling in proof {
76        // MSRV 1.74: избегаем `is_multiple_of` (стабилен с 1.87).
77        let even = (index & 1) == 0;
78        let (left, right) = if even {
79            (hash, *sibling)
80        } else {
81            (*sibling, hash)
82        };
83
84        let mut h = Sha256::new();
85        h.update(left);
86        h.update(right);
87        hash = h.finalize().into();
88
89        index /= 2;
90    }
91
92    &hash == root
93}
s3p_core/merkle.rs

s3p_core/
merkle.rs
