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.
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.
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.
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
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).
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:
@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?
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.
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?
@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.
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?
There is an ongoing effort to have host functions for ZK integration here from @achim
I dont know how it will be used though.
Yes, that’s the meaning of ‘ZK cores’ in this context.
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. 
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: risc0/examples/wasm at main · risc0/risc0 · GitHub
Maybe such a solution could be adapted for a new type of parachains that are natively zkRollup?
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.
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.
If anyone’s interested, Sovereign just released their SDK for ZK rollups, which is supported by Avail - the substrate DA solo-chain.
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?
Sovereign targets STFs based on risc0. risc0 is a zkVM that implements RISC-V ISA. Being zkVM means that they can provide ZK proofs of execution. Sovereign doesn’t support ORs.
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.
I am rather dubious that a) it’s really that easy b) makes sense c) that it will be that much “faster”. The throughput of a ZK rollup might not be limited by ZK proving that much. I say that because it seems to be possible to remove proving from the critical path and it also seems to be possible to parallelize it. Therefore, it then becomes mostly the question how much hardware you can throw on proving and how much latency you can tolerate.
Yes, 10k to 100k times less CPU time sounds more correct. It’s maybe not worth the effort of course, really depends…