ZK12: Abstractions for a multi-prover zkVM - Georg Wiese

Transcript

[Music] so this talk is about how can we build a zkv m in a way that's agnostic of the proving system which is something that we're concerned with that powder um so let me give you a very quick introduction so um at powder we kind of have a DSL to describe a VM and looks like this the user can declare some registers and some instructions and then provide an assembly program using these registers and instructions um and then that comparts to a ckvm but we want to do this in a

way that is agnostic of the proving system um obviously this zkm is extremely simple and um kind of useless um but we also have an implementation of risk 5 for example but you could also Imagine um ZK evm um yeah and that would take a few hundred lines of code in this language but this talk is going to be more about the low level so let me walk you through the compiler pipeline so on the left hand side you see the high level description and the first step would be to compile to pill pill stands for polinomial identity language and has originally been developed by

polygon um and describe some low-level constraints and then from pill we can compile to different proving systems an obvious choice is darks because that was the original use case um by polygon um but this talk is going to be about how can we also go towards uh folding based backends or tkr so in order to explain that let's go through some of the details of pill so this of course I'm going to explain this using Fibonacci and um so on the left hand side you see a very simple pull program

that describes a Fibonacci computation on right hand side you see the corresponding execution Trace um so in the first two lines um the program declares two fixed columns and fixed columns are columns of the execution trays that have a fixed value so the values are fixed ones at setup time and the appr cannot change them and in this case they're only used to indicate whether we are currently in the First Column or the last column and then there are two witness columns and witness columns can be filled with any value by the prover but they're subject to some constraints um and so if we look at the constraints for example the first two

constraints essentially Force the prover to initialize the Fibonacci sequence correctly with the values one and one and you can see that we have to multiply with this is First Column because one property of constraints is that they always have to be satisfied in all rows of execution trays and then the the next two constraints basically Force approver to update the Fibonacci sequence correctly and you can see that we have this next operator which is kind of this Prime operator um which means that we're not referencing the value of x in the current row but in the next row so that's mostly the obstructions that

we have um so just to recap there's columns which can be fixed or witness columns there are constraints which involve additions and multiplications and they can have a next operator and they need to be satisfied in all rows of execution trays um and one thing I haven't yet talked about is verifier challenges which are just random field elements assembled by the re by the verifier after some witness columns have been committed and this is useful to implement lookup imputation arguments and other things and here you can see an example of how you would Implement a permutation argument so let's go through all the

proving systems um and first up dark as mentioned before this is the most straight forward one because that's kind of what P was designed for um and I don't want to spend too to much time on it but basically a stark is going to interpretate a polinomial for each column of execution trays and this is my attempt at drawing these polinomial um and then the constraints just become constraints on these polinomial and Starks are designed to prove that um constraints and polinomial are satisfied and next up um is folding based backends

so what are folding schemes so one thing they do is they provide for incrementally verifiable computation which means that you start out with some initial state which you can think of it's just a small Vector of field elements and then you keep repeating the application of a function which is fixed function it's always the same function in each step until you end up with some final State and that's the result of your computation and this function at least in the simple cases should be the same in each step of the computation and that is kind of similar to pill which has the same constraints on all rows of execution

Trace so if we if we look at a simplified version of this Fibonacci program um here it's the same program as before but I left out this this first and this last column because um voting schemes kind of have a native way to represent the first and last state um but given these constraints we can essentially extract a function f that computes the next row from the current row and so we can view the execution Trace as a collection of intermediate states where each row has been computed by the function f from the previous row um and so if we view it like this then that fits into this IVC scheme and

then we can compile to a folding base back end and last not but not last but not least JKR uh so gkr is a is another protocol that proves correct computation of shallow layered arithmetic circuit so let's go through each of these terms so an arithmetic circuit is a circuit that computes something just using additions and multiplications and a layered circuit means that each node the circuit can be assigned to a layer number and then you can only receive inputs from the previous layer and by shallow we mean that the number of layers should be

small um which is important because the verification time is going to depend like it's going to be proportional to the number of layers so in particular the the number of layers should not depend too much on the size of the input layer for example and another property that's desirable if it's a structured computation which you can see here so you can see here it's not an arbitrary circuit it's uh many copies of a small subcircuit so it's kind of describing um um a data parall computation it's applying the same function to different inputs and eventually all these layers the

value of these layers are going to be represented as pols and the verifier needs to be able to evaluate these polinomial but only for the input layer and the output layer which typically means that for the input layer there's going to be some polinomial commitment scheme and for the output layer it could also be committed or it could be easy to evaluate by the verifier for some other reason so that's it for background let's look into um how does it all relate to p and how can we take a p program and compile to gkr so in this extremely simple program we just have two columns and one constraint and the idea is kind of to to

just put a concatenation of all the rows of the execution trays and put them into the input layer and then the constraint needs to be satisfied in all of the rows so we can instantiate a small arithmetic circuit many times that just evaluates the left hand side of this constraint and if and only if all the constraints are satisfied the output layer would just be the vector of all zeros which is encoded as the zero polinomial so is trival to evaluate by the verifier and that's it so just to recap I kind of view pill as a language uh to express constraints on vectors of field

Elements which is kind of a data parel way to describe computation and yeah like a structured computation that is exploited by different proving schemes but in different ways um but we can kind of compile to all of them or at least the ones I've mentioned and um yeah that's nice because then you can describe your zkm once and decide on the proving system later or even prove different parts of the zkm with different proving systems time for questions [Applause]