A Framework for Efficient STARKs

Combining probabilistic proofs and hash functions

StarkWare
Apr 17 ยท 12 min read

Our goal: scalable transparent arguments

Figure 1: Diagram of a STARK.

Roadmap for this post

Cryptographic proofs from PCPs, via the Micali construction

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

Scalability comes from the probabilistic proof

IOPs: a new notion of probabilistic proof

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

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

Cryptographic proofs via the BCS construction

Conclusion

StarkWare

Developing the Full Proof Stack for STARK

239

239 claps
StarkWare

Written by

StarkWare

bringing scalability and privacy to a blockchain near you

StarkWare

StarkWare

Developing the Full Proof Stack for STARK