<?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 Horizen Labs Tech on Medium]]></title>
        <description><![CDATA[Stories by Horizen Labs Tech on Medium]]></description>
        <link>https://medium.com/@horizenlabs-tech?source=rss-b632385be288------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*2e1CFEFbh2j6LERMpDB-Aw.png</url>
            <title>Stories by Horizen Labs Tech on Medium</title>
            <link>https://medium.com/@horizenlabs-tech?source=rss-b632385be288------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 17:42:50 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@horizenlabs-tech/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[Verifiable Federated Learning: Verifying Training, Data Use, and Aggregation]]></title>
            <link>https://medium.com/horizen-labs/verifiable-federated-learning-verifying-training-data-use-and-aggregation-2343a5f78113?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/2343a5f78113</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[federated-learning]]></category>
            <category><![CDATA[zkverify]]></category>
            <category><![CDATA[vfl]]></category>
            <category><![CDATA[verification]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Thu, 05 Mar 2026 17:57:33 GMT</pubDate>
            <atom:updated>2026-03-05T18:02:50.880Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WUx9uESJ74zdAJ8oTGcBjA.png" /></figure><h3>TL;DR:</h3><p>Federated Learning keeps data private, but it still relies on trust. Clients or aggregators can cheat, poison updates, free-ride, or tamper with results. <strong>Verifiable Federated Learning (VFL)</strong> adds proofs (via zero-knowledge proofs and/or trusted execution environments (TEEs)) so parties can verify data usage, training behavior, and aggregation correctness.</p><p>Today, <strong>v</strong>erifying aggregation is the most practical/near-term win, while full verifiable training is still expensive and hard. Blockchains can act as a public verifier + audit log, and <a href="https://zkverify.io/">zkVerify</a> can make proof verification dramatically cheaper, improving real-world feasibility.</p><h3>A Journey Into Verifiable Federated Learning</h3><p>We are currently living in the AI era and, as everyone of you probably knows, AI products are enabled thanks to Machine Learning models. Now, as a company, we particularly care about the privacy of data, and it has turned out that a specific field of Machine Learning, namely Federated Learning, is of particular interest.</p><p>Let’s consider a scenario where multiple entities need to train a common model: with the classic ML approach, these entities will send the data to a resourceful server performing the training on this merged dataset. This is fine if the datasets don’t contain sensitive information or if we consider the server as a trusted entity that’s not curious, but this is a strong assumption. What happens instead in those scenarios where the entities are not willing to share the dataset with the training server? Just to mention a couple, take into consideration healthcare and finance.</p><h3>Federated Learning 101: Clients, Aggregator, Rounds</h3><p>Well, Federated Learning is the answer.</p><p>This is a Machine Learning approach introduced by Google in 2016, where every client trains the same model locally, and these partial local models are sent to an aggregator, which aggregates them, obtaining a global model. This global model is then checked against a stopping criterion that, if met, yields the final model; otherwise, it will be redistributed and another round of training will take place, starting from that model and the same dataset.</p><p>Federated Learning framework, for a general round t:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/718/1*2SyNCf3en-_m_VC53jaGfg.png" /><figcaption>Federated Learning framework, for a general round t</figcaption></figure><p>Where C(<em>i</em>) denotes client i, D(<em>i</em>) denotes the dataset of client i, 𝜃(<em>i,t</em>) denotes the weights of client i at round t, and 𝜃(<em>global,t</em>) denotes the resulting model after the aggregation at round t.</p><p>It is clear how, in this framework, the privacy of the datasets is preserved, as they never leave the clients’ machines.</p><h3>The Catch: More Parties, Bigger Attack Surface</h3><p>This vanilla framework, per se, already offers these strong privacy guarantees, but there are some nuances, and one of these is that since many entities are involved, the attack surface is increased. The following are some of the most well-known attacks:</p><ul><li><strong>Inference attacks and gradient inversion attacks</strong>: these classes of attacks make it possible to obtain information about the dataset starting from the gradients. This turns out to be nicely mitigated by enforcing the gradients not to be in clear once sent to the aggregator. The main mitigation techniques are differential privacy and secure aggregation.</li><li><strong>Data/Model poisoning attacks</strong>: it is possible that the entities try to alter the global model by introducing biases through their gradients or compromising its integrity. This can be mitigated by the aggregator checking properties of the gradients, so this would require sending them in the clear, falling back to the inference and gradient inversion attacks. <em>Smarter mitigations?</em></li><li><strong>Global model tampering</strong>: the aggregator could tamper with the aggregated model. <em>Mitigations?</em></li><li><strong>Selective dropping</strong>: the aggregator could discard some of the clients’ updates. <em>Mitigations?</em></li><li><strong>Free riding</strong>: clients could attempt to obtain the global model without participating in the FL protocol. <em>Mitigations?</em></li></ul><h3>Enter VFL: Add Verifiability With ZK Proofs + TEEs</h3><p>As you can see, there are many attacks where the central point is the lack of trust concerning the entities; specifically, we can’t be sure that they are behaving as they should, following the protocol specifications.</p><p>But notably, it has been shown in many research efforts that a way to mitigate part of those classes of attacks is by integrating verifiable technologies into the vanilla federated learning framework, obtaining a sounder framework called Verifiable Federated Learning. These technologies are <em>zero-knowledge proofs</em> and <em>trusted execution environments</em>, the former relying on cryptographic assumptions, the latter relying on hardware assumptions.</p><p>Both of them come with advantages and disadvantages, but their integration within the FL framework can really strengthen behavioural guarantees.</p><h3>State of the Art: What Recent Research Focuses On (2023–2026)</h3><p>This is a real state-of-the-art topic in the verifiable computing field, and we managed to make a systematization effort by analyzing 13 papers that tried to tackle this problem. These papers were all published from 2023 to 2026; in the following two comprehensive tables, we divide them by the technologies being used.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*rOWFoAfHmK4RIl9d5GlqqQ.png" /></figure><h3>The 3 Things You Actually Need to Verify: Data, Training, Aggregation</h3><p>But where are the main challenges related to verifiability in Federated Learning? Well, we can find three delicate points:</p><ol><li><strong>Verifiability in the data usage:</strong> namely, whether a client is using some stated data and whether this data respects certain properties or policies.</li><li><strong>Verifiable training:</strong> namely, whether the client has performed the training based on the agreed-upon algorithm on a specific model.</li><li><strong>Verifiable aggregation</strong>: having the guarantee that the aggregator performed the aggregation correctly and based on the agreed-upon algorithm.</li></ol><p><strong>Making those three claims verifiable can help mitigate certain attacks illustrated above.</strong></p><h3>How Verifiability Reduces Attacks (What Each Proof Prevents)</h3><p>First, implementing verifiable claims in data usage can help mitigate data poisoning attacks, as clients may be required to provide evidence that they are using specific data that could have been committed previously, along with additional guarantees regarding policies or certain properties of the data. Verifiability in data usage can be broadened by also considering the gradients sent to the aggregator as data, requiring the client to provide additional constraints on their properties, like norm bounds, thereby helping to mitigate model poisoning attacks.</p><p>Furthermore, implementing verifiable claims during the training phase can help mitigate model poisoning and free riding, as clients are required to provide evidence proving that they complied with the agreed-upon training procedure. This means that if they deviate from the procedure or send arbitrary gradients without accompanying evidence, the aggregator can detect and flag such behaviour as misbehaviour. This also prevents free riding, meaning that if a client does not provide evidence of the computation, it can be flagged as a free rider and excluded from the protocol by the next iteration.</p><p>Eventually, enforcing verifiable claims during aggregation can prevent global model tampering and selective dropping, as the aggregator is required to provide evidence proving that all gradients from the expected clients were included in the aggregation, along with an integrity constraint on the computation to prevent any interference with the procedure.</p><h3>Reality Check: What’s Feasible Today (Aggregation Wins)</h3><p>The following table presents the state of the art of the most recent works, where VD stands for Verifiability in Data, VT stands for Verifiable Training, and VA stands for Verifiable Aggregation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/1*ucCO60LMqfEJdgY2nQYxvQ.png" /></figure><p>An ideal verifiable federated learning framework would implement verifiability across all three dimensions, but the current verifiability mechanisms are better suited to some claims than to others, as can be noticed from the table.</p><p>Verifiable training is the most computationally intensive phase of the protocol, and current zero-knowledge proving schemes struggle with the circuitization of non-linear layers that are typical in modern architectures. Trusted execution environments (TEEs) face similar challenges, as current enclave solutions struggle to run the entire training procedure within the enclave. What is instead really feasible with current technologies is proving the aggregation, given its linear nature that fits well into zero-knowledge circuits and runs smoothly within enclaves up to a certain number of client contributions.</p><p>Verifiability in data usage appears to be feasible, as it would require proving the usage of certain committed data for dataset integrity, which amounts to nothing more than Merkle proofs with additional constraints, along with some range proofs regarding the properties of the gradients. However, it currently does not seem to be a priority in any of the implementations surveyed.</p><h3>Why Blockchain Helps: Public Verification + Audit Transcript</h3><p>Notably, the blockchain infrastructure and its transparency property prove to be of interest in this framework, serving as an enabler for verifiability along two dimensions:</p><ul><li>First, it can be used to verify proofs generated off-chain for training and aggregation, given verifiers deployed on-chain whose execution can be checked by anyone.</li><li>Second, it can serve as a transcript to register the entire FL process, giving auditors the possibility to verify the executed flow. The following table reports which works rely on the blockchain infrastructure and for what purposes.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*DORmP0033V1Bl8l10odyvA.png" /></figure><p>As can be noticed from the table, the main usage of the blockchain turns out to be as the medium for proofs generated off-chain. This, of course, comes at a cost that increases as the number of clients increases and as the complexity of the computation to be proven increases.</p><h3><strong>Verification Costs: The Bottleneck Everyone Ignores</strong></h3><p>The following table provides the average verification cost for a light computation to be proven using Groth16 (values as of Feb, 16):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/645/1*SurZIJ07TentHLMFNY-oEw.png" /></figure><p>As can be seen, there are Layer 2 solutions that are already quite cheap.</p><p><strong>An even cheaper solution would be relying on our blockchain, recently launched on Mainnet: </strong><a href="https://zkverify.io/"><strong>zkVerify</strong></a><strong>!</strong></p><h3>zkVerify Changes the Economics</h3><blockquote>Considering a proof for the same calculation to be verified on zkVerify, we can achieve a cost of 0.0003 USD, which is a decimal order of magnitude less compared to the cheapest Layer 2 option!</blockquote><p>But this does not end here. Given the sparsity of framework proposals in the solutions we have analyzed, we have formalized a common framework that could potentially standardize the VFL one, setting a common ground for all stakeholders interested in this area, including researchers, developers, and those willing to contribute to existing solutions.</p><p>Stay tuned for that!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2343a5f78113" width="1" height="1" alt=""><hr><p><a href="https://medium.com/horizen-labs/verifiable-federated-learning-verifying-training-data-use-and-aggregation-2343a5f78113">Verifiable Federated Learning: Verifying Training, Data Use, and Aggregation</a> was originally published in <a href="https://medium.com/horizen-labs">Horizen Labs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Recovering Encrypted Data Without Your Decryption Key]]></title>
            <link>https://medium.com/horizen-labs/recovering-encrypted-data-without-your-decryption-key-05ddab75cfac?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/05ddab75cfac</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[tees]]></category>
            <category><![CDATA[encrypted-data]]></category>
            <category><![CDATA[data-privacy]]></category>
            <category><![CDATA[horizen-labs]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Mon, 02 Mar 2026 16:12:11 GMT</pubDate>
            <atom:updated>2026-03-02T17:32:14.345Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d4rd1n4oNmFdOhvvu7uFrg.png" /></figure><p>Private cloud backups are a vital tool in today’s digital landscape. Backups, in general, allow users to store important information off-site on a server, ensuring that the information remains available even in the event of a local failure. Adding privacy measures allows users to back up sensitive information, such as the key to their cryptocurrency wallet. This addition introduces a tradeoff between privacy and availability.</p><p>Privacy requires remembering some cryptographic secrets, like the decryption key and digital signature key, or a password, without which the user loses their availability. <a href="https://dl.acm.org/doi/pdf/10.1145/3719027.3765127">A recent work</a> coauthored by a member of our research team [1] explores the interesting question of whether this tradeoff can be avoided.</p><blockquote>More specifically, can a user recover encrypted data stored on a cloud server even when they do not remember<strong> <em>anything</em></strong>?</blockquote><h3>The Problem</h3><p>Suppose that Alice wants to back up her cryptocurrency wallet key on a remote server in order to retain availability if her local storage fails. Alice must store her wallet key privately: if it is revealed to any other party, that party will have access to her funds. Further, suppose that after Alice has stored her wallet key, she has somehow lost all means of accessing that backup: any cryptographic keys that she used to perform the storage, access to her personal devices, she even forgot any passwords that she had used to set up the backup. While it seems that Alice’s key is now lost forever, [1] shows that if the proper steps were taken during storage, she can still recover her key.</p><p>This problem can be broken down into two subproblems: credential-less authentication, and emergency recovery. In credential-less authentication, Alice must prove her identity to the server storing her wallet key. She must do this while remembering nothing, making digital signatures or password-based authentication unusable in this setting. Further, we must ensure that Alice is the only one who is able to authenticate, otherwise an adversary could come and steal Alice’s wallet key.</p><p>In emergency recovery, Alice must break the confidentiality of the stored information. Because Alice wants her wallet key to remain private throughout storage, she uses a cryptographic technique to hide the true value from the server. This is most often done through encryption, where Alice encrypts her wallet key, using an encryption key unknown to the remote server, and sends the subsequent ciphertext to the server. By the security of encryption, we know that the server learns nothing about the wallet key from the ciphertext. However, in an emergency recovery, Alice has forgotten her encryption key. This means that she also learns nothing about her wallet key from the ciphertext. Alice, therefore, needs a way to <em>break</em> the encryption. Further, we must ensure that <em>only</em> Alice can break the encryption, else an adversary could steal her wallet key. Encryption could be avoided altogether if Alice hires multiple servers and secret-shares her wallet key. Secret sharing is a primitive where Alice splits her wallet key into pieces such that given enough pieces, one can reconstruct the original value. A simple example would be choosing n numbers that sum to Alice’s wallet key. Then, one of these pieces is sent to each of the employed servers. This approach, however, requires Alice to trust some subset of the employed servers, which we wish to avoid, because if all servers misbehave, they could collaborate to steal her secret without her knowledge.</p><p>This leaves us with two questions to answer:</p><ol><li>How can <em>only</em> Alice prove that she is Alice, even when she has forgotten everything?</li><li>Given that Alice has proven her identity, how can <em>only</em> Alice break the security of encryption?</li></ol><h3>Credential-less Authentication</h3><p>Credential-less authentication is the process by which Alice, and only Alice, can prove her identity. Suppose that Alice is a member of a group of people who all start with some form of credential, like an ID card. When all parties possess their IDs, authentication is easy: Alice simply presents her ID. But how can Alice prove her identity when she has lost her ID? She can simply reclaim her identity by announcing that she is Alice. Alice announces to the group that she has lost her ID card, but that she is indeed Alice. Surely, if this were not Alice, the real Alice would refute the claim by presenting her own ID. This shows how Alice can stop an adversary, say Eve, from stealing her identity. If Eve claims to be Alice, then Alice can prove that this is a malicious request by presenting her own ID. Note however, that when Alice has lost her own ID, she must make this announcement immediately, as she has also lost her ability to stop Eve from stealing her identity.</p><p>The protocol presented in [1] uses a permissionless blockchain to make this announcement, and digital signatures in the place of an ID card. Alice registers with a particular server in the authentication protocol by announcing the server’s digital signature verification key and her digital signature verification key on chain, establishing her identity. Later on, when Alice has forgotten everything, she posts a request on chain, potentially from a new account, claiming to be Alice. If no party posts a signature from Alice denying this claim, then it must have been Alice making the request. If it was Eve making the request, then Alice simply posts a signature denying the request. Of course, we cannot wait forever for a denial to be posted, so Alice must decide upon registration how long she will give herself to respond to a request, in [1] this is referred to as the challenge time, t(<em>chal</em>). Then, the block containing her request and the t(<em>chal</em>) blocks afterwards serve as proof of Alice’s authentication.</p><p>This, however, does not provide Alice with sufficient protection. Eve could employ a front-running attack to steal Alice’s identity. Alice’s request will appear in mempool before it appears on chain, and mempool is publicly available. Meaning that Eve can see the request in mempool, and rush her own post claiming Alice’s identity first. [1] uses a standard technique for mitigating front-running attacks, known as commit-and-reveal. In this approach, Alice first posts a cryptographic commitment to her request. Upon seeing the commitment on chain, Alice can post the opening. To prevent Eve from posting a commitment to a request on Alice’s behalf and front-running her opening, Alice sets a second timing parameter upon registration: open time t(<em>open</em>), which determines how long Alice has to open a commitment to a request. Now, the t(<em>open</em>) blocks before Alice’s request, which must contain a commitment, and the t(<em>chal</em>) blocks afterward her request serve as proof of Alice’s authentication.</p><p>But there is one final problem here. Alice must give herself sufficient time to respond to Eve’s malicious requests. Alice cannot be expected to constantly monitor the chain for such requests and respond immediately. Eve may take advantage of personal knowledge about Alice to make a timely request. For example, if Eve knows that Alice is going camping and will be away from her devices for a week, she could make a request during the trip and catch Alice off guard. Alice must therefore give herself weeks or even months to respond to requests made on her behalf. Setting t(<em>chal</em>) to such a lengthy period would result in many blocks being included in the proof of authentication: potentially hundreds of gigabytes of data. If this proof needs to be passed along to another party, as it will be in the emergency recovery protocol, this becomes infeasible. This is solved by having Alice set a third timing parameter upon registration, the waiting time t(<em>wait</em>). This is the amount of time that passes after the request, before a denial can occur. The blocks during this period are not included in the proof of authentication, and therefore has no impact on the size.</p><p>Putting this all together, Alice first registers for the credential-less authentication protocol by announcing her server’s and her own digital signature verification keys as well as her three timing parameters t(<em>open</em>), t(<em>wait</em>), and t(<em>chal</em>) on chain. Alice then uses her signing key, as long as she has it, to respond to malicious requests by signing and posting denials. It is vital that Alice not post her denial during the waiting period, since these blocks are not part of the proof. When Alice loses her credentials, she posts her own request. First, posting a commitment to the request followed by an opening to the commitment within time t(<em>open</em>). Then begins the waiting period. Once time t(<em>wait</em>) has passed, the challenge period of time t(<em>chal</em>) begins. Since Alice is the one making the request, she can be certain that no denial will be posted. Her proof of authentication is the t(<em>open</em>) blocks before her request, which must contain a commitment to the request, and the t(<em>chal</em>) blocks occurring t(<em>wait</em>) blocks after the request, which must not contain a denial.</p><h3>Emergency Recovery</h3><p>Now that Alice has a method of authenticating herself even after losing her credentials, we need a way for Alice to break the security of encryption. Suppose that Alice has already stored a ciphertext on the remote server, but has forgotten her decryption key. Then, Alice and the remote server are both stuck with a ciphertext that tells them nothing. One way that Alice could break the ciphertext, or rather, have the server break the ciphertext for her, is if the server was able to run a secure “re-encrypt” procedure. What we need from this procedure is that the server decrypts the ciphertext and encrypt the plaintext under a fresh public encryption key chosen by Alice, without ever revealing the plaintext to the server. If the cloud had Alice’s original decryption key, it would be able to perform such a re-encryption, however this would reveal the plaintext to the cloud. Further, the server cannot be in possession of Alice’s decryption key: If the server has Alice’s decryption key, it would be able to steal Alice’s wallet key, because we consider the server to be untrusted. But even if the the server is untrusted, it can still host trusted hardware, such as a Trusted Execution Environment (TEE).</p><p>A TEE is a secure hardware enclave within an untrusted host. In this enclave, storage and computation are hidden from the host, despite sharing the same hardware. Further, the output of the TEE comes with an unforgeable attestation, like a digital signature. This allows Alice to ensure that she truly is talking to the TEE instead of the host pretending to be the TEE. Alice can then make use of a TEE hosted by the server to securely decrypt her ciphertext and re-encrypt it under a freshly chosen public key.</p><p>All together, this protocol involves Alice performing a key exchange with the TEE via the server to establish a shared symmetric key. Then, Alice encrypts her wallet key under this shared symmetric key, and sends the ciphertext to the cloud, who forwards it to the TEE. Later, when Alice has forgotten her wallet key, her encryption key, and everything else, she authenticates with the credential-less authentication protocol, and passes this authentication token to the cloud, who forwards it to the TEE. If the authentication token verifies, the TEE will perform the re-encryption, and send the fresh ciphertext back to Alice.</p><p>There is, however, one last complication. The credential-less authentication protocol we discussed makes use of a permissionless blockchain, and the TEE is simply a hardware enclave, incapable of truly communicating with the outside world, except via their host. This gives the server the ability to forge an authentication token and steal Alice’s secret, falsely claiming that the token comes from the chain. [1] therefore borrows the techniques of [2], using a publicly verifiable ledger. Here, public verifiability means that any party is able to verify that a block truly comes from the chain, even without access to the ledger. Such a verification would likely require some auxiliary information, such as the genesis block of the chain. This auxiliary information would be provided by Alice upon storage. Now, the TEE can ensure that an authentication token truly is valid.</p><h3>How to Recover a Cryptographic Secret from the Cloud</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6FQkm0C3Kx0bQ2XMdAUlsw.png" /></figure><p>Figure 1, taken from [1] shows the composition of the two protocols. Alice begins by registering with the cloud server through the credential-less authentication protocol, posting the cloud’s digital signature verification key, her own verification key, and her three timing parameters t(<em>open</em>), t(<em>wait</em>), and t(<em>chal</em>). Once Alice is registered, she engages in a key exchange with the TEE via the cloud to establish a shared symmetric key. This key is used to encrypt Alice’s wallet key, and the ciphertext is sent to the cloud and stored.</p><p>Later, when Alice has forgotten everything, she finds her registration transaction to re-learn her timing parameters. She then posts a commitment to a request to recover her stored secret under a fresh public key. Once the commitment has been posted, Alice can open the commitment to her request, making the announcement public. The cloud then waits for the waiting period to pass, which begins the challenge period. The cloud waits for the challenge period to pass, then collects the t(<em>wait</em>) blocks before the opening, and the t(<em>chal</em>) blocks occurring t(<em>wait</em>) blocks after the opening. If there is a signed denial in the challenge period, the cloud does not proceed. If there does not exist a denial in the challenge period, the cloud forwards the authentication token to the TEE.</p><p>The TEE also verifies the authentication token, ensuring that the cloud did not cheat. As long as the authentication token verifies, the TEE uses the stored symmetric key, established with Alice via key exchange during storage, to decrypt the stored ciphertext. The TEE then encrypts Alice’s secret using the fresh public key included in her request. This ciphertext is forwarded back to Alice via the cloud.</p><p>For more details on how to solve this interesting problem, we recommend the reader check the full paper [1].</p><h3>References</h3><ul><li>[1] David Adei, Chris Orsini, Alessandra Scafuro, and Tanner Verber. <a href="https://dl.acm.org/doi/pdf/10.1145/3719027.3765127">How to recover a cryptographic secret from the cloud.</a> In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, CCS 2025, Taipei, Taiwan, October 13–17, 2025. ACM, 2025.</li><li>[2] Gabriel Kaptchuk, Matthew Green, and Ian Miers. Giving state to the stateless: Augmenting trustworthy computation with ledgers. In 26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, February 24–27, 2019. The Internet Society, 2019.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=05ddab75cfac" width="1" height="1" alt=""><hr><p><a href="https://medium.com/horizen-labs/recovering-encrypted-data-without-your-decryption-key-05ddab75cfac">Recovering Encrypted Data Without Your Decryption Key</a> was originally published in <a href="https://medium.com/horizen-labs">Horizen Labs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ZK Analysis: The True Cost of ZK Verification]]></title>
            <link>https://medium.com/horizen-labs/how-much-does-it-cost-to-verify-a-zero-knowledge-proof-on-chain-and-what-does-it-mean-exactly-2cefd68cf204?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/2cefd68cf204</guid>
            <category><![CDATA[crytpocurrencies]]></category>
            <category><![CDATA[zk-proofs-verification]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[privacy]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Wed, 03 Dec 2025 12:02:54 GMT</pubDate>
            <atom:updated>2025-12-04T14:58:53.321Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xhbLBOpeGOyk6wHvfr84Sw.png" /></figure><p>How much does it cost to verify a zero-knowledge proof on-chain? And, what does it mean exactly?</p><p>In this blog post we are going to have a look at the real cost of verifying proofs on some popular chains, and we will compare it to <a href="http://zkverify.io/">zkVerify</a> to show the practical savings.</p><h3>One Step Back: ZKPs</h3><p>Succinct probabilistic proving systems are a class of schemes that allow one party (the Prover) to convince another party (the Verifier) that the result obtained by performing a certain computation on some input is correct, in a faster way than asking the Verifier to re-perform the same computation and check correctness by herself. The term “succinct” refers exactly to this efficiency property: on one side, the effort required by the Prover to convince the Verifier is “not much more” than performing the computation; on the other hand, the effort required by the verifier to check this proof is “much less” than performing the computation.</p><p>These proving systems can be interactive (where Prover and Verifier engage in a multi-round communication protocol) or non-interactive (where the Prover just sends a single message to the Verifier). In the latter case, succinctness also implies that the size of this message (the proof) is “much smaller” than the size of a full description of input and circuit performing the computation. SNARKs and STARKs are the two most known examples of non-interactive succinct probabilistic proving system families.</p><p>Zero-Knowledge (ZK), instead, is a property related to the privacy of the inputs of the computation: in a zero-knowledge proving system, the Prover can convince the verifier that the output of a given computation on some secret input is correct, without having to reveal the input to the Verifier. Zero-knowledge proof systems are generally abbreviated as simply ZKP.</p><p>Zero-knowledge and succinct non-interactive proving systems (such as zkSNARKs and zkSTARKs) are important building blocks for Web3 applications, due to their properties of efficiency and privacy. Groth16 is one of the most famous and most widely used practical schemes in this space, due to the extremely short proof size (120–300 bytes) and extremely fast, constant verification time (a few ms).</p><h3>Why verification on-chain?</h3><p>It is worth highlighting the fact that, in succinct ZKP systems, verifying a proof is usually very fast and cheap: the whole scheme has been designed to make this easy. While the proof generation can be quite taxing in terms of power and can take up to a couple of minutes of intensive computing, the verification of a proof can usually be done in a few ms on modest hardware. So, why are we concerned about the cost of verification at all?</p><p>The reason is that, even if verification is fast and cheap, there is a big difference on whether it is performed off-chain (e.g. on a user’s computer, by a web service, etc), or on-chain (by a smart contract). In fact, it is a relatively common use case to have a smart contract perform an action depending on whether a received proof is valid or not. In order to do so, the smart contract has to perform the verification using the chain’s logic, and this can get rapidly expensive, because the smart contract must request fees in order to provide an incentive to the network to perform this verification. Computation on a blockchain VM is expensive, and even a relatively fast and easy task can have a non-negligible cost.</p><p>We created zkVerify to solve this problem. Instead of having smart contracts verify proofs on their native chain, they can outsource the verification process to the dedicated zkVerify chain using appropriate bridges. The zkVerify chain cuts the verification cost by being extremely specialized in proof verification only, using aggregation techniques to further reduce the cost.</p><h3>A Comparison</h3><p>For this comparison we look at on-chain typical verification costs of the popular Groth16 proofs on zkVerify and on 5 other chains: Ethereum, BNB Chain, Avalanche, Arbitrum, and Optimism. The first three are L1, the other two are L2.</p><p>We look at precompile costs for the BN254 curve, for which all these networks provide built-in instructions for curve pairing computation.</p><p>The gas cost for verifying Groth16 is dominated by the cost for performing pairing operations (constant), plus a variable cost per additional public input of the circuit, and another fixed cost representing the EVM execution overhead. Let’s analyse all these costs separately.</p><ul><li>According to EIP-1108 [1], the cost for pairing check is 34,000 * k + 45,000 gas, where k is the number of pairings (4 in our case [2]). This sums up to 181,000 gas.</li><li>The EVM execution overhead is composed of an ETH base transfer fee of 21,000 gas, plus calldata costs and EVM “scaffolding” opcodes.</li><li>The calldata cost is the cost for loading data in the contract call, fixed at 16 gas/byte. A Groth16 proof on BN254 has a fixed size of 256 bytes, for a total of 4,096 gas.</li><li>The “scaffolding” is the cost for the logic that prepares the data and calls the precompile instructions of the verifying contract. This requires a series of EVM instructions (CALL, PUSH, STORE&lt; ISZERO, RETURN, etc) for a total of ~1&#39;600 gas.</li></ul><p>This sums up to ~207,700 gas of fixed cost.</p><p>For each additional public input to the circuit, we have to add 7&#39;160 gas [4]. Let’s consider simple circuits with only 2 public inputs.</p><p>This leads to a total verification cost of ~220&#39;000 gas.</p><p>Given the gas cost, for L1 chains we must multiply this by the gas price (in Gwei) for each chain, which depends on the congestion of the network and is very volatile. Then divide this number by 1,000,000,000 and multiply it by the current market price of the related coin.</p><p>Let’s consider an average priority transaction fee. For the month of October 2025 we had a rough average of:</p><p>Ethereum [5]: ~2 Gwei</p><p>BNB Chain [6]: ~2.5 Gwei</p><p>Avalanche [7]: ~25 Gwei</p><p>For L2 chains (Arbitrum, Optimism), instead, the computation is more complex. The L2 gas cost is lower (and tracked in ETH since these chains are roll-up to Ethereum):</p><p>Arbitrum [8]: ~0.05 Gwei</p><p>Optimism [9]: ~0.01 Gwei</p><p>but we also have to add the cost to post the proof data (256 bytes) to Ethereum in an EIP-4844 “blob”. The blob price per byte is regulated by the blob market [10] which, considering it has been introduced relatively recently, is currently unsaturated, and fees are very low: for the 256 bytes of a Groth16 proof we are looking at ~0.004 USD for Arbitrum and less than 0.001 USD for Optimism.</p><p><strong>Current token prices are:</strong></p><p>ETH: 3,073.75 USD*</p><p>BNB: 899.18 USD*</p><p>AVAX: 14.08 USD*</p><p><em>*Prices shown as of December 3, 2025</em></p><p>Summing up, we have:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2dCnAowqYd9CJYPOJCCWdQ.png" /></figure><p>Computation on zkVerify is more difficult because proofs are batched, but let’s just look at the zkVerify blockchain explorer [11].</p><p>A typical Groth16 settlement transaction [12] uses a fee like 0.021 VFY. At a current price of 0.03261 USD*, that makes it just slightly less than 0.0007 USD*. That is well under one-tenth of a cent.</p><p><em>*Prices shown as of December 3, 2025</em></p><h3>Conclusion</h3><p>As we have seen, verifying ZK proofs on-chain can be expensive. zkVerify makes it incredibly cheap for smart contracts to verify proofs, reducing verification cost to less than 1/100 of the cost on Ethereum, and beating even popular L2 chains in most scenarios.</p><h3>References</h3><p>[1] <a href="https://eips.ethereum.org/EIPS/eip-1108">https://eips.ethereum.org/EIPS/eip-1108</a></p><p>[2] <a href="https://xn--2-umb.com/22/groth16/">https://xn--2-umb.com/22/groth16/</a></p><p>[3] <a href="https://ethereum.org/developers/docs/gas/">https://ethereum.org/developers/docs/gas/</a></p><p>[4] <a href="https://hackmd.io/@Orbiter-Research/S1nat__m0">https://hackmd.io/@Orbiter-Research/S1nat__m0</a></p><p>[5] <a href="https://ycharts.com/indicators/ethereum_average_gas_price">https://ycharts.com/indicators/ethereum_average_gas_price</a></p><p>[6] <a href="https://ycharts.com/indicators/binance_smart_chain_average_gas_price">https://ycharts.com/indicators/binance_smart_chain_average_gas_price</a></p><p>[7] <a href="https://ycharts.com/indicators/avalanche">https://ycharts.com/indicators/avalanche</a></p><p>[8] <a href="https://arbiscan.io/chart/gasprice">https://arbiscan.io/chart/gasprice</a></p><p>[9] <a href="https://optimistic.etherscan.io/chart/gasprice">https://optimistic.etherscan.io/chart/gasprice</a></p><p>[10] <a href="https://blobscan.com/">https://blobscan.com/</a></p><p>[11] <a href="https://zkverify.subscan.io/block">https://zkverify.subscan.io/block</a></p><p>[12] <a href="https://zkverify.subscan.io/extrinsic/656949-6">https://zkverify.subscan.io/extrinsic/656949-6</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2cefd68cf204" width="1" height="1" alt=""><hr><p><a href="https://medium.com/horizen-labs/how-much-does-it-cost-to-verify-a-zero-knowledge-proof-on-chain-and-what-does-it-mean-exactly-2cefd68cf204">ZK Analysis: The True Cost of ZK Verification</a> was originally published in <a href="https://medium.com/horizen-labs">Horizen Labs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Protecting Voter Privacy in DAOs]]></title>
            <link>https://medium.com/@horizenlabs-tech/protecting-voter-privacy-in-daos-5fbddb295ae5?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/5fbddb295ae5</guid>
            <category><![CDATA[dao]]></category>
            <category><![CDATA[voting]]></category>
            <category><![CDATA[onchain]]></category>
            <category><![CDATA[web3]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Fri, 01 Sep 2023 20:40:31 GMT</pubDate>
            <atom:updated>2023-09-07T15:35:46.686Z</atom:updated>
            <content:encoded><![CDATA[<h4>Utilizing zk-proofs to enable hidden on-chain votes for DAOs</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MfIQX5LLA61YX61e8Ld1Cg.jpeg" /></figure><p>Voting plays a crucial role within Decentralized Autonomous Organizations (DAOs). Currently, on-chain voting ensures transparency and resistance to censorship in the voting process, though this is done at the expense of voter privacy.</p><p>For example, in the OpenZeppelin’s Governor framework, the most widely used on-chain voting system, votes are not encrypted and are visible to everyone. This means anyone can see how each user voted.</p><p><em>To address the exposure of votes on-chain, Horizen Labs created a solution using zk-proofs to keep votes private while still keeping votes transparent and resistant to censorship, just like current on-chain voting systems. For a more technical overview of our approach, please reference our </em><a href="https://hackmd.io/@hackmdhl/BJSz8pnan"><em>technical guide</em></a><em>.</em></p><h3>How it works</h3><p>The voting protocol we implemented involves some complex cryptography, such as <strong>linear homomorphic encryption</strong>, and <strong>zero-knowledge proofs</strong>.</p><p>Before sending their votes on-chain, users encrypt them. In this way, to an observing third party, each on-chain vote looks like random gibberish, from which it’s impossible to recover the original vote.</p><p>Now it could be reasonable to think that, since each vote looks like random gibberish, in order to compute the final result, it’s necessary to decrypt each individual vote beforehand. But by adopting a l<strong>inear homomorphic encryption scheme</strong>, it’s possible to actually compute the (still encrypted) result on-chain, without ever decrypting a single vote.</p><p>After the encrypted result has been computed, a tallying authority is in charge of decrypting it using its private decryption key, and publish it.</p><p>Zk-proofs play a crucial role in two phases of the protocol, ensuring:</p><ol><li><strong>Well-formedness of the votes</strong>: since each vote is encrypted (hence, for all purposes, indistinguishable by a random string), voters must prove the validity of their vote by generating a zk-proof of vote well-formedness. They send it on-chain together with their encrypted vote, so that the voting smart contract can discard invalid votes.</li><li><strong>Correct decryption of the result</strong>: the tallying authority must generate a zk-proof of correct decryption in order to ensure that it has correctly decrypted the final result, which is available on-chain. Again, this proof is checked on-chain by the voting smart contract, thus ensuring that the tallying authority cannot cheat.</li></ol><h3>Limitations and future work</h3><p>Our solution has <strong>strong guarantees of integrity and correctness</strong>: the combination of transparent on-chain computation and zk-proofs ensures that no actor can cheat. Cheating is impossible both for voters, who cannot cast invalid votes, or perform double votes, and for the tallying authority, who cannot ignore, forge, or otherwise tamper with votes. These guarantees of correctness are very important, and do not require putting trust in anyone, except in cryptography and, of course, in the consensus of the chain itself.</p><p>Our protocol also ensures privacy of votes. In this regard, guarantees are somewhat weaker, in the sense that they require assuming that the tallying authority is honest, and doesn’t decrypt each individual vote, but only the final encrypted result. We are working to improve this aspect by implementing <strong>threshold decryption</strong>: then it will be possible to create a setup in which the decryption key won’t be held by a single party, rather it will be split into multiple shares, each one held by a different party. This would prevent the situation in which a single tallying authority is able to decrypt individual votes. For that to occur, multiple parties would have to collude.</p><p>There is another trust assumption in our protocol: that the tallying authority abides by its duty, and actually performs the tallying. Otherwise the result of the voting cannot be determined and remains available only in encrypted form. The best way to prevent this possibility varies on a case by case basis, but, generally speaking, cryptoeconomic mechanisms (such as slashing) can be useful.</p><h3>Conclusion</h3><p>At Horizen Labs we have developed an on-chain private voting solution which is compatible with the OpenZeppelin Governor framework. At the moment, adopting our solution requires modifications to the governance contract, but we are working to solutions which could avoid this necessity.</p><p>We believe that enabling privacy in on-chain voting is important for a broader adoption of this technology, and this is our first step in that direction. If you have any question, feel free to <a href="https://share.hsforms.com/1EhH10K2wSPiRtwnMcuBS4gdjxbg">get in contact with our team</a>!</p><p>Luca Giussani, <a href="/service/mailto:lucagiussani@horizenlabs.io">lucagiussani@horizenlabs.io</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5fbddb295ae5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Technical Deep Dive — Coins Selection Algorithm]]></title>
            <link>https://medium.com/@horizenlabs-tech/technical-deep-dive-coins-selection-algorithm-2508618ddc3e?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/2508618ddc3e</guid>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Wed, 30 Aug 2023 20:09:42 GMT</pubDate>
            <atom:updated>2023-08-31T13:23:24.319Z</atom:updated>
            <content:encoded><![CDATA[<h3>Technical Deep Dive — Coins Selection Algorithm</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k2T1FrwmDnSI9yTzPkDTOQ.png" /></figure><h3>Intro:</h3><p>While we are about to release EON on Mainnet, as the first EVM compatible sidechain in the Horizen Ecosystem, the team hasn’t stopped improving what we still consider the center of our universe, Zend.</p><p>We would like to share the way we have improved the algorithm of coins selection used by Horizen mainchain (Zend client). In this article we start with a description of the root issue that led the improvement activity, then continue with the analysis and the approach to design and implementation of the new algorithm; eventually we conclude with some benchmarked results.</p><h3>A bit of Background:</h3><h4>The Blockchain:</h4><p>The Horizen mainchain has embraced the UTXO (unspent transaction output) model, that is a stateless model where every transaction creates one or many outputs (new coins) based on the inputs (feeding coins) it spends. For example, if we think of a generic transaction, the sender will have to specify as inputs the owned UTXOs to use, while the outputs will be the amount that he wanted to send to the receiver, the paid fees, and possibly the change.</p><h4>The Application:</h4><p>Zend, the official Horizen mainchain client, acts as a network node of the Zen cryptocurrency.</p><p>Just like Bitcoin, it comes with a local wallet that can be used for sending different types of transactions using the command line. To mention one example, sending $ZEN coins to another user through what we call an RPC command.</p><h4>The main issue:</h4><p>It all began with an internal ticket (what a thriller novel intro, no?); it was reporting a failure during the attempt to send coins. In short, the eventual symptom was the transaction being rejected by the node, after being built based on the coins selection performed by the associated algorithm. For the end user, this meant the coins were not sent to the recipient, and any retry was pointless.</p><h4>The desired outcome:</h4><p>Well, in the first place understanding if the issue was a bug and in case it was, fixing it, possibly taking the chance to perform some refactoring and improvements.</p><h4>Where to find our work:</h4><p>Wait, wait, don’t rush, here are the links to our pull requests on GitHub (<a href="https://github.com/HorizenOfficial/zen/pull/576">feature</a>, <a href="https://github.com/HorizenOfficial/zen/pull/577">benchmark</a>) but probably it’s better if you continue reading, then take a coffee (or maybe two) and later move to the code.</p><h3>Caution! Spoiler!</h3><p>Did we succeed in fixing the bug and improving our application?</p><p>Yes, for sure we did! Long story short, we were able to find the root cause of the issue and fix it, making the algorithm more robust. In addition, we pushed on modifying the algorithm and some auxiliary functions in order to get additional benefits.</p><p>To anticipate a few results, here are some key achievements:</p><ul><li>enhanced robustness for coins selection algorithm (failure rate dramatically dropped to 0%),</li><li>28% reduction of paid fee rate (and no one likes paying high commissions!), fee rate being defined as the ratio between actual fees over total transaction size,</li><li>15% reduction of cases where an output change is generated (and when you go shopping at the market, you prefer to match exactly the amount, instead of receiving back a boring small change!).</li></ul><h3>So, that’s how we did it…</h3><p>As soon as we started working on this task, we organized the activity going through the following steps:</p><h4>Reproduce the issue: the need for testing</h4><p>Instead of trying to manually reproduce the issue, we have followed a TDD (test driven development) approach; by adding a new Python script in our existing regression test framework, we made the failure repeatable. This helped a lot in the initial analysis and during the development phase.</p><h4>Analysis: why the problem and what to touch</h4><p>Simply the mandatory part: analyzing the code to get the root cause of the issue. Taking advantage of the Python script mentioned above, we went through a meticulous process of code inspection, debugging and profiling.</p><p>In the end, we’ve found the bug in the lack of a constraint on the total size of the selected coins, resulting in the creation of an oversized transaction when too many coins were selected. Moreover, during this investigation we were able to detect some inefficiencies and flaws both in the pre-processing phase of the coins selection algorithm and in the fee management procedure; hence we grabbed the opportunity to clean and improve them.</p><h4>Time for d&amp;d (roleplaying? no, we mean design and development!):</h4><p>Now let’s try to formulate the coins selection problem in a more scientific way:</p><p>Coins selection can be modeled as a discrete optimization problem:</p><p>Input variables:</p><ul><li><strong>Values:</strong> the set of N elements representing coins values (unit of measure is Zen)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*q_IG7gPJU2Qdwpj-" /></figure><ul><li><strong>Weights:</strong> the set of N elements representing coins weights (unit of measure is bytes)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*sP78lhOCBEeOkKsO" /></figure><ul><li><strong>TargetValue:</strong> the total value of coins we want to send (unit of measure is Zen)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*tkHSCc2ZfRPz0DT4" /></figure><ul><li><strong>TargetValueWithOffset:</strong> the maximum total value of coins we allow to select, considering a possible change for having back the surplus (unit of measure is Zen)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*ATvqrRO4xteZAh8h" /></figure><ul><li><strong>WeightLimit:</strong> the maximum total weight of coins we allow to select (unit of measure is bytes)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*GDdYh5a1qT0im1eP" /></figure><p><strong>Output variables:</strong></p><ul><li><strong>SelectionSet:</strong> the set of N elements representing selection of coins (0-&gt;unselected, 1-&gt;selected)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*4QBkcg_6BuWw7v-z" /></figure><p>Derived output variable (can be computed from selection set):</p><ul><li><strong>OptimalSelection:</strong> the quantity of selected coins</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*QyMu-lNVpROa5Oky" /></figure><ul><li><strong>OptimalValue:</strong> the total value of selected coins</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*JPv5H20MC8o-coyj" /></figure><ul><li><strong>OptimalWeight:</strong> the total weights of selected coins</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*-vesS47Gr1EwAnNU" /></figure><p><strong>Cost function:</strong></p><ul><li>maximize OX; the algorithm wants to select as many coins as possible (you always want to get rid of those annoying dimes from your wallet!); in case of ties, minimize OV to keep the change lower.</li></ul><p><strong>Constraints:</strong></p><ul><li>TV≤OV≤TVWO the algorithm wants to reach the requested target value, but also not exceed it by much (why pay for a beer with a $100 banknote?)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*HYEc_uEv6gxcrqIc" /></figure><ul><li>OW≤WL the algorithm must not exceed maximum transaction size (who wants to pay that beer with one hundred cents?)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/0*Of3V-a7BCe3ItckZ" /></figure><p>(if you didn’t, just go back and print in your brain those names like V, W, TV, etc; they will be used throughout the article!)</p><p>So, going back to the bugged algorithm, we found it was not considering the weight limit constraint; hence, in some cases (quite seldom telling the truth, but still happening) the selection was affecting so many small coins that the final transaction was later rejected, being abnormally big; but if a good portion of those many small coins was replaced with fewer bigger coins, the eventual total size would have been admissible and the transaction accepted.</p><p>So, given the above finding and the problem modelization, we implemented a two-solvers algorithm, that is to say:</p><ul><li>SlidingWindow solver (SW)</li><li>Branch&amp;Bound solver (B&amp;B)</li></ul><p>SW is the one acting first, its purpose is to find a suboptimal solution and to identify an admissible value for TargetValueWithOffset to be passed to the next solver.</p><p>Here below the associated procedure:</p><ol><li>order coins from lowest value to highest value, initialize X to empty</li><li>push in X the next (lowest) coin</li><li>if constraints OV≤TVWO and OW≤WL are not met, continue to pop out of X coins from lowest to highest until both the constraints are fulfilled</li><li>if constraint TV≤OV is not met, go to step #2 above</li><li>if constraint TV≤OV is met return</li></ol><p>This solver runs iteratively at different increasing levels of TargetValueWithOffset, starting from TargetValue (hence no change) until a predefined maximum value. As mentioned above, this solver generally produces a suboptimal solution but the positive aspects are that it’s extremely fast and it serves as a quick initializer for the second solver.</p><p>B&amp;B is the solver running after SW, its purpose is to find an optimal solution.</p><p>Its implementation uses a binary tree, to be considered as the combination of exclusion/inclusion of each coin. B&amp;B is based on a depth-first brute force exploration strategy, empowered by two additional optimization features, namely backtracking and bounding. Starting with an “all coins unselected” setup, the algorithm recursively explores the tree (from biggest coin towards smallest coin) opening two new branches, the first one excluding the current coin, the second one including the current coin; when a leaf is reached, the output variables are checked to identify if an improved solution (with respect to the temporary optimal one) is found and eventually marked as the new temporary optimal solution.</p><p>Just to have a better understanding, let’s have a look at what a full depth-first brute force exploration strategy means:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/691/0*h81wEU01XN05cdK4" /></figure><p>Now let’s consider the first part of backtracking feature, stating “if OV&gt;TVWO or OW&gt;WL, then prune the exploration of this branch, since the constraints are irrevocably broken and cannot recover through adding other coins” (because adding any coin would result in an increase of both OV and OW)…</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/0*2rvrboO_VLdtirkb" /></figure><p>…and the second part of backtracking feature, based on the assumption “if OV summed to the value obtained by including all the following coins does not exceed TV, then prune the exploration of this branch” (because even including all the remaining coins we would not be able to met the constraint TV≤OV):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/752/0*_buvxUgVQ2nn-XgW" /></figure><p>Finally, the bounding feature allows us to optimize the exploration even further, considering “if OX summed to the quantity of following coins still to be included does not improve the temporary optimal solution, then prune the exploration of this branch” (because even including all the remaining coins we would not be able to have a better value for OX):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/751/0*yuXFFD1tfVS5Jq2h" /></figure><p>With those features, we can achieve a very significant reduction of tree exploration, avoiding making useless computations and having the solver to run more efficiently in terms of speed and resources consumption.</p><p>Conversely to SW, B&amp;B solver runs significantly slower because it aims at finding an optimal solution to the selection problem. This led us to control its execution with a configurable timeout; as soon as the timeout is hit, the B&amp;B run stops and its partial result is compared (using the cost function) against the one previously obtained by SW; the best among them is considered the final solution.</p><p>For the sake of completeness, the possibility to handle coins weights was allowed through the introduction of some auxiliary functions responsible for estimating the size of the transaction excluding the inputs (i.e. the selected coins); this allowed us also to improve the fee management procedure, avoiding selection of unneeded coins that previously resulted in higher fee rates.</p><h4>Results as a compass: the need of benchmarking</h4><p>In the second phase of the development, we decided to write a Python script for measuring in some way the quality of what we were implementing; that would have been our compass when it came down to implementation details, and it helped a lot in the fine tuning of the code. In the end it was also a good way to show our boss we are the good guys!</p><p>So, the script provides the generation of some randomized wallets, with different attributes:</p><ul><li>wallets with few low value coins</li><li>wallets with many low value coins</li><li>wallets with many low, middle and high value coins</li></ul><p>Then several different transactions are performed using a stored randomly generated set of amounts (so in this way we were able to have randomness, but in a repeatable way), keeping track of the following metrics:</p><ol><li>errors [%]: intended as RPC command failure, for sure this was the key element to be benchmarked otherwise we were crashing to the ground</li><li>fee rate [%]: how much fee rate the user has to pay for the transaction</li><li>change creation [%]: the percentage of transactions creating a change (OV not exactly matching TV)</li><li>wallet reduction [%]: the comparison of coins quantity contained in the wallet (after the last transaction, with respect to the initial setup)</li><li>execution time [s]: that’s something you always benchmark!</li></ol><p>Having a significantly high number of runs, in order to get a good sample size and averaging the results, we obtained for the old algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*g4OkUgSxwm50eDM0svpFqQ.png" /></figure><p>and for the new one:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*E6qPnOZ22lTzTS6I4WZQ1g.png" /></figure><p>with the following overall comparison (as relative percentage differences) table:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YMXF4q74PuTDaK4To0JbEQ.png" /></figure><p>Looking at the results we can see that:</p><ol><li>-100% errors; boom! No more failures it’s something we are very proud of, witnessing the fact the bug was totally fixed,</li><li>-28% fee rate; the performance increase was a great surprise, the size estimation functions and the revision of the fee management procedure were behaving like a charm, granting very sharp savings in terms of fee rate.</li><li>-15% change creation; quite nice results were achieved also related to change generation, as a nice to have benefit,</li><li>-4% wallet reduction; this metric is almost unchanged, which is kind of negatively surprising, since the cost function of B&amp;B algorithm is to maximize the selection set; it must be said that a detrimental contribution is given by the few-low category wallets experiments, where we suppose the old algorithm behaved in such a bad way that it selected so many coins in excess resulting in a faster coins exhaustion (but a significantly worst fee management), while for the many-low and many-lowmiddlehigh categories wallets we have better performance for this metrics with the new algorithm (respectively +30% and +215%),</li><li>+309% execution time; yes, for sure this was a performance degradation, the RPC commands being three times slower; it’s something we can afford, since this is the execution time of an RPC command and the absolute value in seconds remains below half second; moreover, the new algorithm can be configured to be faster with a user-defined setting (clearly at the expense of quality results, refer to the other metrics here reported).</li></ol><h3>This is the end, my friend</h3><p>So, here we are, at the end of our story. The overall achievement is really satisfying, and we are also very proud of the analytic approach we set up for the resolution of this task; the new feature is just waiting for a monitored run on a more realistic and stressed test environment (private or public testnet) but the feelings seem promising and positive.</p><p>But since we are never totally done, possible next steps we can define could be:</p><ul><li>make the B&amp;B solver iterative instead of recursive, to make it more efficient in terms of memory management and possibly more performant too,</li><li>make the B&amp;B solver faster,</li><li>push further on fee management procedure optimization,</li><li>explore other cost functions, like minimizing change.</li></ul><p>And why not add something more to this nice list? Any thoughts on this? Any feedback or proposal would be really really appreciated! Then, in case you missed it or scrolled down here because of low patience, here again the links to our pull requests on GitHub (<a href="https://github.com/HorizenOfficial/zen/pull/576">feature</a>, <a href="https://github.com/HorizenOfficial/zen/pull/577">benchmark</a>).</p><p>Thanks for reading, see you in the next episode!</p><p>Author: Giacomo Pirinoli, <a href="/service/mailto:gpirinoli@horizenlabs.io">gpirinoli@horizenlabs.io</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2508618ddc3e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Introducing Monolith, for faster hashing in ZK settings]]></title>
            <link>https://medium.com/@horizenlabs-tech/introducing-monolith-for-faster-hashing-in-zk-settings-6980f406af0e?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/6980f406af0e</guid>
            <category><![CDATA[hash-function]]></category>
            <category><![CDATA[zero-knowledge]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Wed, 12 Jul 2023 15:12:03 GMT</pubDate>
            <atom:updated>2023-07-15T02:17:56.093Z</atom:updated>
            <content:encoded><![CDATA[<h4>Evaluating hash functions is a major bottleneck in many modern proving systems. Introducing Monolith, the fastest hash function to-date.</h4><p><em>This work is the result of a collaboration between Horizen Labs and various universities and other companies, including Ethereum Foundation and Graz University of Technology. For more details we refer to the </em><a href="https://eprint.iacr.org/2023/1025.pdf"><em>full paper</em></a><em>.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0LVI-Q57Ih7o3FGAz5eY9Q.jpeg" /></figure><p>The evaluation of hash functions is a major bottleneck in many modern proving systems. While using standardized hash functions such as SHA-2 or SHA-3 is certainly possible, using these classical constructions often result in a fast plain evaluation but <strong>expensive proof generations</strong>.</p><p>In recent years, new “arithmetization-oriented” or “circuit-friendly” hash functions were designed for settings of computational integrity. The Poseidon hash function, one of these new hash functions, is widely used in many different frameworks and projects in the ZK space.</p><p><strong>Here we introduce Monolith, a new family of hash functions.</strong> Together with all the other recently proposed hash functions, it may seem that there are almost too many different hash functions to choose from. In the following, we’ll give a background of some clear distinctions between these proposed hash functions, before explaining Monolith and its advantages.</p><h3>Hash Functions in ZK Settings</h3><p>Some components in modern (zero-knowledge) proving systems require the evaluation of hash functions, or more precisely chains of hash function evaluations. In Plonky2, this step needs a significant amount of the total time required to generate a proof.</p><p>Symmetric cryptographers have recently started to design hash functions to make modern proving systems more efficient. Multiple of these hash functions are now proposed every year, which makes it difficult to maintain an overview of the different tradeoffs.</p><h3>From Poseidon to Newer Approaches</h3><p>Generally speaking, components with a <em>low degree</em> when written down as a mathematical function are more efficient in (zero-knowledge) proving systems. For example, the function f(x) = x³ is generally more efficient than g(x) = x⁸²⁶³¹⁷. The idea for the Poseidon permutation was, therefore, to only use low-degree components and to iterate them until a sufficiently large degree is reached in order to withstand cryptographic attacks. Of course, this means that potentially many of these iterations are necessary in order to reach a very large degree.</p><p>Hash functions like <a href="https://medium.com/@horizenlabs-tech/introducing-poseidon2-559c1b33b102">Poseidon2</a>, Neptune, and GMiMC-based approaches follow the same approach. While many iterations of low-degree components (or “rounds” in symmetric cryptography terms) are needed, these functions usually provide a good plain performance (i.e., a fast computation time on software).</p><h3>From Low-Degree Components to High-Degree Components</h3><p>In 2018, the Friday hash function was proposed. The main idea of the paper is that using exclusively low-degree components may not be the best approach when reducing the number of constraints (i.e., increasing the circuit efficiency) in a proving system. In particular, the authors use the fact that the generally high-degree inverse function <em>f(x) = x^(-1)</em> can be rewritten as <em>f(x) = x^(-1) = y</em> if and only if <em>x*y</em> = <em>1 </em>for a nonzero x (some details are omitted for simplicity). This means that an otherwise high-degree function can be represented as a degree-<em>2</em> constraint (degree <em>2</em> due to the multiplication of <em>x</em> and <em>y</em>).</p><p>While the Friday hash function was broken shortly after its publication, its main idea, later named <em>non-procedural computation</em>, is still a very relevant result. Indeed, the popular and efficient hash functions Rescue and Rescue-Prime and newer ones such as Griffin and Anemoi follow exactly this approach. The advantage is that fewer rounds are needed to achieve cryptographic security, and thus the circuit efficiency in terms of constraints can often be increased significantly. However, the high-degree functions need to be evaluated in software when computing a hash value, and these evaluations are generally expensive. As a result, hash functions following this approach achieve higher circuit efficiency, but often a lower plain performance in software.</p><h3>Combining Good Plain Performance with Circuit Efficiency</h3><p>The two approaches shortly described above essentially offer two different tradeoffs. If we want to achieve the fastest hash computation, we opt for the first approach. If we want to reduce the number of constraints and hence achieve more efficient proofs, we opt for the second approach. But what if we want to achieve both? We could then efficiently compute hash values used in the proving system while at the same time maintaining a circuit-friendly representation in terms of constraints.</p><p>Luckily, a new component, called the <em>lookup argument</em>, allows us to do exactly that. In particular, it allows us to evaluate <em>any</em> function f(x) = y efficiently inside the circuit, as long as x and y cannot take too many different values (for example, 256 different values is perfectly fine). Following this definition, the function f can then essentially be defined as a small “lookup table”, where for each of the different input values a specific “output” or “result” is chosen. In software, this can be implemented rather efficiently using only memory accesses to different addresses.</p><p>Arguably, the first new hash function following this approach is <a href="https://www.rc-hash.info/">Reinforced Concrete</a> from 2021. It was immediately the fastest hash function for a particular type of proving system. Unfortunately, however, it isn’t possible to use Reinforced Concrete efficiently in other proving systems. This issue was solved with the Tip5 hash function in 2023, which makes it possible to increase the performance in proving systems for which Reinforced Concrete was not designed.</p><p>This already brings us to Monolith, which is the most recent hash function following the lookup-based approach at the time of writing this document.</p><h3>What is Monolith?</h3><p>Just like Poseidon or Poseidon2, Monolith is a family of hash functions optimized for zero-knowledge protocols (or, more generally, computational integrity use cases). By default it supports 31-bit and 64-bit prime fields, which have gained popularity recently due to their advantageous implementation characteristics. Indeed, arithmetic operations like additions and multiplications are particularly efficient when using these fields.</p><p>Moreover, Monolith relies on the new “lookup argument” to speed up its computation. However, in contrast to other lookup-oriented schemes like Reinforced Concrete or Tip5, the lookup table is not actually stored in the software implementation, and instead simple CPU-friendly instructions are used. This has the following two advantages.</p><ol><li>It makes a parallelized implementation comparatively straightforward, which helps making it faster than actually using the lookup tables directly in software.</li><li>It allows for a constant-time implementation, which is not possible for Reinforced Concrete or Tip5 in an efficient way. This mitigates the risk of side-channel timing attacks, which have for example been applied to AES in the past.</li><li>To the best of our knowledge, this is the first time that CPU-friendly lookup-based S-boxes over a binary field are used in combination with a larger element of a prime field.</li></ol><h3>How does Monolith work?</h3><p>Similar to the Poseidon or Rescue permutation, the Monolith one consists of multiple round functions. A single round function is defined as given in the following illustration.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/866/1*k3iBWvhFIWVn85Bin3Lqlw.png" /><figcaption>Illustration of a single round function</figcaption></figure><p>One round is divided into Bars, Bricks, and Concrete. Concrete is defined by a matrix multiplication and Bricks is essentially a nonlinear component called a “Type-3 Feistel network” in the area of symmetric cryptography. The most novel component is Bars, which implements the lookup-based behavior. It is responsible for achieving security against algebraic attacks while still being efficiently computable. Monolith uses 6 rounds, i.e., it iterates the above round function 6 times.</p><p>The components Bricks and Concrete are responsible for the security against statistical attacks. Bricks is chosen such that the number of multiplications is minimized. Indeed, while many competitors like Poseidon, Rescue, or Tip5 use low-degree monomial power maps such as f(x) -&gt; x⁷, using the square map x -&gt; x² reduces the number of multiplications significantly. Moreover, it means that we only need degree-2 constraints for this layer, which is again a major advantage of Monolith.</p><h3>Applications</h3><p>We suggest using Monolith when two conditions are fulfilled. First, a proving system focusing on small prime fields is needed. This is the case for most FRI-based approaches, as used for example in Risc0, Plonky2, and Plonky3. Moreover, the proving system should support the lookup argument. Implementing Monolith without the lookup argument is certainly also possible, but it results in a larger proving cost.</p><p>We implemented Monolith and compared its performance against competing constructions. Our focus initially was plain performance, but of course the circuit performance also played a major role during the design phase.</p><p>In the following table, we analyze the plain performance of Monolith.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/608/1*tvOb7ct4j912h6mptZE5vw.png" /><figcaption>Monolith compared with other popular hash algorithms</figcaption></figure><p>As can be seen, Monolith is significantly faster than all other arithmetization-oriented (circuit-friendly) constructions, especially when being used in compression mode with a state size of eight 64-bit elements. This particular instance is even faster than SHA-3, which makes Monolith the first circuit-friendly construction faster than a popular classical hash function.</p><p>In the next table, we compare the circuit performance of Monolith. Here we focus on the number of lookups being used and on the area-degree product, which gives a good indication of how efficient the function is when implemented in an arithmetic circuit.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/776/1*z5VktyQSRTwPHgRytOlsNQ.png" /><figcaption>Monolith circuit performance comparison</figcaption></figure><p>We can observe that Monolith is very efficient also in terms of circuit performance. Indeed, its major advantage of having a native degree of only 2 makes it possible to use many different tradeoffs when writing the circuit. This is not the case for most of the competing designs.</p><p>We emphasize, however, that comparing the circuit performance of different hash functions is in general a nontrivial task. This is mainly due to the fact that various different tradeoffs are possible.</p><h3>Conclusion</h3><p>The Monolith family of hash functions is specifically tailored towards lookup-based proving systems and exploits this fact in order to achieve a plain performance very similar to that of SHA-3. In some cases, it’s even faster.</p><p>While being very fast in a software implementation, Monolith is also circuit-friendly and supports various efficient arithmetization approaches.</p><p>Markus Schofnegger, <a href="/service/mailto:mschofnegger@horizenlabs.io">mschofnegger@horizenlabs.io</a></p><h3>Further Reading</h3><p>Monolith: <a href="https://eprint.iacr.org/2023/1025">https://eprint.iacr.org/2023/1025</a><br>Reinforced Concrete: <a href="https://eprint.iacr.org/2021/1038">https://eprint.iacr.org/2021/1038</a><br>Tip5: <a href="https://eprint.iacr.org/2023/107">https://eprint.iacr.org/2023/107</a><br>Poseidon: <a href="https://eprint.iacr.org/2019/458">https://eprint.iacr.org/2019/458</a><br>Poseidon2: <a href="https://eprint.iacr.org/2023/323">https://eprint.iacr.org/2023/323</a><br>Rescue: <a href="https://eprint.iacr.org/2019/426">https://eprint.iacr.org/2019/426</a><br>Griffin: <a href="https://eprint.iacr.org/2022/403">https://eprint.iacr.org/2022/403</a><br>Anemoi: <a href="https://eprint.iacr.org/2022/840">https://eprint.iacr.org/2022/840</a><br>Risc0: <a href="https://www.risczero.com/">https://www.risczero.com/</a><br>Plonky2: <a href="https://polygon.technology/blog/introducing-plonky2">https://polygon.technology/blog/introducing-plonky2</a><br>Plonky3: <a href="https://github.com/Plonky3/Plonky3">https://github.com/Plonky3/Plonky3</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6980f406af0e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Best of Both Worlds: How to Transform ZK Proofs]]></title>
            <link>https://medium.com/@horizenlabs-tech/the-best-of-both-worlds-how-to-transform-zk-proofs-951c9b3d3bcd?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/951c9b3d3bcd</guid>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[zkstark]]></category>
            <category><![CDATA[zkp]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Mon, 22 May 2023 12:35:07 GMT</pubDate>
            <atom:updated>2023-06-05T08:07:52.803Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Plonky2 is an efficient ZKP system for constructing succinct non-interactive arguments of knowledge. Groth16 is a widely used ZKP system based on bilinear pairings, known for its strong security and efficiency in generating zk-SNARKs. In this article, discover how Horizen Labs’ research aims to revolutionize both worlds to make them more decentralized and scalable.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*H1l-lzhL27FP01vKhM_Clw.jpeg" /></figure><p><strong>Using “wraps” to transform a STARK (Plonky2) to a SNARK (Groth16), achieving a smaller and faster zero-knowledge proof.</strong></p><p>At Horizen Labs, we have a strong cryptography team specializing in the usage of zero-knowledge proofs (ZKPs). Two types of ZKPs used in blockchain are STARKs and SNARKs. STARKs are transparent and fast, while SNARKs have smaller proofs. While these two types of ZKPs are often used separately, our team has recently discovered how to transform STARK (Plonky2) to a SNARK (Groth16) in order to reduce proof size and increase speed.</p><p>In this blog post, we will delve into the significance of this transformation and explain how Horizen users will benefit from it.</p><p><strong>Introducing zero-knowledge technologies</strong></p><p>Zero-knowledge technologies refer to a class of cryptographic protocols and systems that allow one party to prove to another that it knows certain information without revealing any additional details, thereby preserving privacy and confidentiality while still allowing verification. These technologies have applications in secure authentication, secure communication, and privacy-preserving computation.</p><p>Zero Knowledge Proof (ZKP) technology is used in the blockchain industry in several ways. Let’s see some examples:</p><ul><li><em>Scalable and efficient verification</em>: ZKPs improve blockchain scalability by providing concise proofs for complex computations, enabling faster verification and reducing computational overhead.</li><li><em>Identity and Authentication</em>: ZKPs enhance secure identity systems on the blockchain, allowing users to prove their identity or attributes without revealing unnecessary personal information, enabling secure logins and selective data disclosure.</li></ul><p>Now let’s dive into the Plonky2 and Groth16 zero-knowledge proofs.</p><h3>Deeper Dive into Plonky2 and Groth16</h3><p>Plonky2 and Groth16 are two types of zero-knowledge proofs (ZKPs) used in blockchain technology.</p><p><a href="https://polygon.technology/blog/introducing-plonky2">Plonky2</a> is a STARK that uses a technique called Plonk arithmetization to achieve incredibly fast proving times (only 170 milliseconds on an average laptop), making it highly recommended for use in our sidechains. However, Plonky2 has a drawback: its proof size can be quite large, ranging from 50 to 130 kilobytes depending on the configuration.</p><p><a href="https://www.zeroknowledgeblog.com/index.php/groth16">Groth16</a> is a SNARK that uses a different technique called R1CS relying on elliptic curve pairings. Groth16 has one of the smallest proof sizes of any ZKP, at only around 300 bytes. However, its proving time is slower than Plonky2, taking anywhere from 50 to 100 times longer.</p><p>While these technical details may seem complex, they are essential to understand the benefits and limitations of each ZKP type. In the next section, we will explore how we planned to transform Plonky2 to Groth16 with ‘look-up arguments’.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*F5FeKT0uVgM_xrljVx-Jaw.png" /><figcaption><strong>¹</strong> Measured on a laptop with processor Intel Core i7–10870H, memory 16 GB RAM 3200 MHz. Circuit benched: 2000 Poseidon Hashes.</figcaption></figure><p><strong>Wrapping</strong></p><p>In the context of zero-knowledge proofs, a “wrap” is a way of transforming a proof for a particular statement from one proving system to another. Wraps can be useful in situations where one proving system has certain limitations or drawbacks, and it is necessary to switch to another system in order to achieve better performance or other benefits.</p><p>In this scenario, we used a “wrap” to transform a Plonky2 proof into a Groth16 proof. The main problem with using a “wrap” to transform a proof from one proving system to another is that the two systems may not be fully compatible with each other. This means that the wrapping process can require a lot of extra checks to make sure everything works correctly, which can be very time-consuming and expensive in terms of computer resources.</p><p>However, we have found a way to reduce the number of checks needed by using something called “look-up arguments”. This means that the wrapping process will be faster and more efficient, but it may result in slightly larger proof sizes.</p><p><strong>How does it benefit the user?</strong></p><p>The use cases of zero-knowledge technologies are the same depending on the protocols used. As mentioned in the introduction, it allows verifying information without revealing it.</p><p>Using “wrapping” to transform a Plonky2 proof into a Groth16 proof allows the end user to benefit from the best of both worlds of SNARKs and STARKs.</p><p>In fact, Groth16 proofs are cheaper to verify on an EVM chain because of their smaller size and the simplicity of the operations to perform on the verifier side.</p><p>Thus, the scalability of Plonky2 can be used to make off-chain recursions of proofs — where the requirements are simpler — and then use Groth16 to post a rollup on the L1.</p><p>That is scalability at reduced cost. Speed and low cost with the bonus of improved decentralization with the same security. This can translate into low transaction fees to perform cross-chain transactions while being very fast.</p><p>In other words, a SNARK/STARK protocol is even more suitable for enterprises, developers, and end users in the blockchain industry.</p><p>Daniele Di Tullio, <a href="/service/mailto:danieled@horizenlabs.io">danieled@horizenlabs.io</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=951c9b3d3bcd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Introducing Poseidon2]]></title>
            <link>https://medium.com/@horizenlabs-tech/introducing-poseidon2-559c1b33b102?source=rss-b632385be288------2</link>
            <guid isPermaLink="false">https://medium.com/p/559c1b33b102</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[zero-knowledge]]></category>
            <dc:creator><![CDATA[Horizen Labs Tech]]></dc:creator>
            <pubDate>Tue, 11 Apr 2023 18:37:57 GMT</pubDate>
            <atom:updated>2023-07-05T19:59:02.910Z</atom:updated>
            <content:encoded><![CDATA[<h4>The upgraded hash function optimized for speed and ease-of-use in zero-knowledge applications</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FRSbGMm-NHng2gEcstUkWg.jpeg" /></figure><p>Efficient hash functions play a major role in modern zero-knowledge (ZK) settings. One of these hash functions, Poseidon, has found use in many of the currently used protocols, including Zcash and Mina. However, improvements can be made to its performance, functionality, and usability to adopt it for a wider range of applications. We identify those improvements and present Poseidon2, a faster version of Poseidon.</p><p><em>To advance the application and adoption of zero-knowledge technology, Horizen Labs collaborated with Ethereum Foundation and Ponos Technology on Poseidon2. For more details we refer to the </em><a href="https://eprint.iacr.org/2023/323.pdf"><em>full paper</em></a><em>.</em></p><h3>Hash Functions in ZK Settings and Poseidon</h3><p>In zero-knowledge (ZK) settings, hash functions are important for ensuring the accuracy and security of information. There are several efficient hash functions used in ZK settings, including Poseidon, Rescue, Griffin, and Anemoi. Among these, Poseidon is the most widely used and is found in many ZK protocols like our ginger-lib library used in our chain network.</p><p>Compared to traditional hash functions like SHA-2, Poseidon is much more efficient in ZK settings. However, its performance outside of the proving system is still a bit slow because of its complex internal components. To address this issue, we have developed a new version of Poseidon called Poseidon2, which is faster and more efficient.</p><h3>What is Poseidon2?</h3><p>Poseidon2 is a new and improved version of Poseidon, a popular hash function used in many zero-knowledge protocols. Poseidon2 is designed to be faster and more efficient than the original version.</p><p>One of the benefits of Poseidon2 is that it’s easier to use. It can be used like any other hash function, but we also recommend using it with a more efficient compression function, especially when computing Merkle trees.</p><p>Another advantage of Poseidon2 is that it’s simpler and more memory-efficient than the original version. This means it can achieve maximum performance without requiring any changes to the algorithm, which was not the case for the original Poseidon.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*14LmMJGCBa5bWtU_PhOG1g.png" /></figure><h3>Applications</h3><p>We recommend using Poseidon2 in all use cases where Poseidon has proven its efficiency in the last couple of years. Comparing the original Poseidon and Poseidon2 in various popular settings, we observe that the latter gives a performance boost by a factor of up to 4. <em>This makes Poseidon2 currently one of the fastest hash functions optimized for zero-knowledge applications.</em></p><p>In particular, together with the newly recommended compression mode, Poseidon2 is significantly more efficient for Merkle tree computations. We see a plain performance improvement over the original Poseidon in sponge mode by a factor of up to 5, while at the same time being around 30% more efficient in proving systems.</p><h3>Conclusion</h3><p>With Poseidon2, we improve the state of the art in fast hashing for zero-knowledge use cases. We achieve our goals by optimizing various internal components of the original Poseidon hash function, and we also show that our modifications do not decrease the advertised security level.</p><p>Markus Schofnegger, <a href="/service/mailto:mschofnegger@horizenlabs.io">mschofnegger@horizenlabs.io</a></p><h3>Further Reading</h3><p><em>For a technical deep-dive, check out </em><a href="https://hackmd.io/@hackmdhl/B1DdpVmK2"><em>Faster Hashing in Zero-Knowledge Settings</em></a><em>.</em></p><p>Poseidon: <a href="https://eprint.iacr.org/2019/458">https://eprint.iacr.org/2019/458</a><a href="https://eprint.iacr.org/2019/426"><br></a>Poseidon2: <a href="https://eprint.iacr.org/2023/323">https://eprint.iacr.org/2023/323</a><a href="https://eprint.iacr.org/2022/403"><br></a>Rescue: <a href="https://eprint.iacr.org/2019/426">https://eprint.iacr.org/2019/426<br></a>Griffin: <a href="https://eprint.iacr.org/2022/403">https://eprint.iacr.org/2022/403<br></a>Anemoi: <a href="https://eprint.iacr.org/2022/840">https://eprint.iacr.org/2022/840<br></a>plonky2: <a href="https://polygon.technology/blog/introducing-plonky2">https://polygon.technology/blog/introducing-plonky2</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=559c1b33b102" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>