hotshot_query_service/merklized_state/
data_source.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the HotShot Query Service library.
3//
4// This program is free software: you can redistribute it and/or modify it under the terms of the GNU
5// General Public License as published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7// This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
8// even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
9// General Public License for more details.
10// You should have received a copy of the GNU General Public License along with this program. If not,
11// see <https://www.gnu.org/licenses/>.
12
13//! Data for the [`merklized_state`](super) API.
14//!
15//! This module facilitates storing the state of a Merkle Tree at a specific point in time
16//! and provides methods for querying and reconstructing the snapshot.
17//!
18
19use std::{cmp::Ordering, fmt::Debug, str::FromStr};
20
21use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
22use async_trait::async_trait;
23use derivative::Derivative;
24use derive_more::Display;
25use hotshot_types::traits::node_implementation::NodeType;
26use jf_merkle_tree::{
27    prelude::MerkleProof, DigestAlgorithm, Element, ForgetableMerkleTreeScheme, Index,
28    MerkleCommitment, NodeValue, ToTraversalPath,
29};
30use serde::{de::DeserializeOwned, Serialize};
31use tagged_base64::TaggedBase64;
32
33use crate::QueryResult;
34
35/// This trait defines methods that a data source should implement
36/// It enables retrieval of the membership path for a leaf node, which can be used to reconstruct the Merkle tree state.
37#[async_trait]
38pub trait MerklizedStateDataSource<Types, State, const ARITY: usize>
39where
40    Types: NodeType,
41    State: MerklizedState<Types, ARITY>,
42{
43    async fn get_path(
44        &self,
45        snapshot: Snapshot<Types, State, ARITY>,
46        key: State::Key,
47    ) -> QueryResult<MerkleProof<State::Entry, State::Key, State::T, ARITY>>;
48}
49
50/// This trait defines methods for updating the storage with the merkle tree state.
51#[async_trait]
52pub trait UpdateStateData<Types: NodeType, State: MerklizedState<Types, ARITY>, const ARITY: usize>:
53    Send + Sync
54{
55    async fn set_last_state_height(&mut self, height: usize) -> anyhow::Result<()>;
56    async fn insert_merkle_nodes(
57        &mut self,
58        path: MerkleProof<State::Entry, State::Key, State::T, ARITY>,
59        traversal_path: Vec<usize>,
60        block_number: u64,
61    ) -> anyhow::Result<()>;
62}
63
64#[async_trait]
65pub trait MerklizedStateHeightPersistence {
66    async fn get_last_state_height(&self) -> QueryResult<usize>;
67}
68
69type StateCommitment<Types, T, const ARITY: usize> = <T as MerklizedState<Types, ARITY>>::Commit;
70
71/// Snapshot can be queried by block height (index) or merkle tree commitment
72#[derive(Derivative, Display)]
73#[derivative(Ord = "feature_allow_slow_enum")]
74#[derivative(
75    Copy(bound = ""),
76    Debug(bound = ""),
77    PartialEq(bound = ""),
78    Eq(bound = ""),
79    Ord(bound = ""),
80    Hash(bound = "")
81)]
82pub enum Snapshot<Types: NodeType, T: MerklizedState<Types, ARITY>, const ARITY: usize> {
83    #[display("{_0}")]
84    Commit(StateCommitment<Types, T, ARITY>),
85    #[display("{_0}")]
86    Index(u64),
87}
88
89impl<T: MerklizedState<Types, ARITY>, Types: NodeType, const ARITY: usize> Clone
90    for Snapshot<Types, T, ARITY>
91{
92    fn clone(&self) -> Self {
93        *self
94    }
95}
96
97impl<T: MerklizedState<Types, ARITY>, Types: NodeType, const ARITY: usize> PartialOrd
98    for Snapshot<Types, T, ARITY>
99{
100    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
101        Some(self.cmp(other))
102    }
103}
104
105/// This trait should be implemented by the MerkleTree that the module is initialized for.
106/// It defines methods utilized by the module.
107pub trait MerklizedState<Types, const ARITY: usize>:
108    ForgetableMerkleTreeScheme<Commitment = Self::Commit> + Send + Sync + Clone + 'static
109where
110    Types: NodeType,
111{
112    type Key: Index
113        + Send
114        + Sync
115        + Serialize
116        + ToTraversalPath<ARITY>
117        + FromStr
118        + DeserializeOwned
119        + Display
120        + CanonicalSerialize
121        + CanonicalDeserialize;
122    type Entry: Element
123        + Send
124        + Sync
125        + Serialize
126        + DeserializeOwned
127        + CanonicalSerialize
128        + CanonicalDeserialize;
129    type T: NodeValue + Send;
130    type Commit: MerkleCommitment<Self::T>
131        + Send
132        + for<'a> TryFrom<&'a TaggedBase64>
133        + Display
134        + Debug
135        + Into<TaggedBase64>;
136    type Digest: DigestAlgorithm<Self::Entry, Self::Key, Self::T>;
137
138    /// Retrieves the name of the state being queried.
139    fn state_type() -> &'static str;
140
141    /// Retrieves the field in the header containing the Merkle tree commitment
142    /// for the state implementing this trait.
143    fn header_state_commitment_field() -> &'static str;
144
145    /// Get the height of the tree
146    fn tree_height() -> usize;
147
148    /// Insert a forgotten path into the tree.
149    fn insert_path(
150        &mut self,
151        key: Self::Key,
152        proof: &MerkleProof<Self::Entry, Self::Key, Self::T, ARITY>,
153    ) -> anyhow::Result<()>;
154}
hotshot_query_service/merklized_state/data_source.rs

hotshot_query_service/merklized_state/
data_source.rs
