STARKs have recently received quite a lot of attention due to their small proof size and supposedly simple assumptions. The paper introduction itself seems to mainly state that their construction is solely based on collision-resistant hash functions. However, further down in the paper they seem to require some conjectures related to reed-solomon codes (see conjectures B.16 and B.17 as well as Appendix D.3).

Can somebody explain these conjectures in simple words? Are these conjectures crucially required for the asymptotic proof size that STARKs achieve or are they only required for some practical performance improvements?

  • $\begingroup$ Did you see the "conservative" soundness error bound they gave for their ALI IOP? (It's stated in B.15 item 3, and proven later on in D.2.2.) $\endgroup$ – Daniel Lubarov Mar 20 '19 at 21:10
  • $\begingroup$ So what does conservative mean here? Is it just based on CRHFs? $\endgroup$ – Cryptonaut Mar 21 '19 at 16:32
  • $\begingroup$ AFAICT their whole "STIK" construction is information theoretically secure in the IOP model, ignoring those non-essential conjectures. It seems they only rely on CRHFs to transform a "STIK" to an "iSTARK" (essentially Killian's argument scheme), and rely on random oracles to transform an "iSTARK" to an "nSTARK". I could have missed something though, so hopefully someone else can post an authoritative answer. $\endgroup$ – Daniel Lubarov Mar 21 '19 at 19:44
  • $\begingroup$ What do you mean by non-essential conjectures? What is their exact purpose? What do they get without these conjectures in terms of results? $\endgroup$ – Cryptonaut Mar 21 '19 at 21:29
  • $\begingroup$ It seems like a practical optimization. We still get polylogarithmic argument lengths without those conjectures, since that's implied by Theorem 3.5. Notice how their proof of Theorem 3.5 builds on Lemma B.6, an IOP with proven soundness, rather than Lemma B.7, an IOP with conjectured soundness based on Conjecture B.17. $\endgroup$ – Daniel Lubarov Mar 22 '19 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.