hop_mix/

lib.rs

#![forbid(unsafe_code)]
#![deny(missing_docs)]
//! Deterministic, transcript-bound aggregation of HOP actions.

use core::fmt;

use hop_actions::{Action, ActionError};
use sha2::{Digest, Sha256};

const MIX_DOMAIN: &[u8] = b"HOP-MIX\0\x02";
const FIELD_MODULUS: u64 = 65_537;

/// Inputs and optional contributor ordering for an aggregate action.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct MixBatch {
    /// Actions to aggregate by field addition of their polynomials and masks.
    pub contributors: Vec<Action>,
    /// Optional permutation of contributor indexes used by the transcript hash.
    pub permutation_hint: Option<Vec<u32>>,
}

/// Errors returned when a mix cannot be represented canonically.
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum MixError {
    /// At least one contributor is required.
    EmptyBatch,
    /// A permutation was not an exact permutation of all contributor indexes.
    InvalidPermutation,
    /// Contributor masks had incompatible dimensions.
    MaskDimensionMismatch,
    /// A contributor was not a canonical action.
    InvalidAction(ActionError),
}

impl fmt::Display for MixError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::EmptyBatch => f.write_str("a mix requires at least one contributor"),
            Self::InvalidPermutation => {
                f.write_str("mix permutation must contain every contributor index exactly once")
            }
            Self::MaskDimensionMismatch => {
                f.write_str("mix contributor masks have incompatible dimensions")
            }
            Self::InvalidAction(error) => write!(f, "invalid mix contributor: {error}"),
        }
    }
}

impl std::error::Error for MixError {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        match self {
            Self::InvalidAction(error) => Some(error),
            _ => None,
        }
    }
}

/// Aggregates a batch using field addition and a transcript-derived nonce.
///
/// This operation is an additive aggregate, not sequential action composition.
/// The output nonce commits to every full action hash and the selected order.
pub fn build_mix(batch: MixBatch) -> Result<Action, MixError> {
    if batch.contributors.is_empty() {
        return Err(MixError::EmptyBatch);
    }

    let dimension = batch
        .contributors
        .iter()
        .find_map(|action| action.mask_row0.as_ref().map(Vec::len))
        .unwrap_or(0);
    for action in &batch.contributors {
        action.validate().map_err(MixError::InvalidAction)?;
        if action
            .mask_row0
            .as_ref()
            .is_some_and(|mask| mask.len() != dimension)
        {
            return Err(MixError::MaskDimensionMismatch);
        }
    }

    let order = contributor_order(batch.contributors.len(), batch.permutation_hint)?;
    let coefficient_count = batch
        .contributors
        .iter()
        .map(|action| action.g_coeffs.len())
        .max()
        .ok_or(MixError::EmptyBatch)?;
    let mut coefficients = vec![0; coefficient_count];
    let mut mask = (dimension != 0).then(|| vec![0; dimension]);
    let mut transcript = Sha256::new();
    transcript.update(MIX_DOMAIN);
    transcript.update((order.len() as u128).to_le_bytes());

    for index in order {
        let action = &batch.contributors[index];
        transcript.update((index as u128).to_le_bytes());
        transcript.update(action.hash());
        for (sum, coefficient) in coefficients.iter_mut().zip(&action.g_coeffs) {
            *sum = add_field(*sum, *coefficient);
        }
        if let (Some(sum), Some(contribution)) = (&mut mask, &action.mask_row0) {
            for (value, addend) in sum.iter_mut().zip(contribution) {
                *value = add_field(*value, *addend);
            }
        }
    }

    while coefficients.len() > 1 && coefficients.last() == Some(&0) {
        coefficients.pop();
    }
    let digest = transcript.finalize();
    let mut nonce_bytes = [0_u8; 8];
    nonce_bytes.copy_from_slice(&digest[..8]);
    let nonce = u64::from_le_bytes(nonce_bytes);
    Ok(Action {
        g_coeffs: coefficients,
        nonce,
        mask_row0: mask,
    })
}

fn contributor_order(count: usize, permutation: Option<Vec<u32>>) -> Result<Vec<usize>, MixError> {
    let Some(permutation) = permutation else {
        return Ok((0..count).collect());
    };
    if permutation.len() != count {
        return Err(MixError::InvalidPermutation);
    }
    let mut seen = vec![false; count];
    let mut order = Vec::with_capacity(count);
    for encoded in permutation {
        let index = encoded as usize;
        if index >= count || seen[index] {
            return Err(MixError::InvalidPermutation);
        }
        seen[index] = true;
        order.push(index);
    }
    Ok(order)
}

fn add_field(left: u64, right: u64) -> u64 {
    ((left as u128 + right as u128) % FIELD_MODULUS as u128) as u64
}

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

    fn action(g_coeffs: Vec<u64>, nonce: u64) -> Action {
        Action {
            g_coeffs,
            nonce,
            mask_row0: None,
        }
    }

    #[test]
    fn addition_is_correct_across_u64_overflow_boundary() {
        let mixed = build_mix(MixBatch {
            contributors: vec![action(vec![65_536], 1), action(vec![2], 2)],
            permutation_hint: None,
        })
        .unwrap();
        assert_eq!(mixed.g_coeffs, vec![1]);
    }

    #[test]
    fn permutation_changes_transcript_nonce_but_not_sum() {
        let contributors = vec![action(vec![1, 2], 1), action(vec![3], 2)];
        let natural = build_mix(MixBatch {
            contributors: contributors.clone(),
            permutation_hint: None,
        })
        .unwrap();
        let reversed = build_mix(MixBatch {
            contributors,
            permutation_hint: Some(vec![1, 0]),
        })
        .unwrap();
        assert_eq!(natural.g_coeffs, reversed.g_coeffs);
        assert_ne!(natural.nonce, reversed.nonce);
    }

    #[test]
    fn rejects_empty_and_malformed_permutations() {
        assert_eq!(
            build_mix(MixBatch {
                contributors: Vec::new(),
                permutation_hint: None,
            }),
            Err(MixError::EmptyBatch)
        );
        assert_eq!(
            build_mix(MixBatch {
                contributors: vec![action(vec![1], 1), action(vec![2], 2)],
                permutation_hint: Some(vec![0, 0]),
            }),
            Err(MixError::InvalidPermutation)
        );
    }
}