samaharam 0.2.0

//! Accumulator for collecting pairing elements.
//!
//! The accumulator collects G1 and G2 elements that will be
//! batched into a single pairing check for efficient verification.

use std::marker::PhantomData;

use crate::traits::PairingEngine;

/// Accumulator for batch pairing verification.
///
/// Instead of verifying each proof with a separate pairing,
/// we accumulate the elements and verify with a single multi-pairing.
///
/// # Example
///
/// ```rust,ignore
/// let mut acc = Accumulator::<Bn254>::new();
/// acc.add_pairing_check(g1, g2);
/// acc.add_pairing_check(g1_2, g2_2);
/// assert!(acc.verify()); // Single batched check
/// ```
#[derive(Debug, Clone)]
pub struct Accumulator<E: PairingEngine> {
    /// Accumulated G1 elements
    g1_elements: Vec<E::G1Affine>,

    /// Accumulated G2 elements
    g2_elements: Vec<E::G2Affine>,

    /// Random challenges for combining pairings
    challenges: Vec<E::Fr>,

    _engine: PhantomData<E>,
}

impl<E: PairingEngine> Default for Accumulator<E> {
    fn default() -> Self {
        Self::new()
    }
}

impl<E: PairingEngine> Accumulator<E> {
    /// Create a new empty accumulator.
    pub fn new() -> Self {
        Self {
            g1_elements: Vec::new(),
            g2_elements: Vec::new(),
            challenges: Vec::new(),
            _engine: PhantomData,
        }
    }

    /// Create an accumulator with specified capacity.
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            g1_elements: Vec::with_capacity(capacity),
            g2_elements: Vec::with_capacity(capacity),
            challenges: Vec::with_capacity(capacity),
            _engine: PhantomData,
        }
    }

    /// Add a pairing element pair to the accumulator.
    pub fn add(&mut self, g1: E::G1Affine, g2: E::G2Affine, challenge: E::Fr) {
        self.g1_elements.push(g1);
        self.g2_elements.push(g2);
        self.challenges.push(challenge);
    }

    /// Get the number of accumulated pairing elements.
    pub fn len(&self) -> usize {
        self.g1_elements.len()
    }

    /// Check if the accumulator is empty.
    pub fn is_empty(&self) -> bool {
        self.g1_elements.is_empty()
    }

    /// Merge another accumulator into this one.
    pub fn merge(&mut self, other: Self) {
        self.g1_elements.extend(other.g1_elements);
        self.g2_elements.extend(other.g2_elements);
        self.challenges.extend(other.challenges);
    }

    /// Verify all accumulated pairings.
    ///
    /// Returns true if the batched pairing check passes.
    pub fn verify(&self) -> bool {
        use group::Group; // Used for Gt::identity() check
        if self.is_empty() {
            return true;
        }

        // Compute random linear combination of pairings
        // ∏ e(challenge_i * G1_i, G2_i) == 1 in Gt
        let pairs: Vec<_> = self
            .g1_elements
            .iter()
            .zip(self.g2_elements.iter())
            .zip(self.challenges.iter())
            .map(|((g1, g2), challenge)| {
                // Scale G1 by challenge
                let scaled_g1 = scale_g1::<E>(g1, challenge);
                (scaled_g1, *g2)
            })
            .collect();

        // Build references for multi_pairing
        let refs: Vec<_> = pairs.iter().map(|(g1, g2)| (g1, g2)).collect();

        // Check if product of pairings is identity
        let result = E::multi_pairing(refs);
        result == E::Gt::identity()
    }
}

/// Scale a G1 element by a scalar.
fn scale_g1<E: PairingEngine>(g1: &E::G1Affine, scalar: &E::Fr) -> E::G1Affine {
    use group::Curve;

    // Convert affine to projective, scale, convert back
    let projective: E::G1 = (*g1).into();
    let scaled = projective * *scalar;
    scaled.to_affine()
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::backend::bn254::Bn254;
    use ff::Field;
    use group::{Curve, Group};
    use halo2curves::bn256::{Fr, G1};
    use rand::rngs::OsRng;

    #[test]
    fn accumulator_starts_empty() {
        let acc = Accumulator::<Bn254>::new();
        assert!(acc.is_empty());
        assert_eq!(acc.len(), 0);
    }

    #[test]
    fn accumulator_empty_verifies() {
        let acc = Accumulator::<Bn254>::new();
        assert!(acc.verify());
    }

    #[test]
    fn accumulator_adds_elements() {
        let mut acc = Accumulator::<Bn254>::new();

        let g1 = G1::random(OsRng).to_affine();
        let g2 = halo2curves::bn256::G2::random(OsRng).to_affine();
        let challenge = Fr::random(OsRng);

        acc.add(g1, g2, challenge);

        assert_eq!(acc.len(), 1);
        assert!(!acc.is_empty());
    }

    #[test]
    fn accumulator_merges() {
        let mut acc1 = Accumulator::<Bn254>::new();
        let mut acc2 = Accumulator::<Bn254>::new();

        let g1 = G1::random(OsRng).to_affine();
        let g2 = halo2curves::bn256::G2::random(OsRng).to_affine();
        let challenge = Fr::random(OsRng);

        acc1.add(g1.clone(), g2.clone(), challenge);
        acc2.add(g1, g2, challenge);

        acc1.merge(acc2);

        assert_eq!(acc1.len(), 2);
    }
}