penumbra_sdk_tct/internal/
interface.rs

1//! This module contains trait definitions for the entire interface of the internal tree. All of
2//! them are exported from either [`frontier`](crate::internal::frontier) or
3//! [`complete`](crate::internal::complete), but they are also exported from here for ease of
4//! reading.
5
6use std::fmt::Debug;
7
8use crate::prelude::*;
9
10/// A frontier of a tree supporting the insertion of new elements and the updating of the
11/// most-recently-inserted element.
12pub trait Frontier: Focus + Sized {
13    /// The type of item to persist in each witnessed leaf of the frontier.
14    type Item;
15
16    /// Make a new [`Frontier`] containing a single [`Hash`](struct@Hash) or `Self::Item`.
17    fn new(item: Self::Item) -> Self;
18
19    /// Insert a new [`Hash`](struct@Hash) or `Self::Item` into this [`Frontier`], returning either
20    /// `Self` with the thing inserted, or the un-inserted thing and the [`Complete`] of this
21    /// [`Frontier`].
22    fn insert_owned(self, item: Self::Item) -> Result<Self, Full<Self>>;
23
24    /// Update the currently focused `Insert<Self::Item>` (i.e. the most-recently
25    /// [`insert`](Frontier::insert_owned) one), returning the result of the function.
26    fn update<T>(&mut self, f: impl FnOnce(&mut Self::Item) -> T) -> Option<T>;
27
28    /// Get a reference to the focused `Insert<Self::Item>` (i.e. the most-recently
29    /// [`insert`](Frontier::insert_owned) one).
30    fn focus(&self) -> Option<&Self::Item>;
31
32    /// Check whether this frontier is full.
33    fn is_full(&self) -> bool;
34}
35
36/// A type which can be the focus of an [`Frontier`] tree: it can be finalized to make a [`Complete`]
37/// tree.
38pub trait Focus: Height<Height = <Self::Complete as Height>::Height> + GetHash {
39    /// The [`Complete`] of this [`Frontier`].
40    type Complete: Complete<Focus = Self>;
41
42    /// Transition from an [`Frontier`] to being [`Complete`].
43    fn finalize_owned(self) -> Insert<Self::Complete>;
44}
45
46/// Marker trait for a type which is the frozen completion of some [`Focus`]ed insertion point.
47///
48/// It is enforced by the type system that [`Complete`] and [`Focus`] are dual to one another.
49pub trait Complete: Height + GetHash {
50    /// The corresponding [`Focus`] of this [`Complete`] (i.e. the type which will become this type
51    /// when it is [`finalize_owned`](Focus::finalize_owned)).
52    type Focus: Focus<Complete = Self>;
53}
54
55/// The result of [`Frontier::insert_owned`] when the [`Frontier`] is full.
56#[derive(Debug)]
57pub struct Full<T: Frontier> {
58    /// The original hash or item that could not be inserted.
59    pub item: T::Item,
60    /// The completed structure, which has no more room for any further insertions, or a hash of
61    /// that structure if it contained no witnesses.
62    pub complete: Insert<T::Complete>,
63}
64
65/// Witness an authentication path into a tree, or remove a witnessed item from one.
66pub trait Witness: Height + Sized {
67    /// Witness an authentication path to the given index in the tree.
68    ///
69    /// The input mutable slice should be at least the height of the tree, and is overwritten by
70    /// this function.
71    fn witness(&self, index: impl Into<u64>) -> Option<(AuthPath<Self>, Hash)>;
72}
73
74/// Get the position of the next insertion into the tree.
75pub trait GetPosition {
76    /// The position of the next insertion into the tree.
77    ///
78    /// Returns `None` if the tree is full.
79    fn position(&self) -> Option<u64>;
80}
81
82/// Forget about the authentication path to a given index.
83pub trait Forget: Height {
84    /// Remove the witness for the given index. If a forgotten version is specified, update the path
85    /// down to the forgotten item to that version plus one.
86    ///
87    /// Returns `true` if the witness was previously present in the tree.
88    fn forget(&mut self, forgotten: Option<Forgotten>, index: impl Into<u64>) -> bool;
89}
90
91/// Forget about the authentication path to a given index, when forgetting can turn the entirety of
92/// `Self` into a hash.
93pub trait ForgetOwned: Height + Sized {
94    /// Remove the witness for the given index and summarize the item as a single `Hash` if it now
95    /// contains no more witnesses. If a forgotten version is specified, update the path
96    /// down to the forgotten item to that version plus one.
97    ///
98    /// Returns either `(Self, boool)` where the boolean is `true` if the witness was removed or
99    /// `false` if the witness was not present, or `Hash` if the witness was removed and it was the
100    /// last witness remaining in this tree.
101    fn forget_owned(
102        self,
103        forgotten: Option<Forgotten>,
104        index: impl Into<u64>,
105    ) -> (Insert<Self>, bool);
106}
107
108// These traits are crate-only, because they violate internal invariants unless used correctly.
109// There is absolutely no reason to use them outside this crate; they are use to implement
110// deserialization, and do not need to be used for anything else!
111
112/// When deserializing, we need to insert into an initially empty structure filled with
113/// uninitialized interior hashes, then insert all the commitments into the leaves of that
114/// structure, filling its shape out correctly. Then, we can use [`UncheckedSetHash`] to set the
115/// internal hashes of the structure, and finalize it.
116pub(crate) trait OutOfOrder {
117    /// Create a new frontier which has the given position, with all frontier hashes filled in with
118    /// `Hash::uninitialized()`.
119    fn uninitialized(position: Option<u64>, forgotten: Forgotten) -> Self;
120
121    /// Sets the commitment at the position to the given commitment, creating uninitialized internal
122    /// nodes as necessary.
123    ///
124    /// If the commitment is already set, overwrites it. If the index is outside the bounds of the
125    /// structure, does nothing.
126    fn uninitialized_out_of_order_insert_commitment(
127        &mut self,
128        index: u64,
129        commitment: StateCommitment,
130    );
131}
132
133/// Owned version of [`OutOfOrder::insert_commitment`], used for complete nodes.
134pub(crate) trait OutOfOrderOwned: Sized {
135    /// Sets the commitment at the position to the given commitment, creating uninitialized internal
136    /// nodes as necessary.
137    ///
138    /// This takes an `Insert<Self>` and returns `Self` to accurately model that internal nodes may
139    /// be abbreviated by a hash, but once a commitment is witnessed beneath them, they are not.
140    ///
141    /// If the commitment is already set, overwrites it. If the index is outside of the bounds of
142    /// the structure, does nothing.
143    fn uninitialized_out_of_order_insert_commitment_owned(
144        this: Insert<Self>,
145        index: u64,
146        commitment: StateCommitment,
147    ) -> Self;
148}
149
150/// When deserializing, we need to insert all the commitments, then set all the cached hashes, then
151/// recalculate any hashes that weren't cached.
152pub(crate) trait UncheckedSetHash: Height {
153    /// Sets the hash at the position and height to the given hash.
154    ///
155    /// If the hash is already set, overwrites it. If there is not a node at the given position and
156    /// height to set the hash of, does nothing.
157    fn unchecked_set_hash(&mut self, index: u64, height: u8, hash: Hash);
158
159    /// For all hashes in the tree, converts uninitialized leaf hashes to the appropriate
160    /// (un)finalized empty hash (`Hash::one()` or `Hash::zero()` depending on position), and
161    /// calculates and sets the hash for internal nodes, meaning that the internal structure no
162    /// longer contains any `Hash::uninitialized()` anywhere.
163    fn finish_initialize(&mut self);
164}
penumbra_sdk_tct/internal/interface.rs

penumbra_sdk_tct/internal/
interface.rs
