Proof Aggregation using GKR

Transcript

all right uh we can go ahead and get started so if everyone wants to make sure that they're they stay muted um until the end and we can we can ask questions at the end uh Navado please please mute there we go cool all right yeah so um this is suwan he's going to be presenting proof of aggregation using uh gkr so yeah if you want to you want to take it the floor is yours hmm yeah thank you for coming today's running share session and I will talk about proof aggregation using gkr

uh I am in the PSA team research group and by the way I want to apologize that I cannot speak clearly because I got sort worth yeah and I assume that most of you have experience about sarcom and maybe you know what is rncs before we start and keep in mind that this protocol is not verified and may have several security vulnerabilities uh I think your screen is black your screen share is black right now uh okay all right there we go okay

can you can you see it yes okay so uh for today's talk I will explain description of chicken AR and design of proof aggregation system especially using fully recursive proof and how to generate gkr circuit from sarcom for the last for the last limitation and further research topic for this protocol gkr is probing scheme for proving that calculation result of this arithmetic circuit is valid

and it uses special form of arithmetic circuit it is called layered or symmetric circuit so initial version of gkr was interactive proof protocol it consists of the iterations one for each layer of the circuit and it is because Separation by layer reduces claim with some check protocol and I will explain it explain it later by using add and multi function wi function takes as input a binary gate label and I'll put the gates value at layer I

so uh let's take it deeper as I mentioned before to care circuits have layers number and the number the layers from zero to depth d a layer 0 is the output layer and layer D is the input layer so these two gates is our in layer 0 and this these gates are the output output Gates and this intermediate four Gates belongs to layer one and these four gates are input layers

and can call layer 2. next s is s i is number of gates at layer I and assume that it is 2 to the power of k i for example S1 in layer one is four and k i k no it is a k 1 is 2. so for each layer number indicates at layer I from 0 to s i minus 1.

and let w i is function that takes Boolean Piper Cube and output field element and also we can get multilinear extension of wi for after use so here here is the example we can set pulling hypercube for Eastgate like binary encoding uh the left most skate can be represented as 0 0 and next is zero one and the next is one zero and the next one is one one this is why we assume that the number of gate is 2 to the power of k i and let's

fill Gates values so first one is three times three so it is nine and next case value is 2 times 2 so it is four and the next is yeah it it can be calculated yeah so six and the next case value is also also two so we can Define the W1 function it is as shown in the slide we can assign each case value to Wi so last property of G Care Circuit is at

I and multi-function these functions get three gates label and if first gate is same kind with function kind and two labels are linked to First gate with input wire it returns one otherwise it returns zero let's see example so yeah add one function and mult1 function have six parameters because previous layer of layer one has four Gates it is Layer Two and for each gate that most label is

gate level label of itself and next to label are input case label so for the other Gates is it can be calculated for the input and the output yeah so for this third gate it is included by one zero and the input gates are 0 1 and 1 0 it is second and the third and the last gate is

can be represented as add one so to to probability of computation proper claims a value for function output which can be obtained by putting r i to the multilinear extension of WI so RI is random field element given by verifier and to prove that prover knows multi-linear extension of wi apply some check to the uh

2 k i plus 1 variate polynomial f if you get some if you get sum of f it is value of multilinear extension of wi when argument is RI because at I and multi cannot be one at the same time when get the same argument in the sum check the probability can prove that P nodes H which is sum of evaluations of polynomials G over all Boolean inputs

in the first round he sends the uni unibariate polynomial G1 X1 claim to equal following sum for all I which is larger than one and smaller than b a p sends to be univariate polynomial see gjxj claim to equal following out that this is typo is this GI and XI and yes claim to equal following yeah um

yeah of this so verifier checks that GI minus 1 r i minus 1 is equal to g i zero plus J i1 and verifier chooses a random value and the field element and sends it to the proverb and for the last step uh it is called final check so verifier choices are random fill the element RB and evaluate original G and then checks that g vrv is equal to the that function value

so yeah we know some check now and in tkr for each layer to some check verification verify we cannot know multi-linear extension of WI yeah but we can do something verification and if some check verification is done for one layer verifier chooses random Vector B Star and C star which lengths our Ki plus one and make function that l0

SB star and L1 is C star and approver P makes unibody polynomial Q which is multi-linear extension of wi plus one of L Q is parallel proof and it is passed to the verifier in q0 is value of multilinear extension wi plus one when the argument is B Star and q1 is the value of multi-linear extension of wi plus 1 when argument is C star so verifiers chooses random R star and r

I plus one is l r star and give it to proverb as m i Plus 1. approval should prove next layer from Mi plus one this is the interactive version of gkr and we can apply Fair Shamir transform to make this non-interactive and I made gkr non-interacted by the uh PS image transform so it is simple to implement wherever you get R star from hashing previous fruit value and it

can be verified by verifier with hash verification in the circuit and the starting point of this research was recursive proof we can get better results by composed different schemes let's first put by internal improving scheme and get proof and then y Circuit of internal approving schemes verification then prove it by external proving scheme so in this composition external proof should have constant or logarithmic

verifier and very small proof size because external proof will be put on chain verifier and in this obligation system external proving scheme is close to 16. and then interfoof should have very fast proverb like gkr and should be efficient to rsmetize the verifier because verify you should be written in circuit like circum or other yeah circuit language and it should be verified in in the circuit

so she cares characteristic is that verification logic consists of just addition and multiplication like it is verified by some do the articulation of univariate polynomial Origins multivariate polynomial so in this organization system my internal improving scheme is tkr is written in circum it consists of some check verification and evaluation of universe and multivariate the polynomial

this can be expressed simply as addition and multiplication so with this circuit you can do snarl composition easily writing circuit in layered arithmetic circuit Manner and get proof from it and then using Circle and struct.js make secure purifying circuit and then get growth 16 proof from that circuit bypassing GCR proof as input however writing complicates circuit with the form of native arithmetric circuit is too hard like it just make graph from

the like python or roast you should make own arithmetic circuit for what from what do you want to make yeah so and if there is to care approver for circum proof aggregation can be done because recursion step can be much deeper with two care approval for circum and we can do iteration for to the circle so this is the diagram for whole system so there is circuit written in circum name it C is it is

original circuit which is uh want to be verified and to be aggregated and for initial step to kruber get witness for C and prove it and we can get the pi I and then for recursive step combine C and verifying circuit CP and it is done by circum syntax like uh import it as the template and we can get the component of the

modify C by adding CVS using template and then previous proof Pi I and the witness wi plus one are input the care approver proves c plus c b and generates proof Pi I plus 1 in this step so we can do the recursive step and then for the last step a similar with previous iteration but prepared yeah c plus c b and generates proof pi n

but uh it is then but it is done by the Snapchat yes then we can get aggregated group 16 proof from sonic.js and we did the verification all step the in the recursive steps so if growth 16 proof is verified all steps are verified also we can call that so to make this I should get layered arsenic circuit from circumcircuit

however uh in the process of converting the arithmetic circuit to our NCS some connectivity is lost and GK approval doesn't have written's generation and I try to make arithmetic starter kit from solarcom file using Circle compiler but it has many optimization inside so I cannot separate from the circle compiler so I chose to convert rncs to layered arithmetic circuit the constraints from around CS have the form a times b equals c

that is represented as argument Circuit by this but we cannot easily convert it as this because C is not a single value ABC or linear combination so for C it consists of many terms and also in our mixer Advocate single term is also the output wire of multiplication gate so we should try to recover also circuit information from rncs so first make directly as I click graph

from each linear combination and this represents a and then connect a and b by multiplication gate and make minus C with this representation and combine them by addition gate it so this tag represents a times B minus C equals zero but uh some in some cases C is used to other constraints like this example so it was originally connected but

optimization of circum eliminated this connectivity then we can substitute c as a times B and then e keeps the connectivity from the original rsmetic circuit and the last step all layers in gkr circuit should have 2 to the power of K Gates so we should pad with zeros for the layers and let's see example so in this layer there are three gates so we should put one zero gate to this

layer and for the next layer there are six Gates so we should path with zero gate two zero Gates so make zero gate in previous Edition and two zero gates are generated after making the Care Circuit we should calculate all gauge value after all weaknesses are assigned to make wi function which represents the gates value so with this implementation we can generate to care proof from sarcom and

make aggregated group 16 proof of for the aggregation however um it was too slow so oh yeah I can't verify just one constraint like a plus b equals c so I applied some optimization to put that like concurrent calculation and check trailing bits for filtering like uh in the previous slide there are there is f function and it has add function and mode function and it cannot

be a same one in the same in the same time so it can be filters so for now