TritonVM / tasm-lib

A collection of functions written in Triton VM assembly (tasm)
Apache License 2.0
11 stars 2 forks source link

Change return type of `pseudorandom_initial_state` to `Vec<InitStates>` #56

Closed Sword-Smith closed 6 months ago

Sword-Smith commented 1 year ago

Consider the snippet safe_pow that implements Closure. My implementation of pseudorandom_initial_state is

    fn pseudorandom_initial_state(
        &self,
        seed: [u8; 32],
        bench_case: Option<crate::snippet_bencher::BenchmarkCase>,
    ) -> Vec<triton_vm::BFieldElement> {
        let (base, exponent): (u32, u32) = match bench_case {
            Some(BenchmarkCase::CommonCase) => (10, 5),
            Some(BenchmarkCase::WorstCase) => (2, 31),
            None => {
                let mut seeded_rng = StdRng::from_seed(seed);
                let base: u32 = seeded_rng.gen_range(0..0x10);
                let exponent: u32 = seeded_rng.gen_range(0..0x8);
                (base, exponent)
            }
        };

        [
            get_init_tvm_stack(),
            vec![
                BFieldElement::new(base as u64),
                BFieldElement::new(exponent as u64),
            ],
        ]
        .concat()
    }

The problem here is that, to avoid overflows, only a very specific range of values are being tested. If, instead, pseudorandom_initial_state return Vec<Vec<triton_vm::BFieldElement>>, then you could test with ranges like so:

// existing ranges
let base: u32 = seeded_rng.gen_range(0..0x10);
let exponent: u32 = seeded_rng.gen_range(0..0x8);

// Big bases
let base: u32 = seeded_rng.gen_range(0..(1 << 16));
let exponent: u32 = seeded_rng.gen_range(0..3);

// Medium-sized bases
let base: u32 = seeded_rng.gen_range(0..(1 << 8));
let exponent: u32 = seeded_rng.gen_range(0..5);

And then return a list of pseudo-random initial states.

Sword-Smith commented 6 months ago

Closed by the possibility of adding corner-cases to all snippet trait implementations. Cf. corner_case_initial_states for the Algorithm trait, the Closure trait etc.