How do you like your eggs?
To give you a better chance of solving this puzzle, we suggest that you look through some relevant background materials. For this particular puzzle, we recommend that you get upto speed on StarkDEX, the STARK Core Engine and ethSTARK.
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.
You can see all of the scores for this puzzle in the spreadsheet here.
The winner of the puzzle write up was submitted by MatanHamilis as part of a
team submission from tom marvolo riddle. You can view the solution and puzzle write up
The background material required to solve the puzzle is also covered in the write up.
There were many excellent solution submissions which are linked below:
* Solution by SoloHiker
* Solution by huitseeker
* Solution by cronokirby
* Solution by TrapdoorTech
* Solution by logN
* Solution by mimoo
* Solution by hyunok oh
* Solution by niooss-ledger