penumbra_sdk_tct/internal/
hash.rs

1//! The core [`Hash`](struct@Hash) type, which is used internally to represent hashes, the
2//! [`GetHash`] trait for computing and caching hashes of things, and the [`CachedHash`] type, which
3//! is used internally for lazy evaluation of hashes.
4
5use std::{
6    fmt::{self, Debug, Formatter},
7    ops::RangeInclusive,
8};
9
10use ark_ff::{One, Zero};
11use once_cell::sync::Lazy;
12use poseidon377::{hash_1, hash_4, Fq};
13use serde::{Deserialize, Serialize};
14
15use crate::prelude::*;
16
17mod cache;
18mod option;
19pub use {cache::CachedHash, option::OptionHash};
20
21/// A type which can be transformed into a [`struct@Hash`], either by retrieving a cached hash, computing a
22/// hash for it, or some combination of both.
23pub trait GetHash {
24    /// Get the hash of this item.
25    ///
26    /// # Correctness
27    ///
28    /// This function must return the same hash for the same item. It is permissible to use internal
29    /// mutability to cache hashes, but caching must ensure that the item cannot be mutated without
30    /// recalculating the hash.
31    fn hash(&self) -> Hash;
32
33    /// Get the hash of this item, only if the hash is already cached and does not require
34    /// recalculation.
35    ///
36    /// # Correctness
37    ///
38    /// It will not cause correctness issues to return a hash after recalculating it, but users of
39    /// this function expect it to be reliably fast, so it may cause unexpected performance issues
40    /// if this function performs any significant work.
41    fn cached_hash(&self) -> Option<Hash>;
42
43    /// If there is a hash cached, clear the cache.
44    ///
45    /// By default, this does nothing. Override this if there is a cache.
46    fn clear_cached_hash(&self) {}
47}
48
49impl<T: GetHash> GetHash for &T {
50    #[inline]
51    fn hash(&self) -> Hash {
52        (**self).hash()
53    }
54
55    #[inline]
56    fn cached_hash(&self) -> Option<Hash> {
57        (**self).cached_hash()
58    }
59}
60
61impl<T: GetHash> GetHash for &mut T {
62    #[inline]
63    fn hash(&self) -> Hash {
64        (**self).hash()
65    }
66
67    #[inline]
68    fn cached_hash(&self) -> Option<Hash> {
69        (**self).cached_hash()
70    }
71}
72
73/// The hash of an individual [`Commitment`] or internal node in the tree.
74#[derive(Clone, Copy, PartialEq, Eq, std::hash::Hash, Serialize, Deserialize)]
75pub struct Hash(#[serde(with = "crate::storage::serialize::fq")] Fq);
76
77impl From<Hash> for Fq {
78    #[inline]
79    fn from(hash: Hash) -> Self {
80        hash.0
81    }
82}
83
84impl Debug for Hash {
85    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
86        if *self == Hash::zero() {
87            write!(f, "0")
88        } else if *self == Hash::one() {
89            write!(f, "1")
90        } else if *self == Hash::uninitialized() {
91            write!(f, "!")
92        } else {
93            write!(f, "{}", hex::encode(self.to_bytes()))
94        }
95    }
96}
97
98/// The domain separator used for leaves in the tree, and used as a base index for the domain
99/// separators of nodes in the tree (nodes get a domain separator of the form `DOMAIN_SEPARATOR +
100/// HEIGHT`).
101pub static DOMAIN_SEPARATOR: Lazy<Fq> =
102    Lazy::new(|| Fq::from_le_bytes_mod_order(blake2b_simd::blake2b(b"penumbra.tct").as_bytes()));
103
104#[allow(unused)]
105impl Hash {
106    /// Create a hash from an arbitrary [`Fq`].
107    pub fn new(fq: Fq) -> Self {
108        Self(fq)
109    }
110
111    /// Get an array of bytes representing the hash
112    pub fn to_bytes(self) -> [u8; 32] {
113        self.0.to_bytes()
114    }
115
116    /// Decode a hash from bytes representing it
117    pub fn from_bytes(bytes: [u8; 32]) -> Result<Self, decaf377::EncodingError> {
118        Ok(Self(Fq::from_bytes_checked(&bytes)?))
119    }
120
121    /// The zero hash, used for padding of frontier nodes.
122    pub fn zero() -> Hash {
123        Self(Fq::zero())
124    }
125
126    /// Checks if the hash is zero.
127    pub fn is_zero(&self) -> bool {
128        self.0.is_zero()
129    }
130
131    /// The one hash, used for padding of complete nodes.
132    pub fn one() -> Hash {
133        Self(Fq::one())
134    }
135
136    /// Checks if the hash is one.
137    pub fn is_one(&self) -> bool {
138        self.0.is_one()
139    }
140
141    /// A stand-in hash that is out-of-range for `Fq`, to be used during intermediate construction
142    /// of the tree as a sentinel value for uninitialized nodes.
143    pub(crate) fn uninitialized() -> Hash {
144        Self(Fq::SENTINEL)
145    }
146
147    /// Checks if the hash is uninitialized.
148    pub(crate) fn is_uninitialized(&self) -> bool {
149        *self == Self::uninitialized()
150    }
151
152    /// Hash an individual commitment to be inserted into the tree.
153    #[inline]
154    pub fn of(item: StateCommitment) -> Hash {
155        Self(hash_1(&DOMAIN_SEPARATOR, item.0))
156    }
157
158    /// Construct a hash for an internal node of the tree, given its height and the hashes of its
159    /// four children.
160    #[inline]
161    pub fn node(height: u8, a: Hash, b: Hash, c: Hash, d: Hash) -> Hash {
162        // Definition of hash of node without cache optimization
163        fn hash_node(height: u8, a: Hash, b: Hash, c: Hash, d: Hash) -> Hash {
164            let height = Fq::from_le_bytes_mod_order(&height.to_le_bytes());
165            Hash(hash_4(&(*DOMAIN_SEPARATOR + height), (a.0, b.0, c.0, d.0)))
166        }
167
168        // The range of hashes to precompute: this captures hashes starting at the first internal node
169        // above the epoch leaf, and up to the epoch root. These are the only useful hashes to
170        // precompute, because commitments are expected to be cryptographically random, so
171        // precomputing internal hashes within blocks won't save work, and epochs are extremely
172        // unlikely to be entirely filled with empty blocks. However, in the middle, we can save
173        // work by remembering how to hash power-of-4-aligned sequences of empty blocks.
174        const PRECOMPUTE_HEIGHTS: RangeInclusive<u8> = 9..=16;
175
176        const TOTAL_PRECOMPUTED: usize =
177            *PRECOMPUTE_HEIGHTS.end() as usize - *PRECOMPUTE_HEIGHTS.start() as usize + 1;
178
179        // Precompute internal node hashes lying above sequences of empty blocks within epochs
180        static PRECOMPUTED_HASH_PAIRS: Lazy<[(Hash, Hash); TOTAL_PRECOMPUTED]> = Lazy::new(|| {
181            let mut hashes: Vec<(Hash, Hash)> = Vec::with_capacity(PRECOMPUTE_HEIGHTS.len());
182
183            for height in PRECOMPUTE_HEIGHTS {
184                let below = hashes.last().map(|below| below.1).unwrap_or_else(Hash::one);
185                hashes.push((below, hash_node(height, below, below, below, below)));
186            }
187
188            hashes
189                .try_into()
190                .expect("precomputed hashes should be the right length")
191        });
192
193        // If the height is in the range of the precomputed hashes, check if all the inputs are
194        // equal to the singular precomputed input for that height, and return the output if so
195        if PRECOMPUTE_HEIGHTS.contains(&height) {
196            let index = usize::from(height - PRECOMPUTE_HEIGHTS.start());
197            let (input, output) = PRECOMPUTED_HASH_PAIRS[index];
198            if [a, b, c, d] == [input, input, input, input] {
199                debug_assert_eq!(
200                    output,
201                    hash_node(height, a, b, c, d),
202                    "precomputed hash mismatched calculated hash"
203                );
204                return output;
205            }
206        }
207
208        // Otherwise, hash the node normally
209        hash_node(height, a, b, c, d)
210    }
211}
212
213/// A version tracking when a particular piece of the tree was explicitly forgotten.
214#[derive(
215    Derivative,
216    Clone,
217    Copy,
218    PartialEq,
219    Eq,
220    PartialOrd,
221    Ord,
222    std::hash::Hash,
223    Serialize,
224    Deserialize,
225    Default,
226)]
227#[cfg_attr(any(test, feature = "arbitrary"), derive(proptest_derive::Arbitrary))]
228#[serde(from = "u64", into = "u64")]
229pub struct Forgotten([u8; 6]);
230
231impl Debug for Forgotten {
232    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
233        write!(f, "{}", u64::from(*self))
234    }
235}
236
237impl Forgotten {
238    /// Get the next forgotten-version after this one.
239    pub fn next(&self) -> Self {
240        Self::from(
241            u64::from(*self)
242                .checked_add(1)
243                .expect("forgotten should never overflow"),
244        )
245    }
246}
247
248impl From<Forgotten> for u64 {
249    fn from(forgotten: Forgotten) -> Self {
250        let mut eight_bytes = <[u8; 8]>::default();
251        for (in_byte, out_byte) in eight_bytes.iter_mut().zip(forgotten.0) {
252            *in_byte = out_byte;
253        }
254
255        u64::from_le_bytes(eight_bytes)
256    }
257}
258
259impl From<u64> for Forgotten {
260    fn from(u: u64) -> Self {
261        let bytes = u.to_le_bytes();
262
263        let mut six_bytes = [0; 6];
264        for (in_byte, out_byte) in six_bytes.iter_mut().zip(&bytes[..6]) {
265            *in_byte = *out_byte;
266        }
267
268        Self(six_bytes)
269    }
270}
271
272#[cfg(any(test, feature = "arbitrary"))]
273mod arbitrary {
274    use poseidon377::Fq;
275
276    use super::Hash;
277
278    impl proptest::arbitrary::Arbitrary for Hash {
279        type Parameters = ();
280
281        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
282            HashStrategy
283        }
284
285        type Strategy = HashStrategy;
286    }
287
288    #[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
289    pub struct HashStrategy;
290
291    impl proptest::strategy::Strategy for HashStrategy {
292        type Tree = proptest::strategy::Just<Hash>;
293
294        type Value = Hash;
295
296        fn new_tree(
297            &self,
298            runner: &mut proptest::test_runner::TestRunner,
299        ) -> proptest::strategy::NewTree<Self> {
300            use proptest::prelude::RngCore;
301            let rng = runner.rng();
302            let mut bytes = [0u8; 32];
303            rng.fill_bytes(&mut bytes);
304            Ok(proptest::strategy::Just(Hash(Fq::from_le_bytes_mod_order(
305                &bytes,
306            ))))
307        }
308    }
309}
310
311#[cfg(test)]
312mod test {
313    #[test]
314    fn forgotten_increments() {
315        use super::Forgotten;
316
317        let mut last = Forgotten::default();
318        for _ in 0..10 {
319            let next = last.next();
320            assert_eq!(u64::from(next), u64::from(last) + 1);
321            last = next;
322        }
323    }
324}
penumbra_sdk_tct/internal/hash.rs

penumbra_sdk_tct/internal/
hash.rs
