Snippets indicating completeness problems in Triton-vm

[Sword-Smith]

Proving and verifying execution of these snippets fail. This is most likely a problem in Triton-VM

    hashing::sample_indices::tests::new_prop_test
    hashing::sample_indices::tests::sample_indices_benchmark_safe
    hashing::sample_indices::tests::sample_indices_benchmark_unsafe
    mmr::calculate_new_peaks_from_append::tests::calculate_new_peaks_from_append_benchmark
    mmr::calculate_new_peaks_from_append::tests::calculate_new_peaks_from_append_test_safe_lists
    mmr::load_from_secret_in_then_verify::tests::load_from_secret_in_then_verify_benchmark_safe_lists
    mmr::load_from_secret_in_then_verify::tests::load_from_secret_in_then_verify_benchmark_unsafe_lists
    mmr::load_from_secret_in_then_verify::tests::load_from_secret_in_then_verify_test_safe_lists
    mmr::load_from_secret_in_then_verify::tests::load_from_secret_in_then_verify_test_unsafe_lists
    mmr::verify_from_memory::auth_path_verify_from_memory_tests::mmra_ap_verify_many_leafs
    mmr::verify_from_memory::auth_path_verify_from_memory_tests::mmra_ap_verify_test_pbt
    mmr::verify_from_memory::auth_path_verify_from_memory_tests::mmra_ap_verify_test_two
    mmr::verify_from_memory::auth_path_verify_from_memory_tests::verify_from_memory_benchmark_safe_lists
    mmr::verify_from_memory::auth_path_verify_from_memory_tests::verify_from_memory_benchmark_unsafe_lists
    mmr::verify_from_memory::auth_path_verify_from_memory_tests::verify_from_memory_test_safe_list
    mmr::verify_from_memory::auth_path_verify_from_memory_tests::verify_from_memory_test_unsafe_list

To verify the failure of the proving/verification of any snippet in this list, execute the following command in your terminal:

MY_COMPUTER_HAS_NOTHING_BETTER_TO_DO=1 cargo t <name-of-test> -- --nocapture

[Sword-Smith]

The smallest test case I've found that shows the completeness error in Triton-VM is the test mmra_append_test_three_leaves_safe. But some more digging should be done to get to the bottom of this, as that's still a quite big program with an execution trace length of 542.

Error from Triton-VM shows that the error is in codeword 243:

  Codeword 241 has degree  5118. Must be of maximal degree  8191.
  Codeword 242 has degree  3071. Must be of maximal degree  8191.
! Codeword 243 has degree 32767. Must be of maximal degree  8191.
  Codeword 244 has degree  5118. Must be of maximal degree  8191.
  Codeword 245 has degree  5118. Must be of maximal degree  8191.

The equivalent program using unsafe lists succeeds, so the problem is probably in an instruction that's present in the safe list implementation but not in the unsafe list implementation.

[Sword-Smith]

One bug identified and upgraded to issue and PR in Triton-VM:
TritonVM/triton-vm#205

[Sword-Smith]

These snippets are still failing:

    hashing::sample_indices::tests::new_prop_test
    hashing::sample_indices::tests::sample_indices_benchmark_safe
    hashing::sample_indices::tests::sample_indices_benchmark_unsafe

[Sword-Smith]

These snippets are still failing:

    hashing::sample_indices::tests::new_prop_test
    hashing::sample_indices::tests::sample_indices_benchmark_safe
    hashing::sample_indices::tests::sample_indices_benchmark_unsafe

Addressed in Triton VM RP: TritonVM/triton-vm#208