Improving Performance of Provable Computations Using Rust | Devcon Bogotá

foreign [Music] thanks all for coming in today and in this talk we are going to be talking about how we improve the performance of probability computations using rust and specifically how we implemented the carobm using rust so okay let's go first I want to give a little worse on who we are we around the class Lambda class is a lesson base so for company and it's in the industry a more head interiors and yes basically we love soybean difficult problems so if you if you have any problem just give us a call and okay let's go straight to to the talk and the first thing I want to start with is to give a little bit of context and talk a little bit about ethereum and as you all may know ethereum is a decentralized network meaning that when you run it on suction the transaction is not run in only one computer but in every computer that forms part of ethereum of the network so that's really cool because the verification of the transaction does not depend on only one computer on a centralized entity but on every computer inside the network but it comes with a downside and the downside is that the computation capacity of the network depends of on your slowest note so we have in a situation that we have a high demand of running transactions and our computation capacity is limited by our slowest low so how can we solve this problem and here is where starnet comes into play starnet is a secret roll up and what rollapse allows us is to run transactions of chain then make a batch of intersection and send to ethereum the update State and what CK adds to roll up is that we can run the construction of chain generate a proof of the Integrity of the execution of the transactions and then we send to ethereum they update the state and the proof of the computational integrity so then on chain uh the proof is verified by a verifier and that verification is running all the computers inside ethereum so well and the coolest thing about this verification is that the verification cost of the proof growth logarithmically with respect the number of transactions inside the batch so as the the cost of verification is distributed between all the transactions including the batch as we add more transactions in the in the batch the cost per transaction the average cost per transactions goes to zero so ah yeah here is a slide that I was supposed to to say that because of verification grows logarithmically and with respect the numbers and section and yeah if we tend to Infinity if you take this one extreme and we tend to Infinity the number of transactions inside the batch the cost the average cost per transactions go to zero so okay we say that in stagnet we can generate a proof on the execution of our transaction but what kind of proof well it's a series proof and specifically a stack and to your knowledge allows us to prove the veracity of a statement without rebuilding anything beyond the fact that the statement the statement is true and in this specific case Stacks allow us to prove their computational integrity of the transaction that would run off chain we are having to run it all again so this is kind of a game changer because before serial knowledge the only way we had to to prove the rest the computation Integrity of a computation was to run that computation ourselves but with with your knowledge and stacks now and untrusted entity can run transactions a generator proof on the Integrity of that execution and then the proof have to be verified and we can be sure that everything is okay so okay how do we write a program that is a probable meaning that its execution can be can be proven the Integrity of execution and okay we have Cairo and Cairo is a primary language a specific design to doing this when we we write a program in Cairo it's run in the Caribbean and that Cairo VM executes a program and also generate a trace of the execution and that Trace is then is going to be sent to approver and generate the start proof and that's that's that probe is going to be verified by a verifier so okay how does the Caribbean works and now Federica will guide us through the internals of the Caribbean so ferrica soldiers well now let's talk about about how the Caribbean works well you already know how a virtual machine works basically you write your source code you compile it and then you use the virtual machine to interpret that compile code and execute the instructions but what sets apart this current Bureau machine is that it also generates this Trace that can be used to generate the proof so let's go a bit into the architecture of the career virtual machine well first we have the memory model it is the right one's read-only memory that is divided into different segments these segments have a known size at runtime and once we finish the BM run we these segments go for a relocation process and we end up with a continuous memory so well the segments consists of the program segment which contains the code of the program the execution segment which gets filled up as the VM runs the built-in segment which we'll talk about later and the user segment which contains structures defined by the users such as arrays or dictionaries well let's explain a bit about this provocation process the first step is to assign a size to each segment for example the segment serial has five elements so it has size 5 and then we will use the sizes to assign a base to each segment what when you say with base is that is the first address of each segment in the relocated memory so for example for segment one we have the previous segment base is one because this is the first segment and we add five which is the size and we get six now with this space is calculated we'll proceed to relocate all the addresses we'll do this by adding the base of the segment with the offset of the address so for example here we have the segment the address 0 0 the base of the segment 0 is 1 and we add 0 and get one we'll do this with all the addresses and also with the addresses that are contained inside the memory for example you see here that we have two zero and three zero and they both relocate to nine as the base of the segment two and segment three is nine and this is how the relocated memory looks like it's a set of continuous addresses with elements but now let's talk about the registers Cairo has three general purpose registers the first one is the program counter which iterates over the program segments and points to the next instruction to be executed then we have the frame pointer and allocation pointer in execution segment the allocation pointer will point to the next and use memory cell while the frame pointer points to the current frame what this means is that when we want to execute a chiro function the frame pointer takes the value of the allocation pointer and remains constant while the allocation pointer keeps increasing as we add elements into memory and when we exceed this function the frame pointer will change its value this is how the VM operates this is the main execution Loop we first get the next instruction we decoded we compute the operands then we add the current register values to a trace and then we update the registers so okay this is how the trace looks like it keeps track of how the registers change for the execution of the program and it also goes through the same relocation process as memory well as we can see the size of this Trace will depend on the amount of steps that a chirop program takes so if a chiral program takes a lot of steps this Trace will get very big and will take more time to generate the proof so sometimes there are some computations which are expensive take a lot of steps but maybe the information provided by each of the steps is not that relevant for example if we want to compute a Pederson hash this will take many many steps so in order to solve this what we have is oh sorry we have built-ins built-ins are low-level optimizations that are integrated in the core Loop of the VM and they allow otherwise expensive computation to be performed more efficiently and while each of these segments each of the built-ins have a segment in memory okay but where do they come into play well we see here that we have our main execution Loop and we have this the GS operands added and what this means is that sometimes we might want to compute an operand and we can't really compute it directly and we'll rely on some deduction rules example here we have the Paterson built-ins Auto reaction wall what it does is it takes the two previous values in memory and computes the patterns and hash of them this rule comes into play when the address of the operand that we cannot compute belongs to the built-in segment and that built-in has the anal to the action rule so what does what this allows us to do is for example here we want to compute the hash of X and Y so what we do is insert X and y's memory and then we ask for the next memory location as we haven't inserted anything into this memory location we won't be able to compute the operand and we will fall back on this deduction rule that will be the one Computing the hash so we computed a person hash but there is no sign of the computation in the chiral memory or the steps or the trace another feature that Cairo offers are hints these are blocks of python code embedded into a career program and they allow a python context to access the BM State and modifier also access local carrier variables and can communicate between each other for execution Scopes what we see on screen is the unlock function from the common Library this function is commonly used to generate arrays and what it does is it creates a new segment and it inserts it into memory so we can use it from Cairo we mentioned execution skills these Scopes are a stack of dictionaries that can hold variables that are created inside a hands these variables are not seen by Carol just by the hands and this can be created and removed inside hints and multiple hints can access the same scope for example this code is a bit long but we could just focus on for example we first enter the scope with an N variable then we use that n variable we modify it for by situations and then we exit the scope deleting this and variable well so now let's talk about how we implemented hints in Cairo RS that is our implementation of the VM well first why we chose rust we chose Frost because it offers very good performance memory safety guarantees and it also has an amazing Community well our first iteration of hints entire RS was basically to implement Ros functions that would imitate the behavior of hands and match these blocks of python code to our sense for example the constants we see here are the blocks of python code and this is again the example of the alac function this is the block of python code and this is how we replace it with a rust native function well this first iteration had pros and cons on the cross side we had that it was very easy to implement as we didn't need any new tools and it also offered better performance as calling functions within the BM was much faster than compiling and running code during the vm's run but on the con side is that we needed to watch out for changes we first applied this to the common Library so if a common Library hand were to change we needed to change our implementation in order to keep supporting it and it also wasn't really extensible as if we wanted to support more hints we'd had to code it inside our BM so as we wanted to support user defined hints and we also wanted to integrate our VM with the current python infrastructure we decided to go with the next iteration that consisted of integrating python with RBM in order to achieve this we used the create Pi u3 it is a creative provides rust bindings for Python and it allowed us to share our BM state with the python context I know that python context to modify RBM and also allow us to define a strict interface between our VM and python by using pi classes and Pi methods Pi classes are brush structs that can be interpreted as python objects and Pi methods are Russ methods that can be called from within python so let's take a look at the code and well this is how we allowed hints to modify memory we created this Pi memory object and when we want to get an item what actually happens is that we call our VMS memory and we use our rust get function and the same happens when we want to set an item uh well how did we allow it to modify chiral local variables and carry local variables can be accessed inside Hands by writing ideas dot the name of the variable so what we did was override these IDs objects set attributes and get attribute methods so when we want to get an attribute we are actually calculating the value of that attribute inside during the hinge run and we want to modify a local variable we calculate its address and insert the new value into memory well the next step was execution Scopes in order to implement this we took advantage of the local python variables so what we did was take our execution scope variables convert them to python objects and inject them into the python locals and when the hint was done running we extracted the python objects from the locals and inserted them into our execution Scopes this is how executing a hint currently looks like we first take this to our local variables and inject them into python locals we create these Pi classes that will allow hints to interact with our VM and insert them into globals and then we again retrieve these values from python locals and update our execution scopes but well how does this all look like we we created a separate grade for this called Cairo RS Pi in which we instantiate the VM and we execute the Cairo methods debians methods such as initialization running instructions and when a hint cannot be run by our VM we fall back to this python hint execution so with this approach we were able to maintain the rest functions that we created in the first iteration and also add this python integration so when you use the common Library hints you can still enjoy the boosting performance from the plus native functions okay awesome thanks okay um well in the name of our talk is how we improve the performance of private computation so showing some Benchmark with some must and here we can see how our implementation of Cairo Cairo RS is um about uh 100 100 times faster than the Caribbean using the C python interpreter and about 20 times faster than the Caribbean using the Pi Pi interpreter and the coolest thing is that the our implementation is 100 times faster than a car VM using CC python but also consumes half of the memory and our implementation is 20 times faster than the Pi Pi version but consumes 12th time less memory than Pi Pi so yeah it's really cool and yeah okay I hope that standard development developers Embrace a Kairos and that helps building and accelerating the ecosystem so yeah that's it thanks for being here questions we still have time for some questions so we have our Volunteers in the room just raise your hand if you have any questions compliments for the great presentation um hello hello um well I've seen you before um my question is how stable is this is this available to use right now uh or if it's available if tuition right now yeah yes if we are still a developing the integration with python but yes Kairos is a is open source and you can use it but we are finishing I think in maybe two weeks and they implement the integration with python so after that we are going to start a testing it and making a faster so we can be sure that everything is okay and then where it comes to be start using it in production so we are really excited we let them speechless about the representation well maybe big round of applause thank you so much for the weekend Herman