Six Moonshot ZK Applications
In the last three years, we have seen an explosion in application-level innovation on platforms like Ethereum. However, recent work in DeFi and decentralized governance has often focused on iterating on or permuting existing mechanics—in the most uninspiring cases, as Vitalik put it, "giving people tokens, and letting people earn yield on their tokens, and tokenizing the yield, and earning yield on the yield tokens...".
While novel project ownership models, improvements on wallet or dapp UX, and experiments with new community incentivization mechanisms are important for pushing adoption forwards, they are less likely to move the bottom line on what is fundamentally possible with decentralized tech. To raise the ceiling on what decentralized applications are even capable of doing, we need to leverage new technology.
We believe that new tech like zero-knowledge cryptography will play a key role in a next generation of Ethereum applications. ZK crypto is a powerful and general-purpose tool enabling a wide variety of scalability and privacy primitives. Those who have read our essay on crypto-native gaming will find this thesis familiar: the next step function in Ethereum apps won't come from doing existing stuff better—it will come from being able to do new things that weren't possible before.
Here are six ZK projects we're excited about, ranging from "prototype in production" to "sci-fi moonshot with a 10% chance of working." Much of this builds off of the excellent work done by Applied ZKP project teams supported by the Ethereum Foundation and others. 0xPARC supports R&D on projects like these via grants and contracts.
Decentralized MMO Strategy Games: Highly programmable strategy games similar to Starcraft or Eve Online, on the blockchain.
Secret Data Marketplaces: Marketplaces for users to transact secret or encrypted data.
Minecraft on the Blockchain: Rich, procedurally-generated worlds that are entirely on-chain.
Decentralized Machine Learning Oracles: Matrix arithmetic, regression, and even neural network execution on-chain.
Private Asset / Inventory Commitments: Fully decentralized TCGs, where games (and not just card ownership) are on the blockchain; private inventories in digital worlds.
ZK Message Board: Fully-decentralized message boards (i.e. a Reddit analog) that give mainstream users privacy and power over their data.
Decentralized MMO Strategy Games
Mass-market RTS, TBS, or MMO persistent strategy games, like Starcraft/Civilization/Eve Online (respectively), entirely on the blockchain.
Cryptographic fog of war, using zkSNARKs to hide the location of units in a shared digital world.
One level deeper
Without zkSNARKs or similar techniques, any fully on-chain MMO game must be a complete information game, meaning that basic strategy game mechanics such as fog of war are impossible. Using zkSNARKs, we can hide location on a shared map, creating a decentralized fog of war—a key missing element in on-chain RTS (prior to Dark Forest).
Dark Forest is in production beta as of mid-2020.
A prototype of a new strategy game is being built.
Blockchain MMO scalability: Not a ZK question, but an MMO question broadly - we can currently support several thousand players on-chain on a side chain. How do we get to millions?
Private Data Marketplaces
On-chain data marketplaces where users can transact secret or encrypted data.
zkSNARKs can be used to design private data escrow smart contracts. These contracts allow data sellers to share encrypted data with buyers, while proving that the private data being transacted does indeed satisfy some desired property that the buyer cares about. For example, I could sell another Dark Forest player the coordinates of a common enemy's home planet, conducting the transaction privately but also verifiably and completely on-chain.
One level deeper
Private data, such as Dark Forest planet hash pre-images or TornadoCash withdrawal notes, can be transacted on chain credibly (i.e. with smart contracts verifying that the correct underlying data is being exchanged) and privately (only buyer and seller can decrypt the data, unless either chooses to reveal publicly).
With a bit of additional work, this construction can also allow the creation of on-chain markets for private off-chain content. A marketplace could allow people to auction off private content with certain properties:
a dataset with certain aggregate statistics
a high-res image that downsamples to a known low-res image
an image which a publicly-known ML model classifies as a cat (see ZK-ML section)
a set of ML model parameters which achieves a desired performance on a task
Nick Ulven, a student from ETHUniversity, has a proof of concept implementation here.
UX: Some of these constructions involve more back-and-forth than is desireable. For example, data and payment must be held "in escrow," necessitating the seller to make multiple blockchain transactions to complete an exchange.
Performance: The ZK circuits necessary to prove that some secret data has certain desired properties may be infeasible.
Procedurally-Generated Virtual Worlds on Blockchain
Fully crypto-native and procedurally-generated virtual worlds, as rich as Minecraft.
Procedural generation algorithms like Perlin Noise implemented in zkSNARKs.
One level deeper
Complex procedural generation algorithms are too expensive to run in the EVM. However, ZK proof verification is always constant-time, and Perlin noise, one of the most fundamental procedural generation algorithms, is possible to implement inside of a zkSNARK.
Last August, the Dark Forest team implemented a bare-bones Perlin noise circuit that is in now in production in Dark Forest; this circuit is also used in the unnamed new strategy game.
0xPARC and ETHUniversity students are prototyping a procedurally-generated, open-world on-chain RPG.
Configurability: Our Perlin circuit is not very configurable; it relies on a number of hacks and hardcoded components, including hardcoded gradients and a specific SNARK-friendly interpolation function. What are the features that worldbuilders and procedural generation engineers care to be able to modify, and can they be efficiently implemented in a SNARK?
ZK circuit performance: Most consumer machines take thousands of milliseconds to generate SNARK proofs for our bare-bones Perlin SNARK. Are Perlin noise functions with more octaves or other auxiliary features feasible to implement?
Arithmetic operations, numerical methods: To implement more complex noninteger operations, we may potentially have to rewrite SNARK-friendly real number approximation arithmetic (analogs to floating point math) from scratch.
ZK Machine Learning
On-chain execution of machine learning algorithms, such as regression or neural networks—optionally with strong privacy guarantees.
Implement matrix arithmetic, regression algorithms, neural networks, and other machine learning algorithms inside zkSNARKs.
One level deeper
Machine learning algorithms are too expensive to run on-chain directly. But by putting regression and other machine learning algorithms inside of a zkSNARK, we would be able to execute models off-chain and verify the correct execution of these models on-chain. ZK also enables us to optionally hide model parameters, or to hide private (but pre-committed) test data that models are executed on.
Being able to execute machine learning algorithms on chain would have a number of applications.
If we have access to an on-chain ZK verifier for discriminator model execution, we have an "oracle" that can (for example) trustlessly classify images as horses vs. ducks.
ZK proofs for ML model execution would enable personalized ad/attention auctions that still allow users to control their data and maintain privacy. In bidding for ad attention, clients would generate ZK proofs that public "recommendation scoring" algorithms output certain results on the user's private demographic or psychographic data.
Two students (Peiyuan Liao and Milo Cress) from ETHUniversity have implemented linear regression in circom—generating a ZK proof that a private regression model achieves a certain accuracy on a public dataset.
ZK Circuit Performance: Can more complex models than linear regression be implemented efficiently in ZK?
Arithmetic operations, numerical methods: To implement more complex noninteger operations, we may potentially have to rewrite SNARK-friendly real number approximation arithmetic (analogs to floating point math) from scratch. Peiyuan has implemented a first pass at SNARK-friendly quantization and dequantization of model parameters.
Adversarial attacks: Generating adversarial test data for public models (or generating models with known adversarial outputs) is well-understood, which presents a problem for on-chain ML models that are treated as "oracles." This problem is exacerbated if datasets or model params are private—people with knowledge of private model parameters may be able to "backdoor" these ZKML systems. For transparency and to prove neutrality of models, maybe you'd also need to put model training someday in a SNARK, which is seems much harder (if not impossible).
Private Asset / Inventory Commitments
Fully decentralized TCGs where entire card games, and not just card ownership, are executed completely on-chain (or in state channels). These constructions can also be applied to management of private asset sets and inventories more broadly.
zkSNARKs can be used to implement primitives like privately rolling random items, adding items to a private inventory, withdrawing items from said inventory, and combining items in said inventory.
One level deeper
Card games (or more generally, games with private inventories) have been notoriously hard to implement in decentralized settings, dating back to the seminal paper on mental poker. Subproblems include allowing players to privately but verifiably draw random cards, and verifying that state transitions which players make on their private hands/inventories are valid while maintaining secrecy.
Commit-reveal systems are inadequate in games where revealing full game history is undesirable (a player may not want to show their hand at the end of a round); oftentimes they must also be paired with staking or other cryptoeconomic systems that add additional complexity; finally, they impose practical upper limits on game complexity or duration due to the need to verify a complete historical game log at the end of a game.
Conversely, zkSNARKs allow us to build the necessary primitives in fairly straightforward ways—players can commit to a private "inventory" (i.e. a hand in a card game), withdraw assets, deposit assets, discard assets, combine assets, and draw random new assets privately but verifiably. This might enable:
A fully decentralized TCG, like Hearthstone.
MMORPGs with private inventories or player "banks"; asset privacy is a default expectation already in nearly all popular MMORPGs today.
I've implemented some simplified ZK constructions for drawing and playing cards from a deck, which the Dark Forest team incorporated into a proof-of-concept demo game last year. Another ETHUniversity team (Abby Lu, Shu Ge, Jennifer Pan) also showcased similar building blocks in a recent project.
ZK circuit performance: For a decentralized card game, ZK circuit constraints scale either quadratically with number of cards in the deck, or linearly with a high (hundreds of constraints) constant factor. Can we efficiently prove drawing / playing cards for decks of size ~50 or greater?
State channels: Running card games completely on-chain may be infeasible due to blockchain scalability limits. Can we use state channels, and if so, what are the ZK or cryptographic mechanisms necessary to move logic off-chain while still maintaining complete decentralization?
ZK Message Board
Fully-decentralized message boards (i.e. a Reddit analog) that give mainstream users privacy and power over their data.
Users can post messages anonymously, while using zkSNARKs to signal that they are credible (they have a certain reputation score, or they are a member of a certain group, etc.)
One level deeper
zkSNARKs allow us to theoretically build message boards with strong privacy guarantees, censorship-resistance, and expressive / granular reputation and credibility systems.
Using these constructions, anonymous whistleblowers can signal credibility ("This message is signed by me; I am a US Senator, but I won't reveal which US Senator I am" or "I am a user with at least 10m Twitter followers") without putting exact identity at risk.
In a message board with an associated upvote/downvote system, users can prove statements like "I am signing this message as someone whose posts have achieved at least X karma in the past, but I won't reveal who I am or which posts contribute to that score."
This enables online communities to separate signal from noise and to verify reputation or credibility, without requiring that a centralized party to store underlying user data.
The Ethereum Foundation's applied ZK team has produced Semaphore, a set of primitives for anonymous signaling.
Aayush Gupta and Nick Ulven from ETHUniversity have and proof-of-concept demo of a "ZK Confessions" application, similar in spirit to Semaphore. Writeup here.
UX: Current constructions require users to make multiple back-and-forth steps just to join a system or to post messages/proofs. This is a potentially unacceptable amount of friction for a social app.
Execution environment: It is unclear if such a network should be completely on-chain—can we sacrifice censorship resistance or data availability for ease of use? For example, by building on a some network of broadcaster nodes in a p2p network, rather than a robustly-incentivized blockchain.
Constructions: We don't yet have complete ZK constructions for some of the above primitives!
Shall admit to trying my hand on two of the problems as a startup and it’s pivot 2018-20. Also looked at ML one, up close as I was involved in design of data market places . Would love to hear learnings of other folks, who are open to sharing. Lot has changed in world of ZKP, but somethings remain the same …
The private data marketplace and possibly private asset commitments are all but here already through Railgun. NFT functionality not yet live but in late development. So the use case would be sell an NFT to another player / trader / customer privately through Railgun. They then create a ZKP offchain to prove ownership - which can then be used as a credential for accessing the information, design or website.