I have a question about the generator and primitive _nth_root, it says the code also needs to supply the user with a generator for the entire multiplicative group, What is the entire multiplicative group, is it Fp*? If the root is the generator of Fp*, how to derive the primitive_nth_root? why is the 407 omitted in the primitive_nth_root function? Can you tell me, thanks

  def generator( self ):
        assert(self.p == 1 + 407 * ( 1 << 119 )), "Do not know generator for other fields beyond 1+407*2^119"
        return FieldElement(85408008396924667383611388730472331217, self)
        
    def primitive_nth_root( self, n ):
        if self.p == 1 + 407 * ( 1 << 119 ):
            assert(n <= 1 << 119 and (n & (n-1)) == 0), "Field does not have nth root of unity where n > 2^119 or not power of two."
            root = FieldElement(85408008396924667383611388730472331217, self)
            order = 1 << 119
            while order != n:
                root = root^2
                order = order/2
            return root
        else:
            assert(False), "Unknown field, can't return root of unity."

Hey I am confused about these lines in stark.py in prove() function

# symbolically evaluate transition constraints
point = [Polynomial([self.field.zero(), self.field.one()])] + trace_polynomials + [tp.scale(self.omicron) for tp in trace_polynomials]
transition_polynomials = [a.evaluate_symbolic(point) for a in transition_constraints]

Isn't the point bigger array than transition_constraints have variables? And thus these omicron variables are not being assigned at all?

Hello! Been studying STARKs, found this is in Part 1 of the Anatomy of a STARK, in the Cryptographic Compilation with FRI section.

Is the non-interactive proof system described here suppose to be a SNARK and not a STARK?

Thank you very much for writing this series of tutorials. It's a great study material for me. In the process of learning I had some small questions:

In Part 1: STARK Overview, here's what got me wondering:

Interpolation and Polynomial IOPs: …… At this point the AIR constraints give rise to operations polynomials that send low-degree polynomials to low-degree polynomials only if the constraints are satisfied. The verifier simulates these operations and can thus derive new polynomials whose low degree certifies the satisfiability of the constraint system, and thus the integrity of the computation.

1. what do 'operations polynomials' stand for ? Or maybe I got something wrong with my sentence break...?
2. 'send low-degree polynomials to low-degree polynomials' means what ? After having the AIR constraints, I think it's the time for getting 'quotients' , what do the two 'low-degree polynomials' here refer to respectively?

I would appreciate it if you could answer my questions above.

Disclosure: Orbis Labs who funded the paper are also funding me.

Link: https://eprint.iacr.org/2022/1216

It was very helpful for me in order to understand FRI.

Polynoms representing an exactly horizontal line have degrees < 1:

• for f(x) = n with n != 0, degree is 0
• for f(x) = 0 degree is -1

The test_colinearity function incorrectly reported points on such polynoms as not being part of the same line. This is fixed by adjusting the test to account for the cases with degrees < 1.

Even though both names are somewhat generic, not very descriptive, and technically correct, I think changing the figures' term “composition polynomial” to “transition polynomial” makes sense because

1. they are visually and semantically between the “transition constraints” and the “transition quotient(s)”, and
2. they are already called “transition polynomials” in the text (where, in fact, the term “composition polynomial” does not appear).

The boundary quotient is found by dividing the trace interpolant minus the boundary interpolant with the boundary zerofier, so to find the resulting degree, one should subtract the degree of the boundary zerofier from the degree of the trace interpolant.

When reading index folding section of the chapter 3: FRI (https://aszepieniec.github.io/stark-anatomy/fri#index-folding) I am having a hard time making sense of the chart, the index folding half.

I'd say the bottom two levels should be blue (as the points have been chosen from the blue parts in the malicious hybrid codeword)

Does this make sense?

Thanks for putting this together!