STARK Math: The Journey Begins

Part I

Feb 5, 2019 · 9 min read

StarkWare’s mission is to bring STARKs to the real world. This is the first in a series of posts explaining the theory behind STARKs and our implementation of it. We start lightly and will ratchet up the math in subsequent posts.

Image for post
Image for post
Photo by Joanna Kosinska on Unsplash

I. Intro

II. Trust vs. Verification

“Old World”: Trust, or Delegated Accountability

A new variant of the “old world” approach is the Trusted Execution Environment (TEE). A trusted hardware manufacturer (like Intel) produces a physical machine (like the SGX chip) that cannot deviate from the specified computation and signs correct states using a secret key known only to that physical machine. Integrity is now based on trust in the hardware and its manufacturer and on the assumption that it is impossible to extract secret keys from such physical devices.

“New World”: Verify, or Inclusive Accountability

The prevalent method to verify CI in permissionless blockchains is via naive replay: all nodes are asked to re-execute (replay) the computations that verify each and every transaction. Inclusive Accountability, in this naive form, leads to two immediate challenges:

  • Privacy: If everyone gets to inspect all transactions then privacy might be compromised. The absence of privacy deters businesses, as it means sensitive information may not remain proprietary. It also deters individuals, as it erodes human dignity.
  • 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.

Proofs systems (discussed next) are an excellent solution to both challenges. Zero Knowledge (ZK) proof systems are by now an established tool to address privacy in blockchains and explained excellently in several posts of Zcash [1, 2, 3]. Although ZK-STARKs offer Zero Knowledge, this post will not discuss it but focus on Scalability and Transparency (the S and T in STARK).

III. Proof Systems

A good analogy is the examination process practiced in a court of law when one party submits a claim and its counterparty questions its validity. For the claim to be accepted as true, the answers provided by the claimant (prover) to the examiner’s (verifier’s) queries must be consistent and valid. The examination process is expected to expose any mismatch between a statement and reality, and thus expose it as false.

We say that a proof system solves CI if when updating the system from state A to state B, the following properties hold:

  • Completeness: If the prover indeed knows how to change the state from A to B in a valid way then the prover will manage to convince the verifier to accept the change.
  • 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.

This pair of properties has a crucial implication to the principle of Inclusive Accountability discussed earlier. The verifier can accept the state transition suggested by the prover without making any assumptions about the integrity of the prover. In fact, the prover can run on faulty hardware, it can be closed source and it can be executed on a computer controlled by a malicious entity. The only thing that matters¹ is that the messages sent by the prover lead the verifier to accept the statement. If that is the case, we know that computational integrity holds.


Scalability — Exponential Speedup of Verification

  • Scalable Prover: The prover’s running time is “nearly-linear” in the time it would take a trusted computer to check CI by just re-executing the computation themselves and checking that the result matches what someone is claiming. The ratio of “overhead” (time needed to generate a proof / time needed to just run the computation) remains reasonably low.
  • 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).
Image for post
Image for post

Apply this notion of scalability to a blockchain. Instead of the current mode of verification by naive replay, imagine how things will look when a blockchain moves to verification by using proof systems. Instead of simply sending the transactions to be added to the blockchain, a prover node will need to generate a proof but thanks to the Scalable Prover its running time is nearly-linear in the running time of the naive replay solution. And the Scalable Verifier will benefit from an exponential decrease in its verification time. Furthermore, as blockchain throughput scales up, most of the effect will be shouldered by the prover nodes (which could run on dedicated hardware, like miners), whereas the verifiers, which would constitute most of the nodes in the network, would hardly be affected.

Let’s consider a concrete hypothetical example, assuming verifier time (in milliseconds) scales like the square of the logarithm of the number of transactions (tx). Suppose we start with 10,000 tx/block. Then the verifier’s running time is

VTime = (log₂ 10,000)² ~ (13.2)² ~ 177 ms

Now increase the blocksize a hundredfold (to 1,000,000 tx/block). The new running time of the verifier is

VTime = (log₂ 1,000,000)² ~ 20² ~ 400 ms

In words, a 100x increase in transaction throughput led only to a 2.25x increase in the verifier’s running time!

In some cases, the verifier will still need to download and verify availability of data, which is a linear-time process, but downloading data is generally much cheaper and faster than checking its validity.

Transparency: with Trust toward None, with Integrity for All

Lean Cryptography: Secure & Fast

  • Post-Quantum Security: STARKs are plausibly secure against efficient quantum computers.
  • 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

STARKs are a special kind of a proof system that offers scalability and transparency, and are based on lean cryptography. Their scalability and transparency allow inexpensive and trustless verification of the CI. This is the promise of STARKs and the mission of StarkWare.

Our next post will go a bit deeper into the mathematics of constructing STARKs.

Thanks to Vitalik Buterin and Arthur Breitman for reviewing drafts of this blog post.

Michael Riabzev & Eli Ben-Sasson
StarkWare Industries

¹Privacy preservation (ZK) does make demands on the prover code, to ensure prover messages do not leak information about the witness via side channels. But soundness requires no trust assumptions.

²Formally, a transparent proof system is one in which all verifier messages are public random strings. Such systems are also known as Arthur-Merlin protocols.

³This minimality of cryptographic assumptions holds for interactive STARKs (iSTARKs). Noninteractive STARKs (nSTARKs) require the Fiat-Shamir heuristic which is a different beast.


Developing the Full Proof Stack for STARK

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

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