Back
Puzzle M2

8th March

18:45 UTC

Built by:

Prizes:

How do you like your eggs?


Puzzle M2 Solution

Puzzle Preparation

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.




See puzzle details on Github

Puzzle link

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.

Puzzle Winners


gold 01

Trapdoor Tech

Puzzle completed

Score

1000

silver 02

maxgillett

Puzzle completed

Score

849.0

bronze 03

ZKSession

Puzzle completed

Score

812.3


You can see all of the scores for this puzzle in the spreadsheet here.

Puzzle Solution

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 here. 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