STARK Math: The Journey Begins

Part I

StarkWare
StarkWare
Feb 5 · 9 min read
Photo by Joanna Kosinska on Unsplash

I. Intro

Computational Integrity (CI) is a fundamental property that underlies commerce. In simple terms, it means that the output of a certain computation is correct. CI is what allows us to trust an account balance presented to us, or the bill at a store. This post will dive into how permissionless blockchains achieve CI without requiring trust, the dramatic price they pay for this in terms of scalability and privacy, and how STARKs can save the day.

II. Trust vs. Verification

“Old World”: Trust, or Delegated Accountability

Financial systems (banks, brokers, exchanges, etc.) need to operate with integrity to serve their societal functions. What mechanisms incentivize them to operate with integrity? The “old world” assumes trust as a proxy for integrity. We trust banks, pension funds, etc., to operate honestly. Let’s go down the rabbit hole and examine the basis for this trust, ignoring the “integrity theater” — the tall buildings and fancy suits — set to impress us. From a purely rational and utilitarian perspective, the thing that prevents the financial system from seizing all our funds is the threat of social disgrace, jail, and fines. There’s also a carrot — reputation, which attracts future customers and generates future profits. By signing on financial statements with their names, people in the “old world” stake their personal freedom, existing and future finances as a collateral for integrity, and we, the public, base our trust on this arrangement. The verification of this integrity is delegated to experts like accountants, auditors, and regulators. We will call this Delegated Accountability. It’s not a bad system: it’s been serving modern economies faithfully for quite some time.

“New World”: Verify, or Inclusive Accountability

Blockchains offer a more direct way to reach integrity, captured by the motto “Don’t Trust, Verify”. This “new world” does not require an integrity theater, it doesn’t rely on accountants, nor do its developers and network maintainers stake their personal freedom to gain public trust. Integrity is guaranteed by Inclusive Accountability: a node with a standard computational setup (a web-connected laptop) should be able to verify the integrity of all transactions in the system.

  • Scalability: Demanding that the system be accountable to a standard laptop means it cannot scale up by simply moving to bigger computers and larger bandwidth. This leads to a severe bound on the throughput of the system.

III. Proof Systems

Proof Systems started with the introduction of the Interactive Proof (IP) model by Goldwasser, Micali, and Rackoff in 1985. Interactive proofs are protocols that involve two kinds of entities: a prover and a verifier, who interact over a number of rounds by sending messages. The prover and verifier have conflicting objectives: the prover wants to convince the verifier of the integrity of a certain computation, and the verifier is a suspicious gatekeeper entrusted by the public with the task of distinguishing between truisms and falsities. The prover and verifier communicate interactively, taking turns in sending messages to one another. These messages depend on the statement being proved, on prior messages, and may also use some randomness. On the prover side, randomness is used to achieve zero knowledge and on the verifier side randomness is needed to generate queries to the prover. At the end of the interactive process the verifier outputs a decision, to either accept the new state or reject it.

  • Soundness: If the prover doesn’t know how to change the state from A to B, then the verifier will notice an inconsistency in the interaction and reject the suggested state transition. There remains a tiny false-positive probability, i.e., a probability of the verifier accepting an invalid proof. This probability is a system security parameter which can be set to an acceptable level like 1/(2¹²⁸), similar odds to winning the powerball five times in a row.

IV. STARK

By now there are quite a few theoretical constructions of proof systems, along with implementations. Some are deployed in cryptocurrencies, like the SNARKs used by Zerocash/Zcash, and Bulletproofs (BP) deployed in Monero. (For general information on proof systems go here.) What distinguishes STARKs is the combination of the following three properties: scalability (the S in STARK), transparency (the T in STARK), and lean cryptography.

Scalability — Exponential Speedup of Verification

Scalability means that two efficiency properties hold simultaneously:

  • Scalable Verifier: The verifier’s running time is polynomial in the logarithm of naive replay time. In other words, the verifier’s runtime is exponentially smaller than simply replaying the computation (recall that ‘replay’ is the current blockchain method to achieve Inclusive Accountability).

Transparency: with Trust toward None, with Integrity for All

Transparency means² there is no trusted setup — there is no use of secrets in the setting up of the system. Transparency offers many benefits. It eliminates the parameter setup generation procedure which constitutes a single point of failure. The lack of a trusted setup allows even powerful entities — big corporations, monopolies and governments, which control the “old world” financial system — to prove CI and gain public acceptance of their claims because there’s no known way to forge STARK proofs of falsities, even by the most powerful of entities. On a more tactical level, it makes it much easier to deploy new tools and infrastructure and change existing ones without a need for elaborate parameter-generation ceremonies. Most importantly, transparency aligns well with the “new world” that demands Inclusive Accountability under no trust assumptions. To paraphrase Abraham Lincoln, transparent systems allow to operate with trust toward none, with integrity for all.

Lean Cryptography: Secure & Fast

STARK has minimal³ cryptographic assumptions underlying its security: the existence of secure cryptographic and collision-resistant hash functions. Many of these primitives exist today as hardware instructions, and the lean cryptography leads to two more benefits:

  • Concrete Efficiency: For a given computation, the STARK prover is at least 10x faster than both the SNARK and Bulletproofs prover. The STARK verifier is at least 2x faster than the SNARK verifier and more than 10x faster than the Bulletproof verifier. As StarkWare continues to optimize STARKs these ratios will likely improve. However, a STARK proof length is ~100x larger than the corresponding SNARK and ~20x larger than BulletProofs.

V. Summary

We started by explaining the “new world” of permissionless blockchains, in which the motto is “Don’t Trust, Verify”. The principle of Inclusive Accountability demands that the integrity of the financial system be verifiable readily by anyone, as opposed to the Delegated Accountability of the “old world”. To allow blockchains to scale we need methods that allow for verification of computational integrity that are faster than naive replay.


StarkWare

Developing the Full Proof Stack for STARK

StarkWare

Written by

StarkWare

bringing scalability and privacy to a blockchain near you

StarkWare

StarkWare

Developing the Full Proof Stack for STARK