ZK9: Exploring client-side zero-knowledge proofs - Dan Tehrani (Personae Labs)

Transcript

foreign [Music] pleasure to introduce Dan tirani and he will give us an introduction to client-side zero knowledge proofs take it away um hello hello everyone uh who here owns a world coin ID World Corner the world ID from old coin I guess no one or no many one person one person maybe and who here owns an ethereum address yeah basically everyone I guess um so in our research we want to enable journalist proofs to all of you who own an ethereum address

um rather than didn't approach uh taken by something like worldcoin where they create a new identity stack that is Journal friendly um but we we think that there is a lot of things that we can do about with the on-chained state with existing ecdsa uh special AC DSA Keepers and enabling um uh generating their knowledge proofs with existing Keepers I could have many applications and in this stock I'm going to talk about the status of the research for enabling General entrepreneurs for existing identities mainly ethereum accounts uh okay so I'll start with the motivation and talk about these Solutions we have built so far and then

about things we're working on uh and then uh talk about album questions um so first what do we even mean by client-side ZK and what's the motivation uh there um as I said uh there are several paradigms when it comes to using Journal knowledge proofs um not for scaling but scaling blockchains um but for actually doing Journal stuff and one is using um snark friendly keys for example a baby shop job Keepers which I think is done with many um zika applications and having and having a dedicated identity stack for that and another is using keys that exists in crypto walls like uh you see they say ecdsa Keepers in ethereum and

the goal is to do this simple thing a user makes these their knowledge proofs about the adrenology proof pipe that says something about the answer in state and most of it's on the proof consists of something like a membership proof which obscures the identity of the user while preserving the correct credibility of that user uh so in short uh what what we are aiming for is a credible Nuance uh which is a credible Nuance from blockchain State uh for example on some applications um example applications are like here now which you can give feedback to their proposals without revealing your

ethereum address so you only need to prove that you own in particular uh nft and uh another interesting example potential application is a relation discounted quadratic funding which is um which which is like one really specific example of using Studio launch proofs but I believe it's um it's an interesting um application to explore in close writing funding um you in a variant of graduating funding which uses pairwise matching you want to prove that um you you have like this relation with other voters or other funders but you don't want to reveal your identity you don't want you want to

um fund or votes to a proposal or to a funds anonymously so you can generate a membership or or like a proof that the pairwise coefficients were calculated correctly so uh in in our research I will aim for we aim to enable these kind of applications um and yeah next I'm going to talk about uh um what kind of what kind of their knowledge groups we need to enable those kind of applications um so what we aim for is is a proving system that has a really small public parameter in other words The Proven Keys should be pretty small and um fast moving obviously and reasonable reasonable communication and uh at the

very very far complexity could be it doesn't have to be like oh an oral login because um we we don't we don't aim to directly post these proofs launching we could um compress that with like really stronger approver later on so on the verifier complexity could be on or sub-linear but um it's yeah and let's see and like really broadly um there are two kinds of journalize proofs that have applications in client signs AK one is a bespoke solution like uh that which uses Primitives like ring signatures for membership proving which

is for example what zekia test does and another is just all um other Moving Systems that we talk about every day I've got 16 flunk um MP complete improving system that can encode any state any NP statements and in this talk uh yeah we'll focus on the we'll focus on with working with the MP complete ones because for some applications um like really high expressiveness including approving the knowledge of a pre-mesh of a hash function is required which is not possible with bespoke solution like ring signatures or um the other other Primitives and we also want a field flexibility which

um uh which like in zero launch proving systems we often need to do wrong fuel automatic when we are working on curves like the n254 or BLS three three uh BLS and but in existing systems there these kind of curves are used it's like B um segment if it's a K1 or SEC BT physics R1 and we want to encode um operation in these fields natively so we wanted to write field arithmetic um using these curves and so that was the that was like the requirements that we want and what kind of ZK proving systems that we were aiming for so uh what do we have now what kind of solutions we have now

uh Sport and easy to say is a scheme that we've been working on for approving membership in an ecdsa public key ecd is a public key group and it makes significant improvements improving time compared to solutions that came before it and Sport and easy to say encodes statements in r1cs over the scalar over the scalar field of the SEC Q 2560 K1 curve which is a curve that forms a cycle with the Zac B curve um so you can encode secp based field operations natively without doing any wrong field arithmetic and the circuit for proving validity of a of an ecdsa signature and including

that that is included in the depth to any a binary numerical tree results in about a thousand r1cs constraints with some now this 8 000 r1cs constraints is is a result of another like ecdc optimization which I won't talk about talk about in detail here but um with this premium system a proof can be generated in about four seconds so this specific circuit um specific like a predicate you can generate a proof in about four seconds in browser which is a significant Improvement compared to doing wrong field arithmetic I think uh yes some of some of you know that generating an ecdc uh proof will like take like 10 minutes or impossible in a

browser if you do wrong field or like with girl 16 or something so now we have this scheme that you can generate a proof in a reasonable time and but um this uh this specific um circuit with a thousand dollars of constraints doesn't include the ketchak hashing of the ethereum public key which we think is okay um because public keys can be extracted from past transactions so we can create a group of ethereum public Keys instead of creating group of ethereum addresses I'll buy simply extracting public keys from the transaction history of the addresses we're interested in so we don't include we don't do the kijak in

our circuit because Jack is just brutal for browser proving and um so we have this like basic proving time improvements and so what what kind of things are missing to enable more applications to flourish now they're actually uh a bunch of things that are missing um this is likely not all of it but um for this stock I will focus on uh onto your verification and recursion which are which I hear the most uh demand for first I want to mention that recursion is not only for scaling proving system um but it's it could be a primitive that

could play a role as a pretty high level building block for a certain set of abilities for example um ethos is an application that lets you prove your degree of separation from vitalik and it uses recursion to pass on proofs so you can build the proof that you're you're this degree separate from this person by by proving the validity of the previous proof and also proving that you own a signature that uh that is signed by that person who passed universe um and so going back to onto your verification for Spartan ecdsa uh the proofs are pretty large so directly posting them to like change like ethereum is likely not

an option we have uh this phenomenon of proofs being large in um first being large in client-side ZK is Pretty Natural because a considering that we we don't want to let the users compress we don't want to make the users compress improves we only want to let them blind the awareness and then just let the compression down by like other remote servers so the proofs being large are pretty natural and we we do think that even if we come up with something um other than Sport and easy to say the burst will be pretty large so the general Paradigm for um verifying proofs online for clients and ecds across like client-side CK will probably

going to look like this um where the proofs are largely generally proofs generated by the users are pretty large and in order to post them on chain we must we want a stronger proverb that compresses the proof and then pass that to the weak River like if there are more any like blockchain and to get more scale we want the strong privilege to work as an aggregator that Aggregates using techniques like recursion to compress multiple proofs into a small curve so how can we actually do this recursion um first recalling that we want this the system to work with alternate fields and

that we're actually doing their knowledge so we're operating under different set of assumptions compared to um systems like tkbms um several systems construct aggregation schemes for example Nova superinova um Halo 2 there are multiple ways to multiple strategies due to recursion and um currently we're working on the payload to verifier of a Spartan proof so basically compressing is Spartan ecdsa proof with Halo 2 which uses a variant of a Halo 2 that uses kgz as a backend so we can post the purpose on chain and we should get that on benchmarks pretty soon

and um given these recursion strategies we believe there are these two um pyramids Primitives that might be important when um when building a recursion abbreviation strategy for client-side DK one is ecfft and another is the folding scheme first ecfd or elliptic curve fast Fury a Fourier transform is an algorithm for doing ffts in all here all fields um to briefly go through the algorithm uh let's uh fbbd field we want to work on uh maybe this could be the second

base field for ecdsa and um we find first we find an elliptic curve in that field with an order for of some Power of Two and we use a degree to exogeny uh to map elements in that elliptic curve we find into another replica curve with the half the size and this degree 2 isogony can be substituted for this squaring operation in the fft algorithm so this allows us to do fft in all of an appeals and um many yeah as I think many of you know they're most of the probing systems require fft so having this ecf50 algorithm uh we could modify Planck or

any other proving system that use fft to work with all finite fields which is which is really really powerful yes and it works for fry as well which is kind of which uses a DC ffd a little different from it is used in fft but fry is fries and Fry House is like an analogy to fft uh which like Falls the operation um every time in half and you can do similar techniques using as ecf50 to make fry work with elephant appeals So in theory we can do fry and sakapi which could be really really powerful considering that we might be able to do uh well we could do a start over 60 or

something but I see fft as as far as I know um there are no any deployments and the concrete performance is still yet unknown so even though this scheme is actually pretty simple um some some yeah additional work is required to get this reproduction and get the benchmarks another primitive that could be interesting and important recursion for client size DK is the folding scheme um to go through it briefly as well the folding scheme um specifically the one used in Nova works as follows first uh to set the notations a classic r1cs instance consists of three matrices a b

and c um and in the witness W public input X and uh and concat concatenating them we have the vector Z and yeah and this and the ABC matrices should satisfied with W should satisfy the relation anti-nova we fold two relaxed r1cs instances which is the variant of r1cs that is defined in the Nova paper uh by um introducing a bunch of variables but the core idea is to take the random eliminary combination of two Z vectors and fit that into the r1cs equation so um even though we have two instances we

can check them as we're checking only one and that's the basic of the folding scheme uh describing Nova and the proofer or um aggregator in our context snarkifies the equation in brown and in post this snark on chain so we still need to aggregate we still need to snorkify this equation and um we still need to let the uh let the aggregator know what the when s Witnesses are in in this specific specific example what W1 and W2 are in order for the for the aggregator to actually create the final snark

um but in our context we want to hide W1 and W2 from the aggregator because the aggregator is the powerful prover that that um sits in middle of the user and the chain so we cannot directly use um Nova like folding scheme for client-side CK um so the but the ideal flow um just to define the model is uh yeah it's basically like this so weak River or weak river is the users and all every users submit their Witnesses wi blinded when it says wi CD strong River and the stronger basically pulls those Witnesses and then produce the final

small small proof pie that can be verified on chain this is the ideal flow but um we still don't know if we can make this uh we if we can make this an efficient system so um we still don't know if we can introduce this like blinded when this uh while preserving the efficiency of Nova um but yeah it's definitely it's definitely an important direction to explore and um we have some ideas but uh they're not ready yet and they're not definitely concrete so um I will well yeah I will not talk about it in this talk um so to conclude we have some basic

proving some improvements that let us build um some of the locations enabling credible new ones but their large set of applications that we can't build because we don't have uh nullifiers which I didn't talk about in the southwest it's also an important primitive in client-side DK and if you have questions about it uh definitely um I can answer and then if you have any thoughts on it uh I would like to talk to you with it um about it and there are also a lot of unknown unknowns answer verification we still don't know what kind of strategy is best as they talk about one could be yeah for Iowa the cf50s or a folding scheme like Nova but modified to preserve uh to your knowledge

and also recursion could also be it might be the case that in some kind of um use cases of recursion for example like an ethos which is which uses recursion for as a really high level building block we might want to use one particular recursion strategy but for online verification we want to use another strategy for equation so there might be this like um different um like different trade trade-off space in the in designing recursion as well so that's another interesting topic to look into and finally um even though we have like we we have our ethereum addresses as we have our public

Keys uh we don't know like what we don't know what the identity stack will look like in the future especially after things like account abstraction um gets adoption um so yeah as always a lot of problems to solve and yeah fun and exciting work ahead of us I guess and yeah that is all thanks for listening excellent any questions yeah can you hand the mic over because I can't walk through yeah uh I Wanna Know Why the wig Hoover

cannot just aggregate the proof in the blockchain like um so let's see let me just show you this slide again um so I think you're talking about this right um so the reason we the reason why we can't aggregate the proof of the weak River cannot aggregate it can but it will require a lot of proving time because in order to pass it on chain we want the proof to be small so either like constant size or um logarithmic size but in order to let the proverb generate proofs efficiently we have to we can't we can't make the approver um we can't require the weak River to do the compression work

um so in order to post it on team we need to have this intermediate shrunk River so it's more about the gas concern yes yes it is yeah uh what's your intuition for how like where finality will be from the perspective of the the end user like the browser the week proofer will they think that it's done and like is it good enough for most use cases that they send it to the strong prover or is it going to be one's a strong proverb does fold those proofs and put puts it on chain finality you mean like on L1 like in a

use case where you're doing this um for I guess for hey announce you know the timeline doesn't matter so much but then when you get into use cases that are more and more latency sensitive um do you think that the the trust involved and the strong proofer is going to basically uh prevent some use cases or will that be efficient enough to yeah um that's a good question we still didn't know and yeah I think it's pretty um yeah it's I think when yeah I think the time that we face that problem will be pretty ahead of us um but yeah certain type of applications won't be possible due to GTA latency but we believe many ziki VMS and ZK Roll-Ups will use recursion strategies so I think

that um sequencer it's like a simple L2 sequencers will have similar latency problems um so I don't think this is like this is a specific issue for um aggregating their knowledge base but just like having in sequencer or an aggregator or like a regressive approver I think yeah most of applications will have similar issues um in terms of like you've got uh the aggregated which I assume is like posting information on chain right um in terms of the kind of gas costs does that leave you exposed as Persona labs to fluctuations in gas or are you covering that somehow oh

definitely we'll have issues with gas costs but one thing to note is that we don't need to post our proofs on L1 because we're not doing like roll up stuff uh we're not Roll-Ups we're just um trying to yeah in order to interact with other like smart contracts or for example any blockchain it could be a female one but it could be a ml2's Optimum is an arboretum those kind of stuff in order to interact with that we want to post it on chain so it could it could be the case that for many use cases that use general knowledge proofs clients as journalist groups will have their smart contracts on like l2s like optimism or even like ball DMS that has volume that have really cheap gas cost so um yeah definitely we will be

affected by gas costs but um there are many like chains uh chains that we can post stem to and yeah it will depend on machine I guess I wanted to ask you something related to the Brewer keys I that you are mentioning that it's an issue there was a similar thing in a ZK Bridges application the succinct labs they built something where they did not use the public key itself but it was the hash of the public key and do you see any scenario where you could actually you don't really actually have to download the public key but perhaps it needs some properties the hash must be additively homomorphic or something like that so in order for it to work

um so we need to so the public key uh here most of the time it will be simply the circuit itself so we want the user to [Music] um yeah most of so the proofing system like that encode statements and almost yes we need the user to download the actual l1cs to generate the awareness and then yeah so most of most of the time the improving key will be just this circuit so it's huge um yeah it could be huge but for example in sport and easy they say it's like five megabytes or so because it's only 8 000 constraints or so yes exactly if we go to like 100 000 constraints or something it's still I

guess like several like I don't know 10 like 30 40 megabytes or something it's not impossible to download but if yeah we we kind of have to expect users to have good bandwidth internet and yeah the download download time could be pretty long so any large circuit itself so yeah I don't know maybe you mentioned Nova and so on so as if there was anything yeah maybe Nova could be one like using folding scheme too exactly yeah yeah if there's like a duplicate uh duplicate circuit come straight into it you might be able to do

but I'm kind of folding yeah uh so for the for the aggregator it says centralized or decentralized and what will happen if uh it is um the aggregator so yeah this is really really clear without theoretic at this point so we still don't know um uh if it's if if applications will require a decentralized aggregator or a centralized one could be sufficient and um there are some like other methods to post think on posting things on chain and we could play around with the trust assumption um with like other uh like weather with other designs or something but

eventually yes decentralized aggregation could make sense but yeah we're still early and that we still don't we still don't have like this uh working yet so yeah it is a question about it um it's going to be yeah pretty far in the future I guess thank you thanks so thank you um it's like a mix of a question of a comment you mentioned nullifiers and I suspect that there are a number of projects in this area which need these nullifiers um and don't you think it would be an idea then to sort of come together and create a kind of ZK registry on chain that many projects would use at the same time where people could just post some

Randomness or public keys or whatever they need to post um yeah um yeah I agreed at a lot of applications will require nullifiers and I think that's I think the registry idea is pioneered by the algebra Solutions like semaphore which probably are using um DK friendly basically they can friendly um curves but in our case we want to so in our case we just don't want to have that kind of register registry but we could have it but it introduces like this anonymity set of complexity and like users also have to manage their um ZK adminton um like halfway wallet just for that so

it could that could eventually be like the um industry standard we still don't know but we're just um trying we're just exploring this approach of using existing keys and um uh and enabling adjective improving and using existing keys and using nullifiers we need to so for example in ecdc nullifiers we need uh existing wallets to adopt this new uh signing scheme which um which you can which basically uh that which only lets you generate a single signature for a particular message or you can generate like two different but uh if you DK preview that you cannot prove that the signature is

unique so we have to um we have this proposal to proposals like it's basically an EIP for wallets implementers to implement this particular signature scheme that allows uh notifiers for cdsa but we don't know if wallets will actually adopt that or if like that's the proper way to go forward so um but yeah it is a really really um important primitive and um yeah without nullifiers many applicants can be developed and then also in general you don't necessarily need signatures from one scheme it's enough to have just some randomness that the user can can regenerate and then that Randomness can be used for many schemes

so it can actually simplify things okay that's another discussion thank you yeah in a blog post You released a while ago you tried to optimize the proof Generation by pre-calculating the results of some possible scalar multiplication yes yeah and I saw that uh it's 65 or so in numbers I was wondering if that would reduce the entropy for it to become too vulnerable what's up I don't think so we're just pre-computing the variables and you use it as a public input yes the circuit right yeah and that would give some

Clues to some adversaries uh we include all of the uh pre-computes so so that we include all of the pre-compasses and we don't know which pure computes are used in the circuit so it doesn't reduce any like journality but given the number of pre-computes like given the number of the results of the scalar multiplication maybe the adversary could run you know some possible permutations you mean like a side Channel attacks or no um maybe I can uh ask later yeah we can disguise later all right I would say let's wrap it up and head over to lunch if you have more questions for them find him on the lunch

break thanks everyone