Improves 2 times the prover speed.

• Computes outside of the forloop some polynomial evaluations and inverses.
• Change lagrange evaluation to FFT.
• Uses batch inverse.

When calculating FRI layers, the lde_root_order must be passed. We were passing the regular root_order, and these was hidden because our tests had trace lengths that were not very long.

• Add basic cairo run for making and verifying proofs
• Added a call to either cairo-compile or the cairo compiler Dockerfile to let the prove and verify run with a call of one line

• Extracts the build_main_trace function from the AIR trait.
• Refactors trace padding.
• Refactors program generation functions so that both integration and unit tests uses the same logic to generate prover arguments.

This PR adds the following:

1. Use a modified version of Merkle trees that don't hash back to Field Elements and builds the entire tree using bytes.
2. Instead of building a Merkle tree for each column of the RAP, use a single Merkle tree for the trace columns of the main part of the RAP another Merkle tree for the second part. The data of each leaf of these merkle trees are the vectors of evaluations of all the polynomials involved.

There are two merkle trees for each part of the RAP because the prover needs to commit to the first ones before getting the RAP challenges from the verifier. Improvements on this are left for another PR.

Benchmarking CAIRO/fibonacci/10: Collecting 10 samples in estimated 31.762 s (99
CAIRO/fibonacci/10      time:   [31.787 ms 32.771 ms 34.208 ms]
                        change: [-42.359% -40.011% -37.434%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking CAIRO/fibonacci/30: Collecting 10 samples in estimated 32.952 s (44
CAIRO/fibonacci/30      time:   [67.688 ms 68.215 ms 69.366 ms]
                        change: [-38.890% -36.275% -33.590%] (p = 0.00 < 0.05)
                        Performance has improved.

Updates lambdaworks dep to use Ruffini division in deep composition polynomials. The update also includes a few other optimizations, namely the Merkle tree build one.

Bench results (on M1)

CAIRO/fibonacci/10      time:   [59.898 ms 60.048 ms 60.284 ms]
                        change: [-53.124% -52.911% -52.675%] (p = 0.00 < 0.05)
CAIRO/fibonacci/30      time:   [132.44 ms 132.91 ms 133.17 ms]
                        change: [-66.094% -66.001% -65.920%] (p = 0.00 < 0.05)

• Add a function to create public inputs from registers and memory
• Add documentation
• Add a call to the Cairo VM Runner in integration to get memory and trace from it, remove the need to use intermediate files for it
• Remove unused test files
• Made layouts an Enum so they are easy to pick
• Removed ignored tests that were not runned because of proving time
• Removed call test, since it was tested indirectly by other programs

We need another refactor, and after optimization make a bigger test suite to be run in the CI

It uses a helper function to convert the Stark Proof struct to Strings with conversion from montgomery representation.

Probably not the most elegant way but it works fine at least Reviews/Suggestions welcomed

There were some transitions constraints (continuous range-check values) that didn't had their degrees set in the Cairo AIR. This is something that does not affect in a lot of cases, but when developing builtin features and adding new constraints broke some things.

The prover is using constraints selectors to enable or disable contraints for optimizations. The verifier then doesn't check which constraints have been disabled, so incorrect proofs can be shared.

This can lead to issues where the Prover disable constraints that shouldn't be disabled

Taken from EthStark and paper

The conjectured security in this system is the minimum of three values:

log_n_cosets * n_queries + proof_of_work_bits (these are the parameters that appear in the parameter_file. Refer to the [Prover Inputs] section for details). The collision resistance of the hash used by the protocol. This system employs Blake2s160 for the protocol, which is considered to provide 80 bits of security at the time of writing this project. log(extension_field_size) - log(trace_length) (where the extension field is hardcoded to be of size 122 bits, and trace_length = (chain_length / 3) * 32 rounded up to nearest power of 2).

Work in progress.

Done : STARK proof generated by test_prove_cairo_program in the integration tests is written to a json file. It is then parsed with the parse_cairo_proof.py script and written to a Cairo file and loaded into the correct structs to match the lambdaworks Verifier 1:1. Same for CairoAIR stuct that holds some parameters. Same for public inputs (after the proving part).

Next steps : Complete step_1 of verification algorithm. Complete step_2 of verification algorithm. Complete step_3 of verification algorithm. Complete step_4 of verification algorithm. Optimizations. Include more builtins. Use poseidon instead of keccak. Convert to Starknet smart contract.

[...]