miden-precompiles-prover 0.33.0

//! EC store tests — the group table + point store pair: bindings, the
//! curve-membership MAC trio (the `UintMul` provide's first consumer),
//! PAI rows, the consecutive-ptr chains, act padding, the vacuous /
//! constrained scalar bound, and the adversarial matrix (off-curve
//! coordinates, PAI forgeries, phantom groups, forged scalar bounds,
//! duplicate ptrs — each rejected by the constraint or the bus that
//! owns it).

use std::collections::HashMap;

use miden_air::lookup::{Challenges, LookupAir, ProverLookupBuilder, build_lookup_fractions};
use miden_core::{
    Felt,
    field::QuadFelt,
    utils::{Matrix, RowMajorMatrix},
};
use miden_lifted_air::LiftedAir;
use miden_precompiles::CurveId;
use rand::{Rng, RngExt, SeedableRng, rngs::StdRng};

use crate::{
    ec::{
        COL_ECPOINT_MULT, COL_GROUP_PTR, COL_IS_PAI, COL_PTR, COL_SBOUND_PTR, COL_X_PTR, COL_Y_PTR,
        EcPointStoreAir, EcRequire, NUM_MAIN_COLS,
        add::trace::EcAddRequires,
        groups::{
            COL_SBOUND_PTR as G_COL_SBOUND_PTR, EcGroupsAir, NUM_MAIN_COLS as G_NUM_MAIN_COLS,
        },
        trace::{EcPointPtr, EcStoreRequires, generate_traces as ec_store_traces},
    },
    math::{U256, from_hex},
    primitives::byte_pair_lut::{BytePairLutAir, BytePairLutRequires, generate_trace as bpl_trace},
    relations::{MAX_MESSAGE_WIDTH, NUM_BUS_IDS},
    uint::{
        UintRequire, UintStoreAir,
        add::trace::UintAddRequires,
        mul::{
            UintMulAir,
            trace::{UintMulRequires, generate_trace as mul_trace},
        },
        trace::{UintPtr, UintStoreRequires, generate_trace as store_trace},
    },
};

fn rand_qf(rng: &mut impl Rng) -> QuadFelt {
    QuadFelt::new([Felt::from(rng.random::<u32>()), Felt::from(rng.random::<u32>())])
}

/// Accumulate one chiplet's net per-denom LogUp multiplicity. Mirrors
/// `tests::uint::fold_balance`.
fn fold_balance<A>(
    air: &A,
    main: &RowMajorMatrix<Felt>,
    challenges: &Challenges<QuadFelt>,
    net: &mut HashMap<QuadFelt, Felt>,
) where
    A: LiftedAir<Felt, QuadFelt> + Sync,
    for<'a> A: LookupAir<ProverLookupBuilder<'a, Felt, QuadFelt>>,
{
    let periodic = air.periodic_columns();
    let combined = crate::tests::combined_lookup_main(air, main);
    let lookup_main = combined.as_ref().unwrap_or(main);
    let fractions = build_lookup_fractions(air, lookup_main, &periodic, challenges);
    for &(multiplicity, denom) in fractions.fractions() {
        *net.entry(denom).or_insert(Felt::ZERO) += multiplicity;
    }
}

/// A curve fixture: the uint store holds the modulus + params +
/// coordinates + membership transients, the mul requires hold the
/// membership trio (provides required), the group table holds the VM-owned
/// fixed curve slots plus this fixture's group, and the point store holds
/// PAI @1 and the point @2.
struct Fixture {
    store: UintStoreRequires,
    muls: UintMulRequires,
    ec: EcStoreRequires,
    point: EcPointPtr,
}

/// Build a fixture for the curve `y² = x³ + ax + b` over `p = bound + 1`
/// with one finite point `(x, y)` (must be on-curve; asserted by the
/// membership MACs) — the modulus pinned @1, everything else recorded
/// through [`EcRequire`]. The add-relation and EcGroupAdd accumulators
/// stay empty (point binding records only MACs) and are dropped.
fn fixture(bound: U256, a: U256, b: U256, x: U256, y: U256) -> Fixture {
    let mut store = UintStoreRequires::new();
    let fp = store.pin_modulus(1, bound);
    let mut adds = UintAddRequires::new();
    let mut muls = UintMulRequires::new();
    let mut ec = EcStoreRequires::new();
    let mut ec_add = EcAddRequires::new();

    let mut req =
        EcRequire::new(&mut ec, &mut ec_add, UintRequire::new(&mut store, &mut adds, &mut muls));
    let (g, _pai) = req.create_group(a, b, fp);
    let point = req.add_point(g, x, y);

    Fixture { store, muls, ec, point }
}

/// secp256k1: y² = x³ + 7, with the standard base point.
fn k1_fixture() -> Fixture {
    let bound = from_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2E");
    let gx = from_hex("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798");
    let gy = from_hex("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8");
    fixture(bound, from_hex("0"), from_hex("7"), gx, gy)
}

/// The five involved mains, laid in one consuming sweep over a fixture.
struct FixtureTraces {
    bpl: RowMajorMatrix<Felt>,
    store: RowMajorMatrix<Felt>,
    mul: RowMajorMatrix<Felt>,
    groups: RowMajorMatrix<Felt>,
    points: RowMajorMatrix<Felt>,
}

impl Fixture {
    /// Lay all five mains, each pass consuming its accumulator and
    /// routing the demand its rows consume (mul → store; the point
    /// store's own `EcGroup` consume was fed at intern). Bus-closed over
    /// {BPL, UintStore, UintMul, EcGroups, EcPointStore} — no `UintAdd`
    /// (membership is MACs only).
    fn traces(mut self) -> FixtureTraces {
        let mut bpl = BytePairLutRequires::new();
        let mul = mul_trace(self.muls, &mut self.store, &mut bpl);
        let store = store_trace(self.store, &mut bpl);
        let (groups, points) = ec_store_traces(self.ec);
        FixtureTraces {
            bpl: bpl_trace(bpl),
            store,
            mul,
            groups,
            points,
        }
    }
}

/// Net LogUp residual across the five mains (0 ⟺ balanced); the EC mains
/// are passed explicitly so tamper tests can substitute a forged one for
/// the laid one.
fn residual(
    t: &FixtureTraces,
    groups: &RowMajorMatrix<Felt>,
    points: &RowMajorMatrix<Felt>,
    rng: &mut impl Rng,
) -> usize {
    let [alpha, beta] = [rand_qf(rng), rand_qf(rng)];
    let challenges = Challenges::new(alpha, beta, MAX_MESSAGE_WIDTH, NUM_BUS_IDS);
    let mut net: HashMap<QuadFelt, Felt> = HashMap::new();
    fold_balance(&EcGroupsAir, groups, &challenges, &mut net);
    fold_balance(&EcPointStoreAir, points, &challenges, &mut net);
    fold_balance(&UintMulAir, &t.mul, &challenges, &mut net);
    fold_balance(&UintStoreAir, &t.store, &challenges, &mut net);
    fold_balance(&BytePairLutAir, &t.bpl, &challenges, &mut net);
    net.values().filter(|m| **m != Felt::ZERO).count()
}

fn check_points(main: &RowMajorMatrix<Felt>) {
    crate::tests::check_local(EcPointStoreAir, main);
}

fn check_groups(main: &RowMajorMatrix<Felt>) {
    crate::tests::check_local(EcGroupsAir, main);
}

#[test]
fn log_quotient_degree_matches_design_target() {
    // Flattened via `frac_col!` into 5 aux columns (col 0 the gated
    // running-sum anchor alone, col 1 a pair, cols 2-4 each a lone
    // degree-3 membership MAC), so every closing constraint stays at
    // degree ≤ 3 → log_quotient_degree = 1.
    assert_eq!(crate::tests::log_quotient_degree(&EcPointStoreAir), 1);
}

fn group_trace_with_pad_row() -> (RowMajorMatrix<Felt>, usize) {
    let mut store = EcStoreRequires::new();
    let mut live_groups = CurveId::ALL.len();
    while live_groups.is_power_of_two() {
        let base = 10_000 + live_groups as u32 * 3;
        store.create_group(
            UintPtr::from_addr(base),
            UintPtr::from_addr(base + 1),
            UintPtr::from_addr(base + 2),
        );
        live_groups += 1;
    }

    let (groups, _) = ec_store_traces(store);
    assert!(groups.height() > live_groups);
    (groups, live_groups)
}

#[test]
fn ec_stores_hold_and_balance() {
    let mut rng = StdRng::seed_from_u64(0xec_0001);
    let fx = k1_fixture();
    let (group, _) = fx.ec.point_params(fx.point);
    let group_row = (group.addr() as usize - 1) * G_NUM_MAIN_COLS;
    let t = fx.traces();
    // Group table: VM-owned fixed curve slots plus the fixture-created group,
    // padded to a power-of-two height. Point store: PAI @1, point @2 — exactly
    // height 2, no pad.
    assert_eq!(t.groups.height(), (CurveId::ALL.len() + 1).next_power_of_two());
    assert_eq!(t.points.height(), 2);
    assert_eq!(t.points.values[COL_IS_PAI], Felt::ONE, "row 0 is the canonical PAI",);
    assert_eq!(t.points.values[NUM_MAIN_COLS + COL_IS_PAI], Felt::ZERO);
    // The vacuous scalar bound defaults to the F_p handle on both point rows
    // and the owning group row.
    assert_eq!(t.groups.values[group_row + G_COL_SBOUND_PTR], t.points.values[COL_SBOUND_PTR],);
    assert_eq!(
        t.groups.values[group_row + G_COL_SBOUND_PTR],
        t.points.values[NUM_MAIN_COLS + COL_SBOUND_PTR],
    );

    check_groups(&t.groups);
    check_points(&t.points);
    assert_eq!(residual(&t, &t.groups, &t.points, &mut rng), 0);
}

#[test]
fn ec_store_ed25519_image_torsion_point() {
    // The ed25519 SW image (the design notes) and its single
    // rational 2-torsion point (A/3, 0): a finite point whose y is the
    // stored zero — cleanly distinct from PAI — passing membership with
    // w = y² = 0. Constants machine-verified against the map derivation.
    let mut rng = StdRng::seed_from_u64(0xec_25519);
    let bound = from_hex("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC");
    let a_w = from_hex("2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA984914A144");
    let b_w = from_hex("7B425ED097B425ED097B425ED097B425ED097B425ED097B4260B5E9C7710C864");
    let x_t = from_hex("2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD2451");
    let t = fixture(bound, a_w, b_w, x_t, from_hex("0")).traces();

    check_groups(&t.groups);
    check_points(&t.points);
    assert_eq!(residual(&t, &t.groups, &t.points, &mut rng), 0);
}

#[test]
fn constrained_scalar_bound_balances() {
    // Pin the secp256k1 group order's n − 1 as a second modulus and
    // constrain the group's scalar field with it: every EcGroup tuple
    // site (group row, point rows) must carry the F_s handle instead of
    // the vacuous F_p default, and the bus still closes.
    let mut rng = StdRng::seed_from_u64(0xec_f5);
    let mut fx = k1_fixture();
    let n_minus_1 = from_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140");
    let fs = fx.store.pin_modulus(2, n_minus_1);
    let (group, _) = fx.ec.point_params(fx.point);
    let group_row = (group.addr() as usize - 1) * G_NUM_MAIN_COLS;
    fx.ec.set_scalar_bound(group, fs);
    let t = fx.traces();
    assert_eq!(t.groups.values[group_row + G_COL_SBOUND_PTR], Felt::from(fs.addr()));
    assert_eq!(
        t.points.values[COL_SBOUND_PTR],
        Felt::from(fs.addr()),
        "PAI row resolves the constrained scalar bound",
    );
    assert_eq!(
        t.points.values[NUM_MAIN_COLS + COL_SBOUND_PTR],
        Felt::from(fs.addr()),
        "finite point row resolves the constrained scalar bound",
    );

    check_groups(&t.groups);
    check_points(&t.points);
    assert_eq!(residual(&t, &t.groups, &t.points, &mut rng), 0);
}

#[test]
fn forged_scalar_bound_unbalances() {
    // A point row claiming a different scalar bound than its group's:
    // every local constraint holds, but the 5-tuple EcGroup consume
    // matches no provide.
    let mut rng = StdRng::seed_from_u64(0xec_f5bad);
    let t = k1_fixture().traces();
    let mut forged = t.points.clone();
    forged.values[NUM_MAIN_COLS + COL_SBOUND_PTR] = Felt::from(7u32);

    check_points(&forged);
    assert_ne!(residual(&t, &t.groups, &forged, &mut rng), 0);
}

#[test]
fn off_curve_point_unbalances() {
    // Repoint the stored point's y at a different (valid, canonical)
    // uint: every local constraint still holds — the cells are bindings,
    // not equations — but the y² membership MAC consume now names a tuple
    // nothing proves, so the bus rejects what the AIR alone cannot see.
    let mut rng = StdRng::seed_from_u64(0xec_0ff);
    let fx = k1_fixture();
    let (_, coords) = fx.ec.point_params(fx.point);
    let (x_ptr, _) = coords.expect("finite point");
    let t = fx.traces();
    let mut forged = t.points.clone();
    forged.values[NUM_MAIN_COLS + COL_Y_PTR] = Felt::from(x_ptr.addr()); // y := x

    check_points(&forged);
    assert_ne!(residual(&t, &t.groups, &forged, &mut rng), 0);
}

#[test]
#[should_panic]
fn pai_forgery_on_finite_point_rejected() {
    // Claiming is_pai on the finite point row (to skip membership) trips
    // the none-sentinel ties: is_pai · x_ptr = 0.
    let mut forged = k1_fixture().traces().points;
    forged.values[NUM_MAIN_COLS + COL_IS_PAI] = Felt::ONE;

    check_points(&forged);
}

#[test]
#[should_panic]
fn pai_with_coordinates_rejected() {
    // A PAI row naming real coordinates is equally rejected (the dual
    // forgery: smuggling a point binding under the membership-free flag).
    let fx = k1_fixture();
    let (_, coords) = fx.ec.point_params(fx.point);
    let (x_ptr, _) = coords.expect("finite point");
    let mut forged = fx.traces().points;
    forged.values[COL_X_PTR] = Felt::from(x_ptr.addr()); // the PAI row is row 0

    check_points(&forged);
}

#[test]
#[should_panic]
fn duplicate_point_ptr_rejected() {
    // Two points sharing a ptr would break ptr → point; the consecutive
    // chain (act-gated ptr' = ptr + 1) rejects it.
    let mut forged = k1_fixture().traces().points;
    forged.values[NUM_MAIN_COLS + COL_PTR] = Felt::ONE; // duplicate of row 0

    check_points(&forged);
}

#[test]
fn phantom_group_unbalances() {
    // A point claiming a group that was never created: constraints hold,
    // the EcGroup consume finds no provider.
    let mut rng = StdRng::seed_from_u64(0xec_9457);
    let t = k1_fixture().traces();
    let mut forged = t.points.clone();
    forged.values[NUM_MAIN_COLS + COL_GROUP_PTR] = Felt::from(7u32);

    check_points(&forged);
    assert_ne!(residual(&t, &t.groups, &forged, &mut rng), 0);
}

#[test]
#[should_panic]
fn group_ptr_chain_is_ungated() {
    // The group table has no act flag: ptr = row + 1 is forced on every
    // row, pads included (a pad is just a mult = 0 row). Rewriting a pad
    // row's ptr — the move that would mint a duplicate group id — trips
    // the ungated chain.
    let (groups, live_groups) = group_trace_with_pad_row();
    let mut forged = groups;
    let pad_row = live_groups * G_NUM_MAIN_COLS;
    forged.values[pad_row] = Felt::ONE; // pad row ptr := 1 (dup of row 0)

    check_groups(&forged);
}

#[test]
fn forged_group_mult_unbalances() {
    // Zeroing the live fixture group's provide mult leaves the point rows'
    // EcGroup consumes dangling — the dual of the phantom group. The fixture
    // group is not hardcoded to row 0 because the group table starts with
    // VM-owned preseeded rows.
    let mut rng = StdRng::seed_from_u64(0xec_3017);
    let fx = k1_fixture();
    let (group, _) = fx.ec.point_params(fx.point);
    let group_mult = (group.addr() as usize - 1) * G_NUM_MAIN_COLS + crate::ec::groups::COL_MULT;
    let t = fx.traces();
    let mut forged = t.groups.clone();
    forged.values[group_mult] = Felt::ZERO;

    check_groups(&forged);
    assert_ne!(residual(&t, &forged, &t.points, &mut rng), 0);
}

#[test]
fn empty_stores_hold() {
    // No runtime groups or points: fixed group rows plus pad rows must satisfy
    // every constraint and touch no bus unless separately required.
    let (groups_main, points_main) = ec_store_traces(EcStoreRequires::new());
    assert_eq!(groups_main.height(), CurveId::ALL.len().next_power_of_two().max(2));
    assert_eq!(points_main.height(), 2);
    assert_eq!(groups_main.values.len(), groups_main.height() * G_NUM_MAIN_COLS);
    check_groups(&groups_main);
    check_points(&points_main);
}

#[test]
#[should_panic]
fn inactive_point_row_cannot_provide() {
    // A pad row with nonzero EcPoint multiplicity would provide a point
    // without paying its EcGroup / membership obligations.
    let (_, mut points_main) = ec_store_traces(EcStoreRequires::new());
    points_main.values[COL_ECPOINT_MULT] = Felt::ONE;

    check_points(&points_main);
}