Forum
Finance
Specials
On-chain Eco
Entry
Podcasts
Activities
OPRR
Comprehensively sort out StarkWare's new L2 expansion solution "recursive proof"
Original title: "Recursive STARKs"
Original author: Gidi Kaempfer, StarkWare Core Engineer
Original compilation: "StarkNet Chinese" community
Summary
< b>· Recursive proof is launched on the main network, and one proof is used to expand StarkEx applications and StarkNet
· Recursive proof to improve scalability, reduce cost and delay (rare scalability and delay are developed simultaneously, without trade-offs)
·
· Recursive proof creates conditions for L3 and other wonderful uses
· Look at the blog post of recursive proof, Super cool
Multiple expansion
Recursive proofs powered by Cairo general computation are now in production. This marks a major improvement in STARK's L2 scaling capabilities. The number of transactions written to Ethereum with a single proof can quickly multiply.
So far, STARK proofs scale by "aggregating" tens or even hundreds of thousands of transactions into a single proof written into Ethereum. Through recursion, many such proofs can be "rolled up" into a single proof.
This approach is already used in numerous Cairo-based applications: those running on StarkWare's SaaS extension engine StarkEx and the permissionless Rollup StarkNet program.
Development history so far
Since the first proof was generated on the mainnet in March 2020 , STARK proves that it has gone through different stages of development so far.
STARK Extension
June 2020, first STARK extension solution StarkEx is deployed on the Ethereum mainnet. StarkEx has a prover that performs large calculations off-chain, generates a STARK proof to represent transaction accuracy, and a validator that verifies the proof's accuracy on-chain. The first deployment was done by StarkWare engineers from scratch, so the functionality of StarkEx is extremely limited. Ultimately we decided that we needed a programming language that supports proof-of-general computation. In this way, Cairo came into being.
The Cairo programming language
In the summer of 2020, Cairo will debut on Ethereum net. Cairo, or CPU Algebraic Intermediate Representation (AIR), contains a single AIR that verifies the corresponding "CPU" instruction set. Cairo opens the door to coded proofs for more complex business logic, arbitrary computational statements, and is faster and more secure. A Cairo program can prove the execution logic of the corresponding application. But a Cairo program can also integrate multiple such applications, which is SHARP.
SHARP
SHARP That is, the shared prover (SHARed ProSver), which can aggregate the transactions of several independent applications and prove them in a single STARK proof. Applications can combine different batches of transactions to fill up the capacity of STARK proofs faster. Transaction processing speed and latency have both increased. Recursive proofs are a next-generation cutting-edge technology, not just for some hard-coded logic, but for universal computing.
To understand the full benefits of recursive proofs, it is necessary to take a closer look at how SHARP has performed (non-recursive) proofs so far. Figure 1 depicts a typical non-recursive process:
Figure 1: Typical non-recursive proof process
In this process, propositions arrive gradually. When the capacity (or time) reaches a certain threshold, a large composite proposition (Train) is generated. This combined proposition can only be proved after all the individual propositions have been received. This proof takes a long time (roughly the sum of the times required to prove each proposition individually). Proving extremely large propositions is ultimately limited by available computational resources such as memory. Before recursion, this was actually a big hurdle limiting the scalability of STARK proofs.
What is a recursive proof?
With the STARK proof, the time it takes to verify a proposition is roughly linear in the time it takes to execute it. Furthermore, if proving a proposition takes time T, then verifying the proof takes approximately log(T) time, which is often referred to as "logarithmic compression". In other words, using STARK allows users to spend much less time verifying propositions than computing them.
Cairo Allows the expression of general computational propositions, which can be proven by STARK proofs and verified by corresponding STARKs device verification.
This is where the opportunity to perform recursion comes in: just like you can write a Cairo program to prove the correctness of thousands of transactions, It is also possible to write a Cairo program to verify multiple STARK proof. A proof can be generated to verify the validity of multiple "upstream" proofs. This is what we call a recursive proof.
Due to the roughly linear relationship between logarithmic compression and proof time, the time required to verify a STARK proof is relatively short (expected to take only a few minutes in the near future ).
When implementing recursion, SHARP can verify propositions as soon as they are received. Proofs can be iteratively combined into recursive proofs in various modes until, at some point, the resulting proof is submitted to the on-chain validator contract. Figure 2 is a typical recursive proof mode:
Figure 2: Typical recursive proof flow
In this example, four propositions are sent to SHARP (possibly originating from four different applications). These propositions are independently proved in parallel. Each pair of proofs is then verified by a recursive verifier proposition (the Cairo program that verifies STARK proofs), resulting in a proof. This proposition is verified by two proofs. Next, the two proofs are merged again via a recursive verifier proposition. This yields a proof that confirms all four original propositions. This proof can eventually be submitted to the chain and verified by the Solidity validator smart contract.
Direct advantage of recursive proof
Reduce on-chain costs
There is no doubt that we have achieved "compressing" multiple proofs into one, which means that the cost of on-chain verification for each transaction (where each proposition may contain many transactions) will be significantly lower.
The use of recursive proofs removes the computational resource barrier (such as memory) that has hitherto limited the size of proofs, since each proposition has a finite capacity and can be proved individually. Therefore, when recursion is used, the capacity of recursive effective combination proposition (Train) is almost unlimited, and the cost of each transaction can be reduced by several orders of magnitude.
In practice, reducing costs depends on acceptable latency (and how quickly transactions arrive). Additionally, since each proof is usually accompanied by a corresponding on-chain data output, the amount of data written on-chain with a single proof will also be limited. Still, reducing cost by an order of magnitude, and even continuing to improve performance, are easily achievable.
Reduce Latency
The recursive proof mode reduces the latency of proving large combinatorial propositions. Two factors come into play:
1. The received propositions can be proved parallel (instead of proving huge combinatorial propositions).
2. Prove without waiting for the last proposition in Train to arrive. On the contrary, new propositions can be combined with proofs at any time. That is, the latency of the last proposition added to the Train is roughly the time required to prove the last proposition plus the time required to prove the recursive verifier proposition (which proves all the propositions that have "joined" this particular Train).
We are actively developing and optimizing latency issues for proving recursive validator propositions. Proving recursive validator propositions is expected to be on the order of minutes within months. Therefore, an efficient SHARP delay can be controlled from a few minutes to a few hours, and the length of the delay depends on the trade-off of the cost on the chain of each transaction. This is a significant improvement over SHARP latency.
Promoting L3 Applications
The recursive validator proposition developed with Cairo also opens up the possibility of submitting proofs to StarkNet, as the proposition can be written into StarkNet smart contracts. This allows L3 deployment on the StarkNet L2 public network.
Recursive mode also applies to aggregated proofs from L3, verified by a single proof on L2. Therefore, L3 can also achieve ultra-large scale.
More magical uses
Application recursion
Recursion opens up more opportunities for platforms and applications that want to further scale their cost and performance.
Each STARK proof proves the validity of a proposition applied to some "public input" (or "program output" in Cairo terminology). Conceptually, STARK recursively compresses two proofs with two inputs into one proof with two inputs. In other words, while the number of proofs has decreased, the number of inputs has not changed. The input is then typically used by applications to update some state on L1 (for example, to update a state root or perform on-chain withdrawals).
If recursive propositions can be application-level aware, that is, recognize the semantics of the application itself, then recursive propositions can combine both Proofs can be compressed into one, or two inputs can be combined into one. The final proposition proves the validity of the combination of inputs based on application semantics, which is Applicative Recursion (see Figure 3 for an example).
Figure 3: Application recursion example
Proposition 1 proves a state update from A to B, while Proposition 2 verifies a further update from B to C. The proofs of Proposition 1 and Proposition 2 can be combined into a third proposition, directly proving the update from A to C. By applying similar recursive logic, the cost of state updates can be reduced very significantly to meet the ultimate latency requirement.
Another important example of applying recursion is compressing aggregated data from multiple proofs. For example, for Rollup, which proves validity like StarkNet, each storage update in L2 is also updated in L1 as transmission data to ensure data availability. However, there is no need to send multiple updates for the same storage unit, since only provably verified transactions will eventually satisfy data availability. This optimization has been performed in a single StarkNet block. However, applying recursion can compress multiple L2 block summary data by generating proofs for each block. This can significantly reduce costs and reduce L2 block times without sacrificing the scalability of L1 updates.
It's worth noting that applying recursion can be combined with applying general recursion as described earlier. But these two optimizations are not related to each other.
Reducing the complexity of on-chain validators
The complexity of a STARK validator depends on the type of proposition being validated. For Cairo propositions in particular, the complexity of the validator depends on the specific elements allowed in the Cairo language, more specifically, the supported built-ins (if Cairo is likened to a CPU, then the built-ins are equivalent to the microcircuits in the CPU: Calculations are performed too frequently, so you need to optimize your own calculations).
The Cairo language is constantly evolving and provides more and more useful built-ins. On the other hand, recursive validators only need to use a small set of built-ins. Therefore, recursive SHARP can successfully support any proposition in Cairo by supporting the full language in recursive verifiers. Specifically, Solidity verifiers on L1 only need to verify recursive proofs, so verifiers can be limited to verifying a more stable subset of the Cairo language: L1 verifiers don't need to be updated with the latest, most stable builtins. In other words, as propositions evolve, complex verifications are handled by L2, and L1 verifiers only need to verify simple, stable propositions.
Reduce Computational Footprint
Prior to recursion, aggregating multiple propositions into a proof is limited by the size of propositions that can be proved on the available computing instances (and the time required to generate such proofs).
With recursion, there is no need to prove such a huge proposition. Because more compute instances are available that are small and cheap (although there may be more compute instances than would be required with a large monolithic prover). This makes it possible to deploy prover instances in more physical and virtual environments.
Summary
The recursive proof of general computing has now served multiple product systems on the Ethereum mainnet including StarkNet.
Due to continuous improvement, the advantages of recursion will gradually appear. After the potential of parallel computing is realized, the gas fee will be reduced, the latency will be improved, and ultra-high scalability will eventually be realized.
The advantages of recursion in terms of cost and latency are very significant, and it also opens up new opportunities such as L3 and application recursion. The recursive validator continues to be optimized, and its performance and cost-effectiveness will gradually improve.
Appendix
Original text: Recursive STARKs
Original text: Youtube: StarkEx - How Does it Work?
Original text: Hello, Cario!< p>
Original text: Hello, Cario!
Original text: Wikipedia Entry: Recursion
Original text: "Fractal Expansion: From L2 to L3"
Original link
Welcome to join the official BlockBeats community:
Telegram Subscription Group: https://t.me/theblockbeats
Telegram Discussion Group: https://t.me/BlockBeats_App
Official Twitter Account: https://twitter.com/BlockBeatsAsia
