polyc-mmr 2026.7.0

//! Verifiable event log on top of a Merkle Mountain Range (MMR).
//!
//! ## Why
//!
//! The Commonware journal that backs the polychrome event log gives
//! durability and ordering but doesn't make the log *tamper-evident*: a
//! reader has no way to verify the operator hasn't quietly rewritten an
//! event between when it was appended and when they replayed it. A
//! Merkle Mountain Range (append-only Merkle structure) closes that gap
//! cheaply:
//!
//! 1. Every appended event becomes one MMR leaf, with the leaf digest
//!    bound to the event's `(kind, payload)` bytes.
//! 2. After each turn (or any operator-chosen cadence) the control plane
//!    computes the current MMR root and signs it with the polychrome
//!    `ApprovalSigner` (ed25519). The signed root is persisted as its own
//!    event in the journal — same partition, same atomic batch.
//! 3. A future reader can ask for any past event's inclusion proof
//!    (O(log n) digests), verify it against the most recent signed root,
//!    and detect tampering.
//!
//! ## Layering vs the journal
//!
//! This crate is independent of the journal: it consumes
//! `(position, kind, payload)` triples and emits leaves + roots + proofs.
//! Integration with `polyc-eventlog` lives in the call sites that
//! append events — they extend the MMR alongside the journal write and
//! persist the signed root.
//!
//! ## Stability of the leaf hash
//!
//! The leaf digest is `SHA-256(position_be || kind_len_be || kind ||
//! payload_len_be || payload)` (lengths as 8-byte big-endian for
//! unambiguous framing). This is intentionally not the wire encoding of
//! the event so a future change to the on-disk format doesn't
//! invalidate historic proofs.

#![forbid(unsafe_code)]
#![warn(missing_docs)]
// The MMR mutex is held across short critical sections by design (the
// append/proof/root operations need a consistent view); ditto the
// first-doc-paragraph rule for the longer module/function summaries that
// don't fit one sentence.
#![allow(
    clippy::significant_drop_tightening,
    clippy::too_long_first_doc_paragraph
)]

use std::sync::Mutex;

use commonware_cryptography::{Hasher as _, Sha256, sha256::Digest as Sha256Digest};
use commonware_storage::merkle::{
    Bagging::ForwardFold,
    Location, Proof,
    mmr::{StandardHasher as Standard, mem::Mmr},
};
use polyc_crypto::approval::ApprovalSigner;
use serde::{Deserialize, Serialize};

/// Errors a verifiable-log operation can produce.
#[derive(Debug, thiserror::Error)]
pub enum MmrError {
    /// The position requested isn't a current MMR leaf.
    #[error("position {position} is not a known leaf (size {size})")]
    UnknownPosition {
        /// Position that was requested.
        position: u64,
        /// Current MMR leaf count.
        size: u64,
    },
    /// Producing the proof failed inside `commonware-storage`.
    #[error("proof: {0}")]
    Proof(String),
    /// Mutex poisoned — a previous panic left the state inconsistent.
    #[error("mmr lock poisoned")]
    Poisoned,
}

/// Compute the canonical leaf digest for an event.
///
/// Format: `SHA-256(position_be || kind_len_be || kind || payload_len_be
/// || payload)`. The length-prefixing keeps `kind` and `payload` from
/// colliding under concatenation (`a||b == c||d` only when the lengths
/// also match). Position is included so reordering events produces a
/// distinct leaf — defends against a "shuffle without changing
/// contents" attack.
#[must_use]
pub fn leaf_digest(position: u64, kind: &str, payload: &[u8]) -> Sha256Digest {
    let mut hasher = Sha256::new();
    hasher.update(&position.to_be_bytes());
    hasher.update(&(kind.len() as u64).to_be_bytes());
    hasher.update(kind.as_bytes());
    hasher.update(&(payload.len() as u64).to_be_bytes());
    hasher.update(payload);
    hasher.finalize()
}

/// A signed MMR root, ready to embed in the event log.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
pub struct SignedRoot {
    /// Hex-encoded 32-byte SHA-256 root.
    pub root_hex: String,
    /// Number of MMR leaves the root covers (1-indexed total count).
    pub leaf_count: u64,
    /// Hex-encoded ed25519 signature over `(leaf_count_be || root_bytes)`.
    pub signature_hex: String,
    /// Hex-encoded ed25519 public key of the signer.
    pub signer_pk_hex: String,
}

/// Hex-encoded element inclusion proof for one leaf.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
pub struct InclusionProof {
    /// MMR leaf position the proof targets.
    pub position: u64,
    /// MMR leaf count at the moment the proof was issued (= root scope).
    pub leaf_count: u64,
    /// Number of MMR peaks pruned before this proof was generated; the
    /// verifier needs the same value the prover used. Today the polychrome
    /// `inclusion_proof` API always passes 0 (no pruning), so this field
    /// is always 0 in current writes; the field is on the wire so
    /// historical proofs survive a future change to enable pruning.
    pub inactive_peaks: u64,
    /// Hex-encoded digests that lift the leaf to the root.
    pub digests_hex: Vec<String>,
}

/// Namespace separator for signed roots — keeps a root-signature from
/// being valid in any other domain (HITL approval, handoff, etc.).
const ROOT_SIGNING_NAMESPACE: &[u8] = b"polychrome.mmr.signed_root.v1";

/// Verifiable-log handle. Wraps an in-memory MMR + the standard SHA-256
/// hasher. Thread-safe; multiple appenders serialise through the mutex
/// (the journal is single-writer per partition, so contention is
/// minimal in practice).
pub struct VerifiableLog {
    inner: Mutex<Inner>,
}

struct Inner {
    mmr: Mmr<Sha256Digest>,
    hasher: Standard<Sha256>,
    /// Cached current leaf count (== position the next `append` will
    /// receive). Mirrors the MMR's internal size but cheaper to read.
    leaf_count: u64,
}

impl Default for VerifiableLog {
    fn default() -> Self {
        Self::new()
    }
}

impl VerifiableLog {
    /// Build a fresh, empty log.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            inner: Mutex::new(Inner {
                mmr: Mmr::new(),
                hasher: Standard::new(ForwardFold),
                leaf_count: 0,
            }),
        }
    }

    /// Append an event leaf and return the position assigned to it
    /// (matches the journal position for the same event when both write
    /// in lockstep).
    ///
    /// # Errors
    ///
    /// Returns [`MmrError::Proof`] if the underlying MMR batch fails,
    /// [`MmrError::Poisoned`] if the lock is poisoned.
    pub fn append(&self, kind: &str, payload: &[u8]) -> Result<u64, MmrError> {
        let mut guard = self.inner.lock().map_err(|_| MmrError::Poisoned)?;
        let position = guard.leaf_count;
        let digest = leaf_digest(position, kind, payload);
        let batch = guard
            .mmr
            .new_batch()
            .add(&guard.hasher, &digest)
            .merkleize(&guard.mmr, &guard.hasher);
        guard
            .mmr
            .apply_batch(&batch)
            .map_err(|e| MmrError::Proof(format!("apply_batch: {e:?}")))?;
        guard.leaf_count += 1;
        Ok(position)
    }

    /// Current MMR leaf count.
    ///
    /// # Errors
    ///
    /// Returns [`MmrError::Poisoned`] if the lock is poisoned.
    pub fn leaf_count(&self) -> Result<u64, MmrError> {
        Ok(self
            .inner
            .lock()
            .map_err(|_| MmrError::Poisoned)?
            .leaf_count)
    }

    /// Compute the current MMR root.
    ///
    /// # Errors
    ///
    /// Returns [`MmrError::Proof`] if the underlying MMR returns an error.
    pub fn root(&self) -> Result<Sha256Digest, MmrError> {
        let guard = self.inner.lock().map_err(|_| MmrError::Poisoned)?;
        guard
            .mmr
            .root(&guard.hasher, 0)
            .map_err(|e| MmrError::Proof(format!("root: {e:?}")))
    }

    /// Sign the current root with `signer`. The signed bytes are
    /// `leaf_count_be (8 bytes) || root_bytes (32 bytes)` under the
    /// `polychrome.mmr.signed_root.v1` namespace.
    ///
    /// # Errors
    ///
    /// Returns [`MmrError::Proof`] on any underlying failure.
    pub fn sign_root(&self, signer: &ApprovalSigner) -> Result<SignedRoot, MmrError> {
        let (root, leaf_count) = {
            let guard = self.inner.lock().map_err(|_| MmrError::Poisoned)?;
            let root = guard
                .mmr
                .root(&guard.hasher, 0)
                .map_err(|e| MmrError::Proof(format!("root: {e:?}")))?;
            (root, guard.leaf_count)
        };
        let mut msg = Vec::with_capacity(8 + 32);
        msg.extend_from_slice(&leaf_count.to_be_bytes());
        msg.extend_from_slice(root.as_ref());
        // ApprovalSigner uses the fixed `polychrome.v1` namespace; we
        // prefix the message with [`ROOT_SIGNING_NAMESPACE`] so a
        // signature minted here can't be replayed as an approval (the
        // approval canonical-JSON form starts with `{`, never with our
        // namespace bytes).
        let mut to_sign = Vec::with_capacity(ROOT_SIGNING_NAMESPACE.len() + msg.len());
        to_sign.extend_from_slice(ROOT_SIGNING_NAMESPACE);
        to_sign.extend_from_slice(&msg);
        let signature = signer.sign(&to_sign);
        let signer_pk = signer.public_key_bytes();
        Ok(SignedRoot {
            root_hex: hex::encode(root.as_ref()),
            leaf_count,
            signature_hex: hex::encode(signature),
            signer_pk_hex: hex::encode(signer_pk),
        })
    }

    /// Produce an inclusion proof for the leaf at `position`.
    ///
    /// # Errors
    ///
    /// Returns [`MmrError::UnknownPosition`] if `position` is past the
    /// last appended leaf, [`MmrError::Proof`] if the underlying MMR
    /// can't build the proof.
    pub fn inclusion_proof(&self, position: u64) -> Result<InclusionProof, MmrError> {
        let guard = self.inner.lock().map_err(|_| MmrError::Poisoned)?;
        if position >= guard.leaf_count {
            return Err(MmrError::UnknownPosition {
                position,
                size: guard.leaf_count,
            });
        }
        let proof = guard
            .mmr
            .proof(&guard.hasher, Location::new(position), 0)
            .map_err(|e| MmrError::Proof(format!("proof: {e:?}")))?;
        // `commonware_storage` exposes `inactive_peaks` as `usize`; we
        // serialise as `u64` so the wire form is stable across 32-bit and
        // 64-bit hosts. The polychrome `inclusion_proof` API always
        // requests proofs with 0 inactive peaks (no pruning), so this is
        // 0 today — we still capture it so a future pruning change
        // doesn't silently invalidate historical proofs.
        let inactive_peaks = proof.inactive_peaks as u64;
        Ok(InclusionProof {
            position,
            leaf_count: guard.leaf_count,
            inactive_peaks,
            digests_hex: proof
                .digests
                .iter()
                .map(|d| hex::encode(d.as_ref()))
                .collect(),
        })
    }
}

/// Verify that a `(kind, payload)` event appears in the log at the
/// given position, against a [`SignedRoot`] the verifier already trusts
/// (e.g. obtained from the signing key's known public key).
///
/// Pure / stateless — accepts hex inputs as serialised by
/// [`VerifiableLog::sign_root`] + [`VerifiableLog::inclusion_proof`].
///
/// # Errors
///
/// Returns `Ok(false)` for a structurally-valid-but-mismatched proof.
/// Returns `Err` with a string describing the failure for malformed
/// inputs.
pub fn verify(
    root: &SignedRoot,
    proof: &InclusionProof,
    kind: &str,
    payload: &[u8],
) -> Result<bool, String> {
    if proof.leaf_count != root.leaf_count {
        return Ok(false);
    }
    let leaf = leaf_digest(proof.position, kind, payload);
    let mut digests = Vec::with_capacity(proof.digests_hex.len());
    for hex_d in &proof.digests_hex {
        let bytes = hex::decode(hex_d).map_err(|e| format!("digest hex: {e}"))?;
        let arr: [u8; 32] = bytes
            .try_into()
            .map_err(|_| "digest length != 32".to_owned())?;
        digests.push(Sha256Digest::from(arr));
    }
    let root_bytes = hex::decode(&root.root_hex).map_err(|e| format!("root hex: {e}"))?;
    let arr: [u8; 32] = root_bytes
        .try_into()
        .map_err(|_| "root length != 32".to_owned())?;
    let root_digest = Sha256Digest::from(arr);

    // Wire form carries `inactive_peaks` as u64; the storage Proof type
    // expects usize. On a 64-bit host this is a no-op; on a 32-bit host
    // we refuse to silently truncate.
    let inactive_peaks = usize::try_from(proof.inactive_peaks).map_err(|_| {
        format!(
            "inactive_peaks {} exceeds usize on this target",
            proof.inactive_peaks
        )
    })?;
    let merkle_proof = Proof::<commonware_storage::merkle::mmr::Family, Sha256Digest> {
        leaves: Location::new(proof.leaf_count),
        inactive_peaks,
        digests,
    };
    let hasher: Standard<Sha256> = Standard::new(ForwardFold);
    Ok(merkle_proof.verify_element_inclusion(
        &hasher,
        &leaf,
        Location::new(proof.position),
        &root_digest,
    ))
}

/// Verify the ed25519 signature on a [`SignedRoot`] against a known
/// signer public key. The two-step check is by design: a verifier first
/// confirms the root is signed by the expected key, then uses [`verify`]
/// to check element inclusion under that root.
///
/// # Errors
///
/// Returns `Err` for malformed hex inputs.
pub fn verify_root_signature(root: &SignedRoot, expected_pk_hex: &str) -> Result<bool, String> {
    if !root.signer_pk_hex.eq_ignore_ascii_case(expected_pk_hex) {
        return Ok(false);
    }
    let pk_bytes = hex::decode(&root.signer_pk_hex).map_err(|e| format!("pk hex: {e}"))?;
    let sig_bytes = hex::decode(&root.signature_hex).map_err(|e| format!("sig hex: {e}"))?;
    let root_bytes = hex::decode(&root.root_hex).map_err(|e| format!("root hex: {e}"))?;
    if root_bytes.len() != 32 {
        return Err("root length != 32".to_owned());
    }
    let mut msg = Vec::with_capacity(ROOT_SIGNING_NAMESPACE.len() + 8 + 32);
    msg.extend_from_slice(ROOT_SIGNING_NAMESPACE);
    msg.extend_from_slice(&root.leaf_count.to_be_bytes());
    msg.extend_from_slice(&root_bytes);
    Ok(polyc_crypto::verify(&pk_bytes, &msg, &sig_bytes))
}

#[cfg(test)]
mod tests {
    #![allow(clippy::pedantic, clippy::nursery, missing_docs)]
    use super::*;

    fn signer() -> ApprovalSigner {
        ApprovalSigner::from_seed(42)
    }

    #[test]
    fn leaf_digest_is_deterministic() {
        assert_eq!(leaf_digest(0, "k", b"v"), leaf_digest(0, "k", b"v"));
    }

    #[test]
    fn leaf_digest_distinguishes_position() {
        assert_ne!(leaf_digest(0, "k", b"v"), leaf_digest(1, "k", b"v"));
    }

    #[test]
    fn leaf_digest_distinguishes_kind() {
        assert_ne!(leaf_digest(0, "k1", b"v"), leaf_digest(0, "k2", b"v"));
    }

    #[test]
    fn leaf_digest_resists_concat_collision() {
        // ("ab", "c") and ("a", "bc") would collide under naive concat —
        // length prefixing prevents that.
        assert_ne!(leaf_digest(0, "ab", b"c"), leaf_digest(0, "a", b"bc"));
    }

    #[test]
    fn appending_assigns_monotonic_positions() {
        let log = VerifiableLog::new();
        assert_eq!(log.append("k", b"v0").unwrap(), 0);
        assert_eq!(log.append("k", b"v1").unwrap(), 1);
        assert_eq!(log.append("k", b"v2").unwrap(), 2);
        assert_eq!(log.leaf_count().unwrap(), 3);
    }

    #[test]
    fn round_trip_single_event() {
        let log = VerifiableLog::new();
        let _pos = log.append("user_msg", b"hello").unwrap();
        let proof = log.inclusion_proof(0).unwrap();
        let signed = log.sign_root(&signer()).unwrap();
        assert!(verify(&signed, &proof, "user_msg", b"hello").unwrap());
    }

    #[test]
    fn round_trip_many_events() {
        let log = VerifiableLog::new();
        let events: Vec<(String, Vec<u8>)> = (0..32)
            .map(|i| (format!("k{i}"), format!("payload-{i}").into_bytes()))
            .collect();
        for (k, v) in &events {
            log.append(k, v).unwrap();
        }
        let signed = log.sign_root(&signer()).unwrap();
        for (i, (k, v)) in events.iter().enumerate() {
            let proof = log.inclusion_proof(i as u64).unwrap();
            assert!(
                verify(&signed, &proof, k, v).unwrap(),
                "event {i} ({k}) should verify"
            );
        }
    }

    #[test]
    fn tampered_payload_does_not_verify() {
        let log = VerifiableLog::new();
        log.append("k", b"original").unwrap();
        let proof = log.inclusion_proof(0).unwrap();
        let signed = log.sign_root(&signer()).unwrap();
        assert!(!verify(&signed, &proof, "k", b"tampered").unwrap());
    }

    #[test]
    fn tampered_kind_does_not_verify() {
        let log = VerifiableLog::new();
        log.append("k1", b"v").unwrap();
        let proof = log.inclusion_proof(0).unwrap();
        let signed = log.sign_root(&signer()).unwrap();
        assert!(!verify(&signed, &proof, "k2", b"v").unwrap());
    }

    #[test]
    fn proof_for_out_of_range_position_errors() {
        let log = VerifiableLog::new();
        log.append("k", b"v").unwrap();
        let err = log.inclusion_proof(1).unwrap_err();
        match err {
            MmrError::UnknownPosition { position, size } => {
                assert_eq!(position, 1);
                assert_eq!(size, 1);
            }
            other => panic!("unexpected error: {other:?}"),
        }
    }

    #[test]
    fn signed_root_signature_verifies_under_correct_pk() {
        let s = signer();
        let log = VerifiableLog::new();
        log.append("k", b"v").unwrap();
        let signed = log.sign_root(&s).unwrap();
        let pk_hex = hex::encode(s.public_key_bytes());
        assert!(verify_root_signature(&signed, &pk_hex).unwrap());
    }

    #[test]
    fn signed_root_signature_rejects_wrong_pk() {
        let log = VerifiableLog::new();
        log.append("k", b"v").unwrap();
        let signed = log.sign_root(&signer()).unwrap();
        let other = ApprovalSigner::from_seed(999);
        let wrong_pk = hex::encode(other.public_key_bytes());
        assert!(!verify_root_signature(&signed, &wrong_pk).unwrap());
    }

    #[test]
    fn verify_consults_inactive_peaks_field() {
        // Regression guard: `verify()` used to hardcode `inactive_peaks =
        // 0`, so any proof claiming a non-zero pruning depth would still
        // verify as if it were unpruned. Confirm the field is now wired
        // through: take a known-good proof, mutate `inactive_peaks` to a
        // non-zero value, and assert verification fails.
        let log = VerifiableLog::new();
        log.append("user_msg", b"hello").unwrap();
        let proof = log.inclusion_proof(0).unwrap();
        let signed = log.sign_root(&signer()).unwrap();
        // Sanity: original proof verifies.
        assert!(verify(&signed, &proof, "user_msg", b"hello").unwrap());
        // Mutated proof claims pruning that didn't happen → must NOT
        // verify (would have spuriously verified under the old hardcoded
        // path).
        let mut tampered = proof.clone();
        tampered.inactive_peaks = 1;
        assert!(!verify(&signed, &tampered, "user_msg", b"hello").unwrap());
    }
}