stable_hash/crypto/
hasher.rs

1use super::address::CryptoAddress;
2use crate::prelude::*;
3use blake3::Hasher;
4use ibig::UBig;
5use lazy_static::lazy_static;
6use num_traits::{identities::One, Zero};
7use std::default::Default;
8
9// TODO: Consider using a Solinas prime
10/*
11From Jackson:
12    In particular we could change the prime to be a Solinas prime.
13    If we implement the algorithm for fast modular multiplication around a solinas prime then we get a big speed up.
14    So the changes would be just change the public parameter prime in the codebase, and don’t just naively multiply and reduce, but write the algorithm to take advantage of the structure inherent in Solinas primes
15    (they are prime numbers that have really low hamming weights, a sort of generalization of Mersenne primes — and so computers love these numbers)
16*/
17lazy_static! {
18    static ref P: UBig = "50763434429823703141085322590076158163032399096130816327134180611270739679038131809123861970975131471260684737408234060876742190838745219274061025048845231234136148410311444604554192918702297959809128216170781389312847013812749872750274650041183009144583521632294518996531883338553737214586176414455965584933129379474747808392433032576309945590584603359054260866543918929486383805924215982747035136255123252119828736134723149397165643360162699752374292974151421555939481822911026769138419707577501643119472226283015793622652706604535623136902831581637275314074553942039263472515423713366344495524733341031029964603383".parse().unwrap();
19}
20
21/// Based on https://crypto.stackexchange.com/a/54546
22///
23/// The idea here is to use the FieldAddress to unambiguously identify each
24/// field as within it's own database cell, and use an online order-independent
25/// aggregator of the cells to produce a final result.
26///
27/// Within this framework a huge struct can be hashed incrementally or even in
28/// parallel as long as field addresses are deterministically produced to
29/// uniquely identify parts within the struct. Conveniently, the FieldAddress::skip
30/// method can be used to jump to parts of a vec or struct efficiently.
31#[derive(Clone, Eq, PartialEq, Debug)]
32pub struct CryptoStableHasher {
33    // TODO: (Performance). We want an int 2056 + 2048 = 4104 bit int (u4160 if using a word size of 64 at 65 words)
34    // That's enough to handle any sequence of mixin operations without overflow.
35    // https://github.com/paritytech/parity-common/issues/388
36    // Not a bad idea to start here so that when we convert we know that the transformation is ok.
37    value: UBig,
38}
39
40impl Default for CryptoStableHasher {
41    fn default() -> Self {
42        Self { value: UBig::one() }
43    }
44}
45
46#[inline]
47fn mul_mod_p(into: &mut UBig, value: &UBig) {
48    profile_method!(mul_mod_p);
49    *into *= value;
50    *into %= &*P;
51}
52
53impl StableHasher for CryptoStableHasher {
54    type Out = [u8; 32];
55    type Addr = CryptoAddress;
56    type Bytes = Vec<u8>;
57
58    #[inline]
59    fn new() -> Self {
60        profile_method!(new);
61
62        Default::default()
63    }
64
65    fn write(&mut self, field_address: Self::Addr, bytes: &[u8]) {
66        profile_method!(write);
67
68        // Write the field into a database cell
69        let mut output = field_address.finish(bytes);
70        // Extend to the length necessary. This is a 2048 bit value, 1 bit
71        // less than the prime the hash wraps around.
72        let mut digits = [0u8; 256];
73        output.fill(&mut digits);
74        let digits = UBig::from_le_bytes(&digits);
75        mul_mod_p(&mut self.value, &digits);
76    }
77
78    #[inline]
79    fn mixin(&mut self, other: &Self) {
80        mul_mod_p(&mut self.value, &other.value);
81    }
82
83    fn unmix(&mut self, other: &Self) {
84        // The capacity 2049 is because that's the maximum number of divisions there will be.
85        // With high probability, it will all be used.
86        let mut todo = Vec::with_capacity(2049);
87
88        // Find the multiplicative inverse under the field.
89        let mut y = &*P - UBig::from(2u32);
90        while !y.is_zero() {
91            todo.push(y.clone());
92            y = y / 2;
93        }
94        let mut p = UBig::one();
95        while let Some(next) = todo.pop() {
96            let clone = p.clone();
97            mul_mod_p(&mut p, &clone);
98            if next % 2 != 0 {
99                mul_mod_p(&mut p, &other.value);
100            }
101        }
102
103        // If it's the multiplicative inverse, and we multiply it, then we've inversed it.
104        mul_mod_p(&mut self.value, &p);
105    }
106
107    fn finish(&self) -> Self::Out {
108        profile_method!(finish);
109
110        // Re-mix the state with a Hasher.
111        let mut hasher = Hasher::new();
112        let le = self.value.to_le_bytes();
113        hasher.update(&le);
114        hasher.finalize().into()
115    }
116
117    fn to_bytes(&self) -> Self::Bytes {
118        profile_method!(to_bytes);
119        self.value.to_le_bytes()
120    }
121    /// Panics if the bytes are not in a valid format.
122    /// The only valid values are values returned from to_bytes()
123    fn from_bytes(bytes: Vec<u8>) -> Self {
124        profile_method!(from_bytes);
125
126        let value = UBig::from_le_bytes(&bytes);
127        assert!(&value <= &*P);
128        Self { value }
129    }
130}
131
132#[cfg(test)]
133impl CryptoStableHasher {
134    pub(crate) fn rand() -> Self {
135        use rand::Rng;
136        loop {
137            let mut bytes = Vec::new();
138            for _ in 0..257 {
139                let rand_byte: u8 = rand::thread_rng().gen();
140                if bytes.len() == 0 && rand_byte == 0 {
141                    continue;
142                }
143                bytes.push(rand_byte);
144            }
145            let big = UBig::from_be_bytes(&bytes);
146            if &big >= &*P {
147                continue;
148            }
149            return CryptoStableHasher { value: big };
150        }
151    }
152}
stable_hash/crypto/hasher.rs

stable_hash/crypto/
hasher.rs
