Recursion refers to when a function calls on itself directly or indirectly in a circular loop(s).
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.
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.
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.
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
Join the thousands already learning crypto!