---
title: Sudoku snark
subtitle: a story by [Kompact.io](https://kompact.io)
mainfont: jetbrains-mono
# title-slide-attributes:
    # data-background-image: ./assets/background.jpg
    # data-background-gradient: "linear-gradient(147deg, #000000 0%, #2c3e50 74%)"
# data-background-gradient: "radial-gradient(#283b95,#17b2c3)"
# background-image: ./assets/background.avif 
background-image: ./assets/background.svg
background-opacity: "0.35"
---

# 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][pr-5231] 👀 {data-background-image="./assets/zk-pr-screenshot.png" data-background-opacity="0.3"} 

[pr-5231]: https://github.com/input-output-hk/plutus/pull/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][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

[cip-0381]: https://cips.cardano.org/cips/cip0381/

## So Yes! 🤯 <br/> 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, <br/> but ... hydra {data-background-image="./assets/hydra.png" data-background-opacity="0.3"} 

- 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: 🎲<br/> 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][groth16paper]?

- 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

[groth16paper]: https://eprint.iacr.org/2016/260.pdf

## Components ⚒️ tooling 

- [Arkworks][arkworks-gh] framework: generate groth16 setup and proofs 
- Plutus-tx: handling plutus validators

[arkworks-gh]: https://github.com/arkworks-rs

# How it's going?

## Links 

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

<span style="font-size:1rem"> ( 🟩 done --- 🟨 more progress required --- 🟥 much more to do ) </span>

## 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 <br/> 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](https://z.cash/) and [monero](https://www.getmonero.org/) 
- There are dapps on existing chains like [railgun](https://www.railgun.org/) 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 

<span style="font-size:1rem"> ( 🟩 easy --- 🟨 more work needed --- 🟥 even more work ... ) </span>

# Why this 🏆<br/> 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 {data-background-image="./assets/dp.jpg" data-background-opacity="0.3"} 

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

<a href="https://www.linkedin.com/in/dominic-algernon-wallis-123b42187/">
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" height="80" preserveAspectRatio="xMidYMid meet" fill="white">
    <!--! Font Awesome Pro 6.4.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license (Commercial License) Copyright 2023 Fonticons, Inc. -->
    <path
      d="M416 32H31.9C14.3 32 0 46.5 0 64.3v383.4C0 465.5 14.3 480 31.9 480H416c17.6 0 32-14.5 32-32.3V64.3c0-17.8-14.4-32.3-32-32.3zM135.4 416H69V202.2h66.5V416zm-33.2-243c-21.3 0-38.5-17.3-38.5-38.5S80.9 96 102.2 96c21.2 0 38.5 17.3 38.5 38.5 0 21.3-17.2 38.5-38.5 38.5zm282.1 243h-66.4V312c0-24.8-.5-56.7-34.5-56.7-34.6 0-39.9 27-39.9 54.9V416h-66.4V202.2h63.7v29.2h.9c8.9-16.8 30.6-34.5 62.9-34.5 67.2 0 79.7 44.3 79.7 101.9V416z" />
  </svg>
</a>
---
<a href="https://twitter.com/waalge">
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" height="80" preserveAspectRatio="xMidYMid meet" fill="white">
    <!--! Font Awesome Pro 6.4.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license (Commercial License) Copyright 2023 Fonticons, Inc. -->
    <path
      d="M459.37 151.716c.325 4.548.325 9.097.325 13.645 0 138.72-105.583 298.558-298.558 298.558-59.452 0-114.68-17.219-161.137-47.106 8.447.974 16.568 1.299 25.34 1.299 49.055 0 94.213-16.568 130.274-44.832-46.132-.975-84.792-31.188-98.112-72.772 6.498.974 12.995 1.624 19.818 1.624 9.421 0 18.843-1.3 27.614-3.573-48.081-9.747-84.143-51.98-84.143-102.985v-1.299c13.969 7.797 30.214 12.67 47.431 13.319-28.264-18.843-46.781-51.005-46.781-87.391 0-19.492 5.197-37.36 14.294-52.954 51.655 63.675 129.3 105.258 216.365 109.807-1.624-7.797-2.599-15.918-2.599-24.04 0-57.828 46.782-104.934 104.934-104.934 30.213 0 57.502 12.67 76.67 33.137 23.715-4.548 46.456-13.32 66.599-25.34-7.798 24.366-24.366 44.833-46.132 57.827 21.117-2.273 41.584-8.122 60.426-16.243-14.292 20.791-32.161 39.308-52.628 54.253z" />
  </svg>
</a>

## Thank you 🙏


Any questions? Please get in touch

