ckb_proposal_table/
lib.rs

1//! The ckb proposal-table design for two-step-transaction-confirmation
2
3use ckb_chain_spec::consensus::ProposalWindow;
4use ckb_types::{core::BlockNumber, packed::ProposalShortId};
5use std::collections::{BTreeMap, HashSet};
6use std::ops::Bound;
7
8#[cfg(test)]
9mod tests;
10
11/// A view captures point-time proposal set, representing on-chain proposed transaction pool,
12/// stored in the memory so that there is no need to fetch on hard disk, create by ProposalTable finalize method
13/// w_close and w_far define the closest and farthest on-chain distance between a transaction’s proposal and commitment.
14#[derive(Default, Clone, Debug)]
15pub struct ProposalView {
16    pub(crate) gap: HashSet<ProposalShortId>,
17    pub(crate) set: HashSet<ProposalShortId>,
18}
19
20impl ProposalView {
21    /// Create new ProposalView
22    pub fn new(gap: HashSet<ProposalShortId>, set: HashSet<ProposalShortId>) -> ProposalView {
23        ProposalView { gap, set }
24    }
25
26    /// Return proposals between w_close and tip
27    pub fn gap(&self) -> &HashSet<ProposalShortId> {
28        &self.gap
29    }
30
31    /// Return proposals between w_close and w_far
32    pub fn set(&self) -> &HashSet<ProposalShortId> {
33        &self.set
34    }
35
36    /// Returns true if the proposals set between w_close and w_far contains the id.
37    pub fn contains_proposed(&self, id: &ProposalShortId) -> bool {
38        self.set.contains(id)
39    }
40
41    /// Returns true if the proposals set between w_close and tip contains the id.
42    pub fn contains_gap(&self, id: &ProposalShortId) -> bool {
43        self.gap.contains(id)
44    }
45}
46
47/// A Table record proposals set in number-ids pairs
48#[derive(Debug, PartialEq, Clone, Eq)]
49pub struct ProposalTable {
50    pub(crate) table: BTreeMap<BlockNumber, HashSet<ProposalShortId>>,
51    pub(crate) proposal_window: ProposalWindow,
52}
53
54impl ProposalTable {
55    /// Create new ProposalTable from ProposalWindow
56    pub fn new(proposal_window: ProposalWindow) -> Self {
57        ProposalTable {
58            proposal_window,
59            table: BTreeMap::default(),
60        }
61    }
62
63    /// Inserts a number-ids pair into the table.
64    /// If the TABLE did not have this number present, true is returned.
65    /// If the map did have this number present, the proposal set is updated.
66    pub fn insert(&mut self, number: BlockNumber, ids: HashSet<ProposalShortId>) -> bool {
67        self.table.insert(number, ids).is_none()
68    }
69
70    /// Removes a proposal set from the table,　returning the set at the number if the number was previously in the table
71    ///
72    /// # Examples
73    ///
74    /// ```
75    /// use ckb_chain_spec::consensus::ProposalWindow;
76    /// use ckb_proposal_table::ProposalTable;
77    ///
78    /// let window = ProposalWindow(2, 10);
79    /// let mut table = ProposalTable::new(window);
80    /// assert_eq!(table.remove(1), None);
81    /// ```
82    pub fn remove(&mut self, number: BlockNumber) -> Option<HashSet<ProposalShortId>> {
83        self.table.remove(&number)
84    }
85
86    /// Return referent of internal BTreeMap contains all proposal set
87    pub fn all(&self) -> &BTreeMap<BlockNumber, HashSet<ProposalShortId>> {
88        &self.table
89    }
90
91    /// Update table by proposal window move forward, drop outdated proposal set
92    /// Return removed proposal ids set and new ProposalView
93    pub fn finalize(
94        &mut self,
95        origin: &ProposalView,
96        number: BlockNumber,
97    ) -> (HashSet<ProposalShortId>, ProposalView) {
98        let candidate_number = number + 1;
99        let proposal_start = candidate_number.saturating_sub(self.proposal_window.farthest());
100        let proposal_end = candidate_number.saturating_sub(self.proposal_window.closest());
101
102        if proposal_start > 1 {
103            self.table = self.table.split_off(&proposal_start);
104        }
105
106        ckb_logger::trace!("[proposal_finalize] table {:?}", self.table);
107
108        // - if candidate_number <= self.proposal_window.closest()
109        //      new_ids = []
110        //      gap = [1..candidate_number]
111        // - else
112        //      new_ids = [candidate_number- farthest..= candidate_number- closest]
113        //      gap = [candidate_number- closest + 1..candidate_number]
114        // - end
115        let (new_ids, gap) = if candidate_number <= self.proposal_window.closest() {
116            (
117                HashSet::new(),
118                self.table
119                    .range((Bound::Unbounded, Bound::Included(&number)))
120                    .flat_map(|pair| pair.1)
121                    .cloned()
122                    .collect(),
123            )
124        } else {
125            (
126                self.table
127                    .range((
128                        Bound::Included(&proposal_start),
129                        Bound::Included(&proposal_end),
130                    ))
131                    .flat_map(|pair| pair.1)
132                    .cloned()
133                    .collect(),
134                self.table
135                    .range((Bound::Excluded(&proposal_end), Bound::Included(&number)))
136                    .flat_map(|pair| pair.1)
137                    .cloned()
138                    .collect(),
139            )
140        };
141
142        let removed_ids: HashSet<ProposalShortId> =
143            origin.set().difference(&new_ids).cloned().collect();
144        ckb_logger::trace!(
145            "[proposal_finalize] number {} proposal_start {}----proposal_end {}",
146            number,
147            proposal_start,
148            proposal_end
149        );
150        ckb_logger::trace!(
151            "[proposal_finalize] number {} new_ids {:?}----removed_ids {:?}",
152            number,
153            new_ids,
154            removed_ids
155        );
156        (removed_ids, ProposalView::new(gap, new_ids))
157    }
158}
ckb_proposal_table/lib.rs

ckb_proposal_table/
lib.rs
