ZK10: Placeholder proof system workshop - Alisa Cherniaeva

Transcript

foreign [Music] for our first Workshop today we have Elisa from the Neil Foundation presenting about placeholder proof system thank you hi everyone today I want to introduce a police holder I'm Melissa Tonya Eva I'm a head of research team at nil Foundation firstly I wanted to describe in hmm in details what we will discuss for today firstly I want to give you full understanding what okay it's better yeah okay

um firstly we will discuss why we exactly need modularity and Pro System why we need either for all applications we did build it on the top all new infrastructure after this I give you some examples of different setup processes and last thing would be about how we build the orchids via Ezekiel them and why it's better when just human creates it so [Music] firstly I wanted to give you some understanding what exactly is plus folder this folder at modular type of the knowledge Pro system based on long style organization with custom Gates and

yes I know what you know all words almost all words from here but we have one word here it's a modular so um I just wanted to give you some understanding quite important word so let's start from some you know proof life cycle life cycle what happens firstly we have some source of code and we want to translate into circuit representation and it's our first phase it's circuit generation and we can express any calculation inside code via shortcuts which is familiar for Prof system

second phase it's a proof print processor and the previous processor we just switch to another parameters or process them and yeah circuit generation it's actually part of probably preprocessor but for some clarity I divide it into two faces and just mounted it a one-step setup and the next phase it's a hypnotization procedure what I mean about it I mean you know all this lookup argument permutation argument gate generation always think it's a I call it it Organization for the door after this we have a commitment phase it's Final Phase

when we get finally get a proof structure and after this we verify it for new infrastructure we use even in event verification so look first two phases it's some one step and afterwards Refrigeration commitment verification it can be changed it depend on what you choose on the first two phases for now uh many other proof systems have a constant design so we have some constant parameter inside circuit generation and private preprocessor yes you can just modify it but it's take a long time so it so what I offer in the

placeholder you just choose your desired properties and get a result in Minos so so um what exactly is modularity which components we have inside placeholder so let's start it's a test assumption Fields lookup technique gate generation technique General recursion support event verifier and public and processing um let's I give you some details about firstly trust assumption when I say trust assumption I mean what we want to choose not trusted setup or some minimal trusted setup so it would be just between a different commitment

scheme and in the placeholder we offer two options first one it it's a list polynomial commitment you know it maybe it's it's a prime sight so it's not so cheap verification yes but it's allows us to get some trade-off between generation time and verification cost in Effie room site and it get us no trusted setup the second option it's a budget version of kcg It's Always cheap purification but we would be have some Universal trusted setup so the second option is a field and yes it's based on your previous choice so if

you choose the PC Plus fry it would be you you can choose any field but we need to have a property but one of factors would be a big Power of Two For example it would be pulse filled I give you some factorization and you will see here before and if you choose kcg you need to use field of parent friendly curves obviously next one it's lookup techniques basically all lookup techniques is divided on two approaches first one it depend from Main assignment table and second one doesn't depend from an

assignment table size um you can hear about first approach it's a blue cup Halo 2 lookup argument plan cup and we use generation of Pawn cup what I mean about the generalization I mean I just wanted to put all lookup constraints into one lookup argument Elsa I want to achieve some flexibility inside lookup tables so so if we have some big result circuits and small lookup tables I wanted to push several lookup tables inside to one physical column and another option if we have some small result circuit I wanted

to divide big lookup table into several columns so lookup constraints would be like uh with value should contain in First Column or second column or third column it doesn't have any overhead for proofer face so it's just a pawn cup generalization and the second approach it doesn't depend on my assignment table you can hear about like in calc look up balloon that's all um yeah it sounds like it's bad it's a better option but it has some small drawback because we need to use pairing friendly curves for all these approaches and we suggest to use lasso now it's a work in progress to include in the

placeholder but yes I think it would be like so uh next one it's a gate generation techniques we have two options and first one is our usual custom Gates it's a turbo plonk with all constraints would be looks like this and we can express any polynomial equation via custom Gates and the second approach it's a IVC plant cush you may be here about Nova Supernova something like that but I suggest to use protostar it has some relax and plug shot constraints inside with IVC approach so if you try to choose what really

better for your case you need to think if you have some big repeatable computations it's better to use IVC approach I will show you some examples of this when it would be better to use ABC and in that when we it would be better to use just a usual Pawn cash custom Gates so and it's a small parameters but we have General recursion support what I mean about General usually we have some only recursion for independent circuits so V doesn't have any variables inside one circuit and another circuit and it

doesn't connect it with each other so what we offer we offer different options it's a Dependable circuits and independable circuits I will say it for Dependable circuits for example we have two circuits and output from one circuit would be input for the second circuit and usually a solution is used for when you have a really big circuit and the second one as we care about our evm verification about the verification cost you have two small options for public input hash input and direct input hash input is a good option when we you know we have some public Ledger where we can store all public input it's the

option for when we have really big input and we cannot do send it directly it would be not so cheap okay um I say something about different setup um set up alarms for placeholder and now I want to give you some application a real application what I have already done on the top all new infrastructure first of all it's a GK Bridge it's minus State verification so what we have inside Mina we have inside pickles verification what is exactly it's a it has kimchi

verification which components could be used inside it would be a shortcut friendly hash function it would be elliptic curve arithmetics and that's all but look elliptical synthetic we have two Curves in the middle State verification it would be Palace and Fiesta and we need to split all circuits on two parts uh all scholar calculations would be executed would be executed on Palace site and all elliptic curve arithmetics would be on the Vesta side so we need to have two Fields it would be pasta curve fills

it wouldn't be any repeatable calculations inside so we need to use custom plant cache Gates and how I said Palace and Fiesta it's the best choice for lpcn fry so we would be using this option e and we get no trusted setup as we have some big input we would be have hash input verification and how I said we have elliptic curve for a magic native elliptical arithmetic also we have a circuit friendly hash function exactly it's a possible component so we don't need any lookups inside and how it's a pretty small circuits for yesterday it would be too in power

23 and for Palace it would be two in power 22 yes and so we don't need any recursion at all second example it's for it's elsewhere it's for Solana State verification what you have inside Solana we have some chain of blocks and we need to prove it so it would be some nonsense we could spend the hash function exactly it's a chart and also we would be have some signatures of validate validators it's either the size signatures so what's the bad thing here

the curve isn't suitable for LPC it isn't suitable for kcg because of its properties so we need to use non-native work Matrix so how I write here it would be non-native field and how it's a ziki bridge we don't want any trusted setup it would be Palace native field and here why we use just custom Gates we have non-native arithmetics we have a maybe 1000 validators so it isn't enough repetition for IVC approach here it would be better to use just usual Pawn

cash Gates also it would be big input so we use hash input verification um it will be hash function so we need lookup techniques and how I said we use Palace field it's not parent friendly curve so we need to look up technique what doesn't depend on very friendly chords so it's a generation of lookup how I said also it would be pretty big circuits because we have non-native arithmetics um so we need to split it into several signatures and we can afford to ourselves independent recursion support uh next one it's a example of ZK Oracle

it's like that um why the offer us to you know transfer data from consensus layer to application layer and what we have inside we have inside several Miracle trees but it's really big miracle trees so we have um it's about 10 millions of hash function and it's not shortcut friendly hash function so it's pretty big circuit and here here it's better to use AVC Ponca style because we have some small blocks and 10 million repetition yes it wouldn't be so for each hash function it would be

some sub tree of mercury sub Miracle 3 but it's better option to use ABC approach it's a strict requirement from light day it's not trusted setup so we would be use plus fields we need to crash input verification uh it would be again sha function so we need local technique what doesn't depend on pairing friendly curves and we have IBC plankish so it's obvious we don't need any recursion because we have already recursion inside ABC approach and the last example it's an example of the key gaming in our case it's a speedrun of Dome

uh what we have inside inside it's includes some you know usual Game Dev logic so we need to prove uh so what uh State transition from some tick States um was okay so each tick state would be contains all objects on the games 10 and we need to prove what it's in in the range of all possible States so what we would we have inside we need to again custom plan because it would be different calculations on all calculations is just integer numbers

but but we have many booleans components inside it requires to use lookup techniques it's recalls us to go to the sparse representation so it would be bigger than just usual integer so we need to use some native field which is bigger 128 bits no trusted setup and here we need to directly input verification because we don't have any public Ledger and look how I said it's um pretty big calculation so we need to just split it into several circuits and we need to have dependent recursion

support because output of one circuit indicate Doom would be an input for another circuit yeah so I just show you several examples of our real use application and it's for now it's mean what you need to use different modification or different proof system but here you can just I don't know tick tick on your desired parameters and get a result and last part how was it in the last part I wanted to

show you how we can build circuits and firstly I wanted to answer to one question put it better to made by hand over the klvm yeah it's definitely if just circuit designers try to create circuits it would be better assignment table but it takes much time because it may be 10 takes months for example for amino State verification it's really it takes month and here I don't say about some you know low level circuits like scholar multiplication or just native

multiplication I say about high level circuits like evaluate component all layers component kimchi component pickles component always think it's 100 circuits it's really hungry circuits I do it myself it was Madness really and if we just take cklm it would be just a means and I think it's a great thing yeah but we have as one drawback yeah we have ROBLOX when we used to kill them it would be most Parts assignment table but maybe we can avoid it maybe we can

do it via Ezekiel then like just human design it so let me remind how it looks like assignment table here you see the pictures uh especially it's a assignment table for massage shadow in a shy circuit but it's a just example so it's just a real table which discuss columns row all cells in the table which connected with some gates and it gets it some set of polynomial equations and we care about total amount of gates and gate degree also we care about lookup option is on or off

so um let's think about more immunostate verification I say some words about it and I I split low level circuits from high level circuits and for low level circuits for minus State verification would be Poseidon hash would be poor component variable based multiplication variable base multiplication it's a scalar multiplication on elliptic curves it will be just native multiplication addition subtraction and last one it would be inverse and all kimchi verification

we can express from which seven components it's even not kimchi it's I talking about all pickle certification actually so what we would behave inside let's think what Poseidon Po and variable based multiplication we create especially formula so it would be for example 15 columns but it's just example for multiplication addition subtraction it obviously would be a free column and for inverse we need additional variable so it would be four columns um

I I haven't time to build all you know minute purification for now so it would be small example just take it for one percent and one pole one variable based multiplication for free more smaller shortcuts and two two inverse components what we have here if it would be some simple approach from compiler what we'll do so here we have Poseidon component both component variable based component it's always have 15 columns uh like we designed especially for minus State verification and here look

multiplication we have it would be like in this approach just multiplication multiplication and multiplication after this we would be use addition subtraction and inverse is just like uh automatically naive composer try to build the result circuit but you can see the problem in the circuits yes we have many empty spaces and it's just a small circuits just imagine if we repeat it and I don't know thousand times

what we would be have we would be have bigger columns it means what we would be have bigger polynomials we have bigger polynomial operation inside gate arguments in the proper phase and it really increased proper time it's bad thing and yes it's now it's obvious how we can what we can do it a compressed approach the beginnings get the same it's obviously created especially for minimum and yes we try to allocate it into one row all multiplication

Elsa addition and the subtraction and look at this we have on the second row when we have a addition we have 12 columns and three free columns and it's not enough for inverse so it would be the next row so compressed approach would be looks like sets it doesn't have so much empty spaces yes it's a normal thing if we have it inside our circuits because here it's the best circuit for sure and it has empty sizes too but

yeah um what we have all these small components automatically would be generate additional Gates if we have additional Gates it means what we have additional selector column because each gate have their own new column so it would be pretty big amount total amount of additional columns and it means what it's not better option it means what it has some drawbacks but in another side okay and we have a solution for this

problem it's a flexible circuit technique what we have inside inside we have some Metric function it firstly takes all code source of code and try to evaluate all params and let me show you this one parents for each components what would be better execution for this after this columns compilers would be connect metric function with low level components and low level components would be adapt inside and assign all Gates and assignments in the table in accordance with how many inute

columns rows maybe we can restrict some gate degree usually it would be nine so it's have to be some small total degree it restricts that its decrease the total amount of gates and would be think it would be better to use lookup option on untuse and what we can do with lookup table flexibility how I said it can have one column or several columns that's like this and let me show you about this example how it would be look

like um which circus was designed especially for mina so the beginning is the same here what we would behave if I tried to express all flexible circuit technique in the simple words it would be remove all intermediate variables and push it into one gate so try to remove intermediate variables for multiplication we have three and it's obvious for for Simplicity just imagine it will be the question calculation so what we would have for first multiplication we

would be have two inputs variables but for the next multiplication we don't need to have it we just need to one variable so it would be like 2 for first multiplication and one for second and the third after multiplication yeah we have addition as attraction it would be like this and the inversion inversion has some input and additional intermittent variables we cannot remove it and we need to have some output variable so if we try to calculate it we would be have one two three four five six seven eight nine ten twelve fourteen and

fifteen it would be like variable based multiplication yeah it's a good example I designed it specially yeah yeah but uh into the general case flexible circuit technique will give us like with because it would be exactly how human would be designed with circuit yeah so what I want to say uh in our placeholder we have modularity and with modularity it's not only about choice of commitment scheme it also great flexibility inside circuits so it would be automatically generate result circuits

in minutes um yeah thank you everyone maybe you have some questions I would like to answer for them yeah yeah um [Music] did you codes again [Music] as a circuit yeah we translated into circuits but we use the klbm and some you know low level uh you can hear me yes okay

yeah sorry sorry so what we have in the room yes we have some code and which recited because you kill them into circuits so it would be just a few low level circuits like you know we need to build a Nerf Matrix we need to some shift arithmetics we need to pull components and some native operations and that's all I think control knowledge podcast error and he told me that you can prove I discussed with Misha on the Zone knowledge podcast Telegram and he told

me that you can prove most of llvm ir so in that case you actually just need to recompile to plus holder right yeah yeah so you don't need circuits um it's not actually circuits um how I try to divide it it's we have low level circuits and high level circuits we need to level circuits but it's generally just constraints and just uh technique how we express any code inside proc system so I think that's all thank you [Applause]