Inclusive Accountability on Blockchains
The integrity of blockchains is premised on inclusive accountability: all citizens of the world are invited to verify the computational integrity of the blockchain. None is excluded. This creates two problems:
- Scalability: Scaling throughput to ever growing demand would necessarily exclude some from verifying integrity, due to their limited computational resources.
- Privacy: Without cryptographic blinding of information, all blockchain transactions are publicly exposed, which is unacceptable to businesses and individuals alike.
Theoretical Computational Complexity to the Rescue
Starting in the 1980’s and through the 1990’s a brilliant line of theoretical works on Interactive Proofs (IP), Zero Knowledge Proofs (ZKP) and Probabilistically Checkable Proofs (PCP) have shown how to completely resolve both scalability and privacy issues. But, as the famous saying goes, “In Theory, there is no difference between theory and practice. Practically speaking, there is”. Early constructions were, practically, unusable.
STARKs as Culmination of the “Theory to Practice” Journey
Several paths emerged in the new millennium to reach concrete efficiency, mostly to solve the privacy problem. The most prevalent ones are based on number theoretic cryptographic primitives like bilinear pairings over elliptic curves (SNARKs and Bulletproofs are two notable examples).
The path that STARKs pursue is older (or “classic”) – relying on battle-tested hash functions as their sole cryptographic building block. To bridge the chasm to practicality, STARK relies on recent breakthroughs – quasi-linear PCPs, interactive oracle proofs (IOPs) and fast algebraic local coding protocols like FRI.
As a result, at scale the STARK prover and verifier are fastest in class (outperforming all number-theoretic constructions) and reach vastly greater scale than competitors while relying on fewer and safer cryptographic assumptions.