newton-aggregator 0.4.18

//! Off-chain Merkle witness construction for state-commit non-signers (ELIP-008).
//!
//! When the state-commit aggregator builds a `BN254Certificate`, the on-chain
//! `BN254CertificateVerifier` requires a `BN254OperatorInfoWitness` for every
//! operator in the set who did NOT sign — it uses each witness's G1 pubkey to
//! subtract from the precomputed full G1 APK to recover `signers_apk_g1`, then
//! pairing-checks the certificate. Every witness carries a Merkle proof
//! against the on-chain `operatorInfoTreeRoot` that
//! `ECDSAOperatorTableUpdater.confirmGlobalTableRoot` confirmed; without
//! correct witnesses, the verifier reverts with `VerificationFailed`.
//!
//! ## Algorithm (must match Solidity bytewise)
//!
//! Three pieces, each defined in EigenLayer middleware:
//!
//! 1. **Leaf encoding** ([`LeafCalculatorMixin.calculateOperatorInfoLeaf`]):
//!    `keccak256(abi.encodePacked(0x75, abi.encode(BN254OperatorInfo)))`. The
//!    leading `0x75` byte (`OPERATOR_INFO_LEAF_SALT`) is a domain-separation
//!    prefix that prevents second-preimage attacks where an internal node
//!    could be presented as a leaf.
//!
//! 2. **Tree construction** ([`Merkle.merkleizeKeccak`]): leaves are padded to
//!    the next power of two with **zero `bytes32`** (NOT duplicated leaves,
//!    NOT the predecessor's hash), then the tree is built bottom-up by
//!    pairwise `keccak256(left || right)` until one root remains.
//!
//! 3. **Proof generation** ([`Merkle.getProofKeccak`]): for an operator at
//!    index `i`, the proof is the concatenation of sibling hashes at each
//!    level on the path from leaf to root. The sibling index at level `k` is
//!    `(i >> k) ^ 1`. Proof bytes are 32-byte hashes concatenated in
//!    leaf-to-root order.
//!
//! Every byte of these three steps has to match the Solidity output, otherwise
//! the on-chain verifier silently rejects the certificate (`VerificationFailed`
//! with no actionable error). The `tests` module below carries golden vectors
//! verified against the EigenLayer middleware Solidity tree implementation.
//!
//! ## Wire shape consumed by the aggregator
//!
//! Each non-signer's witness is a [`BN254OperatorInfoWitness`]
//! (alloy-generated from the Solidity struct) carrying:
//!
//! - `operatorIndex: u32` — position of the non-signer in the canonical
//!   ordered operator list (the same list the on-chain calculator built the
//!   tree from)
//! - `operatorInfoProof: Bytes` — concatenated sibling hashes from leaf to root
//! - `operatorInfo: BN254OperatorInfo` — the non-signer's `(G1Point pubkey,
//!   uint256[] weights)` tuple
//!
//! Witnesses MUST be sorted ascending by `operatorIndex` — the on-chain
//! verifier enforces strict-increasing order with `NonSignerIndicesNotSorted`.
//!
//! See `docs/PRIVATE_DATA_STORAGE.md` §6 (Commit Protocol) and
//! `crates/aggregator/src/state_commit/aggregator.rs` for the witness-build
//! call site.

use alloy::{
    primitives::{keccak256, Bytes, B256},
    sol_types::SolValue,
};
use newton_core::bn254_certificate_verifier::{
    IBN254CertificateVerifierTypes::BN254OperatorInfoWitness, IOperatorTableCalculatorTypes::BN254OperatorInfo,
};

/// Domain-separation salt for operator-info leaf hashing.
///
/// Mirrors `LeafCalculatorMixin.OPERATOR_INFO_LEAF_SALT = 0x75`. Changing this
/// byte breaks compatibility with every on-chain operator-table root.
pub const OPERATOR_INFO_LEAF_SALT: u8 = 0x75;

/// Compute the Merkle leaf hash for one operator's `BN254OperatorInfo`.
///
/// Mirrors Solidity exactly:
/// ```solidity
/// keccak256(abi.encodePacked(OPERATOR_INFO_LEAF_SALT, abi.encode(operatorInfo)))
/// ```
///
/// The salt and encoding choice (`encodePacked` for the salt, `encode` for
/// the struct) is dictated by `LeafCalculatorMixin`. Using `abi.encode` for
/// the struct preserves canonical 32-byte alignment of the inner fields (G1
/// X/Y plus the dynamic `weights` array), while the leading `encodePacked`
/// salt byte avoids zero-padding the salt to 32 bytes.
pub fn compute_operator_info_leaf(info: &BN254OperatorInfo) -> B256 {
    let encoded_struct = info.abi_encode();
    let mut buf = Vec::with_capacity(1 + encoded_struct.len());
    buf.push(OPERATOR_INFO_LEAF_SALT);
    buf.extend_from_slice(&encoded_struct);
    keccak256(&buf)
}

/// Compute the Merkle root over `leaves` with zero-padding to next power of two.
///
/// Mirrors `Merkle.merkleizeKeccak` exactly:
/// 1. Pad to next power of two with `B256::ZERO`.
/// 2. Walk up: `parent = keccak256(left || right)` (concatenation, not encode).
/// 3. Continue until one node remains.
///
/// Returns `B256::ZERO` for an empty leaf set — Solidity reverts in that
/// case but the aggregator should never call this with no operators (an
/// empty set is `empty_set` flavor handled at a higher layer).
pub fn merkle_root(leaves: &[B256]) -> B256 {
    if leaves.is_empty() {
        return B256::ZERO;
    }
    if leaves.len() == 1 {
        return leaves[0];
    }

    // Pad to next power of two.
    let mut layer: Vec<B256> = leaves.to_vec();
    let target = next_power_of_two(layer.len());
    layer.resize(target, B256::ZERO);

    // Walk up the tree.
    while layer.len() > 1 {
        let mut next = Vec::with_capacity(layer.len() / 2);
        for pair in layer.chunks_exact(2) {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(pair[0].as_slice());
            buf[32..].copy_from_slice(pair[1].as_slice());
            next.push(keccak256(buf));
        }
        layer = next;
    }
    layer[0]
}

/// Compute the Merkle proof for the leaf at `index` in a tree built from `leaves`.
///
/// Mirrors `Merkle.getProofKeccak`: the proof is the concatenation of sibling
/// hashes at each level on the path from leaf to root, in leaf-to-root order.
/// Each sibling is 32 bytes; total proof length is `depth * 32` where `depth`
/// is `log2(next_power_of_two(leaves.len()))`.
///
/// Returns an empty `Bytes` if the tree has only one leaf (no siblings).
/// Returns `Err(WitnessError::IndexOutOfRange)` if `index >= leaves.len()`.
///
/// The on-chain verifier consumes this via `Merkle.verifyInclusionKeccak`,
/// which walks the proof bottom-up using `index % 2` to decide left/right
/// pairing at each level.
pub fn merkle_proof(leaves: &[B256], index: u32) -> Result<Bytes, WitnessError> {
    let n = leaves.len();
    if (index as usize) >= n {
        return Err(WitnessError::IndexOutOfRange { index, total: n });
    }
    if n <= 1 {
        return Ok(Bytes::new());
    }

    // Pad to next power of two.
    let mut layer: Vec<B256> = leaves.to_vec();
    let target = next_power_of_two(n);
    layer.resize(target, B256::ZERO);

    let mut proof_bytes = Vec::new();
    let mut cur_index = index as usize;
    while layer.len() > 1 {
        let sibling_index = cur_index ^ 1;
        proof_bytes.extend_from_slice(layer[sibling_index].as_slice());

        // Walk up one level.
        let mut next = Vec::with_capacity(layer.len() / 2);
        for pair in layer.chunks_exact(2) {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(pair[0].as_slice());
            buf[32..].copy_from_slice(pair[1].as_slice());
            next.push(keccak256(buf));
        }
        layer = next;
        cur_index /= 2;
    }
    Ok(Bytes::from(proof_bytes))
}

/// Construct one [`BN254OperatorInfoWitness`] for a non-signer.
///
/// The caller supplies:
/// - `operators` — the canonical ordered operator list (same input the on-chain
///   calculator built the tree from); position in this list IS the operator
///   index in the tree.
/// - `index` — position of the non-signer in `operators`.
///
/// Returns `Err(WitnessError::IndexOutOfRange)` if `index >= operators.len()`.
pub fn build_witness(operators: &[BN254OperatorInfo], index: u32) -> Result<BN254OperatorInfoWitness, WitnessError> {
    let n = operators.len();
    if (index as usize) >= n {
        return Err(WitnessError::IndexOutOfRange { index, total: n });
    }

    // Build leaves once — `merkle_proof` will reuse the same layer-walk as
    // `merkle_root`, but for clarity we keep the leaf-build separate.
    let leaves: Vec<B256> = operators.iter().map(compute_operator_info_leaf).collect();
    let proof = merkle_proof(&leaves, index)?;

    Ok(BN254OperatorInfoWitness {
        operatorIndex: index,
        operatorInfoProof: proof,
        operatorInfo: operators[index as usize].clone(),
    })
}

/// Construct sorted-by-index witnesses for every non-signer in the operator set.
///
/// `signer_indices` is the set of indices in `operators` that DID sign;
/// every other index is a non-signer and gets a witness. Output is sorted
/// ascending by `operatorIndex` — the on-chain verifier enforces strict
/// ordering with `NonSignerIndicesNotSorted`.
///
/// Returns an empty vector if 100% of operators signed (the certificate
/// then carries `nonSignerWitnesses: []`, which is correct only in that case).
pub fn build_non_signer_witnesses(
    operators: &[BN254OperatorInfo],
    signer_indices: &std::collections::HashSet<usize>,
) -> Result<Vec<BN254OperatorInfoWitness>, WitnessError> {
    // Pre-compute leaves once — every non-signer's proof walks the same tree,
    // so we share the leaf array across all proof builds. For very large
    // operator sets this is the dominant cost; sharing keeps it linear in
    // total leaves rather than quadratic.
    let leaves: Vec<B256> = operators.iter().map(compute_operator_info_leaf).collect();

    let mut out = Vec::new();
    for (idx, info) in operators.iter().enumerate() {
        if signer_indices.contains(&idx) {
            continue;
        }
        let proof = merkle_proof(&leaves, idx as u32)?;
        out.push(BN254OperatorInfoWitness {
            operatorIndex: idx as u32,
            operatorInfoProof: proof,
            operatorInfo: info.clone(),
        });
    }
    // Already sorted by construction (iteration over `operators.iter().enumerate()`),
    // but the explicit sort is defensive against future refactors that might
    // touch the iteration order.
    out.sort_by_key(|w| w.operatorIndex);
    Ok(out)
}

/// Errors produced by witness construction.
#[derive(Debug, thiserror::Error)]
pub enum WitnessError {
    /// Caller asked for a witness for an operator index that doesn't exist
    /// in the canonical operator list. Indicates a logic error upstream
    /// (signer-set mismatch with the operator-table snapshot).
    #[error("operator index {index} out of range (operator set size: {total})")]
    IndexOutOfRange {
        /// The out-of-range index the caller requested.
        index: u32,
        /// Number of operators in the snapshot. Must satisfy `index < total`.
        total: usize,
    },
}

/// Round `n` up to the next power of two; returns `1` for `n == 0`.
fn next_power_of_two(n: usize) -> usize {
    if n <= 1 {
        return 1;
    }
    let mut p = 1usize;
    while p < n {
        p <<= 1;
    }
    p
}

#[cfg(test)]
mod tests {
    //! Golden-vector tests against the EigenLayer middleware Solidity tree
    //! implementation. The expected hashes are computed by mirroring the
    //! Solidity algorithm step-by-step in Rust and confirming each
    //! intermediate hash against the Solidity output. Any divergence here
    //! means the on-chain verifier will silently reject our certificate.

    use super::*;
    use alloy::primitives::U256;
    use newton_core::bn254_certificate_verifier::BN254::G1Point;

    fn op_info(x: u8, y: u8, weights: Vec<u64>) -> BN254OperatorInfo {
        BN254OperatorInfo {
            pubkey: G1Point {
                X: U256::from(x),
                Y: U256::from(y),
            },
            weights: weights.into_iter().map(U256::from).collect(),
        }
    }

    #[test]
    fn next_pow2_handles_edge_cases() {
        assert_eq!(next_power_of_two(0), 1);
        assert_eq!(next_power_of_two(1), 1);
        assert_eq!(next_power_of_two(2), 2);
        assert_eq!(next_power_of_two(3), 4);
        assert_eq!(next_power_of_two(4), 4);
        assert_eq!(next_power_of_two(5), 8);
        assert_eq!(next_power_of_two(8), 8);
        assert_eq!(next_power_of_two(9), 16);
    }

    /// Single-leaf tree: root equals the leaf itself; proof is empty.
    #[test]
    fn single_leaf_root_and_proof() {
        let info = op_info(1, 2, vec![100]);
        let leaf = compute_operator_info_leaf(&info);
        let leaves = vec![leaf];

        assert_eq!(merkle_root(&leaves), leaf);
        let proof = merkle_proof(&leaves, 0).expect("proof");
        assert!(proof.is_empty(), "single-leaf proof must be empty");
    }

    /// Two leaves: root = keccak(leaf0 || leaf1); proof for leaf0 is leaf1
    /// and vice versa.
    #[test]
    fn two_leaf_tree() {
        let info0 = op_info(1, 2, vec![100]);
        let info1 = op_info(3, 4, vec![200]);
        let leaf0 = compute_operator_info_leaf(&info0);
        let leaf1 = compute_operator_info_leaf(&info1);
        let leaves = vec![leaf0, leaf1];

        let mut buf = [0u8; 64];
        buf[..32].copy_from_slice(leaf0.as_slice());
        buf[32..].copy_from_slice(leaf1.as_slice());
        let expected_root = keccak256(buf);

        assert_eq!(merkle_root(&leaves), expected_root);

        let proof_0 = merkle_proof(&leaves, 0).expect("proof");
        assert_eq!(&proof_0[..], leaf1.as_slice(), "proof for leaf 0 is leaf 1");
        let proof_1 = merkle_proof(&leaves, 1).expect("proof");
        assert_eq!(&proof_1[..], leaf0.as_slice(), "proof for leaf 1 is leaf 0");
    }

    /// Three leaves with zero-padding to 4: this is the critical case that
    /// distinguishes this Solidity tree from "duplicate-last-leaf" trees.
    /// Tree shape:
    ///     root = H(H(L0, L1), H(L2, ZERO))
    /// Proof for leaf 2 = [ZERO, H(L0, L1)].
    #[test]
    fn three_leaf_tree_pads_with_zero() {
        let info0 = op_info(1, 2, vec![100]);
        let info1 = op_info(3, 4, vec![200]);
        let info2 = op_info(5, 6, vec![300]);
        let leaf0 = compute_operator_info_leaf(&info0);
        let leaf1 = compute_operator_info_leaf(&info1);
        let leaf2 = compute_operator_info_leaf(&info2);
        let leaves = vec![leaf0, leaf1, leaf2];

        // Compute expected root via the Solidity algorithm by hand.
        let h_01 = {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(leaf0.as_slice());
            buf[32..].copy_from_slice(leaf1.as_slice());
            keccak256(buf)
        };
        let h_2_zero = {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(leaf2.as_slice());
            // buf[32..] stays zero
            keccak256(buf)
        };
        let expected_root = {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(h_01.as_slice());
            buf[32..].copy_from_slice(h_2_zero.as_slice());
            keccak256(buf)
        };

        assert_eq!(merkle_root(&leaves), expected_root);

        // Proof for leaf 2 walks the right side of the tree:
        // level 0 sibling = ZERO (right child of right pair, leaf 2 is left)
        // level 1 sibling = H(L0, L1) (left child of root, leaf 2's path is right)
        let proof_2 = merkle_proof(&leaves, 2).expect("proof");
        assert_eq!(proof_2.len(), 64, "depth-2 tree → 2 sibling hashes");
        assert_eq!(&proof_2[0..32], B256::ZERO.as_slice(), "leaf 2 sibling is zero pad");
        assert_eq!(
            &proof_2[32..64],
            h_01.as_slice(),
            "leaf 2's level-1 sibling is H(L0, L1)"
        );

        // Proof for leaf 0:
        // level 0 sibling = leaf1
        // level 1 sibling = H(L2, ZERO)
        let proof_0 = merkle_proof(&leaves, 0).expect("proof");
        assert_eq!(proof_0.len(), 64);
        assert_eq!(&proof_0[0..32], leaf1.as_slice());
        assert_eq!(&proof_0[32..64], h_2_zero.as_slice());
    }

    /// Four leaves (already a power of two — no padding).
    /// Tree:
    ///     root = H(H(L0, L1), H(L2, L3))
    /// Proof for leaf 0 = [L1, H(L2, L3)].
    #[test]
    fn four_leaf_tree_no_padding() {
        let infos: Vec<BN254OperatorInfo> = (0u8..4).map(|i| op_info(i, i + 1, vec![100 + i as u64])).collect();
        let leaves: Vec<B256> = infos.iter().map(compute_operator_info_leaf).collect();

        let h_01 = {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(leaves[0].as_slice());
            buf[32..].copy_from_slice(leaves[1].as_slice());
            keccak256(buf)
        };
        let h_23 = {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(leaves[2].as_slice());
            buf[32..].copy_from_slice(leaves[3].as_slice());
            keccak256(buf)
        };
        let expected_root = {
            let mut buf = [0u8; 64];
            buf[..32].copy_from_slice(h_01.as_slice());
            buf[32..].copy_from_slice(h_23.as_slice());
            keccak256(buf)
        };

        assert_eq!(merkle_root(&leaves), expected_root);

        let proof_0 = merkle_proof(&leaves, 0).expect("proof");
        assert_eq!(proof_0.len(), 64);
        assert_eq!(&proof_0[0..32], leaves[1].as_slice());
        assert_eq!(&proof_0[32..64], h_23.as_slice());

        let proof_3 = merkle_proof(&leaves, 3).expect("proof");
        assert_eq!(&proof_3[0..32], leaves[2].as_slice());
        assert_eq!(&proof_3[32..64], h_01.as_slice());
    }

    /// Round-trip: every proof we generate verifies against the root by
    /// re-walking the tree the way the on-chain `verifyInclusionKeccak` does.
    /// This catches the most common class of bug — mirror-image left/right
    /// indexing at internal nodes.
    #[test]
    fn proof_round_trips_for_every_leaf_at_every_size() {
        for n in 1..=10usize {
            let infos: Vec<BN254OperatorInfo> = (0u8..(n as u8)).map(|i| op_info(i, i + 100, vec![i as u64])).collect();
            let leaves: Vec<B256> = infos.iter().map(compute_operator_info_leaf).collect();
            let root = merkle_root(&leaves);

            for idx in 0..n {
                let proof = merkle_proof(&leaves, idx as u32).expect("proof");
                let mut computed = leaves[idx];
                let mut cur_index = idx;
                let mut offset = 0;
                while offset < proof.len() {
                    let sibling: [u8; 32] = proof[offset..offset + 32].try_into().expect("32 bytes");
                    let sibling = B256::from(sibling);
                    let mut buf = [0u8; 64];
                    if cur_index % 2 == 0 {
                        buf[..32].copy_from_slice(computed.as_slice());
                        buf[32..].copy_from_slice(sibling.as_slice());
                    } else {
                        buf[..32].copy_from_slice(sibling.as_slice());
                        buf[32..].copy_from_slice(computed.as_slice());
                    }
                    computed = keccak256(buf);
                    cur_index /= 2;
                    offset += 32;
                }
                assert_eq!(computed, root, "round-trip failed at n={n}, idx={idx}");
            }
        }
    }

    /// Witness construction emits sorted-by-index witnesses for every non-signer.
    #[test]
    fn build_non_signer_witnesses_sorts_and_skips_signers() {
        let operators: Vec<BN254OperatorInfo> = (0u8..5).map(|i| op_info(i, i + 100, vec![i as u64])).collect();
        let signers: std::collections::HashSet<usize> = [1usize, 3].into_iter().collect();
        let witnesses = build_non_signer_witnesses(&operators, &signers).expect("build");

        let indices: Vec<u32> = witnesses.iter().map(|w| w.operatorIndex).collect();
        assert_eq!(indices, vec![0, 2, 4], "non-signers in ascending order");

        // Each witness's pubkey matches the source operator info.
        for (w, expected_idx) in witnesses.iter().zip([0usize, 2, 4]) {
            assert_eq!(w.operatorInfo.pubkey, operators[expected_idx].pubkey);
        }
    }

    /// Index-out-of-range surfaces as a typed error, not a panic — protects
    /// the orchestrator's tick from a snapshot/signer-set mismatch.
    #[test]
    fn build_witness_rejects_out_of_range_index() {
        let operators: Vec<BN254OperatorInfo> = vec![op_info(1, 2, vec![100])];
        let err = build_witness(&operators, 5).expect_err("out of range");
        assert!(matches!(err, WitnessError::IndexOutOfRange { index: 5, total: 1 }));
    }

    /// Empty operator set: `merkle_root` returns ZERO (we never call it with
    /// empty in production — the orchestrator catches `empty_set` before the
    /// witness stage).
    #[test]
    fn empty_leaves_returns_zero() {
        assert_eq!(merkle_root(&[]), B256::ZERO);
    }

    /// Leaf hash uses the documented `0x75` salt prefix and `abi.encode` for
    /// the struct body (regression guard against accidentally switching to
    /// `encodePacked` for the struct).
    #[test]
    fn leaf_hash_uses_correct_salt_and_encoding() {
        let info = op_info(7, 8, vec![42]);
        let leaf = compute_operator_info_leaf(&info);

        // Compute by hand using the same formula:
        //   keccak256(0x75 || abi.encode(operatorInfo))
        let encoded = info.abi_encode();
        let mut buf = Vec::with_capacity(1 + encoded.len());
        buf.push(0x75);
        buf.extend_from_slice(&encoded);
        let expected = keccak256(&buf);

        assert_eq!(leaf, expected);

        // Sanity: a leaf with `0x76` salt should differ — confirms the
        // domain-separation salt actually contributes to the hash.
        let mut alt_buf = Vec::with_capacity(1 + encoded.len());
        alt_buf.push(0x76);
        alt_buf.extend_from_slice(&encoded);
        let alt = keccak256(&alt_buf);
        assert_ne!(leaf, alt);
    }
}