nakamoto_common/block/
tree.rs

1//! Types and functions relating to block trees.
2#![warn(missing_docs)]
3use std::collections::BTreeMap;
4
5use bitcoin::blockdata::block::BlockHeader;
6use bitcoin::consensus::params::Params;
7use bitcoin::hash_types::BlockHash;
8
9use thiserror::Error;
10
11use crate::block::store;
12use crate::block::time::Clock;
13use crate::block::{Bits, BlockTime, Height, Target, Work};
14use crate::nonempty::NonEmpty;
15
16/// An error related to the block tree.
17#[derive(Debug, Error)]
18pub enum Error {
19    /// The block's proof-of-work is invalid.
20    #[error("invalid block proof-of-work")]
21    InvalidBlockPoW,
22
23    /// The block's difficulty target is invalid.
24    #[error("invalid block difficulty target: {0}, expected {1}")]
25    InvalidBlockTarget(Target, Target),
26
27    /// The block's hash doesn't match the checkpoint.
28    #[error("invalid checkpoint block hash {0} at height {1}")]
29    InvalidBlockHash(BlockHash, Height),
30
31    /// The block forks off the main chain prior to the last checkpoint.
32    #[error("block height {0} is prior to last checkpoint")]
33    InvalidBlockHeight(Height),
34
35    /// The block timestamp is invalid.
36    #[error("block timestamp {0} is invalid")]
37    InvalidBlockTime(BlockTime, std::cmp::Ordering),
38
39    /// The block is already known.
40    #[error("duplicate block {0}")]
41    DuplicateBlock(BlockHash),
42
43    /// The block is orphan.
44    #[error("block missing: {0}")]
45    BlockMissing(BlockHash),
46
47    /// A block import was aborted. FIXME: Move this error out of here.
48    #[error("block import aborted at height {2}: {0} ({1} block(s) imported)")]
49    BlockImportAborted(Box<Self>, usize, Height),
50
51    /// Mismatched genesis.
52    #[error("stored genesis header doesn't match network genesis")]
53    GenesisMismatch,
54
55    /// A storage error occured.
56    #[error("storage error: {0}")]
57    Store(#[from] store::Error),
58
59    /// The operation was interrupted.
60    #[error("the operation was interrupted")]
61    Interrupted,
62}
63
64/// A generic block header.
65pub trait Header {
66    /// Return the proof-of-work of this header.
67    fn work(&self) -> Work;
68}
69
70impl Header for BlockHeader {
71    fn work(&self) -> Work {
72        self.work()
73    }
74}
75
76/// The outcome of a successful block header import.
77#[allow(clippy::large_enum_variant)]
78#[derive(Debug, Clone, PartialEq, Eq)]
79pub enum ImportResult {
80    /// A new tip was found. This can happen in either of two scenarios:
81    ///
82    /// 1. The imported block(s) extended the active chain, or
83    /// 2. The imported block(s) caused a chain re-org.
84    ///
85    TipChanged(
86        BlockHeader,
87        BlockHash,
88        Height,
89        Vec<(Height, BlockHeader)>,
90        NonEmpty<(Height, BlockHeader)>,
91    ),
92    /// The block headers were imported successfully, but our best block hasn't changed.
93    /// This will happen if we imported a duplicate, orphan or stale block.
94    TipUnchanged, // TODO: We could add a parameter eg. BlockMissing or DuplicateBlock.
95}
96
97/// A chain of block headers that may or may not lead back to genesis.
98#[derive(Debug, Clone)]
99pub struct Branch<'a, H: Header>(pub &'a [H]);
100
101impl<'a, H: Header> Branch<'a, H> {
102    /// Compute the total proof-of-work carried by this branch.
103    pub fn work(&self) -> Work {
104        let mut work = Work::default();
105        for header in self.0.iter() {
106            work = work + header.work();
107        }
108        work
109    }
110}
111
112/// A representation of all known blocks that keeps track of the longest chain.
113pub trait BlockTree: BlockReader {
114    /// Import a chain of block headers into the block tree.
115    fn import_blocks<I: Iterator<Item = BlockHeader>, C: Clock>(
116        &mut self,
117        chain: I,
118        context: &C,
119    ) -> Result<ImportResult, Error>;
120    /// Attempts to extend the active chain. Returns `Ok` with `ImportResult::TipUnchanged` if
121    /// the block didn't connect, and `Err` if the block was invalid.
122    fn extend_tip<C: Clock>(
123        &mut self,
124        header: BlockHeader,
125        context: &C,
126    ) -> Result<ImportResult, Error>;
127}
128
129/// Read block header state.
130pub trait BlockReader {
131    /// Get a block by hash.
132    fn get_block(&self, hash: &BlockHash) -> Option<(Height, &BlockHeader)>;
133    /// Get a block by height.
134    fn get_block_by_height(&self, height: Height) -> Option<&BlockHeader>;
135    /// Find a path from the active chain to the provided (stale) block hash.
136    ///
137    /// If a path is found, the height of the start/fork block is returned, along with the
138    /// headers up to and including the tip, forming a branch.
139    ///
140    /// If the given block is on the active chain, its height and header is returned.
141    fn find_branch(&self, to: &BlockHash) -> Option<(Height, NonEmpty<BlockHeader>)>;
142    /// Iterate over the longest chain, starting from genesis.
143    fn chain<'a>(&'a self) -> Box<dyn Iterator<Item = BlockHeader> + 'a> {
144        Box::new(self.iter().map(|(_, h)| h))
145    }
146    /// Iterate over the longest chain, starting from genesis, including heights.
147    fn iter<'a>(&'a self) -> Box<dyn DoubleEndedIterator<Item = (Height, BlockHeader)> + 'a>;
148    /// Iterate over a range of blocks.
149    fn range<'a>(
150        &'a self,
151        range: std::ops::Range<Height>,
152    ) -> Box<dyn Iterator<Item = (Height, BlockHash)> + 'a> {
153        Box::new(
154            self.iter()
155                .map(|(height, header)| (height, header.block_hash()))
156                .skip(range.start as usize)
157                .take((range.end - range.start) as usize),
158        )
159    }
160    /// Return the height of the longest chain.
161    fn height(&self) -> Height;
162    /// Get the tip of the longest chain.
163    fn tip(&self) -> (BlockHash, BlockHeader);
164    /// Get the last block of the longest chain.
165    fn best_block(&self) -> (Height, &BlockHeader) {
166        let height = self.height();
167        (
168            height,
169            self.get_block_by_height(height)
170                .expect("the best block is always present"),
171        )
172    }
173    /// Get the height of the last checkpoint block.
174    fn last_checkpoint(&self) -> Height;
175    /// Known checkpoints.
176    fn checkpoints(&self) -> BTreeMap<Height, BlockHash>;
177    /// Return the genesis block header.
178    fn genesis(&self) -> &BlockHeader {
179        self.get_block_by_height(0)
180            .expect("the genesis block is always present")
181    }
182    /// Check whether a block hash is known.
183    fn is_known(&self, hash: &BlockHash) -> bool;
184    /// Check whether a block hash is part of the active chain.
185    fn contains(&self, hash: &BlockHash) -> bool;
186    /// Return the headers corresponding to the given locators, up to a maximum.
187    fn locate_headers(
188        &self,
189        locators: &[BlockHash],
190        stop_hash: BlockHash,
191        max_headers: usize,
192    ) -> Vec<BlockHeader>;
193    /// Get the locator hashes starting from the given height and going backwards.
194    fn locator_hashes(&self, from: Height) -> Vec<BlockHash>;
195    /// Get the next difficulty given a block height, time and bits.
196    fn next_difficulty_target(
197        &self,
198        last_height: Height,
199        last_time: BlockTime,
200        last_target: Target,
201        params: &Params,
202    ) -> Bits {
203        // Only adjust on set intervals. Otherwise return current target.
204        // Since the height is 0-indexed, we add `1` to check it against the interval.
205        if (last_height + 1) % params.difficulty_adjustment_interval() != 0 {
206            return BlockHeader::compact_target_from_u256(&last_target);
207        }
208
209        let last_adjustment_height =
210            last_height.saturating_sub(params.difficulty_adjustment_interval() - 1);
211        let last_adjustment_block = self
212            .get_block_by_height(last_adjustment_height)
213            .unwrap_or_else(|| self.genesis());
214        let last_adjustment_time = last_adjustment_block.time;
215
216        if params.no_pow_retargeting {
217            return last_adjustment_block.bits;
218        }
219
220        let actual_timespan = last_time - last_adjustment_time;
221        let mut adjusted_timespan = actual_timespan;
222
223        if actual_timespan < params.pow_target_timespan as BlockTime / 4 {
224            adjusted_timespan = params.pow_target_timespan as BlockTime / 4;
225        } else if actual_timespan > params.pow_target_timespan as BlockTime * 4 {
226            adjusted_timespan = params.pow_target_timespan as BlockTime * 4;
227        }
228
229        let mut target = last_target;
230
231        target = target.mul_u32(adjusted_timespan);
232        target = target / Target::from_u64(params.pow_target_timespan).unwrap();
233
234        // Ensure a difficulty floor.
235        if target > params.pow_limit {
236            target = params.pow_limit;
237        }
238
239        BlockHeader::compact_target_from_u256(&target)
240    }
241}
nakamoto_common/block/tree.rs

nakamoto_common/block/
tree.rs
