Thv/degree lowering hardening

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

247 stars 37 forks source link

Thv/degree lowering hardening #325

Closed Sword-Smith closed 1 month ago

Sword-Smith commented 2 months ago

Add tests that degree lowering and code generator for constraint evaluation is deterministic and does not change unintentionally.

aszepieniec commented 1 month ago

Something funky is happening with the test table::master_table::tests::air_constraints_evaluators_have_not_changed which I can't explain. CI is failing with

expected: (03756754445351585926·x² + 06769459618545093804·x + 09140558386905394900)
observed: (14714205515170095309·x² + 13661591558076455036·x + 14115119063754412580)

whereas on my desktop computer I get

expected: (03756754445351585926·x² + 06769459618545093804·x + 09140558386905394900)
observed: (03346962278739234229·x² + 12572006219868624302·x + 10286558549229477187)

and both are obviously different from my laptop which produced the expected value. Any ideas as to what might cause this?

Sword-Smith commented 1 month ago

On my desktop at home, I get the same as the CI machine observed:

expected: (03756754445351585926·x² + 06769459618545093804·x + 09140558386905394900)
observed: (14714205515170095309·x² + 13661591558076455036·x + 14115119063754412580)

Sword-Smith commented 1 month ago

Would it make sense to also add a proptest like node_substitution_is_complete_and_sound for a DualRowIndicator type?

aszepieniec commented 1 month ago

Correction: on my laptop I get this failure:

exoected: (03756754445351585926·x² + 06769459618545093804·x + 09140558386905394900)
observed: (03346962278739234229·x² + 12572006219868624302·x + 10286558549229477187)

which agrees with my desktop.

After rebasing in @Sword-Smith's faster compilation changes, I get this failure

expected: (03756754445351585926·x² + 06769459618545093804·x + 09140558386905394900)
observed: (14714205515170095309·x² + 13661591558076455036·x + 14115119063754412580)

which agrees with CI and @Sword-Smith's machine.

aszepieniec commented 1 month ago

For the record, applying just the first commit (9e5db866063a6527366be62616611d74db1ef416) of setting opt-level=3 generates this failure:

expected: (03756754445351585926·x² + 06769459618545093804·x + 09140558386905394900)
observed: (03346962278739234229·x² + 12572006219868624302·x + 10286558549229477187)

which agrees with the failure before setting the opt-level. So this compiler optimization does not seem to change anything.

aszepieniec commented 1 month ago

@jan-ferdinand: All checks pass. Any further requested changes?

aszepieniec commented 1 month ago

BTW: I can confirm that all tests pass on my desktop machine as well.

aszepieniec commented 1 month ago

All comments are resolved now (I think).

jan-ferdinand commented 1 month ago

All comments are resolved now (I think).

I'm still wondering about the following points:

Can the code in the various num_ functions be de-duplicated? (review comment)
Is there a copy-paste error in the docstring for num_nodes? (review comment)
Is the method how the various num_ things are computed relevant enough to be mentioned in the docstring? (review comment)
Can the hidden relationship between node types in the multicircuit strategy be removed by changing which node types are supplied? (review comment)

aszepieniec commented 1 month ago

I think I've answered all your questions. Any further remarks / requests?

jan-ferdinand commented 1 month ago

No further requests. Happy to have this test in. :+1: