use sha2::{Digest as _, Sha256};
pub type Hash = [u8; 32];
#[must_use]
pub fn empty_root() -> Hash {
Sha256::digest([]).into()
}
#[must_use]
pub fn leaf_hash(leaf: &[u8]) -> Hash {
let mut h = Sha256::new();
h.update([0x00]);
h.update(leaf);
h.finalize().into()
}
#[must_use]
pub fn node_hash(left: &Hash, right: &Hash) -> Hash {
let mut h = Sha256::new();
h.update([0x01]);
h.update(left);
h.update(right);
h.finalize().into()
}
fn split(n: u64) -> u64 {
debug_assert!(n > 1);
1 << (u64::BITS - 1 - (n - 1).leading_zeros())
}
fn split_len(n: usize) -> usize {
debug_assert!(n > 1);
1 << (usize::BITS - 1 - (n - 1).leading_zeros())
}
#[must_use]
pub fn root(leaves: &[Hash]) -> Hash {
match leaves.len() {
0 => empty_root(),
1 => leaves.first().copied().unwrap_or_else(empty_root),
n => {
let k = split_len(n);
let (left, right) = leaves.split_at(k);
node_hash(&root(left), &root(right))
}
}
}
#[must_use]
pub fn inclusion_proof(leaves: &[Hash], index: usize) -> Vec<Hash> {
let n = leaves.len();
if index >= n {
return Vec::new();
}
if n == 1 {
return Vec::new();
}
let k = split_len(n);
let (left, right) = leaves.split_at(k);
if index < k {
let mut path = inclusion_proof(left, index);
path.push(root(right));
path
} else {
let mut path = inclusion_proof(right, index - k);
path.push(root(left));
path
}
}
#[must_use]
pub fn to_hex(hash: &Hash) -> String {
use std::fmt::Write as _;
hash.iter()
.fold(String::with_capacity(64), |mut acc, byte| {
let _ = write!(acc, "{byte:02x}");
acc
})
}
enum Side {
Left,
Right,
}
#[must_use]
pub fn verify_inclusion(
leaf: &Hash,
index: u64,
size: u64,
path: &[Hash],
expected_root: &Hash,
) -> bool {
if index >= size || size == 0 {
return false;
}
let mut sides = Vec::new();
let (mut idx, mut sz) = (index, size);
while sz > 1 {
let k = split(sz);
if idx < k {
sides.push(Side::Left);
sz = k;
} else {
sides.push(Side::Right);
idx -= k;
sz -= k;
}
}
if sides.len() != path.len() {
return false;
}
let mut computed = *leaf;
for (sibling, side) in path.iter().zip(sides.iter().rev()) {
computed = match side {
Side::Left => node_hash(&computed, sibling),
Side::Right => node_hash(sibling, &computed),
};
}
computed == *expected_root
}
#[must_use]
pub fn consistency_proof(leaves: &[Hash], m: usize) -> Vec<Hash> {
let n = leaves.len();
if m == 0 || m > n {
return Vec::new();
}
if m == n {
return Vec::new();
}
subproof(leaves, m, true)
}
fn subproof(leaves: &[Hash], m: usize, start: bool) -> Vec<Hash> {
let n = leaves.len();
if m == n {
if start {
return Vec::new();
}
return vec![root(leaves)];
}
let k = split_len(n);
let (left, right) = leaves.split_at(k);
if m <= k {
let mut path = subproof(left, m, start);
path.push(root(right));
path
} else {
let mut path = subproof(right, m - k, false);
path.push(root(left));
path
}
}
fn decompose(index: u64, size: u64) -> (u32, u32) {
let inner = u64::BITS - (index ^ (size - 1)).leading_zeros();
let border = index.checked_shr(inner).unwrap_or(0).count_ones();
(inner, border)
}
fn chain_inner(seed: Hash, path: &[Hash], index: u64) -> Hash {
let mut acc = seed;
for (i, sibling) in path.iter().enumerate() {
acc = if (index >> i) & 1 == 0 {
node_hash(&acc, sibling)
} else {
node_hash(sibling, &acc)
};
}
acc
}
fn chain_inner_right(seed: Hash, path: &[Hash], index: u64) -> Hash {
let mut acc = seed;
for (i, sibling) in path.iter().enumerate() {
if (index >> i) & 1 == 1 {
acc = node_hash(sibling, &acc);
}
}
acc
}
fn chain_border_right(seed: Hash, path: &[Hash]) -> Hash {
path.iter()
.fold(seed, |acc, sibling| node_hash(sibling, &acc))
}
#[must_use]
pub fn verify_consistency(
m: u64,
n: u64,
old_root: &Hash,
new_root: &Hash,
proof: &[Hash],
) -> bool {
if m > n {
return false;
}
if m == n {
return proof.is_empty() && old_root == new_root;
}
if m == 0 {
return proof.is_empty();
}
if proof.is_empty() {
return false;
}
let (mut inner, border) = decompose(m - 1, n);
let shift = m.trailing_zeros();
inner -= shift;
let (seed, start) = if m == 1u64 << shift {
(*old_root, 0usize)
} else {
match proof.first() {
Some(h) => (*h, 1usize),
None => return false,
}
};
let expected = start + inner as usize + border as usize;
if proof.len() != expected {
return false;
}
let Some(rest) = proof.get(start..) else {
return false;
};
let Some(inner_part) = rest.get(..inner as usize) else {
return false;
};
let Some(border_part) = rest.get(inner as usize..) else {
return false;
};
let mask = (m - 1) >> shift;
let recomputed_old = chain_border_right(chain_inner_right(seed, inner_part, mask), border_part);
let recomputed_new = chain_border_right(chain_inner(seed, inner_part, mask), border_part);
recomputed_old == *old_root && recomputed_new == *new_root
}
#[must_use]
pub fn checkpoints(head: u64) -> Vec<u64> {
let mut out = Vec::new();
let mut step = 1u64;
while step <= head {
out.push(head - step);
step = step.saturating_mul(2);
}
out.sort_unstable();
out.dedup();
out
}
#[must_use]
pub fn fetches_required(current: u64, head: u64) -> u32 {
if current >= head {
return 0;
}
(head - current).count_ones()
}