Close Menu
    Thursday, November 21
    Price Index Newsletter

    Warning: Trying to access array offset on value of type bool in /home/crypawer/public_html/wp-content/themes/smart-mag/partials/single/layout-cover.php on line 53

    Recursion

    News RoomBy No Comments6 Mins Read

    Recursion refers to when a function calls on itself directly or indirectly in a circular loop(s).

    What Is Recursion?

    Recursion is used most commonly in the fields of mathematics, statistics and computer science, but it is also widely used across a range of other disciplines, including linguistics and logic, and in real-world applications of artificial intelligence and gaming.

    Recursion refers to when a function calls on itself directly or indirectly in a circular loop(s). 

    Recursion can be used to refine the accuracy of computation and reduce the overall computation loads required. By breaking a larger, more complex problem into smaller pieces, also known as “divide and conquer”, recursion makes solving the task quicker and more feasible. A key feature is that the function calls on itself repeatedly in successions to achieve recursion, defined in terms of base cases and recursive steps. 

    Base case refers to the simplest instance of a problem with all the inputs that would compute the output. Recursive steps call the same function but the inputs decrease in size and/or complexity. 

    Both iterative algorithms and recursive algorithms break down problems into smaller ones, but the former requires explicit control logic to manage the sequencing of the algorithms. The sequencing of a recursive function is determined by the interaction of the vector data and the recursive function. This offers greater flexibility in dealing with data structures that cannot be explicitly defined ahead of time. 

    How Is Recursion Applied to Blockchain Technology?

    Recursion is a method to generate proofs on the blockchain. It now serves multiple production systems on Ethereum mainnet. For example, Arbitrum uses a recursive bisection algorithm for its dispute resolution process, whereas StarkWare and zkSync both use recursion to achieve enhanced scaling capabilities.

    Without recursive technology, there is an upper limit of transactions one could fit into a proof, which is determined by the computation capacity of a single block. With recursion, a single proof can be generated from multiple verified proofs that contain hundreds of thousands of underlying transactions. In other words, we can now process many more transactions in a single proof, also known as recursive scaling. 

    Recursive technology being applied to zero-knowledge proof is especially important for it is deemed as a critical piece of the solution in resolving blockchain’s scalability. Taking StarkWare’s StarkNet, one of the leading zk-rollup scaling solutions on Ethereum, as an example, SHARP (SHARed Prover) takes transactions from separate applications on StarkNet to batch and compress them into one ZK-STARK proof (or just STARK proof). The prover then passes the proof to the verifier, and it is the latter’s job to verify and register the state change on layer 1. There are restrictions on who can be a prover based on the computational resources required.
    Now let’s add recursion into the picture. Multiple transactions (or statements) are sent to SHARP and proven in parallel. Each proof is then validated by a STARK verifier. Once verified, they are then merged again by a Recursive Verifier statement. This process can repeat itself until one final proof is submitted onto Layer 1 to a Solidity verifier smart contract. This proof is thus attesting to all original statements, allowing multiple on-chain transactions to be processed in a single proof. In theory, the recursive loop can repeat indefinitely, enabling the potential for “hyper-scaling” capability.
    Recursion, therefore, further unlocks the potential of roll-up technology and layer-2 scaling.

    Benefits of Recursion

    The benefits of recursion for validity proofs include lower gas cost from reduced cost per transaction due to the “compression” of multiple proofs into one. This allows more transactions to split inside a single proof submitted to L1 which amortizes gas cost per transaction. The computational resource barrier that limited a proof size is also no longer a constraint as there is no need to prove extremely large statements in one go. 

    It also results in reduced latency. Statements (containing smaller transactions) can be proven in parallel and not have to wait for other transactions to come in. Provers no longer need to perform large computations off-chain, and thus the barriers to becoming a prover have gone down, incentivizing a decentralized network of provers to further the network’s processing capacity. 

    In addition, users may benefit from “logarithmic compression” with STARK, where proving a statement takes T time and verifying the proof takes roughly log(T) time. Logarithmic compression is important because verifying a proof that contains two proofs of correct execution will take log(2log(T)) steps. In other words, the latency to produce and validate recursive proofs decreases on a logarithmic scale. 

    Through recursion, platforms and applications have the opportunity to further scale their cost and performance. 

    Uses of Recursion Beyond Layer 2

    Recursion sets the stage for layer 3 use cases. The focus thus far has been on using recursion to generate proofs on layer 2 that ultimately settle on layer 1. However, a new layer also opens up the possibility of submitting transaction proofs from layer 3 to layer 2 where execution is done on the top layer, and the proof is ultimately verified on layer 2, which can further unlock performance optimization and cost benefits. The interactions between layer 3 and layer 2 is analogous to layer 2 and layer 1, while all transaction integrity and security are being preserved.

    Specifically, private layer 3 networks are highly customizable so that protocols are able to set their own operational parameters such as setting transaction batch size to balance transaction cost and speed or implementing privacy-preserving features. The bespoke quality of layer 3s to cater to different use cases alongside improved processing capabilities from recursion allows for both a customized chain experience while ensuring the tools for performance and cost optimization are readily available. The benefits of Layer 3 are hyper scalability as a result of leveraging the multiplicative effect of recursive proving, privacy, and improved interoperability between layer 2 and layer 3.  

    Over time more use cases and benefits of recursion on blockchain development will be realized. By unlocking the process of parallelization, it will make hyper-scaling a possibility, improving latency and reducing gas fees all at the same time.

    Author

    Jane Ma, Co-Founder and Co-Project Lead of zkLend, an L2 money-market protocol built on StarkNet, combining zk-rollup scalability, superior transaction speed and cost-savings with Ethereum’s security. The protocol offers a dual solution: a permissioned and compliance-focused solution for institutional clients, and a permissionless service for DeFi users – all without sacrificing decentralization.

    Back to Glossary Index Page

    Share.
    Add A Comment
    Leave A Reply