134 lines
6.5 KiB
Markdown
134 lines
6.5 KiB
Markdown
---
|
|
title: Are we zk-Cardano yet?
|
|
date: 2023-08-07
|
|
---
|
|
|
|
Not so long ago Emurgo announced they were doing a Cardano centered hackathon.
|
|
It was a welcome prospect - very few similar such events seem to exist in the
|
|
space. Things went monotonically south ever since the announcement, but that's a
|
|
different story.
|
|
|
|
One particularly interesting quirk was that of the three "tracks" of the
|
|
hackathon, one was _Zero Knowledge_ (aka zk). Why particularly interesting
|
|
quirk? In some sense it is not surprising: zk has been very trendy these last
|
|
few years around blockchains. However, building on Cardano is notoriously
|
|
challenging. Building with zk on a zk-native blockchain is itself a very steep
|
|
learning curve. So combining the two, zk on Cardano seemed... a bit mad.
|
|
|
|
This post is borne out of a best effort of how far "zk on Cardano" can be
|
|
pushed.
|
|
|
|
## What is zk?
|
|
|
|
There is no shortage of explanations describing what zk is ( _eg_
|
|
[by Vitalik](https://vitalik.ca/general/2021/01/26/snarks.html){target="\_blank"}
|
|
or [a full mooc](https://zk-learning.org/){target="\_blank"} ). There is also a
|
|
reasonable breath to the field of zk that includes things like distributed
|
|
compute. Zk involves some really neat maths that lets you do some seemingly
|
|
magical feats and pairs well with blockchain in extending what is functionally
|
|
possible. Let's stick to a simple and prototypical example.
|
|
|
|
Suppose Alice and Bob are playing battleships. The game begins with Alice and
|
|
Bob placing their ships within their own coordinate grid. They then take turns
|
|
picking coordinates to "strike". If they hit nothing then their turn ends, but
|
|
if they hit a ship then they strike again. The winner is the first to strike all
|
|
coordinates containing their opponent's ships.
|
|
|
|
Alice knows Bob as being a notorious liar; how can she enjoy the game?
|
|
Each guess she makes, Bob gleefully shouts "Miss!". She can't ask Bob to show
|
|
he's not lying by revealing the actual locations of the ships. She could ask
|
|
Charlie to independently verify Bob's not lying, but then what if Charlie is
|
|
actually on team Bob and also lies. Or Bob might suspect Charlie is actually on
|
|
team Alice, slyly brought in to give Alice some hints.
|
|
|
|
Is there a way that Bob can prove to Alice that each guess is a miss, but
|
|
without revealing the locations of the ships either to Alice or anyone else?
|
|
|
|
The answer is yes. Using zk Bob can produce a proof each time Alice's guess
|
|
misses if and only if it honestly does. Alice can inspect each proof and verify
|
|
Bob's response. Alice can interrogate the proof as much as she wants, but she
|
|
won't learn anything more than her guess was a miss.
|
|
|
|
There are a multitude of different ways to do this, but essentially it involves
|
|
modeling the problem as a bunch of algebra over finite fields - like a lot of
|
|
cryptography.
|
|
|
|
What's the _snark_ of zk-snark? Snark stands for _Succinct Non-Interactive
|
|
Argument of Knowledge_. And without saying anything more, it means that Alice
|
|
has to do way less algebra than Bob. In applications this is important because
|
|
Bob might not be able to lie anymore but he could still waste Alice's time.
|
|
|
|
## Sudoku snark
|
|
|
|
Sudoku snark was the entrant to Emurgo's hackathon. The summary-pitch-story deck
|
|
is [here](https://pub.kompact.io/sudoku-snark){target="\_blank"}. Links to the
|
|
associated repos:
|
|
[plutus-zk](https://github.com/waalge/plutus-zk){target="\_blank"} and
|
|
[sudoku-snark](https://github.com/waalge/sudoku-snark){target="\_blank"}.
|
|
|
|
Just after the hackathon got underway there was a
|
|
[large PR merged](https://github.com/input-output-hk/plutus/pull/5231){target="\_blank"}
|
|
into the main branch of plutus. It's a mammoth culmination of many many months
|
|
of work. In it were some fundamental primitives needed for running zk
|
|
algorithms.
|
|
|
|
The idea of the project was as follows:
|
|
|
|
- write a validator implementing a zk algorithm with the new primitives
|
|
- write a program to generate the setup and proofs
|
|
- try to get a version of hydra running this newest version of plutus
|
|
- wrap up in a gui
|
|
|
|
Unsurprisingly to anyone who's hung around the Cardano ecosystem long enough,
|
|
this third part is where things got stuck. We did get as far as running a
|
|
cluster of nodes in the Conway era with the latest version of plutus but
|
|
unrelated changes seemed to thwart any chance of building transactions here.
|
|
|
|
A quick shout-out to the [modulo-p.io](https://modulo-p.io/){target="\_blank"}
|
|
team. They had a different approach and managed to implement a zk algorithm with
|
|
the existing plutus primitives. This spared the need to play the foolhardy
|
|
dependency bumping game with the Cardano node. However, because zk is so
|
|
arithmetically intense, the app wont run outside a hydra head and with very
|
|
generous max unit budgets (afaics). This approach won't be necessary when we
|
|
have the new version of plutus available. Nonetheless, it's very neat to see it
|
|
done and they packaged it very nicely.
|
|
|
|
The validator in Sudoku snark uses
|
|
[groth16](https://eprint.iacr.org/2016/260.pdf). In part because this was
|
|
already mostly available from the plutus repo itself. It is also the most
|
|
obvious candidate to begin with. It's relatively mature, relatively simple, can
|
|
be implemented from the new primitives, and importantly in Cardano land has
|
|
small proof size. (As far as I know, the smallest of comparable algorithms.)
|
|
|
|
The program to generate the setup and proofs uses the Arkworks framework. Again
|
|
this choice was initially inspired by a script from the IOG team, but again it
|
|
seems like a smart choice. Arkworks is a well conceived, highly modular
|
|
framework for zk, which makes it easy to pull in the bits we need to perform our
|
|
off-chain logic.
|
|
|
|
The choice of game, sudoku, was in turn inspired by an arkworks example. It's
|
|
not the most compelling of choices, but it's simple and it did for now.
|
|
Battleships would have been more compelling or mastermind as the modulo-p team
|
|
used.
|
|
|
|
The intended game play involved locking Ada at a utxo correspondinig to a sudoku
|
|
puzzle, and spendable only if a player could provide proof they knew the
|
|
solution. Through the magic of zk they'd not disclose to the other competitors
|
|
the solution itself. Other details were TBC: is it first and second prizes? are
|
|
players whitelisted? _etc_.
|
|
|
|
## So are we zk-Cardano yet?
|
|
|
|
We're close.
|
|
|
|
There is potentially still quite a while before these new primitives in plutus
|
|
reach mainnet. The word on the street is that it might happen before the end
|
|
of 2023.
|
|
|
|
Even sooner, there will be versions of the Cardano node available with the new
|
|
primitives, and so possibly plumb-able into hydra without causing oneself an
|
|
aneurysm.
|
|
|
|
In development time that's not so long: we can start thinking about what to
|
|
build with zk on Cardano.
|