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::with_trait::Display;
25use hotshot_types::traits::node_implementation::NodeType;
26use jf_merkle_tree_compat::{
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    async fn insert_merkle_nodes_batch(
63        &mut self,
64        proofs: Vec<(
65            MerkleProof<State::Entry, State::Key, State::T, ARITY>,
66            Vec<usize>,
67        )>,
68        block_number: u64,
69    ) -> anyhow::Result<()>;
70}
71
72#[async_trait]
73pub trait MerklizedStateHeightPersistence {
74    async fn get_last_state_height(&self) -> QueryResult<usize>;
75}
76
77type StateCommitment<Types, T, const ARITY: usize> = <T as MerklizedState<Types, ARITY>>::Commit;
78
79/// Snapshot can be queried by block height (index) or merkle tree commitment
80#[derive(Derivative, Display)]
81#[derivative(Ord = "feature_allow_slow_enum")]
82#[derivative(
83    Copy(bound = ""),
84    Debug(bound = ""),
85    PartialEq(bound = ""),
86    Eq(bound = ""),
87    Ord(bound = ""),
88    Hash(bound = "")
89)]
90pub enum Snapshot<Types: NodeType, T: MerklizedState<Types, ARITY>, const ARITY: usize> {
91    #[display("{_0}")]
92    Commit(StateCommitment<Types, T, ARITY>),
93    #[display("{_0}")]
94    Index(u64),
95}
96
97impl<T: MerklizedState<Types, ARITY>, Types: NodeType, const ARITY: usize> Clone
98    for Snapshot<Types, T, ARITY>
99{
100    fn clone(&self) -> Self {
101        *self
102    }
103}
104
105impl<T: MerklizedState<Types, ARITY>, Types: NodeType, const ARITY: usize> PartialOrd
106    for Snapshot<Types, T, ARITY>
107{
108    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
109        Some(self.cmp(other))
110    }
111}
112
113/// This trait should be implemented by the MerkleTree that the module is initialized for.
114/// It defines methods utilized by the module.
115pub trait MerklizedState<Types, const ARITY: usize>:
116    ForgetableMerkleTreeScheme<Commitment = Self::Commit> + Send + Sync + Clone + 'static
117where
118    Types: NodeType,
119{
120    type Key: Index
121        + Send
122        + Sync
123        + Serialize
124        + ToTraversalPath<ARITY>
125        + FromStr
126        + DeserializeOwned
127        + Display
128        + CanonicalSerialize
129        + CanonicalDeserialize;
130    type Entry: Element
131        + Send
132        + Sync
133        + Serialize
134        + DeserializeOwned
135        + CanonicalSerialize
136        + CanonicalDeserialize;
137    type T: NodeValue + Send;
138    type Commit: MerkleCommitment<Self::T>
139        + Send
140        + for<'a> TryFrom<&'a TaggedBase64>
141        + Display
142        + Debug
143        + Into<TaggedBase64>;
144    type Digest: DigestAlgorithm<Self::Entry, Self::Key, Self::T>;
145
146    /// Retrieves the name of the state being queried.
147    fn state_type() -> &'static str;
148
149    /// Retrieves the field in the header containing the Merkle tree commitment
150    /// for the state implementing this trait.
151    fn header_state_commitment_field() -> &'static str;
152
153    /// Get the height of the tree
154    fn tree_height() -> usize;
155
156    /// Insert a forgotten path into the tree.
157    fn insert_path(
158        &mut self,
159        key: Self::Key,
160        proof: &MerkleProof<Self::Entry, Self::Key, Self::T, ARITY>,
161    ) -> anyhow::Result<()>;
162}
hotshot_query_service/merklized_state/data_source.rs

hotshot_query_service/merklized_state/
data_source.rs
