<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Rize Labs on Medium]]></title>
        <description><![CDATA[Stories by Rize Labs on Medium]]></description>
        <link>https://medium.com/@RizeLabs?source=rss-ef372ba4553e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*7ENogOAx--nuci2cXCk6RA.jpeg</url>
            <title>Stories by Rize Labs on Medium</title>
            <link>https://medium.com/@RizeLabs?source=rss-ef372ba4553e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 07:29:37 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@RizeLabs/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[A framework for heterogenous proof aggregation]]></title>
            <link>https://medium.com/@RizeLabs/a-framework-for-heterogenous-proof-aggregation-28f2ea8ef96b?source=rss-ef372ba4553e------2</link>
            <guid isPermaLink="false">https://medium.com/p/28f2ea8ef96b</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[zkrollup]]></category>
            <category><![CDATA[rollup]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Rize Labs]]></dc:creator>
            <pubDate>Tue, 07 May 2024 14:00:22 GMT</pubDate>
            <atom:updated>2024-05-28T09:47:20.095Z</atom:updated>
            <content:encoded><![CDATA[<h3>Henosis: A framework for Avail to aggregate heterogenous ZK proofs</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iC7kqyBKDH8trXuIpaI8rg.jpeg" /></figure><h3>Introduction</h3><p>With the current focus on rollups in Ethereum, we will see thousands of them in the future, including both general-purpose and app-specific rollups. These rollups rely on Ethereum for security by settling their blocks on it and in future these rollups would start using Data Availability solutions like Avail DA or a Data Availability Committee on Ethereum.</p><p>In future, as the modular architecture becomes more mature, many of these rollups will shift towards a modular solutions for rollups, which offer benefits such as better finality, composability, and lower costs over time. However, the end-user experience of interacting with these rollups will fragment despite these advantages. Blockchain users today need interop solution in a world with just a few chains; increasing the number without fundamentally improving how these systems work together will complicate things further. Solutions like Avail Nexus try to solve this issue, where proof aggregation plays a significant role.</p><p>In this blog, we will first discuss proof aggregation and why we need proof aggregation. We will argue about the problem with current multi-chain communication (especially rollups) and how even having trust-less bridging will not help solve this problem in the long run. Especially if we need web2-like async communication between multiple rollups the way we have async communication between micro-services, the current architecture will not scale. We will also mention the bare minimum trust assumptions required for a rollup to interact with any other rollup regarding consensus, execution ordering, the validity of states, and the role ZK proofs play in this scenario.</p><p>In the next section, we will present a short overview of ZK recursion, explaining the difference between aggregation of proofs that can occur without recursion for homogenous proof composition and how recursion is required in aggregation for heterogeneous proof composition. Some pointers regarding various Snark and Stark recursion techniques are prevalent in the academic industry and might help the reader understand our approach better.</p><p>Finally, we will share some approaches we experimented with and some benchmarks. The main idea is to find an efficient and secure approach for heterogeneous proof aggregation. We are still in the experimentation phase, and this article is just an effort to mention some approaches we have taken and the problems we feel they have. There are still many proof aggregation systems(ex <a href="https://eprint.iacr.org/2022/1758.pdf">SuperNova</a>) and protocols(ex <a href="https://www.nebra.one/">Nebra</a>) out there that might be better, and we need to experiment with them to find the optimal architecture in terms of speed, efficiency and overall security.</p><p><strong><em>Prerequisite: </em></strong><em>Readers are preferred to have a basic understanding of </em><a href="https://z.cash/learn/what-are-zk-snarks/"><em>zk-snarks</em></a><em>, </em><a href="https://starkware.co/stark/"><em>zk-starks</em></a><em>, </em><a href="https://www.cryptologie.net/article/564/what-are-zkvms-and-whats-the-difference-with-a-zkevm/"><em>zkVMs</em></a>, <a href="https://ethereum.org/en/developers/docs/scaling/zk-rollups/"><em>zk-rollups</em></a>, <a href="https://ethereum.org/en/developers/docs/scaling/zk-rollups/#validity-proofs"><em>validity proofs</em></a> <em>and some Interactive Oracle Proof (IOP) based commitment schemes like </em><a href="https://eprint.iacr.org/2022/1216.pdf"><em>FRI</em></a><em> and </em><a href="https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf"><em>KZG</em></a><em>.</em></p><h3>WTF is proof aggregation?</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lf9vg2ffb2w3gwI9aQYbsQ.png" /><figcaption>Homogenous Proof aggregation</figcaption></figure><p>In simple terms</p><blockquote>Proof aggregation is a technique in which multiple zero-knowledge proofs, 𝜋1,𝜋2,…,𝜋𝑘 are combined into a single aggregated proof, 𝜋_agg​. This aggregated proof verifies the validity of all statements demonstrated by the individual proofs, significantly reducing the computational and storage requirements for verification processes.</blockquote><p>This method mainly benefits blockchain, in enhancing transaction throughput and scaling decentralized applications. However, generating an aggregated proof involves additional computational effort, which can introduce delays in achieving finality, especially in blockchain rollups.</p><h3>Why do we need proof aggregation?</h3><h4>Current bridging between rollups</h4><p>All those <a href="https://ethereum.org/en/developers/docs/scaling/zk-rollups/#validity-proofs">validity proofs</a> that get posted on Ethereum serve as a way to confirm transactions for these rollups, ensuring that a new rollup block is created upon fair execution of transaction. However, when one rollup needs to interact with another, it has to do so synchronously, leading to a poor user experience. Scaling blockchains with synchronous communication between rollups is hard to imagine. By synchronous communication, I mean that one rollup has to wait for confirmation on the Ethereum (L1) before any action can be taken in another rollup. In contrast, web2 architectures use asynchronous micro-services. For example, Amazon uses many backend micro-services, such as Visa processing and inventory management, that handle their tasks independently and interact with each other asynchronously.</p><p>The situation with the current rollup infrastructure is similar; seamless communication between them is crucial. The effectiveness of a modular world depends heavily on the messaging protocols that manage communication across different rollups. These cross-rollup communications often use bridges, and these bridges require minimal trust to match the security level of a traditional, unified blockchain. When bridges operate between rollups on the same Data Availability (DA) Layer, they don’t cross trust and security zones because they all rely on the same consensus and security rules that determine the order of transactions. However, for these bridges to be genuinely trustless, a roll-up must verify whether the actions were carried out correctly so it doesn’t have to depend on external assurances for these guarantees. Before this communication takes place, we need to consider many things regarding the trust assumptions of rollups using different DA layers, whether there can be async messaging between rollups, and how the state will be verified between various types of rollups. <strong>One thing you can remember is that whenever an L2 blockchain communicates with another L2, it must verify two things: first, establish transaction order, which can be ensured by DAS(Data Availability Sampling), and second, it should validate the processes to ensure its safety using state validity proof.</strong></p><h4>Trust guarantees are acquired through recursion.</h4><p>Consensus sets a chain’s established order of transactions. DA Layer gives rollups a consensus on the order of their transactions. This is a significant advantage for rollups sharing the same DA Layer. The same consensus rules determine the order of transactions for all rollups, including their own. This means that even if there is a reorganization (re-org) of the blockchain, the order of transactions for all involved rollups will follow this re-org.</p><p>To ensure these types of guarantees, we need inclusion proofs, completeness proofs, and validity proofs. An inclusion proof confirms that data is included in a DA block. A completeness proof ensures that the state transition has utilized all the transaction data it needs*, and a state validity proof verifies the correctness of the state transition.</p><p>We can check the correctness of these rollup blocks by verifying <a href="https://ethereum.org/en/developers/docs/scaling/zk-rollups/#validity-proofs"><strong>state validity proofs</strong></a>.</p><p>The challenge comes when we recognize that each rollup may have unique state transition functions, with design choices tailored to its specific domain. Validation of executions might depend on game theory, incorporating fraud proofs, or validity proof systems relying on zero-knowledge proofs (ZK proofs). Even within the ZK rollups, the proof systems may exhibit variation, ranging from Groth16 to PLONK. Rollups don’t need to know the specific details or functions of other rollups; they need to confirm that these functions were carried out correctly and understand the results that matter to them. Verifying all necessary transactions with just one proof would be a significant breakthrough. A verification hub that facilitates cross-chain communication while managing the technical specifics of different rollups would be ideal. <a href="https://www.availproject.org/nexus">Avail Nexus</a>, which is a custom ZK coordination rollup on top of Avail that consists of:</p><ul><li>Proof aggregation and verification layer</li><li>Sequencer selection/slot auction mechanism system.</li></ul><p>Nexus also submits the aggregated proof periodically to Ethereum and the Avail DA layer for verification. A custom module within Avail DA verifies the aggregate proof.</p><h3>A brief overview of ZK Recursion</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/810/1*odv5zUlJpE6pluTdp_l1ag.png" /><figcaption><em>How to think about self-recursive SNARKs (</em><a href="https://0xparc.org/blog/groth16-recursion"><em>source</em></a><em>)</em></figcaption></figure><h4>Recursive Zk proving with S{n,t}arks</h4><p>ZK proofs let us confirm that a specific computation was carried out correctly. The verification of a ZK proof is itself a computation and can be performed within another ZK circuit, a process known as recursion, which allows for more complex systems that can verify multiple proofs together. Recursion means verifying one zkSNARK proof within another. This enables provers to include more information in their proofs while keeping them succinct. The verification time of recursive zkSNARKs is comparable to that of non-recursive ones. Recursive zkSNARKs primarily enhance compression and composability.</p><p>Recursion allows information compression into proofs that remain verifiable in constant or polylogarithmic time. This makes them ideal for rollups, where they can efficiently compress a sequence of proofs. Traditionally, proving costs scale linearly with the number of constraints. However, with recursion, you can extend the proof to include more constraints without re-verifying everything from scratch, notably saving computational resources. This approach also helps manage practical limitations like circuit size and memory requirements, as smaller circuits can perform more extensive computations through recursive proofs.</p><h4>Aggregation of proofs</h4><p>The recursion of these ZK proof systems also enables “Aggregation” of proofs, which means replacing<strong><em> multiple ZK proofs π1, π2, …, πk with a single aggregated proof π_agg, which implies the validity of all statements otherwise demonstrated by the individual proofs πi</em></strong>.</p><p>I love the simple explanation from Tomas Krnak in his <a href="https://www.maya-zk.com/blog/proof-aggregation">blog</a>:</p><blockquote>Let’s say that we have two transactions, t1 and t2, attested by two proofs, p1 and p2. A recursive SNARK allows us to generate a single proof for the claim, “There exist valid proofs that prove the validity of t1 and t2.” We have just compressed proofs p1 and p2 into a single proof! Furthermore, this procedure can be repeated, and thus, an unlimited number of proofs can be aggregated into one.</blockquote><p>We’ve been focusing on verifying popular heterogeneous proof systems used widely in the industry. The problem with most heterogeneous proof systems is that they don’t share the same verification method. Two PlonK circuits can share the same verification key if their public input lengths are equal and verifiers perform nearly identical work(even though their sizes are unequal). Some works, like <a href="https://eprint.iacr.org/2022/1758.pdf">SuperNova</a>, build efficient non-uniform proof aggregation schemes capable of aggregating proofs from different circuits into a single proof.</p><h3>Recursion in different types of proof systems</h3><h4>Pairing based SNARK recursion</h4><p>A significant technical advantage of these recursive setups is their flexibility to combine different proof systems and arithmetizations, harnessing the best features of each. SNARKs, which use pairing or <a href="https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html">KZG commitment-based proofs</a>, are fast to verify and have small proof sizes, making them ideal for verification on Ethereum’s EVM. <strong><em>A SNARK is considered recursive if it can efficiently prove the validity of its proofs.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*tKolCPMDev0wUZdkCzMszQ.png" /><figcaption><strong>A simple KZG proof verification equation (</strong><a href="https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html"><strong>source</strong></a><strong>)</strong></figcaption></figure><p>In the above KZG equation, p(x) is a polynomial that the prover wants to prove to the verifier, ‘z’ is a random point of opening given by the verifier to the prover, 𝑝(𝑧)=𝑦 and 𝜋=[𝑞(𝑠)]. Remember, the commitment to the polynomial 𝑝(𝑋) is defined as 𝐶=[𝑝(𝑠)]. An important point is the group element in which these terms are used. 𝜋 &amp; C-[y] is a G1 group element and [s-z] &amp; H is G2 group element. Read “Preparing for Pairings” in this excellent <a href="https://research.metastate.dev/plonk-by-hand-part-1/amp/">blog</a> to know more about them. A similar verification step takes place in groth16.</p><p>While SNARK verification costs are often considered constant, the reality is that for groth16, the cost scales with the number of public inputs. This becomes more evident when verifying a proof within another SNARK, as each additional public input increases the proving cost. To address this issue, a simple technique can be used, as mentioned by <a href="https://0xparc.org/blog/groth16-recursion">Yi Sun</a>, where all intended public inputs are instead treated as private within the circuit, and the only public input is a hash of these private inputs. The circuit verifies that this hash matches the one provided as the public input.</p><p>We have done much work on SNARK aggregation techniques, which don’t use recursive pairing verification. Some well-known homogenous SNARK aggregation techniques are:</p><p><a href="https://eprint.iacr.org/2021/529"><strong>SnarkPack</strong></a> is a sophisticated aggregation scheme for Groth16 proofs, characterized by their compactness and consisting of just three elliptic curve points (<em>A</em>,<em> B</em>,<em> C</em>). Verifying these proofs involves a pairing operation, checking the equation <em>e</em>(<em>A</em>,<em> B</em>)=<em>Y</em>⋅<em>e</em>(<em>C</em>,<em> D</em>) where <em>Y</em> encodes public inputs and <em>D</em> is a fixed elliptic curve point in the G2 curve.</p><p>Aggregating <em>k</em> Groth16 proofs, SnarkPack introduces efficiency by combining individual proof checks into one. This is achieved by forming a random linear combination of the proofs using a scalar <em>r</em>, simplifying the verification to a single equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k5vV-9vylGsqC8r31u-kOQ.png" /></figure><p>This method leverages Inner Product Arguments (IPA) to efficiently manage computational load, resulting in logarithmically scaled proofs and verification times.</p><p><a href="https://eprint.iacr.org/2022/1352"><strong>aPlonK</strong></a> is an advancement within the PlonK protocol family, specifically designed to enhance efficiency by reducing proof size and verification time when handling multiple statements in a batch. This improvement is achieved by utilizing a multi-polynomial commitment scheme (MPCS), a useful primitive that extends traditional polynomial commitment schemes to handle multiple polynomials simultaneously. The proof size and verification complexity scale logarithmically with the number of aggregated statements, which significantly optimizes performance for applications like blockchain rollups where verification speed is critical.</p><p>Note: <em>The recursive proof is not verified in the above two techniques, and aggregation only occurs.</em></p><p><strong>Limitations of SNARK aggregation</strong> <strong>through recursion</strong> include the implementation of bilinear pairings check, which is done in groth16(3 pairings and ‘l’ multi-scalar multiplications where ‘l’ is the number of public inputs in the circuit) and Plonk(2 pairings, and 18 G1 group operations)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*dNbDfiuJdZbILGHp" /><figcaption><a href="https://eprint.iacr.org/2019/953.pdf">PLONK final verification equation</a></figcaption></figure><p>is extremely constraint-heavy inside a circuit. zk-pairing mentions that even after all the optimizations, it’s close to ~20 million constraints per pairing check, which results in 250 seconds proving time on a beefy server (32-core 3.1GHz, 256G RAM). Which is quite a lot and far from the reach of client-side proof on laptops/desktops!</p><h3>Stark Recursion</h3><p>In contrast, STARK proofs are more extensive and involve verifying Merkle Inclusion paths. Mostly, STARKs use AIR arithmetization, which is well-suited for proving state machine executions but tends to be costly to verify. By using recursion, one can generate a STARK proof for a state machine’s execution and then verify this STARK proof within a pairing/KZG Snark. This results in a SNARK proof that is much cheaper to verify. Most ZK Rollups in production use ZK Starks to generate proofs as they offer better concrete performance and efficient recursion.</p><p>In Stark recursion, multiple FRI proofs are usually batch-combined and verified all at once.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MA9odQ8kvYmFam9VZp7Ijg.png" /></figure><p>where di is the DEEP polynomials, w_RAP is the total trace polynomials, and the prover uses the alpha FRI parameter.</p><p>FRI Batching is a technique where you combine multiple trace polynomials into one single polynomial. This reduces the amount of computation and communication needed for each commitment. By grouping polynomials, the verifier can check the commitments more efficiently while keeping the protocol secure and intact. FRI Batching uses methods like mixing and splitting to merge several polynomials into one commitment, making processing and validation smoother. This method is beneficial when you need to handle many commitments at once because it uses resources better and enhances the overall performance of the protocol. Another structure used in this context is the ZK tree, which uses a binary tree format to verify proofs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qLefOezM4bA-nfAimjtjiQ.png" /><figcaption><strong><em>Proof Recursion used by many ZK systems (</em></strong><a href="https://www.youtube.com/watch?v=wkIBN2CGJdc&amp;embeds_referring_euri=https%3A%2F%2Fwww.google.com%2Fsearch%3Fq%3Dpaulgafni%2Bzk%2Bsummit%26sourceid%3Dchrome%26ie%3DUTF-8&amp;source_ve_path=Mjg2NjY&amp;feature=emb_logo"><strong><em>Source</em></strong></a><strong><em>)</em></strong></figcaption></figure><p>At its core, zkTree uses recursion to combine many user proofs into one compact proof. This single proof can be checked quickly and costs much less than traditional methods. Its hierarchical design significantly cuts down on the computing and storage demands on blockchain networks like Ethereum’s EVM by making proofs smaller and allowing batches of transactions or data validations to be processed together.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gtdttKfIPLqw5o5vscmKeg.png" /><figcaption><strong>ZkTree </strong><a href="https://polymerlabs.medium.com/introducing-zktree-a-zk-recursion-tree-with-zkp-membership-proofs-571a244e3169"><strong><em>Source</em></strong></a></figcaption></figure><p>STARKs are faster for recursion as there are no pairing checks, and if we choose a proper hashing function, we can reduce the number of constraints in the verification.</p><h4>Folding schemes</h4><p><a href="https://eprint.iacr.org/2021/370.pdf">Nova</a> framework advances recursion in cryptographic proofs by introducing “folding.” Unlike the Halo framework, which delays verification, Nova delays the computation of (optional) succinct proofs. Folding allows a prover to amalgamate two witness values, <em>w</em>1​ and <em>w</em>2​, into a new witness <em>w</em>3​ of equivalent size, ensuring that validating <em>w</em>3​ simultaneously confirms <em>w</em>1​ and <em>w</em>2​.</p><p>Nova predominantly facilitates <a href="https://link.springer.com/chapter/10.1007/978-3-540-78524-8_1">Incremental Verifiable Computation (IVC)</a>, wherein each computation step involves the IVC prover integrating a previous witness with a new one and validating the merge. This guarantees that at any stage, verification of the most recent IVC proof confirms the accuracy of all preceding computational steps.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hcVyEXwXSW-jqmCGrN-PCA.png" /><figcaption>Folding based Non interactive proof aggregation</figcaption></figure><p>In proof aggregation within IVC, each computational iteration validates a segment of a batch proof, ensuring the proof size remains constant regardless of the number of incremental steps. Nevertheless, IVC proofs can still be substantial, with their size directly proportional to the circuit size of the IVC step function. In practical scenarios, the IVC process can halt at a certain point, after which a SNARK proof is generated from the final IVC output. This SNARK proof is compact and easily verifiable, allowing the IVC system to generate proofs without depending on the SNARK process.</p><h3>Current approach</h3><p>To reiterate the problem we are trying to solve:</p><p><em>We want to aggregate these heterogeneous proofs from rollups(usually KZG pairing-based proofs)into a single ZK proof and then post that to the Nexus in Avails architecture.</em></p><p>At a high level, the current solution mainly relies on zkVMs for verification and consists of recursively verifying all the proofs inside the zkVM. The proofs are now aggregated together inside the zkVM environment into a single proof. Our main goal is to standardize these proofs into a common system through recursive verification to simplify their aggregation.</p><p>The SNARKs-proof land has various types, depending on the platform. As mentioned above, Polygon ZK-EVM uses a system called <a href="https://github.com/0xPolygonHermez/zkevm-contracts/blob/main/contracts/verifiers/FflonkVerifier.sol">Fflonk</a>, and zk-sync uses a modified version of Plonk called <a href="https://github.com/matter-labs/era-boojum">Boojum</a> for their operations. The on-chain contract, which is the settlement contract of the rollup on Ethereum L1(also called the bridge contract), verifies these proofs and updates the state of the rollup. Ethereum L1 is often called the “settlement layer” for rollups because the L1 smart contract supposedly decides the canonical rollup chain. It is from these contracts that we fetch these proofs through a relayer.</p><p>As mentioned above, in these KZG-based systems, there is the need for final pairing checks to ensure the proof’s validity, which is performed by the platform’s on-chain verifier smart contract. We plan to convert all these fetched proofs, KZG-based(and <a href="https://book.starknet.io/ch03-06-solidity-verifier.html#current-architecture-multiple-smart-contracts">STARK-based from StarkNe</a>t in future), into a standard format. Currently, this ordinary format is generated using the zkVM, which internally uses the standard AIR-FRI protocol, <a href="https://arxiv.org/abs/1903.12243">DEEP-ALI</a>, and the batched <a href="https://ieeexplore.ieee.org/document/9317990/">FRI protocol</a>. The zkVM Prover uses the constraints and the execution trace to generate the validity polynomial ‘<strong><em>f</em>’</strong> validity, then uses the validity polynomial to construct the validity witness <strong><em>w</em></strong> and then sends the commitment to <strong><em>w</em></strong> to the Verifier.</p><p>These fetched proofs from rollup L2 contracts on L1 are then verified within the zkVM because the verification, as mentioned above, is a process and a computation that can be modelled as an execution trace in a VM. The prover submits proof, along with the appropriate public inputs, and if verified correctly, it confirms the entire computation process. As mentioned above, a significant challenge in verifying KZG-based SNARKs is that pairings require many complex operations related to elliptic curves. For elliptic curve arithmetic on a non-native field, optimizations used in big integer arithmetic need to be applied and adjusted for some specific curve.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-Ym0-EEvA7Nr7qaOGCI7AA.png" /><figcaption>Current design and components in a binary proof aggregation</figcaption></figure><p>Our architecture prioritizes provable computation capabilities rather than the zero-knowledge aspect (currently, NO zk aspect). We have two modules:</p><ul><li>Common proof generation(Converter): It converts all the input proofs to the proofs generated by zkVM.</li><li>Aggregation of STARK(Aggregator): Most of the zkVMs (SP1, Jolt and Risc Zero) are currently producing STARK proofs, and this component consists of composing them recursively.</li></ul><p>The zkVM proving component currently utilizes Risc Zero’s Bonsai to recursively verify the underlying rollup proof from L1, which is fetched from the relayer. A converter/adapter component will receive the proofs from the rollups and then generate the STARK proofs. This architecture addresses the challenge of aggregating heterogeneous proof systems from different rollups on Layer 1, which often employ varying versions of pairing/KZG-based proofs. One key thing to note is that the public inputs of different proofs need to be appropriately handled and passed down to the architecture used in the Avail Nexus.</p><p>We can implement FRI batch-proof aggregation. A notable limitation of the FRI polynomial commitment scheme is its lack of homomorphic additivity, unlike KZG-based schemes, which complicate the direct aggregation of FRI proofs. To address this, one solution is to leverage Plonky2’s fast recursion capability for FRI proofs or to facilitate the verification of the STARK proof directly within the zkVM. Risc Zero has provided a STARK verifier via <a href="https://www.risczero.com/blog/proof-composition#:~:text=RISC%20Zero%27s%20proofs%20are%20packaged,a%20given%20receipt%20was%20verified.">composition</a>; it allows for the efficient recursive verification of STARK proofs in an AIR builder. This internal verification streamlines the process, enabling a more integrated and seamless approach to handling <strong>stark</strong> proofs within our architecture.</p><p><strong><em>Note: </em></strong>It’s good to mention that we experimented with one more approach earlier that we didn’t end up using. The idea was that after we get the standard zkVM proofs, we recursively convert them to a pairing-based proof by verifying the zkVM proof inside the circuit. Eventually, those pairing-based proofs can be aggregated together. This is similar to what we explained above in STARK aggregation. Earlier, we used the Risc Zero Stark to Snark converter for groth16 proof generation and <a href="https://github.com/axiom-crypto/snark-verifier/tree/main">the Snark-verifiers</a> library by PSE( and modified by Axiom) for aggregating the generated groth16 proofs. We wrote a groth16 proof verifier in Halo2-lib, which gives us the Halo2 Plonk proof, which the Aggregation chip** requires. The main problem with this approach was the time lag and computation overhead in STARK to SNARK conversion, as STARK proofs are large and expensive to verify.</p><h3>Polygon Zk-EVM and Zk-Sync Benchmarks</h3><p>We’ve started with Polygon’s zk-EVM and zkSync for our project. Polygon zk-EVM uses a proving system called <a href="https://eprint.iacr.org/2021/1167">FFLONK</a> to convert STARK proofs to SNARK proofs, while zkSync has its own <a href="https://github.com/matter-labs/era-boojum">modified version of PLONK </a>for the same purpose. The inner dynamics of these proof systems is a topic itself for another blog(i have written about <a href="https://medium.com/@rishotics/notes-on-efficient-polynomial-commitment-schemes-and-fflonk-501ea53df6ef">fflonk</a>; will cover mPlonk later)</p><p>One interesting thing to note is, that both proving schemes use the Keccak hash function for Fiat Shamir heuristic, which makes verifying proofs within the circuit expensive due to the high number of required computations. Specifically, FFLONK must perform 5 hash operations, whereas zkSync’s modified PLONK requires 99 hash operations. Because of this FFLONK verification has far fewer constraints and less overhead compared to zkSync’s modified PLONK, making it a more optimized solution for verification. We ran the RISC Zero benchmarks using BonsaiBonsai and the SP1 benchmarks using <em>c6a.32xlarge 128 vCPU with 256 GB RAM</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GlgOfmMlFgq7M1p74jZLuQ.png" /><figcaption><strong>Risc Zero</strong></figcaption></figure><p><strong>Important<em>: </em></strong><em>These numbers are for a very crude implementation of fflonk and modified plonk verification, which could be greatly improved with precompiles, acceleration, and reducing copy constraints.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*D5flAqfI2Zm6OefamLG9nQ.png" /><figcaption><strong>SP1</strong></figcaption></figure><p><em>We also tried running benchmarks on SP1(zkVM by Succinct Labs) on a c6a.32xlarge machine but as Bonsai is currently using GPU acceleration and proof composition the results cannot be compared for benchmarks. However, we will add the updated results as soon as the SP1 team adds the support.</em></p><p><strong><em>Github code link: </em></strong><a href="https://github.com/availproject/Henosis">https://github.com/availproject/Henosis</a></p><h3>Conclusion</h3><p>Finally, the following work is experimental, and we are still improving. The idea for homogenous proof aggregation differs from something used across the industry. It’s the heterogeneous proof aggregation that opens up a new domain of applications. The goal for atomic composability is the north star, which Avail Nexus aims for, and validity-proof aggregation is one part of the whole architecture.</p><p><em>If you find any mistakes or find any unexpected results, feel free to reach out to me on my Telegram account @rishotics. I’m keen to fix any inaccuracies to make sure the approach is reliable and thorough.</em></p><h3>Acknowledgments</h3><p><em>This work would not have been possible without feedback and suggestions from </em><a href="https://twitter.com/anuragarjun"><em>Anurag Arjun</em></a><em>, </em><a href="https://twitter.com/prabalbanerjee"><em>Prabal Banerjee</em></a><em>, </em><a href="https://twitter.com/vibhu_rajeev"><em>Vibhu Rajeev</em></a><em>, and many from Avail’s team. Special thanks to </em><a href="https://twitter.com/Paul_Gafni"><em>Paul Gafni</em></a><em>, </em><a href="https://twitter.com/jtguibas"><em>John Guibas</em></a><em>, </em><a href="https://twitter.com/NicolasRamsrud"><em>Nicolas Ramsrud</em></a><em>, </em><a href="https://twitter.com/yush_g"><em>Aayush </em></a><em>, </em><a href="https://twitter.com/0xAbix"><em>Ayush</em></a><em>, </em><a href="https://twitter.com/Rahul__Ghangas"><em>Rahul</em></a><em> and others for reviewing and giving valuable feedback.</em></p><h3>References</h3><p><em>[1]: </em><a href="https://eprint.iacr.org/2021/1167.pdf"><em>fflonK: a Fast-Fourier inspired verifier efficient version of PlonK</em></a></p><p><em>[2]: </em><a href="https://eprint.iacr.org/2019/953.pdf"><em>PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge</em></a></p><p><em>[3]: </em><a href="https://eprint.iacr.org/2020/081.pdf"><em>Efficient polynomial commitment schemes for multiple points and polynomials</em></a></p><p><em>[4]: </em><a href="https://alinush.github.io/2020/05/06/aggregatable-subvector-commitments-for-stateless-cryptocurrencies.html#aggregating-proofs-into-subvector-profs"><em>Aggregatable Subvector Commitments for Stateless Cryptocurrencies from Lagrange Polynomials</em></a></p><p><em>[5]: </em><a href="https://blog.availproject.org/the-avail-vision-accelerating-the-unification-of-web3/"><em>Avail’s Vision: The unification layer for web3</em></a></p><p><em>[6]: </em><a href="https://github.com/axiom-crypto/snark-verifier/tree/main"><em>Axiom: Snark Verifier</em></a></p><p><em>[7]: </em><a href="https://eprint.iacr.org/2023/869"><em>UniPlonk: Plonk with Universal Verifier</em></a></p><p><em>[8]: </em><a href="https://blog.lambdaclass.com/proof-aggregation-schemes/"><em>Proof aggregation schemes: SnarkPack and aPlonk</em></a></p><p><em>[9]: </em><a href="https://www.youtube.com/watch?v=wkIBN2CGJdc"><em>ZK10: FRI-based recursion with a Groth16 Wrapper — Paul Gafni</em></a></p><p><em>[10]: </em><a href="https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html"><em>KZG polynomial commitments</em></a><em> by Dankard</em></p><p><em>[11]: </em><a href="https://dev.risczero.com/proof-system/stark-by-hand#lesson-10-mixing-for-fri"><em>STARK by Hand</em></a></p><p><em>[12]: </em><a href="https://dev.risczero.com/proof-system-in-detail.pdf"><em>RISC Zero zkVM: Scalable, Transparent Arguments of RISC-V Integrity</em></a></p><p><em>[13]: </em><a href="https://blog.lambdaclass.com/how-to-code-fri-from-scratch/"><em>How to code FRI from scratch</em></a><em>?</em></p><p><em>[14]: </em><a href="https://github.com/matter-labs/era-boojum"><em>Boojum, the scariest SNARK implementation</em></a></p><p><em>[15]: </em><a href="https://eprint.iacr.org/2016/260.pdf"><em>On the Size of Pairing-based Non-interactive Arguments</em></a><em>?</em></p><p><em>[16]: </em><a href="https://arhat.mirror.xyz/btitpImDQ8m350r4dxBGQHc8sCBUrcdDm3-uiwsrwA0"><em>zkProofs &amp; Recursive SNARKs: Arhat, L2IV</em></a></p><p><em>[17]: </em><a href="https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf"><em>Constant-Size Commitments to Polynomials</em></a><em> and Their Applications</em></p><p><em>[18]: </em><a href="https://whitepaper.alignedlayer.com/"><em>Aligned Layer: universal verification layer</em></a></p><p><em>[19]: </em><a href="https://github.com/privacy-scaling-explorations/snark-verifier"><em>PSE: Snark Verifier</em></a></p><p><em>[20]: </em><a href="https://medium.com/@rishotics/notes-on-efficient-polynomial-commitment-schemes-and-fflonk-501ea53df6ef"><em>Notes on efficient polynomial commitment schemes and fflonk</em></a></p><p><em>[21]: </em><a href="https://polymerlabs.medium.com/introducing-zktree-a-zk-recursion-tree-with-zkp-membership-proofs-571a244e3169"><em>Introducing zkTree: a zk recursion tree with ZKP membership proofs</em></a></p><h3>Footnotes</h3><p>*completness proof means that we are making sure that all the data that is posted on the Avail DA is used for the state transition by the rollup to generate the validity proof.</p><p>**Inside the aggregation chip the costly pairing check is deferred till the last and we aggregate the pairings using a Random Linear Combination (RLC) of the pairing values of all the SNARKS available with us.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=28f2ea8ef96b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How do intent-based systems improve the efficiency of execution?]]></title>
            <link>https://medium.com/@RizeLabs/how-do-intent-based-systems-improve-the-efficiency-of-execution-64c8b379cb6a?source=rss-ef372ba4553e------2</link>
            <guid isPermaLink="false">https://medium.com/p/64c8b379cb6a</guid>
            <category><![CDATA[solver]]></category>
            <category><![CDATA[account-abstraction]]></category>
            <category><![CDATA[execution]]></category>
            <dc:creator><![CDATA[Rize Labs]]></dc:creator>
            <pubDate>Wed, 27 Sep 2023 11:41:31 GMT</pubDate>
            <atom:updated>2023-10-04T14:52:10.259Z</atom:updated>
            <content:encoded><![CDATA[<h3>Past Developments</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NDn5DPLotZ6vhJ5ouy3gVg.png" /><figcaption>architecture diagram</figcaption></figure><p>With the increased focus on improving UX for the web3 systems. Intent paves the way that account abstraction and other developments in the ecosystem set out to solve. Right now, There’s no common way to handle Intents in Ethereum. In our latest <a href="http://ethresear.ch/">ETH Research</a> post: “<a href="https://ethresear.ch/t/a-decentralised-solver-architecture-for-executing-intents-on-evm-blockchain/16608"><strong>A decentralised solver architecture for executing intents on EVM blockchain</strong></a>” we introduced a new idea called Abstracted Transaction Objects (ATOs). Think of ATOs as containers that hold specific details about what users want. For instance, if a user intends to execute a complex DeFi operation involving multiple token swaps and liquidity provisions, the ATOs for this intent will have multiple <strong>ATO</strong>ˢʷᵃᵖ and other DeFi operation-specific ATOs. A central figure called a driver, sends these ATOs to a group of experts (solvers) who figure out the best way to make these intents happen. These solvers give scores based on how well they meet the user’s needs, and the best solution is chosen based on a measure called Degree of Expectation (DoE). By having many solvers work together, we ensure the best solutions are found, there’s no unfair blocking. And in return solvers receive the incentives for providing the solution.</p><h3>Discussed Optimization technique</h3><p>In our discussion, we delved into the methods solvers employ to determine the best execution route for a user’s ATO. A few key takeaways include:</p><p>Solvers heavily rely on a range of resources, tapping into multiple dexes, integrations, liquidity pools, and protocols. This vast network assists them in determining the most efficient pathway for executing user transactions.</p><ul><li><strong>Exclusive Integrations:</strong> By forming partnerships with specific dexes and liquidity platforms, solvers gain a distinctive edge, enhancing their ability to unearth optimal solutions.</li><li><strong>Path Discovery:</strong> A significant portion of the solver’s strategy is anchored in path discovery. They’re committed to navigating through various routes, akin to a traveler seeking the best path to a destination.</li></ul><p>An intriguing facet is the potential interplay between different ATOs. In certain instances, ATOs might complement each other, especially if they’re related to identical operations. Such synergies present solvers with unique opportunities, allowing them to capitalize on these complimentary asset requirement situations.</p><h3>Complementary Asset Requirements</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1mYfxPRvyP3aASHwtkkkAg.jpeg" /><figcaption>ordering and bundling of ATOs</figcaption></figure><h4>Approach 1</h4><p>We’re actively venturing into various avenues to bolster complementary asset requirement discovery within our infrastructure. One promising approach we’re considering is to empower solvers with the capability to detect complementary asset requirements from the bundles of Abstracted Transaction Objects (ATOs) solvers receive for resolution. To shed some light on this, recall our previous discussion where we mentioned that a driver disseminates these ATO bundles to solvers. Each of these bundles is uniquely tailored for a specific operation. For instance, a bundle build for ‘<strong>swap</strong>’ operation is dispatched to solvers who specialize in swapping domain, much like others might specialize in bridging. Now, imagine a scenario where this ‘<strong>swap</strong>’ bundle contains two ATOs: one looking to swap 2 ETH for 2000 USDC and another aiming to do the exact opposite. This presents a golden opportunity for solvers to recognize a perfect complementary asset requirement opportunity where solvers could propose a direct solution: sending 2 ETH from the user of the first ATO to the owner of the second and vice versa with the 2000 USDC, thus fulfilling both intentions seamlessly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3aRrEVeXdLAmD9On5BBjnA.png" /><figcaption>dp based complementary asset requirement discovery</figcaption></figure><h4>Approach 2</h4><p>Another approach that can be explored in situations requiring complementary assets arises. When we send the entire set of ATOs (as we previously said intents are nothing but a set of ATOs) to the solvers. In the previous approach, we executed the ATOs in parallel. This is necessary because the state of the current ATO depends on the previous ATO state.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/509/1*k1Yrt1PncXfDK4qPCOShVw.png" /></figure><p>Sending the set of [ATO] forming an Intent to a solver provides the advantage of having the full context for the Intent, enabling the solver to form a multi-domain constraint satisfaction problem to find complementary asset requirement solutions. Basically, we could visualize this approach as a dynamic programming-based approach in which the solver could start iterating over the ATOs to find the solution, and while iterating it would also remember the ATO along with its solution, and once the solver finds an ATO which could be satisfied by any previous ATO solver has seen. Now solver has an opportunity to construct a complimentary asset requirement solution for both those ATOs. However, a potential disadvantage is that the solver needs to be a generalized solver and should be prepared to provide solutions for all the registered operations in the protocol.</p><h3>Concluding</h3><p>Utilizing complementary asset requirements discovery streamlines user transactions by eliminating the need to navigate multiple protocols or incur extra fees. Protocols like the CoW protocol and Anoma counter-party discovery nodes are leading in adopting this approach. This progress is promising, and by integrating path discovery with complementary asset requirement discovery, solvers can efficiently identify optimal execution routes. Our team is actively researching ways to enhance solver capabilities in addressing user ATOs, so stay tuned for more updates!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=64c8b379cb6a" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>