How we got here, our DNA, and where we’re going.
This article is based on a talk by Prof. Eli Ben-Sasson, a co-founder and president of StarkWare, at the StarkWare Sessions ’23 that were held in Israel recently.
How did we get here?
The STARK technology is based on proofs, and more precisely: proofs of integrity. The great C.S. Lewis beautifully defined integrity as “doing the right thing, even when no one is watching.” The goal is integrity, and proofs are a means to that end. STARKs leverage mathematics to assure integrity, ensuring that computation is done the right way, even if no one is watching.
The concept of using a single reliable computer to monitor a group of unreliable supercomputers was introduced in a 1991 article by László Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy. This “PCP” technology employs mathematics to monitor and ensure the integrity of a large computation. Here is how it’s being done:
Computational claims can be transformed into a Sudoku-style puzzle with constraints that interlace and overlap in a variety of ways. Each claim leads to a unique puzzle. The entity making the claim is known as the Prover, and the proof it submits amounts to a filled sudoku puzzle (see image below). The hallmark of a correct claim is that the submitted solutions satisfies each and every of the myriad constraints associated with the puzzle. And the most magical property of these PCPs (and the part that’s hardest to establish, mathematically) is that for false claims, any submitted solution will violate at least 99% of the sudoku constraints. The Verifier, a trustworthy but weak computer, knows the unique puzzle which needs to be solved to prove the claim, but instead of reading the Prover’s solution in its entirety, it takes a random “poll” and checks a random constraint of the submitted solution (the proof) and decides whether to accept or reject the claim based on whether this single random constraint is satisfied. Given the stark difference between solutions of true claims (which satisfy all constraints) and solutions of false claims (that cannot satisfy more than 1% of constraints), the elementary properties of statistics and polling can be used: by sampling, say, 6 random constraints and checking whether they are valid, the Verifier will know with near-sure certainty, up to an error probability that is at most 1 in a trillion (1,000,000,000,000), whether the computation was carried out with integrity. The final magical property needed for scalability is that even though the sudoko puzzle is as large as the number of steps in the computation, the verifier can sample, read and check a random constraint in it extremely fast. In fact, the amount of computation required for this is exponentially smaller than the size of the sudoku puzzle!
Enter STARK
PCP technology was developed in the 1990s, and STARK is a tweaked version of it. One key difference is that instead of generating and filling a single Sudoku puzzle, this process, of generating sudoku puzzles and having the prover fill them up, is repeated a few times. The Verifier then samples a single constraint from this multi-dimensional Sudoku challenge and based on it decides whether to accept or reject the claim. By using STARKs, the little guy can check and make sure some huge corporation, monopoly, or government is functioning correctly.
An important part of this story is where this technology could be used in the real world. In the conventional world, it’s hard to find a setting in which a single reliable weak computer is needed to monitor a herd of untrusted and possibly unreliable supercomputers. Where do we find the scenario of a single reliable weak PC that everyone trusts?
Enter Blockchain
A crucial category of innovation beyond cryptography and computation emerged in 2008: Satoshi’s work in 2008 changed everything.
Throughout history, transactions used to be conducted in a peer-to-peer manner with cash and goods, but today they are done through centralized platforms like Apple Pay, Visa, and Swift. Users need to trust these platforms to handle their transactions fairly.
Bitcoin revitalized the peer-to-peer nature of money exchange by eliminating the need for a trusted intermediary. Ethereum took this concept further allowing for the creation of generic programs that form the economic fabric of society.
There’s a convergence of two lines of innovation. On one hand, we have PCP (and STARKs) that enable a single weak but reliable computer to enforce integrity on a larger scale. On the other hand, we have a blockchain, which is a highly reliable computer that uses math to verify computations on a large scale. This led to the meaningful realization that blockchains align perfectly with the math that enforces integrity.
Computational Integrity — applications to Bitcoin (ZCash pre-history)
Enter StarkWare
In 2018, StarkWare pioneered the use of STARK validity proofs to address Ethereum’s scalability issues. The uneven distribution of computation between the off-chain Prover and on-chain Verifier unlocks mass scalability. The off-chain Prover processes large batches of transactions and generates a STARK proof, while the Verifier checks the proof on-chain with minimal computation. This allows for off-chain processing of large computations while ensuring their integrity on-chain with minimal overhead.
Since then, StarkWare has achieved several milestones:
- StarkEx, based on a SaaS business model, boasts the largest L2 scale on Ethereum and has been in production since June 2020.
- Cairo — The need to write programs via a general (Turing complete) programming language that would be safe and efficient for developers to write in, but at the same time lead to efficient STARK proofs for the execution of these programs, led to the creation of Cairo. It is the most efficient programming language for leveraging validity proofs, which are essential for scalability.
- Starknet is the first decentralized network in production that allows writing of custom logic, similar to Ethereum.
What is in STARKs DNA?
- Head in the sky, boots in the mud: We follow a two-pronged approach. We love tech, math, and innovation and we focus on delivering our products.
- Excellence begets excellence: The biggest achievement of StarkWare is the level of excellence its giga-brains strive for.
- Excellence begets magnanimity: We embrace and support other teams pushing the boundaries of Ethereum and/or STARKs.
- “To go fast, go alone. To go far, go together.” StarkEx, Cairo, and even Starknet were all initially done in-house, and they were shipped fast. Next, we strive to make our products open-sourced and decentralized, and focus on making STARKs a public good.
https://twitter.com/EliBenSasson/status/1628129930591539228?s=20
Where are we going?
Starknet already has a rapidly expanding bustling ecosystem with ~1000 developers and 400+ GitHub repositories.
Espousing the mindset of “To go fast, go alone. To go far, go together”, StarkWare will:
- Make Starknet a permissionless, decentralized validity rollup governed by the Starknet Foundation.
- Focus on decentralizing Starknet’s various moving pieces like the Prover, the Sequencer and governance.
To benefit from the power and scalability of STARKs, learn the open-souce Cairo and write your programs in that way.
