# Sudoku snark

a story by Kompact.io

# How it started

## There is a hackathon on cardano 🥳 …

## But wait! 🧐 There is a zk track

## Surely No!?

- Fundamental primitives for any zk-alg are not available in plutus

- Midnight, the much hyped zk sidechain, is essentially in stealth mode

- zk on Cardano? not possible! 😵‍💫

- Using some other chain for zk and bridging over … that’s bridging: we want zk

## … oh, hello PR#5231 👀

##

- A beast of a PR: 6 months, 230 commits, 319 files changed
- Finally merged during this hackathon

> This PR adds new built-in types and functions to Plutus Core and PlutusTx for pairings over BLS12-381, as specified in CIP-0381

## What does this mean??

- CIP-0381: plutus support for pairings over `BLS12_381`
- In other words plutus gets the built-ins that make it possible to begin genuine zk on Cardano

## So Yes! 🤯
We can zk on cardano

## First hurdle

- Only the primitives are provided; we need to implement a zk-alg
- Use it as the basis for a dapp
- And do both in a way that doesn’t break the (ex-units) bank

## 🤔 And then?

- Having zk in the latest version of plutus is one thing: running a zk dapp on cardano is quite another!

- There is no chance of running these new primitives on Cardano mainnet any time soon

## Not on L1,
but … hydra

- Hydra is Cardano-native ‘isomorphic’ L2
- Loosely - it can run plutus just like mainnet
- But we could also run it with a modified version of plutus
- Thus we could run hydra with the latest plutus and deploy our zk dapp their

No need to wait for any hardforks!

## … so we’d need to: 📋

- Create a zk validator
- Create tx-building functionality
- Bump all the Cardano libraries from plutus to hydra
- Build + deploy

(Do all this in less than three weeks, while keeping the day job 😅)

# Sudoku snark

## 🎯 Aims

- Create a non trivial zk dapp on Cardano ie demonstrable PoC
- Initial iteration of tooling/ stack
- Derisk more ambitious Cardano-based zk dapps

And conversely, non-aims:

- Larp a fantastical business based on unproven tech

## The game: 🎲
Competitive sudoku

- Trusted entity inits competition
- Contestants register
- Game master sets puzzle + multiple prizes
- Contestant claims a prize with proof of solution

By the powers of zk, the claim does not disclose the solution

## The Snark: Groth16

Why groth16?

- Relatively mature
- Relatively simple
- Can be implemented with the new primitives in plutus
- Has the smallest proof size

All of these make it the right choice for a first zk snark alg

## Components ⚒️ tooling

- Arkworks framework: generate groth16 setup and proofs
- Plutus-tx: handling plutus validators

# How it’s going?

## Links

- 🟩 rust-lib
- 🟩 haskell-lib
- 🟨 cardano-api
- 🟨 cardano-node
- 🟥 hydra

( 🟩 done — 🟨 more progress required — 🟥 much more to do )

## What didn’t get done?

- By far the most time was sunk dependency-wrangling Cardano libs, trying to bump plutus version in a Cardano node
- We managed to have a dev cluster running but key tx building features are missing for conway era
- No Cardano node ==> no hydra

## Other to-dos 📋

- Tau ceremony for setup
- Proper implementation for poseidon hash
- Select a fix for a replay attack eg additional public input and using script context
- Complete constraints in circuit
- Sexy frontend etc

# Beyond sudoku snark

## Sudoku snark is probably not the killer zk app
What is?

## 🕵️ Privacy on public ledgers

- Privacy on blockchains like Cardano is a problem (see articles ad nauseum)
- zk can make it harder to track who’s transacting with whom
- There are L1s dedicated to resolving this like zcash and monero
- There are dapps on existing chains like railgun on Eth

## Privacy on cardano

- Cardano needs a privacy solution
- This can be achieved with a zk dapp
- There are use cases for having this both on the L1 and on L2s

Sudoku snark gives us a foundation on tooling, zk gadgets, and even a choice of snark

## From here to there 🧗

- 🟩 Merkle tree gadgets
- 🟩 Distributed lists
- 🟨 Tau ceremony or plonk
- 🟨 Hydra with latest plutus
- 🟨 Hydra with incremental de/-commits
- 🟨 A system for tx fee sponsorship
- 🟥 Wrap up into an dapp

( 🟩 easy — 🟨 more work needed — 🟥 even more work … )

# Why this 🏆
should win?

##

- Sudoku snark is true to the spirit of this hackathon and track: a genuine zk dapp running on Cardano
- We are at the absolute bleeding edge of what is possible
- This PoC shows fundamental components for zk dapps on Cardano are already here
- We have a clear roadmap from here to a killer zk dapp

# The team

## @waalge

- Chief of Kompact.io
- 2 years building around cardano (eg guchi.io)
- Previously full stack dev, ML/NLP researcher
- PhD in geometry

—

## Thank you 🙏

Any questions? Please get in touch