1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#![forbid(unsafe_code)]
#![deny(missing_docs, unstable_features)]
#![cfg_attr(not(any(test, feature = "std")), no_std)]

//! # Utreexo
extern crate alloc;

mod forest;
mod hash;
mod path;
mod proof;

pub(crate) use self::path::{Direction, Path};

pub use self::forest::Forest;
pub use self::hash::Hash;
pub use self::proof::Proof;

use alloc::vec;
use core::iter::{repeat, Iterator};

use blake2b_simd::{many::update_many, Params};

use self::hash::HASH_SIZE;

/// Calculates hash of a leaf
pub(crate) fn hash_leaf<T: AsRef<[u8]>>(value: T) -> Hash {
    let mut params = Params::default();
    params.hash_length(HASH_SIZE);

    let mut state = params.to_state();

    // Add `0` byte to leaf nodes to prevent second preimage attack
    // https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_attack
    state.update(&[0]);
    state.update(value.as_ref());

    state.finalize().into()
}

/// Calculates hash of many leaves
pub(crate) fn hash_many_leaves<T: AsRef<[u8]>>(values: &[T]) -> impl Iterator<Item = Hash> {
    let mut params = Params::default();
    params.hash_length(HASH_SIZE);

    let mut states = vec![params.to_state(); values.len()];

    // Add `0` byte to leaf nodes to prevent second preimage attack
    // https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_attack
    update_many(states.iter_mut().zip(repeat(&[0]).take(values.len())));
    update_many(states.iter_mut().zip(values.iter()));

    states.into_iter().map(|state| state.finalize().into())
}

pub(crate) fn hash_intermediate<T: AsRef<[u8]>>(a: T, b: T) -> Hash {
    let mut params = Params::default();
    params.hash_length(HASH_SIZE);

    let mut state = params.to_state();

    // Add `1` byte to intermediate nodes to prevent second preimage attack
    // https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_attack
    state.update(&[1]);
    state.update(a.as_ref());
    state.update(b.as_ref());

    state.finalize().into()
}