ckb_shared/types/
mod.rs

1#![allow(missing_docs)]
2use ckb_types::core::{BlockNumber, EpochNumberWithFraction};
3use ckb_types::packed::Byte32;
4use ckb_types::prelude::{Entity, FromSliceShouldBeOk, Reader};
5use ckb_types::{BlockNumberAndHash, U256, packed};
6
7pub mod header_map;
8
9#[derive(Clone, Debug, PartialEq, Eq)]
10pub struct HeaderIndexView {
11    hash: Byte32,
12    number: BlockNumber,
13    epoch: EpochNumberWithFraction,
14    timestamp: u64,
15    parent_hash: Byte32,
16    total_difficulty: U256,
17    skip_hash: Option<Byte32>,
18}
19
20impl HeaderIndexView {
21    pub fn new(
22        hash: Byte32,
23        number: BlockNumber,
24        epoch: EpochNumberWithFraction,
25        timestamp: u64,
26        parent_hash: Byte32,
27        total_difficulty: U256,
28    ) -> Self {
29        HeaderIndexView {
30            hash,
31            number,
32            epoch,
33            timestamp,
34            parent_hash,
35            total_difficulty,
36            skip_hash: None,
37        }
38    }
39
40    pub fn hash(&self) -> Byte32 {
41        self.hash.clone()
42    }
43
44    pub fn number(&self) -> BlockNumber {
45        self.number
46    }
47
48    pub fn epoch(&self) -> EpochNumberWithFraction {
49        self.epoch
50    }
51
52    pub fn timestamp(&self) -> u64 {
53        self.timestamp
54    }
55
56    pub fn total_difficulty(&self) -> &U256 {
57        &self.total_difficulty
58    }
59
60    pub fn parent_hash(&self) -> Byte32 {
61        self.parent_hash.clone()
62    }
63
64    pub fn skip_hash(&self) -> Option<&Byte32> {
65        self.skip_hash.as_ref()
66    }
67
68    // deserialize from bytes
69    fn from_slice_should_be_ok(hash: &[u8], slice: &[u8]) -> Self {
70        let hash = packed::Byte32Reader::from_slice_should_be_ok(hash).to_entity();
71        let number = BlockNumber::from_le_bytes(slice[0..8].try_into().expect("stored slice"));
72        let epoch = EpochNumberWithFraction::from_full_value(u64::from_le_bytes(
73            slice[8..16].try_into().expect("stored slice"),
74        ));
75        let timestamp = u64::from_le_bytes(slice[16..24].try_into().expect("stored slice"));
76        let parent_hash = packed::Byte32Reader::from_slice_should_be_ok(&slice[24..56]).to_entity();
77        let total_difficulty = U256::from_little_endian(&slice[56..88]).expect("stored slice");
78        let skip_hash = if slice.len() == 120 {
79            Some(packed::Byte32Reader::from_slice_should_be_ok(&slice[88..120]).to_entity())
80        } else {
81            None
82        };
83        Self {
84            hash,
85            number,
86            epoch,
87            timestamp,
88            parent_hash,
89            total_difficulty,
90            skip_hash,
91        }
92    }
93
94    // serialize all fields except `hash` to bytes
95    fn to_vec(&self) -> Vec<u8> {
96        let mut v = Vec::new();
97        v.extend_from_slice(self.number.to_le_bytes().as_slice());
98        v.extend_from_slice(self.epoch.full_value().to_le_bytes().as_slice());
99        v.extend_from_slice(self.timestamp.to_le_bytes().as_slice());
100        v.extend_from_slice(self.parent_hash.as_slice());
101        v.extend_from_slice(self.total_difficulty.to_le_bytes().as_slice());
102        if let Some(ref skip_hash) = self.skip_hash {
103            v.extend_from_slice(skip_hash.as_slice());
104        }
105        v
106    }
107
108    pub fn build_skip<F, G>(&mut self, tip_number: BlockNumber, get_header_view: F, fast_scanner: G)
109    where
110        F: Fn(&Byte32, bool) -> Option<HeaderIndexView>,
111        G: Fn(BlockNumber, BlockNumberAndHash) -> Option<HeaderIndexView>,
112    {
113        if self.number == 0 {
114            return;
115        }
116        self.skip_hash = self
117            .get_ancestor(
118                tip_number,
119                get_skip_height(self.number()),
120                get_header_view,
121                fast_scanner,
122            )
123            .map(|header| header.hash());
124    }
125
126    pub fn get_ancestor<F, G>(
127        &self,
128        tip_number: BlockNumber,
129        number: BlockNumber,
130        get_header_view: F,
131        fast_scanner: G,
132    ) -> Option<HeaderIndexView>
133    where
134        F: Fn(&Byte32, bool) -> Option<HeaderIndexView>,
135        G: Fn(BlockNumber, BlockNumberAndHash) -> Option<HeaderIndexView>,
136    {
137        if number > self.number() {
138            return None;
139        }
140
141        let mut current = self.clone();
142        let mut number_walk = current.number();
143        while number_walk > number {
144            let number_skip = get_skip_height(number_walk);
145            let number_skip_prev = get_skip_height(number_walk - 1);
146            let store_first = current.number() <= tip_number;
147            match current.skip_hash {
148                Some(ref hash)
149                    if number_skip == number
150                        || (number_skip > number
151                            && !(number_skip_prev + 2 < number_skip
152                                && number_skip_prev >= number)) =>
153                {
154                    // Only follow skip if parent->skip isn't better than skip->parent
155                    current = get_header_view(hash, store_first)?;
156                    number_walk = number_skip;
157                }
158                _ => {
159                    current = get_header_view(&current.parent_hash(), store_first)?;
160                    number_walk -= 1;
161                }
162            }
163            if let Some(target) = fast_scanner(number, (current.number(), current.hash()).into()) {
164                current = target;
165                break;
166            }
167        }
168        Some(current)
169    }
170
171    pub fn as_header_index(&self) -> HeaderIndex {
172        HeaderIndex::new(self.number(), self.hash(), self.total_difficulty().clone())
173    }
174
175    pub fn number_and_hash(&self) -> BlockNumberAndHash {
176        (self.number(), self.hash()).into()
177    }
178
179    pub fn is_better_than(&self, total_difficulty: &U256) -> bool {
180        self.total_difficulty() > total_difficulty
181    }
182}
183
184impl From<(ckb_types::core::HeaderView, U256)> for HeaderIndexView {
185    fn from((header, total_difficulty): (ckb_types::core::HeaderView, U256)) -> Self {
186        HeaderIndexView {
187            hash: header.hash(),
188            number: header.number(),
189            epoch: header.epoch(),
190            timestamp: header.timestamp(),
191            parent_hash: header.parent_hash(),
192            total_difficulty,
193            skip_hash: None,
194        }
195    }
196}
197
198#[derive(Clone, Debug, PartialEq, Eq)]
199pub struct HeaderIndex {
200    number: BlockNumber,
201    hash: Byte32,
202    total_difficulty: U256,
203}
204
205impl HeaderIndex {
206    pub fn new(number: BlockNumber, hash: Byte32, total_difficulty: U256) -> Self {
207        HeaderIndex {
208            number,
209            hash,
210            total_difficulty,
211        }
212    }
213
214    pub fn number(&self) -> BlockNumber {
215        self.number
216    }
217
218    pub fn hash(&self) -> Byte32 {
219        self.hash.clone()
220    }
221
222    pub fn total_difficulty(&self) -> &U256 {
223        &self.total_difficulty
224    }
225
226    pub fn number_and_hash(&self) -> BlockNumberAndHash {
227        (self.number(), self.hash()).into()
228    }
229
230    pub fn is_better_chain(&self, other: &Self) -> bool {
231        self.is_better_than(other.total_difficulty())
232    }
233
234    pub fn is_better_than(&self, other_total_difficulty: &U256) -> bool {
235        self.total_difficulty() > other_total_difficulty
236    }
237}
238
239// Compute what height to jump back to with the skip pointer.
240fn get_skip_height(height: BlockNumber) -> BlockNumber {
241    // Turn the lowest '1' bit in the binary representation of a number into a '0'.
242    fn invert_lowest_one(n: i64) -> i64 {
243        n & (n - 1)
244    }
245
246    if height < 2 {
247        return 0;
248    }
249
250    // Determine which height to jump back to. Any number strictly lower than height is acceptable,
251    // but the following expression seems to perform well in simulations (max 110 steps to go back
252    // up to 2**18 blocks).
253    if (height & 1) > 0 {
254        invert_lowest_one(invert_lowest_one(height as i64 - 1)) as u64 + 1
255    } else {
256        invert_lowest_one(height as i64) as u64
257    }
258}
259
260pub const SHRINK_THRESHOLD: usize = 300;
ckb_shared/types/mod.rs

ckb_shared/types/
mod.rs
