Puzzle Hints

1. Since the constraints don’t hold and most polynomials will not be low degree, the DEEP consistency check and the DEEP composition polynomial evaluations needed for FRI won’t match between the prover and the verifier. The prover must pretend they’re acting as the verifier. Note that FRI is run with a single query.

2. Look at the “hint2” pull request to see how the prover can act as the verifier would. Now, you can use the low amount of queries done in FRI to create a fake proof. You can use “cargo run --release -- -q 1 fib -n 32” to run with a single FRI query and 32 fibonacci steps.

3. Look at the “hint3” pull request to see a partial modification of the folding process in FRI. Fill up the rest so that the FRI will be verified.
Specifically, notice the following comment from the code:
HINT3: To pass FRI checks, the result of folding the first FRI layer should be a degree 3 polynomial. Since the first FRI layer is folded from a domain of 128 elements to a domain of 32 elements, we can pick some 4 points in the folded domain, interpolate them into a degree 3 polynomial, and then back fill the remaining 28 points with correct evaluations of this polynomial. The trick then is to try different versions of the proof so that the randomly selected query indexes fall on the values which were folded correctly. Since we only have a single FRI query, this is easy to do.