Scaling blockchains with STARKs

Deep Dive Into StarkWare

On September 30th, 2022. Eli Ben-Sasson, the president and co-founder of StarkWare, gave a TechTalk in Singapore hosted by StarkWare and Reddio, about the history of STARK (short for Scalable Transparent ARgument of Knowledge), how STARK works, and a brief explanation of how StarkEx/StarkNet works.

STARK（pre） History

Scalable Proofs

The pre-history of STARK began with the research of Scalable Proofs. To illustrate Scalable Proofs. Eli first came up with an example of the margin of error when polling an election. He mentioned that the margin of error is the same when the polling population is one million or one billion. That means the margin of error is independent of the sample size. According to Probabilistically Checkable Proofs (PCP) theorem, when validating the integrity of computation the margin of error is still independent of the sample size. That also means the costs to generate a poof for huge transactions will be almost the same as tiny little transactions. That is what we called “Scalable Proofs”.

Scalable Proofs can help in verifying Integrity. Integrity means doing the right thing even no one is watching. But the problem is, how can we trust other parties’ computation with complicated steps without any trust assumptions and re-calculations?

A paper from 1992 called Checking Computations in Polylogarithmic Time brought lights to this problem. The paper mentioned that with its mathematical method, a regular PC can monitor the integrity of a herd of supercomputers working. Or that is to say: “In this setup, a single reliable PC can monitor the operation of a herd of supercomputers working with possibly extremely powerful but unreliable software and untested hardware”.

That is a great invention. But you might ask why there isn’t any Stark system that doing this proof at that time? There are two answers for that:

Firstly, there are other ways besides blockchain to solve the integrity issues. Throughout the history of humankind, people have invented legal system and law enforcement system to make a short-term game into a long-term game. What this means is that when a person tries to break the integrity of something, that person needs to pay a very high price such as going to jail. Such potential heavy price ensures the integrity of the system, even though this is not Probabilistically Checkable.

Secondly, in 1992, the system was not scalable, which meant that the format of providing a proof was practically inefficient. If you had wanted to write the proof for 1+1=2, you would have needed more atoms in the solar system to do so, even if the atoms all could hold a single bit. This problem was solved gradually as the new papers written by Eli and some other scholars simplified the complexity of writing a proof.

Finally, in 2018, Eli and other Starkware co-founders came up with the technology to use the computation power of a single laptop to write such a proof.

That became the starting point of StarkWare, a company with the mission to validate integrity through math. To boost the growth of the StarkWare ecosystem, they invented ZK-STARK (Zero-Knowledge Scalable Transparent ARgument of Knowledge), FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity), Cairo, SHARP (SHARed Prover), Validium, Volition and more.

How a STARK works?

To understand how a STARK works, we need to know how to make a claim correct. That Claim is starting from state of accounts whose hash is x, I processed 10,000 Ethereum payments using program P, and the hash of the new system state is y.

In fact, this claim is what STARK does every single day. The math shows a way to arrange any set of statements into a sudoku-like set of constraints. This kind of puzzle only has a few numbers on the paper while leaving all the other spaces empty. Different x, y, P with different transactions will have different constraints. Then, the Prover submits solution (fill in the blank) to this set of constraints. And the Verifier samples and checks just one constraint. That is what we called a PCP.

The STARK is different to PCP by doing the sudoku-like challenges multiple rounds so that it’s in a three-dimensional state, thus saving more information.

There are some magical things that will happen when we use STARK to generate proofs. First, the Verifier doesn’t need to specify all the constraints. Second, the Verifier samples constraint succinctly (only needs one random constraint to verify the whole proof). Third, a good proof of true statement satisfies all constraints. Finally, every “proof” of bad statement must make 99% of constraints unsatisfied.

With all the features above, the STARK can first achieve scalable (which is the “S” in the acronym STARK) since the proving time equals log of the number of transactions. And the verification time equals the log of the number of transactions. What this means is that the average proving time and verification time is reduced as the total number of transactions goes up. For example, to verify 1 million transactions, a STARK system needs 6 steps. But with 1 billion transactions, it would only need 9 steps. This translates to a lower gas fee applied to each transaction.

Second, the STARK is transparent (which is the “T” in the acronym STARK) since all the verifier messages are public random coins. That means there are no trust setup nor keys, so even if a government can use STARK to show integrity to its citizens, it can't manipulate it. Simply put, they cannot break the laws of mathematics.

So how is STARK related to blockchain? To understand the connection, we need to first know about the Blockchain Paradox. Why is blockchain so slow when compared to a Visa credit card transaction? It all comes down to Computational Integrity. To ensure Computational Integrity, traditional financial institutions use large computer servers managed by governments and/or financial institutions to ensure citizens' trust in the system. This also means that users are not allowed to change the system. However, with blockchain technology, no one – no  government, no financial institution, no non-profit organization – no one is to be trusted. Therefore, everybody needs to verify all transactions to ensure integrity. This new method is more inclusive but it is very slow compared to the traditional, centralized way.

But the true question is, how can we increase scale on the blockchains while maintaining decentralisation simultaneously?

Currently, as a blockchain increases its scalability, some nodes will be unable to verify all the transactions due to computational constraints. This can make a decentralised system become more centralised. To resolve the computational constraints, why not just use a super computer instead? That is what happened to Solana. You need a CPU with 12 cores with 24 threads to become a verifier for the Solana blockchain.

To solve the Blockchain Paradox (increasing scalability while maintaining decentralisation), one possible method is called Fraud-Proof Rollups or Optimistic Rollups. This rollup method uses off-chain transaction processing to improve the processing efficiency for a given blockchain. This means that everybody needs to trust the computation results from some other large computer servers, which can lead to security concerns.

To avoid the security issues mentioned above, STARK uses Validity Proofs which means it only needs the large computer to submit the proof to the chains while all the other verifiers can validate this proof to prevent frauds. This process is when a batch of transactions are sent to the prover to generate the proof of new state and then wait until all the verifiers checked the new state. After the verification, the new state is updated to the layer1 blockchain.

Let's imagine that the proof is a sales receipt generated by the Layer 2 restaurant (Prover). Then, we, the customers need to naively sum up all the amount to check the proof is correct to accept the total amount.

In a STARK production environment, 1 block can fits more than 1,800,000 NFTs compared to only 150 NFTs per block in Layer 1. This huge increase in scalability brings 711 billion trading, 230 million transactions settled, and 66 million NFTs minted in total. Furthermore, each transaction’s gas fee is lower than 500 gwei, which is pretty small when comparing to minting on Layer 1.

What is StarkEx

StarkEx is a STARK-powered scalability engine for crypto exchanges that was developed by StarkWare. StarkEx uses cryptographic proofs to attest to the validity of a batch of transactions (such as trades and transfers) and updates a commitment to the state of the exchange on-chain. StarkEx allows exchanges to provide non-custodial trading at scale with high liquidity and lower costs. StarkEx currently supports ETH, ERC-20 and ERC-721 tokens, and can readily support tokens on other EVM-compatible blockchains. StarkEx is a mature platform that has been deployed on Ethereum mainnet since June 2020.

Reddio is built on top of StarkEx and provide all the NFT/ERC20 functionalities you need, such as easy-to-use APIs so that you can enjoy 0 gas fee with instant confirmation. NTF marketplace framework powered by Reddio’ APIs is fully open-source too, so that you can build your own in-App and in-Game NFT logic much faster.

To access the full TechTalk, please visit, https://youtu.be/BZQsF6Bpy5Q