Plonky3 & Valida: Pushing the Performance and Usability of Zero Knowledge Proof | Ventali Tan, Lita

hello everyone um thanks thanks for coming and um today I'm going to talk about um pushing the performance and usability of Zer knowledge proof uh it's a joint work uh you know of over 10 people uh it's uh you know Morgan Daniel Marty um Ellen Michael just wanted to highlight the authors um table of contents so um going to go through like why we building a D KVM what are the methodologies that people have been trying um why we think dkbm is the future Direction and uh what are the limitations with existing ZK VMS uh there are a couple uh Cairo R zero and miden um and uh how we are uh you know what we are doing to build um the fastest ckvm and uh how we're optimizing the Prov zvm the compiler deck um and then I'm going to show a demo benchmarks of of the current uh VM um so I guess the motivations behind DK VMS is um how do you prove succinctly and in zero knowledge that uh a certain program was executed on a certain input and it had a certain output um and um succinctness means that proes are not too long and zero knowledge means that the proof contain no useful information beyond the facts that they're proving um and and the problems I in this Bas is that um first one is the learning curve of the tooling uh is really Steep and then the second is um um the high time space and energy cost of creating zero knowledge proofs um so these are uh three I guess compilation approaches that people have been trying this space uh the first one is DSL I think most of people here are familiar socres cir on a bunch of other languages um are taking the first approach um it's basically attempt to use domain specific language to build abstractions on top of low level constraint systems uh such as R1 CS or plunk acting like uh constraint writing macros um and um the second approach is is direct approach uh is is actually um a project worked by anoma called I think juvu um and uh Chris was leading the project so they're trying to directly compile highlight programs to Circus directly uh without an intermediate construction sets um and the third approach is uh guess the instructions uh sets and VM approach uh which is to define a intermediate uh virtual machine and instruction sets architecture uh to mediate between the highle language and low-level DK constraint systems um and all of them are actually trying to I guess like the first approach um all of them have advantages and disadvantages I listed some that we think are you know the pros and cons and for DSL um it's really easy to build obstructions on constraints and allowing for a closer reasoning about performance circuit performance um direct approach I personally don't know that much but I think it's potentially very very high performance because it doesn't lose information to IRS um and uh it's easier potentially easier to verify um and then VM approach is definitely um developer productivity right it allows for the use of high languages um high level languages uh that are more familiar to developers um and um those those are the three three approaches um and we think that because of uh mainly two reasons development productivity and security um that dkbm is the dominant way that developers would interact with their knowledge um um okay limitations with existing ZK VMS these are too small Texs are too small um but uh we're basically listing some issues with uh I guess CYO and risk zero um uh and um for Cairo I guess uh it's mailing about uh developer productivity writing chyo cold in experience among like Audi firms um and Runner performance um and because of non- determin is and handling CYO has some like fundamental limits um only the Run of performance um and there's no I'm not sure if it's still like closed Source because I heard Stone Prov is open source right now but uh a couple months ago there's no like uh open source Prov um and uh it's hard to to support smaller field like thir one field um uh for Cairo and then for riro it's um mostly like oh there's no open source recursion uh constraints are autogenerated and and the code generation is not open source so it's really uh it's make it impossible to fork and modify and add um uh modules I guess uh and it's also cannot be easily changed to support a smaller field um okay there bigger text um so car limitation uh risk limitation uh and then the common issues is the 31 bit uh bit filled um to improve proove performance um right so I guess in conclusion um miden stack is um stack oriented design and it's probably less efficient due to the you know heavy stack manipulation and uh Caro architecture uh is unsuitable because of its um unusual memory model and lack of essential built-ins co-processors uh risk zero is uh we think is a better option than CYO um but it's not the ideal for pro of performance because it's uh conforming to risk V architecture and it's not uh that snark friendly okay so uh we need a tqvm that's much more extensible performant and developer friendly um that's basically what we've been working on for the past a year or so um and I guess these are the steps to uh build this dkbm um and uh the first one is we chose and build a base proving system uh it's called plunky 3 it's collaboration efforts between polygon and us and some open source contributors um and the second step is to build this dkbm uh with the DK friendly instruction sets uh that are tailored to uh maximize uh Pro of performance and the third is to create a compiler tool chain uh and we're using lvm IR uh so we're writing this lvm IR to our VMS compiler uh allowing for high level languages to compile on R tqvm and the fourth and fifth is like Hardware exploration uh and formal ucation so optimizing for approver VMS and compiler uh there are some I guess uh the slice is just trying to say like uh what are are some of the questions that we were thinking when we designing this um and um so the first I guess is like of course tricks to maximize uh Pro of performance that's on the plunky 3 side uh and I'm not going to talk about plunky 3 uh today I guess um and uh another I guess uh leading qu uh problem is uh there's a difference between ckvn Computing environment and Hardware Computing environment and that can drive and derive different uh instruction sets design decisions um and uh from compiler to like like the zkm ISA side as um as one question is like what instructions are more efficient to include and to check in in the stock constraint system what instruction sets are are more efficient to to exclude from the ISA and eliminate from the compiler output by replacing them with a sequence of instructions uh so those are the questions that we're thinking about when we are designing the isas and designing the the stack um so Vala instruction sets is a Ultra risk um not sure if it's a term but it's like a Ultra reduced instruction sets uh it's modular and it's uh a DK friendly instruction set and it includes um basically the following modules includes uh 32bit Lu chips um and uh includes a CPU chip memory chip pram uh ROM chip and then an a 8 bit Ren Checker chip um here's a cute diagram about uh valita VM uh was talking about uh this is the AL chip with um add be wise equality in equality logical shift uh left and right and stuff like that um and there are some like traits of the ISA so for example is uh we have two special purpose registers um program counter PRP pointer there's no general purpose registers and uh want to take this as an example of so uh how we were thinking about this is that uh it simplifies code Generation by eliminating the need for register to be safe and restored uh in the calling convention and eliminating the need for U register spill and C to be admitted um and then it's two REM addressing modes blah blah and it's program realm can be addressed um uh this is the last slide about Isa um so there is no dedicated stack pointer register and the colon convention uses constant size stack frames and uh variable Siz Locos and arguments will be held on the on the Heap um so uh the VM overview is uh it's it works as you know all the other ZK VMS it has an execution engine which runs valida programs and generate execution trace and then there's a prover that proves the result of um executing a program by proving the existence of that valid execution trays and then the verifier verifies the result of executing program given a certain proof uh so it's three components um and some basic parameters about uh valid KVM so we're right now using it base uh our base finite field is we're using baby bear uh I think we're working on mer and field uh mer and 31 uh 31 and um they're using fry PCS right now um we're also integrating with uh base fold which is uh a paper recently published by Hadas who work with us um and uh and also breakdown but we were still thinking about uh the pros and cons there um and uh this is I guess I talked about this before um so the prover uh I don't think I need to go over all of this it's just like telling you like how the appr is generating the execution traces and you know um the I guess the procedures um I can pass this really quick um okay so the techniques of those uh I guess I want to go over this because um so two main points is that um this proving system the plunky 3 is very efficient and uh the most expensive crypto per if it uses is the hatch function and so rvm uses gate with degree at most three uh we're trying to keep fft and hashing CA as low as possible so that's uh I guess technique number one um number two is uh we're using this finan field that's really efficient um so it's uh B bear and immersive field uh that's the number two so that's I guess the man takeaways for um the optimizing the pro side um and then like the final step is uh the lvm compiler that we writing uh this is just to show you sort of the the process um the mtic is like we're planning to support um right all the front ends uh that's supported by lvm um cc+ plus rust um and uh go um in in other languages uh so this is basic compiling the lvm IR to our VMS assembly um this is the compiler overview uh so from C to cland to lvm to lvm Optimizer to our uh valita backends and then uh to our VMS assembly um so Vala's implementation um I guess two M advantages except performance is uh that application Builders can use uh the included compile time micros to gener generate a with VM improver based on sort of a set of chips customized for their uh use case so if you're building a DK VM um right you can choose like oh I want to uh want to acceleration circuits for key check function uh hash functions and you can add that uh so it's really like a modular customizable uh uh design um and then it's also fully open source so um the VM is uh dual Apache and MIT license um I think we are um probably like the only one or if not the um I guess it's a fully open source um so um please check out the repo and you know feel free to contribute um so I'm going to run like a demo of a FCI um program and uh oh yeah thank you I'm Morgan Thomas applied cryptography researcher at lead Foundation I'm here to demonstrate for you the valid zkv improver I'm using an example which computes the 26 element of the Fibonacci sequence using a simple iterative algorithm this example has been handwritten in valid a machine code you can see here the rust code that generates the machine code and code comments describing the assembly code for this program uh the rest of this program here just instantiates an instance of the valid zkv onover and proves the execution of the program um so let me show you that this is built there you go and let me run it for you um I'm going to run this example in single threaded mode so there it is uh this so this time it took about 0.08 seconds in user time or CPU time to run and about 0.09 seconds about the same in wall clock time uh so for comparison uh Computing the 26 element of the Fibonacci sequence in Risk Z using risk Zero Zone benchmarks uh I found that to be um about uh 33 times slower in terms of wall clock time on the same machine um and it was running in multicore uh it took about 933 times more CPU time or user time on the risk zero side to compute to to compute the same answer uh okay so uh here are the benchmarks so uh what Morgan was demonstrating is uh this iterative Fibonacci um and the depth is 25 um and um I think we're uh 133 times faster than zero and um risk is using like a matrix uh function which is like a bit a typical for like a fonat program so there's like a slightly difference in like the algorithm so it's not 100% um you know exactly the same algorithm but um uh I guess this is The Benchmark for iterative Fibonacci and uh this is for recursive Fibonacci um any so I'll pass this okay so ongoing work um I mean this is what we're working on at the moment um so we still like reconsider the implementation with breakdown we were thinking about using breakdown um and um but then we were still thinking about because it has you know slower recursion Etc and then um yes the second is um a vectorized implementation of s hash functions um and uh the third is um we're trying to optimize fry um using some techniques and then the fourth is we're investigating alternative memory arguments handle uh the long memory traces uh uh that are more efficient in plunky 3 um then fifth is I was talking about the base F PCS and we're implementing that and integrating that into plunky 3 um and these are the going work um so guess like uh we're also building this developer platform that U we're trying to make it easier for developers to uh develop and improve and deploy so uh this is a platform that uh you know you can use it to create new projects and uh You' be able to choose s of different templates this is like language templates but they're we're also writing a lot of um application logic templates that you can use um uh so here are some examples of the templates that provide uh for example providing this consist SDK or uh lik line or Dex SDK and you can leverage SDK uh build your projects and uh you can prove locally about the cost uh to um to to measure the cost of approving and um be able to deploy uh their projects using the platform so you be able to choose the configurations um the hardware configurations of the VM you want to use uh choose the approv agregation Val you want to use um and the network you want to deploy and um so this is the the another um uh developer interface that we're working on as well um so I guess that uh you know last slide is is um valita is extensible performant and developer friendly dkbm and um yeah thanks for everyone um so we have an early Access program uh you know you can uh sign up on our website it's free and it's uh give you early access to the VMS uh and we can also help design and validate your your product ideas um and we are uh hiring people so uh we have this Innovation team which is uh like uh R now has like one person but uh we're trying to put together Innovation team to uh build interesting products um experiments um and we're looking for talented cryptography engineers and lvm compiler engineers and if you're open source contributors um you know uh talk to me and um uh you have mentorship for from all the best like proving people in the field uh I think it's going to be uh really uh uh fun so um this is our Twitter my Telegram and and our website um thank [Applause] you and now we will have five minute QA time so does anybody have question for V Vali uh would a security audit be available for the stack in the near future security security audit oh yeah we haven't done secured Audits and we we're talking to a couple uh firms and uh it's it's like hard for us to like um find someone with like both lvm expertise and ZK expertise so we're we're still trying to you have to audit both the compiler and the host stack essentially yeah so yeah yeah uh two questions the first one I might have missed uh the answer um if you're not using general purpose registers are you using is it is it a stack based machine uh it's uh like yeah okay so but so if that is the case what are you saving um I mean if the argument against using registers is so that they don't have to be pushed on the stack you are using the stack anyway so I'm uh I'm not sure exactly what is gained here um yeah I can talk about this offline if you're okay no problem uh second question is about the comparison like the benchmarks you you shown um um from what I saw in the code uh like demo went a bit fast and I I don't know uh I don't know the the library that well but it seemed to me you were just hardcoding the assembly in Rust uh yeah and I would like to know uh when you when you run when you compare to the risk five uh sorry risk zero implementation there's a risk uh there's somewhere there's a risk five program was it also handwritten in assembly or was it R like compile rust basically uh we're using their own Benchmark and their own Benchmark is uh written in Rust I think okay cool thanks do we have more questions uh I'm curious about uh as you mentioned that uh one of the advantage of Bia will be the cability uh that uh the developer will not to need uh change their C or go or r c um is there any language limitation for the Validia implementation for now for example how will the Validia deal with something sort of that uh Dynamic array or dynamic programming environment that uh if one of uh the developer want to Implement that something sort uh uh the algorithm of digest TR or something sort of that uh how well the Val they deal with that uh were you're asking about language support yeah yeah yeah yeah exactly yeah um right now we uh are working on the compiler most of the c um libraries are working and um uh and then we're going to work on Ross and go and um basically all the lvm compatible languages can be supported and uh about the dynamic uh programming problem uh We've writing uh we we wrote like a note to this uh question so I can send it to you like offline if you're interested it's like a long conversation yeah yeah thanks do we have more questions for vental okay thank you vental thank you and [Applause]