search

TritonVM / triton-vm

Triton is a virtual machine that comes with Algebraic Execution Tables (AET) and Arithmetic Intermediate Representations (AIR) for use in combination with a STARK proof system.
https://triton-vm.org
Apache License 2.0
223 stars 35 forks source link

Proving fails for FRI expansion factors (strictly) larger than 4 #289

Closed Sword-Smith closed 1 month ago

Sword-Smith commented 1 month ago

Somewhere between version 0.42-alpha-3 and alpha-4 prove started to fail for FRI expansion factors of 8 and above. This was discovered through the different_fri_expansion_factors test in tasm-lib.

I managed to reproduce the failure in triton-vm. A failing test can be found on the thv/_289_deep_update_zip_eq_failure branch.

The failure is:

thread 'verifier::stark_verify::tests::different_fri_expansion_factors' panicked at /home/thv/.cargo/registry/src/index.crates.io-6f17d22bba15001f/triton-vm-0.42.0-alpha.4/src/stark.rs:677:14:
assertion `left == right` failed: iterators must have the same length
  left: 2048
 right: 4096

It's the 1st call to deep_codeword that fails:

        let base_and_ext_curr_row_deep_codeword = Self::deep_codeword(
            &base_and_ext_codeword.clone(),
            short_domain,
            out_of_domain_point_curr_row,
            out_of_domain_curr_row_base_and_ext_value,
        );