penumbra_sdk_tct/internal/
height.rs

1//! Type level machinery used to statically determine the height of a tree, to ensure the correct
2//! domain separator is used when hashing at any height.
3//!
4//! Because the height of a tree is inferred by the type system, this means that bugs where the
5//! wrong height is used to compute a subtree's hashing domain separator are greatly reduced.
6//!
7//! This module contains type-level code for computing the height of structures and translating an
8//! unary representation good for type-level constraints ([`Succ`] and [`Zero`]) into constant
9//! `u64`s suitable for value-level computation.
10
11use crate::prelude::*;
12
13/// Trait identifying the statically-known height of a given tree element.
14///
15/// This is used to differentiate the hashes at each level of the tree.
16pub trait Height {
17    /// The height of this type above the leaves of the tree.
18    type Height: Path;
19}
20
21/// The constant `u8` associated with each unary height.
22pub trait IsHeight: sealed::IsHeight {
23    /// The number for this height.
24    const HEIGHT: u8;
25}
26
27/// Height zero.
28pub struct Zero;
29
30impl IsHeight for Zero {
31    const HEIGHT: u8 = 0;
32}
33
34/// Height `N + 1`.
35pub struct Succ<N>(N);
36
37impl<N: IsHeight> IsHeight for Succ<N> {
38    const HEIGHT: u8 = if let Some(n) = N::HEIGHT.checked_add(1) {
39        n
40    } else {
41        panic!("height overflow: can't construct something of height > u8::MAX")
42    };
43}
44
45/// Seal the `IsHeight` trait so that only `Succ` and `Zero` can inhabit it.
46mod sealed {
47    use super::{Succ, Zero};
48
49    pub trait IsHeight {}
50    impl IsHeight for Zero {}
51    impl<N: IsHeight> IsHeight for Succ<N> {}
52}
penumbra_sdk_tct/internal/height.rs

penumbra_sdk_tct/internal/
height.rs
