ZK11: Pretty Optimal: Integrating Application-Specific Circuits and zkVMs - Victor Graf

Transcript

[Music] yeah so I'm I'm Victor I work for for R Zer I work on the platform the cryptography and also some some web 3 integration work and my talk I talk is titled pretty optimal integrating ZK circuits and and ZK BMS and circuits and I'll explain why it's called that in a second so one thing I want to start with just raat is a kind of some context setting which is that we are living in a world where ZK VMS are practical for a wide range of applications today so right now for c for instance and there are others as well uh basically there you can you can compute about 1 million risk five Cycles in 5 seconds on a GPU or about 14 seconds on a Mac M2 Pro uh 1

million Cycles is plenty of time to do things like Json parsing signature verification chess chess board check checkmate validation there's a lot lot of things you can do in million cycles and we also support continuations to go to billions tens of billions even 50 billion cycles or more that's the largest we've done so far but there's no thing that stopping us from further one thing I want to call out in particular as well is people think that work cursion is expensive and it's not exactly cheap but it's much more less expensive than you might think right now we can do a two to one recursion verify two proofs produce one proof in about one to two seconds on a GPU and 3 to four seconds on on a Mac M2 Pro so when you think about recursion don't think it's it's actually not as expensive as

you might think uh also programmability B you can actually compile programs US Standard tool chains you know Clay uh and and uh rusts rust C and actually run those boundaries in dkbm uh and I want I do want to mention the limitations which is that so risk five instruction set is not the most efficient representation for cryptography operations so things like ecdsa verification things like pairings Etc do take a significant amount of Cycles however often not as not as many as you might think oh and one one other thing as well improving on mobile phones and browsers is possible it's not a seamless ux we'll talk about more more later so one of the question with that context set I want to

ask is when should we write circuits and when should we write programs by programs I mean programs that run in a zkm so programs are generally more efficient with your engineering time it's faster to implement them like which is significant cost savings and you know if you're a startup trying startup or protocol or really anybody trying to get your application out to the market this this matters a lot it's simple for human review this includes Security review meaning less bugs there's often less code involved because you have maintain libraries that are maintained by other teams and that that results in in lower maintenance costs and also again less bugs which is incredibly important and we talking about SEC soundness of zero knowledge proofs circuits really maximize that computational efficiency so if you're

trying to really crank it and like get maximum through port or minimum latency circuits are are are basically the best environment for that in many cases uh there are basically in particular there's kind of between between through throughput and latency where Bas say latency I mean by that I mean like the minimum time to produce a proof end to end and by throughput I mean how can you how like how big of a proof can you do you're trying to proove an entire blockchain that's throughput if you're trying to like do a 200 millisecond proof on a mobile phone that's latency in my mind when when I refer those terms and what one thing I want to be very clear about here and this is why I called pretty optimal is that opone really needs to concern more than just performance it's not just about how fast

can the program run it's about how how easy is it to write how easy is it to maintain uh are what are there any security bugs basically there uh what's the user experience what the developer experience like these are all very important things when you're talking about actually shipping an application that's going to produce real value for real people now I'm a software engineer first and foremost and so I have three examples of of of applications that kind of explore the different trade-off space uh among integrating circuits and zkm and I'll kind of explain where the the kind of the boundaries lie in the space of tradeoffs um and then finally after that as a four as a in a fourth section we're going to talk about how you actually Implement integration uh using both

circuits and ZK VMS in the same application so the first one I want to talk about is parsing HTML and PDFs in a in a uh zeron knowledge context so this comes into play when we think about uh proofs of TLS data exchange and other kind of May similar things uh this is a a really powerful use case for identity for bridging L2 uh web through data into the ZK VM I mean into the uh blockchain World more generally and projects like TLS notary Deco ZK pass po they all provide interactive proofs of uh TLS data exchange to to a public key and also the notary trust I'll get back to that a second uh proofs on the contents of that data though really require you

to do act like HTML parsing uh or HTTP interpretation basically you have to actually open the TLs data which basically is a is a wrapper over TCP over a raw data stream and actually figure out what the contents are and for example like make an age check on a on a field from a driver's license website for example that involves parsing parsing HTML parsing is mostly control flow the actual logic and indexing operations are very minimal uh mostly mostly it's ifs and branches and switches and so on and so forth uh and the implementation complexity is super high there is a long long string of bugs including security relevant bugs in things like HTML parsers PDF PDF parsers signature processors x509 as asn1 these are these

are specs you do not want to implement yourself you want to use an implementation which is been battle tested and used in production for many years and this is what ZK and so in this case I I would argue that ZK VMS are clearly the right choice for this application in particular uh all these kind these two factors these two factors combined uh you're actually not going to get better performance with from a circuit because of that control flow and it would actually be an entire just an absolute nightmare to implement in a circuit so this is like a pretty clear-cut case and this is the most clearcut case we're going to get today uh programs are kind of the right choice here this is a demo of of this actually being implemented so this in this case uh uh a member of the community wome

Chen uh Implement work for L2 iterative uh the um it's a fund uh use ZK pass and risk zero simp a demo that will retrieve a us a US Internal Revenue Service document over TLS and then parse it to extract verified income data that's over a certain threshold to show that you can you are an incited investor in the US which allows you to access uh certain private Investments so if you're interested in in looking at that that's that's a live demo all right let's move on to to another case so we're talking about succinct uh onchain governance and one thing I want to make

clear at the moment I'm not talking about private this is all public governance basically where everything where every voter every vote is public so voting voting based governance is extensively used on Chain by lots of organizations voting is often prohibitively expensive that limits who can participate in voting that limits the uh overall coverage of your government system and It ultimately could impact the governance based security that you get of from your system um a lot of voting is going offchain now and offchain in ways that compromises on core security guarantees and and really does that kind of compromises on the vision of decent autonomous organizations and other onchain govern protocols so we really need sync onch we really need sync ZK verified onchain governance signature

verification is the bulk of the work here so basically EC votes are signed by ecdsa signatures seem to verify a lot of ecdsa signatures thousands be ideal maybe T thousands as these governance models grow and grow um um there's also a lot of custom logic though but see custom logic by that mean the the people actually run the organization want to have their own rules for vote vote waiting voter admission voter admission uh um and basically thresholds by which people actually a vote is actually achieved so this is kind of an interesting combination combination of concerns when with with with this combination you have uh you need performance on the ecdsa verify front but you also need the to tune things and

Implement custom logic including custom control flow on the data this mean in my opinion this is a case where actually we really need a marriage between ZK uh zkm programs and circuits so in this case you might have the a ecsa verify circuit and you might additionally have a uh the place for organizations to insert their own uh control flow logic and so this this there is a we actually risk zero we implemented a demo of synct onchain governance it's actually not as succinct as I would like it to be uh but with with a new uh view call library that we just we just released as well we're going to make it basically essentially fully succinct using a constant amount of data to uh verify an arbitrary number of votes and it does so in in a in a way

that is much cheaper and one thing one thing I actually want to call out I forgot as well is uh even without the circuits though it is still cheaper to run an ecsa verify using raw risk five instructions and a standard implementation uh than it is to do L1 computation on ethereum L1 on computation is really expensive ZK proofs are already cheaper than it even D ones all right so I'll talk about private onchain voting now this is I separate this out because it has a slightly different set of concerns so when we want to actually go beyond sickness and actually have privacy as well you need to be running on client devices uh there's really no way around this you have to ship you have to do the

Zer proof on the device where the secret data lives you can but what you can do are yeah and basically the the proof systems that are designed to run on client devices and run well with a seamless ux you know let's think you know below a second below below 500 milliseconds maybe even below 200 milliseconds M like feel to prove in less 200 milliseconds is basically exactly what you want for a really seamless ux so you click a button you don't have to any compromises uh for for your users and this is this is possible using custom circuits and so basically if you use if you have a custom circuit and a and a well tuned uh implementation for mobile devices what you can do is use a proof system is designed for

privacy um you know like zcash as Halo 2 or uh May a really nicely tuned br6 Pro um and then uh basically you you use that to Blind the data over which the vote is occurring once you have those those those proofs you basically have many you many proof gener by kind of at that point you need to make them allnc and so this is a case where I believe there have a combination of of private of custom circuits and ckvm that weits more towards the private the the the custom circuits and maybe even custom proof systems that or basically proof systems that are not ZK VM optimal um in order to make this this work work really well so this this kind of

basically as we're looking at this threshold we kind of gone from ckvm implementations to circuits and kind of even kind of a little more into the circuit including uh differ integrating tool proof systems and this is our sync governance demo as well if people are interested in this this is a blog post we're actually going to re-release this demo as well as soon uh with new and improved features all right let's move on to the third example machine learning so verified machine learning inference is is a highly anticipated use case for ZK snarks uh this is you know verified competition over public mod verified inferences over

Public public models also verified uh inferences over private committed models uh verified training is also an aspirational use case but we're not really anywhere close to doing that for Relevant models yet uh one of the main characteristics of machine learning is highly structured computation these uh machine learning models are often described in very circuit like structures using languages like tensorflow and and torch uh which describe things in terms of structured programs in terms of basically essentially circuits um and they're also highly data parallel so structured Computing highly data parallel there's no control flow uh to speak of this this is kind of one signal that we're kind of in the circuit side of things

additionally they're very computationally intensive and you need that high throughput so basically we were talking about like you have these we want bigger and bigger models as llms have shown the bigger the better um and so you really want to maximize for every single ounce of performance you get in order to actually make get a usable model that produces good inferences so in this case machine learning is mostly a circuit problem in fact you want tailored circuits and even tailored proof systems like P or easy KL um that basically really optimize for this structured competition machine learning use case um so so as we' kind of G the Spectrum this is kind of the fully circuit and tailor P outside of things

however I do think there's still a place for zkv m in this model too in particular in input pre-processing and output post processing if you have an image and you want to turn it into a format you want to take a take your webp image and turn it into a PNG or whatever format your your model actually ingests then you're going to have then a zkm will be a really good way to do that in a flexible way um additionally when you have the output you want to integrate that into into with more more application logic then a zkm will again be a good place to do that so basically this kind of so like if you look at like this the structure the big bulk of the computation is going to be in your in a tailored a tailored circuit tailored proof System model and then on either

end you might have ckvm program to help out ohing okay all right so one the one thing they clear is basically it's not a question of circuits or programs it's a circuit it's a question of circuits and programs we're going to we're going to use both uh they're both we want them both to be integrated together seamlessly um applications are going to be are going to be written in this kind of modular way in this combined way with multiple representations and this is what we see

in the real world like with uh traditional computers fpgas gpus etc Cod processors all right so now we talk about some examples let's talk about how you actually might implement this kind of this this composition between circuits and programs so the first and most kind of obvious approach is direct integration so you put you basically build you build your base Isa so rist five myips whatever you want to be evm uh and then you also add instructions for let's say Shop 2 or nonnative field multiplication or t26 ad and those basically become extra instructions that live inside of your your Isa um no extra purce are needed no I overhead it's all kind of tightly

integrated the downside to this is that basically you're adding complexity directly to your zkm and every time you add a new um instruction or a new accelerator you change the definition of the ZK VM itself and the definition of the verifier as a result so what you do is you have two effects from that one you break composition what provs using one kind of combination of instructions will not operate with with with provs who are using a different uh or really verifiers who are using one set of instructions will not under with ones who are verifiers using with different set of instructions they won't know that each other are you know using the same base Isa for instance um you also uh have this combinatorial blow up in the

number of instructions people might want so some people might want shot two and nonnative field multiplication people want Shot 2 and k26 some people want catch that can cat six basically you have this combin com combinatorial blow up in terms of the things that you might do you can support them all however if you try to support them all basically you have to have every single one of those constraint sets in your verifier definition or some other way of doing this and it just it adds complexity either to the verifier to the prover you have kind of this like you have to put this complexity somewhere between the prover the verifier or somewhere in the system and that's people always make kind of trade-offs some where to put that but you basically you end put this complexity B into the zkb itself also works only a single proof system so we

talk about these applications with tailored proof system multi prooof systems you are hard pressed to do that um and in this model I want this is kind of Hy and kind of dumb and obvious we have aover who sends a single proof to a verifier all right so uh this in in this model basically use you can use your public IO uh on your your your circuit to actually commit to your uh the public signals on like a bus or on a message passing scheme between the zkm and any co-processing circuits so in this case the zkm basically has a

view of what the what the messages sent messages received uh to and from that co-processor and the co- procor also have the exact same view and basically they both either put that transcript fully into the um public signals or they hash it first and then put in public signals this is really nice because now you get this composability property where we have the base ZK VM and you have the co- processor and the ZK the ZK VM programs can call Cod processors that are not previously registered or even known to third parties so basically between two uh two folks using the same BC dkbm verifiers can interoperate you use the same verifier code and same verifier smart contract uh to verify proofs that might actually incorporate

different combinations of code processors um what when when you actually want to when you actually want to go to prove here you'll prove all these things separately so you'll prove the co- processor you'll prove the ZK VM all separately multiple proofs then you'll use recursion like I mentioned before it's actually not that expensive to produce a single proof and send that proof to the verifier two of the things that you have to that that come up that you need that are a bit of a downside here well yeah bit downside here is one you need a commitment to the Circuit itself which some circuits for example like air air representations in particular are don't really have a well- defined uh commitment uh key at least not a a synct one um you also need to possibly

Implement a hash function on both sides so both your your your k26 ad circuit might Al need a hashing function which it might not previously need which adds a bit of comp of slowdown to the uh accelerator side of things and this is where another approach comes in as well this one has its own trade-offs though this is this idea of a shared memory argument so if you have your memory argument and you you need a special that doesn't need sorting for instance first of all but you can um you can use you can commit to both Witnesses ahead of time the zbm and the co-processor uh hash them both or basically send them both to the verifier

and receive a single challenge that is over both Witnesses at once and use that shared witness to actually run the memory argument using this you can actually have a partial transcript on each side basically have this interleaving of like read and write operations where this one's the co-processor and this one is the zkm and together they follow from a full transcript at the end of at the end of each execution you'll commit to an to an unresolved memory state where basically you actually don't know if the memory the memory argument is valid or not yet but in the presence of both when you give both receipts to the verifier possibly recursive verifier then basically they can they can then check those two commits each other for examp add adding them together and confirming that those two accumulators result in zero um and and view basically and resolve the the

individually incomplete um memory arguments this this has a trade-off of requiring reanalysis of the proof system simultaneous production of both proofs and has more which makes it more complicated to SP across multiple machines and you also be difficult to integrate across multiple proof systems but you get the same advantages as the other model before and you get a very uh cheap IO mechanism uh between the two the co-processor and the main c k so so quickly key takeaways optimizing system is more than this performance you need to consider security uh you need to consider complexity which means security as well maintainability developer experience user experience the best combination of circuits and Up Programs is going to be

application specific data dependent control flow is one thing to look for that's like ZK VM favoring usage of cryptography favors circuits uh client side proving favors circuits as well uh we have new approaches in composition between between different proof systems uh that that makes it much more attractive and tractable to actually do these kind of uh uh in circuits and uh zkm and one thing I also want to emphasize as well here is that the the right the best approach which is I think something I'm really excited about with ZK VMS is you can Implement first and then optimize your program after measuring what it does on performance time I mentioned before for example like signatures just just import a d Library run it in in RIS five run it in mips

whatever your native construction set is just run a verifier see if it works out and then check the performance don't you don't don't assume it's going to be bad or too bad at least and I thank everybody for to talk I'm Victor these are my Handles in my email yeah questions I let you I let you catch your breath uh if there are any questions please raise your hands and and someone will bring you a microphone so yeah just here okay back to you all if I get it right your your way for to make the the co-processor and the main processor communicate is through IO

so they commit to a shared sequence of events and then you check that they match mhm uh is this just a general way of doing linking or is just limited to co processors uh it's definitely more of a general it's definely a general approach I mean it's actually and it's used pretty extensively both within circuits and like between circuits like I guess the idea of going between circuits is kind of new with kind of the newest recursion schemes and folding schemes um for examp like Pro Stars a folding SCH that can do different distinct circuits but I'd say that overall the approach is fairly General and I mean shared across a lot of the engineering space not just in this space either transer passing in TLS for example is kind of a similar

idea MH anyone else don't be shy we're here for that any other questions oh yeah okay um so related to that last question could you elaborate a little bit on why you need to have a commitment to the Circuit for linking oh yeah yeah yeah totally um this just has to do with like so when you actually want to so I mentioned before this idea that you can actually have third party developed co-processors that are not part of the verifier definition broadly the way you get that is basically the verifier and also the

program itself or was part like The Trusted code base and so what you can do is you can actually basically you can have the program actually specify an an ID for example a hash of some circuit definition that will bind what co-processor can actually resolve a given request for computation so basically what you do is you need you need basically need an ID of some sort that succinctly identifies for example the ecdsa verify Cod processor and what then you commit in in the public IO or the shared memory argument you commit to that ID and then you commit to your IO and basically when you push that into the public into the receipt the ver the the verifier which could be requ to

verifier again uh basically checks that the secondary receipt the auxil receipt for the co-processor actually is a receipt of it's a receipt of the circuit that was specified by the program's output and also has the same IO commitment so Bally you need a the reason you need a commitment to to or it benefits greatly from a commitment to the Circuit that is succinct is basically that way your zkm program can call out to um these co-processors without pre-registration at the uh ver at the general ver verifier level that makes sense thanks yeah yeah um for integration um are there any

projects you could point to or Frameworks that that uh where you like how the integration was done um so all the products I'm aware of currently are in the like add instructions to the ZK VM model and they do it in different ways like protar is different than valita and sp1 is different than R zero but it uh they all kind of still fall in that bucket and the latter two approaches are kind of new exploration this is what I've been thinking about very recently and what we're developing for RIS Zer right now okay thank you but if you see one that influenced this I'd be very interested I may have missed it um so for the shared shared memory

arguments uh approach that you mentioned uh is that shared memory also impacting the memory of the ZK VM as well um it's like it's the same memory space right um or is it like a specific memory used only like for this message passing between the VM and the co-processors you can do either I think that basically the idea of having it be a shareed memory space is somewhat attractive to me it's kind of similar to like uh dma on PCI cards for instance um however there's also obviously Advantage is to having distinct memory spaces and memory regions that you know the co-processor has control over this memory region and the zkm over this me memory region so both models have advant tradeoffs to

them yeah yeah but both are possible yeah makes sense thank you and if we don't have any more question now it's time for the break thank you Victor