Bounty Proposal: Privacy & ZKP Curated Bounty
ZKValidator (ZKV) in collaboration with STARKs network is proposing two zkp related bounties. In addition, ZKV would like to put itself forward for the role as a curator of this bounty. The bounties amount to a total of 880KSM and have been compiled with the goal to enable experimentation with Zero Knowledge primitives (in this case STARKs) via new pallets. We describe each of the bounties separately below. If one of the two proposals is rejected in discussion we will remove it and reduce the bounty amount accordingly. STARKs are a type of Zero Knowledge proof which can be used for privacy and scaling of blockchain applications and infrastructure. STARKs can be a better choice over SNARKs as they offer simpler cryptographic assumptions and don’t require a trusted setup at the cost of larger proofsize. See here for the bounty proposal, comments are welcome. https://docs.google.com/document/d/1QdlVl2-AV82helNE7UFdpevd0-ItURKNflOAkd3e5yY/edit?usp=sharing
Comments (4)
Comments (4)
STARKs are a type of SNARK with no trusted setup or cryptographic assumptions more dodgy than Fiat-Shamir. They have large proof sizes, in the 100s of kilobytes but relatively fast proving and verifaction time, due to the lack of complex cryptography involved. They are primarily being pushed by the commercial STARKware, who appear to be keeping a closed source prover with open source verifier and less optimized prover.
One other difference to the STARK approach from many other SNARKs, which is actually independent of the underlying technology, is that they target proving the correctness of program execution rather than circuits. Distaff VM is a VM deleoped by Bobbinth independently of STARKware for compiling program execution to STARKs. As an independent project, it is entirely open source.
Glacier Blockchain are building an implementation of Distaff VM for substrate. This implementation is far from perfect so far; in particular we cannot do STARK verification in the Wasm runtime without specialised host calls. This means it cannot be used in parachain logic yet, unless the Polkadot runtime environment implemented these as well by including the library, which we would not do for an application this specialied. Also the prover is independent of substrate.
This bounty would fix both of those by implementing the verifier fully in the runtime and by allowing off-chain workers to talk to the prover.
The original implementation was funded by Web3 foundation's open grant program. While it was being built, it became apparent that converting the Distaff VM's code to nostd would be more complex than imagined and that was removed from the scope of the grant. Given that the original open grant program grant overrun substantially, I'm glad that this grant is in the form of a bounty rather than a direct grant. I understand that ZKValidator know a thing or two about ZK proofs. Would you feel comfortable with evaluating the code quality of a substrate pallet?
STARKware will release their own new VM Cairo any day now. This is a risk that this will obsolete Distaff VM. How confident are we that Distaff VM will keep being maintained? If not, given open source tooling for Cairo, would that be a possible alternative?
Who will use Distaff VM on Substrate? I understand that GBC are planning to work on identity stuff using it?
STARKware are targetting ZKRollups for STARKs on Ethereum because the large proof size is not so important if you only have one proof per block, but the fast proving time (if you use their closed source prover) allows STARKs to be competitive with other SNARK schemes. I don't think anyone doing ZKRollups on Substrate is thinking of using STARKs yet.
@Alistair Thank you for your review. Here are my thoughts regarding your questions.
- Regarding the original open grant project
In the open grant project, we mainly focused on understanding and extracting the verifier part of the Distaff VM and integrating it into Substrate. We realized re-writing the Distaff VM using no_std Rust was technically doable but it was beyond the time budget for an open grant project. So we will be more than happy if the first milestone in this bounty can be solved by other open source teams. If not, we will do it by ourselves after we have finished the off-chain worker milestone.
- Regarding Cairo
StarkWare is the inventor of the zk-STARK technology and their new product Cairo will provide STARK proof generation/verification for general purpose computations. The Distaff VM does the same thing in an open source fashion. We know Cairo is based on the von Neumann architecture and Distaff VM is a stacked based machine. Few implementation details of Cairo are publicly available. But with the information we have, there is no obvious reason why the Distaff VM will be inferior to Cairo.
We don't know whether or how much of Cairo will be open sourced. But we do know StarkWare's attention is focused on Ethereum right now. That gives our project an advantage in the Polkadot/Kusama network. There is actually much more than the prover/verifier of proofs for a useful zk-STARK service. The prover needs to be implemented in various forms, fit for Web app and mobile apps. There is also the off-chain data service which will store STARK proofs and play nicely with on-chain logic. And there is an economic system which will drive the whole thing running. The point is, once our services are embedded into each parachain and our economic system are coupled with each other, we would be hard to replace.
We have had quite a lot of discussions with Bobbin, author of the Distaff VM project. The major part of the Distaff VM has actually been completed. The remaining work will be some improvement on efficiency and functionality. Together with Bobbin, we will make sure the Distaff VM maintained and improved for the Starks Network project.
- Use cases for STARKs in Polkadot/Kusama.
We can see a new paradigm of computation that will be enabled by the Starks Network—one that truly fits into the vision of Web3. We call it self-proving computation. Imagine users never have to send their data to 3rd parties for computation/analysis. Instead, they can do this in their mobile phone or PC and prove the correctness of their computation with a STARK proof.
The Starks Network project will play nicely with other projects in the Polkadot/Kusama ecosystem. We have good connections with KILT, Acala, Crust and Patract Labs, etc and we have discussed potential uses cases with them. Examples include privacy preserving credentials, private credit scores for DeFi, anonymous dex pools, chain throughput scaling, etc—the list will keep growing.
BTW, doing ZK-Rollup with STARK is viable. The Rollup solution from StarkWare is called Validium/Volition and they have been used in the StarkEx product for DiversiFi. We could do similar things at a later stage to scale e.g. a parathread. Imagine you can pay the same amount of dot/ksm for much higher transaction throughput—the feature will be welcomed by most parathread projects.
STARKs are a type of SNARK with no trusted setup or cryptographic assumptions more dodgy than Fiat-Shamir. They have large proof sizes, in the 100s of kilobytes but relatively fast proving and verifaction time, due to the lack of complex cryptography involved. They are primarily being pushed by the commercial STARKware, who appear to be keeping a closed source prover with open source verifier and less optimized prover.
One other difference to the STARK approach from many other SNARKs, which is actually independent of the underlying technology, is that they target proving the correctness of program execution rather than circuits. Distaff VM is a VM deleoped by Bobbinth independently of STARKware for compiling program execution to STARKs. As an independent project, it is entirely open source.
Glacier Blockchain are building an implementation of Distaff VM for substrate. This implementation is far from perfect so far; in particular we cannot do STARK verification in the Wasm runtime without specialised host calls. This means it cannot be used in parachain logic yet, unless the Polkadot runtime environment implemented these as well by including the library, which we would not do for an application this specialied. Also the prover is independent of substrate.
This bounty would fix both of those by implementing the verifier fully in the runtime and by allowing off-chain workers to talk to the prover.
The original implementation was funded by Web3 foundation's open grant program. While it was being built, it became apparent that converting the Distaff VM's code to nostd would be more complex than imagined and that was removed from the scope of the grant. Given that the original open grant program grant overrun substantially, I'm glad that this grant is in the form of a bounty rather than a direct grant. I understand that ZKValidator know a thing or two about ZK proofs. Would you feel comfortable with evaluating the code quality of a substrate pallet?
STARKware will release their own new VM Cairo any day now. This is a risk that this will obsolete Distaff VM. How confident are we that Distaff VM will keep being maintained? If not, given open source tooling for Cairo, would that be a possible alternative?
Who will use Distaff VM on Substrate? I understand that GBC are planning to work on identity stuff using it?
STARKware are targetting ZKRollups for STARKs on Ethereum because the large proof size is not so important if you only have one proof per block, but the fast proving time (if you use their closed source prover) allows STARKs to be competitive with other SNARK schemes. I don't think anyone doing ZKRollups on Substrate is thinking of using STARKs yet.
@Alistair Thank you for your review. Here are my thoughts regarding your questions.
In the open grant project, we mainly focused on understanding and extracting the verifier part of the Distaff VM and integrating it into Substrate. We realized re-writing the Distaff VM using no_std Rust was technically doable but it was beyond the time budget for an open grant project. So we will be more than happy if the first milestone in this bounty can be solved by other open source teams. If not, we will do it by ourselves after we have finished the off-chain worker milestone.
StarkWare is the inventor of the zk-STARK technology and their new product Cairo will provide STARK proof generation/verification for general purpose computations. The Distaff VM does the same thing in an open source fashion. We know Cairo is based on the von Neumann architecture and Distaff VM is a stacked based machine. Few implementation details of Cairo are publicly available. But with the information we have, there is no obvious reason why the Distaff VM will be inferior to Cairo.
We don't know whether or how much of Cairo will be open sourced. But we do know StarkWare's attention is focused on Ethereum right now. That gives our project an advantage in the Polkadot/Kusama network. There is actually much more than the prover/verifier of proofs for a useful zk-STARK service. The prover needs to be implemented in various forms, fit for Web app and mobile apps. There is also the off-chain data service which will store STARK proofs and play nicely with on-chain logic. And there is an economic system which will drive the whole thing running. The point is, once our services are embedded into each parachain and our economic system are coupled with each other, we would be hard to replace.
We have had quite a lot of discussions with Bobbin, author of the Distaff VM project. The major part of the Distaff VM has actually been completed. The remaining work will be some improvement on efficiency and functionality. Together with Bobbin, we will make sure the Distaff VM maintained and improved for the Starks Network project.
We can see a new paradigm of computation that will be enabled by the Starks Network—one that truly fits into the vision of Web3. We call it self-proving computation. Imagine users never have to send their data to 3rd parties for computation/analysis. Instead, they can do this in their mobile phone or PC and prove the correctness of their computation with a STARK proof.
The Starks Network project will play nicely with other projects in the Polkadot/Kusama ecosystem. We have good connections with KILT, Acala, Crust and Patract Labs, etc and we have discussed potential uses cases with them. Examples include privacy preserving credentials, private credit scores for DeFi, anonymous dex pools, chain throughput scaling, etc—the list will keep growing.
BTW, doing ZK-Rollup with STARK is viable. The Rollup solution from StarkWare is called Validium/Volition and they have been used in the StarkEx product for DiversiFi. We could do similar things at a later stage to scale e.g. a parathread. Imagine you can pay the same amount of dot/ksm for much higher transaction throughput—the feature will be welcomed by most parathread projects.