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, how STARK works , and the 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 of transactions. That is what we called “Scalable Proofs”.
Scalable Proofs can help 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:
First, there’s other ways outside the blockchain to solve the integrity questions. During the history of human kinds, people invented legal system and law enforcement system to make a short-term game into a long-term game. That means when a person tries to break the integrity of something, this person needs to pay very huge price like being put into jail. Such potential heavy price ensures the integrity of the system. Even though they are not Probabilistically Checkable.
Second, in the 1992 , the system is not scalable which means the format of providing a proof is practically inefficient. If you want to write the proof of 1+1=2, you will need more atoms in solar system to do that even if the atoms can 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. And 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 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,FRI, Cairo, SHARP, 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 days. The Math shows a way to set any set of statements into a sudoku-like set of constraints . This kind of puzzle only have a few numbers in the paper and leaving all the others blank. 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-dimensions which can save 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 “S” in the word “STARK”) since the proving time equals log of number of transactions. And the verification time equals the log of number of transactions. That means the average proving time and verification time reduced as the total transactions number goes up. For example, to verify 1 million transactions, we need 6 steps. But with 1 billion transactions we only need 9 steps. That will also lower the gas fee applied to each transaction.
Second, the STARK is transparent (which is “T” in the word “STARK”) since all the verifier messages are public random coins. That means there are no trust setup or no keys even if government can use STARK to show integrity to its citizens. Since it cannot break math.
So how is STARK related to blockchain? To understand the connection, we need to first know the blockchain Paradox. Why blockchain is so slow compared to Visa? That is all about Computational Integrity. To ensure Computational Integrity, the traditional world use big computer managed by governments and financial institutions so that citizens can trust on. That also means users are not allowed to change the system. However, in the blockchain world, nobody is trusted. Therefore, everybody needs to verify all transactions to ensure integrity. This method is inclusive but very slow comparing with the traditional ways.
But the true question is how can we increase scale in the blockchains and maintained decentralised at the same time? Since as we increase the total scales, some nodes are unable to verify all the transactions. That makes a decentralised system centralised. So why we don’t use just a super computer instead? That is what happened to Solana. You need a CPU with 12 cores with 24 threads to become the verifiers.
To solve the question above. One of the way is called Fraud Proof Rollups or optimistic rollups. This rollup method uses off-chain transaction processing to improve the processing efficiency. That means everybody needs to trust the computation results from some other big computers which could lead to security issues.
To avoid the security issues mentioned above, STARK uses Validity Proofs that means it only needs the big computer to submit the proof to the chains and all the other verifiers can validate this proof to prevent from frauds. The process is 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.
We can 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 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. Each transaction’s gas fee is lower than 500 gwei which is pretty small compares to minting on layer 1.
What is StarkEx
StarkEx is a STARK-powered scalability engine for crypto exchanges 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 providing all the NFT/ERC20 functionalities you need as easy-to-use APIs so that you can enjoy 0 gas fee with instant confirmation brought to you by the power of StarkEx. NTF marketplace framework powered by Reddio’ APIs is fully open sourced too, so that you can build your own inApp and inGame NFT logic much faster.
To access the full TechTalk, please visit, https://youtu.be/BZQsF6Bpy5Q
