Last FRI polynomial is not normalized

[Sword-Smith]

The last FRI polynomial is not added to the proof stream in a normalized manner, making the degree-check (in Triton VM/TASM) of the last round harder than it should be. Currently, we do:

    fn send_last_polynomial(&mut self) {
        let last_codeword = &self.rounds.last().unwrap().codeword;
        let last_polynomial = ArithmeticDomain::of_length(last_codeword.len())
            .unwrap()
            .interpolate(last_codeword);
        let proof_item = ProofItem::FriPolynomial(last_polynomial.coefficients);
        self.proof_stream.enqueue(proof_item);
    }

Which adds a list of coefficients to the proof stream which will have trailing zeros. A potential solution is to change the above-function to:

    fn send_last_polynomial(&mut self) {
        let last_codeword = &self.rounds.last().unwrap().codeword;
        let mut last_polynomial = ArithmeticDomain::of_length(last_codeword.len())
            .unwrap()
            .interpolate(last_codeword);
        last_polynomial.normalize();
        let proof_item = ProofItem::FriPolynomial(last_polynomial.coefficients);
        self.proof_stream.enqueue(proof_item);
    }

This, combined with a test that the last polynomial is always shared in its normalized form, should solve the problem. The alternative is to write a degree-checker in Triton VM assembly but that seems needlessly complicated and will also lead to larger-than-necessary proofs.

[jan-ferdinand]

How about adding BFieldCodec support for Polynomial instead? That seems like the more general approach to me.

[Sword-Smith]

How about adding BFieldCodec support for Polynomial instead? That seems like the more general approach to me.

That might very well be a more robust solution, yes.

[Sword-Smith]

Superseeded by 7367c677a53487825d7afc101066a16a83ae7227