Linea under the hood: from arithmetization to prover

Transcript

[Music] we can go well ladies and gentlemen good afternoon and thank you for coming so numerous to this presentation where my colleague Olivier on myself we are both a research engineer at consensus we are going to present you the technical underpinnings on the of the linear ziki roller level 2. on yeah we'll try to ask to answer all of the questions that you may have on this on this subject so here is a basic plan of the representation so first we will tell you what is linear then we will detail the

three main technical components of linear so the arithmetization the State Management on the profile and finally we will give you some of regarding the release on the coming roadmap of the linear product by consensus so let us start with what is in here linear is a level 2 ZK roll up so what is level 2zq error let us unwrap that a little bit so a roll up is a way to optimize and to scale up the ethereum blockchain so the idea is that we are going to switch from a monolithic architecture where the execution of the transactions the settlement of the transaction the state and so on and so on are all handled in a single place to a more modular architecture where you have a first block that is the execution

block or what we call Level 2 where you are actually going to execute the transactions and you will be able to do that faster than on the ethereum main net and then the proof of the correct execution of this level 2 chain will be published on verified and validated leveraging the L1 so the ethereum main net on the consensus mechanism that you can find on it so this is a global idea of a rollup there are several ways of doing rollup on the linear is a z kerulop or sometimes also called a validity roller so how does this work basically zero lab is a huge State function transfer function that is

going from a state I of the L2 you inject into it a lot of transaction so block and then you'll get a state I plus 1 on the L2 now how do you prove that you didn't cheat on the execution of this transaction that you didn't give too much or not enough money to the people involved you have here this big function the ZK VM that will be generating a lot of data that will then be used by approver to testify and to ensure that you didn't cheat on the execution of all these transactions on that you were truthful in your implementation of the ethereum protocol and then this proof which is in

let's say in size in bytes rather small and very hard to compute but very easy to verify will be published on the other one so on this theorem in the call data of a transaction from the zikariable operator to the L1 smart contract of the road app and this way you will be able to fit in a single transaction on zl2 a whole block or even several blocks of the L2 so there are many way on many different complexity for implementing Zeke rollup there is this classification that has been established by Victory a few years ago that is more or less accepted in the ecosystem on for now linear is a Type 3

zero left which means that we are white compatible or not compatible with ethereum magnet but we are aiming in the coming months to go to the type 2 which means that we will have prove the Integrity of the ethereum API and that we will have a very similar gas calculation when it comes down to the differences between the L2 and ZR1 so why should you use linear it depends if you are a user you would like to use linear because everything is cheaper all of the transactions tend to be cheaper you get more transaction in the same slice of time so you have IR transaction per second which leads to less congestion of the network if you are a developer you would like to use linear for a very easy for a few

reasons the first one is that you can use linear exactly as if you are using the mainnet thanks to our goal of 100 compatibility between zero one and zl2 on which leads to the fact that you can seamlessly reuse all your existing code either at the language level like solidity or Viper or whatever you like or at the bytecode level and finally you will be able to address all of these users on create a mutual emulation of people wanting cheaper on faster transactions on top of that of course you will get integration with the whole consensus ecosystem so metamasking for our profile and so on and so on so what are the challenges on our side

of developing and implementing such as ekvm so first thing first is the evm so the ethereum virtual machine is composed of many parts related either to the stage or to the free comparison and so on that are strongly careful and that are quite interdependent which is sometimes hard to modernize in a cryptographically provable way second there are many data in the EVMS that are making it very hard to actually arithmetize or to express in terms of eer constraints the auditability is another key point you need to be trusted to be truthful for your community so you have to to get an auditability and to get audits for all of your software

pieces and finally the performances especially the the creation of the proof is something that is computationally very expensive and still you have to do it quickly so that it is done in the the time of of the generation of a block on quite cheaply in terms of gas so that you do not pay too much gas on cl1 so to see how we addressed all of these points I will now give them actual Eva that will be presenting user main technical points of linear thank you Franklin um all right so I'll give a bit of I'll try to give a bit of an insight into several of the components not all of the components that go into linear on the evm side and the arithmetization and

prover side so I'll be talking about the Earth monetization itself the way we represent the state and also the prover so let's start at the beginning so the arithmetization is really comprised of two uh essentially independent components the first one are the constraints so this is The Logical heart of the arithmetization constraints are just equations and to produce an arithmetization of the evm is to produce a collection of these equations so a collection of such constraints which should have the property that when one is able to satisfy all of these constraints simultaneously it should be basically equivalent to having executed a collection of transactions a block of

transactions basically okay and what does it mean to handle these transactions well we want to be able to do the entire life cycle of a transaction of a batch of transactions starting with the transaction itself which is presented to us in the standard rlpis formats in which it is also used in mainnet decoding this extracting the fields executing the evm bytecode if necessary if it is a call to a Smart contract let's say and finally finishing with producing the transaction receipt which is associated to the transaction and all of this of course for a block of transactions this is not all because the evm is not just a virtual machine that runs in The Ether it is connected to a state

so the arithmetization also comprises this part which is we need to connect be able to read and update that is we need to connect with the L2 State and this too must be part of the arithmetization and finally there are certain cryptographic operations that sort of live in a world of their own a class of their own which are ubiquitous throughout the evm be it hashing such as sha3 Chateau Etc or pre-compiles and this is a whole different part of the arithmetalization which I will not be talking very much about today okay I said the arithmetization is a collection of constraints of these

equations written uh as equalities between various uh variables in some sense so the link I posted here is a link to the spec which we published recently and which purpose to be a full spec for the evm so all of the by all of the op codes are handled and all of the sort of strange behavior of the evm itself but the other part of the arithmetization is Trace production because these constraints these equalities they apply to something and that's something are traces traces are these very large matrices which are compiled as an execution client in our case Basu is running on these

transactions and as I said they are the recipient of the constraints constraints applying to these traces and yes so just to give you an idea so just imagine you have these extremely large matrices with in some case maybe 100 columns or maybe more and that are extremely deep on the order of millions of rows and they are subject to to these hundreds if not thousands of constraints which are compiled in the specification so the evm is a very complex piece of software of it's a complex architecture and we are sort of forced in our

arithmetization to break apart the complexity and thus the itemization is really comprised of many different chapters which each represent a sort of a semi-autonomous and semi-independent little box which sort of um Corrals a certain collection or certain section of the complexity and these boxes though they are somewhat independent they are actually connected to one another as represented in this diagram by these arrows which are these cryptographic arguments to sort of transfer data and these lookup arguments and uh another part which I didn't depict here is the offloading of certain parts of the arithmetization such as Computing pre-compiles Etc so how does one go about now that we've

broken up the complexity into little chunks how does one go about actually writing a part of the arithmetization a module as it were um we are thankfully in a position where we can sort of almost forget about the fact that we are handling cryptography in the background so all several at least some of the sort of um standard tools one would expect when writing a program actually available to us in this sort of pseudo language or sort of um not Zulu language but more like a high level uh language we can seamlessly seamlessly do conditional branching we have a sort of a primitive type system we can do function calls and we can do sort of internal consistency arguments which

basically mimic memory uh for certain parts of the evm that may impact the execution at various points in times you can think of storage you can think of ram itself you can think of warmth of addresses or warmth of storage Keys Etc and the main point I want to make is that when writing such a module we are in some sense writing something which is removed from cryptography everything we want to do has a cryptographic equivalent on the right hand side and concretely we use this lisp like language which allows us to succinctly write these constraints in this proof format that we use which is this algebraic intermediate representation

and there is a very tight connection between the spec itself and what is actually written in this lisp in these constraints file files and then this is also used as the sort of input to produce the actual constraints of sort of compiled constraints that we don't want to have to deal with on our end directly at least okay let me say a few words on the state manager so as Hong Kong said we are not a type 1 ZK evm we don't abide by the same representation of the state and concretely uh we are we have two major differences uh in the state itself we

substitute ketchak which is uh sort of very difficult to Earth sometimes with something which is much easier to arithmetize and for which we've already done previous work we used the mimc hash function family for which we have extremely efficient proving schemes the other major difference is that we don't represent the state as a Patricia Merkle tree but rather as a sparse Michael tree and the state manager is a component that basically handles the sparse Merkle Tree Side of Things and it provides the optimization so the ZK VM with all the data it needs such as nonsense balances etc etc and it provides the prover with the

justification for these data such as merkelproofs merkelpass so concretely though there is still a Patricia Merkel tree in the background so as I said earlier we're using best suicide execution client and bessu uses the standard ketchup based Patricia Merkel tree uh we have a plug-in uh I didn't change the slide but based on Bonsai we have a plugin and that converts or sort of produces these try logs that are then passed on to the state manager so all the accesses that are made to the state all the changes potentially that are made to the state are then passed on to the state manager which produces the data which will later on be required by the

approvers such as all these medical paths I was talking about the advantage being that this representation allows us to easily integrate into the prover itself in the end another advantage of this is that if need B in the future we could also replace mimc with a different hash function if we find something that is more efficient maybe and doesn't compromise security okay let me quickly finish on the prover so it's kind of strange to do a very short part on the proof because approver is an extremely complex piece of uh the entirety of linear because the prover is tasked with sort of reconciling

everything so I presented these two main boxes up to now which is the ZK VM itself which is the sort of execution logic of the evm I talked a bit about the state and accessing data and updating data but there's I mentioned a few times there's also the crypto side of things so all those cryptographic Primitives that are really nasty to arithmetize the prover all of these comprise the arithmetization as well as the connections between them and the goal of the prover is to produce these succinct cryptographic proofs that testify to the validity of these boxes individually as well as the connections between them there are issues though

when we run the zkvm we very quickly produce traces that are absolutely humongous in size so the number of cells n will be on the order of trillion billions right yes on the order of billions so it's extremely large and it will not fit into any L1 compatible proof at least naively furthermore the proverb sort of mixes or at least what is given to the approver is a mixture of all kinds of different con constraints we have permutation arguments we have evaluations we have a global evaluations local evaluations we have look arguments we have range proofs Etc

so the first the the solution that we have which is this Vortex proving system is to sort of first do a first compilation step where all of these disparate kind of constraints are converted into a single kind of constraint single kind of evaluation constraints this is the step we call Arcane it's a sort of reduction step it usually blows up the size but at least it produces uniformity in another sense and we then have the Second Step which is a compression step this is where Vortex enters the picture which is uh sort of simultaneously a scheme for compression but also a hash function and the argument is basically reduced to an argument that is of square root of

its initial size original size and this process can be done many times over the reason being that verifying this compressed proof is itself doable in a circuit so we can sort of have this self recursion mechanism where we feed we have this feedback loop where we can do this step many times over sorry okay and we basically continue doing so so we can't do it uh in infinitely often at some points the benefits die down die out but we do it until a point where the proof becomes manageable in size in the sense that we can prove we can verify sorry we can produce a proof which is L1 compatible so we can produce

a plonkish style proof for the entirety of the argument and at this point we are able to publish it on mainnet and to have the smart contract verified so this will be it for me I'll hand it back to Franco [Music] coming monsters so for now since the general is a needs we have been deploying linear on the latest net since March the 28th we have actually a public beta on the early testnet on scene during July the elephants we actually have deployed linear on the main net where we are currently onboarding our partners so that in the coming weeks when everything will be

ready we will be targeting the communication more towards the end users and the other apps so that when they're coming they will have a ready-to-use ecosystem with a lot of services that will already be available so in the coming months or semesters our main goals are first to finish implementing a hundred percent coverage of the evm then work on the open sourcing of the whole software pieces of linear for now only the smart contract has been audited and published on the free license and we intend to do the same thing for the other pieces that Olivia just presented on fight finally on a slightly larger time time frame we are working towards the decentralization

of linear which means uh welcoming privately owned sequencers on proofers onto the linear L2 on here are a few links that may be of interest and if you have any questions you are more than welcome thank you [Applause] yeah someone has any questions okay sounds good thank you foreign [Music]