aszepieniec / stark-anatomy Goto Github PK

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

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.

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!

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?

For example, can I create transaction and make proof and check proof?
And how to use Your code in blockchain protocol?

Hi, I noticed that in the code/test_rpsss.py it has following line

print("size of signature:", len(sig), "bytes, or ", len(sig) / (2**13), "kB")

Which outputs

size of signature: 1309136 bytes, or  159.806640625 kB

Should it be divided by 2**10 because sig is an array of bytes? If so, the signature sizes in rescue-prime.md and faster.md would need to be updated.

Besides, thanks for the great tutorial!

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?