use crate::prelude::*;
use snarkvm_algorithms::merkle_tree::*;
use anyhow::{anyhow, Result};
use itertools::Itertools;
use std::collections::HashMap;
use time::OffsetDateTime;
#[derive(Clone, Debug)]
pub struct Blocks<N: Network> {
current_height: u32,
current_hash: N::BlockHash,
ledger_tree: LedgerTree<N>,
previous_hashes: HashMap<u32, N::BlockHash>,
headers: HashMap<u32, BlockHeader<N>>,
transactions: HashMap<u32, Transactions<N>>,
}
impl<N: Network> Blocks<N> {
pub fn new() -> Result<Self> {
let genesis_block = N::genesis_block();
let height = genesis_block.height();
let mut blocks = Self {
current_height: height,
current_hash: genesis_block.hash(),
ledger_tree: LedgerTree::<N>::new()?,
previous_hashes: Default::default(),
headers: Default::default(),
transactions: Default::default(),
};
blocks.ledger_tree.add(&genesis_block.hash())?;
blocks.previous_hashes.insert(height, genesis_block.previous_block_hash());
blocks.headers.insert(height, genesis_block.header().clone());
blocks.transactions.insert(height, genesis_block.transactions().clone());
Ok(blocks)
}
pub fn latest_block_height(&self) -> u32 {
self.current_height
}
pub fn latest_block_hash(&self) -> N::BlockHash {
self.current_hash
}
pub fn latest_ledger_root(&self) -> N::LedgerRoot {
self.ledger_tree.root()
}
pub fn latest_block_timestamp(&self) -> Result<i64> {
Ok(self.get_block_header(self.current_height)?.timestamp())
}
pub fn latest_block_difficulty_target(&self) -> Result<u64> {
Ok(self.get_block_header(self.current_height)?.difficulty_target())
}
pub fn latest_cumulative_weight(&self) -> Result<u128> {
Ok(self.get_block_header(self.current_height)?.cumulative_weight())
}
pub fn latest_block_transactions(&self) -> Result<&Transactions<N>> {
self.get_block_transactions(self.current_height)
}
pub fn latest_block(&self) -> Result<Block<N>> {
self.get_block(self.current_height)
}
pub fn get_previous_block_hash(&self, height: u32) -> Result<N::BlockHash> {
match self.previous_hashes.get(&height) {
Some(previous_hash) => Ok(*previous_hash),
None => Err(anyhow!("Missing previous block hash for height {}", height)),
}
}
pub fn get_block_header(&self, height: u32) -> Result<&BlockHeader<N>> {
match self.headers.get(&height) {
Some(header) => Ok(header),
None => Err(anyhow!("Missing block header for height {}", height)),
}
}
pub fn get_block_transactions(&self, height: u32) -> Result<&Transactions<N>> {
match self.transactions.get(&height) {
Some(transactions) => Ok(transactions),
None => Err(anyhow!("Missing block transactions for height {}", height)),
}
}
pub fn get_block(&self, height: u32) -> Result<Block<N>> {
match height == 0 {
true => Ok(N::genesis_block().clone()),
false => Ok(Block::from(
self.get_previous_block_hash(height)?,
self.get_block_header(height)?.clone(),
self.get_block_transactions(height)?.clone(),
)?),
}
}
pub fn get_block_hash(&self, height: u32) -> Result<N::BlockHash> {
if height > self.current_height {
return Err(anyhow!("Given block height {} is greater than current height", height));
}
match height == self.current_height {
true => Ok(self.current_hash),
false => match self.previous_hashes.get(&(height + 1)) {
Some(block_hash) => Ok(*block_hash),
None => Err(anyhow!("Missing block hash for height {}", height)),
},
}
}
pub fn contains_height(&self, height: u32) -> bool {
self.previous_hashes.contains_key(&height)
|| self.headers.contains_key(&height)
|| self.transactions.contains_key(&height)
}
pub fn contains_ledger_root(&self, ledger_root: &N::LedgerRoot) -> bool {
*ledger_root == self.latest_ledger_root()
|| self.headers.values().map(BlockHeader::previous_ledger_root).any(|root| root == *ledger_root)
}
pub fn contains_block_hash(&self, block_hash: &N::BlockHash) -> bool {
self.current_hash == *block_hash || self.previous_hashes.values().any(|hash| *hash == *block_hash)
}
pub fn contains_transaction(&self, transaction: &Transaction<N>) -> bool {
self.transactions.values().flat_map(|transactions| &**transactions).any(|tx| *tx == *transaction)
}
pub fn contains_serial_number(&self, serial_number: &N::SerialNumber) -> bool {
self.transactions
.values()
.flat_map(|transactions| (**transactions).iter().map(Transaction::serial_numbers))
.any(|mut serial_numbers| serial_numbers.contains(serial_number))
}
pub fn contains_commitment(&self, commitment: &N::Commitment) -> bool {
self.transactions
.values()
.flat_map(|transactions| (**transactions).iter().map(Transaction::commitments))
.any(|mut commitments| commitments.contains(commitment))
}
pub fn add_next(&mut self, block: &Block<N>) -> Result<()> {
if !block.is_valid() {
return Err(anyhow!("The given block is invalid"));
}
let height = block.height();
if self.current_height + 1 != height {
return Err(anyhow!("The given block has an incorrect block height"));
}
if self.contains_height(height) {
return Err(anyhow!("The given block height already exists in the ledger"));
}
if self.current_hash != block.previous_block_hash() {
return Err(anyhow!("The given block has an incorrect previous block hash"));
}
let block_hash = block.hash();
if self.contains_block_hash(&block_hash) {
return Err(anyhow!("The given block hash already exists in the ledger"));
}
let now = OffsetDateTime::now_utc().unix_timestamp();
if block.timestamp() > (now + N::ALEO_FUTURE_TIME_LIMIT_IN_SECS) {
return Err(anyhow!("The given block timestamp exceeds the time limit"));
}
let current_block = self.latest_block()?;
if block.timestamp() <= current_block.timestamp() {
return Err(anyhow!("The given block timestamp is before the current timestamp"));
}
let expected_difficulty_target =
Blocks::<N>::compute_difficulty_target(N::genesis_block().header(), block.timestamp(), block.height());
if block.difficulty_target() != expected_difficulty_target {
return Err(anyhow!(
"The given block difficulty target is incorrect. Found {}, but expected {}",
block.difficulty_target(),
expected_difficulty_target
));
}
let expected_cumulative_weight =
current_block.cumulative_weight().saturating_add((u64::MAX / expected_difficulty_target) as u128);
if block.cumulative_weight() != expected_cumulative_weight {
return Err(anyhow!(
"The given cumulative weight is incorrect. Found {}, but expected {}",
block.cumulative_weight(),
expected_cumulative_weight
));
}
for transaction in block.transactions().iter() {
if self.contains_transaction(transaction) {
return Err(anyhow!("The given block has a duplicate transaction in the ledger"));
}
if !self.contains_ledger_root(&transaction.ledger_root()) {
return Err(anyhow!(
"The given transaction references a non-existent ledger root {}",
&transaction.ledger_root()
));
}
}
for serial_number in block.serial_numbers() {
if self.contains_serial_number(serial_number) {
return Err(anyhow!("Serial number already exists in the ledger"));
}
}
for commitment in block.commitments() {
if self.contains_commitment(commitment) {
return Err(anyhow!("Commitment already exists in the ledger"));
}
}
{
let mut blocks = self.clone();
blocks.current_height = height;
blocks.current_hash = block_hash;
blocks.ledger_tree.add(&block.hash())?;
blocks.previous_hashes.insert(height, block.previous_block_hash());
blocks.headers.insert(height, block.header().clone());
blocks.transactions.insert(height, block.transactions().clone());
*self = blocks;
}
Ok(())
}
pub fn to_ledger_tree(&self) -> &LedgerTree<N> {
&self.ledger_tree
}
pub fn to_ledger_root_inclusion_proof(
&self,
block_hash: &N::BlockHash,
) -> Result<MerklePath<N::LedgerRootParameters>> {
self.ledger_tree.to_ledger_inclusion_proof(block_hash)
}
pub fn to_ledger_proof(&self, commitment: N::Commitment) -> Result<LedgerProof<N>> {
let transaction = self
.transactions
.values()
.flat_map(|transactions| &**transactions)
.filter(|transaction| transaction.commitments().contains(&commitment))
.collect::<Vec<_>>();
if transaction.len() != 1 {
return Err(anyhow!("Multiple transactions associated with commitment {}", commitment.to_string()));
}
let transaction = transaction[0];
let local_proof = {
let mut transitions_tree = Transitions::<N>::new()?;
transitions_tree.add_all(transaction.transitions())?;
transitions_tree.to_local_proof(commitment)?
};
let transaction_id = local_proof.transaction_id();
let block_height = self
.transactions
.iter()
.filter_map(|(block_height, transactions)| match transactions.transaction_ids().contains(&transaction_id) {
true => Some(block_height),
false => None,
})
.collect::<Vec<_>>();
if block_height.len() != 1 {
return Err(anyhow!("Multiple blocks associated with transaction {}", transaction_id.to_string()));
}
let block_height = *block_height[0];
let transactions = self.get_block_transactions(block_height)?;
let block_header = self.get_block_header(block_height)?;
let transactions_inclusion_proof = {
let index = transactions
.transaction_ids()
.enumerate()
.filter_map(|(index, id)| match id == transaction_id {
true => Some(index),
false => None,
})
.collect::<Vec<_>>();
if index.len() != 1 {
return Err(anyhow!("Block contains multiple transactions with the id {}", transaction_id.to_string()));
}
transactions.to_transactions_inclusion_proof(index[0], transaction_id)?
};
let transactions_root = transactions.transactions_root();
let block_header_inclusion_proof = block_header.to_header_inclusion_proof(1, transactions_root)?;
let block_header_root = block_header.to_header_root()?;
let previous_block_hash = self.get_previous_block_hash(self.current_height)?;
let current_block_hash = self.current_hash;
let record_proof = RecordProof::new(
current_block_hash,
previous_block_hash,
block_header_root,
block_header_inclusion_proof,
transactions_root,
transactions_inclusion_proof,
local_proof,
)?;
let ledger_root = self.latest_ledger_root();
let ledger_root_inclusion_proof = self.to_ledger_root_inclusion_proof(¤t_block_hash)?;
LedgerProof::new(ledger_root, ledger_root_inclusion_proof, record_proof)
}
pub fn compute_difficulty_target(
anchor_block_header: &BlockHeader<N>,
block_timestamp: i64,
block_height: u32,
) -> u64 {
Self::asert_retarget(
anchor_block_header.timestamp(),
anchor_block_header.difficulty_target(),
anchor_block_header.height(),
block_timestamp,
block_height,
N::ALEO_BLOCK_TIME_IN_SECS,
)
}
fn asert_retarget(
anchor_timestamp: i64,
anchor_difficulty_target: u64,
anchor_block_height: u32,
block_timestamp: i64,
block_height: u32,
target_block_time: i64,
) -> u64 {
let drift = {
let block_time_elapsed = core::cmp::max(block_timestamp.saturating_sub(anchor_timestamp), 1);
let number_of_blocks_elapsed = core::cmp::max(block_height.saturating_sub(anchor_block_height), 1);
let expected_block_time_elapsed = target_block_time.saturating_mul(number_of_blocks_elapsed as i64);
block_time_elapsed - expected_block_time_elapsed
};
const RBITS: u32 = 16;
const RADIX: u128 = 1 << RBITS;
const TAU: u128 = 64_800;
let (integral, fractional) = {
let exponent = (RADIX as i128).saturating_mul(drift as i128) / (TAU as i128);
let integral = exponent >> RBITS;
let fractional = (exponent - (integral << RBITS)) as u128;
assert!(fractional < RADIX, "Ensure fractional part is within fixed point size");
assert_eq!(exponent, integral * (RADIX as i128) + fractional as i128);
(integral, fractional)
};
let fractional_multiplier = RADIX
+ ((195_766_423_245_049_u128 * fractional
+ 971_821_376_u128 * fractional.pow(2)
+ 5_127_u128 * fractional.pow(3)
+ 2_u128.pow(RBITS * 3 - 1))
>> (RBITS * 3));
let candidate_difficulty_target = (anchor_difficulty_target as u128).saturating_mul(fractional_multiplier);
let shifts = integral - RBITS as i128;
let mut candidate_difficulty_target = if shifts < 0 {
match candidate_difficulty_target.checked_shr((-shifts) as u32) {
Some(target) => core::cmp::max(target, 1),
None => 1,
}
} else {
match candidate_difficulty_target.checked_shl(shifts as u32) {
Some(target) => core::cmp::max(target, 1),
None => u64::MAX as u128,
}
};
candidate_difficulty_target = core::cmp::min(candidate_difficulty_target, u64::MAX as u128);
assert_eq!(candidate_difficulty_target.checked_shr(64), Some(0));
candidate_difficulty_target as u64
}
}
#[cfg(test)]
#[allow(clippy::comparison_chain)]
mod tests {
use super::*;
use crate::testnet2::Testnet2;
use rand::{thread_rng, Rng};
#[test]
fn test_asert_difficulty_target_simple() {
let anchor_timestamp = 1640179531i64;
let anchor_block_height = 72154u32;
let anchor_difficulty_target = 101336179232188u64;
for i in -19..20 {
let simulated_block_time = Testnet2::ALEO_BLOCK_TIME_IN_SECS + i;
let simulated_block_height = anchor_block_height + 1;
let expected_time_elapsed =
(simulated_block_height - anchor_block_height) as i64 * Testnet2::ALEO_BLOCK_TIME_IN_SECS;
let simulated_time_elapsed = (simulated_block_height - anchor_block_height) as i64 * simulated_block_time;
let simulated_timestamp = anchor_timestamp.saturating_add(simulated_time_elapsed);
let candidate_difficulty_target = Blocks::<Testnet2>::asert_retarget(
anchor_timestamp,
anchor_difficulty_target,
anchor_block_height,
simulated_timestamp,
simulated_block_height,
Testnet2::ALEO_BLOCK_TIME_IN_SECS,
);
println!(
"Anchor (height = {:?}, timestamp = {:?}, difficulty_target = {:?})",
anchor_block_height, anchor_timestamp, anchor_difficulty_target
);
println!(
"Block (height = {:?}, timestamp = {:?}, difficulty_target = {:?})",
simulated_block_height, simulated_timestamp, candidate_difficulty_target
);
println!(
"Difference (height = {:?}, drift = {:?}, delta_in_difficulty_target = {:?})",
simulated_block_height - anchor_block_height,
simulated_time_elapsed - expected_time_elapsed,
candidate_difficulty_target.wrapping_sub(anchor_difficulty_target),
);
if simulated_block_time < Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} < {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert!(candidate_difficulty_target < anchor_difficulty_target);
} else if simulated_block_time == Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} == {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert_eq!(candidate_difficulty_target, anchor_difficulty_target);
} else if simulated_block_time > Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} > {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert!(candidate_difficulty_target > anchor_difficulty_target);
}
}
}
#[test]
fn test_asert_difficulty_target_anchored() {
let anchor_timestamp = 1640179531i64;
let anchor_block_height = 72154u32;
let anchor_difficulty_target = 101336179232188u64;
const TAU: u128 = 64_800;
for num_blocks_since_anchor in 1..500_000 {
for j in -5..5 {
let simulated_block_time = Testnet2::ALEO_BLOCK_TIME_IN_SECS + j;
let simulated_block_height = anchor_block_height + num_blocks_since_anchor;
let expected_time_elapsed =
(simulated_block_height - anchor_block_height) as i64 * Testnet2::ALEO_BLOCK_TIME_IN_SECS;
let simulated_time_elapsed =
(simulated_block_height - anchor_block_height) as i64 * simulated_block_time;
let drift = simulated_time_elapsed - expected_time_elapsed;
let simulated_timestamp = anchor_timestamp.saturating_add(simulated_time_elapsed);
let candidate_difficulty_target = Blocks::<Testnet2>::asert_retarget(
anchor_timestamp,
anchor_difficulty_target,
anchor_block_height,
simulated_timestamp,
simulated_block_height,
Testnet2::ALEO_BLOCK_TIME_IN_SECS,
);
let drift_multiplier = drift as f64 / TAU as f64;
let difficulty_ratio = candidate_difficulty_target as f64 / anchor_difficulty_target as f64;
println!(
"Anchor (height = {:?}, timestamp = {:?}, difficulty_target = {:?})",
anchor_block_height, anchor_timestamp, anchor_difficulty_target
);
println!(
"Block (height = {:?}, timestamp = {:?}, difficulty_target = {:?})",
simulated_block_height, simulated_timestamp, candidate_difficulty_target
);
println!(
"Difference (height = {}, drift = {}, difficulty_ratio = {}, drift_multiplier = {})",
simulated_block_height - anchor_block_height,
drift,
difficulty_ratio,
drift_multiplier
);
let expected_difficulty_ratio = 2f64.powf(drift_multiplier);
if anchor_difficulty_target.checked_mul(expected_difficulty_ratio as u64).is_some() {
let percentage_difference =
100f64 * (expected_difficulty_ratio - difficulty_ratio).abs() / difficulty_ratio;
assert!(percentage_difference < 1f64);
}
if simulated_block_time < Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} < {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert!(candidate_difficulty_target < anchor_difficulty_target);
} else if simulated_block_time == Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} == {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert_eq!(candidate_difficulty_target, anchor_difficulty_target);
} else if simulated_block_time > Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} > {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert!(candidate_difficulty_target > anchor_difficulty_target);
}
}
}
}
#[test]
fn test_asert_difficulty_target_random() {
let rng = &mut thread_rng();
for _ in 0..1_000_000 {
let anchor_timestamp = rng.gen_range(0..1_000_000_000_i64);
let anchor_block_height = rng.gen_range(0..u32::MAX);
let anchor_difficulty_target = rng.gen_range(1..u64::MAX);
let simulated_block_time = rng.gen_range(1..Testnet2::ALEO_BLOCK_TIME_IN_SECS + 100);
let simulated_block_height = anchor_block_height.saturating_add(rng.gen_range(1..10_000_u32));
let expected_time_elapsed =
(simulated_block_height - anchor_block_height) as i64 * Testnet2::ALEO_BLOCK_TIME_IN_SECS;
let simulated_time_elapsed = (simulated_block_height - anchor_block_height) as i64 * simulated_block_time;
let simulated_timestamp = anchor_timestamp.saturating_add(simulated_time_elapsed);
let candidate_difficulty_target = Blocks::<Testnet2>::asert_retarget(
anchor_timestamp,
anchor_difficulty_target,
anchor_block_height,
simulated_timestamp,
simulated_block_height,
Testnet2::ALEO_BLOCK_TIME_IN_SECS,
);
println!(
"Anchor (height = {:?}, timestamp = {:?}, difficulty_target = {:?})",
anchor_block_height, anchor_timestamp, anchor_difficulty_target
);
println!(
"Block (height = {:?}, timestamp = {:?}, difficulty_target = {:?})",
simulated_block_height, simulated_timestamp, candidate_difficulty_target
);
println!(
"Difference (height = {:?}, drift = {:?}, delta_in_difficulty_target = {:?})",
simulated_block_height - anchor_block_height,
simulated_time_elapsed - expected_time_elapsed,
candidate_difficulty_target.wrapping_sub(anchor_difficulty_target),
);
if simulated_block_time < Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} < {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert!(candidate_difficulty_target < anchor_difficulty_target);
} else if simulated_block_time == Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} == {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert_eq!(candidate_difficulty_target, anchor_difficulty_target);
} else if simulated_block_time > Testnet2::ALEO_BLOCK_TIME_IN_SECS {
println!("{} > {}\n", simulated_block_time, Testnet2::ALEO_BLOCK_TIME_IN_SECS);
assert!(candidate_difficulty_target > anchor_difficulty_target);
}
}
}
}