Original: STARK: Endgame
Translation and proofreading: “Starknet Chinese Community”
This blog post is based on a presentation by Professor Eli Ben-Sasson, StarkWare Co-Founder and CEO, at the StarkWare 2023 conference in Israel.
How did the achievement come about?
STARK technology is based on proofs, more precisely proofs of integrity. Professor CSLewis once defined integrity as “doing the right thing even if there is no supervision”. Integrity is the goal, and proof is the means to get there. STARK uses mathematics to ensure integrity, ensuring that computations are performed in the correct manner, even in the absence of supervision.
In a 1991 paper by László Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy, a reliable computer was used to monitor a group of unreliable supercomputers. This Probabilistically Checkable Proofs (PCP) technique uses mathematics to monitor and ensure the integrity of large computations, as explained below.
Computational statements can be transformed into Sudoku-like puzzles, whose constraints overlap in various ways. Each claim leads to a unique puzzle, and the entity making the claim is called a prover, and the proof it submits is equivalent to a filled-in Sudoku puzzle (as shown in the figure below). Correctly claiming a submitted solution requires satisfying various constraints associated with the puzzle, and one of the most amazing properties of PCP (and the hardest part to determine mathematically) is that for incorrect calculation claims, any submitted solution would violate at least 99% of the Sudoku puzzle constraints. A verifier is a reliable but less computationally powerful computer that knows the hard problem that needs to be solved in order to prove the truth of a claim. But instead of reading the solution submitted by the prover in its entirety, the verifier randomly “samples” a constraint and checks whether the condition is satisfied, thus deciding to accept or reject the solution. Given the apparent difference between true claims (all conditions met) and false claims (failure to meet more than 1% of conditions), principles of statistics and sampling can be used for verification. For example, the validator can randomly pick 6 constraints and check whether they are satisfied. This allows the verifier to be almost certain that the computation is complete (the probability of error is controlled to one in a trillion). The final magical property required for scalability is that validators can sample, read, and check random constraints very quickly, even if the number of steps in the Sudoku puzzle and computation is enormous. In fact, these required computations are far less than the size of a Sudoku puzzle!
Walk into STARK
STARK is an adapted version of PCP technology developed in the 1990s. A key difference between the two is that STARK does not simply generate and fill in Sudoku puzzles, but repeats several times in the process of generating Sudoku puzzles and filling in validators. The validator then samples a constraint from this multidimensional Sudoku challenge, judges and decides whether to accept or reject the claim. By adopting STARK technology, ordinary people can also check and ensure the normal operation of some large companies, monopolies or governments.
The focus here is on which practical scenarios this technology can be applied in the future. Traditionally, it is difficult to find a scenario where a reliable but low computing power computer is required to monitor a group of unreliable and untrusted supercomputers. Where can we find reliable low computing power, computer scenarios that everyone trusts?
Into the blockchain
An innovative category beyond cryptography and computers was born in 2008: Satoshi Nakamoto’s paper “Bitcoin, a peer-to-peer electronic cash system” published in 2008 completely revolutionized the blockchain field.
Across the historical process, transactions used to be done in a point-to-point way of cash to goods, but now transactions are completed on centralized platforms such as Apple Pay, Visa, and Swift. Users need to trust that these platforms will process transactions transparently and openly.
Bitcoin removes trust in middlemen and restores the peer-to-peer nature of monetary transactions. Ethereum, in turn, advances this concept, allowing general programs for building socio-economic structures.
The two innovative technology routes are constantly integrated. On the one hand, we use a single low-calculation but reliable computer to realize PCP (STARK technology) for large-scale computational integrity; on the other hand, we use the blockchain as a highly reliable computer, relying on mathematics to verify large-scale calculations. And deeply realized: the perfect combination of blockchain and mathematics to achieve integrity.
Video: Computational Integrity – Applications of Bitcoin (Early background on ZCash)
Walk into StarkWare
In 2018, StarkWare took the lead in proposing the use of SATRK validity proof to solve the scalability problem of Ethereum. Off-chain provers and on-chain validators compute differences, unlocking massive scalability. Off-chain provers process batches of transactions and generate STARK proofs, and validators check on-chain proofs using minimal computation. It supports the processing of large-scale calculations under the chain while ensuring the integrity of the chain with the lowest cost.
Since then, StarkWare has achieved milestone after milestone:
- StarkEx, based on the SaaS business model, has been in production since June 2020, becoming the largest L2 scale on Ethereum.
- The reason for the birth of Cairo: A general-purpose (Turing-complete) programming language for writing programs is needed, which not only meets the security and efficiency of developers, but also introduces efficient STARK proofs for program execution. As the most efficient proof-of-validity programming language, Cairo’s importance to scalability is self-evident.
- Starknet, similar to Ethereum, was the first production-ready decentralized network that allowed writing custom logic.
What is the spirit of STARK?
- Foot on the loess, face the blue sky: we take a two-pronged approach. The StarkWare team loves technology, mathematics, innovation, and is deeply rooted in product excellence.
- Excellence Makes Excellence: StarekWare’s number one achievement is its deep talent base.
- Excellence and generosity: We welcome and support other teams pushing the limits of Ethereum or STARK.
- “One person travels fast, everyone travels far”: Initially, StarkEx, Cairo and even Starknet were all completed internally, and they moved quickly. In the next step, we will strive to achieve open source and decentralization of products, and strive to make STARK technology a public product.
the way of the future
The Starknet ecological construction is expanding rapidly, with about 1,000 developers and over 400 Github code resource libraries.
StarkWare will implement the theme of “one person travels faster, everyone travels far”:
- Let Starknet be a permissionless, decentralized effectiveness scaling solution managed by the Starknet Foundation.
- Focus on Starknet decentralization of various types of components, such as provers, orderers and governance.
Users who are interested in the powerful functions and scalability of STARK are welcome to learn the open source Cairo language and experience the fun of writing programs.