This article expands on the key concepts covered in the presentation "Recursive Proofs: Applications and Affordances" delivered by Ying Tong and Nalin Bharadwaj at Devcon 2022.
Introduction
Over recent years, privacy-preserving systems have garnered tremendous interest, given their capacity to facilitate multi-party computation and validate the integrity of complex processes without exposing raw datasets. Solutions like secure multi-party computation (MPC) and zero-knowledge proofs (ZKPs) have become vital to sectors dealing with confidential information.
However, current ZKP systems have some limits holding back widespread adoption. Validation often hits snags around efficiency, flexibility, and scaling capacity when proving one-off statements.
This is why recursive proofs feel like such a huge game-changer! Their core concept of chaining proofs in sequences could dissolve those bottlenecks and unlock massive potential for privacy preservation.
See, the recursion lets you collapse entire computations with gargantuan data into a single cryptographic proof. Each proof validates prior proofs in turn. This principle delivers insane compression ratios and cuts the costs of generating or checking validity through the roof!
Now, another awesome angle is how recursion enables "composability" - meaning proofs can intersect across trust boundaries without revealing intermediate steps. Folks with fragmentary views can link up tokenized commitments in relays, which opens up super fascinating opportunities for privacy protocols between mutually distrusting parties!
Of course, kinks around scaling and connecting diverse proof systems still need ironing. But the timing seems perfect for a deeper dive into recursion given the immense promise on display.
By peering closer at existing recursive architectures like full recursion, atomic accumulation and such, I'm hoping we can synthesize lessons from current approaches and also inspire more brainstorming around potential applications.
The more developers grasp how recursion introduces standardization and customizability, the quicker we'll see adoption in privacy-sensitive domains.
Introduction to Zero-Knowledge Proofs
Zero-knowledge proofs (ZKPs) are a foundational primitive used to validate the accuracy of computations and statements, while simultaneously preserving the privacy of the underlying data utilized in those computations. This unique dual property of integrity and privacy is what gives zero-knowledge proofs their power and versatility.
At a high level, ZKPs allow one party (the prover) to convince another party (the verifier) that they know certain information or that a computation is correct, without conveying any information apart from the fact that the statement itself is true. This is accomplished through advanced mathematical techniques, including cryptographic proofs, commitments schemes, and interactive challenges.
The critical innovation is that the proof process does not reveal any additional knowledge; hence, the verifier gains "zero knowledge" but gains assurance in the validity of the statement. This concept is akin to a puzzle where the solver proves they have found the solution through a series of steps, without actually disclosing what the solution is.
The zero-knowledge properties open the door for a tremendous range of privacy-preserving applications including private payments, anonymous credentials, confidential transactions in decentralized finance, secret voting systems, and more.
Different Types of Zero-Knowledge Proofs
Interactive ZKPs: Initially, ZKPs were interactive, meaning the prover and verifier engaged in a back-and-forth communication. The prover would provide evidence, and the verifier would challenge the prover for more information.
-
The interactivity enables the verifier to recursively challenge the prover until they gain statistical confidence in the proof's validity. However, the rounds of interaction can be computationally expensive.
-
Examples of interactive ZKPs include various "zero-knowledge arguments" and also schemes based on Probabilistically Checkable Proofs (PCPs). These lay the early groundwork for more advanced constructions.
Non-Interactive ZKPs: Later developments led to non-interactive (NIZK) ZK proofs, where the proof can be generated and verified without direct interaction between the prover and verifier. This advancement is crucial for scalability in decentralized systems like blockchains.
These eliminate the need for interactive challenges. The prover computes an elaborate mathematical proof incorporating cryptographic commitments and sending the entire proof to the verifier in one transmission. This approach is more efficient at scale but proof generation uses heavier computation.
NIZKs are the precursor to...
-
Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs): A specific type of non-interactive ZKP known for its succinctness and efficiency.
-
Zero-Knowledge Scalable Transparent Arguments of Knowledge (zk-STARKs): Similar to zk-SNARKs but without the need for a trusted setup and with better scalability.
Overview of zkSNARKs
Succinct Non-interactive ARguments of Knowledge, or zkSNARKs, represent the state-of-the-art in practical applications of zero-knowledge proofs. They are a specific form of NIZK optimized for high efficiency.
How zkSNARKs works:
-
Program Construction: The first step is to construct a program that encodes the desired statement or computation to be proven. For example, if wanting to prove "I paid Andrew 10 tokens", you would write a program with transfer logic that simulates paying 10 tokens to Andrew.
-
Prover Computation: The prover runs the program with inputs set to reflect the real-world conditions - in this case, actual sender, receiver and amount. The program execution will determine if the statement is true or not.
-
Proof Generation: The prover generates a zkSNARK proof attesting that they ran the program correctly and faithfully. The proof is a cryptographic signature that does not reveal any inputs or intermediary steps due to zero-knowledge properties.
-
Verifier Receives Proof: The verifier receives the proof. All they see is a succinct cryptographic string that hides all intermediate computations via cryptographic randomness and commitments.
-
Verification: The verifier checks if the proof is valid relative to the original program using special cryptographic checks. These include elliptic curve computations that indicate if the proof matches the program WITHOUT revealing anything about the secret inputs.
-
Verification Success: If all checks pass, the verifier can now establish the prover executed the program faithfully while keeping the input data perfectly secret. The verifier knows no more than the core validity of the statement itself.
This unique dual guarantee of privacy and integrity is the magic of zkSNARKs!
Now, coming to Recursive SNARKs
Recursive SNARKs represent a significant advancement in the field of cryptographic proofs, particularly in the realm of zero-knowledge proofs (ZKPs). They are a complex but powerful tool that allows for more efficient and scalable verification processes in various applications, especially in blockchain technology.
Before diving into recursive SNARKs, it's essential to understand the basics of ZK-SNARKs:
-
Zero-Knowledge Proofs: These are methods by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.
-
Succinctness: SNARKs are characterized by their small proof size and fast verification time, regardless of the complexity of the statement being proved.
Recursive SNARKs are a special class of zero-knowledge proofs that allow proving the validity of a computation without revealing any underlying information. They build upon regular SNARKs by adding the ability to nest proofs inside other proofs in a recursive manner.
In a regular SNARK, a prover can generate a proof that shows they performed some computation correctly without revealing any intermediate steps. Recursive SNARKs take this a step further - they allow a proof that a previous SNARK proof is valid, without revealing the contents of that previous proof.
There are two major benefits unlocked by the recursiveness property:
-
Compression: Multiple SNARKs can be compressed into a single proof by recursively proving each one. This saves storage and allows more efficient verification.
-
Composability: SNARKs can be composed in layers, with each layer dependent on the proof of lower layers. This allows constructing complex proofs from simpler building blocks.
Further in the article, we will see how these two benefits help apply recursive SNARKs with real-world applications.
How it works
At a high level, recursive SNARKs enable the creation of proofs that verify previous proofs. This allows "nesting" proofs inside each other to arbitrary depth.
-
Imagine a scenario where you have a series of computations or statements, each with its own proof.
-
In a non-recursive setting, each of these proofs would need to be verified independently, which can be time-consuming and computationally intensive.
-
Recursive SNARKs allow these individual proofs to be "nested" within each other. This means that the verification of one proof includes the verification of another proof inside it.
-
This nesting can continue for several levels, where a proof at one level contains a proof of another level, and so on.
Concretely, a recursive SNARK protocol contains the following steps:
-
Base Computation - The prover performs some initial computation C0 (e.g. executing a program)
-
Generate Proof - The prover generates a zk-SNARK proof π0 that attests to C0 being done correctly.
-
Verify Proof - The verification process for π0 is itself turned into a program C1. The prover generates a new proof π1 that C1 returned accept.
-
Recursive Verification - This proof of a proof process can continue recursively. π2 attests that verification C2 of π1 passed, and so on.
Consider a scenario where each block contains transactions, and each transaction has proof of validity. Verifying each transaction individually for each block is a massive task. With Recursive SNARKs, you could have a proof for each block that includes the proofs of all transactions within it. Then, these block proofs can be recursively nested into a single proof that, when verified, confirms the validity of all transactions in all blocks.
The end result is a chain of proofs that build on one another, from the initial base computation through each level of verification. This chain of layered proofs comprises the full recursive protocol.
Comparison with zkSNARKs
Recursive SNARKs introduce a major extension - the ability to nest proofs inside other proofs in a recursive fashion. One SNARK proof can verify the correctness of previous SNARK proofs in a chain.
For example, SNARK A can prove some statement, and SNARK B can prove that "SNARK A is a valid proof". This can extend recursively with SNARK C proving the validity of SNARK B, and so on in layers.
-
Concretely, consider a proof π1 that attests some core statement is true. For example, "The prover knows the password for bank account #xxx".
-
A second proof π2 can then attest that "π1 is a valid SNARK proof." Note π2 does not need to see the actual contents of π1. It simply confirms via cryptography that π1 itself comprises a properly structured SNARK proof.
This can be extended such that proof π3 validates that "π2 is a valid proof" and so forth in a hierarchical chain. Each proof checks the validity of the previous one without visibility into its internals.
Implementation Classes of Recursive SNARKs:
Now, there are different methods/strategies to construct and optimize recursive SNARKs. These classes represent various approaches to handling the recursive aspect of SNARKs, each with its own set of techniques, advantages, and trade-offs. The goal is to make the recursive proofs more efficient, scalable, and practical for real-world applications. The main classes are:
#1. Full Recursion
In Full Recursion, every step or layer of the proof process involves a recursive verification. This means that each proof generated includes within it the verification of the previous proof.
Essentially, it's a direct application of the recursive SNARKs concept, where each new proof attests to the validity of the previous one without any shortcuts or intermediate steps.
How It Works:
-
Imagine a sequence of computations, each producing a proof.
-
In Full Recursion, for each computation, you generate a SNARK proof that includes within it the proof of the previous computation.
-
This process repeats, with each new proof encompassing the verification of the last, creating a chain of proofs where each link fully verifies the previous one.
If there is a base computation C0, the first proof is π0. The verifier takes π0 and runs the verification circuit, which itself becomes computation C1. This is turned into proof π1, which the verifier again checks, forming C2 and so on.
It provides a very strong guarantee of correctness since each proof is fully verified within the next. While also, this method can be computationally intensive and less efficient, as each proof carries the full burden of verifying the previous one.
This approach is particularly suitable for systems where the integrity of each step is critical, such as in consensus mechanisms. The trade-off for high computational cost is justified by the need for robust trust anchoring.
Full recursion in the context of Incrementally Verifiable Computations (IVCs) using SNARKs with sublinear verification essentially builds upon the notion of creating a chain of proofs where each proof not only attests to the correctness of its specific computation but also incorporates the verification of the previous proof in the sequence.
In the above diagram, Full Recursion can be visualized as a sequence where each IVC prover, after generating a proof (π_i+1), passes it to the next prover. This prover not only generates the proof for the next computation but also verifies the proof it received (π_i+1). The verification result becomes part of the input for the next proof (π_i+2), ensuring that each proof in the sequence is a product of its computation and the verification of all previous computations. This process ensures that errors or malfeasance cannot propagate through the sequence, as each step is independently verified within the recursive framework.
The chained verification emblemized by full recursion epitomizes the versatility afforded by computational recursion. By baking validity of previous steps into the next proof, it enables composite distributed protocols with cryptographic guarantees across transitions. This methodology allows parceling large sequential computations across multiple non-colluding provers with minimal coordination. Each proof produced in isolation only needs the previous proof as input. The sequence stitches together end-to-end assurance spanning components.
The elegance is in the simplicity of relying purely on recursive cryptography rather than interactive coordination. The validity chain seals output to inputs recursively across steps. Moreover, full recursion sequentially alternates between an efficient proving circuit and a more expensive verification circuit. This allows amortizing costs in a way that retains integrity.
The compartmentalization introduced between cheaper generation and stricter validation also allows interesting hybrid models - where portions of an algorithm can be intensely verified without requiring the same rigor universally.
#2. Atomic Accumulation
Atomic Accumulation introduces the concept of an accumulator to manage the verification process more efficiently. Instead of verifying each proof in full, this method accumulates "summaries" or "digests" of proofs and defers full verification to a later stage.
How It Works:
-
Each proof in the sequence contributes to a growing accumulator.
-
This accumulator represents a succinct summary of all the proofs so far.
-
Periodically, or at certain checkpoints, the accumulated proofs are fully verified in one go.
The concept of aggregating multiple proofs (π0, π1, π2) into an accumulated state and then performing a single verification at the end is a key feature of this approach. It effectively balances the computational load by spreading it across multiple proofs. The trade-off is a temporary reduction in assurance until the final batch verification.
This approach is well-suited for scenarios like transaction aggregation in privacy-focused blockchain applications, where batching proofs can significantly improve performance without severely compromising security.
How Atomic Accumulation Works in IVC Context:
-
In the IVC framework, as depicted in the diagram, the prover generates a proof (π_i+1) for each computation (Z_i+1), demonstrating the correct execution of function F.
-
Each proof is split into two components:
-
a part that can be immediately verified (P), and
-
another part that is deferred (a_i).
-
-
The deferred components are aggregated into an accumulator (a_i+1), which serves as a running summary of all the proofs generated so far in the sequence.
-
The IVC verifier periodically checks the public parts of the proofs (SNARK.Verify), while the accumulated parts are stored for batch verification later on.
-
The process is iterative, with each new proof adding to the accumulator. The deferred parts are like "IOUs" of proof verification, promising that these aspects will be checked eventually.
-
When it's time for batch verification, the accumulated deferred parts (D) are processed all at once. This is where the system ensures that all intermediate proofs, not just the latest, are valid.
As the IVC prover works through the sequence of computations, it uses the SNARK.Prove function to contribute to the growing accumulator. This accumulation strategy is akin to adding summaries or digests of each proof to a collective dossier that represents the entire computation chain. Periodically, or at pre-determined checkpoints, the IVC verifier performs a comprehensive review of the dossier—the batch verification step. This step confirms the integrity of the entire computation sequence by processing the accumulated summaries.
By integrating the atomic accumulation approach with IVC, we achieve a balance between immediate verification and computational efficiency. Each proof (π_i) is partially verified upon creation, while the complete assurance of all proofs is delayed until the batch verification (D).
The trade-off is that while there is a temporary suspension of full assurance until the final verification, the overall computational load is distributed more evenly, avoiding the need for intensive verification after each computation.
Atomic Accumulation in the context of IVC is particularly advantageous for applications like transaction aggregation in privacy-centric blockchain systems. It allows for improved performance by batching multiple transaction proofs together, without significantly compromising the system's security integrity.
Also, a core benefit of accumulation is it anchors assurance through continuity while deferring intense checks. The accumulator mutates like a compressed snapshot, accumulating integrity through the computation. This allows for optimizing proof workflows for regular operations. Cheap inline checks sustain assurance while heavier batch verification runs periodically, amortizing costs.
The flexibility also enables just-in-time finalization of proofs. For instance, financial batches can settle transaction proofs daily without impacting real-time validation flows. Interestingly, the incremental accumulation introduces stateful assurance - as if validity ebbs and flows with each new proof until definitive ratification. This graduated model offers efficiency without undermining security.
#3. Split Accumulation
Split Accumulation further refines the accumulator concept by dividing it into public and private components. This division allows for different handling of various parts of the proof, optimizing the process based on the nature of the data involved.
How It Works:
-
The public part of the accumulator is updated and verified more frequently, as it involves aspects of the proof that are essential for immediate validation.
-
The private part accumulates more extensive or complex data and undergoes verification less frequently or at specific points where full validation is necessary.
The idea of quickly verifying public parts of the proof at each level while deferring the more intensive verification of private parts to the end is a strategic approach to manage computational resources. This method strikes a balance between maintaining ongoing security (through public parts) and managing verification costs (through private parts).
This hybrid approach is adaptable and can be tailored to various use cases, offering a middle ground between the security of full recursion and the efficiency of accumulators.
Split Accumulation in IVC leverages the concept of dividing the verification process into public and private components, where the public part of each proof is verified immediately, and the private part is accumulated and verified at specific points.
-
In the IVC system, as illustrated in the provided diagram, the prover uses SNARK.Prove to generate a proof (π_i+1) for each computation (F), resulting in a new state (Z_i+1).
-
This proof is divided into a public part (P) that the verifier (SNARK.Verify) checks right away, ensuring ongoing security by confirming essential aspects of the computation.
-
Simultaneously, the private part (a_i) is added to an accumulator (a_i+1). This private part represents more complex or data-intensive aspects of the proof that do not require immediate validation.
-
Over time, as the IVC prover continues to generate new proofs, the private parts accumulate. They are only fully verified when necessary, optimizing the use of computational resources.
-
The split accumulation approach thus ensures that essential validations are not delayed, while more resource-intensive checks are strategically deferred to maintain efficiency.
The process is iterative, with each new proof adding to both the public and private accumulators. The public accumulator (P) is akin to a ledger that is updated and checked regularly, while the private accumulator (a_i, i) is more like a vault that is only opened and audited when needed. Ultimately, the IVC verifier will conduct a full verification of the accumulated private parts (D), which confirms the validity of all the underlying computations, ensuring the system's integrity.
This approach to split accumulation within IVC is particularly advantageous for systems that require a balance between security and efficiency, such as transaction aggregation in privacy-centric blockchain systems. It offers a pragmatic solution that provides immediate assurance for critical components while distributing the verification workload over time for more complex elements.
A core benefit of split accumulation is efficiently handling proofs with asymmetric verification costs. Public knowledge necessary for continuous assurance gets cheap inline checks. Private knowledge with expensive consistency checks accumulates discreetly. This matches security rigor to validation complexity, while sustaining real-time confidence. Protocol designers can creatively reflect attributes needing intense verification versus innocuous metadata requiring only lightweight validation into this public-private split.
Moreover, the technique offers storage optimizations. Public accumulators may update high-velocity logs to anchor ongoing proof integrity. But heavy batch validation can run directly on archived private components, avoiding retention overhead. Interestingly, split accumulation also enables intermediate trades between privacy and efficiency via tweaked public-private ratios. More transparency brings faster evidence while larger opaque chunks enable intensive batch proofs.
Applications of Recursive Compression
Earlier in this article, I mentioned I’ll explore two main benefits of Recursive SNARKs:
-
Compression, and
-
Composability.
Here it is.
#1. Compression: Condensation of Multiple Proofs
The primary feature of recursive SNARKs is their ability to condense or aggregate multiple proofs. This is achieved through a process where each new proof generated includes the verification of the previous proof. Essentially, a recursive SNARK proof can attest to the validity of another SNARK proof. This nesting can continue, allowing for a series of computations or validations to be compressed into a single proof.
-
In practical terms, consider a scenario where each transaction or block operation requires proof of validity.
-
In a non-recursive setting, each of these proofs would need to be verified independently, which can be time-consuming and computationally intensive. Recursive SNARKs, however, allow these individual proofs to be "nested" within each other.
The approach involves a prover structuring statements into different "levels" of proofs, then recursively demonstrating knowledge of lower levels within a top-level proof:
-
Decompose Statements: Break down the overall statement to be proven into component pieces requiring separate proofs. For example, validate individual steps of a complex computation.
-
Construct Base Proofs: Build individual zero-knowledge proofs for each component statement using SNARKs or STARKs. These establish ground truths of lower-level statements.
-
Recursively Prove Knowledge: Within a new higher-level proof, demonstrate knowledge of the lower-level proofs without revealing actual proof contents. Cryptographic commitments let the verifier confirm valid sub-proof structure without visibility.
-
Aggregate Into One Proof: Repeating the recursive step sequentially compiles an arbitrary number of sub-proofs into one condensed high-level proof. This top proof validates all lower proofs in aggregate by recursively demonstrating knowledge of them.
Specialized knowledge commitments mathematically bind the high-level proof to the proper structuring of lower-level proofs in a way that is cryptographically enforceable. This wiring together prevents the insertion of false proofs within the recursion. The construction relies on advanced commitments and zero-knowledge proofs but unlocks exponential compression from condensing proofs of proofs recursively into one singular verified proof encompassing any number of sub-statements.
The verification of one proof includes the verification of another proof inside it. This process significantly reduces the computational burden and time required for verification. Instead of verifying each proof independently, the verifier checks one encompassing proof that recursively verifies all underlying proofs.
The key idea in recursive compression is that a prover can show "I know N pieces of knowledge" by recursively proving smaller sub-statements in a compressed manner. These following examples illustrate recursive compression, where a large statement (N signatures, full blockchain validity, N transactions) is broken down recursively into smaller sub-proofs in order to derive an extremely compressed overall proof:
-
Signatures: "I have N signatures signing this message"
-
Light Clients: "Light client L has verified all necessary blockchain validity"
-
Rollups: "I have verified the validity of N transactions batched together"
Let’s explore each in detail
Signature Aggregation
Signature aggregation involves combining multiple digital signatures into a single signature, which verifies that each participant signed the same message. This can save significant space instead of transmitting each signature individually.
Recursive SNARKs allow extremely efficient signature aggregation by using compression. The prover can construct a SNARK proof that shows "I have N signatures signed by different parties that endorse this message." The proof recursively shows:
-
Here is one signature
-
I have a SNARK proof that there exist N-1 more signatures
And the N-1 proof recursively decomposes using the same logic. Finally, the verifier only needs to check a single proof that all signatures are valid.
Concretely, let's look at an example application called Isokratia. Isokratia is a decentralized governance protocol built using signature aggregation from recursive SNARKs. It essentially creates a "rollup" which batches many signatures from different parties into a succinct cryptographic proof.
Current governance platforms have limitations. Off-chain systems like Snapshot are free for voters but require trust in centralized entities. On-chain systems, like those used by Compound, eliminate this trust but are expensive due to transaction fees (gas fees), which can reduce participation.
The primary goal of Isokratia is to enable secure, transparent, and nearly cost-free voting mechanisms for DAOs and other governance systems. This allows the building of scalable voting schemes, coordination mechanisms, and decision records. Signatures signify attestations from members without explicitly revealing each individual signature. The proof simply states - "100 people signed message X".
How it works exactly:
In Isokratia, voters cast their votes off-chain, which is free. These votes are then aggregated into a succinct recursive ZK-SNARK proof, which is submitted and verified on-chain. This method ensures security and integrity while keeping costs low.
-
Users vote on proposals off-chain. Creating a proposal might require an on-chain transaction to ensure it's recorded for aggregation.
-
These nodes collect votes and continually generate larger aggregation proofs. Once ready, they submit these proofs on-chain to finalize the vote.
By aggregating signatures in this manner, Isokratia is able to construct a highly efficient decentralized governance protocol on top of a public blockchain. Events, actions, and records can be published with proof of endorsement from several participants in a privacy-preserving and compact way.
The recursive proof architecture used by Isokratia results in massive savings in terms of bandwidth, storage space, and verifier computation for handling multitudes of signatures. This unlocks practical decentralized governance at scale by leveraging the compression enabled through recursive SNARK constructions.
Light Client Proofs
In blockchains, light clients allow users to verify transactions and check account balances without needing to run full-node software or store the entire blockchain. Light clients only download block headers and use cryptography to ascertain validity - proving the light node has all the necessary data.
Recursive SNARKs hugely optimize proofs used in light clients. Again, compression allows a succinct proof structure showing "light client L has verified all essential information in blockchain B". This can recursively check individual headers, account states, transaction validity and more through sub-SNARKs in a highly compressed and aggregated manner.
One example of this is Plumo. Plumo uses zkSNARKs to create efficient "light client proofs" that allow ultra-light blockchain clients to sync state with minimal bandwidth and computation:
Light clients in Plumo only need to verify "epoch transition messages" in Celo which encode validator set changes, rather than entire blocks. Plumo builds a zkSNARK circuit that validates sequences of epoch messages. The circuit checks:
-
Signatures over epoch messages are valid
-
Messages correctly encode validator set changes
-
Messages link epoch entropy values for unpredictability
The SNARK prover aggregates validator signatures into a single proof using BBSGLRY multisignatures. This greatly reduces proof size. Clients only need to verify the SNARK proof to validate many epoch transitions. The SNARK proof judiciously hides all intermediate state while enabling light client state sync. As the epoch messages themselves are generated by the Celo consensus protocol, the zkSNARK acts as an efficient light client proof system without having to revalidate every network block. Optimizations like composite hashing, batch verification and efficient SNARK arithmetic enable proof generation costing only ~$25 per day and verification in <1 second on mobiles. Plumo constructs optimized zkSNARK proofs to abstract complex blockchain state transitions into simple epoch messages. This allows the creation of highly efficient light client proofs to sync state on resource-constrained clients with strong integrity guarantees.
Breaking up the validity of the entire blockchain into chunks, recursively proving each chunk, and aggregating enables far superior efficiency and performance in light clients over non-recursive proofs. This makes light clients much more usable for average users verifying blockchain activity on personal devices with limited bandwidth and storage.
Rollups for Transactions
Transaction rollups involve batching/aggregating transactions off-chain and publishing an aggregated validity proof to mainchain. This can achieve orders of magnitude better transaction throughput compared to direct mainchain transactions.
Recursive SNARKs are very well suited for rollups since the core operation involves aggregating and condensing knowledge - exactly what recursive proofs provide. The prover can show "I have verified N transactions are valid and signed properly off-chain." Breaking this statement apart recursively leads to optimized rollup designs.
For example,
-
zkSync from Matter Labs uses this approach by proving "k transactions are valid AND I have a proof for N-k remaining transactions." Unfolding recursively allows arbitrary numbers of transactions with tiny proof sizes.
-
Hermez uses STARKs for efficient proof generation composed inside the FRI SNARK for optimized verification. This exploits complementary advantages of the two SNARK types in a recursive manner.
By batching the validity of numerous transactions into a single proof, rollups powered by recursive SNARKs achieve dramatic scalability, reduced fees, and high throughputs exceeding tens of thousands of TPS.
Mina protocol and Polygon Hermez demonstrate cutting-edge transaction rollup architectures benefiting from recursive proof logic. Let’s explore each in detail:
Mina Protocol and Transaction Rollups
Mina Protocol employs a novel approach called recursive rollups that uses recursive zkSNARK proofs to validate transactions off-chain and generate a succinct cryptographic representation of the ledger state.
-
Instead of individual transaction proofs, each Mina block contains a zk-SNARK proof that recursively validates all prior blocks in the chain. This creates a linked chain of SNARKs that efficiently validate integrity of the entire blockchain history.
-
By chaining SNARK validity proofs in each block, Mina compresses the ledger state to around 22 kb, which is simply the size of a single SNARK proof encoding the transactions since genesis. This allows easy synchronization of state.
-
The succinct ledger enables major scalability gains as resource costs of participation do not grow with more blocks and transactions. More economic activity has minimal impact on hardware needed to run nodes.
-
Each SNARK proof sequence certifies validity of contained transactions - that they correctly follow protocol rules and ledger state. However, full transaction correctness is not guaranteed.
-
zk-SNARK proofs ensure privacy as transactions are validated without revealing input data or intermediate state. Only validity metadata is exposed publicly.
Thus, Mina Protocol pioneers an innovative recursive SNARK architecture to compress ledger history into a succinct representation that maintains validity, scalability and privacy - unlocking the potential for decentralized and private transactions at scale. The recursive nature is integral to achieving efficiency gains relative to individual transaction proofs.
Polygon Hermez and Transaction Rollups
Polygon (formerly Matic Network) is a platform designed to scale Ethereum and improve its user experience without sacrificing security. Hermez is one of its scaling solutions. Here's how Polygon Hermez utilizes transaction rollups:
-
Polygon Hermez operates as a Layer 2 scaling solution on top of Ethereum. It aggregates multiple transactions into a single proof, known as a rollup, which is then submitted to the Ethereum main chain. This process reduces the overall gas fees and improves transaction throughput.
-
Hermez uses zk-rollups to bundle a large number of off-chain transactions into a single proof. This proof attests to the validity of all the transactions in the bundle and is submitted to Ethereum for final settlement.
-
By moving the computational and data storage requirements off-chain and only submitting proof to Ethereum, Hermez significantly reduces the load on the Ethereum network. This is crucial as Ethereum currently struggles with high gas fees and network congestion.
-
Hermez enables fast withdrawals from Layer 2 to the Ethereum main chain, which is a significant advantage over other L2 solutions where withdrawal times can be lengthy.
In both cases, the core approach is the use of zk-SNARKs to compress the data needed for verifying transactions. This compression facilitates transaction rollups, where many individual transactions are proven to be valid all at once, without the need for each to be processed individually by the main chain. The result is a system that can handle many more transactions per second than traditional blockchains, while also offering privacy and reducing the costs associated with transaction fees.
For both Mina and Polygon Hermez, the implementation of transaction rollups is a key component in their strategy to create scalable blockchain systems. These rollups provide a pathway to handle a vast number of transactions efficiently, which is a significant step towards the mass adoption of blockchain technology.
I believe this also hints at a broader trend - recursion acting as a primitive to not only compress knowledge, but also compress computational overhead. Verifying 10,000 transactions via rollups is monumentally faster than doing so individually on-chain. The exponential efficiency gains from proof composition unlock new scalability horizons.
Additionally, our research explains how these cryptographic innovations intersect with incentivization mechanisms and decentralization. Mina's tiny blockchain footprint enhances decentralization prospects by allowing ordinary nodes to participate. Meanwhile, Hermez inherits the security of Ethereum's base layer.
This demonstrates how the base incentive structures and ecosystem architectures co-evolve with new cryptographic constructs. Cryptography unlocks new possibilities in system design and performance. But fully realizing this potential requires holistic thinking across layers. Rollups form an integral part of the roadmaps for both Polygon and Mina as part of broader pushes for scalability and efficiency.
Finally, I believe there is tremendous potential in cross-pollination. As noted, Hermez connects to StarkWare's STARK ecosystem. Exploring synergies between SNARK and STARK constructions could yield further breakthroughs. Mina and Polygon may offer the first glimpse of recursive proof technologies permeating real-world blockchain infrastructure. But this likely marks only the beginning as these techniques spread across protocols and industries.
#2. Composability unlocked by recursive SNARKs
Typically zero-knowledge proofs allow a prover to demonstrate knowledge of some secret information to a verifier without revealing the actual underlying secrets. Recursive SNARKs take this a step further.
Using recursion, it becomes possible for the prover to demonstrate knowledge even if they themselves do not possess the complete underlying facts. The prover only has a fragment of the information, but can leverage other Trusted proofs to transitively compose knowledge proofs.
This powerful paradigm unlocks entirely new types of emergent decentralized applications with information flow across multiple parties, akin to privacy-preserving telephone games. Participants can jointly compute functions without fully disclosing inputs.
Recursive proofs enable a demonstration of the form "I know X is true" even if the prover does not have access to the complete basis for X. The prover may only have a subset of facts supporting X, but relies on other trusted proofs to fill gaps.
For example, consider a multi-step social graph relationship between Person A and Person Z, with intermediate connections through persons B,C,D etc. Person A can prove "I have a relationship link to Z" by showing:
-
A knows B
-
B has supplied proof of connectivity to Z
So A leverages B's separate proof compositionally without visibility into details of the intermediate hops. The transitivity holds as long as the individual proofs are Trusted in isolation. But now facts can be jointly validated without full disclosure. This expands possibilities for privacy-preserving applications.
Also, Recursive SNARKs really shine when implementing games or computational tasks that require hiding information. Participants have access to partial knowledge, make decisions based on that, receive outputs, and update state. But mechanisms preserve privacy constraints on what data gets revealed. For example, multi-party games like multiplayer poker where each player holds private cards combine public actions with hidden game state. Recursive proofs allow certifying correctness of actions without exposing underlying holdings across all intermediate steps. ideal for mental poker over networks.
Some other examples of such incomplete information games and protocols enabled by recursion:
-
Telephonic Applications: Recursive zero-knowledge proofs resemble telephone games, with participants modifying their state based on partial knowledge before propagating it onward. This gives a flavor of old-school mix networks with verifiable shuffles.
-
Mafia: Popular party games like Werewolf or Mafia require secretly assigned roles that influence public voting outcomes over time. Recursive proofs can credibly implement such social deduction without requiring a trusted third party.
-
Private State Channels: Enable efficient multi-step protocols between two parties who require privacy on intermediate states. Only final outcomes get published for verification instead of entire flow. Useful for gaming, financial exchanges and auctions.
In all cases, recursive proofs enable embedding deceit or secrecy within larger truthful constructs without visibility into intermediate building blocks for observers. This flexibility opens the design space for decentralized apps with creative informational constraints.
Recursive SNARKs fundamentally enhance the zero knowledge property from individual proofs to nested chains of proofs over time. Provers no longer need full visibility, just sufficient fragments that synergize with other Trusted proofs.
This mystery creates opportunities for new adversarial and cooperative games with enforced secrecy around intermediate states. Applications built atop recursive proofs start resembling verifiable relay networks or poker tournaments rather than static mathematical constructs.
The composability transfers knowledge reveals across compartmental boundaries without compromising overall system integrity. This ushers in a new generation of multi-party computation, privacy-conscious protocols and previously impossible games now made realizable.
While still nascent, recursive proofs lay the foundation for the imagination to stretch beyond micropayments and DeFi into decentralized apps with rich, dynamic information flow. The capacity to prove incomplete knowledge expands developer creativity in designing novel participant experiences.
Despite their advantages, recursive SNARKs are not without challenges. Two significant issues are data provisioning and computational overhead.
Data Provisioning:
-
Ensuring that all necessary data for proof verification is available and correctly formatted is a crucial aspect of implementing recursive SNARKs. As applications scale, the size and complexity of the data involved in generating proofs can become a significant challenge.
-
Data provisioning also involves ensuring the availability and integrity of the data, which can be particularly challenging in decentralized systems like blockchains.
Computational Overhead:
-
While recursive SNARKs reduce the verification time, the generation of proofs, especially in a recursive context, can be computationally intensive. This is due to the complex mathematical operations required to generate each proof and the additional complexity introduced by the recursive structure.
-
The computational overhead can become a bottleneck, particularly in systems with limited resources or in applications requiring real-time processing.
Trend toward modular & customizable SNARK architectures
Recursive SNARK constructions allow verifying proofs within proofs. This enables new capabilities like compression and zero-knowledge composability. However, current recursive schemes can still be quite rigid in their configurations. For example, the prover and verifier algorithms are often tightly coupled to optimize specific Proof parameters.
As adoption spreads across use cases like rollups, light clients and confidential transactions, the constraints and efficiencies desired are becoming more diverse. What suffices for governance proofs may be unsuitable for supply chains. One recursive architecture cannot serve all needs optimally.
This diversity parallels the pressure that drove enterprise software from monolithic systems to configurable microservices. Modular components with defined interfaces increased customizability. Cryptography now acknowledges similar forces demanding versatility - a movement away from monopolistic proofs toward specialized building blocks.
Emerging recursive proof ecosystems exhibit more modular designs allowing developers to better customize implementations by mixing and matching elements. Constraint engines, transparent setups and arithmetic libraries snap together into flexible recursive configurations.
Teams can also focus innovation on individual components like efficient inner product arguments purpose-built for aggregation. Modularity enables recombining these optimizations into recursive proof flows per application needs. Math primitives are no longer ossified.
Modular recursive schemes reflect zero-knowledge proofs coming of age - the existential need for specialization indexed to real problem spaces rather than mathematical elegance alone. As proofs permeate everyday processes, versatility enabled by modularity becomes mandatory rather than desired.
The overall vision is one of "proof Lego blocks" - where developers combine specialized building blocks that snap together securely via defined interfaces. This is seen as essential for the customization and versatility needed as zero-knowledge proofs get deployed for an exploding range of real-world demands. A reboot toward modularity aims to fuel the next stage of efficiency and scale.
References:
Thank you for reading through, and subscribe below for regular post updates.
I’d also appreciate it if you shared this with your friends, who would enjoy reading this.
You can contact me here: Twitter and LinkedIn.
Please also find the research I contribute to at L2 Iterative Ventures Substack for more detailed institutional insights.