Proving mainstream languages computations to StarkNet via zkLLVM with zkBridging as an example.

Written by Mikhail Komarov on 01 Jul 2022.

Special thanks to Ohad Barta, Nitzan Grossman and StarkWare fellows in general for discussion, adjustments and comments.

This post covers one of the applications of a =nil; `DROP DATABASE *-based Trustless Data Accessibility protocol - trustless bridging. In particular, it covers what StarkNet users could gain from retrieving proofs of various protocols.

That is right. Recently we’ve introduced our Data Accessibility protocol and a Proof Market facilitating it. A Data Accessibility protocol is supposed to be capable to provide trustless I/O to various databases through the DBMS query language unified for all the databases (Bitcoin, Ethereum, Solana, Mina, others) proved with SNARK proofs done in Placeholder proof system and a Proof Market is what facilitates it.

In particular, =nil; Proof Market provides users (no matter what kind of users - applications or protocols) with on-demand state and query proofs for three different use cases:

Trustless Data Access.If a proof consumer is an end-user application or a frontend of any kind, it could be used for accessing data on the protocol that it lives on.Trustless Bridging.If a proof consumer is a protocol (e.g. Mina), and a user of this protocol requested a state/query proof of another protocol (e.g. Ethereum or Solana), it could be used for trustless bridging of these two protocols.Pluggable Scaling.If a proof consumer is a protocol and its user (an application or otherwise) it is of the same kind a user has requested a state/query proof from (e.g. some Avalanche user has requested a state/query proof of another independent, application-specific Avalanche deployment), then it results into increasing the throughput of the original protocol cluster deployment.

And! StarkNet integration leverages the second use case - trustless bridging.

That is true. And, this Ethereum L2 could use some data from other protocols in the same way as actual Ethereum’s users - through =nil; `DROP DATABASE * and Data Accessibility protocol.

That means, we’re talking about bridging third-party protocols TO StarkNet.

Recently StarkWare started pushing forward the idea of using STARK recursion for achieving more scalability to StarkNet. It was called an “L3” concept. An “L3” concept supposes for independent StarkNet instances (any Cairo-generated logic to be precise) to bring their state proofs to StarkNet, making it possible to verify themselves in StarkNet.

In particular StarkWare supposes for Cairo/StarkNet to gain STARK verification Cairo-based logic, so Cairo-generated STARK proofs could be verified within StarkNet.

And, of course, I gotta admit that Cairo postprocessing output have almost nothing to do with legacy STARK proofs because Cairo compilation output is more of a public assignment to STARK proof generator. That means, yeah, we’re talking only about getting independent StarkNet instances verified on StarkNet.

In the same time, trustless bridging use case of =nil; `DROP DATABASE *-based Data Accessibility protocol supposes for various protocols state proofs to be generated in Placeholder proof system and ordered by whoever needs them for whatever use case.

Not so fast. Remember our integration with Mina Protocol? The one for which we’ve introduced a trick with wrapping the proof verification in another proof.

Let’s briefly remind you about that. Mina Protocol has its state proof generated in Kimchi proof system. Since strainghtforward Kimchi proof verification on EVM is too expensive, we basically have to to wrap Kimchi proof verification algorithm in another proof (using =nil; Placeholder proof system), and create a ‘proof of a successful verification’ - this can then be cheaply verified within the EVM.

So the current step by step process is as follows:

- Mina’s native state proof gets retrieved
- Auxiliary proof in Placeholder proof system is being generated
- Auxiliary proof is being submitted to EVM for the verification to happen

More detailed overview of a currently existing solution can be found in previous relevant blog posts: https://blog.nil.foundation/2021/11/01/mina-ethereum-bridge-design.html, https://blog.nil.foundation/2021/09/30/mina-ethereum-bridge.html.

So, the same trick we apply to StarkNet. Whatever protocol’s (like Solana’s or Avalanche’s) state/query proof is being generated with our Data Accessibility protocol, we can wrap its verification into Cairo-compatible STARK proof.

And that would result into…

That is right.

Let’s break this process down step-by-step.

- First of all, we need a state proof for the third-party protocol we want to bridge to StarkNet, generated in the Placeholder proof system, and wrapped in a Cario-compatible STARK proof. Let’s say this third-party protocol is Solana (but in reality, it could be any protocol supported by =nil;). So the user or application wanting to bridge Solana’s data to StarkNet has to retrieve this proof from =nil;.
- Then it is required submit the retrieved proof to Cairo’s STARK proof verifier. From StarkNet’s perspective, a =nil;-generated data proof will be identical to the natively generated Cairo-based proof.
- After the proof is submitted to StarkNet in-Cairo proof verifier, the user (or StarkNet-based application) receives the relevant Solana’s data - and voila! Solana’s data is being safely and trustlessly used in StarkNet.

Again. That is right. But! Who said we cannot exploit such a concept in a wrong way bringing some additional capabilities to StarkNet through =nil;?

In particular, StarkWare’s vision on a “L3” concept is pretty much described as a set of independent StarkNet instances bringing themselves to the actual L2 StarkNet.

But, funny fact is, =nil; binds this concept over by vanishing the difference between L1s and L3s by litreally binding over various L1s to become L3s.

**So funny thing is that every L1 now becomes an L3 through =nil;**.

Other protocols, supported by =nil; are also going to be available for StarkNet-compatible state/query proof generation and retrieval. For example, Solana’s integration is on its way.

Once this is fully delivered, we’d love to have some help with integrations. We need bridges and wallets to use this. Transferring user-specific data from different databases to StarkNet is what requires application-level wrapping. We’d be happy to become a base layer for that. Reach us out via Telegram (https://t.me/nilfoundation) or via Discord (https://discord.gg/KmTAEjbmM3) regarding this.