STARKs: Verifying Computations Faster than Re-Executing Them - Christian Reitwiessner

this I will try to explain to you how it is possible to verify the correct execution of a computation without re executing of course just so a computation is in this sense a fixed procedure that runs on a certain input and and results in a certain output and the the computation itself is deterministic so whenever you run it on the same input you always get the same output and of course the obvious way to do that is to just run the program again and that is what is currently done in blockchains if you sink a blockchain you just rerun all the computation that the miners have already done I mean you don't rerun the search that is done in mining but you rerun executing the transactions and on the horizon there is there are new research results which might allow you to do some things which then result in checking a computation and being reasonably sure that it's correct faster than re executing them okay and as an outline of this talk I will start with explaining why that might be useful for block chains already started a little on that and then there are yeah basically two popular approaches to that problem one of them is called snark and the other one is called Stark and they share some properties and they tend in some other regards they are fundamentally different and since the world already talks about snarks I will focus on Starks for the rest of the talk and yeah I'll try to explain how they work and the first component of Starks are running the computation and generating something that's called a computation trace and this is then encoded into a polynomial and the second component is something called IO PP Interactive Oracle proof of proximity first two already board can understand that and this is used for low degree testing and then in the end we'll see how you can add zero knowledge to the whole thing I am in no way responsible for any of the results explained here and this is a long line of research that started in the 90s and the names here are just some of the contributors and I already warned you that I will leave out some details quite a lot actually but I hope it's still you can still see the the main breakthrough ideas there and I yeah I already have warned you that it might be a little dry so if you have any questions in between please ask - - yeah make it a Biddle but let's try okay when I find blockchain when you look at a blockchain it always starts with a block with a number 0 which contains the Genesis state which might be completely empty or contains some pre allocated funds and then you add a new block and this block number 1 then contains a list of transactions and sometimes also something called a post State Route so this is you you take the the state of the blockchain - so kind of the account balances and create a local tree of it and in in the block or in the block header you store the root hash of that Merkle tree and now assuming we have this technology and it is practical this stark technology this verifying computations without reacts accusing them or faster than we executed them then we might be able to attach a proof to that block which can convince a verifier that the transition from the Genesis state to the state and block 1 by the given transactions was done correctly so that this post state route is the postage what you actually get when you run the transactions and but we assume that it's possible to verify this proof without actually react securing the transactions without actually finding out the effect of the transactions and so if this block comes in and you want to verify it you just run the proof you don't react secure the transactions and this is little boring but it gets more exciting when we add block number to this block number two looks similar it also has transactions and it also has a post state route it also has a proof but now the proof does not only prove that the transactions took the state from the state in block number one to the state in block number two but it also proves that the verification of the proof in block number one was done correctly ok so this proof does not prove that the transition from Genesis state to block number one was correct it only proves that the proof in block number one was verified correctly and that's a big big difference because especially as the blockchain grows the amount of work that is required there stays the same so we only verify the transition from block two to block 3 and the checking of the proof in block - we don't verify the checking of the proof in block number one and the transition from zero to one so what we only do is we have a proof that the state transition from the previous block to the current was correct and the previous proof is correct and this means that syncing a blockchain if you have the technology then seeking a blockchain just means download the state and verifying the proof in the highest block that's it that's all you need to do so you don't need to rerun all the previous transactions so yeah and to warn you so this does not yet work in practice and it does not solve the problem of data availability and it does not solve yeah you only know that the block that you have is correct you don't know whether it's the highest or the one with with the most proof work so that that's similar to data world ability so somewhere out there so you might be disconnected from the network and the rest of the network might see a much longer chain and you're on the wrong block that's something you can't do here you can only see that the block you have is correct and the whole history is correct okay so that's what might be possible in the future and now how does how do these yeah computation verifiers work almost always those start with something that is called an interactive protocol in the native protocol you always have two parties one party or yeah you might also have more parties but most of the time you have two parties one of them is called approver and the other one is called a verifier the prover is usually much more powerful than the verify so think of that prover is someone who creates a transaction and the verifier is just a smart contract on the blockchain so the prover has a tremendous amount of memory tremendous amount of disk space access to network and verify is extremely limited and they exchange messages approvers enter message the verifier verify reach that message answers with her own message prove a reach that message again answers with with her own message and so on and the verifier is allowed to use runs and so on correct input so think of it as for a fixed computation input and output pair and this this is correct if the computation on that input yields that output if that's the case then the verify has to accept after the exchange for messages and on incorrect input if the computation was wrong then the verify has to reject with high probabilities the verify uses randomness so we have to say with with high probability here and not with the certainty okay and you might already see that this is not really suitable for block chains because I can't really exchange messages with block chains I mean I can but it would be a hassle because it takes multiple blocks and so on and because of that interactive projects can often be made non interactive by a technique called or named after Fiat and shamea we might take a look at that later okay and now let's compare snarks and Stark so just name the the acronym snarks is succinctly non-interactive arguments of knowledge and Starks is six inked arguments of knowledge although Starks are also not active most of the time but it doesn't really matter what these acronyms mean the thing is that the proof size so proof size means the length of the exchanged messages and usually when they are non interactive this means the prove it just sends one single message to the verifier the verifier processes this message and says I accept or I reject and since it's just a silly message it's also called proof for snarks they are very short so something like 188 bytes mostly regardless of the size of the computation and for Starks they are longer currently in the range of 400 kilobytes something like that snarks are not run once this means snarks require a quite costly setup phase but the setup phase has only has to be done once for one type of computation and then it's extremely fast so you have to invest a little in the setup then you can repeat it multiple times and for stocks that's not the case there's no setup so it's it generates a little slower but you can do it multiple times on different functions transparent that's quite important that means that for snarks you need random numbers and you need to keep them secret so in this so-called trusted setup setup face that you just do once in the beginning random numbers are generated and they have to be kept secret or you have to pick it secret kept secret at all cost but they are not lead needed anymore later so you can also destroy them that's why you might have seen videos of people drilling holes and their computers and things like that for starts that's not the case anything that happens in Starks is public so of course Starks can also have zero knowledge but so there are private parts but you don't need this trusted setup you don't need the the toxic waste the random numbers that you need to destroy and snarks rely on some assumptions about cryptography for example that elliptic curves are secure and also something like knowledge of exponent which is in practice not true anymore once we have scalable yeah scalable actual quantum computers so because quantum computers can break elliptic curve cryptography for Starks that's also better because they only rely on the existence of collision resistant hash functions and I think this is something that is reasonably true for yeah quite a long time okay both technologies here and many others start with encoding computations as statements about the Equality of polynomials and this is so encoding computations as polynomials is quite useful because you can easily check whether two polynomials are equal or not by evaluating on them on some points and the reason is that if two polynomials are not equal then they are different at almost all points so in the rest of the talk we will always talk about polynomials over finite fields and this means you can actually have numbers there so there are two different polynomials are only equal at a number of points that is equal to that degree and different all other points of the fields and so the problem is that we want to avoid the proof of having to send the full polynomial to the verify because the polynomial is usually rather large and we want the messages to keep small because these messages are stuff then it's then to be encoded into the blockchain so the verifier wants to check that two polynomials the prover claims something about are equal and has to evaluate them for that but she doesn't know the polynomial so she kind of has to ask the prover to evaluate the polynomial for her and then check that then the numbers are equal but she has to kind of trust the prover that this even evaluation was done correctly or the prover has to convince her that she did it correctly and snarks in stark take two different approaches there snarks use partially homomorphic encryption for that and it works by the prover evaluating the polynomial at an unknown point or an encrypted point and this encrypted point is the thing that is generated during this trusted set up so some randomness that is later destroyed is used to create a random but later secret point where the polynomials will be evaluated and [Music] since so this is home morphic encryption so if the if the value at the encrypted point which is the encryption of the value at the point so if those are different then also the decrypted versions are different and because of that you can throw away the randomness so you don't need the decrypted point anymore you can just work with the encrypted point okay and Starks are don't use cryptography they just use hash functions not sure if you can test ask cryptography and here the rough idea is that the prover commits to the full evaluation of the polynomial so they take the polynomial evaluated at all points in the field or at least a large number of points and then create a moko tree of these function values and sent the root hash to the verify just the root hash and then the verifier can request the prover to send some values and these valleys then of course come with mercury proofs and the only flaw is that as I said earlier the verify has no control about how the prover actually evaluates this function and because of that we need a second component where the prover proves the verifier that this gigantic array of values she has is actually the value set of a polynomial and this is done in something called a OPP interactive Oracle proof of proximity okay so let's get into detail what is the computation as I said it starts with it starts with an input so let us simplify computations here rather strongly and let's assume we have a computer that only has three registers these registers are a 1 a 2 and a 3 the input at the beginning of computation is present in these registers at step 0 this is 1 4 and 2 and then we have a fixed program that does something on these registers so for example at step 1 we take the value of a 2 and a 3 at them and store it in a 3 and then at step 2 we take the value at register to a register 3 at them and store that in register 1 in step 3 we take the value in register 1 and register 2 multiply that and stored in register 3 and so on we do that for 8,000 steps of course the program is not a list of 8,000 instructions but it's somehow more compressed so it has loops and and things like that so the description of the program is much shorter but at every step of the computation you kind of know which operation to perform on which registers ok and yes so we have an input of 1 for 2 and the approver claims that the output is 15 334 and of course the computation is correct if it is correct at every single step and the idea now is that verifying a single step is easy in comparison to running the whole thing and now yeah we wanted to encode that in polynomials so what the prove it does is she takes the sequence of values for a1 and turns that into a function so the function a one at point zero is 1 a 1 at point 1 is 1 a 1 and point 2 is 10 a 1 and point 3 is 40 and so on these are 8001 points and because of that you can create a degree 8000 polynomial that behaves exactly as that function at these points so the polynomial at 0 is 1 the polynomial at 1 is 1 and so on degree 8000 might sign might sound a lot here but yeah that's how it works and yeah I mean in the paper they actually go to degree I think 10 million or something like that I mean number of steps of a computation yeah and we do that with all three registers and now there is another polynomial called C and this kind of encodes the the program so and it can be used to check the correctness of a single step in the following way okay so this is the first complicated formula I'm sorry about that so the computation is correct if and only if the inputs and the outputs are correct so that's something we have to check in addition and I mean output is correct this here does not mean that output and all the preceding stuff is correct but just the output and in addition to that for all X in between 0 and 8,000 so these steps we run C or we evaluate see the which is the step correctness checker and as inputs it gets X the step and then a 1 of X a 2 of X a 3 of X the values of the register that registers at the beginning of the step and the values of the registers after the step so that is all you need if you know the program that is all you need to verify the correctness of a single step and it has to be 0 and yeah we assume that this can be encoded as a polynomial since the program is finite this is always the case clear so far any questions who is already asleep good there was graphics here okay that's there's a table and has actual numbers okay let's continue so that's again repetition of what we had in the bottom the condition for computation being correct now something happens that's a simplification but you might not think of it as a simplification simplification let's see so we have these three registers and what we do so we have three registers and one polynomial per register and we combine these three polynomials into a single polynomial by just kind of stretching it so we call this single polynomial a and so perhaps it's better to explain it on the table again we build it such that a at zero is this one here this is a at one a at three a at four a at 5 at 6 at 7 and so on so it's basically just encoding the whole table into a single sequence of values and yeah so and we need this lowercase J's to perform the mapping between the indices here so and if we look at that and replace all the ai's by the single a we get this here so C of X then a at the first index I get the second index I hit a third index and then a at the first index at X plus 1 second index that X plus 1 and 13 X at X plus 1 ok question when you execute the program and you have different relatives for the intervals then you everytime have a different polynomial right so yes this is stuff a Krueger has to do and of course that has to be repeated for every single execution yes okay once you polynomial once you have polynomial so if you want this basically what you want to do it so you have to run exactly so this is so yeah this is stuff to prove has to do but that stuff the verifier does not have to do right so and the idea is verifying the computation is faster than re executing it but generating the proof of course takes longer than just reacts acute it or just executing it the downside a question little or not yet okay I will I will have an overview of the whole protocol later perhaps it gets clearer then okay and now so what the statement here that's a statement about a polynomial on the left hand side and a number on the right hand side and it's a statement at 8,000 discrete points of this polynomial 8,000 discrete input points of the polynomial and what we now want to do to get it fully algebraic is to turn this into a statement not about discrete points but a statement about two polynomials and statement about them being identical and so yeah I'll just okay what we do is so we say that the the polynomial on the left hand side here is 0 at these points and this means on the right hand side if you want to have a polynomial here at the right hand side we have to find a polynomial that is 0 at these points and that is this polynomial here the polynomial Z is 0 at exactly the point zero one two until seven nine and nowhere else and if you just put Z here then this will not capture the full polynomial here so we need to add another polynomial factor or multiply a different explanation is we take this polynomial and it has some zeros we know that it has zeros here so if we have a field that is algebraically closed like the complex number or a proper finite field then we can factor out these factors X minus 0 and if we do that then these factors we removed are Z and the rest is d [Music] yes the degree of C is higher than 8,000 because I mean if you take a look at it the degree of a 1 is exactly 8,000 and that's a argument of C so and has more stuff so it will probably be higher okay and the important thing here is that so we have the same left-hand side here and replace the 0 by a product of two polynomials and now we can say that this equality is not only hold for all X in this discrete set but for all X in the whole field so we have actual polynomial identity everywhere and because of that we can apply the stuff we talked about earlier checking equality of two polynomials by evaluating them at some points and checking that the value is the same yeah right so all polynomials here have small degree and small here means small in comparison to the size of the field so the size of the field is something like 2 to the 80 and the degree of the polynomial is something like between 8,000 and 10 million or something like that this will be important later okay now we've come unto here and I see still see some open eyes that's great because now I will describe the full interactive protocol that is run now between prove and verify and as a reminder this is the property you want to show at the end okay given so this means this is a shared input that is available both through the prove ER and the verifier C is available to both because this is kind of encoded in the program that's the the function the program they want to verify then these a 1 a 2 a 3 these are simple functions 3x plus 2 or something like that and then Z that's the polynomial that has zeros exactly at the point 0 1 2 and so on this is a polynomial of rather high degree especially for the verifier but it has a very simple structure ok the prover now computes the polynomials int these are gigantic beasts and we do not want to send them to the verifier she computes a by basically running the computation and looking at the values of the registers running polynomial interpolation and yeah that's how she gets a and then D is obtained by evaluating this expression here and dividing it by Z using polynomial division or yeah something like it was fast Fourier transform there are quite efficient algorithms to that and now the proof actually wants to send the full a and the full D to the verifier but that is way too long so we do something that is almost like sending the full thing to the verifier and it's that this is creating a miracle tree of all these 8,000 or yeah of all these values and sending the Merkel route to the verify yeah I actually we have to evaluate a and T not only on these 8,000 points but actually on way more and the reason for that is if we compare polynomials by evaluating them at some points and these these points can only be points can only be from this set of 8,000 points then they will always match so we have to evaluate the polynomials on way more points okay always match why if we only evaluate these functions at 8,000 points and assume that they are degree 8000 then - okay - polynomials of degree 8,000 that are different can still be equal at 8,000 points because of that we need way more than a thousand points to get the right probability so if the verifier is unlucky she might hit one of these points where the different polynomials are actually equal and but if there are 1 million points to choose from and only 8,000 are unlucky then the probability is rather low so we probably want to ramp that up to 10 million ok that's a very large American dream but it still seems to work so yeah what the verifying out does she requests so she picks a random X Prime from these 1 million points and requests the values of the polynomials at these points there's some weird notation here and the reason is that the verifier requests the requests a and T to be evaluated but if you look at this formula here then it the X prime doesn't directly go into a its first transformed why are these lowercase a functions and this means we have to request we have to first transform this X prime by a 1 that's actually wrong this -1 shouldn't be there right okay and then the next step is the prove of course provides these values again don't remove this minus 1 here and she provides his valid together with a Mercker proof inside the Merkel tree where the the root of which she sent earlier and the verify of course checks the the Merkur proofs and also checks that yeah basically this equation adds up when you're in when you insert the values that the prover just provided yep in this model we just assume that I mean this is still interactive so it is the model is much more powerful its interactive and the verify has randomness you know I don't have a slide for that because of reasons so I can talk about that now the way you remove both interaction randomness is similar and the reason is so if it if you take a close look then everything the verifier sends to the prover is actually just a random number so it's it's just I mean the the verify code also just sent this X Prime and then check that the prover computed these things correctly so and it is also important that this random number is public so the the variant the prover can have access to the random number because the prover pre-committed to the root of the marquetry so and if the proof of first commits the root of remote country and then gets the randomness then she cannot modify the mo country anymore and the way you remove both interaction remembers now is you so if it's not interactive then this means the prove it just generates a single string a single message and then this is verified once on the blockchain for example and this means this message is basically everything to send to the proof as to the verifier so the the roots of the milky trees and then to get randomness you basically just evaluate a hash function on these two routes and take the randomness from there because this is the same thing so if the prove of first sends the merkel roots and then receives the reminisce she cannot modify the mohkumat anymore and if the if the randomest just depends on the Merkle tree then any modification the Merkle tree will also change the render but in the beginning you said you just expects when they talk about the assumptions you just expect collision resistance and now all of a sudden you expect and have read Oracle access from the hash function right there's much more [Music] yeah yeah I know what you're talking about might be that I confused some terms here so but it's is it enough if the hash function is uniformly distributed yeah it might be that you need to assume stronger hash functions but usually this is what should suffice and just there was another question but let me just finish now we have this random number and then the the prove I can just use that random number and continue and provide that stuff and then perform this check and now the verify which and then this proof is complete we sell it the blockchain and the blockchain just reruns the steps of the verifier and that's how we remove both into action runs questions [Music] art inside beautiful the egg Dalton because our our the point outside the Rose well it doesn't matter and it's actually no I mean these are so there's no really a concept of inside or outside or I mean and to know because the field is finite so they're the values of the polynomials polynomials are always elements of a finite field I need to have an ethical problem it would be [Music] properly defined to be a mathematical thing without any and another thing of using hash function parameters of courses that sting gets for distance which is also important for berries be okay what is missing from here actually yeah that we can stop them so he said that phenomena is proved that the two numbers are small so small Vegas [Music] yes otherwise the prover can just I mean the proof of computes this a and creates a miracle tree of the values and these values can just be anything they doesn't they don't have to be so just just from the Merkel root you don't really see whether the values are the values of a polynomial and if they are not the values of a polynomial we lose this property that two different functions are different at almost all points okay so yeah the I OPP will solve that and yeah the as I already said the proof I can cheat unless a and T are polynomials of low degree and low degree in this case is 8000 and the interactive Oracle proof of proximity will help us I will actually give a very simplified presentation of I OPP especially we will just ignore the proximity part in our simplified version we have a Merkle tree of the values of a function and you want to prove that this function is a polynomial of degree at most e we actually don't care which polynomial and that's also important that the prover doesn't have to prove that this is it that this a is a certain polynomial you just need to prove that is some polynomial and if we do it properly then we are so we add if we add this proximity thing then we actually show that it's either a polynomial of degree at most D or it's far away from all polynomials of degree D and far away here means it differs at many points at many values but that's a little bit more complicated so we'll do the simplified thing the main idea so we will also this will also be an interactive protocol because inside an entire interactive protocol we can invoke another interactive protocol as subroutine and the main idea is divided conquer here so we what we do is so we assume of course that F is a polynomial so it has it's a sum of coefficients times X to the power of K and we take these powers of K and regroup them into art and even once in the following way so we have our polynomial f of X and we state that it's equal to G of X square these are the even coefficients plus X time H of X square these are the odd coefficients and then G and H are again polynomials but the degree is D 1/2 now it's d 1/2 because the input is already x squared is it clear that that is possible so we just move all even coefficients to the left group them and interpret them as expressions in X square instead of X and move all or to the right factor out 1 X and also important interpret them as coefficients in X square and what is also important that the domain size so that the domain is always a finite field and this is also 1/2 because we only have squares here ok and now what we do is again the prover commits to a marquetry of all values of G and H and the verifier requests a random check that this equality actually holds we already have the proved already committed to all values of X she does the same for G and H and then we just evaluate this equality at a single point at a single random point and so we know that this actually holds with high probability and now we do the same thing recursively for G and a but now the degree is only D half and this recursion will terminate at some point whether degrees one at which point whether at and at that point or at zero and at that point verify I can just check that by looking at it [Music] exactly so the only reminisce the verifier request is just so the randomness doesn't depend on any previous messages that's also important it's just a random number at a certain range any random number it's a chief in the same way exactly okay we're almost through so the exciting part the next talk is not far away how do we add seer knowledge that is also simplified again because we ignore the fact that this this proximity thing what is your knowledge there have been so you can have a different talk about the whole concept of knowledge a very simple explanation is that in such an interactive protocol the prover convinces the verifier about the fact that the computation is true without revealing anything else about the computation so in our specific example the verifier never learns these intermediate values in the computation of course the verifies yeah it's a bit more to the since the verifying can actually compute these intermediate values this is not really true here so the actual concepts a bit more complex because you can add hidden inputs but yeah let's take a look at pseudocode for example there's an interactive protocol for Sudoku where I can prove to you that I know that this pseudo is solvable without you actually learn learning the actual solution I can do it now but because I don't know the solution there is a protocol that does that so at the end you're convinced that it is solvable without knowing how to solve it okay and how does it work with starks or actually so we will only look at the zero knowledge aspect of this IO pp and the Starks the full Stark so your knowledge so again the task is to show that these two polynomials a and D are arbitrary low degree polynomials I said that before it doesn't we don't want to know we don't want to convince to verify that they are have a space they are specific polynomials it just suffice us to show that they are arbitrary polynomials of a certain maximum degree and so if we say that P is the set of all polynomials of degree at most D then the following is true for any polynomial you in P so for any polynomial of degree at most D and any function f F is in P if and only if F plus U is in P the reason is so if F is a polynomial of degree at most T then adding a polynomial of degree at most D will not yield a polynomial with higher degree and if F Plus u has degree at most D then you can subtract U and this will yield F and of course a polynomial with degree at most D minus a polynomial with degree at most D years a polynomial with degree at most e good and we use that now to show how we can get an IO P P with zero knowledge and yeah we will almost show that there's some tiny point that doesn't really work out the prover chooses so we want to show that a is a polynomial with degree at most D and but what we do is instead the proved it uses randomness here and chooses a random polynomial with degree at most D and adds it to a and then we creates the mercury of values for a plus U and then both run the IOP p4a Prime and the thing is now since you was chosen uniformly at random from P this a prime is actually just a random polynomial of degree at most e and the verifier cannot deduce anything about a from that yeah clear or less and yeah it works because of this lemma here alright again something I forgot of course the Provost still has to convince the verifier that this equality here holds this is the kind of small hole here and the zero-knowledge thing because for that we again have to evaluate them at a random point and because of that the verifier learns at least a single point of e actually the verify also learns the root hash of the values of a but in the full star construction this so the reason why this doesn't matter in the full star construction is that it has a property that if you learn up to T bits of the proof for a certain small constant T you learn nothing about the the actual witness and this is because of that you can it actually is fine to evaluate this at one point this will not yield anything about the actual thing the proof is about okay I don't have any more slides are there questions [Music] actually it's the opposite so snarks are already possible in the theorem because we have these pre compiles and also because the proofs are only 800 and 188 bytes which is which fits easily into transaction and for starts we have proofs of size I don't know five hundred kilobytes which is way too large for a transaction so I could think of a specialist blockchain that only has Starks where 500 bytes is not that large because we have 1 megabyte blocks in Bitcoin but I don't think it's practical for if you at the current point in time oh yeah the benefits of Starks are no trusted set up they are quantum resistant what else did I say yeah yeah quantum resistant transparent I mean that means no trusted set up and that's about it yeah and they also they they don't make any unproven assumptions so I mean crypto sanctions does not only mean not quantum resistant but I mean snarks assume this knowledge of exponent thingy which might just turn out to be not true [Music] the question was where the setup for the run ones thing and that transparent is the same yes it is the same yeah yeah so in snarks the there's an internal initial set up that generates a certain amount of data you're saying Starks are mainly longer because they have interaction and because of ehm here and the mocha proofs the proofs are longer yeah I mean II lab and so saw is confident that that can be considerably improved I don't have that much inside so I hope [Music] there are implementations on github for the whole thing I'm not sure what the actual input is but they it's not as so snarks for snarks usually have to create arithmetic circuits and then compile them and for starks they start with register machines so they actually use computation traces and the paper says that it is better to run on register machines then create our thematic circuits because when you start with automatic circuits you end up with polynomials of degree two and this is important for snarks because they can only handle polynomials of degree two but starks can handle polynomials with higher degree and if you start with computation traces you get polynomials of degree eight and because of that it's more efficient and going through circuits risky but I'm not really up to date but I doubt that they can handle 50 cubits right so there might so there's so in popular articles they usually say quite a computer's part but actually there are two vastly different types of frontal computers and one of them is adiabatic quantum computers and they kind of break discrete logarithm they can just do some optimization problems probably quite fast but actually there's not a lowering of theory about that and I think they always have 40 or 50 cubits and the others I think might have 10 or something like that and so the number of qubits you need is basically the key size if you have a full quantum computer with a key size up to your private key then you can recover that just from a popular public key whether you can switch from snarks to Starks I mean they are fundamentally different things but if you build your system flexible enough then of course you can switch I mean yeah and I mean if you start with the system like etherium then you can have smart contracts and I kind of both at the same time if Starks if either the EVM is performed enough to implement Starks or Starks are improved as much as such that they are can be run on the VM okay then sorry for boring you for an hour and thanks for your attention [Applause]