Bad parameter leads to an infinite loop

[pventuzelo]

Executive Summary

The Prover doesn't check the folding_factor before using it, leading to a potential infinite loop.

Steps to Reproduce

1. Reproduce the command lines in the demo of Sandstorm adding the following line:

       --fri-folding-factor 1

   between the line

       --air-private-input example/air-private-input.json \

   and the line

      --output example/array-sum.proof

   Like that:

        # 1. (optional) install Cairo and activate the venv
        # https://www.cairo-lang.org/docs/quickstart.html
        source ~/cairo_venv/bin/activate
   
        # 2. (optional) compile and run the Cairo program
        cairo-compile example/array-sum.cairo --proof_mode --output example/array-sum.json
        cairo-run --program example/array-sum.json \
                --air_private_input example/air-private-input.json \
                --air_public_input example/air-public-input.json \
                --trace_file example/trace.bin \
                --memory_file example/memory.bin \
                --min_steps 128 \
                --layout recursive \
                --proof_mode
   
        # 3. generate the proof
        cargo +nightly run -p sandstorm-cli -r -F parallel -- \
            --program example/array-sum.json \
            --air-public-input example/air-public-input.json \
            prove --air-private-input example/air-private-input.json \
                --fri-folding-factor 1 \
                --output example/array-sum.proof

Root Cause Analysis

In the main function of Sandstorm, at line 76, the parameters of the command are charged from the command lines, and so is the fri-folding-factor, equal to 1.

This factor is used in the num_layers function,
itself called by build_layers (here),
itself called by default_prove (here),
itself called by the function prove called in the main file at line 201.

Normally the fri-folding-factor, (i.e. the folding_factor) should not be anything other than 2, 4, 8, 16, but, in the build_layers function, the num_layers function is called before checking the factor (line 185). In another case than ours, this is not a problem, because exiting the num_layers function leads to the verifications (with the match use) in the build_layers function, but in our case, since the folding_factor is 1, we never go out the num_layers function (since we divide the domain_size by 1 at each iteration), and so we have an infinite loop.