ep2 On proving systems - What ZKP builders need to know

September 25th, 2023

Intro

How non-interactive zk proof used in blockchain app

Changes to proving systems and the main popular ones

What are the challenges in terms of the proving and verifying process

Final notes and related resources

01:16 Dr.Cathie's background

02:37 A brief intro to NOVA

05:50 How interactive zk proof works

08:35 Non-interactive zk proof in blockchain app

10:03 A high-level overview of how mathematics is being used in the proving and verifying process

12:28 What does it mean to decentralize provers

14:45 Changes to proving systems and the main popular ones

18:57 Comparisons between groth16 and plonkish system

21:42 The trend is to abstract proving schemes away from languages

23:52 What are the challenges in terms of the proving and verifying process

30:02 How nova can help tackle some of these challenges

32:38 Other advancements in proving schemes - the novaish side and the plonkish side

34:30 We need not to understand the moon math behind untill we start to build our zk app

42:17 How proof recursion applied to ZK machine learning

In the past few months,a rising star called NOVA, kind of got everyone's attention, especially those cryptographers and builders working on zk projects. Nova is an advancement in proving systems. NOVA is actually what we call a folding scheme. Essentially it folds the same computation or operation over and over repeatedly, and it folds it into a proof size of o(1). Assume that we do 10 times, 100 times, 1000 times of the same thing, the outcome is gonna be around the same size. Proving system is core at the entire ZKP field and every builder who wants to implement applications with zkp needs to understand. In this episode, we have Dr.Cathie to explain these complicated things to a more general public, hoping to inspire more builders who have been discouraged by moon math.

Dr.Cathie is a zero knowledge machine learning researcher from the Privacy and Scaling Explorations Team under Ethereum Foundation. She used to focus on the fields of data science and machine learning engineer, until she got into zk because of an educational program ZK University, which is an open-source course made by her. And for her personal project, she is doing research of how to get machine learning into zk.

**host：Franci @FrancixDeng**

**guest: Dr.Cathie @drCathieSo_eth**

In blockchain applications usually we are doing what's called a non-interactive zkp, whereas the proof generation and verifying process only happened once. At a high-level, you have a prover that generates some mathematical statement, and then you have a verifier that verifies this mathematical statement. And the verifier, when we're talking about a blockchain application, is usually a smart contract.

We put it in a way of answering a mathematical question. The verifier can verify the answer to a mathematical question, and the prover is literally the only person or the only machine in this world that can answer this question, only with the correct inputs. That's why it's called proof. Only the prover has the capability of generating this correct answer that will make the verifier say that, oh, this answer is true.

But behind that super high-level description, there's a lot of different mathematics that goes in. That's why we will hear about different proving scheme or different proving system. But in essence, all these mathematics is just trying to guarantee that it's very hard to guess this correct answer to verify. All these mathematics is just trying to guarantee that only the prover with the correct input is able to generate something that the verifier will accept.

A proving system or proving scheme it's like what type of mathematics is used to generate the proof.

Generally, we start from groth16 which is based on some mathematics called elliptic curves, and it's a proving system that is based on a constraint system called R1CS. And it's largely associated with the language circom, where we can only write what's called a arithmetic circuit. That means all you can do in this program is plus and multiply.

Then we moved on to something that is a little bit more flexible, now is largely called Plonkish systems where it works on custom gates. Custom gates means that now we have more than just plus and multiply, and that we can basically self define some operations.

And then we also move on to something that is unique to Plonkish system called lookup. So lookup is basically saying that, if we can't do certain operation in ZK, why don't we just write up all the possible outputs? So we have this big table where we write down all the possible inputs and all the possible outputs. That also brings a lot of flexibility, and these are currently the more popular proving systems. And so you can see why maybe a lot of people have moved from like groth16 into Plonkish because of the flexibility.

But then with Nova, it also kind of moves everyone back to the R1CS systems because Nova doesn't work on Plonkish system.

So different proving system, basically they rely on different mathematics, they support different operations. And there are different limitations to it.

Previously, usually the language it's tied to the proving system. They used to be a pair, which means by choosing the language, you choose also the proving system. But it's being more and more abstracted away. So hopefully in the near future, developers would just be able to write the program, like write it in one of the ZK language, and then maybe choose the proving system later.

It's almost always a trade off between proving costs and verifying costs. Hence proving is off chain and verifying is typically on chain. So at least for now, because we're talking about blockchain, usually we try to make the verifying side as cheap as possible. And that the trade-off means that usually the proving will become very expensive, which means it takes a lot of time or a lot of memory. Besides hardware acceleration, there’s other ways we can improve proving cost from the software side, which may depend on the backends, namely the proving systems that also affect the proving time.

On the verifying side, its cost has a lot of different dimensions. But nova actually has help with the verifying side. So with Nova is basically like if we're trying to prove the same thing over and over again, now the verification costs will actually be the same or about the same as if we're just trying to prove it once. So that means that we're saving a lot of costs if we're trying to verify the proof.

But nova can still have a specific application to ZK machine learning. Firstly, ZKML is basically trying to put machine learning model into its ZK counterpart. Machine learning has a lot of repeated and very structured operations. For example, if we have a convolutional neural network, which is just applying matrix multiplication over and over again, these matrix multiplications are the same operation. So if you want to do all of them in a full program separately, of course it will be very expensive. But if we can do proof recursion over them, then essentially what we can do is apply nova or apply any other proof recursion technique.

**We need not to completely understand the moon math behind untill we start to build our zk app!**

At the end of the conversation with Dr.Cathie, we had a casual talk about ZK developers or ZK builders onboarding. As a branch of cryptography, zero knowledge has seen as moon math by so many blockchain builders, and somehow the moon math fear becomes the obstacle for a lot of builders who are interested in applied zkp. While Dr.Cathie gave some very sincere advices and her own experiences on getting started building zkp projects from scratch. It’s really instructive for beginners who are fascinated about applied zkp. And also I strongly recommend you to check out the open-source zkp course made by Dr.Cathie!

**Zero-Knowledge University**

ZKML PoC

What is ZKML and how can Devs get involved

Nova ML

Proof Recursion in ZKML

Wen Building aims to engage in in-depth conversations with Web3 builders. It explores the cutting-edge technological developments in Web3, analyzes the mechanics of blockchain products, and observes industry trends and challenges.

Homepage:https://labs.antalpha.com/podcast/

Notion: https://www.notion.so/antalpha/Wen-Building-Homepage-e052297983e944f8a80f9e00f1871093

Youtube: https://www.youtube.com/@Antalpha_Labs/podcasts

Contacts：

Donation!

ETH Address: 0x18226b84677a7a59D0A498d428feE9208105D0F7

Subscribe to Antalpha HackerHouse Media

Receive the latest updates directly to your inbox.

Mint this entry as an NFT to add it to your collection.

Verification

This entry has been permanently stored onchain and signed by its creator.

Arweave Transaction

vfLwaxAxs_TT3u7…zZIlHg3a_vcMM7Q

Author Address

0x0c0fa52Fe5dD13e…3EB96F84F3a2628

Content Digest

N3BKvnlaYVEHpER…PuD44a9xi5bHqkE