#![deny(missing_docs)]
#![allow(clippy::redundant_else, clippy::too_many_lines)]
#![doc = include_str!("../README.md")]
use crc::crc32;
use maplit::btreemap;
use primitive_types::H256;
use std::{
collections::{BTreeMap, BTreeSet},
ops::{Add, AddAssign},
};
use thiserror::Error;
pub type BlockNumber = u64;
#[derive(
Clone,
Copy,
Debug,
PartialEq,
Eq,
Hash,
fastrlp::EncodableWrapper,
fastrlp::DecodableWrapper,
fastrlp::MaxEncodedLen,
)]
pub struct ForkHash(pub [u8; 4]);
impl From<H256> for ForkHash {
fn from(genesis: H256) -> Self {
Self(crc32::checksum_ieee(&genesis[..]).to_be_bytes())
}
}
impl AddAssign<BlockNumber> for ForkHash {
fn add_assign(&mut self, block: BlockNumber) {
let blob = block.to_be_bytes();
self.0 = crc32::update(u32::from_be_bytes(self.0), &crc32::IEEE_TABLE, &blob).to_be_bytes();
}
}
impl Add<BlockNumber> for ForkHash {
type Output = Self;
fn add(mut self, block: BlockNumber) -> Self {
self += block;
self
}
}
#[derive(
Clone,
Copy,
Debug,
PartialEq,
Eq,
Hash,
fastrlp::Encodable,
fastrlp::Decodable,
fastrlp::MaxEncodedLen,
)]
pub struct ForkId {
pub hash: ForkHash,
pub next: BlockNumber,
}
#[derive(Clone, Copy, Debug, Error, PartialEq, Eq, Hash)]
pub enum ValidationError {
#[error("remote node is outdated and needs a software update")]
RemoteStale,
#[error("local node is on an incompatible chain or needs a software update")]
LocalIncompatibleOrStale,
}
#[derive(Clone, Debug, PartialEq)]
pub struct ForkFilter {
forks: BTreeMap<BlockNumber, ForkHash>,
head: BlockNumber,
cache: Cache,
}
#[derive(Clone, Debug, PartialEq)]
struct Cache {
epoch_start: BlockNumber,
epoch_end: Option<BlockNumber>,
past: Vec<(BlockNumber, ForkHash)>,
future: Vec<ForkHash>,
fork_id: ForkId,
}
impl Cache {
fn compute_cache(forks: &BTreeMap<BlockNumber, ForkHash>, head: BlockNumber) -> Self {
let mut past = Vec::with_capacity(forks.len());
let mut future = Vec::with_capacity(forks.len());
let mut epoch_start = 0;
let mut epoch_end = None;
for (block, hash) in forks {
if *block <= head {
epoch_start = *block;
past.push((*block, *hash));
} else {
if epoch_end.is_none() {
epoch_end = Some(*block);
}
future.push(*hash);
}
}
let fork_id = ForkId {
hash: past
.last()
.expect("there is always at least one - genesis - fork hash; qed")
.1,
next: epoch_end.unwrap_or(0),
};
Self {
epoch_start,
epoch_end,
past,
future,
fork_id,
}
}
}
impl ForkFilter {
pub fn new<F>(head: BlockNumber, genesis: H256, forks: F) -> Self
where
F: IntoIterator<Item = BlockNumber>,
{
let genesis_fork_hash = ForkHash::from(genesis);
let mut forks = forks.into_iter().collect::<BTreeSet<_>>();
forks.remove(&0);
let forks = forks
.into_iter()
.fold(
(btreemap! { 0 => genesis_fork_hash }, genesis_fork_hash),
|(mut acc, base_hash), block| {
let fork_hash = base_hash + block;
acc.insert(block, fork_hash);
(acc, fork_hash)
},
)
.0;
let cache = Cache::compute_cache(&forks, head);
Self { forks, head, cache }
}
fn set_head_priv(&mut self, head: BlockNumber) -> bool {
#[allow(clippy::option_if_let_else)]
let recompute_cache = {
if head < self.cache.epoch_start {
true
} else if let Some(epoch_end) = self.cache.epoch_end {
head >= epoch_end
} else {
false
}
};
if recompute_cache {
self.cache = Cache::compute_cache(&self.forks, head);
}
self.head = head;
recompute_cache
}
pub fn set_head(&mut self, head: BlockNumber) {
self.set_head_priv(head);
}
#[must_use]
pub const fn current(&self) -> ForkId {
self.cache.fork_id
}
pub fn validate(&self, fork_id: ForkId) -> Result<(), ValidationError> {
if self.current().hash == fork_id.hash {
if fork_id.next == 0 {
return Ok(());
}
if self.head >= fork_id.next {
return Err(ValidationError::LocalIncompatibleOrStale);
} else {
return Ok(());
}
}
let mut it = self.cache.past.iter();
while let Some((_, hash)) = it.next() {
if *hash == fork_id.hash {
if let Some((actual_fork_block, _)) = it.next() {
if *actual_fork_block == fork_id.next {
return Ok(());
} else {
return Err(ValidationError::RemoteStale);
}
}
break;
}
}
for future_fork_hash in &self.cache.future {
if *future_fork_hash == fork_id.hash {
return Ok(());
}
}
Err(ValidationError::LocalIncompatibleOrStale)
}
}
#[cfg(test)]
mod tests {
use super::*;
use hex_literal::hex;
const GENESIS_HASH: H256 = H256(hex!(
"d4e56740f876aef8c010b86a40d5f56745a118d0906a34e69aec8c0db1cb8fa3"
));
#[test]
fn forkhash() {
let mut fork_hash = ForkHash::from(GENESIS_HASH);
assert_eq!(fork_hash.0, hex!("fc64ec04"));
fork_hash += 1_150_000;
assert_eq!(fork_hash.0, hex!("97c2c34c"));
fork_hash += 1_920_000;
assert_eq!(fork_hash.0, hex!("91d1f948"));
}
#[test]
fn compatibility_check() {
let mut filter = ForkFilter::new(
0,
GENESIS_HASH,
vec![
1_150_000, 1_920_000, 2_463_000, 2_675_000, 4_370_000, 7_280_000,
],
);
filter.set_head(7_987_396);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("668db0af")),
next: 0
}),
Ok(())
);
filter.set_head(7_987_396);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("668db0af")),
next: BlockNumber::max_value()
}),
Ok(())
);
filter.set_head(7_279_999);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("a00bc324")),
next: 0
}),
Ok(())
);
filter.set_head(7_279_999);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("a00bc324")),
next: 7_280_000
}),
Ok(())
);
filter.set_head(7_279_999);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("a00bc324")),
next: BlockNumber::max_value()
}),
Ok(())
);
filter.set_head(7_987_396);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("a00bc324")),
next: 7_280_000
}),
Ok(())
);
filter.set_head(7_987_396);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("3edd5b10")),
next: 4_370_000
}),
Ok(())
);
filter.set_head(7_279_999);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("668db0af")),
next: 0
}),
Ok(())
);
filter.set_head(4_369_999);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("a00bc324")),
next: 0
}),
Ok(())
);
filter.set_head(7_987_396);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("a00bc324")),
next: 0
}),
Err(ValidationError::RemoteStale)
);
filter.set_head(7_987_396);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("5cddc0e1")),
next: 0
}),
Err(ValidationError::LocalIncompatibleOrStale)
);
filter.set_head(7_279_999);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("5cddc0e1")),
next: 0
}),
Err(ValidationError::LocalIncompatibleOrStale)
);
filter.set_head(7_987_396);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("afec6b27")),
next: 0
}),
Err(ValidationError::LocalIncompatibleOrStale)
);
filter.set_head(88_888_888);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("668db0af")),
next: 88_888_888
}),
Err(ValidationError::LocalIncompatibleOrStale)
);
filter.set_head(7_279_999);
assert_eq!(
filter.validate(ForkId {
hash: ForkHash(hex!("a00bc324")),
next: 7_279_999
}),
Err(ValidationError::LocalIncompatibleOrStale)
);
}
#[test]
fn forkid_serialization() {
assert_eq!(
&*fastrlp::encode_fixed_size(&ForkId {
hash: ForkHash(hex!("00000000")),
next: 0
}),
hex!("c6840000000080")
);
assert_eq!(
&*fastrlp::encode_fixed_size(&ForkId {
hash: ForkHash(hex!("deadbeef")),
next: 0xBADD_CAFE
}),
hex!("ca84deadbeef84baddcafe")
);
assert_eq!(
&*fastrlp::encode_fixed_size(&ForkId {
hash: ForkHash(hex!("ffffffff")),
next: u64::max_value()
}),
hex!("ce84ffffffff88ffffffffffffffff")
);
assert_eq!(
<ForkId as fastrlp::Decodable>::decode(&mut (&hex!("c6840000000080") as &[u8]))
.unwrap(),
ForkId {
hash: ForkHash(hex!("00000000")),
next: 0
}
);
assert_eq!(
<ForkId as fastrlp::Decodable>::decode(&mut (&hex!("ca84deadbeef84baddcafe") as &[u8]))
.unwrap(),
ForkId {
hash: ForkHash(hex!("deadbeef")),
next: 0xBADD_CAFE
}
);
assert_eq!(
<ForkId as fastrlp::Decodable>::decode(
&mut (&hex!("ce84ffffffff88ffffffffffffffff") as &[u8])
)
.unwrap(),
ForkId {
hash: ForkHash(hex!("ffffffff")),
next: u64::max_value()
}
);
}
#[test]
fn compute_cache() {
let b1 = 1_150_000;
let b2 = 1_920_000;
let h0 = ForkId {
hash: ForkHash(hex!("fc64ec04")),
next: b1,
};
let h1 = ForkId {
hash: ForkHash(hex!("97c2c34c")),
next: b2,
};
let h2 = ForkId {
hash: ForkHash(hex!("91d1f948")),
next: 0,
};
let mut fork_filter = ForkFilter::new(0, GENESIS_HASH, vec![b1, b2]);
assert!(!fork_filter.set_head_priv(0));
assert_eq!(fork_filter.current(), h0);
assert!(!fork_filter.set_head_priv(1));
assert_eq!(fork_filter.current(), h0);
assert!(fork_filter.set_head_priv(b1 + 1));
assert_eq!(fork_filter.current(), h1);
assert!(!fork_filter.set_head_priv(b1));
assert_eq!(fork_filter.current(), h1);
assert!(fork_filter.set_head_priv(b1 - 1));
assert_eq!(fork_filter.current(), h0);
assert!(fork_filter.set_head_priv(b1));
assert_eq!(fork_filter.current(), h1);
assert!(!fork_filter.set_head_priv(b2 - 1));
assert_eq!(fork_filter.current(), h1);
assert!(fork_filter.set_head_priv(b2));
assert_eq!(fork_filter.current(), h2);
}
}