merkle_search_tree/digest/
trait.rs

1use std::num::NonZeroU8;
2
3/// A hash function outputting a fixed-length digest of `N` bytes.
4///
5/// The hash function must produce strong digests with a low probability of
6/// collision. Use of a cryptographic hash function is not required, but may be
7/// preferred for security/compliance reasons.
8///
9/// Use of a faster hash function results in faster tree operations. Use of
10/// 64bit hash values (`N <= 8`) and smaller is not recommended due to the
11/// higher probability of collisions.
12///
13/// # Determinism & Portability
14///
15/// Implementations are required to be deterministic across all peers which
16/// compare tree values. Notably the standard library [`Hash`] derive does not
17/// produce portable hashes across differing platforms, endian-ness or Rust
18/// compiler versions.
19///
20/// # Default Implementation
21///
22/// The default [`Hasher`] implementation ([`SipHasher`]) outputs 128-bit/16
23/// byte digests which are strong, but not of cryptographic quality.
24///
25/// [`SipHasher`] uses the standard library [`Hash`] trait, which may produce
26/// non-portable hashes as described above (and in the [`Hash`] documentation).
27///
28/// Users may choose to initialise the [`SipHasher`] with seed keys if untrusted
29/// key/value user input is used in a tree in order to prevent chosen-hash
30/// collision attacks.
31///
32/// The provided [`SipHasher`] implementation is not portable across platforms /
33/// Rust versions due to limitations of the [`Hash`] trait.
34///
35/// [`SipHasher`]: super::siphash::SipHasher
36pub trait Hasher<const N: usize, T> {
37    /// Hash `T`, producing a unique, deterministic digest of `N` bytes length.
38    fn hash(&self, value: &T) -> Digest<N>;
39}
40
41/// A variable bit length digest, output from a [`Hasher`] implementation.
42#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
43pub struct Digest<const N: usize>([u8; N]);
44
45impl<const N: usize> Digest<N> {
46    /// Wrap an opaque byte array in a [`Digest`] for type safety.
47    pub const fn new(digest: [u8; N]) -> Self {
48        Self(digest)
49    }
50
51    /// Return a reference to a fixed size digest byte array.
52    pub const fn as_bytes(&self) -> &[u8; N] {
53        &self.0
54    }
55}
56
57impl<const N: usize> AsRef<[u8]> for Digest<N> {
58    fn as_ref(&self) -> &[u8] {
59        &self.0
60    }
61}
62
63#[cfg(feature = "digest_base64")]
64impl<const N: usize> std::fmt::Display for Digest<N> {
65    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
66        use base64::{display::Base64Display, engine::general_purpose::STANDARD};
67
68        Base64Display::new(&self.0, &STANDARD).fmt(f)
69    }
70}
71
72// TODO(dom:doc): update this
73
74/// Extract the number of leading 0's when expressed as base 16 digits, defining
75/// the tree level the hash should reside at.
76pub(crate) fn level<const N: usize>(v: &Digest<N>, base: NonZeroU8) -> u8 {
77    let mut out = 0;
78    for v in v.0.into_iter().map(|v| base_count_zero(v, base)) {
79        match v {
80            2 => out += 2,
81            1 => return out + 1,
82            0 => return out,
83            _ => unreachable!(),
84        }
85    }
86    out
87}
88
89const fn base_count_zero(v: u8, base: NonZeroU8) -> u8 {
90    if v == 0 {
91        return 2;
92    }
93
94    if v % base.get() == 0 {
95        return 1;
96    }
97
98    0
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104    use crate::DEFAULT_LEVEL_BASE;
105
106    #[test]
107    fn test_as_bytes() {
108        let b = [42, 42, 42, 42];
109        let d = Digest::new(b);
110        assert_eq!(b, *d.as_bytes());
111    }
112
113    /// Validate the current level derivation scheme is compatible (produces the
114    /// same output for a given input) as the original algorithm used.
115    #[test]
116    fn test_compatibility_b16() {
117        fn old_algorithm(v: u8) -> u8 {
118            match v {
119                0x00 => 2,
120                0x10 => 1,
121                0x30 => 1,
122                0x20 => 1,
123                0x40 => 1,
124                0x50 => 1,
125                0x60 => 1,
126                0x70 => 1,
127                0x80 => 1,
128                0x90 => 1,
129                0xA0 => 1,
130                0xB0 => 1,
131                0xC0 => 1,
132                0xD0 => 1,
133                0xE0 => 1,
134                0xF0 => 1,
135                _ => 0,
136            }
137        }
138
139        for i in 0..u8::MAX {
140            assert_eq!(old_algorithm(i), base_count_zero(i, 16.try_into().unwrap()));
141        }
142    }
143
144    #[test]
145    fn test_prefix_lens() {
146        let got = level(&Digest::new([0x00, 0x00, 0x00, 0x11]), DEFAULT_LEVEL_BASE);
147        assert_eq!(got, 6);
148
149        let got = level(&Digest::new([0x11, 0x00, 0x00, 0x00]), DEFAULT_LEVEL_BASE);
150        assert_eq!(got, 0);
151
152        // Stops after the first non-zero value
153        let got = level(&Digest::new([0x00, 0x10, 0x00, 0x11]), DEFAULT_LEVEL_BASE);
154        assert_eq!(got, 3);
155
156        // Matches the base
157        let got = level(&Digest::new([0x00, 16]), DEFAULT_LEVEL_BASE);
158        assert_eq!(got, 3);
159
160        // Wrap-around the base
161        let got = level(&Digest::new([0x00, 17]), DEFAULT_LEVEL_BASE);
162        assert_eq!(got, 2);
163    }
164}
merkle_search_tree/digest/trait.rs

merkle_search_tree/digest/
trait.rs
