What is the purpose of adding ShakePolynomial？

[cyl19970726]

In STIR paper, we don't need shake polynomial to verify the ans_polynomial, but in the code implement why we need it?

[cyl19970726]

https://github.com/WizardOfMenlo/stir/blob/main/src/stir/prover.rs#L294

[WizardOfMenlo]

This is an optimization. Computing the Ans polynomial is a quadratic cost for the verifier, so we ask the prover to send it instead. Since we can't trust it, we use a new technique called SHAKE to verify that the sent ans polynomial is correct (and this shake polynomial is the proof for it).

[cyl19970726]

But the degree of answer_polynomial is not very high, Does verifier really spend a lot of time calculating answer_polynomial?

degree = Repetitions_num + odd_samples 

In the below case the highest degree of the answer_polynomial is only 55.

STIR - Shaken
Targeting 128-bits of security - protocol running at 106-bits - soundness: Conjecture
Starting degree: 2^20, stopping_degree: 2^6
Starting rate: 2^-2, folding_factor: 16
Number of rounds: 3. OOD samples: 2
Rates: 2^-2, 2^-5, 2^-8, 2^-11
PoW bits: [22, 18, 16, 18]
Repetitions: [53, 22, 14, 10]

[WizardOfMenlo]

Yes, the degree is quite small, but this cost still adds up quite a bit. It could be also a subpar interpolation algorithm, but I remember this being quite a significant difference.

[cyl19970726]

Thank you for your response; it was very helpful. I’m currently integrating STIR into Plonky3 and plan to incorporate WHIR in the next phase.

[WizardOfMenlo]

Ah very nice! When you do, there is a significant verifier optimization for STIR that I have not implemented yet. When you get around writing the verifier, let me know and I can explain.

[cyl19970726]

I’m currently integrating the prover and may start on intergating STIR verifier into Plonky3 next week. With your explanation of this optimization, I believe I can implement it in this repo at first.