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$ Commented Mar 20, 2019 at 21:10
  • $\begingroup$ So what does conservative mean here? Is it just based on CRHFs? $\endgroup$
    – Cryptonaut
    Commented Mar 21, 2019 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$ Commented Mar 21, 2019 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
    Commented Mar 21, 2019 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$ Commented Mar 22, 2019 at 1:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.