kyoto/chain/
mod.rs

1//! Structures and checkpoints related to the blockchain.
2//!
3//! Notably, [`checkpoints`] contains known Bitcoin block hashes and heights with significant work, so Kyoto nodes do not have to sync from genesis.
4pub(crate) mod block_queue;
5mod cfheader_batch;
6#[allow(clippy::module_inception)]
7pub(crate) mod chain;
8/// Expected block header checkpoints and corresponding structure.
9pub mod checkpoints;
10/// Errors associated with the blockchain representation.
11#[allow(dead_code)]
12pub(crate) mod error;
13pub(crate) mod graph;
14pub(crate) mod header_batch;
15
16use std::collections::HashMap;
17
18use bitcoin::constants::SUBSIDY_HALVING_INTERVAL;
19use bitcoin::hashes::{sha256d, Hash};
20use bitcoin::Amount;
21use bitcoin::{
22    bip158::BlockFilter, block::Header, params::Params, BlockHash, FilterHash, FilterHeader,
23    ScriptBuf,
24};
25
26use crate::network::PeerId;
27
28use cfheader_batch::CFHeaderBatch;
29use error::FilterError;
30
31type Height = u32;
32
33/// A block header with associated height.
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35pub struct IndexedHeader {
36    /// The height in the blockchain for this header.
37    pub height: u32,
38    /// The block header.
39    pub header: Header,
40}
41
42impl std::cmp::PartialOrd for IndexedHeader {
43    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
44        Some(self.cmp(other))
45    }
46}
47
48impl std::cmp::Ord for IndexedHeader {
49    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
50        self.height.cmp(&other.height)
51    }
52}
53
54impl IndexedHeader {
55    pub(crate) fn new(height: u32, header: Header) -> Self {
56        Self { height, header }
57    }
58}
59
60impl IndexedHeader {
61    /// The block hash associated with this header.
62    pub fn block_hash(&self) -> BlockHash {
63        self.header.block_hash()
64    }
65
66    /// The previous block hash.
67    pub fn prev_blockhash(&self) -> BlockHash {
68        self.header.prev_blockhash
69    }
70}
71
72#[derive(Debug, Clone, PartialEq, Eq)]
73pub(crate) enum HeaderChainChanges {
74    Extended(u32),
75    Reorg { height: u32, hashes: Vec<BlockHash> },
76    ForkAdded { tip: IndexedHeader },
77    Duplicate,
78}
79
80#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
81pub(crate) struct FilterCommitment {
82    pub header: FilterHeader,
83    pub filter_hash: FilterHash,
84}
85
86#[derive(Debug, Clone)]
87pub(crate) struct FilterRequestState {
88    pub last_filter_request: Option<FilterRequest>,
89    pub last_filter_header_request: Option<FilterHeaderRequest>,
90    pub pending_batch: Option<(PeerId, CFHeaderBatch)>,
91    pub agreement_state: FilterHeaderAgreements,
92}
93
94impl FilterRequestState {
95    pub(crate) fn new(required: u8) -> Self {
96        Self {
97            last_filter_request: None,
98            last_filter_header_request: None,
99            pending_batch: None,
100            agreement_state: FilterHeaderAgreements::new(required),
101        }
102    }
103}
104
105#[derive(Debug, Clone, Copy)]
106pub(crate) struct FilterRequest {
107    #[allow(unused)]
108    pub start_height: u32,
109    pub stop_hash: BlockHash,
110}
111
112#[derive(Debug, Clone, Copy)]
113pub(crate) struct FilterHeaderRequest {
114    pub start_height: u32,
115    pub stop_hash: BlockHash,
116    pub expected_prev_filter_header: Option<FilterHeader>,
117}
118
119#[derive(Debug, Clone, Copy, PartialEq, Eq)]
120pub(crate) struct FilterHeaderAgreements {
121    current: u8,
122    required: u8,
123}
124
125impl FilterHeaderAgreements {
126    pub(crate) fn new(required: u8) -> Self {
127        Self {
128            current: 0,
129            required,
130        }
131    }
132
133    pub(crate) fn got_agreement(&mut self) {
134        self.current += 1;
135    }
136
137    pub(crate) fn enough_agree(&self) -> bool {
138        self.current.ge(&self.required)
139    }
140
141    pub(crate) fn reset_agreements(&mut self) {
142        self.current = 0;
143    }
144}
145
146#[derive(Debug, Clone, Copy, PartialEq, Eq)]
147pub(crate) enum CFHeaderChanges {
148    AddedToQueue,
149    Extended,
150    // Unfortunately, auditing each peer by reconstruction the filter would be costly in network
151    // and compute. Instead it is easier to disconnect from all peers and try again.
152    Conflict,
153}
154
155#[derive(Debug, Clone, Copy, PartialEq, Eq)]
156pub(crate) struct FilterCheck {
157    // This filter was for the `stop_hash`
158    pub(crate) was_last_in_batch: bool,
159}
160
161#[derive(Debug, Clone, PartialEq, Eq)]
162pub(crate) struct Filter {
163    filter_hash: FilterHash,
164    block_hash: BlockHash,
165    block_filter: BlockFilter,
166}
167
168#[allow(dead_code)]
169impl Filter {
170    pub fn new(contents: Vec<u8>, block_hash: BlockHash) -> Self {
171        let hash = sha256d::Hash::hash(&contents);
172        let filter_hash = FilterHash::from_raw_hash(hash);
173        let block_filter = BlockFilter::new(&contents);
174        Self {
175            filter_hash,
176            block_hash,
177            block_filter,
178        }
179    }
180
181    pub fn filter_hash(&self) -> &FilterHash {
182        &self.filter_hash
183    }
184
185    pub fn block_hash(&self) -> &BlockHash {
186        &self.block_hash
187    }
188
189    pub fn contains_any<'a>(
190        &'a self,
191        scripts: impl Iterator<Item = &'a ScriptBuf>,
192    ) -> Result<bool, FilterError> {
193        self.block_filter
194            .match_any(&self.block_hash, scripts.map(|script| script.to_bytes()))
195            .map_err(|_| FilterError::IORead)
196    }
197
198    pub fn into_filter(self) -> BlockFilter {
199        self.block_filter
200    }
201
202    pub fn contents(self) -> Vec<u8> {
203        self.block_filter.content
204    }
205}
206
207#[derive(Debug)]
208pub(crate) struct HeightMonitor {
209    map: HashMap<PeerId, Height>,
210}
211
212impl HeightMonitor {
213    pub(crate) fn new() -> Self {
214        Self {
215            map: HashMap::new(),
216        }
217    }
218
219    pub(crate) fn max(&self) -> Option<Height> {
220        self.map.values().copied().max()
221    }
222
223    pub(crate) fn retain(&mut self, peers: &[PeerId]) {
224        self.map.retain(|peer_id, _| peers.contains(peer_id));
225    }
226
227    pub(crate) fn insert(&mut self, peer_id: PeerId, height: Height) {
228        self.map.insert(peer_id, height);
229    }
230
231    pub(crate) fn increment(&mut self, peer_id: PeerId) {
232        if let Some(height) = self.map.get_mut(&peer_id) {
233            *height = height.saturating_add(1);
234        }
235    }
236}
237
238// Attributes of a height in the Bitcoin blockchain.
239trait HeightExt: Clone + Copy + std::hash::Hash + PartialEq + Eq + PartialOrd + Ord {
240    fn increment(&self) -> Self;
241
242    fn from_u64_checked(height: u64) -> Option<Self>;
243
244    fn is_adjustment_multiple(&self, params: impl AsRef<Params>) -> bool;
245
246    fn last_epoch_start(&self, params: impl AsRef<Params>) -> Self;
247}
248
249impl HeightExt for u32 {
250    fn increment(&self) -> Self {
251        self + 1
252    }
253
254    fn is_adjustment_multiple(&self, params: impl AsRef<Params>) -> bool {
255        *self as u64 % params.as_ref().difficulty_adjustment_interval() == 0
256    }
257
258    fn from_u64_checked(height: u64) -> Option<Self> {
259        height.try_into().ok()
260    }
261
262    fn last_epoch_start(&self, params: impl AsRef<Params>) -> Self {
263        let diff_adjustment_interval = params.as_ref().difficulty_adjustment_interval() as u32;
264        let floor = self / diff_adjustment_interval;
265        floor * diff_adjustment_interval
266    }
267}
268
269// Emulation of `GetBlockSubsidy` in Bitcoin Core: https://github.com/bitcoin/bitcoin/blob/master/src/validation.cpp#L1944
270pub(crate) fn block_subsidy(height: u32) -> Amount {
271    let halvings = height / SUBSIDY_HALVING_INTERVAL;
272    if halvings >= 64 {
273        return Amount::ZERO;
274    }
275    let base = Amount::ONE_BTC.to_sat() * 50;
276    let subsidy = base >> halvings;
277    Amount::from_sat(subsidy)
278}
279
280#[cfg(test)]
281mod tests {
282    use super::*;
283    use bitcoin::Network;
284
285    #[test]
286    fn test_height_monitor() {
287        let peer_one = 1.into();
288        let peer_two = 2.into();
289        let peer_three = 3.into();
290
291        let mut height_monitor = HeightMonitor::new();
292        height_monitor.insert(peer_one, 10);
293        assert!(height_monitor.max().unwrap().eq(&10));
294        height_monitor.insert(peer_two, 11);
295        height_monitor.insert(peer_three, 12);
296        assert!(height_monitor.max().unwrap().eq(&12));
297        // this should remove peer three
298        height_monitor.retain(&[peer_one, peer_two]);
299        assert!(height_monitor.max().unwrap().eq(&11));
300        height_monitor.retain(&[]);
301        assert!(height_monitor.max().is_none());
302        height_monitor.insert(peer_one, 10);
303        assert!(height_monitor.max().unwrap().eq(&10));
304        height_monitor.insert(peer_two, 11);
305        // peer one is now at 11
306        height_monitor.increment(peer_one);
307        // peer one is now at 12
308        height_monitor.increment(peer_one);
309        assert!(height_monitor.max().unwrap().eq(&12));
310    }
311
312    #[test]
313    fn test_height_ext() {
314        assert!(2016.is_adjustment_multiple(Network::Bitcoin));
315        assert!(4032.is_adjustment_multiple(Network::Bitcoin));
316        let height = 2300;
317        assert_eq!(height.last_epoch_start(Network::Bitcoin), 2016);
318        let height = 4033;
319        assert_eq!(height.last_epoch_start(Network::Bitcoin), 4032);
320        let height = 4032;
321        assert_eq!(height.last_epoch_start(Network::Bitcoin), 4032);
322    }
323
324    #[test]
325    fn test_subsidy_calculation() {
326        let first_subsidy = block_subsidy(2);
327        assert_eq!(first_subsidy, Amount::from_btc(50.0).unwrap());
328        let first_subsidy = block_subsidy(209_999);
329        assert_eq!(first_subsidy, Amount::from_btc(50.0).unwrap());
330        let second_subsidy = block_subsidy(210_000);
331        assert_eq!(second_subsidy, Amount::from_btc(25.0).unwrap());
332        let fourth_subsidy = block_subsidy(630_000);
333        assert_eq!(fourth_subsidy, Amount::from_btc(6.25).unwrap());
334        let now = block_subsidy(902_000);
335        assert_eq!(now, Amount::from_btc(3.125).unwrap());
336    }
337}
kyoto/chain/mod.rs

kyoto/chain/
mod.rs
