eml 0.9.1

//! RFC 9162 proof generation and verification for EML.
//!
//! Implements the standard Merkle tree proof algorithms adapted for
//! `Vec<u8>` digests and `dyn Hasher`. These are free functions — they
//! operate on leaf hash sequences, not on `Log` state.

use crate::Hasher;

// ============================================================================
// Tree helpers
// ============================================================================

/// Largest power of 2 strictly less than `n`.
///
/// Defined for `n > 1`. Panics if `n <= 1`.
pub(crate) fn largest_pow2_lt(n: u64) -> u64 {
    debug_assert!(n > 1, "largest_pow2_lt requires n > 1, got {n}");
    1u64 << (63 - (n - 1).leading_zeros())
}

/// Batch Merkle Tree Hash (RFC 9162 §2.1).
///
/// Computes the root hash of an ordered list of leaf hashes using the
/// recursive definition. Specification oracle — used by test code only.
#[cfg(test)]
pub(crate) fn mth(hasher: &dyn Hasher, leaves: &[Vec<u8>]) -> Vec<u8> {
    match leaves.len() {
        0 => hasher.empty(),
        1 => leaves[0].clone(),
        n => {
            let k = largest_pow2_lt(n as u64) as usize;
            let left = mth(hasher, &leaves[..k]);
            let right = mth(hasher, &leaves[k..]);
            hasher.node(&left, &right)
        },
    }
}

// ============================================================================
// Proof generation (free functions)
// ============================================================================

/// PATH algorithm for inclusion proofs (RFC 9162 §2.1.3).
///
/// Recursively computes the sibling hashes from leaf `m` to the root.
/// Specification oracle — superseded by `Log::path` for production use.
#[cfg(test)]
pub(crate) fn gen_path(hasher: &dyn Hasher, m: usize, leaves: &[Vec<u8>]) -> Vec<Vec<u8>> {
    let n = leaves.len();
    if n == 1 {
        return Vec::new();
    }
    let k = largest_pow2_lt(n as u64) as usize;
    if m < k {
        let mut result = gen_path(hasher, m, &leaves[..k]);
        result.push(mth(hasher, &leaves[k..]));
        result
    } else {
        let mut result = gen_path(hasher, m - k, &leaves[k..]);
        result.push(mth(hasher, &leaves[..k]));
        result
    }
}

/// SUBPROOF algorithm for consistency proofs (RFC 9162 §2.1.4).
///
/// Recursively computes the intermediate hashes proving that the first
/// `m` leaves are a prefix of the `leaves` slice.
/// Specification oracle — superseded by `Log::subproof` for production use.
#[cfg(test)]
pub(crate) fn gen_subproof(
    hasher: &dyn Hasher,
    m: usize,
    leaves: &[Vec<u8>],
    b: bool,
) -> Vec<Vec<u8>> {
    let n = leaves.len();
    if m == n {
        if b {
            return Vec::new();
        } else {
            return vec![mth(hasher, leaves)];
        }
    }
    let k = largest_pow2_lt(n as u64) as usize;
    if m <= k {
        let mut result = gen_subproof(hasher, m, &leaves[..k], b);
        result.push(mth(hasher, &leaves[k..]));
        result
    } else {
        let mut result = gen_subproof(hasher, m - k, &leaves[k..], false);
        result.push(mth(hasher, &leaves[..k]));
        result
    }
}

// ============================================================================
// Proof types
// ============================================================================

/// Inclusion proof — proves a leaf at `index` exists in a tree of `tree_size`.
///
/// Generated by [`Log::inclusion_proof`](crate::Log::inclusion_proof) and
/// verified by [`verify_inclusion`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct InclusionProof {
    /// 0-based leaf index.
    pub index: u64,
    /// Size of the tree for which this proof is valid.
    pub tree_size: u64,
    /// Sibling hashes from leaf to root.
    pub path: Vec<Vec<u8>>,
}

/// Consistency proof — proves a tree of `old_size` is a prefix of `new_size`.
///
/// Generated by [`Log::consistency_proof`](crate::Log::consistency_proof) and
/// verified by [`verify_consistency`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ConsistencyProof {
    /// Size of the older tree.
    pub old_size: u64,
    /// Size of the newer tree.
    pub new_size: u64,
    /// Intermediate hashes.
    pub path: Vec<Vec<u8>>,
}

// ============================================================================
// Proof verification (standalone — no Log needed)
// ============================================================================

/// Verify an inclusion proof (RFC 9162 §2.1.3.2).
///
/// Returns `true` if the proof demonstrates that `leaf_hash` is the leaf at
/// `proof.index` in a tree of `proof.tree_size` with the given `root`.
///
/// This is a standalone verifier — no [`Log`](crate::Log) is needed.
pub fn verify_inclusion(
    hasher: &dyn Hasher,
    leaf_hash: &[u8],
    proof: &InclusionProof,
    root: &[u8],
) -> bool {
    if proof.index >= proof.tree_size {
        return false;
    }

    let mut fn_ = proof.index;
    let mut sn = proof.tree_size - 1;
    let mut r = leaf_hash.to_vec();

    for p in &proof.path {
        if sn == 0 {
            return false;
        }
        if (fn_ & 1 == 1) || fn_ == sn {
            r = hasher.node(p, &r);
            while fn_ & 1 == 0 && fn_ != 0 {
                fn_ >>= 1;
                sn >>= 1;
            }
        } else {
            r = hasher.node(&r, p);
        }
        fn_ >>= 1;
        sn >>= 1;
    }

    sn == 0 && r == root
}

/// Verify a consistency proof (RFC 9162 §2.1.4.2).
///
/// Returns `true` if the proof demonstrates that the tree of `proof.old_size`
/// with `old_root` is a prefix of the tree of `proof.new_size` with `new_root`.
///
/// This is a standalone verifier — no [`Log`](crate::Log) is needed.
pub fn verify_consistency(
    hasher: &dyn Hasher,
    proof: &ConsistencyProof,
    old_root: &[u8],
    new_root: &[u8],
) -> bool {
    if proof.old_size == 0 || proof.old_size >= proof.new_size {
        return false;
    }

    // Build the effective path: if old_size is a power of 2, prepend old_root.
    let path: Vec<&[u8]> = if proof.old_size.is_power_of_two() {
        std::iter::once(old_root)
            .chain(proof.path.iter().map(|v| v.as_slice()))
            .collect()
    } else {
        proof.path.iter().map(|v| v.as_slice()).collect()
    };

    if path.is_empty() {
        return false;
    }

    let mut fn_ = proof.old_size - 1;
    let mut sn = proof.new_size - 1;

    // Strip common prefix of trailing ones.
    while fn_ & 1 == 1 {
        fn_ >>= 1;
        sn >>= 1;
    }

    let mut fr = path[0].to_vec();
    let mut sr = path[0].to_vec();

    for c in &path[1..] {
        if sn == 0 {
            return false;
        }
        if (fn_ & 1 == 1) || fn_ == sn {
            fr = hasher.node(c, &fr);
            sr = hasher.node(c, &sr);
            while fn_ & 1 == 0 && fn_ != 0 {
                fn_ >>= 1;
                sn >>= 1;
            }
        } else {
            sr = hasher.node(&sr, c);
        }
        fn_ >>= 1;
        sn >>= 1;
    }

    sn == 0 && fr == old_root && sr == new_root
}

// Elided proofs — wire-optimized inclusion proofs for EML
// ============================================================================

/// An inclusion proof with null subtree siblings elided.
///
/// Wire-optimized proof for EML: siblings covering ranges entirely
/// within the null prefix are omitted (represented as `None`). The
/// client rehydrates them deterministically using interval arithmetic
/// and the algorithm's [`NullTable`](crate::NullTable).
///
/// # Wire Size
///
/// For an algorithm active for `nₐ` appends in a tree of `n` total,
/// the elided proof contains `O(log nₐ)` entries instead of `O(log n)`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ElidedInclusionProof {
    /// 0-based leaf index.
    pub index: u64,
    /// Size of the tree for which this proof is valid.
    pub tree_size: u64,
    /// Sibling hashes from leaf to root. `None` = elided null subtree.
    pub path: Vec<Option<Vec<u8>>>,
}

impl ElidedInclusionProof {
    /// Count of non-elided (transmitted) siblings.
    pub fn wire_len(&self) -> usize {
        self.path.iter().filter(|e| e.is_some()).count()
    }
}

/// Compute the leaf-coverage range `[start, end)` for each sibling in an
/// inclusion proof path.
///
/// The returned vector is parallel to the proof path (leaf-adjacent first,
/// root-adjacent last). Each entry is `(start, end)` representing the
/// absolute range of leaves that the sibling subtree covers.
fn sibling_ranges(index: u64, tree_size: u64) -> Vec<(u64, u64)> {
    let mut ranges = Vec::new();
    walk_path(index, tree_size, 0, &mut ranges);
    ranges
}

/// Recursive tree walk matching `gen_path` traversal order.
fn walk_path(m: u64, n: u64, base: u64, out: &mut Vec<(u64, u64)>) {
    if n == 1 {
        return;
    }
    let k = largest_pow2_lt(n);
    if m < k {
        // Recurse into left subtree first (matching gen_path order).
        walk_path(m, k, base, out);
        // Right sibling covers [base+k, base+n).
        out.push((base + k, base + n));
    } else {
        // Recurse into right subtree first.
        walk_path(m - k, n - k, base + k, out);
        // Left sibling covers [base, base+k).
        out.push((base, base + k));
    }
}

/// Compute the hash of a null subtree covering `size` leaves.
///
/// For complete subtrees (power-of-2 size), this is a direct `NullTable`
/// lookup. For incomplete subtrees, this recursively decomposes using the
/// RFC 9162 splitting rule.
fn null_subtree_hash(hasher: &dyn Hasher, null_table: &mut crate::NullTable, size: u64) -> Vec<u8> {
    if size == 0 {
        return hasher.empty();
    }
    if size == 1 {
        return null_table.leaf_null().to_vec();
    }

    let k_bits = 63 - (size.leading_zeros() as usize);
    let k = 1u64 << k_bits;
    let left = null_table.get(hasher, k_bits).to_vec();

    let remainder = size - k;
    if remainder == 0 {
        return left;
    }

    let right = null_subtree_hash(hasher, null_table, remainder);
    hasher.node(&left, &right)
}

/// Elide null subtree siblings from a full inclusion proof.
///
/// Uses interval arithmetic to identify siblings whose entire
/// leaf-coverage range falls within an inactive gap (outside all
/// active epochs). These siblings are replaced with `None`.
///
/// Each epoch is `(start, end)` where `end == None` means the epoch
/// extends to the current tree size. Both the server (elider) and
/// client (rehydrator) share `tree_size`, `index`, and the epoch list,
/// ensuring lockstep agreement with zero wire overhead.
pub fn elide_inclusion_proof(
    proof: &InclusionProof,
    epochs: &[(u64, Option<u64>)],
) -> ElidedInclusionProof {
    let ranges = sibling_ranges(proof.index, proof.tree_size);

    let path: Vec<Option<Vec<u8>>> = proof
        .path
        .iter()
        .zip(ranges.iter())
        .map(|(hash, &(start, end))| {
            // A sibling is elidable if its entire coverage range [start, end)
            // is inactive — i.e., no position in [start, end) belongs to any
            // active epoch. Equivalently, no epoch overlaps [start, end).
            let any_active = epochs.iter().any(|&(ep_start, ep_end)| {
                let ep_end = ep_end.unwrap_or(proof.tree_size);
                // Two intervals [start, end) and [ep_start, ep_end) overlap
                // iff start < ep_end && ep_start < end.
                start < ep_end && ep_start < end
            });
            if any_active { Some(hash.clone()) } else { None }
        })
        .collect();

    ElidedInclusionProof {
        index: proof.index,
        tree_size: proof.tree_size,
        path,
    }
}

/// Rehydrate an elided inclusion proof by synthesizing null subtree hashes.
///
/// For each elided sibling (`None` entry), computes the deterministic null
/// subtree hash from the [`NullTable`](crate::NullTable). The returned proof
/// is a standard [`InclusionProof`] that verifies against the unmodified
/// [`verify_inclusion`] function.
///
/// # Arguments
///
/// * `elided` — The elided proof from the server.
/// * `hasher` — The algorithm's hasher instance.
pub fn rehydrate_inclusion_proof(
    elided: &ElidedInclusionProof,
    hasher: &dyn Hasher,
) -> InclusionProof {
    // Guard against degenerate inputs from untrusted wire data.
    // A tree of size 0 or 1 has no siblings; an out-of-bounds index is
    // nonsensical. Return a passthrough that harmlessly fails verification.
    if elided.tree_size <= 1 || elided.index >= elided.tree_size {
        return InclusionProof {
            index: elided.index,
            tree_size: elided.tree_size,
            path: elided
                .path
                .iter()
                .map(|e| e.clone().unwrap_or_default())
                .collect(),
        };
    }

    let ranges = sibling_ranges(elided.index, elided.tree_size);
    let mut null_table = crate::NullTable::new(hasher);

    let path: Vec<Vec<u8>> = elided
        .path
        .iter()
        .zip(ranges.iter())
        .map(|(entry, &(start, end))| {
            match entry {
                Some(hash) => hash.clone(),
                None => {
                    // Sibling covers [start, end), entirely in null prefix.
                    let size = end - start;
                    null_subtree_hash(hasher, &mut null_table, size)
                },
            }
        })
        .collect();

    InclusionProof {
        index: elided.index,
        tree_size: elided.tree_size,
        path,
    }
}
// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use crate::test_hashers::Sha256Hasher;

    #[test]
    fn largest_pow2_lt_cases() {
        assert_eq!(largest_pow2_lt(2), 1);
        assert_eq!(largest_pow2_lt(3), 2);
        assert_eq!(largest_pow2_lt(4), 2);
        assert_eq!(largest_pow2_lt(5), 4);
        assert_eq!(largest_pow2_lt(8), 4);
        assert_eq!(largest_pow2_lt(9), 8);
        assert_eq!(largest_pow2_lt(16), 8);
        assert_eq!(largest_pow2_lt(17), 16);
        // 32-bit boundary: values above 2^32 must work.
        assert_eq!(largest_pow2_lt(1u64 << 33), 1u64 << 32);
        assert_eq!(largest_pow2_lt((1u64 << 33) + 1), 1u64 << 33);
    }

    #[test]
    fn mth_matches_incremental() {
        let h = Sha256Hasher;
        let leaves: Vec<Vec<u8>> = (0..7u8).map(|i| h.leaf(&[i])).collect();
        let batch = mth(&h, &leaves);

        let n01 = h.node(&leaves[0], &leaves[1]);
        let n23 = h.node(&leaves[2], &leaves[3]);
        let n45 = h.node(&leaves[4], &leaves[5]);
        let n0123 = h.node(&n01, &n23);
        let n456 = h.node(&n45, &leaves[6]);
        let expected = h.node(&n0123, &n456);
        assert_eq!(batch, expected);
    }

    #[test]
    fn inclusion_proof_single_leaf() {
        let h = Sha256Hasher;
        let leaves = vec![h.leaf(b"only")];
        let root = mth(&h, &leaves);
        let path = gen_path(&h, 0, &leaves);
        assert!(path.is_empty());

        let proof = InclusionProof {
            index: 0,
            tree_size: 1,
            path,
        };
        assert!(verify_inclusion(&h, &leaves[0], &proof, &root));
    }

    #[test]
    fn inclusion_proof_roundtrip() {
        let h = Sha256Hasher;
        for size in [2, 3, 4, 5, 7, 8, 9, 15, 16, 17] {
            let leaves: Vec<Vec<u8>> = (0..size as u8).map(|i| h.leaf(&[i])).collect();
            let root = mth(&h, &leaves);

            for idx in 0..size {
                let path = gen_path(&h, idx, &leaves);
                let proof = InclusionProof {
                    index: idx as u64,
                    tree_size: size as u64,
                    path,
                };
                assert!(
                    verify_inclusion(&h, &leaves[idx], &proof, &root),
                    "inclusion proof failed: size={size}, idx={idx}"
                );

                // Wrong leaf should fail.
                let wrong_leaf = h.leaf(b"wrong");
                assert!(
                    !verify_inclusion(&h, &wrong_leaf, &proof, &root),
                    "wrong leaf should not verify: size={size}, idx={idx}"
                );
            }
        }
    }

    #[test]
    fn consistency_proof_roundtrip() {
        let h = Sha256Hasher;
        let max_size = 16;
        let all_leaves: Vec<Vec<u8>> = (0..max_size as u8).map(|i| h.leaf(&[i])).collect();

        for old_size in 1..max_size {
            for new_size in (old_size + 1)..=max_size {
                let old_root = mth(&h, &all_leaves[..old_size]);
                let new_root = mth(&h, &all_leaves[..new_size]);

                let path = gen_subproof(&h, old_size, &all_leaves[..new_size], true);
                let proof = ConsistencyProof {
                    old_size: old_size as u64,
                    new_size: new_size as u64,
                    path,
                };
                assert!(
                    verify_consistency(&h, &proof, &old_root, &new_root),
                    "consistency proof failed: old={old_size}, new={new_size}"
                );
            }
        }
    }

    // ---- Elided proof tests ----

    #[test]
    fn sibling_ranges_power_of_two() {
        // Tree of 8 leaves, proof for leaf 6.
        let ranges = sibling_ranges(6, 8);
        // gen_path traversal for m=6, n=8:
        //   k=4, m>=k → recurse right (m=2, n=4, base=4)
        //     k=2, m>=k → recurse right (m=0, n=2, base=6)
        //       k=1, m<k → recurse left (m=0, n=1, base=6): base case
        //       push right sibling [7, 8)
        //     push left sibling [4, 6)
        //   push left sibling [0, 4)
        assert_eq!(ranges, vec![(7, 8), (4, 6), (0, 4)]);
    }

    #[test]
    fn elide_rehydrate_roundtrip() {
        let h = Sha256Hasher;
        // Build a tree: 8 null leaves (activation=8) + 8 real leaves.
        let activation = 8u64;
        let tree_size = 16u64;

        // Construct the projected leaf sequence.
        let null_leaf = h.null();
        let mut leaves = Vec::new();
        for _ in 0..activation {
            leaves.push(null_leaf.clone());
        }
        for i in 0..8u8 {
            leaves.push(h.leaf(&[i]));
        }

        let root = mth(&h, &leaves);

        // Proof for leaf at index 10 (in the real range).
        let path = gen_path(&h, 10, &leaves);
        let full_proof = InclusionProof {
            index: 10,
            tree_size,
            path,
        };

        // Sanity: full proof verifies.
        assert!(verify_inclusion(&h, &leaves[10], &full_proof, &root));

        // Elide null siblings.
        let elided = elide_inclusion_proof(&full_proof, &[(activation, None)]);

        // The elided proof should be shorter on the wire.
        assert!(
            elided.wire_len() < full_proof.path.len(),
            "elided proof should have fewer wire entries: wire_len={}, full_len={}",
            elided.wire_len(),
            full_proof.path.len()
        );

        // Rehydrate.
        let rehydrated = rehydrate_inclusion_proof(&elided, &h);

        // Rehydrated proof must equal the original full proof.
        assert_eq!(
            rehydrated, full_proof,
            "rehydrated proof differs from original"
        );

        // And it must verify.
        assert!(verify_inclusion(&h, &leaves[10], &rehydrated, &root));
    }

    #[test]
    fn elide_no_null_prefix() {
        let h = Sha256Hasher;
        // Algorithm active from genesis — no null prefix.
        let activation = 0u64;
        let leaves: Vec<Vec<u8>> = (0..8u8).map(|i| h.leaf(&[i])).collect();

        let path = gen_path(&h, 3, &leaves);
        let full_proof = InclusionProof {
            index: 3,
            tree_size: 8,
            path,
        };

        let elided = elide_inclusion_proof(&full_proof, &[(activation, None)]);

        // Nothing should be elided.
        assert_eq!(
            elided.wire_len(),
            full_proof.path.len(),
            "no siblings should be elided when activation=0"
        );
    }

    #[test]
    fn elide_large_null_prefix() {
        let h = Sha256Hasher;
        // Extreme case: activation at 960 in tree of 1024.
        // Algorithm only active for last 64 leaves.
        let activation = 960u64;
        let tree_size = 1024u64;

        let null_leaf = h.null();
        let mut leaves = Vec::new();
        for _ in 0..activation {
            leaves.push(null_leaf.clone());
        }
        for i in 0..64u8 {
            leaves.push(h.leaf(&[i]));
        }
        assert_eq!(leaves.len(), tree_size as usize);

        let root = mth(&h, &leaves);

        // Proof for leaf near the end (index 1000).
        let path = gen_path(&h, 1000, &leaves);
        let full_proof = InclusionProof {
            index: 1000,
            tree_size,
            path,
        };

        let elided = elide_inclusion_proof(&full_proof, &[(activation, None)]);

        // Full proof depth: log2(1024) = 10 siblings.
        assert_eq!(full_proof.path.len(), 10);

        // Elided should have substantially fewer wire entries.
        // (960 = 512+256+128+64, so left siblings at depths 0,1,2,3 from
        // root are entirely null → 4 elided, 6 remain)
        assert!(
            elided.wire_len() < full_proof.path.len(),
            "large null prefix should produce wire savings"
        );

        // Roundtrip.
        let rehydrated = rehydrate_inclusion_proof(&elided, &h);
        assert_eq!(rehydrated, full_proof);
        assert!(verify_inclusion(&h, &leaves[1000], &rehydrated, &root));
    }
}