How STARKs Work

STARKs are a class of cryptographic proof systems. They can deliver scale and privacy, and they are post-quantum secure. In this multi-part article, I’ll do my best to explain how STARKs work in a simplified manner for non-mathematicians. Note: what I’ll describe is not a theoretical possibility, but a battle-tested technology used by StarkWare since 2018.

First, housekeeping:

Important notes before we dive in:

1. I will focus mainly on how we generate the STARK proof.
2. I will use simplified examples to explain what is actually a very complicated mathematical process. Naturally, there will be parts of the process that I will skip, and some of the analogies will not be perfect. This leads me to the 3rd note:
3. I really encourage *anyone* who has done a deep dive into this topic to offer their best explanation of how STARKs work. There’s no such thing as too much education!
4. STARKs can be used outside the blockchain world. However, for our purposes, this article will describe how STARKs work when scaling blockchains.

This is a long explanation, so get yourself a cup of coffee, stretch your legs, and massage your eyes before we begin. ☕

Ok, let’s go.

At a high level:

(You may already be familiar with the basic information about Blockchain’s scaling challenge and what STARKs are used for in that context. If that’s the case, feel free to skip to Generating a STARK proof.)

The Problem: Blockchains Can Be Slow

To understand the solution STARKs offer, we first need to understand one of the problems they solve: Scaling.

Decentralized blockchains enable users to conduct digital activities and store their data onchain. In a decentralized chain, all parties that operate it check and verify every interaction. Decentralized blockchains like Bitcoin and Ethereum are secure because everyone checks all the data. For example, if Alice sent funds to Bob, every node in the network re-executes this transaction and verifies its details, as follows:

• Did Alice have enough funds?
• Was her signature valid?
• Did balances update correctly?
• Etc.

Having everyone verify this data is great for security, but requiring every node to re-execute every transaction is terrible for scalability. Here’s an analogy:

Imagine a school where 30 students are taking a math test. Normally, one teacher grades the exams, and everyone trusts that grade. But what if that teacher is not trustworthy? What if other teachers suspect he has a reason to give fake grades, for example, he was offered money to give the highest score to a specific student?

In that scenario, the other teachers would all want to grade all the exams themselves to ensure their results match the given grades. Imagine the burden. It would take too much time and energy. On a larger scale, it simply would not work, not with 30 students, and certainly not with 300 or 3,000.

The Solution: Provide proof of validity

Instead of having all teachers re-check all exams, or having thousands of computers re-execute all transactions, what if there was a way to have one party do most of the work, and prove to the others that it was done correctly? If the other parties could run a simple check to ensure the validity of transactions and the integrity of their processing, that would save them a huge amount of work, while allowing them to commit to the resulting data, without compromising security. That’s what STARKs enable.

There are two parties involved in the STARK protocol:

1. The Prover: a computer that processes transactions through extremely complex and lengthy computations, and generates a STARK proof.
2. The Verifier: a piece of software that checks the Prover’s work in a few steps.

When applied to blockchains, and once the proof is verified, the system can be updated with the data resulting from the processed transactions.

With STARKs, the Prover can be anyone, including someone you don’t trust: a nation-state, a corporation, an anonymous individual, or even Darth Vader. They cannot bend the math for their malicious intentions. We don’t trust Darth, we trust the math, and we each run this math when we run a Verifier.

Sampling instead of re-executing the computation

Verifying the STARK proof does not require re-executing all processed transactions. The proof is built in a way that allows the Verifier to run a relatively small computation to check if there are any indications of error or invalid data. If there aren’t any, the Verifier can confirm that all processed transactions are valid.

STARKs make this possible through math. The mathematical protocol mixes and amplifies the data, so even the smallest error affects every part of the proof. This ensures that any invalid data will become detectable, much like a single drop of blood reveals key information about our health.

How efficient is this process that lets us verify the Prover’s work instead of having all nodes of the network redo it? If we are processing 1 million transactions, the Verifier can check the STARK proof with the same amount of computation needed to execute 6 transactions.

So how is it done? How do STARKs process 1 million transactions, roll them into a proof that can be verified with the amount of work needed to process 6 transactions, and still ensure no errors or maliciousness remain undetected? Read Part 2.

• If you want to go deeper into how zero-knowledge and blockchain can shape our society and our future, I have a new book coming out on exactly that. You can check it out here.