Are we zk-Cardano yet?

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 or a full mooc ). 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. Links to the associated repos: plutus-zk and sudoku-snark.

Just after the hackathon got underway there was a large PR merged 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 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. 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.