Recursive STARKs – what are they and how do they work?
For context, StarkWare has implemented them a few years ago, and you may have seen them mentioned in Ethereum’s upgrade plans. So what are they?
First, let's explain Recursion.
Recursion is a marvelous technique in computer science: you take a problem and break it down into a few smaller sub problems, where each sub problem is *exactly* the same as the original problem, but only smaller. Then you repeat this process till you have a large number of very small problems that are easy to solve.
The simplest example of recursion is binary search. Let's say I want to find the definition entry of a word (let's choose "Symphony") in the dictionary, and let’s assume the dictionary has 1000 pages. So I open the dictionary at roughly the middle and see what letter I'm at (suppose it’s "Lamb"). Based on that, I choose the half that comes after Lamb, and I open it, again, in the middle. Now, based on the letter I'm at, I know which half to narrow down next. I repeat the process, each time with half of the size of pages. Or in other words, I recursively search on smaller and smaller number of pages.
Now to STARKs.
A Prover claims she processed 1000 blocks, each containing 1000 transactions (for a total of 1M txs). We want to update the state of the system based on that. The Prover could submit one single proof, which the verifier would verify in roughly the time it takes to process, say, one transaction. But going down this route requires a very large computer, with a lot of RAM. If throughput increases and we need to prove 1M blocks, each with 1K txs, we'll need an even larger computer. There's a different and better way.
Now, recall that verifying a STARK proof takes an amount of computation that is roughly equivalent to processing one single tx.
Furthermore, since Starknet is Turing complete, there's no difference between a tx transferring STRK from Alice to Bob, a tx doing a swap, or... a tx that verifies a STARK proof. All of these are just examples of computation.
So, instead of using a big computer to prove 1M txs, a recursive STARK prover creates 1000 STARK proofs, one for each Starknet block. A verifier could spend the cost of 1000 txs to verify each of these 1000 proofs. But a more efficient way is to have a prover prove that she processed these 1000 txs, each tx is a verification tx. And thus, we have reached a way to use a smaller computer (or several separate computers in parallel) to prove the 1000 blocks, and then recursively prove that the 1000 proofs are all valid. We prove, and then we prove that we proved.
This recursive process is actually used in practice in Starknet, and leads to huge savings in latency and proving cost.
THE END.
For context, StarkWare has implemented them a few years ago, and you may have seen them mentioned in Ethereum’s upgrade plans. So what are they?
First, let's explain Recursion.
Recursion is a marvelous technique in computer science: you take a problem and break it down into a few smaller sub problems, where each sub problem is *exactly* the same as the original problem, but only smaller. Then you repeat this process till you have a large number of very small problems that are easy to solve.
The simplest example of recursion is binary search. Let's say I want to find the definition entry of a word (let's choose "Symphony") in the dictionary, and let’s assume the dictionary has 1000 pages. So I open the dictionary at roughly the middle and see what letter I'm at (suppose it’s "Lamb"). Based on that, I choose the half that comes after Lamb, and I open it, again, in the middle. Now, based on the letter I'm at, I know which half to narrow down next. I repeat the process, each time with half of the size of pages. Or in other words, I recursively search on smaller and smaller number of pages.
Now to STARKs.
A Prover claims she processed 1000 blocks, each containing 1000 transactions (for a total of 1M txs). We want to update the state of the system based on that. The Prover could submit one single proof, which the verifier would verify in roughly the time it takes to process, say, one transaction. But going down this route requires a very large computer, with a lot of RAM. If throughput increases and we need to prove 1M blocks, each with 1K txs, we'll need an even larger computer. There's a different and better way.
Now, recall that verifying a STARK proof takes an amount of computation that is roughly equivalent to processing one single tx.
Furthermore, since Starknet is Turing complete, there's no difference between a tx transferring STRK from Alice to Bob, a tx doing a swap, or... a tx that verifies a STARK proof. All of these are just examples of computation.
So, instead of using a big computer to prove 1M txs, a recursive STARK prover creates 1000 STARK proofs, one for each Starknet block. A verifier could spend the cost of 1000 txs to verify each of these 1000 proofs. But a more efficient way is to have a prover prove that she processed these 1000 txs, each tx is a verification tx. And thus, we have reached a way to use a smaller computer (or several separate computers in parallel) to prove the 1000 blocks, and then recursively prove that the 1000 proofs are all valid. We prove, and then we prove that we proved.
This recursive process is actually used in practice in Starknet, and leads to huge savings in latency and proving cost.
THE END.