igneum/igneum-pow/tests/derive.rs

//! The per-day item-derivation program (Counter ASIC 3.0 item 2, `docs/plans/counter-asic-3-derivation.md`): the
//! soundness runs on the CPU.
//!
//! 1. By hand: the derived item of class dr736 restated with the scalar reference on a small cache equals the
//!    verifier's batched (SoA) derivation, at the item boundary and the index wrap.
//! 2. The v2 and v3 paths are untouched: the derivation field is 0 on both, their items are the fixed-mixer items.
//! 3. Determinism and the stream: two epochs agree on every vector and file; the program is the continuation of the
//!    mixer's stream (the first draw of the program follows the 40 mixer draws); a different day draws a different
//!    program; the class is in the program id and the name.
//! 4. Stats beside x8: bit balance and single-bit avalanche of the derived items and of the hash, on the same seeds.
//! 5. A program whose text is the kernels': every instruction's C text evaluated by hand on one state matches the
//!    scalar reference (the text forms are what Metal, CUDA and OpenCL compile).

use igneum_pow::derive::{instr_text, run_round_scalar, DOp, DeriveProgram, DERIVE_LEN_X8, DERIVE_PROGRAMS};
use igneum_pow::emit::export_pack;
use igneum_pow::generator::{generate_from_seed_bytes_class, LoadClass, V3_CLASS};
use igneum_pow::memhard::{derive_item, derive_items, mixer, round_key, Cache, MixParams, Shape, ITEM_ROUNDS};
use igneum_pow::seed::{day_key, SplitMix64};
use igneum_pow::verify::{DatasetMode, DatasetSource, Epoch};

const DAY: &str = "2026-10-03";

/// The item of a derivation class restated by hand with the scalar reference.
fn item_by_hand(t: u32, mp: &MixParams, cache: &Cache) -> [u32; 16] {
    let prog = mp.derive.as_ref().expect("a derivation class");
    let mut s = [0u32; 16];
    s[..8].copy_from_slice(&mp.key);
    for i in 0..8 {
        s[8 + i] = t.wrapping_mul(mp.mul[i]).wrapping_add(mp.rc[i]);
    }
    for r in 0..ITEM_ROUNDS {
        run_round_scalar(&prog.rounds[r], &mut s);
        let line = cache.line(s[0]);
        for i in 0..16 {
            s[i] ^= line[i];
        }
    }
    run_round_scalar(&prog.rounds[ITEM_ROUNDS], &mut s);
    s
}

#[test]
fn derived_item_by_hand_and_in_batches() {
    let key = day_key(DAY);
    let cache = Cache::fill_log2(key, 16);
    let shape = Shape { mixer_mult: 1, cache_log2_words: 16, derive_len: DERIVE_LEN_X8 };
    let mp = MixParams::with_shape(key, shape);
    let prog = mp.derive.as_ref().unwrap();
    assert_eq!(prog.rounds.len(), DERIVE_PROGRAMS);
    assert!(prog.check().is_ok());
    assert_eq!(shape.derive_instrs_per_item(), 9 * DERIVE_LEN_X8);
    assert_eq!(shape.mixers_per_item(), 0);
    for t in [0u32, 1, 2, 15, 16, 17, 12_345, (1 << 28) - 1, u32::MAX - 1, u32::MAX] {
        assert_eq!(derive_item(t, &mp, &cache), item_by_hand(t, &mp, &cache), "t {t}");
    }
    // a batch of 32 distinct items against one at a time, and a short batch
    let ts: Vec<u32> = (0..32).map(|k| k * 7_919 + 3).collect();
    let mut out = [[0u32; 16]; 32];
    derive_items(&ts, &mp, &cache, &mut out);
    for (k, &t) in ts.iter().enumerate() {
        assert_eq!(out[k], item_by_hand(t, &mp, &cache), "batch slot {k}");
    }
    let mut out5 = [[0u32; 16]; 5];
    derive_items(&ts[..5], &mp, &cache, &mut out5);
    assert_eq!(&out5[..], &out[..5]);
    // the fixed mixer of the same key gives other items
    let v3 = MixParams::with_shape(key, Shape { mixer_mult: 8, cache_log2_words: 16, derive_len: 0 });
    assert!(v3.derive.is_none());
    assert_ne!(derive_item(0, &v3, &cache), derive_item(0, &mp, &cache));
}

#[test]
fn v2_and_v3_are_untouched() {
    assert_eq!(LoadClass::V2.derive_len, 0);
    assert_eq!(V3_CLASS.derive_len, 0);
    assert_eq!(LoadClass::MX8.derive_len, 0);
    assert_eq!(Shape::V2.derive_len, 0);
    assert!(!Shape::for_class(&V3_CLASS).is_derived());
    let key = day_key(DAY);
    let cache = Cache::fill_log2(key, 16);
    // the version 2 item restated by hand (the mixer_mult_by_hand test of memhard.rs, m = 1)
    let v2 = MixParams::with_shape(key, Shape { mixer_mult: 1, cache_log2_words: 16, derive_len: 0 });
    let t = 12_345u32;
    let mut s = [0u32; 16];
    s[..8].copy_from_slice(&key);
    for i in 0..8 {
        s[8 + i] = t.wrapping_mul(v2.mul[i]).wrapping_add(v2.rc[i]);
    }
    for r in 0..8usize {
        mixer(&mut s, round_key(r), &v2);
        let line = cache.line(s[0]);
        for i in 0..16 {
            s[i] ^= line[i];
        }
    }
    mixer(&mut s, round_key(8), &v2);
    assert_eq!(derive_item(t, &v2, &cache), s);
    // the mixer constants of the derivation class are the v2 draws (the stream continues after them)
    let dr = MixParams::with_shape(key, Shape { mixer_mult: 1, cache_log2_words: 16, derive_len: DERIVE_LEN_X8 });
    assert_eq!((dr.rot, dr.mul, dr.rc), (v2.rot, v2.mul, v2.rc));
}

#[test]
fn stream_class_name_and_id() {
    let key = day_key(DAY);
    // the program is the continuation of the mixer stream: 40 draws, then the program
    let mut rng = SplitMix64::new(key[0] as u64 | ((key[1] as u64) << 32));
    for _ in 0..40 {
        rng.next();
    }
    let expect = DeriveProgram::draw(&mut rng, DERIVE_LEN_X8);
    let mp = MixParams::with_shape(key, Shape { mixer_mult: 1, cache_log2_words: 26, derive_len: DERIVE_LEN_X8 });
    assert_eq!(mp.derive.as_ref().unwrap(), &expect);
    // another day, another program; another length, another program
    let other = MixParams::with_shape(day_key("2026-10-04"), Shape { mixer_mult: 1, cache_log2_words: 26, derive_len: DERIVE_LEN_X8 });
    assert_ne!(other.derive.as_ref().unwrap().fingerprint(), expect.fingerprint());
    let short = MixParams::with_shape(key, Shape { mixer_mult: 1, cache_log2_words: 26, derive_len: 368 });
    assert_eq!(short.derive.as_ref().unwrap().instr_count(), 9 * 368);
    // the class: name, parse, id, and the v2 program stream (v2 loads, no width roll)
    let c = LoadClass::DR736;
    assert_eq!(c.name(), "dr736");
    assert_eq!(LoadClass::parse("dr736"), Some(c));
    assert_eq!(LoadClass::parse("dr368"), Some(LoadClass::MX4.with_derive(368)));
    assert_eq!(LoadClass::parse("dr0"), None);
    assert_eq!(LoadClass::parse("dr5000"), None);
    assert!(c.v2_loads() && !c.takes_width_roll() && c.growth && c.mixer_mult == 1 && c.is_derived());
    let p = generate_from_seed_bytes_class("igneum-genesis", b"igneum-genesis", c);
    let v2 = generate_from_seed_bytes_class("igneum-genesis", b"igneum-genesis", LoadClass::V2);
    let mx8 = generate_from_seed_bytes_class("igneum-genesis", b"igneum-genesis", LoadClass::MX8);
    assert_eq!(p.instrs, v2.instrs, "the v2 program of the seed");
    assert_ne!(p.program_id(), v2.program_id());
    assert_ne!(p.program_id(), mx8.program_id());
    assert_ne!(
        generate_from_seed_bytes_class("igneum-genesis", b"igneum-genesis", LoadClass::MX4.with_derive(368)).program_id(),
        p.program_id()
    );
}

#[test]
fn determinism_and_pack_text() {
    let a = Epoch::new_class("igneum-genesis", DAY, DatasetMode::MemoryHard, 20, LoadClass::DR736);
    let b = Epoch::new_class("igneum-genesis", DAY, DatasetMode::MemoryHard, 20, LoadClass::DR736);
    let pa = export_pack(&a, DAY, "test");
    let pb = export_pack(&b, DAY, "test");
    assert_eq!(pa.outs, pb.outs);
    assert_eq!(pa.files, pb.files);
    let names: Vec<&str> = pa.files.iter().map(|(n, _)| n.as_str()).collect();
    assert!(names.contains(&"memhard.h") && names.contains(&"memhard.metal"));
    for (name, text) in &pa.files {
        if name == "memhard.h" || name == "memhard.metal" || name == "kernel.cl" {
            for r in 0..DERIVE_PROGRAMS {
                assert!(text.contains(&format!("mh_round_{r}(")), "{name} carries round program {r}");
            }
            assert!(!text.contains("mh_mixer(s,"), "{name}: no mixer application under a derivation program");
            let dp = a.dataset.memhard().unwrap().params.derive.as_ref().unwrap();
            // every instruction's text appears, in order, inside the round functions
            let first = instr_text(&dp.rounds[0][0]);
            assert!(text.contains(&first), "{name} carries the first instruction {first}");
        }
        if name == "program.h" {
            assert!(text.contains("#define IGNEUM_LOAD_CLASS \"dr736\""));
            assert!(text.contains("#define IGNEUM_DERIVE_LEN 736"));
            assert!(text.contains("#define IGNEUM_CLASS_DERIVE_LEN 736"));
            assert!(!text.contains("#define IGNEUM_MIXER_MULT"));
            assert!(text.contains("#define IGNEUM_GENERATOR 2"));
        }
        if name == "program.json" {
            assert!(text.contains("\"derive_len\": 736"));
            assert!(text.contains("\"programs\": ["));
            serde_json::from_str::<serde_json::Value>(text).expect("valid JSON");
        }
    }
    // the vectors are the interpreter's
    assert_eq!(pa.outs[0], a.hash_warp(0));
}

/// Bit balance and single-bit avalanche of the derived items (t flipped one bit) and of the hash, beside x8.
#[test]
fn stats_beside_x8() {
    let key = day_key(DAY);
    let cache = Cache::fill_log2(key, 18);
    let dr = MixParams::with_shape(key, Shape { mixer_mult: 1, cache_log2_words: 18, derive_len: DERIVE_LEN_X8 });
    let x8 = MixParams::with_shape(key, Shape { mixer_mult: 8, cache_log2_words: 18, derive_len: 0 });
    for (label, mp) in [("dr736", &dr), ("x8", &x8)] {
        let n = 2048u32;
        let mut ones = [0u32; 512];
        let mut flips = 0u64;
        let mut flip_n = 0u64;
        let mut seen = std::collections::HashSet::new();
        for t in 0..n {
            let a = derive_item(t * 2_654_435_761, mp, &cache);
            assert!(seen.insert(a), "{label}: duplicate item");
            for i in 0..16 {
                for b in 0..32 {
                    ones[i * 32 + b] += (a[i] >> b) & 1;
                }
            }
            let bit = t % 32;
            let c = derive_item((t * 2_654_435_761) ^ (1 << bit), mp, &cache);
            for i in 0..16 {
                flips += (a[i] ^ c[i]).count_ones() as u64;
            }
            flip_n += 512;
        }
        let avalanche = flips as f64 / flip_n as f64 * 100.0;
        let worst_z = ones.iter().map(|&o| ((o as f64 - n as f64 / 2.0) / (n as f64 / 4.0).sqrt()).abs()).fold(0.0, f64::max);
        println!("{label}: avalanche {avalanche:.2} percent, worst bit z {worst_z:.2}");
        assert!((48.5..=51.5).contains(&avalanche), "{label}: avalanche {avalanche}");
        assert!(worst_z < 4.5, "{label}: worst bit z {worst_z}");
    }
    // the hash on the same seeds: avalanche across a nonce flip within the unit
    let e = Epoch::new_class("igneum-genesis", DAY, DatasetMode::MemoryHard, 20, LoadClass::DR736);
    let w0 = e.hash_warp(0);
    let w1 = e.hash_warp(32);
    let mut d = 0u64;
    for l in 0..32 {
        d += (w0[l] ^ w1[l]).count_ones() as u64;
    }
    let av = d as f64 / (32.0 * 64.0) * 100.0;
    println!("hash unit 0 against unit 1: {av:.2} percent of bits differ");
    assert!((44.0..=56.0).contains(&av));
}

/// The kernels' text forms: every form's C text, read back into the scalar reference's arithmetic by hand.
#[test]
fn text_forms_match_scalar_reference() {
    let mut rng = SplitMix64::new(42);
    let p = DeriveProgram::draw_candidate(&mut rng, 64, 0);
    let mut s = [0u32; 16];
    for (i, v) in s.iter_mut().enumerate() {
        *v = 0x9e37_79b9u32.wrapping_mul(i as u32 + 1);
    }
    let mut seen = [false; 12];
    for ins in p.rounds.iter().flatten() {
        seen[ins.op as usize] = true;
        let before = s;
        run_round_scalar(std::slice::from_ref(ins), &mut s);
        let (d, c, b) = (ins.dst as usize, ins.src as usize, ins.src2 as usize);
        let (dv, cv, bv) = (before[d], before[c], before[b]);
        let want = match ins.op {
            DOp::Add => dv.wrapping_add(cv),
            DOp::Sub => dv.wrapping_sub(cv),
            DOp::Xor => dv ^ cv,
            DOp::Mul => dv.wrapping_mul(cv | 1),
            DOp::Rot => dv.rotate_left(ins.rot as u32).wrapping_add(cv),
            DOp::XRot => (dv ^ cv).rotate_left(ins.rot as u32),
            DOp::AddC => dv.wrapping_add(cv.wrapping_add(ins.imm)),
            DOp::XorC => dv ^ cv ^ ins.imm,
            DOp::MulC => (dv ^ cv).wrapping_mul(ins.imm),
            DOp::MulC2 => dv.wrapping_mul(ins.imm).wrapping_add(cv),
            DOp::AndX => dv ^ (cv & bv),
            DOp::OrX => dv.wrapping_add(cv | bv),
        };
        assert_eq!(s[d], want, "{}", instr_text(ins));
        for i in 0..16 {
            if i != d {
                assert_eq!(s[i], before[i], "only the destination changes: {}", instr_text(ins));
            }
        }
        assert!(instr_text(ins).starts_with(&format!("s[{d}]")));
    }
    assert!(seen.iter().all(|s| *s), "64 x 9 draws cover every form");
}

/// The dataset source of the class on a day: the verifier's `word` path derives through the program.
#[test]
fn dataset_source_word_path() {
    let ds = DatasetSource::new_shape(DAY, DatasetMode::MemoryHard, 20, Shape { mixer_mult: 1, cache_log2_words: 16, derive_len: DERIVE_LEN_X8 });
    let m = ds.memhard().unwrap();
    let item = derive_item(3, &m.params, &m.cache);
    for j in 0..16u32 {
        assert_eq!(ds.word(3 * 16 + j), item[j as usize]);
    }
    assert_eq!(ds.word((1 << 20) + 5), ds.word(5), "the mask");
}