node/transition_frontier/candidate/
transition_frontier_candidate_state.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use mina_p2p_messages::v2::StateHash;
4use serde::{Deserialize, Serialize};
5
6use openmina_core::{
7    block::ArcBlockWithHash,
8    consensus::{
9        consensus_take, ConsensusLongRangeForkDecisionReason, ConsensusShortRangeForkDecisionReason,
10    },
11};
12
13use crate::{
14    snark::block_verify::SnarkBlockVerifyId, transition_frontier::TransitionFrontierState,
15};
16
17#[derive(Serialize, Deserialize, Debug, Clone)]
18pub enum ConsensusShortRangeForkDecision {
19    TakeNoBestTip,
20    Take(ConsensusShortRangeForkDecisionReason),
21    Keep(ConsensusShortRangeForkDecisionReason),
22}
23
24impl ConsensusShortRangeForkDecision {
25    pub fn use_as_best_tip(&self) -> bool {
26        matches!(self, Self::TakeNoBestTip | Self::Take(_))
27    }
28}
29
30#[derive(Serialize, Deserialize, Debug, Clone)]
31pub enum ConsensusLongRangeForkDecision {
32    Keep(ConsensusLongRangeForkDecisionReason),
33    Take(ConsensusLongRangeForkDecisionReason),
34}
35
36impl ConsensusLongRangeForkDecision {
37    pub fn use_as_best_tip(&self) -> bool {
38        matches!(self, Self::Take(_))
39    }
40}
41
42#[derive(Serialize, Deserialize, Debug, Clone)]
43pub enum TransitionFrontierCandidateStatus {
44    Received {
45        time: redux::Timestamp,
46    },
47    Prevalidated,
48    SnarkVerifyPending {
49        time: redux::Timestamp,
50        req_id: SnarkBlockVerifyId,
51    },
52    SnarkVerifySuccess {
53        time: redux::Timestamp,
54    },
55}
56
57impl TransitionFrontierCandidateStatus {
58    pub fn is_received(&self) -> bool {
59        matches!(self, Self::Received { .. })
60    }
61
62    pub fn is_prevalidated(&self) -> bool {
63        matches!(self, Self::Prevalidated)
64    }
65
66    pub fn is_snark_verify_pending(&self) -> bool {
67        matches!(self, Self::SnarkVerifyPending { .. })
68    }
69
70    pub fn is_snark_verify_success(&self) -> bool {
71        matches!(self, Self::SnarkVerifySuccess { .. })
72    }
73
74    pub fn is_pending(&self) -> bool {
75        matches!(self, Self::SnarkVerifyPending { .. })
76    }
77}
78
79#[derive(Serialize, Deserialize, Debug, Clone)]
80pub struct TransitionFrontierCandidateState {
81    pub block: ArcBlockWithHash,
82    pub status: TransitionFrontierCandidateStatus,
83    pub chain_proof: Option<(Vec<StateHash>, ArcBlockWithHash)>,
84}
85
86impl Ord for TransitionFrontierCandidateState {
87    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
88        if self.eq(other) {
89            return std::cmp::Ordering::Equal;
90        }
91        let is_candidate_better = consensus_take(
92            self.block.consensus_state(),
93            other.block.consensus_state(),
94            self.block.hash(),
95            other.block.hash(),
96        );
97        match is_candidate_better {
98            true => std::cmp::Ordering::Less,
99            false => std::cmp::Ordering::Greater,
100        }
101    }
102}
103
104impl PartialOrd for TransitionFrontierCandidateState {
105    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
106        Some(self.cmp(other))
107    }
108}
109
110impl Eq for TransitionFrontierCandidateState {}
111
112impl PartialEq for TransitionFrontierCandidateState {
113    fn eq(&self, other: &Self) -> bool {
114        self.block.hash() == other.block.hash()
115    }
116}
117
118impl TransitionFrontierCandidateState {
119    pub fn height(&self) -> u32 {
120        self.block.height()
121    }
122}
123
124#[derive(Serialize, Deserialize, Debug, Clone, Default)]
125pub struct TransitionFrontierCandidatesState {
126    /// Maintains an ordered list of transition frontier Candidates,
127    /// ordered using consensus rules worst to best.
128    ordered: BTreeSet<TransitionFrontierCandidateState>,
129    /// Candidate block hashes, which failed either the prevalidation
130    /// or block proof verification. We move them here so that they
131    /// consume less memory while still preventing us from triggering
132    /// revalidation for an invalid block if we receive it on p2p again.
133    invalid: BTreeMap<StateHash, u32>,
134}
135
136impl TransitionFrontierCandidatesState {
137    pub fn new() -> Self {
138        Self::default()
139    }
140
141    pub fn contains(&self, hash: &StateHash) -> bool {
142        self.invalid.contains_key(hash) || self.get(hash).is_some()
143    }
144
145    pub(super) fn get(&self, hash: &StateHash) -> Option<&TransitionFrontierCandidateState> {
146        self.ordered.iter().rev().find(|s| s.block.hash() == hash)
147    }
148
149    pub(super) fn add(
150        &mut self,
151        time: redux::Timestamp,
152        block: ArcBlockWithHash,
153        chain_proof: Option<(Vec<StateHash>, ArcBlockWithHash)>,
154    ) {
155        self.ordered.insert(TransitionFrontierCandidateState {
156            block,
157            status: TransitionFrontierCandidateStatus::Received { time },
158            chain_proof,
159        });
160    }
161
162    fn update(
163        &mut self,
164        hash: &StateHash,
165        update: impl FnOnce(TransitionFrontierCandidateState) -> TransitionFrontierCandidateState,
166    ) -> bool {
167        let Some(state) = self.get(hash).cloned() else {
168            return false;
169        };
170        self.ordered.remove(&state);
171        self.ordered.insert(update(state));
172        true
173    }
174
175    pub(super) fn update_status(
176        &mut self,
177        hash: &StateHash,
178        update: impl FnOnce(TransitionFrontierCandidateStatus) -> TransitionFrontierCandidateStatus,
179    ) -> bool {
180        self.update(hash, move |mut state| {
181            state.status = update(state.status);
182            state
183        })
184    }
185
186    pub(super) fn invalidate(&mut self, hash: &StateHash, is_forever_invalid: bool) {
187        self.ordered.retain(|s| {
188            if s.block.hash() == hash {
189                if is_forever_invalid {
190                    self.invalid.insert(hash.clone(), s.block.global_slot());
191                }
192                false
193            } else {
194                true
195            }
196        });
197    }
198
199    pub(super) fn set_chain_proof(
200        &mut self,
201        hash: &StateHash,
202        chain_proof: (Vec<StateHash>, ArcBlockWithHash),
203    ) -> bool {
204        self.update(hash, move |mut s| {
205            s.chain_proof = Some(chain_proof);
206            s
207        })
208    }
209
210    pub(super) fn prune(&mut self) {
211        let mut has_reached_best_candidate = false;
212        let Some(best_candidate_hash) = self.best_verified().map(|s| s.block.hash().clone()) else {
213            return;
214        };
215
216        // prune all blocks that are worse(consensus-wise) than the best
217        // verified candidate.
218        self.ordered.retain(|s| {
219            if s.block.hash() == &best_candidate_hash {
220                // prune all invalid block hashes which are for older
221                // slots than the current best candidate.
222                let best_candidate_slot = s.block.global_slot();
223                self.invalid.retain(|_, slot| *slot >= best_candidate_slot);
224
225                has_reached_best_candidate = true;
226            }
227
228            has_reached_best_candidate
229        });
230    }
231
232    pub(super) fn best(&self) -> Option<&TransitionFrontierCandidateState> {
233        self.ordered.last()
234    }
235
236    pub fn best_verified(&self) -> Option<&TransitionFrontierCandidateState> {
237        self.ordered
238            .iter()
239            .rev()
240            .find(|s| s.status.is_snark_verify_success())
241    }
242
243    pub fn is_chain_proof_needed(&self, hash: &StateHash) -> bool {
244        self.get(hash).is_some_and(|s| s.chain_proof.is_none())
245    }
246
247    pub fn best_verified_block(&self) -> Option<&ArcBlockWithHash> {
248        self.best_verified().map(|s| &s.block)
249    }
250
251    pub fn best_verified_block_chain_proof(
252        &self,
253        transition_frontier: &TransitionFrontierState,
254    ) -> Option<(Vec<StateHash>, ArcBlockWithHash)> {
255        self.block_chain_proof(self.best_verified()?, transition_frontier)
256    }
257
258    fn block_chain_proof(
259        &self,
260        block_state: &TransitionFrontierCandidateState,
261        transition_frontier: &TransitionFrontierState,
262    ) -> Option<(Vec<StateHash>, ArcBlockWithHash)> {
263        let pred_hash = block_state.block.pred_hash();
264        block_state.chain_proof.clone().or_else(|| {
265            let old_best_tip = transition_frontier.best_tip()?;
266            let mut iter = transition_frontier.best_chain.iter();
267            if old_best_tip.hash() == pred_hash {
268                if old_best_tip.height() > old_best_tip.constants().k.as_u32() {
269                    iter.next();
270                }
271                let root_block = iter.next()?.block_with_hash().clone();
272                let hashes = iter.map(|b| b.hash().clone()).collect();
273                Some((hashes, root_block))
274            } else if old_best_tip.pred_hash() == pred_hash {
275                let root_block = iter.next()?.block_with_hash().clone();
276                let hashes = iter.rev().skip(1).rev().map(|b| b.hash().clone()).collect();
277                Some((hashes, root_block))
278            } else {
279                None
280            }
281        })
282    }
283}