StarkWare
Published in

StarkWare

A Framework for Efficient STARKs

Combining probabilistic proofs and hash functions

Our goal: scalable transparent arguments

We wish to construct a STARK, which is a cryptographic proof (aka an “argument”) that is both scalable and transparent. Our first post describes this goal in detail, which we now summarize.

Figure 1: Diagram of a STARK.
  • Transparency: the global parameters of the cryptographic proof system, used to produce and validate proofs, have no trapdoors. This is in contrast to proof systems that rely on a trusted party to sample public parameters based on secret information, which can be used as a “trapdoor” to compromise the security of the proof system.

Roadmap for this post

Known STARK constructions combine two ingredients:

  1. a cryptographic hash function such as SHA-256 or Keccak.
  • Second, we explain why the Micali construction provides transparency and scalability.
  • Third, we describe the notion of Interactive Oracle Proofs (IOPs), which generalizes PCPs and enables designing much more efficient protocols. We also explain how the arithmetization and low-degree testing protocols in prior posts are IOPs.
  • Finally, we mention the BCS construction, an extension of the Micali construction that uses the more general notion of IOPs instead of PCPs. Efficient STARKs, including those that we use, are obtained via the BCS construction.

Cryptographic proofs from PCPs, via the Micali construction

In this section we introduce probabilistically-checkable proofs (PCPs), a type of proof system that involves a random local check to a long proof. Then we explain how a PCP can be combined with lightweight cryptography to obtain a STARK. This construction comes from a paper of Silvio Micali (building on prior work of Joe Kilian).

Figure 2: Diagram of a probabalistically checkable proof (PCP).
Figure 3: Diagram of the Micali construction, which uses a cryptographic hash function to securely pre-sample a PCP.

Transparency comes from the cryptography

An important feature of the Micali construction is that the only cryptography needed for producing or validating a short proof 𝛑 is a cryptographic hash function H (e.g., SHA-256 or Keccak). The choice of H is thus the only “global parameter” that all users of the proof system need to know, and this choice can be made via public information. This means that cryptographic proofs obtained via the Micali construction are transparent.

Scalability comes from the probabilistic proof

Another important feature of the Micali construction is that the time to produce/validate the short proof 𝛑 is close to the time to produce/validate the long proof 𝚿. This is simply because the needed cryptographic operations are inexpensive when compared to the PCP operations. We thus learn that efficiency in the Micali construction is essentially determined by the efficiency of the underlying PCP. In particular, if the PCP is scalable (producing 𝚿 takes time quasilinear in T whereas validating 𝚿 is exponentially faster) then the Micali construction yields a scalable cryptographic proof. Constructions of scalable PCPs are known (see this paper).

IOPs: a new notion of probabilistic proof

Efficient STARKs are based on a type of probabilistic proof system known as interactive oracle proofs (IOPs), which was introduced in 2015. Informally, a prover and a verifier engage in an interactive protocol where in each round the verifier sends some randomness 𝛔ᵢ to the prover, and the prover replies with a long proof 𝚿ᵢ. At the end of the interaction, the verifier performs a random local check on all the long proofs (𝚿₁,𝚿₂,…) sent by the prover throughout the interaction. See Figure 4 for a diagram. Note that a PCP is simply a “non-interactive IOP”, and thus is a restricted case.

Figure 4: Diagram of an interactive oracle proof (IOP). This notion extends the notion of a PCP (cf. Figure 2).

Prior posts describe an efficient IOP

We now explain how our prior posts on arithmetization and low-degree testing actually described an efficient IOP. In Figure 5 we provide a diagram of this IOP. The first phase of the protocol is arithmetization, which transforms the given CI statement (𝐀,x,y,T) into a problem that involves establishing degree bounds on certain polynomials. Second phase is low-degree testing, which solves this latter problem. We summarize the protocol’s workflow.

Figure 5: Diagram of the IOP protocol described in prior posts.

Cryptographic proofs via the BCS construction

Efficient STARKs are obtained via the BCS construction a method that combines an IOP with a cryptographic hash function H in order to obtain a cryptographic proof. This method is an extension of the Micali construction, and it retains its features (of transparency and scalability) that we discussed above. We do not describe the BCS construction in this post, and only remark that it can be viewed as applying the Micali construction at each round of an IOP and putting each round’s commitments in a hash chain (which keeps the rounds in order).

Conclusion

In this post we have explained that efficient STARK constructions are obtained by combining efficient IOPs (a type of probabilistic proof) and cryptographic hash functions. The IOP confers the STARK its scalability, while the hash function confers the STARK its transparency. Different STARK constructions differ in the underlying IOPs, and we have explained how our prior posts have described the components of the IOP protocol used in our STARK construction.

--

--

Developing the Full Proof Stack for STARK

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store