1//! Checkpoint lists for checkpoint-based block verification
2//!
3//! Each checkpoint consists of a coinbase height and block header hash.
4//!
5//! Checkpoints can be used to verify their ancestors, by chaining backwards
6//! to another checkpoint, via each block's parent block hash.
78#[cfg(test)]
9mod tests;
1011use crate::BoxError;
1213use std::{
14 collections::{BTreeMap, HashSet},
15 ops::RangeBounds,
16 str::FromStr,
17};
1819use zebra_chain::block;
20use zebra_chain::parameters::Network;
2122/// The hard-coded checkpoints for mainnet, generated using the
23/// `zebra-checkpoints` tool.
24///
25/// To regenerate the latest checkpoints, use the following commands:
26/// ```sh
27/// LAST_CHECKPOINT=$(tail -1 main-checkpoints.txt | cut -d' ' -f1)
28/// echo "$LAST_CHECKPOINT"
29/// zebra-checkpoints --cli /path/to/zcash-cli --last-checkpoint "$LAST_CHECKPOINT" >> main-checkpoints.txt &
30/// tail -f main-checkpoints.txt
31/// ```
32///
33/// See the checkpoints [./README.md] for more details.
34const MAINNET_CHECKPOINTS: &str = include_str!("main-checkpoints.txt");
3536/// The hard-coded checkpoints for testnet, generated using the
37/// `zebra-checkpoints` tool.
38///
39/// To use testnet, use the testnet checkpoints file, and run
40/// `zebra-checkpoints [other args] -- -testnet`.
41///
42/// See [`MAINNET_CHECKPOINTS`] for detailed `zebra-checkpoints` usage
43/// information.
44const TESTNET_CHECKPOINTS: &str = include_str!("test-checkpoints.txt");
4546/// Network methods related to checkpoints
47pub trait ParameterCheckpoint {
48/// Returns the hash for the genesis block in `network`.
49fn genesis_hash(&self) -> zebra_chain::block::Hash;
50/// Returns the hard-coded checkpoint list for `network`.
51fn checkpoint_list(&self) -> CheckpointList;
52}
5354impl ParameterCheckpoint for Network {
55fn genesis_hash(&self) -> zebra_chain::block::Hash {
56match self {
57// zcash-cli getblockhash 0
58Network::Mainnet => "00040fe8ec8471911baa1db1266ea15dd06b4a8a5c453883c000b031973dce08"
59.parse()
60 .expect("hard-coded hash parses"),
61// See `zebra_chain::parameters::network::testnet` for more details.
62Network::Testnet(params) => params.genesis_hash(),
63 }
64 }
6566fn checkpoint_list(&self) -> CheckpointList {
67let (checkpoints_for_network, should_fallback_to_genesis_hash_as_checkpoint) = match self {
68 Network::Mainnet => (MAINNET_CHECKPOINTS, false),
69 Network::Testnet(params) if params.is_default_testnet() => (TESTNET_CHECKPOINTS, false),
70 Network::Testnet(_params) => ("", true),
71 };
7273// Check that the list starts with the correct genesis block and parses checkpoint list.
74let first_checkpoint_height = checkpoints_for_network
75 .lines()
76 .next()
77 .map(checkpoint_height_and_hash);
7879match first_checkpoint_height {
80// parse calls CheckpointList::from_list
81Some(Ok((block::Height(0), hash))) if hash == self.genesis_hash() => {
82 checkpoints_for_network
83 .parse()
84 .expect("hard-coded checkpoint list parses and validates")
85 }
86_ if should_fallback_to_genesis_hash_as_checkpoint => {
87 CheckpointList::from_list([(block::Height(0), self.genesis_hash())])
88 .expect("hard-coded checkpoint list parses and validates")
89 }
90Some(Ok((block::Height(0), _))) => {
91panic!("the genesis checkpoint does not match the {self} genesis hash")
92 }
93Some(Ok(_)) => panic!("checkpoints must start at the genesis block height 0"),
94Some(Err(err)) => panic!("{err}"),
95None => panic!(
96"there must be at least one checkpoint on default networks, for the genesis block"
97),
98 }
99 }
100}
101102/// Parses a checkpoint to a [`block::Height`] and [`block::Hash`].
103fn checkpoint_height_and_hash(checkpoint: &str) -> Result<(block::Height, block::Hash), BoxError> {
104let fields = checkpoint.split(' ').collect::<Vec<_>>();
105if let [height, hash] = fields[..] {
106Ok((height.parse()?, hash.parse()?))
107 } else {
108Err(format!("Invalid checkpoint format: expected 2 space-separated fields but found {}: '{checkpoint}'", fields.len()).into())
109 }
110}
111112/// A list of block height and hash checkpoints.
113///
114/// Checkpoints should be chosen to avoid forks or chain reorganizations,
115/// which only happen in the last few hundred blocks in the chain.
116/// (zcashd allows chain reorganizations up to 99 blocks, and prunes
117/// orphaned side-chains after 288 blocks.)
118///
119/// This is actually a bijective map, but since it is read-only, we use a
120/// BTreeMap, and do the value uniqueness check on initialisation.
121#[derive(Clone, Debug, Eq, Hash, PartialEq)]
122pub struct CheckpointList(BTreeMap<block::Height, block::Hash>);
123124impl FromStr for CheckpointList {
125type Err = BoxError;
126127/// Parse a string into a CheckpointList.
128 ///
129 /// Each line has one checkpoint, consisting of a `block::Height` and
130 /// `block::Hash`, separated by a single space.
131 ///
132 /// Assumes that the provided genesis checkpoint is correct.
133fn from_str(s: &str) -> Result<Self, Self::Err> {
134let mut checkpoint_list: Vec<(block::Height, block::Hash)> = Vec::new();
135136for checkpoint in s.lines() {
137 checkpoint_list.push(checkpoint_height_and_hash(checkpoint)?);
138 }
139140 CheckpointList::from_list(checkpoint_list)
141 }
142}
143144impl CheckpointList {
145/// Create a new checkpoint list for `network` from `checkpoint_list`.
146 ///
147 /// Assumes that the provided genesis checkpoint is correct.
148 ///
149 /// Checkpoint heights and checkpoint hashes must be unique.
150 /// There must be a checkpoint for a genesis block at block::Height 0.
151 /// (All other checkpoints are optional.)
152pub(crate) fn from_list(
153 list: impl IntoIterator<Item = (block::Height, block::Hash)>,
154 ) -> Result<Self, BoxError> {
155// BTreeMap silently ignores duplicates, so we count the checkpoints
156 // before adding them to the map
157let original_checkpoints: Vec<(block::Height, block::Hash)> = list.into_iter().collect();
158let original_len = original_checkpoints.len();
159160let checkpoints: BTreeMap<block::Height, block::Hash> =
161 original_checkpoints.into_iter().collect();
162163// Check that the list starts with _some_ genesis block
164match checkpoints.iter().next() {
165Some((block::Height(0), _hash)) => {}
166Some(_) => Err("checkpoints must start at the genesis block height 0")?,
167None => Err("there must be at least one checkpoint, for the genesis block")?,
168 };
169170// This check rejects duplicate heights, whether they have the same or
171 // different hashes
172if checkpoints.len() != original_len {
173Err("checkpoint heights must be unique")?;
174 }
175176let block_hashes: HashSet<&block::Hash> = checkpoints.values().collect();
177if block_hashes.len() != original_len {
178Err("checkpoint hashes must be unique")?;
179 }
180181// Make sure all the hashes are valid. In Bitcoin, [0; 32] is the null
182 // hash. It is also used as the parent hash of genesis blocks.
183if block_hashes.contains(&block::Hash([0; 32])) {
184Err("checkpoint list contains invalid checkpoint hash: found null hash")?;
185 }
186187let checkpoints = CheckpointList(checkpoints);
188if checkpoints.max_height() > block::Height::MAX {
189Err("checkpoint list contains invalid checkpoint: checkpoint height is greater than the maximum block height")?;
190 }
191192Ok(checkpoints)
193 }
194195/// Return true if there is a checkpoint at `height`.
196 ///
197 /// See `BTreeMap::contains_key()` for details.
198pub fn contains(&self, height: block::Height) -> bool {
199self.0.contains_key(&height)
200 }
201202/// Returns the hash corresponding to the checkpoint at `height`,
203 /// or None if there is no checkpoint at that height.
204 ///
205 /// See `BTreeMap::get()` for details.
206pub fn hash(&self, height: block::Height) -> Option<block::Hash> {
207self.0.get(&height).cloned()
208 }
209210/// Return the block height of the highest checkpoint in the checkpoint list.
211 ///
212 /// If there is only a single checkpoint, then the maximum height will be
213 /// zero. (The genesis block.)
214pub fn max_height(&self) -> block::Height {
215self.max_height_in_range(..)
216 .expect("checkpoint lists must have at least one checkpoint")
217 }
218219/// Return the block height of the lowest checkpoint in a sub-range.
220pub fn min_height_in_range<R>(&self, range: R) -> Option<block::Height>
221where
222R: RangeBounds<block::Height>,
223 {
224self.0.range(range).map(|(height, _)| *height).next()
225 }
226227/// Return the block height of the highest checkpoint in a sub-range.
228pub fn max_height_in_range<R>(&self, range: R) -> Option<block::Height>
229where
230R: RangeBounds<block::Height>,
231 {
232self.0.range(range).map(|(height, _)| *height).next_back()
233 }
234235/// Returns an iterator over all the checkpoints, in increasing height order.
236pub fn iter(&self) -> impl Iterator<Item = (&block::Height, &block::Hash)> {
237self.0.iter()
238 }
239240/// Returns the checkpoint at `height`, as a zero-based index.
241 /// If `height` is not a checkpoint height, returns the checkpoint immediately before that height.
242pub fn prev_checkpoint_index(&self, height: block::Height) -> usize {
243self.0
244.keys()
245 .rposition(|&key| key <= height)
246 .expect("checkpoints must start at the genesis block height 0")
247 }
248249/// Returns the number of checkpoints in the list.
250//
251 // Checkpoint lists are never empty by construction.
252#[allow(clippy::len_without_is_empty)]
253pub fn len(&self) -> usize {
254self.0.len()
255 }
256}