Why are timesteps a power of 2?

[jimouris]

I am reading the whitepaper and I am trying to understand why in this implementation the timesteps (-t flag) should be declared as a power of 2.

In the paper, if I haven't missed anything, no such thing is mentioned.

"α is the result of executing C for T steps on (public) input x"

Thanks, Dimitris Mouris

[elistark]

Good question: the STARK paper does use powers of 2, see, e.g., Definition B.5 there (T=2^t-1). Why? Because succinctness: if you want verifier to be able to argue algebraically about long computations, it's better to use evaluation domains that are elements of a (coset) of some group that is "FFT-friendly". It can be a multiplicative group of size 2^k, integer k (as is often done when working with SNARKs) and it can be an additive group, as used in the STARK paper you refer to.

Best Eli

On Thu, Nov 7, 2019 at 11:23 PM Dimitris Mouris notifications@github.com wrote:

I am reading the whitepaper https://eprint.iacr.org/2018/046.pdf and I am trying to understand why in this implementation the timesteps (-t flag) should be declared as a power of 2.

In the paper, if I haven't missed anything, no such thing is mentioned.

"α is the result of executing C for T steps on (public) input x"

Thanks, Dimitris Mouris

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/elibensasson/libSTARK/issues/23?email_source=notifications&email_token=AJQNVP2KZHQZEZF2MJRDCW3QSSBNXA5CNFSM4JKOA5R2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HXXIITQ, or unsubscribe https://github.com/notifications/unsubscribe-auth/AJQNVP24WWYWFNH2Y3E4WMLQSSBNXANCNFSM4JKOA5RQ .

[jimouris]

Got it, thank you!