ZK11: Pushing the Performance and Usability of Zero Knowledge Proofs - Daniel Dore

Transcript

[Music] hi everyone um so yeah I'm from the Lita Foundation we'll be talking about the valid VM and how we're using it to push the performance and usability of zero knowledge proofs is this worth slide Advance okay there you go um we'll be talking about zkm zero knowledge virtual machines some of the different high level approaches to designing these uh as well as limitations with some of the other VMS on the market today and some of the choices that we've made with valida to get what we believe to be the

fastest VM um as well as a little bit about the Future these last two points we probably won't get to here but if you come to my ZK accelerate talk tomorrow afternoon uh we'll get a little bit more into the demos and benchmarks uh so we've been talking about zero knowledge all day um but let's recall a zero knowledge virtual machine it's supposed to be a universal ZK circuit so something that allows you to verify the result of an arbitrary computer program uh the deera as usual we want proofs to be succinct much easier to verify than the original computation is to perform and we want to do it in zero knowledge so not revealing anything about intermediate States or private

inputs um as with much of ZK the main difficult difficulties uh with adopting this more widely today are the learning curve of the tooling the high level of tech technical content required as well as the proof systems themselves their um high energy space and time costs uh so the first question that you ask when thinking about uh what is a zkv m is what does it mean to specify a computer program uh you know just about anything can uh simulate Universal computation ranging from ordinary programming languages to something like magic the Gathering uh so one approach here and

this is what we see in um some VMS like Cairo is to use a domain specific language uh so this is something where the interface looks something like a regular programming language but uh you can think of it as a set of macros for generating uh circuit constraints directly um on the opposite end of the spectrum we could have something that takes uh a high level description of a program in in a Common Language and directly uh produces an equivalent circuit this is uh this is challenging to do requiring a lot of sophisticated compiler tooling as well as um the usual High versus lowlevel trade-off where high level things are easy to ver uh

reason about correctness whereas lowlevel things are easier to verify performance or Reason about performance uh so we take a hybrid approach um where we have an intermediate representation of the program uh that is thought of as a set of machine instructions for a virtual machine uh so M much like you actual physical processors uh so we hope that VMS will be the main way in which developers interact with zero knowledge in the future avoiding the need for um you know long learning times of ZK systems knowledge of cryptography as well as the potential security implic of working with these things

directly um so some of the limitations with the VMS that are out there today uh are that the domain specific languages the domain specific language based VMS can be difficult to work with requiring developers to learn a specific language for the given VM um not being able to reuse code across different proof systems and just representing a different way of thinking about programming than developers are likely used to um as well some of the VMS on the market today uh do not have full open- source support for all parts of the stack um by which we mean not just the um the core components of the verifier and prover

but including things like um proof aggregation proof recursion and uh constraint generation uh so many of the other systems around have some of these but not all of them open source uh as well we want to have uh something like ethereum pre-compiled we want to have special handrolled circuits for common cryptographic operations um like signatures or evm transactions that uh can work faster than you know the equivalent uh bite code um there's also uh inefficiencies in performance uh some of the things that lead to this are VM design issues where uh your memory model

or your instruction set are not optimized for uh friendliness of representing in snarks but rather for similarity to electronic computers um another thing that uh that we care about a lot is we want to be able to quickly integrate the uh zoo of recent cryptographic advances in this field um I think there's a a new paper that kind of changes everything every two weeks at this point uh one big thing here is support for small Fields um as we've seen in the last year or two this is really driving a lot of the performance gains in zero knowledge uh so in other words we need a VM that is extensible performant and

developer friendly uh so the high level idea of how we go about designing such a thing is that we start with the cryptography choosing a proving system that is uh performant and has the right trade-offs between proof size and pro performance among other things and for this we use Starks um and then the the next thing we do is we uh create a virtual machine description uh this uses an instruction set that is not a standard one like Risk 5 but rather something specific to us and the benefit here is that the model of the virtual machine itself and the instruction set are easier to represent in zero knowledge circuits than a

standard instruction set might be um however this creates the need to create compiler tooling to prevent developers from having to work in this unfamiliar environment themselves so we want to be able to compile programs from something like C into our instruction set uh from here and uh these are the parts that are are a little bit uh forward-looking we want to use Hardware acceleration ranging from gpus to ASX to uh you know really get the best possible performance and we want to use formal verification for uh core components like the especially the proof verifier and the constraint system itself um if you were at Justin Drake's

talk earlier today uh we see there's some exciting things coming up from the ethereum world on both of these fronts so the VM we can think of as having uh communication on two sides on one side it talks to the Prov the approver is you know a an engine that creates the zeron knowledge proofs themselves on the other end it talks to the compiler which translates ordinary programs into the instruction set um at both of these there's op there's opportunities for optimization uh so the idea is that because um zero knowledge circuits are very different from ordinary electronic circuits the design of an instruction set uh might look different for example

in ordinary electronic circuits it um it's important to have uh to to use cache and registers as much as possible because accessing them is faster than accessing main memory due to the physical location on the chip this of course has no meaning in the abstract world of zero knowledge circuits uh and so so one of the things that we change is we get rid of registers I'll say a little bit more about that in a second and then to support this we need to have compiler tooling that rewrites code that uses instructions that we don't want to include in our instruction set and replaces it with equivalent code that does um so our system we can think of as uh consisting of a set of chips modeled on

how an actual processor Works uh so there's the main CPU module a module for memory a model for b a module for binary arithmetic as well as um yeah some more spe specialized things like in range Checker chip uh so each of these is sort of an independent circuit that communicates with each other using the io of the circuit as well as additional arguments to verify compatibility between them uh so here's a schematic of what this looks like uh our memory is divided uh this is a Harvard architecture so main memory is separated from the memory uh including the source code of the

program as well as um a special tape for the input and output these communicate using a series of buses uh which are just the public IO of the circuit in um circuit language uh now here's some here's some interesting choices so the only registers that we support are two special purpose registers uh one contains the program counter so that's the address of the current instruction and memory one contains the frame pointer which is where the um stock frame begins uh we do not include any general purpose registers like an ordinary CPU has uh for the reason that it's no more

costly to work with main memory than it is to work with registers in our setting and having registers requires us to have Trace columns for each register and the air programming model used by Starks this creates a pretty heavy overhead for each register um so to uh the way that we work with memory is that you can address it in two different ways either relative to the frame pointer or using addresses uh so instead of you know instead of uh an instruction reading something from you know one of 32 registers like you have in Risk 5 you put everything in main memory and um address it using offsets from the frame

pointer so this would include you know operand for an instruction um return address for function calls that sort of thing uh and and like I said it's a Harvard architecture you can't address the program memory separated um so yeah so in in some sense uh we have a separation between stock and Heap stock grows in One Direction Heap grows in the other um I'm not going to say too much more about that uh but yeah so we can think of the software as consisting of three big Parts one is the execution engine which runs the actual program and generates an execution Trace one is the

prover which takes the execution trace and turns it into a zero knowledge proof using cryptography and then the last is the verifier this is the same setup that every VM has uh one key thing about our design is that we use the baby bear finite field this field is awesome because arithmetic in it looks very similar to ordinary 32-bit arithmetic um reducing something modulo P for this p is a very fast operation in actual Hardware um however this field is too small to provide the uh requisite amount of cryptographic security so when we do challenges we have to draw them from a larger field this is a degree 5 extension of this field given by

adjoining a fifth root of two nothing particularly special about the fifth root of two here it's just some degree five extension of this finite field they're all isomorphic um and then we use uh we use Starks so the commitment scheme of interest is the fry polinomial commitment scheme uh however we are looking at the possibility of using some uh new commitment schemes that came out this year such as Bas fold um so the the general way the operation works is we have um one execution trace for each chip so the memory the arithmetic the CPU um and then we encode these traces

which are you know vectors of scalers in this 32-bit field we encode them as univariate polinomial using interpolation the same idea that that is used throughout ZK commit to these using fry and then um the last bit is a little bit interesting is to ensure uh compatibility between the io of the different chips so that you know the CPU has the same view of the information being exchanged between it and the memory chip as the memory chip does uh because these are separate constraint systems this uses a the permutation argument similar to the way that copy constraints work in plunk um then to get the actual proof we plug these into the constraint equations

uh these are multivariate equations uh this is the air constraint system but uh plugging in a bunch of single variable pols each constraint gives us a single variable polinomial and then we combine these using random linear combination from a challenge Alpha uh generated by hashing the um everything committed to so far then finally uh to show that this constraint vanishes on all of the points used to define the polinomial uh we show that we know the quotient by the zero fire polinomial which is the one that vanishes on the set of um of the domain okay this is the same the same

construction that's used in every Stark and broadly similar to the constructions used in in other snarks as well um but we do this once for each of the chips we do uh we get all the execution traces and then only after all of that is done we generate the traces for the permutation argument um one thing to note here is that all of our constraints have degree at most three which helps keep the cost down uh also Starks only use hash functions so we completely avoid the need for 250 6bit Fields elliptic curves and other expensive cryptographic operations um already mentioned this

that this baby bear field also known as the 31-bit maren field uh or maren Prime has uh has extremely good arithmetic uh here's a diagram of our compiler pipeline so we uh we use llvm because it's something that is enjoys a wide degree of support um and has compilers from your favorite programming language IE rust okay just dropped the pointer uh here's here's another schematic of this uh so we we see that we pass through a series of intermediate representations uh know from the llvm

generated by the ordinary llvm compiler we then optimize this uh to end up with something at is instructions for our specialized valida language um something that we care about a lot with valida is that we want everything to be very customizable uh so you can go right now to our GitHub download this and spin up a VM with your you know favorite series of configuration choices um we want to be modular in sort of all aspects of the cryptography from the um from the choice of polinomial commitment scheme to even the arithmetization and stuff itself um also everything that we do is

fully open source Apachi MIT licensed uh so you can use it and do whatever you want with it um finally uh and this is what I'm going to say a little bit more about in my accelerate talk tomorrow but here's some numbers from running a basic Fibonacci program and uh we see that we end up 933 times faster than risk Zero running on the same program so that's pretty good um finally uh click through here's here's an idea of what the developer interface might look like I don't really have time to see more about that uh but I wanted to make sure to mention our Early Access program

so you can uh use the valid VM now help us develop it and uh also we are hiring so let us know if you're looking for a job we're hiring ing for um compiler Engineers cryptography Engineers contributors um as well as as product people uh here is our contact uh lead XYZ is the company Twitter my telegram is tessera and vental is vental 8 and that's it thanks very much [Applause]