cumulus_primitives_spec_messaging/

lift.rs

// Copyright (C) Parity Technologies (UK) Ltd.
// This file is part of Cumulus.
// SPDX-License-Identifier: Apache-2.0

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 	http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! Requires-lift and consumption-record primitives.
//!
//! Blocks never emit `Requires` and never see a `StreamsRoot`. Processing the messaging inherent
//! writes a [`ConsumptionRecord`]: which streams the block touched and the [`Interval`] consumed on
//! each. The `validate_block` wrapper then synthesizes the candidate's `Requires` set from the
//! records plus PoV-carried lifts ([`RequiresLift`]), one per recorded stream, binding that
//! stream's consumption to a current committed `StreamsRoot`. The relay chain sees only entries it
//! can match.
//!
//! The invariant [`build_requires`] enforces, per stream and candidate: the recorded intervals form
//! a proven forward chain (each block continues where the previous ended, or a PoV proof shows the
//! gap is a forward extension, see [`stitch`]), and one lift binds the chain's endpoint to a
//! committed root, which binds everything consumed.
//!
//! The record is STF output and trusted; the lifts are PoV data and verified here. Lifts are
//! matched to a source's `StreamId`-sorted record streams by position. A mispaired lift cannot
//! verify, because the `tree_proof` walk binds the record's key
//! ([`crate::streams_root::streams_root_from_proof`]).

use alloc::{collections::BTreeMap, vec, vec::Vec};
use codec::{Decode, DecodeWithMemTracking, Encode};
use mmr_lib::{
	helper::{get_peak_map, get_peaks, is_valid_mmr_size},
	leaf_index_to_pos, MerkleProof, NodeMerkleProof,
};
use polkadot_core_primitives::Hash;
use polkadot_parachain_primitives::primitives::Id as ParaId;
use polkadot_primitives::{v9::MAX_COMMITMENT_ENTRIES, RequiresSet};
use scale_info::TypeInfo;
use sp_core::ConstU32;
use sp_runtime::BoundedVec;

use crate::{
	mmr::{
		mmr_size, MessagePosition, MmrFrontier, MmrRoot, SpecMerge, MAX_MMR_HASHES,
		MAX_MMR_LEAF_COUNT,
	},
	stream::StreamId,
	streams_root::{streams_root_from_proof, StreamProof, StreamsRoot},
};

/// The keyed-tree proof a lift walks from a stream root to the `StreamsRoot`.
pub type TreeInclusionProof = StreamProof;

/// Upper bound on an [`MmrInclusionProof`]'s items. A single-leaf proof needs at most the subtree
/// height plus the other peaks, each at most 63; this constant is a ceiling no valid proof reaches.
/// Enforced at decode, which bounds `calculate_root`'s work on untrusted input.
pub const MAX_INCLUSION_PROOF_ITEMS: u32 = 2 * 64;

/// Why an MMR proof verification rejected its input. Typed so callers can tell a malformed or
/// forged proof from an out-of-range or non-forward one.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum ProofError {
	/// The proof is structurally malformed: an invalid `mmr_size`, a wrong item/node count, or
	/// `mmr_lib` could not reconstruct a root from it.
	InvalidProof,
	/// A leaf position is at or past the proven MMR's leaf count (an empty MMR has no head).
	PositionOutOfRange,
	/// An extension does not go strictly forward (its target is not newer than the frontier).
	NotForward,
	/// A leaf count exceeds [`MAX_MMR_LEAF_COUNT`].
	LeafCountTooLarge,
}

/// An append-only MMR extension proof: O(log n) connecting nodes that, with a frontier's own peaks,
/// reconstruct a newer root. The `mmr_lib` `gen_ancestry_proof` form of the design's
/// `connecting_nodes`. Verification computes the new root; it is never declared alongside the
/// proof. It holds node hashes only, no message payloads.
#[derive(Clone, Encode, Decode, DecodeWithMemTracking, PartialEq, Eq, Debug, TypeInfo, Default)]
pub struct MMRExtensionProof {
	/// Leaf count of the extended MMR. The `mmr_lib` node count is derived from it, so no
	/// independent size can be smuggled in. `0` with empty `connecting_nodes` is the identity
	/// extension.
	/// Compact-encoded, since this is PoV-carried.
	#[codec(compact)]
	pub leaf_count: u64,
	/// The connecting-node hashes, in `mmr_lib`'s proof order. Positions are not stored: an MMR's
	/// shape is fixed by its size, so they are derived at verify time from the two leaf counts
	/// (`ancestry_proof_positions`). Empty for the identity. At most [`MAX_MMR_HASHES`], enforced
	/// at decode.
	pub connecting_nodes: BoundedVec<Hash, ConstU32<MAX_MMR_HASHES>>,
}

impl MMRExtensionProof {
	/// The identity extension. Yields a frontier's own root for the caught-up case.
	pub fn identity() -> Self {
		Self { leaf_count: 0, connecting_nodes: BoundedVec::new() }
	}

	/// Extend `from` and return the new root, computed from `from`'s peaks and the connecting
	/// nodes; `Err` if the proof does not fit that placement. The identity extension yields
	/// `from`'s own root. Comparing the root is the caller's job. `from`'s contents are not
	/// re-checked: a forged peak yields a root no committed `StreamsRoot` can bind.
	pub fn calculate_root(&self, from: &MmrFrontier) -> Result<MmrRoot, ProofError> {
		// `mmr_lib` accepts counts up to 2^63; bound the proof's to `MAX_MMR_LEAF_COUNT` first.
		// `from` is already in range by construction.
		if self.leaf_count > MAX_MMR_LEAF_COUNT {
			return Err(ProofError::LeafCountTooLarge);
		}
		// `0` is the identity only without connecting nodes. This also keeps the `leaf_count - 1`
		// below from underflowing.
		if self.leaf_count == 0 {
			return if self.connecting_nodes.is_empty() {
				Ok(from.root())
			} else {
				Err(ProofError::InvalidProof)
			};
		}
		// Strictly forward: the extended MMR must have more leaves than the frontier.
		if self.leaf_count <= from.leaf_count() {
			return Err(ProofError::NotForward);
		}
		let new_mmr_size = mmr_size(self.leaf_count);

		// Extending from the empty stream: nothing binds, so the connecting nodes must be the new
		// MMR's peaks in `get_peaks` order.
		if from.leaf_count() == 0 {
			// The nodes must form a frontier of exactly `self.leaf_count` leaves; `from_parts`
			// checks that.
			return MmrFrontier::from_parts(self.connecting_nodes.to_vec(), self.leaf_count)
				.map(|f| f.root())
				.ok_or(ProofError::InvalidProof);
		}

		// `from`'s peaks are complete subtrees of the new MMR at unchanged positions; with the
		// connecting nodes they reconstruct the new root under `SpecMerge`.
		let old_mmr_size = from.mmr_size();
		let old_positions = get_peaks(old_mmr_size);
		// Positions are not carried: derive them from the two sizes and pair them with the hashes
		// in `mmr_lib`'s proof order. A length mismatch means the proof does not fit the claimed
		// extension.
		let positions =
			mmr_lib::ancestry_proof::ancestry_proof_positions(old_mmr_size, new_mmr_size)
				.map_err(|_| ProofError::InvalidProof)?;
		if positions.len() != self.connecting_nodes.len() {
			return Err(ProofError::InvalidProof);
		}
		let proof: Vec<(u64, Hash)> =
			positions.into_iter().zip(self.connecting_nodes.iter().copied()).collect();
		let nodes: Vec<(u64, Hash)> =
			old_positions.into_iter().zip(from.peaks().iter().copied()).collect();
		NodeMerkleProof::<Hash, SpecMerge>::new(new_mmr_size, proof)
			.calculate_root(nodes)
			.map(|bag| MmrRoot::from_bag(self.leaf_count, bag))
			.map_err(|_| ProofError::InvalidProof)
	}
}

/// A single-leaf MMR inclusion proof: `mmr_lib`'s [`MerkleProof`] items (the sibling path plus the
/// other peaks) and the node count it was generated against. Used by the event and register head
/// read. Where [`MMRExtensionProof`] moves a frontier forward, this places one leaf under a fixed
/// MMR. The root is derived, never declared.
#[derive(Clone, Encode, Decode, DecodeWithMemTracking, PartialEq, Eq, Debug, TypeInfo)]
pub struct MmrInclusionProof {
	/// `mmr_lib` node count of the MMR the proof was generated against. With the leaf count it
	/// derives (`get_peak_map`), it pins a head read.
	pub mmr_size: u64,
	/// The leaf's sibling path plus the other peaks, in `mmr_lib` order.
	pub items: BoundedVec<Hash, ConstU32<MAX_INCLUSION_PROOF_ITEMS>>,
}

impl MmrInclusionProof {
	/// Leaf count of the proven MMR. `mmr_lib` accepts counts up to 2^63; ours is lower.
	fn checked_leaf_count(&self) -> Result<u64, ProofError> {
		if !is_valid_mmr_size(self.mmr_size) {
			return Err(ProofError::InvalidProof);
		}
		let leaf_count = get_peak_map(self.mmr_size);
		if leaf_count > MAX_MMR_LEAF_COUNT {
			return Err(ProofError::LeafCountTooLarge);
		}
		Ok(leaf_count)
	}

	/// Verify `leaf` (already hashed by [`crate::message::leaf_hash`]) as the last leaf of the
	/// proven MMR. Returns the head position and the frontier of that MMR; `Err` on any structural
	/// defect.
	///
	/// The expected shape is what `gen_proof` produces for the last leaf: the other peaks left to
	/// right, then the head's left siblings bottom up. The item count
	/// is checked exactly.
	///
	/// Only reconstructs a frontier; does not bind it to any committed `StreamsRoot`. `Ok` is not
	/// authentication. Prefer [`crate::message::verify_event`], which binds the result to a trusted
	/// `under`.
	pub fn verify_head(&self, leaf: Hash) -> Result<(MessagePosition, MmrFrontier), ProofError> {
		let leaf_count = self.checked_leaf_count()?;
		if leaf_count == 0 {
			return Err(ProofError::PositionOutOfRange);
		}
		if self.items.len() != leaf_proof_len(leaf_count, leaf_count - 1) {
			return Err(ProofError::InvalidProof);
		}

		let other_peaks = leaf_count.count_ones() as usize - 1;
		let (peak_items, path) = self.items.split_at(other_peaks);
		let mut last_peak = leaf;
		for sibling in path {
			last_peak = <SpecMerge as mmr_lib::Merge>::merge(sibling, &last_peak)
				.expect("SpecMerge::merge is infallible; qed");
		}
		let peaks: Vec<Hash> =
			peak_items.iter().copied().chain(core::iter::once(last_peak)).collect();
		// `other_peaks + 1 == leaf_count.count_ones()` and the ceiling was checked, so this is
		// `Some`.
		let frontier =
			MmrFrontier::from_parts(peaks, leaf_count).ok_or(ProofError::InvalidProof)?;

		Ok((MessagePosition(leaf_count - 1), frontier))
	}

	/// Verify `leaf` (already hashed by [`crate::message::leaf_hash`]) at `position` and return the
	/// implied [`MmrRoot`]. `Err` if the position is out of range or the proof malformed. Only
	/// reconstructs the root; `Ok` is not authentication. Prefer [`crate::message::verify_event`],
	/// which binds the result to a trusted `under`.
	pub fn verify_leaf(
		&self,
		position: MessagePosition,
		leaf: Hash,
	) -> Result<MmrRoot, ProofError> {
		let leaf_count = self.checked_leaf_count()?;
		if position.0 >= leaf_count {
			return Err(ProofError::PositionOutOfRange);
		}
		// `calculate_root` ignores the items of a 1-leaf proof, so padding would slip through.
		if self.items.len() != leaf_proof_len(leaf_count, position.0) {
			return Err(ProofError::InvalidProof);
		}
		let pos = leaf_index_to_pos(position.0);
		MerkleProof::<Hash, SpecMerge>::new(self.mmr_size, self.items.to_vec())
			.calculate_root(vec![(pos, leaf)])
			.map(|bag| MmrRoot::from_bag(leaf_count, bag))
			.map_err(|_| ProofError::InvalidProof)
	}
}

/// Proof length `gen_proof` produces for leaf `index`: siblings up to its peak, the peaks to its
/// left, and one bagged item for any peaks to its right.
fn leaf_proof_len(leaf_count: u64, index: u64) -> usize {
	let mut first = 0;
	let heights = (0..u64::BITS).rev().filter(|h| leaf_count >> h & 1 == 1);
	for (left_peaks, height) in heights.enumerate() {
		let peak_leaves = 1u64 << height;
		if index < first + peak_leaves {
			let right_peaks = leaf_count.count_ones() as usize - left_peaks - 1;
			return height as usize + left_peaks + usize::from(right_peaks > 0);
		}
		first += peak_leaves;
	}
	unreachable!("index < leaf_count lies under some peak; qed")
}

/// Per stream and block: consumption entered the block at `start` and left it at `end`.
///
/// The candidate's lift binds only the last state to a committed root; the intervals extend that
/// guarantee back over the bundle. Each block must start where the previous ended, or prove the
/// jump moved forward ([`stitch`]).
///
/// - Channels: `start` is the frontier root before the block's incoming messages, `end` the
/// frontier after. `start == previous end` holds by construction, so the chain check is free.
/// - Register and event reads: `end` is the context the reads were verified against, `start` its
/// root; nothing advances. Contexts can jump between blocks, so a fabricated context breaks the
/// chain instead of hiding behind a later genuine one.
///
/// `end` is a full frontier because the next gap check, or the lift, extends from it.
#[derive(Clone, Encode, Decode, DecodeWithMemTracking, PartialEq, Eq, Debug, TypeInfo)]
pub struct Interval {
	/// Root the block's consumption on this stream started from.
	pub start: MmrRoot,
	/// Frontier the block's consumption on this stream ended at.
	pub end: MmrFrontier,
}

/// Written per block: the streams this block touched and the interval consumed on each, grouped by
/// source. One interval per stream, keyed so the type enforces it; per-source order is the
/// canonical `StreamId` order the lifts match against. The API view of a flat, host-append-only
/// outbox vec. Encodes as the sorted vec of pairs would.
#[derive(Clone, Encode, Decode, PartialEq, Eq, Debug, TypeInfo, Default)]
pub struct ConsumptionRecord {
	/// `source -> stream -> interval`.
	pub entries: BTreeMap<ParaId, BTreeMap<StreamId, Interval>>,
}

/// One source's streams with their intervals across a bundle, in block order. [`build_requires`]
/// merges the per-block records into this and [`build_requires_entry`] lifts it.
pub type SourceStreams = BTreeMap<StreamId, Vec<Interval>>;

/// One lift, carried in the PoV. Matched by position to a source's `StreamId`-sorted record
/// streams; a mispaired lift cannot verify because `tree_proof` binds the record's key.
#[derive(Clone, Encode, Decode, DecodeWithMemTracking, PartialEq, Eq, Debug, TypeInfo)]
pub struct RequiresLift {
	/// One extension per gap in the stream's interval chain, in gap order. Empty when there are no
	/// gaps.
	pub advances: Vec<MMRExtensionProof>,
	/// Extends the chain's endpoint to the stream's current root. The identity extension when the
	/// endpoint already is that root.
	pub extension: MMRExtensionProof,
	/// Keyed walk from the current stream root to the `StreamsRoot` the requires entry becomes.
	pub tree_proof: TreeInclusionProof,
}

/// The candidate's lifts, grouped per source: the PoV transport form. `Decode` enforces strictly
/// increasing `ParaId`s and bounds the source count at [`MAX_COMMITMENT_ENTRIES`], so more sources
/// than a `RequiresSet` can hold are rejected before any lift is verified.
/// [`TryFrom<BTreeMap>`](Self::try_from) is canonical by construction. [`build_requires`] zips
/// these against the record's sources by position.
#[derive(Clone, Encode, PartialEq, Eq, Debug, TypeInfo, Default)]
pub struct LiftsBySource(BoundedVec<(ParaId, Vec<RequiresLift>), ConstU32<MAX_COMMITMENT_ENTRIES>>);

impl LiftsBySource {
	/// The sources, in strictly increasing order.
	pub fn sources(&self) -> impl Iterator<Item = &ParaId> {
		self.0.iter().map(|(source, _)| source)
	}

	/// `(source, lifts)` pairs, in source order.
	pub fn iter(&self) -> impl Iterator<Item = &(ParaId, Vec<RequiresLift>)> {
		self.0.iter()
	}

	pub fn len(&self) -> usize {
		self.0.len()
	}

	pub fn is_empty(&self) -> bool {
		self.0.is_empty()
	}
}

impl TryFrom<BTreeMap<ParaId, Vec<RequiresLift>>> for LiftsBySource {
	type Error = LiftError;

	/// A map iterates in `ParaId` order with unique keys, so only the bound can fail.
	fn try_from(map: BTreeMap<ParaId, Vec<RequiresLift>>) -> Result<Self, LiftError> {
		BoundedVec::try_from(map.into_iter().collect::<Vec<_>>())
			.map(Self)
			.map_err(|_| LiftError::TooManySources)
	}
}

/// Matches the derived `Encode`. The sequence must be strictly increasing by `ParaId`.
impl Decode for LiftsBySource {
	fn decode<I: codec::Input>(input: &mut I) -> Result<Self, codec::Error> {
		let inner =
			BoundedVec::<(ParaId, Vec<RequiresLift>), ConstU32<MAX_COMMITMENT_ENTRIES>>::decode(
				input,
			)?;
		if inner.windows(2).any(|w| w[0].0 >= w[1].0) {
			return Err("LiftsBySource: sources must be strictly increasing".into());
		}
		Ok(Self(inner))
	}
}

impl DecodeWithMemTracking for LiftsBySource {}

/// Why requires synthesis failed. All are deterministic in the records and PoV, so every validator
/// reaches the same verdict.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum LiftError {
	/// A stream's interval list was empty.
	EmptyRecord,
	/// A gap needed a forward-extension proof but `advances` was exhausted.
	MissingAdvance,
	/// `advances` carried more proofs than there were gaps.
	StrayAdvance,
	/// A gap's proof did not forward-extend the previous endpoint to the next start.
	BrokenChain,
	/// The endpoint extension did not verify against the stitched endpoint.
	BadExtension,
	/// The tree proof did not fold to a `StreamsRoot` (malformed / wrong key).
	BadTreeProof,
	/// A source's stream count and lift count disagreed.
	LiftCountMismatch,
	/// A source's streams lifted to more than one `StreamsRoot`.
	DivergentRoots,
	/// The recorded sources and the provided lifts' sources did not match exactly.
	LiftSourceMismatch,
	/// More sources than the `RequiresSet` bound allows.
	TooManySources,
}

/// Stitch one stream's intervals, in bundle order, into its endpoint frontier. `advances` must hold
/// exactly one extension per gap (a `start` that is not the previous `end`'s root), in gap order.
/// Gaps are proven forward, so within a candidate verified states cannot regress; across candidates
/// that is the STF's to hold.
pub fn stitch(
	intervals: &[Interval],
	advances: &[MMRExtensionProof],
) -> Result<MmrFrontier, LiftError> {
	let (first, rest) = intervals.split_first().ok_or(LiftError::EmptyRecord)?;
	let mut gaps = advances.iter();
	// `first.start` is the boundary with the previous candidate; nothing here can check it, and
	// nothing needs to: everything consumed is bound through the chain from `first.end`.
	// Cross-candidate continuity is the STF's (the stored frontier for channels; for register
	// reads, the last applied position and the register's monotonic fields).
	let mut current = &first.end;
	for next in rest {
		let current_root = current.root();
		if next.start != current_root {
			// A gap must be a proven forward extension of where we ended.
			let proof = gaps.next().ok_or(LiftError::MissingAdvance)?;
			let extended = proof.calculate_root(current).map_err(|_| LiftError::BrokenChain)?;
			if extended != next.start {
				return Err(LiftError::BrokenChain);
			}
		}
		current = &next.end;
	}
	if gaps.next().is_some() {
		return Err(LiftError::StrayAdvance);
	}
	Ok(current.clone())
}

/// Lift one source's streams to a single committed `StreamsRoot`: stitch each stream's intervals
/// into an endpoint, extend it to the stream's current root, walk the tree to the `StreamsRoot`,
/// and require all of the source's streams to reach the same root. `streams` iterates in `StreamId`
/// order; `lifts` matches it by position.
pub fn build_requires_entry(
	streams: &SourceStreams,
	lifts: &[RequiresLift],
) -> Result<StreamsRoot, LiftError> {
	if streams.len() != lifts.len() {
		return Err(LiftError::LiftCountMismatch);
	}
	let mut entry: Option<StreamsRoot> = None;
	for ((stream, intervals), lift) in streams.iter().zip(lifts) {
		let endpoint = stitch(intervals, &lift.advances)?;
		// The endpoint is contained in the stream's current root, computed rather than declared,
		let current =
			lift.extension.calculate_root(&endpoint).map_err(|_| LiftError::BadExtension)?;
		// and the keyed walk from it yields the `StreamsRoot`. The walk binds the record's `stream`
		// key, so a mispaired lift cannot verify.
		let root = streams_root_from_proof(*stream, current.0, &lift.tree_proof)
			.ok_or(LiftError::BadTreeProof)?;
		match entry {
			None => entry = Some(root),
			Some(prev) if prev != root => return Err(LiftError::DivergentRoots),
			Some(_) => {},
		}
	}
	entry.ok_or(LiftError::EmptyRecord)
}

/// Synthesize the candidate's [`RequiresSet`] from the per-block records, in bundle order, and the
/// PoV lifts. Sources must match exactly; a recorded source without lifts, or lifts for an
/// unrecorded source, invalidates the candidate.
///
/// `None` when the candidate consumed nothing: there is no entry the relay could match, and the
/// candidate emits no `Requires` signal. `RequiresSet` cannot be empty.
pub fn build_requires(
	records: &[ConsumptionRecord],
	lifts: &LiftsBySource,
) -> Result<Option<RequiresSet>, LiftError> {
	// Merge per (source, stream) intervals across the bundle, preserving block order.
	let mut merged: BTreeMap<ParaId, SourceStreams> = BTreeMap::new();
	for record in records {
		for (source, streams) in &record.entries {
			let by_stream = merged.entry(*source).or_default();
			for (stream, interval) in streams {
				by_stream.entry(*stream).or_default().push(interval.clone());
			}
		}
	}
	// Recorded sources and lift sources must be equal; both are ParaId-sorted.
	if !merged.keys().eq(lifts.sources()) {
		return Err(LiftError::LiftSourceMismatch);
	}
	if merged.is_empty() {
		return Ok(None);
	}
	let entries = merged
		.iter()
		.zip(lifts.iter())
		.map(|((source, by_stream), (_, source_lifts))| {
			build_requires_entry(by_stream, source_lifts).map(|root| (*source, root))
		})
		.collect::<Result<Vec<_>, _>>()?;
	RequiresSet::try_from_iter(entries)
		.map(Some)
		.map_err(|_| LiftError::TooManySources)
}

#[cfg(test)]
mod tests {
	use super::*;
	use crate::{
		streams_root::{gen_stream_proof, streams_root, TreeStep},
		test_utils::{ch, extension, frontier_at, leaves, mmr_size},
	};
	use mmr_lib::{
		ancestry_proof::ancestry_proof_positions,
		util::{MemMMR, MemStore},
	};
	use polkadot_primitives::v9::MAX_COMMITMENT_ENTRIES;
	use sp_core::H256;

	/// Root over the first `k` leaves.
	fn root_at(all: &[Hash], k: usize) -> MmrRoot {
		frontier_at(all, k).root()
	}

	#[test]
	fn extension_computes_root_and_rejects_tampering() {
		let all = leaves(5);
		let ext = extension(&all, 2, 5);
		// Computes root@5 from frontier@2 + O(log n) connecting nodes (never a declared root).
		assert_eq!(ext.calculate_root(&frontier_at(&all, 2)), Ok(root_at(&all, 5)));
		// Wrong starting frontier → does not reconstruct the extended root.
		assert_ne!(ext.calculate_root(&frontier_at(&all, 3)), Ok(root_at(&all, 5)));
		// Tampered connecting node → a different computed root.
		let mut bad = ext.clone();
		bad.connecting_nodes[0] = H256::repeat_byte(0xff);
		assert_ne!(bad.calculate_root(&frontier_at(&all, 2)), Ok(root_at(&all, 5)));
		// Identity extension yields the frontier's own root.
		let id = MMRExtensionProof::identity();
		assert_eq!(id.calculate_root(&frontier_at(&all, 3)), Ok(root_at(&all, 3)));
	}

	/// `connecting_nodes` stores bare hashes, so the positions we derive must match what
	/// `gen_ancestry_proof` emits. Checked for every `(old, new)` pair up to 256 leaves, which
	/// includes the seven- and eight-peak sizes 127 and 255. A change in `mmr_lib` trips this;
	/// `Cargo.lock` pins it.
	#[test]
	fn ancestry_positions_matches_mmr_lib() {
		for n in 2..=256usize {
			let all = leaves(n as u64);
			let store = MemStore::<Hash>::default();
			let mut mmr = MemMMR::<Hash, SpecMerge>::new(0, &store);
			for l in &all {
				mmr.push(*l).unwrap();
			}
			for k in 1..n {
				let ap = mmr.gen_ancestry_proof(mmr_size(k)).unwrap();
				let expected: Vec<u64> =
					ap.prev_peaks_proof.proof_items().iter().map(|(p, _)| *p).collect();
				let got = ancestry_proof_positions(mmr_size(k), mmr_size(n)).unwrap();
				assert_eq!(got, expected, "position mismatch at k={k}, n={n}");
			}
		}
	}

	#[test]
	fn extension_leaf_count_disambiguates_equal_node_counts() {
		// 1→3 and 1→4 both take two nodes, placed differently, so only `leaf_count` tells them
		// apart.
		let all = leaves(4);
		let to3 = extension(&all, 1, 3);
		let to4 = extension(&all, 1, 4);
		assert_eq!(to3.connecting_nodes.len(), 2);
		assert_eq!(to4.connecting_nodes.len(), 2);
		let from1 = frontier_at(&all, 1);
		assert_eq!(to3.calculate_root(&from1), Ok(root_at(&all, 3)));
		assert_eq!(to4.calculate_root(&from1), Ok(root_at(&all, 4)));
		// The same two nodes under the other count place differently and reach neither root.
		let relabelled =
			MMRExtensionProof { leaf_count: 4, connecting_nodes: to3.connecting_nodes };
		let got = relabelled.calculate_root(&from1);
		assert_ne!(got, Ok(root_at(&all, 3)));
		assert_ne!(got, Ok(root_at(&all, 4)));
	}

	#[test]
	fn extension_verify_rejects_non_forward() {
		let all = leaves(5);
		// A real (non-identity) extension pointed *back* to the frontier's own size is not strictly
		// forward → rejected up front, before any crypto work.
		let mut ext = extension(&all, 2, 5);
		ext.leaf_count = 2;
		assert_eq!(ext.calculate_root(&frontier_at(&all, 2)), Err(ProofError::NotForward));
	}

	#[test]
	fn extension_verify_bounds_untrusted_leaf_counts() {
		let all = leaves(5);
		// The proof's own count. A value whose derived node count would overflow `u64` is rejected
		// before any position is computed from it.
		let mut ext = extension(&all, 2, 5);
		ext.leaf_count = u64::MAX;
		assert_eq!(ext.calculate_root(&frontier_at(&all, 2)), Err(ProofError::LeafCountTooLarge));
		ext.leaf_count = MAX_MMR_LEAF_COUNT + 1;
		assert_eq!(ext.calculate_root(&frontier_at(&all, 2)), Err(ProofError::LeafCountTooLarge));
		// The frontier's count is not this function's to check. An out-of-range `MmrFrontier`
		// cannot be built, from `from_parts` or from `Decode`.
		assert!(MmrFrontier::from_parts(vec![all[0]], 1 << 63).is_none());
	}

	#[test]
	fn extension_verify_rejects_zero_leaf_count() {
		let all = leaves(5);
		// `0` with connecting nodes is not the identity: malformed, not merely non-forward.
		let mut ext = extension(&all, 2, 5);
		ext.leaf_count = 0;
		assert_eq!(ext.calculate_root(&frontier_at(&all, 2)), Err(ProofError::InvalidProof));
	}

	#[test]
	fn extension_identity_on_empty_frontier_yields_empty_root() {
		// Yields `empty_root()`. An empty stream is never in the tree, so the tree walk is what
		// fails.
		assert_eq!(
			MMRExtensionProof::identity().calculate_root(&MmrFrontier::default()),
			Ok(MmrFrontier::default().root()),
		);
	}

	#[test]
	fn the_longest_valid_extension_fits_the_node_ceiling() {
		// Worst case, one node per set bit: 1 → the largest all-ones count. The lift's PoV
		// reservation relies on it.
		let nodes =
			ancestry_proof_positions(mmr_size(1), mmr_size((MAX_MMR_LEAF_COUNT - 1) as usize))
				.unwrap()
				.len();
		assert_eq!(nodes, 48);
		assert!(nodes <= MAX_MMR_HASHES as usize);
	}

	#[test]
	fn over_long_extension_proof_fails_to_decode() {
		// The bound is in the type, so an over-long proof is rejected at the length prefix.
		let max = MAX_MMR_HASHES as usize;
		let at_bound = (codec::Compact(5u64), vec![H256::zero(); max]).encode();
		assert!(MMRExtensionProof::decode(&mut &at_bound[..]).is_ok());
		let over = (codec::Compact(5u64), vec![H256::zero(); max + 1]).encode();
		assert!(MMRExtensionProof::decode(&mut &over[..]).is_err());
	}

	#[test]
	fn stitch_caught_up_needs_no_advance() {
		let all = leaves(5);
		let i1 = Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 2) };
		let i2 = Interval { start: root_at(&all, 2), end: frontier_at(&all, 5) };
		assert_eq!(stitch(&[i1, i2], &[]).unwrap(), frontier_at(&all, 5));
	}

	#[test]
	fn stitch_bridges_a_gap_and_flags_bad_advance_counts() {
		let all = leaves(5);
		let i1 = Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 2) };
		// Block 2 jumped forward to context @4 before continuing to @5.
		let i2 = Interval { start: root_at(&all, 4), end: frontier_at(&all, 5) };
		let advance = extension(&all, 2, 4);

		assert_eq!(
			stitch(&[i1.clone(), i2.clone()], &[advance.clone()]).unwrap(),
			frontier_at(&all, 5)
		);
		// Missing the gap proof.
		assert_eq!(stitch(&[i1.clone(), i2.clone()], &[]), Err(LiftError::MissingAdvance));
		// A stray advance where the chain was already continuous.
		let cont = Interval { start: root_at(&all, 2), end: frontier_at(&all, 5) };
		assert_eq!(stitch(&[i1, cont], &[advance]), Err(LiftError::StrayAdvance));
	}

	#[test]
	fn stitch_rejects_a_gap_bridged_to_the_wrong_context() {
		// The advance is all that binds the earlier read to the stream: a context the chain does
		// not reach must fail, or a fabricated read could hide behind a later genuine one.
		let all = leaves(5);
		let i1 = Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 2) };
		let i2 = Interval { start: root_at(&all, 4), end: frontier_at(&all, 5) };
		// A genuine extension of @2, but to @3, not to the context @4 block 2 started from.
		assert_eq!(
			stitch(&[i1.clone(), i2.clone()], &[extension(&all, 2, 3)]),
			Err(LiftError::BrokenChain)
		);
		// An extension that does not fit @2 at all (built from @1).
		assert_eq!(stitch(&[i1, i2], &[extension(&all, 1, 4)]), Err(LiftError::BrokenChain));
	}

	#[test]
	fn stitch_rejects_a_backward_step() {
		// A later block read an older context. Extensions only go forward, so nothing can bridge
		// it; the pallet does not record an ignored stale read for this reason.
		let all = leaves(5);
		let i1 = Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 4) };
		let i2 = Interval { start: root_at(&all, 2), end: frontier_at(&all, 2) };
		assert_eq!(stitch(&[i1.clone(), i2.clone()], &[]), Err(LiftError::MissingAdvance));
		assert_eq!(stitch(&[i1, i2], &[extension(&all, 4, 5)]), Err(LiftError::BrokenChain));
	}

	#[test]
	fn nothing_recorded_lifts_nothing() {
		assert_eq!(stitch(&[], &[]), Err(LiftError::EmptyRecord));
		assert_eq!(build_requires_entry(&SourceStreams::new(), &[]), Err(LiftError::EmptyRecord));
	}

	#[test]
	fn an_empty_source_entry_fails_closed() {
		// The pallet records a source only with a stream. An entry with none has nothing to lift,
		// so the candidate is invalid rather than silently requiring nothing from that source.
		let source = ParaId::from(1000);
		let record = ConsumptionRecord { entries: BTreeMap::from([(source, BTreeMap::new())]) };
		let lifts = LiftsBySource::try_from(BTreeMap::from([(source, Vec::new())])).unwrap();
		assert_eq!(build_requires(&[record], &lifts), Err(LiftError::EmptyRecord));
	}

	#[test]
	fn consumption_record_encodes_as_the_sorted_vec_of_pairs() {
		// The record crosses the runtime-API boundary; keying it must not move a byte relative to
		// the design's `Vec<(StreamId, Interval)>` view of the same sorted, unique entries.
		let all = leaves(3);
		let (a, b) = (ch(1), ch(2));
		let (ia, ib) = (
			Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 1) },
			Interval { start: root_at(&all, 1), end: frontier_at(&all, 3) },
		);
		let keyed = ConsumptionRecord {
			entries: BTreeMap::from([(
				ParaId::from(7),
				BTreeMap::from([(b, ib.clone()), (a, ia.clone())]),
			)]),
		};
		let as_vec: BTreeMap<ParaId, Vec<(StreamId, Interval)>> =
			BTreeMap::from([(ParaId::from(7), vec![(a, ia), (b, ib)])]);
		assert_eq!(keyed.encode(), as_vec.encode());
	}

	#[test]
	fn hot_path_single_block_single_stream() {
		let all = leaves(3);
		let root3 = root_at(&all, 3);
		let stream = ch(2000);
		// StreamsRoot over the single active stream at root@3.
		let entries = BTreeMap::from([(stream, root3.0)]);
		let expected = streams_root(&entries).unwrap();
		let (_r, tree_proof) = gen_stream_proof(&entries, stream).unwrap();

		// One interval, endpoint = frontier@3; identity extension (caught up).
		let interval = Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) };
		let lift = RequiresLift {
			advances: Vec::new(),
			extension: MMRExtensionProof::identity(),
			tree_proof,
		};
		let streams = SourceStreams::from([(stream, vec![interval])]);
		let root = build_requires_entry(&streams, &[lift]).unwrap();
		assert_eq!(root, expected);
	}

	#[test]
	fn build_requires_end_to_end_and_source_match() {
		let all = leaves(3);
		let root3 = root_at(&all, 3);
		let source = ParaId::from(1000);
		let stream = ch(2000);
		let entries = BTreeMap::from([(stream, root3.0)]);
		let expected = streams_root(&entries).unwrap();
		let (_r, tree_proof) = gen_stream_proof(&entries, stream).unwrap();

		let record = ConsumptionRecord {
			entries: BTreeMap::from([(
				source,
				BTreeMap::from([(
					stream,
					Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) },
				)]),
			)]),
		};
		let mut lifts = BTreeMap::new();
		lifts.insert(
			source,
			vec![RequiresLift {
				advances: Vec::new(),
				extension: MMRExtensionProof::identity(),
				tree_proof,
			}],
		);

		let lifts_by_source = LiftsBySource::try_from(lifts.clone()).unwrap();
		let requires = build_requires(&[record.clone()], &lifts_by_source).unwrap().unwrap();
		assert_eq!(requires.get(source), Some(&expected));

		// A lift for an unrecorded source (or a missing one) is rejected.
		let mut extra = lifts.clone();
		extra.insert(ParaId::from(9999), Vec::new());
		let extra = LiftsBySource::try_from(extra).unwrap();
		assert_eq!(build_requires(&[record], &extra), Err(LiftError::LiftSourceMismatch));

		// Nothing consumed, nothing lifted: no set, not an empty one.
		assert_eq!(build_requires(&[], &LiftsBySource::default()), Ok(None));
	}

	#[test]
	fn lifts_by_source_decode_enforces_canonical_form() {
		let lift = || RequiresLift {
			advances: Vec::new(),
			extension: MMRExtensionProof::identity(),
			tree_proof: StreamProof { steps: Default::default() },
		};
		let pair = |id: u32| (ParaId::from(id), vec![lift()]);
		// Canonical round-trips …
		let good = vec![pair(1), pair(2)].encode();
		assert!(LiftsBySource::decode(&mut &good[..]).is_ok());
		// … out of order and duplicate sources do not …
		let unsorted = vec![pair(2), pair(1)].encode();
		assert!(LiftsBySource::decode(&mut &unsorted[..]).is_err());
		let duplicate = vec![pair(1), pair(1)].encode();
		assert!(LiftsBySource::decode(&mut &duplicate[..]).is_err());
		// … and more sources than a RequiresSet could hold are rejected before any verification.
		let too_many: Vec<_> = (0..=MAX_COMMITMENT_ENTRIES).map(pair).collect();
		assert!(LiftsBySource::decode(&mut &too_many.encode()[..]).is_err());
		// A map is canonical by construction; only the bound can fail it.
		let map: BTreeMap<_, _> = (0..=MAX_COMMITMENT_ENTRIES).map(pair).collect();
		assert_eq!(LiftsBySource::try_from(map).err(), Some(LiftError::TooManySources));
	}

	#[test]
	fn late_block_non_identity_extension_end_to_end() {
		// The block ended at @2 and the committed root is at @5: a real extension bridges them.
		let all = leaves(5);
		let stream = ch(2000);
		let committed = root_at(&all, 5);
		let entries = BTreeMap::from([(stream, committed.0)]);
		let expected = streams_root(&entries).unwrap();
		let (_r, tree_proof) = gen_stream_proof(&entries, stream).unwrap();

		let interval = Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 2) };
		let lift =
			RequiresLift { advances: Vec::new(), extension: extension(&all, 2, 5), tree_proof };
		let streams = SourceStreams::from([(stream, vec![interval])]);
		assert_eq!(build_requires_entry(&streams, &[lift]).unwrap(), expected);
	}

	#[test]
	fn multi_stream_source_converges_on_one_root() {
		// Two streams at different frontiers both lift to the source's one `StreamsRoot`.
		let all = leaves(5);
		let (a, b) = (ch(2000), ch(3000));
		let (ra, rb) = (root_at(&all, 3), root_at(&all, 5));
		let entries = BTreeMap::from([(a, ra.0), (b, rb.0)]);
		let expected = streams_root(&entries).unwrap();
		let (_pa, proof_a) = gen_stream_proof(&entries, a).unwrap();
		let (_pb, proof_b) = gen_stream_proof(&entries, b).unwrap();

		let lift = |tree_proof| RequiresLift {
			advances: Vec::new(),
			extension: MMRExtensionProof::identity(),
			tree_proof,
		};
		// SourceStreams is keyed, so it iterates a, b — the order the lifts must match.
		let streams = SourceStreams::from([
			(a, vec![Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) }]),
			(b, vec![Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 5) }]),
		]);
		assert_eq!(
			build_requires_entry(&streams, &[lift(proof_a), lift(proof_b)]).unwrap(),
			expected
		);
	}

	#[test]
	fn build_requires_covers_multiple_sources() {
		// Two sources, each one stream → a two-entry RequiresSet, each entry the source's own root.
		let all = leaves(3);
		let committed = root_at(&all, 3);
		let (src_a, src_b) = (ParaId::from(1000), ParaId::from(2000));
		let stream = ch(4000);
		let entries = BTreeMap::from([(stream, committed.0)]);
		let expected = streams_root(&entries).unwrap();

		let record_for = |source| {
			let (_r, tree_proof) = gen_stream_proof(&entries, stream).unwrap();
			let record = ConsumptionRecord {
				entries: BTreeMap::from([(
					source,
					BTreeMap::from([(
						stream,
						Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) },
					)]),
				)]),
			};
			let lift = RequiresLift {
				advances: Vec::new(),
				extension: MMRExtensionProof::identity(),
				tree_proof,
			};
			(record, lift)
		};
		let (ra, la) = record_for(src_a);
		let (rb, lb) = record_for(src_b);
		let lifts = LiftsBySource::try_from(BTreeMap::from([(src_a, vec![la]), (src_b, vec![lb])]))
			.unwrap();

		let requires = build_requires(&[ra, rb], &lifts).unwrap().unwrap();
		assert_eq!(requires.len(), 2);
		assert_eq!(requires.get(src_a), Some(&expected));
		assert_eq!(requires.get(src_b), Some(&expected));
	}

	#[test]
	fn build_requires_entry_stitches_a_bundle_gap() {
		// A bundle whose second block jumped @2 → @4: an advance bridges the gap, then the
		// extension reaches the committed @5.
		let all = leaves(5);
		let stream = ch(2000);
		let committed = root_at(&all, 5);
		let entries = BTreeMap::from([(stream, committed.0)]);
		let expected = streams_root(&entries).unwrap();
		let (_r, tree_proof) = gen_stream_proof(&entries, stream).unwrap();

		let intervals = vec![
			Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 2) },
			Interval { start: root_at(&all, 4), end: frontier_at(&all, 5) }, // gap @2 → @4
		];
		let lift = RequiresLift {
			advances: vec![extension(&all, 2, 4)],    // bridges the gap
			extension: MMRExtensionProof::identity(), // endpoint @5 already the committed root
			tree_proof,
		};
		let streams = SourceStreams::from([(stream, intervals)]);
		assert_eq!(build_requires_entry(&streams, &[lift]).unwrap(), expected);
	}

	#[test]
	fn lift_count_must_match_stream_count() {
		let all = leaves(3);
		let stream = ch(2000);
		let streams = SourceStreams::from([(
			stream,
			vec![Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) }],
		)]);
		let lift = || RequiresLift {
			advances: Vec::new(),
			extension: MMRExtensionProof::identity(),
			tree_proof: StreamProof { steps: Default::default() },
		};
		// One stream, no lifts, and one stream, two lifts — both mismatch.
		assert_eq!(build_requires_entry(&streams, &[]), Err(LiftError::LiftCountMismatch));
		assert_eq!(
			build_requires_entry(&streams, &[lift(), lift()]),
			Err(LiftError::LiftCountMismatch)
		);
	}

	#[test]
	fn build_requires_entry_rejects_a_backward_extension() {
		// A forged extension that does not go strictly forward fails verification → BadExtension,
		// before any root is synthesized.
		let all = leaves(5);
		let stream = ch(2000);
		let (_r, tree_proof) =
			gen_stream_proof(&BTreeMap::from([(stream, root_at(&all, 5).0)]), stream).unwrap();
		let streams = SourceStreams::from([(
			stream,
			vec![Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) }],
		)]);
		// leaf_count 1 <= the endpoint's 3 leaves → NotForward inside `calculate_root` →
		// BadExtension.
		let lift = RequiresLift {
			advances: Vec::new(),
			extension: MMRExtensionProof { leaf_count: 1, connecting_nodes: BoundedVec::new() },
			tree_proof,
		};
		assert_eq!(build_requires_entry(&streams, &[lift]), Err(LiftError::BadExtension));
	}

	#[test]
	fn stitch_ignores_the_first_interval_start() {
		// `first.start` is the boundary with the previous candidate and is deliberately unchecked;
		// garbage there does not affect the stitched endpoint.
		let all = leaves(5);
		let garbage =
			Interval { start: MmrRoot(H256::repeat_byte(0xEE)), end: frontier_at(&all, 2) };
		let cont = Interval { start: root_at(&all, 2), end: frontier_at(&all, 5) };
		assert_eq!(stitch(&[garbage, cont], &[]).unwrap(), frontier_at(&all, 5));
	}

	#[test]
	fn build_requires_entry_rejects_a_malformed_tree_proof() {
		// A hand-built step with an out-of-range split bit (a one-stream tree has no real steps).
		let all = leaves(3);
		let stream = ch(2000);
		let streams = SourceStreams::from([(
			stream,
			vec![Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) }],
		)]);
		// `split_bit == KEY_BITS` (64) is past the key; the fold rejects it.
		let bad = StreamProof {
			steps: BoundedVec::try_from(vec![TreeStep { split_bit: 64, sibling: H256::zero() }])
				.unwrap(),
		};
		let lift = RequiresLift {
			advances: Vec::new(),
			extension: MMRExtensionProof::identity(),
			tree_proof: bad,
		};
		assert_eq!(build_requires_entry(&streams, &[lift]), Err(LiftError::BadTreeProof));
	}

	#[test]
	fn build_requires_entry_flags_missing_and_stray_advances() {
		// stitch's advance-count errors, reached through the entry path rather than in isolation.
		let all = leaves(5);
		let stream = ch(2000);
		let (_r, tree_proof) =
			gen_stream_proof(&BTreeMap::from([(stream, root_at(&all, 5).0)]), stream).unwrap();
		let mk = |intervals, advances| {
			let lift = RequiresLift {
				advances,
				extension: MMRExtensionProof::identity(),
				tree_proof: tree_proof.clone(),
			};
			build_requires_entry(&SourceStreams::from([(stream, intervals)]), &[lift])
		};

		// Gap @2 → @4 with no advance to bridge it.
		let gapped = vec![
			Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 2) },
			Interval { start: root_at(&all, 4), end: frontier_at(&all, 5) },
		];
		assert_eq!(mk(gapped, Vec::new()), Err(LiftError::MissingAdvance));

		// Continuous @2 → @2 but an advance supplied anyway.
		let continuous = vec![
			Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 2) },
			Interval { start: root_at(&all, 2), end: frontier_at(&all, 5) },
		];
		assert_eq!(mk(continuous, vec![extension(&all, 2, 4)]), Err(LiftError::StrayAdvance));
	}

	#[test]
	fn divergent_roots_rejected() {
		let all = leaves(3);
		let root3 = root_at(&all, 3);
		let (sa, sb) = (ch(2000), ch(3000));

		// Two single-stream trees → each stream's tree_proof folds to a DIFFERENT StreamsRoot.
		let (_ra, proof_a) = gen_stream_proof(&BTreeMap::from([(sa, root3.0)]), sa).unwrap();
		let (_rb, proof_b) = gen_stream_proof(&BTreeMap::from([(sb, root3.0)]), sb).unwrap();

		let mk = |tree_proof| RequiresLift {
			advances: Vec::new(),
			extension: MMRExtensionProof::identity(),
			tree_proof,
		};
		let streams = SourceStreams::from([
			(sa, vec![Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) }]),
			(sb, vec![Interval { start: MmrRoot(H256::zero()), end: frontier_at(&all, 3) }]),
		]);
		assert_eq!(
			build_requires_entry(&streams, &[mk(proof_a), mk(proof_b)]),
			Err(LiftError::DivergentRoots),
		);
	}

	/// Single-leaf inclusion proof for leaf `index` of an `n`-leaf MMR (`mmr_lib`'s `gen_proof`).
	fn inclusion(all: &[Hash], n: usize, index: usize) -> MmrInclusionProof {
		let store = MemStore::<Hash>::default();
		let mut mmr = MemMMR::<Hash, SpecMerge>::new(0, &store);
		for l in &all[..n] {
			mmr.push(*l).unwrap();
		}
		let proof = mmr.gen_proof(vec![leaf_index_to_pos(index as u64)]).unwrap();
		MmrInclusionProof {
			mmr_size: mmr_size(n),
			items: BoundedVec::truncate_from(proof.proof_items().to_vec()),
		}
	}

	#[test]
	fn inclusion_verify_head_pins_head_and_derives_root() {
		let all = leaves(6);
		// 6 leaves → head = index 5 (a lone smallest peak with a 1-step sibling path AND one other
		// peak: count_ones(6) - 1 = 1), exercising both halves of the item split.
		let proof = inclusion(&all, 6, 5);

		// Correct head leaf → head position 5 + the frontier of exactly these 6 leaves.
		let (pos, frontier) = proof.verify_head(all[5]).expect("well-formed head proof");
		assert_eq!(pos, MessagePosition(5));
		assert_eq!(frontier.leaf_count(), 6);
		assert_eq!(frontier.root(), root_at(&all, 6));

		// Another leaf under the same proof gives a different root, so an old leaf can't pass as
		// the head.
		let (_, forged) = proof.verify_head(all[0]).expect("shape still parses");
		assert_ne!(forged.root(), root_at(&all, 6));

		// Wrong item count (one extra item) → structural reject.
		let mut bad = proof.clone();
		bad.items.try_push(H256::zero()).expect("below the bound; qed");
		assert_eq!(bad.verify_head(all[5]), Err(ProofError::InvalidProof));

		// Invalid `mmr_size` (2 is not a valid MMR node count) → reject, no panic.
		assert_eq!(
			MmrInclusionProof { mmr_size: 2, items: BoundedVec::new() }.verify_head(all[5]),
			Err(ProofError::InvalidProof),
		);
	}

	#[test]
	fn inclusion_verify_head_boundary_shapes() {
		// The `path_len = trailing_zeros` / `other_peaks = count_ones - 1` formulas at their
		// extremes.

		// n = 1: a single-leaf MMR. The head proof has zero items (no sibling path, no other
		// peak).
		let all1 = leaves(1);
		let (pos1, f1) = inclusion(&all1, 1, 0).verify_head(all1[0]).expect("n=1 head");
		assert_eq!(pos1, MessagePosition(0));
		assert_eq!(f1.leaf_count(), 1);
		assert_eq!(f1.root(), root_at(&all1, 1));

		// n = 8: a perfect single-peak MMR. A full 3-step sibling path with no other peaks.
		let all8 = leaves(8);
		let (pos8, f8) = inclusion(&all8, 8, 7).verify_head(all8[7]).expect("n=8 head");
		assert_eq!(pos8, MessagePosition(7));
		assert_eq!(f8.leaf_count(), 8);
		assert_eq!(f8.root(), root_at(&all8, 8));
	}

	#[test]
	fn inclusion_verify_leaf_binds_position_and_value() {
		let all = leaves(6);
		let want = root_at(&all, 6);
		let proof = inclusion(&all, 6, 3);

		// Correct leaf at its position → the committed stream root.
		assert_eq!(proof.verify_leaf(MessagePosition(3), all[3]), Ok(want));
		// Tampered leaf value → a different root (never the committed one).
		assert_ne!(proof.verify_leaf(MessagePosition(3), H256::repeat_byte(0xAA)), Ok(want));
		// Correct leaf claimed at the wrong position → a different root.
		assert_ne!(proof.verify_leaf(MessagePosition(4), all[3]), Ok(want));
		// Position at/after the leaf count (6 leaves → valid 0..=5) → reject.
		assert_eq!(
			proof.verify_leaf(MessagePosition(6), all[3]),
			Err(ProofError::PositionOutOfRange)
		);
		// Invalid `mmr_size` → reject, no panic.
		assert_eq!(
			MmrInclusionProof { mmr_size: 2, items: BoundedVec::new() }
				.verify_leaf(MessagePosition(0), all[0]),
			Err(ProofError::InvalidProof),
		);
	}

	#[test]
	fn oversized_inclusion_proof_fails_to_decode() {
		// The bound is in the type, so an oversized proof is rejected at the length prefix.
		let max = MAX_INCLUSION_PROOF_ITEMS as usize;
		let at_bound = (mmr_size(6) as u64, vec![H256::zero(); max]).encode();
		assert!(MmrInclusionProof::decode(&mut &at_bound[..]).is_ok());
		let over = (mmr_size(6) as u64, vec![H256::zero(); max + 1]).encode();
		assert!(MmrInclusionProof::decode(&mut &over[..]).is_err());
	}

	/// Found by the `lift_inclusion` fuzzer: a padded 1-leaf proof used to verify.
	#[test]
	fn inclusion_verify_leaf_rejects_padding() {
		let all = leaves(6);
		let one = inclusion(&all, 1, 0);
		assert!(one.items.is_empty());
		assert_eq!(one.verify_leaf(MessagePosition(0), all[0]), Ok(root_at(&all, 1)));
		let mut padded = one.clone();
		padded.items.try_push(H256::repeat_byte(0xAB)).expect("below the bound; qed");
		assert_eq!(padded.verify_leaf(MessagePosition(0), all[0]), Err(ProofError::InvalidProof));

		let mut longer = inclusion(&all, 6, 3);
		longer.items.try_push(H256::zero()).expect("below the bound; qed");
		assert_eq!(longer.verify_leaf(MessagePosition(3), all[3]), Err(ProofError::InvalidProof));
	}

	/// 130 leaves gets us past 127, the first count with seven peaks.
	#[test]
	fn leaf_proof_len_matches_mmr_lib() {
		let all = leaves(130);
		for n in 1..=130 {
			for i in 0..n {
				assert_eq!(
					leaf_proof_len(n as u64, i as u64),
					inclusion(&all, n, i).items.len(),
					"leaf {i} of {n}"
				);
			}
		}
	}

	#[test]
	fn inclusion_verify_head_rejects_non_head_proof() {
		let all = leaves(6);
		// Leaf 2's proof has 3 items; a 6-leaf head proof has 2.
		let non_head = inclusion(&all, 6, 2);
		assert_eq!(non_head.verify_head(all[2]), Err(ProofError::InvalidProof));
	}

	#[test]
	fn inclusion_head_and_leaf_agree_on_root() {
		// `verify_head`'s own peak walk and `mmr_lib::calculate_root` must agree.
		let all = leaves(6);
		let proof = inclusion(&all, 6, 5);
		let (pos, frontier) = proof.verify_head(all[5]).expect("head verifies");
		assert_eq!(pos, MessagePosition(5));
		let via_head = frontier.root();
		let via_leaf = proof.verify_leaf(pos, all[5]).expect("leaf verifies");
		assert_eq!(via_head, via_leaf);
		assert_eq!(via_head, root_at(&all, 6));
	}
}