zkStudyClub: AirScript presented by Bobbin Threadbare

Transcript

welcome everybody to the study club we're this week we have Bob and threadbare who's gonna share with us air script and I believe there's the paper by the I think by the stark word guys that you had is like pre as something to read in advance and there's also as far as I could see like some sort of repo what did you share it was like a github so basically what I would like to do and maybe let me see if I can just go to the agenda slide so the first two parts here is basically just slide with some information presentation so forth but the second two items is I'd like to do actual examples and the repo contains

those examples so if anybody wants to clone it and kind of follow along I will actually be sharing my screen and how I write air script and how execution traces and so forth so if anybody's interested you know what'll welcome to do it but if not and or if you are not able so I will be doing the same thing on the screen so either way it works okay all right all right so basically the first thing I would like to do is to just go through some of the concepts behind and exactly the musicians over and then very quickly go through start basics and then jump into some examples and you know feel free to interrupt at any point ask questions if in time stating something let me know and I'll

be going fairly quickly because I think all of this is familiar to many people on the call but if something doesn't sound it's confusing or anything just you know speak up okay so just to set the context know if you think about computations in general we can think about them in two different ways there is a circuit or there are two different ways to represent them there are circuit computations or machine and representation of a computation and the first one is dominating circuits you can reduce computation to the kind of a circuit and the second one is that is a transition function that explains how a complete state of computation changes from one statute

and in terms of refute ization for the certain computations we have our ones years and this is what is typically used and for machine computations we use air algebraic intermediate representation and kind of fine little benefits and again the nuances here but high-level benefits are one CS is fairly easy to kind of reduce yet from a general-purpose computation it's the composition is fairly simple it's not necessarily the case with error it's not as easy to kind of compose different computations together but at the same time error because of the way is represented simply and it allows you to have potentially faster proof and

verification times as well and in terms of languages and sorry you seem like a dog my dog in the background I'll try to look in but in terms of languages there is a bunch of languages for our ones here's our kiss your comb Socrates and for machine deputations as far as I know as of right now there is air strip and air assembly and I'll be focusing on air script for this kind of session but air assembly is a kind of low-level language at air speed compile speed and in terms of where different types of representations are used in so most snarks as far as I know maybe the own Starks are relying on our 1cs constraints or our 1cs representation and here is as far as I know again is

only used in Sparks I don't know if other systems that use a representation but I might know know everything okay so any questions about this part all right so it's sorry to interrupt would be first to say that as could potentially be used with a pairing based system on our minds mm stock to generate a stock it could be but to be honest I'm not sure how that will be done but I mean it's possible I guess you should be able to use the compiler and Marlin like I think you can convert in the air RS io

p into an a HP and then use the penultimate scheme KCG or darks okay so then I guess you can in theory use air with yes no it's doneness yeah make sense okay so kind of to understand air there is kind of you know few high-level concepts that once you kind of understand what they do I think everything else is fairly easy and the first kind of base concept is a commutation stage so the state can be represented as more registers and these registers are field elements and some field that you've chosen for let's start and again it could be either one you

know if you want to do anything useful it's probably more than one and it's kind of a snapshot over computation the given point in time and you can think about it as almost as a computer processor it has registers and this is similar to that those registers have States at a given point in time so the next kind of concept is execution trace so if you take if we take the state of a computation every step of the execution we get the committed execution trace and this is nothing more than kind of a two-dimensional array you can think about it where a column is a register and a row is a state of kind of state of those registers the given point in time the next concept and probably one of the

more important ones is the transition function and a transition function describes how you get from one state to another basically you know you take you know first aid apply some if make operations to it and you get a second state and so forth and the transition function you know in this case like it can take in this the way I described it here it can take a vector of values and it produces the same of a different vector of balance it doesn't work on a single value then the next thing is transitional constraints and this is a kind of slightly different from a transition function now we take two consecutive states and we run those through another function and if we get a

0 that means constraints satisfied so the function G in this case it also works with two vectors and you know if we get a vector of zero said then that means that means the constraints are satisfied in basically the traditional constraint just they describe and algebraic relation between two consecutive states and then the last thing is boundary constraints and you know they just allow you to say that at a given point in time or at a given step even register has specified value now both transitional constraints and boundary constraints they actually kind of just different way to think about rational constraints and you know they kind of have a the most kind of basic level they have the same representation but conceptually I think it makes sense

to separate them and was much more than transitional constraints in this presentation all right any questions I have it I mean I have a quick question regarding the transition function and transition constraints so constraints does that mean that like the important thing from the point of view of the validity of the stock is that the constraints be held but is is the implication then that the transition function it's not necessarily a function as in it can be like non-deterministic and as possible possibly multiple allowable state transitions yeah you could you could do a lot like you don't have to in theory you don't even have to

have a transition function it's easier at least for me to think about there is a transition function you can generate the execution trace in which are away but as long as you can apply transitional constraints to the you can trace that that's all that's needed but from a standpoint of how you describe computation might be easy frequently to have a transition function so what you're saying is totally valid okay thanks yeah so execution trace and kind of I described it in a little bit it's a sequence of kind of states of the computation given point of time and this is what I call a dynamic dynamic registers there is another thing part to it which I call static registers and

these are registers that can be generated without a transition function these are registers that can be described basis simply both for the proven the verifying they work under the verifier can evaluate and can get the value of those registers at any point in the computation very simply and just to give an example one of such static registers would basically register where you have a sequence of values that gets repeated over and over in the institution trades this is extremely easy to describe and the vapor I just need to know the description those you know balance that needs to be repeated and they can compute the you know the state of the register thing against that

the other one could be what I call fully register is where you have you know values spread across the entire register you don't really necessarily care about what the in-between values are but you here that would say you know it's the bonding our bond that's that v you can step for you have two and so forth and those are the two times that I kind of at least an airstrip work with but it actually is pretty powerful you can combine them in many different ways to get different shapes of the registers that can be communicated to that give you fire in the very 16 manner it can be evaluated by the fire in the basis of matter and air script actually uses this if once we go through the examples I'll show you how they are used to kind of

feed input samples and ingest them into the computation state or execution trace and just some general considerations about the execution trace the length must be a power of two this is needed for efficient evaluation or interpolation and evaluation using FFTs you can make kind of by default all the dynamic registers are private so the day fire doesn't know cannot get the state of the dynamic registers but static registers you can make either public or private you know if their respect even if they're described so simply you can still keep the actual register private and only just disclose part you know even point in that register using boundary constraints and the field in which

you're working should have a fired new order route so engine again this is needed for efficient evaluation interpolation used by 50 so often on the previous slide yeah would it be fair to say that these static registers are kind of somewhat reminiscent of pre-processing in the case with I think you could say that I mean it's just it really is just a kind of an equation that gives you like a very sick syncopation that I before I can evaluate so maybe there is some connection to that yeah B verifier has and is kind of sick sinked

yeah and it helps along with the computation yeah exactly I think there's and I guess my second question is in practice if if you're interested in running your your state-transition function some number of times other than the power of two how do you deal with that so you can run it for X now whatever steps you need and then you can kind of zero out the rest and I'll show you a kind of technique on the next slide how you can have two different transition functions that do different things okay you can say like for the first you know let's say you

have sixteen steps for the first ten steps you know I do something and then for the other six steps I find different transition function okay so a transition function kind of just extend the definition that I gave on the first slide now that we know about static registers is very similar it takes you know the current state of the computation now it also takes both static and dynamic registers and it produces the next state of the computation and the technique that I was talking about is you know I don't know maybe there's a different thing for you but I call it I've make switching but basically what you can do is you can have two different functions and you can have what's a static register that takes some value it know at one point and then

it could be like positive zeros then you can turn on and off different functions so in this case you know where K 0 static register is one F one function gets executed and when it is zero the functions who gets executed and this is pretty powerful you can extend this to a lot of different kind of complex scenarios where you have multiple transition functions one once ethical leading a let's say harsh the animal will be doing something else so it's pretty powerful the one thing to keep in mind is obviously the more of this you have the more it increases the mutational complexity because all of this I've added in parallel so you the

more you add the more you have to evaluate it also and I'll talk about this a little bit later maybe even here it actually increases the degree like every multiplication you do increases the degree of transition functional constraints as well and you need to to get as much out of kind of in terms of the Coover time you need to decrease the completely degree as low as possible so some considerations for transition function you know you can do any kinds of arithmetic operations multiplication addition division and so forth a degree of the transition function grows when register is raised to a power we multiply its registers and kind of one thing I didn't really talk about is this

tradition function only works was two consecutive states but in theory and not only in theory but actually you know there might be useful in situations where you want to count with this color like home range transition function where it can work on multiple states not just the two consecutive basically it takes more than one state to produce the next state and example of this would be like if I match a sequence where you actually have to rely on the two prior states there is a way to represent a financial sequence using this type of function as well but a more natural way would be to be able to rely on the creep in two previous states I'm not going to talk a lot about kind of long-range transition functions constraints in this presentation but there is there is a different way to describe a transition

function the more powerful way but it also adds much more complexity alright and constraints now just to update the definition that they gave on the first slide again now it takes the first two states of the computation and it produces or as well as the static registers and it produces a sequence of values that become your constraints that even they evaluate to zero for you know those types of mutation than your constraint is valid and then frequently you know if you have a transition function and this is where you know sometimes it's useful to describe because you kind of kill two birds with one stone is that if you already have a transition function frequency frequently

your transition constraint is just you take state of a commutation of my transition function to it and subtract it from the next state and that should give you zero but it's not always like that sometimes you can no have split your transition function into two different functions and apply it let's say the first one to the next if they're the computation the first one to the previous happens subtract one from the other to get a relation this is for exactly what the rescue hash function is doing they make our transition constraints that are not kind of just as simple as subtracting their transition we thought of a transition function from the next state some consideration division at least with an air script and

kind of conceptually I'm not sure how to did addition and within the traditional functions but you can emulate it using kind of other means the degree of the transition function or sorry this is transition transition constraints the degree of transition constraints do not have to be the same as the degree of transition function so to bring up the example of rescue again the transition function has extremely high degree because they're raising you know registers to a very high power but because they are splitting that constraints into two separate functions and they're able to kind of to do the inverse of the original kind of raising to a power the degree of them constraints is much much smaller

actually like only three where the transition function is actually close to the magnitude of the modulus of the field so you can and again as Justin said before the transition constraints are the ones that you really care about the degree of the transition function doesn't really matter that much medically of the transition constraints matters a lot and again this doesn't address the long-range constraints where you can actually work over more than just two consecutive states okay emulation of the division is just you know multiplication with the helper the most general form of transition

constraint function you show two variants and if the second T is the most general or not uh I mean you can make it almost anything you you like in the simple computations like most of most frequently is the frequent one it was the ones that I've been working with I think as your computation get more complex you will need to apply slightly more complicated transitional constraints so I'm not sure if I seem enough to say what's the kind of the more general case the things that I've been working with more frequently is just the simple constraints okay all right so the next thing is just kind of

very very basic overview of how starix work and this should be you know somewhat redundant to what I've already said but basically you start with some set of inputs you run a transition function and you generate an execution trace and then you know you're applying your constraints to the execution trees and you get the constraint evaluations and then these get kind of using linear combination of random linear combination that they get compressed into a single composition polynomial and then you use the Frye protocol so kind of and you know I have skipped a bunch of things here there is like a degree extension and there other things that happen here but at the high level this is kind of the process

and the important thing is really that the first two steps are computation specific and the other two are commuting agnostic meaning like once I have my constraint evaluations I don't really know there isn't really anything different that I will do for about computation versus another computation and the way I think about the world at least in the libraries that I work with the way I split up that air script is kind of used to handle the first two states that steps you just this is what and if you used to describe the computation as well as what you use to generate execution trees and the constraint evaluations and then the gen spark is the library that picks up whatever could generate some kind of a

price there that starts to generate the start proof and kind of a defined level then the major components of error script is but it needs to have the food is three things it means to have the logic for how you generate execution trace it needs to kind of logic for how you generate constraint evaluations and also somebody about how you interpret the inputs that you pass on to the script and the way it works from kind of a tool chain perspective is that you have a food source it gets compiled into air assembly module I think I mentioned it but air assemblers can have a low-level representation it's not something that you will use to like write but it is much easier extra work was it this very low level

representation and one of the things that I'm working on is trying to make it composable and it turns out that making things composable at the lower level is much easier than high level so I've created air assembly so that I can make air straight composable and then just arc no kuvera fire and evaluates the module builds the proof out of it and you can also use it to verify the processor and and I'm hoping that air assembly can be kind of generic enough where other people can create different types of scripts or your script is just one example but maybe somebody will come up with something else that compiles to air assembly and then maybe in the future as well will have different tools as well we're assembly have some assembly or

something written in rust and so forth but as of right now I can just Park is the only Hoover very fire lit works was air assembly and people speaking is the only language it compiles into their assembly I mean I just finished their assembly like a month ago so I wouldn't expect anybody to do anything all right any questions Before we jump into an example a quick question I have is is this like a passion project for you are you funded by by an entity I mean started out as a passion project but actuation Foundation gave me a small brand so I'm kind of working on was the help of the theme foundation excellent wholesome affair all right so let's do

so I give two examples prepared the first one is air script for MinC calculation which is very simple I think most of you are probably familiar with what it is and then we can go into something more complex which is a si Prakash function and I think we should have enough time to cover both so but most been probably bit more time with MinC just to get the concepts down okay so this is you know my MC completion you know you take the current stage raise it to the power of three and you add around constant to it and you know this is the current state this is the round constant and this is how you get the next date and this really translates to just having one dynamic register and having

one static register and you know for our example we're going to use a few parameters so we're going to say that our input values so you need to start somewhere you need to start cubing something so the input that we can start with is going to be three we're going to use a very simple cycle for round constants is just repeating one two three four and we have a very short vacations with maybe 64 steps and then we're going to use a very small field it's going to be a 32 bit field first it's actually the size of the field doesn't matter that much you can have a 32 bit field you can have a note six bit field there are some limitations like if

you use a 32 bit field I think doing anything that has to do with elliptic first becomes very very difficult but from a security standpoint you can have as long if you don't really need to do anything with other features you can use a 32 bit field for example and still kind of get away with okay so if we run this computation using this parameters we will generate a look like execution trace like little platelets so you know you can see the sequence of four values repeating here and you can see what's are doubtless three you know but qubit add this value so it's actually sorry works like this and it works like that so it's fairly straightforward so let's do this using air script and I'll be sharing my screen

here but if you guys so the project the github project that I kind of shared has basically this project and I'm gonna show how to use it but if you want to kind of follow along and write it on your machine you're more than welcome first thing let me see can anybody can everybody see the screen or should i zoom in I can see it okay oh also I wanted to say something if anyone has any questions while bobbin is speaking just stick them in this chat notes because will like check those out in a bit forgot to mention that before alright so the way you write arrow

script is first you say you kind of do it define a start so it the way you do it as you type define and give it a name and you would say let's say and we need to give the modulus to the field so we're gonna use this very simple modulus so this is basically we've created the start saying our start is gonna be in this field with this modulus the next thing let's define the constants so we're going to be raising something to a power of three so we're gonna have our let's say I'll call it alpha and I'll

saged in that half it's gonna be three the next thing we need to define our the static is the static register or our round constant so let's say so we just pass in the round constant or our we need to actually do this so basically we define how our static register is going to be generated the next thing we need to specify so we have a single input so we're going to say and it's going to be

a secret input and we're going to call it start value and it's gonna be a field element and it's gonna be just one field element so where we don't have two registers or anything so we only have one element that we need to pass in as a start as a start value and then we're going to define our transition function that's kind of the next step so we kind of set up all their you know properties these properties but now we're going to define the transition function and we all we have register so just say transition one register and the way we can kind of read the inputs and this is a bit tricky but

for me for mmm you see example is going to be simple but boom needs to somehow specify know at which point to read the input and the way you do it is in our script live is there for each loop and we would say for each start value we'll do the kind of this set of missteps the first thing we'll need to do is initialize our execution trace and this is kind of the first step of the execution that happens and we would say you know it just yields start value so the first step is gonna just initialize

itself to the start well that we've passed in is an input and then we would say four four steps from 1 to 63 so we're gonna run for 63 steps 64 including the first you know step zero that we initialize to which has been a say our competition's going to be equal to the current state and one thing no kind of every transition function and tradition constraints has an implicit implicitly two variables passed into it it's the transition module actually has only one variable passed into it as they payable dollar sign R which basically holds the current step step state of the computation and there is also dollar

sign M which holds the next state of the computation but it's only accessible in transition constraints but here we would say we will take the current step and we're gonna raise it to the our power of you know alpha which is 3 and we're gonna add our own constant to it so this is the entire transition function there isn't much more to do and then we need to define our transition constraints as well we have one constraint and this constraint is gonna basically say for all steps because it's it's not really doing anything special it's just

taking the next step of the commutation and subtracting from it the kind of tradition function evaluated in the previous step so we can just say for all staff to do the same thing and it's going to be enforce that transition of our current state is equal to our next date and you know on the background all the data just says you know run the transition function and then subtract the results from the next state now I went through this fairly quickly does anybody have questions or is anything specific I could talk about to make it more clear all right title from 1.63 method in gentle I have seen two-dimensional

inputs arrays not not one-dimensional so we could set a set of inputs for one start with your element yep yeah I should probably just mention this so there are several types so there is a field element type and then there is a vector and the names of matrix and the vector is just the way you would expect it's a sequence of

values in the array of values in the matrix is a 2-dimensional matrix so your variables can be either single field elements or vectors or matrixes and you can do arithmetic operations with them and have just as easily so you can add two vectors together and that would be element wise addition you can answer me to exists together and that would be a nice addition as well you can multiply matrix with a vector and that would be kind of matrix multiplication and all kind of comment on that in the example as I didn't have function I think it would be actually work with vectors there so it would be natural place to cover there but yeah so there are those three about three times three basic

types and then you know the arithmetic operations are just addition subtraction multiplication division and vector or matrix multiplication is a separate medication okay is it just index sugars or not just syntactic sugar so you can now express it as like and that's how I actually started out when you know I try to first write the air for let's say Poseidon or rescue card front and I started out just having simple arithmetic expressions but it just becomes so cumbersome when you do need to do matrix multiplication for example just describing that as individual statements becomes very cumbersome so that syntactic sugar that

and then just translates into you know like individual thank you all right so this is our MinC kind of air for MMC and just to show how this works but me later what I've done before I can run this example and let's say we want to start with value three right so if we run this I probably miss type something somewhere let's see I should save it first you

that's true I didn't close something I have an extra well luckily I have an example say that should work here's what I screw up maybe you don't have to cycle key word back then maybe well I mean that mistake somewhere but

so this version works let me kind of do it again so this is our execution trace and we can see our dynamic register here so air script on the background builds several static registers that control the flow of execution to help handle is execution this is our dynamic register that we defined explicitly works sorry static register that is the cycle of once with before but there's people actually built three other static registers the first one is where the inputs comes from with so it you can see the value is V it's rotated here and there is a reason for that but I'm not gonna get into it right

now but basically this is this is the register that kind of where the inputs would go will go in and this register another static register that gets generated it's just kind of a switch register that I kind of explained the medic switching so here it says you know at this point you need to read the inputs and at this point you apply the transition function and this is kind of the inverse of that register it's well you can do it in theory only was this register but this actually makes it simpler if were computation because the trace for the static register is very easy to generate but complicating the transition function constraints was you know additions and

subtractions sometimes may not be worth it so in this case I just generate another register it's a little bit but here's our trace I mean if you go through this you should get to this and this is kind of my separate validation I ran I mean my MC function separately outside of start just like a simple no function written in JavaScript and then should resolve to the same value we see we get to the same value in both cases we can actually run in for let's say multiple values so let's say we'll run it for three and four you so now her execution traces down below them because we do 64 steps for each input and you can see for example that this register that kind of reads the

inputs you know here at step 63 and it was equal to 4 so like it gets to this value and then it resets and now runs with the value of 4 as the transition function so if we did it correctly no the first one at step 63 was this and then the correct value at the end is going to be this I am it would be better or worse to have one long column as opposed to two columns if you have two inputs it's easier to mean you can you can have multiple input so in this case we'd have

a single input so in this case we define a single input if we had defined two inputs we would have two columns for input so each input gets a separate column and you can actually provide like in the way here that I've provided three or actually two values as an input here you can for each of the inputs you can provide and it's an array of values so to say so [Music] I'm not like if you had different inputs I don't think it'd make sense to combine them in this register but if you have same input can it can take a mini values

and that's why you need a single register of to represent all of it because one question if we set three and four does does a check at border step the transition constraints or not it does not but that would be handled by boundary constraints so when you generate a proof so this this step just generates the execution trace there is another step that will generate constraint evaluations B from this trace and then the the other part that is I'm not kind of showing here is that to

generate the proof you actually need to have boundary constraints because just running this kind of having execution trace doesn't give you much but what you would do is once you have the diffusion trace you would say a boundary constraint let's say a boundary constraint is that at step 63 the value of the register mean you know is equal to whatever this is and that's step one 27 at is equal to this and this way you know you you can convince somebody that you've ran the computation for 64 steps and you got this result but that's that Bradlee so like when you generate the proof you would say you know for this computation my assertion and in ghent

park boundary constraints are called assertions you would say the assertion is that the institution trees has this value at this point and at this point in execution trees if I want to take this constraint system and deploy it on a theorem does does your software generate a small contract for me it does not you know generate a smart contract I mean it's not something I've been working on so far I kind of mostly been working on the air spirit but I think the smart contract would not necessarily be specific well you can make it specific to your computation but it would be more of a verifier you need to have a verifier that would take the result of this and then I don't think you would

want to generate execution trace on there as a part of the if you go smart contract you would want to define somebody generate the truth so I think it's a bit different there is probably a way to think about how you can create a smart contract out of it but I haven't done this far yet and if we were to go down this route um with would it be a different small contract so train system yeah so if if you so let's say a verifier right so every time you define a computation it has some specific parts to it so the contract would be different for like you

know mean MC versus the rest reverse is like American branch proof or whatever they would have different expectations so the repeat ization would require a different smart contract so you would not be able to have a generic I mean maybe no I don't think you would be able to have a generic and maybe me I might be wrong with that but that's kind of my thought you'd have to unchain describe the different rational constraints you use and how they apply like you're not sort of serialize that as part of your problem description which is like which might well be very expensive yeah there is a like one of the things that I've been thinking about and is like you can

create a stark that can no interpret the given very simple language for example so you can have a smart country that it has a single start which you can feed in a kind of like a let's say some language that does additions multiplication and so forth but it would be slightly different from this this this kind of describes the execution trait like the computation itself and there you would have a computation that can verify other computations so there's a way it's interesting way to think about it but I don't think you would necessarily be able to build a generic start a fire and it was at this point where you come on things like IV see a friend is verifiable computation I think there is

a paper on this but no implementations it wasn't efficient enough I can try to put up this interesting so Michael from Stockwell and sent me a private note I'm I think it's quite interesting so he basically told me that you know the question versus doing a single long column versus two shorter columns if you use two columns the verification is a bit more expensive but I guess the proving time is less expensive and vice versa if you have a single column then the proving time is more expensive but verification is a bit cheaper yeah I think that's that's fair I think the

question is like how many inputs do you have versus at least the computation that I've been working on so far they don't have a lot of inputs and usually those inputs are you know maybe like limited to no like let's say half a dozen three dozen of different inputs each input again can be like it and I really sore necessary values so and maybe if you have a lot of inputs it might it makes me it might make sense to optimize it even further therefore the verifier but I think at least was it like a small number of inputs the very fire like there's almost no difference it also has a complex difference on proof size like we'll use one or two registers these two registers your degree halves and then you have potentially one last round of fry which

could save proof size we've also added one more Oracle which could then increase proof size so it's like so actually that's that's a very valid point and another thing I want to say about the register the input registers is that each register that you have and that applies to dynamic registers and secret static registers they increase your proof size so like if you're working in what's a 256 bit field every register increases your crew size by probably between 1 & 2 kilobytes so if you have just one register you add another you increase the size but there are other parts of the proof that are bigger than that but if you have too many registers you're just number of registers with dominated from size

alright should static register increases proof sized by one or two kilobytes ah it's each dynamic register and each secret static register so a public static register does not affect the proof size because you know it's communicated to the verifier and you know separately it's not part of the kind of it so that's probably part of the description of the commutation itself but if you have a secret static register that gets encoded into the execution trace and kind of becomes the part of the truth then it increases the proof size by between one and two kilobytes and that's only in the you know 256 bit fields if you feel this

role or the impact of it additional register is much smaller as well but what if your secret register is like succinctly representable well in that case you need to somehow communicate that sixteen representation to the daily fire and then it becomes not secret okay I see so that's only for applications where you care about privacy okay let me show you how we're doing with time so we have nine minutes let me try to run through the example of a site and hash function in that time so same thing let me just copy it so that I don't waste time typing it up but so

here is the Poseidon hash function this is air for the facade of hash function we use the same field now we define our we have an MDS matrix as part of the cost function and it's you know this is very simple I'm using a small field and registers actually three registers should be enough even for in a large field for like a real cost function so here we have the three by three MDS matrix it will you find we have our round round constants and there are kind of three registers so our round consensus but being a single element is not three elements and instead of like typing up the values by him you can you can have new here by hand as well like specific values of the round constant

but here in their script I have ability to just shoot around only generate from a given scene so here it's just see there are only generate them from different different scenes and it's going to be the number of constants January so you can think about this just as an array each of this as an array of 64 values in the field run see the randomly generated now as a cash purchase when we have this is a hash function that will take two values and cut them together and produce the output as its bank value and what we do here is that we have two inputs and each of them is a single field element and then for each combination of this two inputs in the transition function the first row will be you know just this two values

and put 0 is the third register so the way poseidon hash function what is it you can have two registers it will I think the first two registers are the rate and the other one is you can use as a capacity so that it's kind of be used in that fashion process and then the person who first function it has different functions applied depending on which step you are in so in this case this illustrates how you can use two different transition functions so this is a transition function for the full round while this is a transition function for the partial rod of the cash function and you know constraints are very simple they're just again for every step you just apply traditional

functions the current state and then you subtract it from the next state I know I went super quickly but anything that is specifically confusing here one thing I should mention is that this this sign is actually matrix multiplication so what we do here is that we take our vector of three registers we add our vector of you know round constants to it so it's like element wise vector addition we raise the result in vector to the power of five which means we just raise every element of the vector to the power of 5 and then we kind of do a multiplication through that matrix and vector multiplication and that's the output of

our kind of computation does that make sense or if it doesn't speak up if pnj defined somewhere else or PRNG is kind of you can think about this as a built-in function that I described it in definition of air assembly actually but it's basically appends there is no way how it generates 56 function to even see it in a kind of a tense there I don't remember the exact finish it is but there is a description of it if you interested also let you in the last like enforced three constraints what is dollar sign then dollar sign M

is the vector that contains the next state of the computation okay it's just a macro for any constraint well so there are the constraints definition has to implied variables in this dollar sign are in dollar sign em and dollar sign are contains the current step it's basically a vector so like if I go back to my presentation when I described the state of the computation right so you could have like three registers in this case and in this case your dollar sign R will contain the values of those three registers at the current step and dollar sign L will continue the value of those registers in the next step okay thanks and you said you can't can you can you

not support more than just the previous step you yes you can and ariselu actually supports this but for simplicity airstream doesn't yet because if you support more than like it's possible to do that it's a bit more complexity Emma and just haven't spent time on building in the complexity cool also this seems like really tailored to cyclical computations if I actually have to specify what I want to do each step then do I have to write this construction every time like for step one for step two or for step three um yes if you have like a computation changing from one step like if you apply

a different transition function in every step then it will be very difficult to describe this using air constraints because error are specifically tailored to describing cyclical computations that happen over and over again make sense yeah so but let's let's run this example so and let's hash to values let's say 42 and 43 so here is the execution trees we have our dynamic registers they get initialized to 42 and 43 this is the capacity register that gets initialized to zero and then it applies those transition functions you can see this is let's see so this would be our this

three registers are our around around constants generated pseudorandomly and this registers actually control the switching between a different you know so like you can see that for the first four steps we are client we will apply one transition function then for the next 50 or something steps we apply the other transition function and again we apply the first so this basically register is representation of this structure where we say for the first four steps and then force it in steps 62 63 we apply this function and then for the steps we apply this function so this is kind of this is kind of the switching register that controls the execution of different hash functions and then you

have your input registers here at 42 and 43 and you you know if you around the contraction here is my control now your result should be in this register so they align and basically generates the correct value at the end of the diffusion trace bobbin are you taking an eye on the chat because there's a few questions in there I just want to make I mean God I was not actually let me see if I can mini a bit sorry about that you see actually need to find where the child is well one was from dev I don't know Deb

did you say that out loud actually that one uh-oh saying something about IVC and I was just saying try I misread for dead results okay and even where you how to put you posted something as well yeah what do you mean by non determinist or in deterministic examples for example if we need to check that the number is zero or not zero and put the result to next registry I don't have those constructs yet I have some ideas of how to build them I think I don't think they're conceptually very difficult to do but I haven't done that yet I think and my next to do thing in terms of air script is to build a composable area

where you can import so let me actually show a slightly more complicated example I'm not going to go into details but this is how you do a miracle path verification using air script let me just copy it so I don't have to type it up so this is for example a way to do a miracle path verification in air script and you know the custom leaf registering passed there now you've passed like a multi-dimensional set of values as as one of you registered actually is true he registers the index bid is also kind of binary expansion of the index value and here you just run the Poseidon hash function and it creates sort of like I

needed things because I don't really need to know the first function that I want to write or run to do in vertical range verification so and ideally that should be written somewhere else so like my next time that I'm working on is being able to say like import aside and hash function and then it's the fright in this here you could just say go run a second hash function for this number stats it is interesting but my cup of computation is deterministic seen in deterministic examples is beautification for example if we need to split one filled element to set of bits such

things right now you will do that kind of a priori by yourself so you would like create a like in case of this example for example you one of the input is expected to be a binary expansion of [Music] index of the leaf that we're trying to verify the proof for so it's not built into the language but you can treat you kind of like when you submit it so we generate the proof you already kind of binary expansion I think it would be useful to have more complicated contracts here and that would do it for you I just haven't gotten to them yet okay and such constructions couldn't be written in air sweeps it could be add

into S cube as primitives on me yes yeah they're not here as primitives but you can emulate them it's slightly more difficult and you have to do a lot of you know maybe some bookkeeping by yourself but I think you can emulate most of the things that it's just not gonna be easy to do it and if you guys are interested I can just run this example of local proof as well so just to show you is slightly more complicated and it's going to be more registers so here I wanna like genuine the description trees for verifying that at index 3 the value of leaf is 4 and this

is the my America branch path so here's my execution trace you can see for example you know this is the these are the input registers and I'm reading in the values of the nodes in the allegorical branch and kind of this runs the cost function I mean it's quite a more complex I don't have a lot of time to explain but it like this uses you can see like it hashes you know the leaf in there and then branch from the or and leaf in the node from the branch or its opposite and then every 64 steps it figures out which one of these two is the correct one and then it continues to the next step and all of this is in the repo so if you guys want to play around

with it if you have any questions just ask you can play around with this examples very easily are there any other questions yes if not then I think that could round out the study club so thank you thanks bobbin for putting this together