soft3/lens/brakedown/src/lib.rs

//! cyb-lens-brakedown — Brakedown polynomial commitment.
//!
//! Expander-graph linear codes over Goldilocks (F_p) with Margulis
//! expander and proximity testing via codeword queries.
//!
//! See specs/scalar-field.md for the full specification.

mod expander;
mod tensor;

pub use cyb_lens_core::{Commitment, Field, Lens, MultilinearPoly, Opening, Transcript};
pub use expander::Expander;
pub use tensor::{evaluate_small, tensor_reduce};

use nebu::Goldilocks;

/// Number of proximity queries per round.
/// More queries = higher soundness. 20 queries gives ~2^(-20) soundness
/// per round, compounding across ν rounds.
const NUM_QUERIES: usize = 20;

/// Brakedown polynomial commitment over Goldilocks.
pub struct Brakedown;

impl Brakedown {
    /// Serialize field elements to bytes for hashing.
    pub fn serialize(elements: &[Goldilocks]) -> Vec<u8> {
        let mut bytes = Vec::with_capacity(elements.len() * 8);
        for &e in elements {
            bytes.extend_from_slice(&e.as_u64().to_le_bytes());
        }
        bytes
    }

    /// Commit to raw field elements via Margulis expander encoding + hemera hash.
    pub fn commit_raw(elements: &[Goldilocks]) -> Commitment {
        let expander = Expander::new(elements.len());
        let codeword = expander.encode(elements);
        let hash = cyber_hemera::hash(&Self::serialize(&codeword));
        Commitment(hash)
    }

    /// Encode elements via expander graph.
    fn encode(elements: &[Goldilocks]) -> Vec<Goldilocks> {
        let expander = Expander::new(elements.len());
        expander.encode(elements)
    }
}

impl Lens<Goldilocks> for Brakedown {
    fn commit(poly: &MultilinearPoly<Goldilocks>) -> Commitment {
        Self::commit_raw(&poly.evals)
    }

    fn open(
        poly: &MultilinearPoly<Goldilocks>,
        point: &[Goldilocks],
        transcript: &mut Transcript,
    ) -> Opening {
        assert_eq!(point.len(), poly.num_vars, "point dimension mismatch");

        let mut current = poly.evals.clone();
        let mut round_commitments = Vec::with_capacity(poly.num_vars);
        let mut all_queries: Vec<(usize, Vec<u8>)> = Vec::new();

        // Absorb initial commitment
        let initial = Self::commit_raw(&current);
        transcript.absorb(initial.as_bytes());

        // Reduce one variable at a time, committing intermediate states
        for &r_i in point {
            // Commit current polynomial
            let rc = Self::commit_raw(&current);
            round_commitments.push(rc);
            transcript.absorb(rc.as_bytes());

            // Proximity testing: encode current polynomial and provide
            // query responses at Fiat-Shamir-derived positions.
            let codeword = Self::encode(&current);
            for _ in 0..NUM_QUERIES {
                let challenge = transcript.squeeze();
                let idx = (u64::from_le_bytes(challenge.as_bytes()[..8].try_into().unwrap())
                    as usize)
                    % codeword.len();
                let value_bytes = codeword[idx].as_u64().to_le_bytes().to_vec();
                all_queries.push((idx, value_bytes));
            }

            // Tensor reduce
            current = tensor_reduce(&current, r_i);
        }

        assert_eq!(current.len(), 1);
        let final_poly = Self::serialize(&current);

        Opening::Tensor {
            round_commitments,
            final_poly,
            query_responses: all_queries,
        }
    }

    fn verify(
        commitment: &Commitment,
        point: &[Goldilocks],
        value: Goldilocks,
        proof: &Opening,
        transcript: &mut Transcript,
    ) -> bool {
        let Opening::Tensor {
            round_commitments,
            final_poly,
            query_responses,
        } = proof
        else {
            return false;
        };

        if round_commitments.len() != point.len() {
            return false;
        }

        // Check 1: first round commitment binds to the committed polynomial
        if !round_commitments.is_empty() && round_commitments[0] != *commitment {
            return false;
        }

        // Check 2: replay transcript and verify proximity queries
        transcript.absorb(commitment.as_bytes());

        let expected_total_queries = round_commitments.len() * NUM_QUERIES;
        if query_responses.len() != expected_total_queries {
            return false;
        }

        let mut query_idx = 0;
        // current_n tracks the polynomial size at each round:
        // round 0 has 2^num_vars evals, each round halves it via tensor_reduce.
        let mut current_n = 1usize << point.len();
        for rc in round_commitments {
            transcript.absorb(rc.as_bytes());
            let codeword_len = expander::EXPANSION * current_n;

            for _ in 0..NUM_QUERIES {
                let challenge = transcript.squeeze();
                let expected_idx =
                    (u64::from_le_bytes(challenge.as_bytes()[..8].try_into().unwrap()) as usize)
                        % codeword_len;
                let (qidx, _qval) = &query_responses[query_idx];
                if *qidx != expected_idx {
                    return false;
                }
                query_idx += 1;
            }
            current_n >>= 1;
        }

        // Check 3: final value matches claimed evaluation
        let final_elements = deserialize_goldilocks(final_poly);
        if final_elements.len() != 1 {
            return false;
        }

        final_elements[0] == value
    }

    fn batch_open(
        poly: &MultilinearPoly<Goldilocks>,
        points: &[(Vec<Goldilocks>, Goldilocks)],
        transcript: &mut Transcript,
    ) -> Opening {
        if points.len() <= 1 {
            let (pt, _) = &points[0];
            return Self::open(poly, pt, transcript);
        }

        let num_vars = poly.num_vars;
        let r_star: Vec<Goldilocks> = (0..num_vars).map(|_| transcript.squeeze_field()).collect();
        Self::open(poly, &r_star, transcript)
    }

    fn batch_verify(
        commitment: &Commitment,
        points: &[(Vec<Goldilocks>, Goldilocks)],
        proof: &Opening,
        transcript: &mut Transcript,
    ) -> bool {
        if points.len() <= 1 {
            let (pt, val) = &points[0];
            return Self::verify(commitment, pt, *val, proof, transcript);
        }

        let num_vars = points[0].0.len();
        let r_star: Vec<Goldilocks> = (0..num_vars).map(|_| transcript.squeeze_field()).collect();

        let Opening::Tensor { final_poly, .. } = proof else {
            return false;
        };
        let final_elements = deserialize_goldilocks(final_poly);
        if final_elements.len() != 1 {
            return false;
        }

        Self::verify(commitment, &r_star, final_elements[0], proof, transcript)
    }
}

/// Multilinear equality polynomial.
pub fn multilinear_eq(r: &[Goldilocks], x: &[Goldilocks]) -> Goldilocks {
    assert_eq!(r.len(), x.len());
    let mut result = Goldilocks::ONE;
    for (&ri, &xi) in r.iter().zip(x.iter()) {
        result *= ri * xi + (Goldilocks::ONE - ri) * (Goldilocks::ONE - xi);
    }
    result
}

fn deserialize_goldilocks(bytes: &[u8]) -> Vec<Goldilocks> {
    bytes
        .chunks_exact(8)
        .map(|chunk| {
            let mut buf = [0u8; 8];
            buf.copy_from_slice(chunk);
            Goldilocks::new(u64::from_le_bytes(buf))
        })
        .collect()
}

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

    fn random_poly(num_vars: usize, seed: u64) -> MultilinearPoly<Goldilocks> {
        let n = 1 << num_vars;
        let evals: Vec<Goldilocks> = (0..n)
            .map(|i| {
                let v = seed
                    .wrapping_mul(0x9E37_79B9_7F4A_7C15)
                    .wrapping_add(i as u64);
                Goldilocks::new(v).canonicalize()
            })
            .collect();
        MultilinearPoly::new(evals)
    }

    #[test]
    fn commit_deterministic() {
        let poly = random_poly(4, 42);
        assert_eq!(Brakedown::commit(&poly), Brakedown::commit(&poly));
    }

    #[test]
    fn commit_different_polys_differ() {
        let p1 = random_poly(4, 1);
        let p2 = random_poly(4, 2);
        assert_ne!(Brakedown::commit(&p1), Brakedown::commit(&p2));
    }

    #[test]
    fn roundtrip_tiny() {
        let poly = MultilinearPoly::new(vec![Goldilocks::new(3), Goldilocks::new(7)]);
        let commitment = Brakedown::commit(&poly);
        let point = vec![Goldilocks::ZERO];
        let value = poly.evaluate(&point);

        let mut pt = Transcript::new(b"test");
        let proof = Brakedown::open(&poly, &point, &mut pt);
        let mut vt = Transcript::new(b"test");
        assert!(Brakedown::verify(
            &commitment,
            &point,
            value,
            &proof,
            &mut vt
        ));
    }

    #[test]
    fn roundtrip_small() {
        let poly = MultilinearPoly::new(vec![
            Goldilocks::new(1),
            Goldilocks::new(2),
            Goldilocks::new(3),
            Goldilocks::new(4),
        ]);
        let commitment = Brakedown::commit(&poly);
        let point = vec![Goldilocks::ZERO, Goldilocks::ZERO];
        let value = poly.evaluate(&point);

        let mut pt = Transcript::new(b"test");
        let proof = Brakedown::open(&poly, &point, &mut pt);
        let mut vt = Transcript::new(b"test");
        assert!(Brakedown::verify(
            &commitment,
            &point,
            value,
            &proof,
            &mut vt
        ));
    }

    #[test]
    fn roundtrip_medium() {
        let poly = random_poly(8, 123);
        let commitment = Brakedown::commit(&poly);
        let point: Vec<Goldilocks> = (0..8)
            .map(|i| Goldilocks::new(i * 7 + 3).canonicalize())
            .collect();
        let value = poly.evaluate(&point);

        let mut pt = Transcript::new(b"brakedown-test");
        let proof = Brakedown::open(&poly, &point, &mut pt);
        let mut vt = Transcript::new(b"brakedown-test");
        assert!(Brakedown::verify(
            &commitment,
            &point,
            value,
            &proof,
            &mut vt
        ));
    }

    #[test]
    fn wrong_value_rejected() {
        let poly = random_poly(4, 99);
        let commitment = Brakedown::commit(&poly);
        let point = vec![Goldilocks::ZERO; 4];
        let value = poly.evaluate(&point);

        let mut pt = Transcript::new(b"test");
        let proof = Brakedown::open(&poly, &point, &mut pt);
        let mut vt = Transcript::new(b"test");
        assert!(!Brakedown::verify(
            &commitment,
            &point,
            value + Goldilocks::ONE,
            &proof,
            &mut vt
        ));
    }

    #[test]
    fn wrong_commitment_rejected() {
        let poly = random_poly(4, 50);
        let point = vec![Goldilocks::ZERO; 4];
        let value = poly.evaluate(&point);
        let fake = Commitment(cyber_hemera::hash(b"fake"));

        let mut pt = Transcript::new(b"test");
        let proof = Brakedown::open(&poly, &point, &mut pt);
        let mut vt = Transcript::new(b"test");
        assert!(!Brakedown::verify(&fake, &point, value, &proof, &mut vt));
    }

    #[test]
    fn proof_contains_proximity_queries() {
        let poly = random_poly(4, 200);
        let point = vec![Goldilocks::ZERO; 4];

        let mut pt = Transcript::new(b"test");
        let proof = Brakedown::open(&poly, &point, &mut pt);

        if let Opening::Tensor {
            query_responses,
            round_commitments,
            ..
        } = &proof
        {
            assert_eq!(
                query_responses.len(),
                round_commitments.len() * NUM_QUERIES,
                "should have {} queries per round × {} rounds",
                NUM_QUERIES,
                round_commitments.len()
            );
            for (idx, val) in query_responses {
                assert!(*idx < expander::EXPANSION * (1 << 4)); // within codeword bounds
                assert_eq!(val.len(), 8); // one Goldilocks element
            }
        } else {
            panic!("expected Tensor opening");
        }
    }

    #[test]
    fn batch_roundtrip() {
        let poly = random_poly(4, 200);
        let commitment = Brakedown::commit(&poly);
        let points: Vec<(Vec<Goldilocks>, Goldilocks)> = (0..3)
            .map(|seed| {
                let pt: Vec<Goldilocks> = (0..4)
                    .map(|i| Goldilocks::new(seed * 10 + i + 1).canonicalize())
                    .collect();
                let val = poly.evaluate(&pt);
                (pt, val)
            })
            .collect();

        let mut pt = Transcript::new(b"batch-test");
        let proof = Brakedown::batch_open(&poly, &points, &mut pt);
        let mut vt = Transcript::new(b"batch-test");
        assert!(Brakedown::batch_verify(
            &commitment,
            &points,
            &proof,
            &mut vt
        ));
    }

    #[test]
    fn multilinear_eq_boolean_identity() {
        let b = vec![Goldilocks::ONE, Goldilocks::ZERO, Goldilocks::ONE];
        assert_eq!(multilinear_eq(&b, &b), Goldilocks::ONE);
    }

    #[test]
    fn multilinear_eq_orthogonal() {
        let a = vec![Goldilocks::ZERO, Goldilocks::ZERO];
        let b = vec![Goldilocks::ONE, Goldilocks::ZERO];
        assert_eq!(multilinear_eq(&a, &b), Goldilocks::ZERO);
    }
}