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
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

use super::blake3_sequence::Blake3SeqNo;
use crate::prelude::*;
use crate::stable_hash::UnorderedAggregator;
use blake3::Hasher;
use ibig::UBig;
use lazy_static::lazy_static;
use num_traits::identities::One;
use std::default::Default;

lazy_static! {
    static ref P: UBig = "50763434429823703141085322590076158163032399096130816327134180611270739679038131809123861970975131471260684737408234060876742190838745219274061025048845231234136148410311444604554192918702297959809128216170781389312847013812749872750274650041183009144583521632294518996531883338553737214586176414455965584933129379474747808392433032576309945590584603359054260866543918929486383805924215982747035136255123252119828736134723149397165643360162699752374292974151421555939481822911026769138419707577501643119472226283015793622652706604535623136902831581637275314074553942039263472515423713366344495524733341031029964603383".parse().unwrap();
}

/// Based on https://crypto.stackexchange.com/a/54546
///
/// The idea here is to use the SequenceNumber to unambiguously identify each
/// field as within it's own database cell, and use an online order-independent
/// aggregator of the cells to produce a final result.
///
/// Within this framework a huge struct can be hashed incrementally or even in
/// parallel as long as sequence numbers are deterministically produced to
/// identify parts within the struct. Conveniently, the SequenceNumber::skip
/// method can be used to jump to parts of a vec or struct efficiently.
pub struct SetHasher {
    // TODO: (Performance). We want an int 2056 + 2048 = 4104 bit int (u4160 if using a word size of 64 at 65 words)
    // That's enough to handle any sequence of mixin operations without overflow.
    // https://github.com/paritytech/parity-common/issues/388
    // Not a bad idea to start here so that when we convert we know that the transformation is ok.
    value: UBig,
}

impl Default for SetHasher {
    fn default() -> Self {

        Self { value: UBig::one() }
    }
}

impl SetHasher {
    #[inline]
    pub fn new() -> Self {
        profile_method!(new);

        Default::default()
    }
    #[inline]
    fn mixin(&mut self, digits: &UBig) {
        profile_method!(mixin);

        self.value *= digits;
        self.value %= &*P;
    }
    pub fn to_bytes(&self) -> Vec<u8> {
        profile_method!(to_bytes);

        self.value.to_le_bytes()
    }
    /// Panics if the bytes are not in a valid format.
    /// The only valid values are values returned from to_bytes()
    pub fn from_bytes(bytes: &[u8]) -> Self {
        profile_method!(from_bytes);

        assert!(bytes.len() <= 257);
        let value = UBig::from_le_bytes(bytes);
        Self { value }
    }
}

/// The SetHasher is already updated in an unordered fashion, so no special second struct
/// is needed. Starts at 1 and mixin when finished.
impl UnorderedAggregator<Blake3SeqNo> for SetHasher {
    #[inline]
    fn write(&mut self, value: impl StableHash, sequence_number: Blake3SeqNo) {
        profile_method!(write);

        // Add the hash of the value to the set.
        let hash = crate::utils::stable_hash::<Self, _>(&value);
        StableHasher::write(self, sequence_number, &hash);
    }
}

impl StableHasher for SetHasher {
    type Out = [u8; 32];
    type Seq = Blake3SeqNo;
    type Unordered = Self;

    fn write(&mut self, sequence_number: Self::Seq, bytes: &[u8]) {
        profile_method!(write);

        // Write the field into a database cell
        let mut output = sequence_number.finish(bytes);
        // Extend to the length necessary. This is a 2048 bit value, 1 bit
        // less than the prime the hash wraps around.
        let mut digits = [0u8; 256];
        output.fill(&mut digits);
        let digits = UBig::from_le_bytes(&digits);
        self.mixin(&digits)
    }

    #[inline]
    fn start_unordered(&mut self) -> Self::Unordered {
        profile_method!(start_unordered);

        Self::new()
    }

    #[inline]
    fn finish_unordered(&mut self, unordered: Self::Unordered, _sequence_number: Self::Seq) {
        profile_method!(finish_unordered);

        self.mixin(&unordered.value)
    }

    fn finish(&self) -> Self::Out {
        profile_method!(finish);

        // Re-mix the state with a Hasher.
        let mut hasher = Hasher::new();
        let le = self.value.to_le_bytes();
        hasher.update(&le);
        hasher.finalize().into()
    }
}