penumbra_sdk_tct/
epoch.rs

1use std::fmt::Display;
2use std::sync::Arc;
3
4use decaf377::Fq;
5use hash_hasher::HashedMap;
6use penumbra_sdk_proto::{penumbra::crypto::tct::v1 as pb, DomainType};
7use serde::{Deserialize, Serialize};
8
9use crate::error::epoch::*;
10use crate::{prelude::*, Witness};
11
12#[path = "block.rs"]
13pub(crate) mod block;
14
15/// A sparse merkle tree to witness up to 65,536 blocks, each witnessing up to 65,536
16/// [`Commitment`]s.
17///
18/// This is one epoch in a [`Tree`].
19#[derive(Derivative, Debug, Clone, Serialize, Deserialize)]
20pub struct Builder {
21    index: HashedMap<StateCommitment, index::within::Epoch>,
22    inner: Arc<frontier::Top<frontier::Tier<frontier::Item>>>,
23}
24
25impl Default for Builder {
26    fn default() -> Self {
27        Self {
28            index: HashedMap::default(),
29            inner: Arc::new(frontier::Top::new(frontier::TrackForgotten::No)),
30        }
31    }
32}
33
34/// A finalized epoch builder, ready to be inserted into a [`Tree`].
35#[derive(Derivative, Debug, Clone, Serialize, Deserialize)]
36pub struct Finalized {
37    pub(super) index: HashedMap<StateCommitment, index::within::Epoch>,
38    pub(super) inner: Insert<complete::Top<complete::Tier<complete::Item>>>,
39}
40
41impl Default for Finalized {
42    fn default() -> Self {
43        Builder::default().finalize()
44    }
45}
46
47impl Finalized {
48    /// Get the root hash of this finalized epoch.
49    ///
50    /// Internal hashing is performed lazily to prevent unnecessary intermediary hashes from being
51    /// computed, so the first hash returned after a long sequence of insertions may take more time
52    /// than subsequent calls.
53    ///
54    /// Computed hashes are cached so that subsequent calls without further modification are very
55    /// fast.
56    pub fn root(&self) -> Root {
57        Root(self.inner.hash())
58    }
59}
60
61impl From<Root> for Finalized {
62    fn from(root: Root) -> Self {
63        Self {
64            index: HashedMap::default(),
65            inner: Insert::Hash(root.0),
66        }
67    }
68}
69
70impl From<Builder> for Finalized {
71    fn from(mut builder: Builder) -> Self {
72        builder.finalize()
73    }
74}
75
76/// The root hash of an epoch.
77#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
78#[serde(try_from = "pb::MerkleRoot", into = "pb::MerkleRoot")]
79#[cfg_attr(any(test, feature = "arbitrary"), derive(proptest_derive::Arbitrary))]
80pub struct Root(pub Hash);
81
82impl Root {
83    /// Check if this is the root of an empty finalized block.
84    pub fn is_empty_finalized(&self) -> bool {
85        self.0 == Hash::one()
86    }
87
88    /// Check if this is the root of an empty unfinalized block.
89    pub fn is_empty_unfinalized(&self) -> bool {
90        self.0 == Hash::zero()
91    }
92}
93
94impl From<Root> for Fq {
95    fn from(root: Root) -> Self {
96        root.0.into()
97    }
98}
99
100impl TryFrom<pb::MerkleRoot> for Root {
101    type Error = RootDecodeError;
102
103    fn try_from(root: pb::MerkleRoot) -> Result<Root, Self::Error> {
104        let bytes: [u8; 32] = (&root.inner[..]).try_into().map_err(|_| RootDecodeError)?;
105        let inner = Fq::from_bytes_checked(&bytes).map_err(|_| RootDecodeError)?;
106        Ok(Root(Hash::new(inner)))
107    }
108}
109
110impl From<Root> for pb::MerkleRoot {
111    fn from(root: Root) -> Self {
112        Self {
113            inner: Fq::from(root.0).to_bytes().to_vec(),
114        }
115    }
116}
117
118impl DomainType for Root {
119    type Proto = pb::MerkleRoot;
120}
121
122impl Display for Root {
123    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
124        write!(f, "{}", hex::encode(Fq::from(self.0).to_bytes()))
125    }
126}
127
128impl From<InsertBlockError> for block::Finalized {
129    fn from(error: InsertBlockError) -> Self {
130        error.0
131    }
132}
133
134impl Builder {
135    /// Create a new empty [`epoch::Builder`](Builder).
136    pub fn new() -> Self {
137        Self::default()
138    }
139
140    /// Add a new [`Commitment`] to the most recent block of this [`epoch::Builder`](Builder).
141    ///
142    /// # Errors
143    ///
144    /// Returns [`InsertError`] if either:
145    ///
146    /// - the [`epoch::Builder`](Builder) is full, or
147    /// - the most recent block is full.
148    pub fn insert(
149        &mut self,
150        witness: Witness,
151        commitment: StateCommitment,
152    ) -> Result<(), InsertError> {
153        let item = match witness {
154            Witness::Keep => commitment.into(),
155            Witness::Forget => Hash::of(commitment).into(),
156        };
157
158        // Get the position of the insertion, if it would succeed
159        let position = u32::try_from(self.inner.position().ok_or(InsertError::Full)?)
160            .expect("position of epoch is never greater than `u32::MAX`")
161            .into();
162
163        // Try to insert the commitment into the latest block
164        Arc::make_mut(&mut self.inner)
165            .update(|block| {
166                // Don't insert into a finalized block (this will fail); create a new one instead
167                // (below)
168                if block.is_finalized() {
169                    return None;
170                }
171
172                Some(block.insert(item).map_err(|_| InsertError::BlockFull))
173            })
174            .flatten()
175            // If the latest block was finalized already or doesn't exist, create a new block and
176            // insert into that block
177            .unwrap_or_else(|| {
178                Arc::make_mut(&mut self.inner)
179                    .insert(frontier::Tier::new(item))
180                    .map_err(|_| InsertError::Full)?;
181                Ok(())
182            })?;
183
184        // Keep track of the position of this just-inserted commitment in the index, if it was
185        // slated to be kept
186        if let Witness::Keep = witness {
187            if let Some(replaced) = self.index.insert(commitment, position) {
188                // This case is handled for completeness, but should not happen in
189                // practice because commitments should be unique
190                let forgotten = Arc::make_mut(&mut self.inner).forget(replaced);
191                debug_assert!(forgotten);
192            }
193        }
194
195        Ok(())
196    }
197
198    /// Insert a block into this epoch.
199    ///
200    /// This function can be called on anything that implements `Into<block::Finalized>`; in
201    /// particular, on [`block::Builder`], [`block::Finalized`], and [`block::Root`].
202    pub fn insert_block(
203        &mut self,
204        block: impl Into<block::Finalized>,
205    ) -> Result<block::Root, InsertBlockError> {
206        let block::Finalized { inner, index } = block.into();
207
208        // If the insertion would fail, return an error
209        if self.inner.is_full() {
210            return Err(InsertBlockError(block::Finalized { inner, index }));
211        }
212
213        // Convert the top level inside of the block to a tier that can be slotted into the epoch
214        let inner: frontier::Tier<frontier::Item> = match inner {
215            Insert::Keep(inner) => inner.into(),
216            Insert::Hash(hash) => hash.into(),
217        };
218
219        // Finalize the latest block, if it exists and is not yet finalized -- this means that
220        // position calculations will be correct, since they will start at the next block
221        Arc::make_mut(&mut self.inner).update(|block| block.finalize());
222
223        // Get the block index of the next insertion
224        let index::within::Epoch { block, .. } = u32::try_from(
225            self.inner
226                .position()
227                .expect("epoch must have a position because it is not full"),
228        )
229        .expect("position of epoch is never greater than `u32::MAX`")
230        .into();
231
232        // Calculate the root hash of the block being inserted
233        let block_root = block::Root(inner.hash());
234
235        // Insert the inner tree of the block into the epoch
236        Arc::make_mut(&mut self.inner)
237            .insert(inner)
238            .expect("inserting a block must succeed because epoch is not full");
239
240        // Add the index of all commitments in the block to the epoch index
241        for (c, index::within::Block { commitment }) in index {
242            // If any commitment is repeated, forget the previous one within the tree, since it is
243            // now inaccessible
244            if let Some(replaced) = self
245                .index
246                .insert(c, index::within::Epoch { block, commitment })
247            {
248                // This case is handled for completeness, but should not happen in practice because
249                // commitments should be unique
250                let forgotten = Arc::make_mut(&mut self.inner).forget(replaced);
251                debug_assert!(forgotten);
252            }
253        }
254
255        Ok(block_root)
256    }
257
258    /// Explicitly mark the end of the current block in this epoch, advancing the position to the
259    /// next block.
260    pub fn end_block(&mut self) -> Result<block::Root, InsertBlockError> {
261        // Check to see if the latest block is already finalized, and finalize it if
262        // it is not
263        let (already_finalized, finalized_root) = Arc::make_mut(&mut self.inner)
264            .update(|tier| {
265                let already_finalized = tier.finalize();
266                (already_finalized, block::Root(tier.hash()))
267            })
268            // If the entire epoch is empty, the latest block is considered already finalized
269            .unwrap_or((true, block::Finalized::default().root()));
270
271        // If the latest block was already finalized (i.e. we are at the start of an unfinalized
272        // empty block), insert an empty finalized block
273        if already_finalized {
274            self.insert_block(block::Finalized::default())?;
275        };
276
277        Ok(finalized_root)
278    }
279
280    /// Get the root hash of this epoch builder.
281    ///
282    /// Note that this root hash will differ from the root hash of the finalized epoch.
283    pub fn root(&self) -> Root {
284        Root(self.inner.hash())
285    }
286
287    /// Finalize this epoch builder, returning a finalized epoch and resetting the underlying
288    /// builder to the initial empty state.
289    pub fn finalize(&mut self) -> Finalized {
290        let this = std::mem::take(self);
291
292        // This avoids cloning the arc when we have the only reference to it
293        let inner = Arc::try_unwrap(this.inner).unwrap_or_else(|arc| (*arc).clone());
294
295        let inner = inner.finalize();
296        let index = this.index;
297        Finalized { index, inner }
298    }
299}
penumbra_sdk_tct/epoch.rs

penumbra_sdk_tct/
epoch.rs
