ZK Rollups as Parachains

Tech Talk
1

ZK Rollups are an interesting scaling mechanism, and over the past couple weeks I’ve been considering how we might bring them to Polkadot as well. Here is a description of an MVP supporting ZK Rollups at the consensus layer by changing the execution cores mechanism slightly.

While I don’t think that ZK rollups are a one-size-fits-all (proving is expensive, blockspace not as flexible as Wasm), this is an interesting experiment worth prototyping.

Execution cores in Polkadot currently work as follows:

  1. assignments of parachains to cores are determined in advance
  2. collators for assigned parachains create blocks, sending them to backing validators
  3. backing validators check the blocks, and then produce a quorum allowing the parablock + metadata to be posted on-chain
  4. data is made available
  5. approval-checking leads to further checks for finality

This mechanism could be slightly modified to support ZK-Parachains

  1. same
  2. same
  3. the parablock is posted on-chain, and the ZK circuit encapsulating the parachain logic evaluates the parablock and checks its outputs
  4. data is made available
  5. ZK parablocks are skipped, as the parablock is already valid

With further improvements, such as exposing the Data-Availability layer as a service independent of execution cores, this flow could be further minimized and would easily enable things such as L3s.

33 Likes
2

Super interesting post! I also believe this idea has great potential, specially when/if ZK rollups are universal and performant enough.

For clarification, the main difference for ZK-parachains vs current approach is in the data available step 3, yes? My understanding is that with ZK-parachains the whole parachain block fits on a relay chain block which allows us to skip the availability and approval steps of the parachain protocol. Every relay chain validator will validate every parachain block by protocol construction.

3

ZK Rollups still need data availability because the state changes that result from a state transition must be available to the broader network in order to create subsequent state transitions.

The main difference is that we could in theory skip the approval-checking logic for ZK Rollups, as they could be checked by all full nodes when initially posted to the relay chain.

4 Likes
4

Can you elaborate on what kind of data would need to be available, as compared to the PoV which is currently needed for Polkadot? I had thought / hoped that the amount of data that would need to be available would be constant size for ZK proofs, but it seems like you are implying the data that needs to be made available is the similar as needed for Polkadot today.

5

I’m no expert on ZK Rollups, but I believe it would be smaller than typical parachain PoVs, as it’d basically just be a post-state diff and the block header. Maybe the block body itself too, but that doesn’t seem necessary although useful for things like block explorers.

6

I think for ZK-parachains data that needs to be available won’t be constant size. Even though ZK-proofs could be the same size (although to become ZK scheme agnostic it is better to keep it flexible) transactions data will be different every time

1 Like
7

We do not imho need more “roll ups” per se, given polkadot already is an interactive “cut n choose roll up” under a byzantine threat model.

We do otoh need whole block optimizations (WBO), or maybe some future better name, by which I mean tricks which exploit the prover-verifier dynamic of blockchains. Among these, we have ideas like:

Algorithmic WBOs are tricks like verifiers sorting in linear time, because the block producer pre-sorts, except larger. We do have some in governance, but they could become more user-friendly, and some maybe demand storage improvements.

Business logic WBOs avoid problems like MEV by fixing some choices per parablock. As an example, uniswap parachain could fix one bid-ask price per pair for the whole block, perhaps requiring the collator select transaction by running a linear program solve, but simplifying verifiers.

At a high level, smart contracts are antithetical to WBOs so you can make parachains be more fair than their competitors built upon smart contract. As logic WBOs often simplify verifiers, they also make adopting zero-knowledge logic proofs easier. In particular, a zkUniswap becomes much faster and simpler if it fixes bid-ask prices for the whole block, given the LP solver is completely orthogonal to the ZKPs.

Cryptographic WBOs mean cryptographic batching, like SnarkPack, Schnorr half-aggregation, all the Plonk batching ideas, etc. ZK roll ups need tools like this, but face other problems, which parachains already solve.

As a rule, WBOs would benefit from actually passing local memory between on_initialize, individual transactions, and on_finalize (or at least having more efficient local storage, or at least having O(1) subtree drops).

2 Likes
8

I think with the notion of Data Availability as a Service we can focus entirely on ZK rollups that live on top of parachains.

That said, I think that there are a few not-specifically-technical reasons to support this at the base layer:

  • It’s not clear exactly how good ZK rollup scaling is going to get. Future-proofing Polkadot to be able to adapt to a full ZK scaling approach is a useful strategic hedge, even though Wasm parachains should be notably faster for the foreseeable future.
  • The development focus on ZK Rollups is substantive, and it’d be useful for Polkadot to make inroads at a protocol level for this developer audience. This should help cement Polkadot as an innovation hub, particularly among smart ZK folks.

@burdges I don’t fully understand what you mean by Whole Block Optimizations, but maybe you could make a separate post outlining how that might work from top-to-bottom?

9

We’ll scale much further than our current design using parallel relay chains, which become secure once you’ve like 1000 random validators per relay chain.

We’ll watch how zk roll ups develop of course. I kinda suspect special purpose SNARKs fair much better than general purpose ones, making the field less accessible, not more accessible. Among the general ones, zkSTARKs need considerable space, so they actually fit nicely within our framework.

We’ll hopefully lure EC zkSNARK dev teams onto Polkadot with Arkworks, as well as how we’ve already done the less sexy parts like availability. Yet, once they’re here I’d idealistically expect their best zk roll ups always cost more than parachain slots, driving a pivot towards user privacy.

We’ll see… If VCs foot the bill, and users accept latency, then zk roll ups could hang around even if they really cost more under the hood.

4 Likes
10

I would also love to explore them for their benefits around privacy. In our current infra, is there a way for a parachain to validate private transactions?

2 Likes
11

@gupnik Very much so - Parachain Validation Functions are full-fledged Wasm programs, which can do anything you can normally do on a CPU, including executing ZK verification circuits. Manta is the clearest example of a project doing exactly that.

This post is specifically around making ZK verification first-class within Polkadot, so parachains themselves can be defined as a ZK circuit rather than a Wasm program that evaluates them internally.

3 Likes
12

Thanks @rphmeier. Wasm programs being able to execute ZK verification circuits makes perfect sense.

Regarding parachains defined as a ZK circuit, I am trying to develop a better understanding of what it would look like. Would it mean that the relay chain runs a native ZK verifier circuit that is agnostic to parachain logic? Or, each parachain would provide its verifier circuit (which potentially is possible already as we discussed above)? Or, could it be something else entirely?

1 Like
13

There is an ongoing effort to have host functions for ZK integration here from @achim

I dont know how it will be used though.

4 Likes
14

Yes, that’s the meaning of ‘ZK cores’ in this context.

1 Like
15

Agnostic code cannot be native of course, but…

Among elliptic curve based protocols there are only a handful of really slow procedures: scalar multiplications including subgroup checks, multi- scalar multiplications, G2 point preparation, multi- miller loops, final exponentiations, scalar multiplications etc in G_T, and FFTs for scalars and points. We’ve started adding host calls for selected procedures from this list in substrate PR 13031 linked above.

As a rule, cryptographic protocols invoke these only O(1) times during verification, although some like MIPP needs O(log n) which makes marlin O(log circuit_size) and snarkpack O(log batch_size), and some like bullet proofs need linear O(circuit_size) time, but then batching maybe improves things, sometimes dramatically ala halo2.

Importantly, there is enough variation in batching optimizations that again you cannot simply make a few native verifiers fit everyone. We do however want higher bandwidth between on-initialize, individual transactions, and on-finalize, because batching requires moving part of transactions verification into on-initialize and/or on-finalize.

Among protocols like STARKs not based upon elliptic curves, we’ll explore doing acceleration eventually, but…

There is much more variability so exactly how we what acceleration remains uncertain. It’s uncertain which protocols even dominate here too. At present STARKs have kinda poor security margins, but they’re likely fairly safe otherwise, and the otherwise maybe matters more than the security margins.

At least some lattice folk argue that lattice based zk proofs soon out perform STARKs across many applications, so maybe STARKs loose out in a few years, or maybe not really. At the same time, lattice are an quagmire of foot guns, aka job security for cryptographers, so lattices might fit poorly with the blockchain worlds’ current rushed & slipshod development practices. Expect chaos. :slight_smile:

4 Likes
16

It would seem so, I watched a risc0 presentation (seen thanks to this forum post) and they claim to have made a zkVM agnostic that can prove the execution of any arbitrary code as long as it compile to RISK-V.

They have already published all the code on github, and there are examples in rust, including 1 to prove a wasm execution: https://github.com/risc0/risc0/tree/main/examples/wasm

Maybe such a solution could be adapted for a new type of parachains that are natively zkRollup?

2 Likes
17

I don’t think it makes sense to bake in a specific application level system right now. There is an entire zoo of different projects, proof systems, etc. The jury is still out IMO which is better.

As a rule of thumb, a general purpose ZK system would be beaten hard by a specifically designed system. Therefore, I think having an abstraction where the zkparachain specifies it’s circuit/verification key, as Rob proposes, is important.

What I know for sure is that having a wasm interpreter running in a risc0 is a pretty bad idea efficiency wise.

4 Likes
18

I typically say polkadot benefits from “whole block optimizations”, which includes both cryptographic batching, like zcash+snarkpack, as well as simpler logic optimizations and even MEV defenses, like fixing the price for the whole block in a uniswap. Almost nobody else understands this term though.

Already zk roll up has several different meanings, so instead of arguing against terminology, why not add another one?

Zcash+SnarkPack is not a “roll up” on most chains. It accesses unspent UTXOs from users’ SNARKs, but then stores their nullifers and checks for double spending transparently, like Zcash does. As polkadot is already a “roll up”, if you run zcash or zcash+snarkpack on a parachain then you “roll up” the nullifer storage and double spending checks.

As snarkpack “rolls up” the Groth16 checks in zk, then we could perhaps say Zcash+SnarkPack on a parachain is a “(partial) zk roll up”, which turns out much faster than any true zk roll up because SnarkPack is much faster than accessing storage inside a SNARK.

Also, you could build a zkUniswap with multi-asset Zcash variant plus a SnarkPack variant, in which your SnarkPack variant also proves (a) the purchases and sales from the uniswap add up to some publicly stated delta in its liquidity pool, and (b) their prices all lie between the prices approved by each of user’s trades. In this, each block producer learns what the users buy & sell, and chooses the price for everyone, but then hide this behind the SnarkPack and this extra proof.

19

If anyone’s interested, Sovereign just released their SDK for ZK rollups, which is supported by Avail - the substrate DA solo-chain.

1 Like
20

There is nothing zk there since they only target risc0 and ORs on Celestia, right?

It’s likely easy to do a cargo-patchable Sovereign SDK shim, so that anything which runs on their chain could run on Frame in a parachain, except maybe a million times faster than on their risc0 zk roll up.

Any hackathons coming up?