Scalable, Transparent and Post-quantum Secure Computational Integrity...

I'm a professor at the Technion computer science I'm also one of the seven founding scientists of Z cache and I'm gonna tell you mostly about joint work with dough bento you know I wish Michael adaptive and it will have three parts the first part is gonna be a little bit more theoretical the second part is gonna be very practical and then the third part is gonna be again more theoretical okay so those and I'll tell you when we're moving between the parts and you can stop me and ask questions okay so I want to tell you first of all about this sort of the theoretical models in which we like to play these games and build these proof systems and then I want to talk to you about the way we realize them in some numbers of benchmarks and then again go back to some theory that applies to both Starks and to snarks okay so I'm gonna tell you about something called an interactive Oracle proof it's a kind of a game that mathematicians like to study it's very clean mathematically and you can make a lot of progress studying this game but it's unrealistic if you want to use it in practice then I'm gonna tell you about a special kind of IOPS interactive Oracle proofs that are really really efficient almost optimally so and they're gonna be really great and again we can prove a lot of things about them even without any cryptographic assumptions but again they are unrealistic and then if you go and realize them and I'll talk a little bit about that and you realize such a stick then you get something that is practical and you do need cryptographic assumptions but very lean ones ones that are post quantum secure they don't have any number theory involved in them they don't require a trusted set up and that sort of stuff so that's how you get a start in the end good so let's start we play these games about computational pretty statement so Bob makes a claim that he wishes to convince the world and he says I know some private witness W such if you take if I would take that witness and run up specific computation see on this thing that only I know and also some public input that everyone knows then I'll reach an output of why within t steps this is a very general statement but examples are the Z cash join split that's a special case of such a computation or if you want to proof of solvency or that you own enough coins and you could have applications in smart contracts and so on and so forth so we'd like to study these very abstract settings ok so what is this game called an interactive oracle proof it's a game of many rounds between approver that's Bob and a verifier that could be anyone and the game the best way to think about it is that the prover sends a USB stick that the verifier keeps and then the verifier tosses some random coins public or private and sends a message back to the prover and the prover sends another USB stick that depends also on the randomness that he was asked ok and then this goes on for a while and then at the end so the verifier in this case alice has collected a bunch of USB sticks and now she tosses some more coins and based on those coins she goes and queries a few random locations of the data written on these various USB sticks and she plugs it into some computation and based on that computation she decides whether to accept or reject the statement ok so it's a very simple game one in which you you get a USB stick you send some randomness and so on and so forth ok and we would say that this game is good for the purpose we made it up if it has completeness which means that a true statement of Bob really knows this private W then he can indeed convince through this game with USB sticks he can convince the verifier that it's true and soundness is is the more tricky and important part that if the statement is indeed false or Bob doesn't know this w then it's gonna be very unlikely for him to convince the verifier that the statement is true so it's an unrealistic model but it's mathematically clean and why do I say it's mathematically clean because with this model within this model we could say if you were we're willing to play this game you could take any kind of computation even if the prover has to run exponentially longer than what the verifier will do this is a class of problems called necks then any one of these problems that includes the joint split circuit in various smart contracts and a lot more you can have this sort of IOP that's also really really great first of all it has your in knowledge but it has a bunch of colored terms here that I'm now going to explain so it's fully scalable it's transparent it's an IO P of knowledge and it has perfect zero knowledge okay and this is joint work also with Alessandro Piazza real Gabby's own sitting here manasvi osa all of us are with Z cash and then there's follow-up work also with Mike Forbes Michael adaptive and Nick Spooner so let me explain now those colored terms so fully scalable or doubly scalable means scalable proving time and scaleable verifying time prove er timescales almost linearly in the time it would have taken just to run the computation so instead of taking T steps it takes T times log T to some small exponent hopefully the exponent is small sometimes it's called quasi linear time and it's not hard to show that prover cannot run less than T steps so up to this poly log factor its optimal on the provers side and at the same time it's also optimal on the verifier side the verifier needs at least to specify the statement and and and logged years is a theoretical lower bound for this for this thing and you can still get the verifier to run only in log T which is the bare minimum needed to some power transparency means there is no trusted set up there is no there are no secrets all the randomness the verifier needs is just public random coins so in particular if you could think of a setup where you have a blockchain with blocks once in a while and containing some some randomness in them you could say we don't need the verifier if everyone if everyone's watching the blockchain we could extract the randomness from there and have that play this side of the verifier and you would get public verifiability in a very transparent way that everyone can sort of believe in okay an IOT of knowledge I don't want to go into the definition but it actually means that if Alice takes the USB sticks and opens everything up in them then she can find this witness which seems to be contradicting perfect zero knowledge which says that it's the strongest form of zero knowledge in a mathematical defined way now the last two bullets seem to contradict each other because if Alice gets the USB sticks and reads everything in them she can recover W so but the last bullet says that looking at the interaction Alice learns nothing and this is part of why we say that the model is unrealistic because first of all sending USB sticks is kind of inconvenient but worse if Alice has these sticks and she is malicious she can compromise zero knowledge so for these two reasons we need something else to implement this this model and this goes back thirty years more to basic works of Killian and McCauley and how to take protocols like these things called pcps of which I Opie's are a generalization and how you can convert them into practical things so you can do it in two ways basically and and the solution should seem reasonable to anyone working with blockchains instead of sending this whole big message see USB stick what what the prover does is compute a Merkel root of the information a hash and that's a commitment everything he wants to send and he sends that so it's a very short message and then he gets randomness and then he sends another hash a Merkel drooped hash for the second USB stick and then at the end Alice or the verifier will ask him some questions and whenever he opens those questions he will append to them an authentication path proving that with a second USB okay as claimed and these are standard things that are done with Merkel trees good and you could do it in two interactive yeah you could do this interactively which means let's say you could rely on a blockchain and way to block each time to get new randomness or you could have someone send the randomness or you could do it also non interactively in which basically you take the hash of the latest message and you think of it as the randomness that the verifier sends and both of these now both of these realizations now require some cryptographic assumptions so we're moving away by doing this from the clean theoretical abstract game and we rely either on collision resistant hash functions in the interactive case in an iced arc or you take you do a non interactive one get an N stark and then we need something called a random Oracle assumption which is commonly used but mathematically not as clean as the games we started playing good so a good research question I mean snarks and Starks have a similar sound and it's on purpose but a research question that I actually do not know to answer formally there are definitions for these two things are all in Starks non Interactive's so interactive Starks are clearly not snarks because the end in snark is non interactive so you can't have an interactive non interactive thing but you could ask whether an end stark is actually always necessarily a snark it's a question that I think is interesting and answerable but I haven't looked at it ok but they definitely serve the same purpose which is proving in zero-knowledge very very efficiently general statements about computation good so we talked a little bit about theory and what we've been doing it took actually quite a long time but we now have some implementations of of Starks that have either without your knowledge or with zero knowledge so the first ther stark without zero knowledge was presented about a year and a half ago if you're a crypt it's it's a whole bunch of authors that here is one of them as is among the Z cash founders it also includes Alessandro Piazza a tanto male and models Villa I hope I'm not forgetting anyone here and a whole bunch of students - Tecna on so I mean I don't want to waste all the time on this so and now we're we we have the first ZK Stark it's based on a theoretical zero knowledge 16 trans fat trans sex sorry scaleable transparent IOP of knowledge which is again one of those theoretical constructions that's again joint work with VL models in Alessandro and we have already the proof of concept code I'll show you some some some benchmarks the paper takes always much longer if you think that to debug code takes long than debugging papers is I guess similar if not worse so are just writing them and one component already appears online it's a very clean and separated thing that those of you who like algebra I urge you to download it and read it and you can actually implement it both of our prime fields and over binary fields I think it's very digestible for those who know who know algebra or took ok so some part of the new Stark is already out there and the rest I hope so ok we're done with the first part which is sort of abstract now I want to show you what happens like in terms of running time when we use this realization this this torque the zero knowledge stark good so those of you who sort of spaced out because it was very abstract now I'm just gonna show you some running times and measurements so the benchmark I'm gonna talk about is this setting where the FBI has let's say a DNA profile database and it is willing to publish daily a merkel sorry a hash of the state of this database and in it or basically the DNA profiles taken from all crime scenes and each DNA profile is then compressed you know analyzed and compressed and it turns out to be 40 integers okay that's sort of each one of us if our DNA sample is taken is reduced to a set of 40 integers and yet publishes this daily and now some day along let's say a new head of the you know head of the FBI solicited and like this okay I don't know yeah microphones are really spooky things what okay okay so the FBI is database is posted and now there was supposed to be a new head of the FBI and the public is worried whether he's a sort of shady and you know the FBI wants to convince the public that this is not the case and that they can run a profile Matt search of the incoming head of police or whatever against this forensic DNA profile database and report the match okay so that's the program that we actually implemented and the program is written down there it's sort of the public input X that everyone sees is a hash commitment to the database and a hash commitment to the incoming chief of police and the witness that only the FBI should hold are the preimages of the database a pretty large you know string or a set of profiles and also the preimage of this incoming chief of police is a DNA good and they run this computation where they both compute the hash and compare it to the publicly known hashes and they also check some profile match which is it's not just this string equality there are some little logical complications there but nothing too deep good so we ran this thing actually and it's kind of a large machine then has like 16 cores I mean 32 AMD cores which are I just learned recently it's like 16 cores with hyper-threading nevermind and half a terabyte of RAM and so we managed to run it all the way up to a million profile which is 40 megabyte size file and is there any way that maybe decrease the light for a minute because probably only the first row can see anything is there a way what can you guys in the back see anything I mean there you'll see some graphs here okay on the top there are various measures for the provers site for the site generating the proofs this would be the FBI and on the bottom there are measures for the folks you know the public us trying to verify it and for instance what we see here is the ratio of approving running time to naive running time so when that when that when the database size is kind of small so it's only 50,000 times more time takes 50,000 X 50,000 more time to generate a proof than it is to just naively run the computation and then it jumps up to like 250,000 and right about this is where we sort of max the RAM out and we need to start doing either swapping or redoing the proof so presumably if we get more RAM then we would be able to do it only at 50,000 times more or slower than just doing the generate just running the computation without any proofs this is the overall proving time so it takes much less than one second if you just have a very small database and it takes about a day to generate the proof for you know the whole million size database by the way I think the USA is a forensic DNA profile is around 20 million or so sort of okay there are different places so we're not that far away even today from being able to prove something on that large database and here we have the proof size this is like an internal measure a theoretical measure of the amount of space that the prover needs not the amount that he's sending over here we have the verifier side and what we can see is the communication complexity the amount of information being sent now the prover we can run even sorry the verifier we can measure even on on on data for which we cannot generate proofs because the verifier you just make some queries and then checks is everything if everything is fine so we might as well generate see what the verify looks like even for inputs that we cannot yet generate proofs for it that's what we did here so we ran all the way up to 2 to the 36 entries which is pretty big it's like 2 to the 6 times gigabytes right many entries so billions of entries much more than there are people you know living on the face of the earth today and even there at the end you get something like around 1.2 megabytes long argument if you do it non interactively again for something that would be many many gigabytes of information so we actually get compression in space and I mean by the way so we said there's a clean mathematical model and that cost very little of the communication complexity and most of it is about the authentication paths from these Merkle's another interesting thing that we'll talk about later in a minute yeah and the overall running time starts at 20 milliseconds and even for 2 to the 36 it would have taken less than 80 milliseconds to verify so which would have been much faster than doing it naively now because of this because the verification time is exponentially faster than naive computation time right this it behaves like log of T as opposed to T where T is the running time we can talk about compression functions so the time compression function is the time it takes to verify a statement divided by the time it takes to run the statement and if this value is above 1 it means your verification takes longer than just running the computation but once it goes below 1 you're actually saving on verification time and you could do the same thing with space supposing that the witness is this non-deterministic you know proof that the computation is good you could compare the size of that proof with the argument that comes from from using a proof system and again you could divide the communication complexity of the proof system by the size of the database and one this once this ratio goes below one you're actually compressing and this is something we're very proud of we actually managed in practice for the first time to overcome to overcome boast the time compression and the safe space compression functions which means that we actually generated proofs and verified them in time that is about I think four times faster and compresses by a factor of 50 so but as you can see from the plots because of this exponential speed-up the larger the data sets in general and the larger the scope of the computation the more impressive that your compression in space and in time must be so we're very optimistic that in the future we'll see even more compressions and you know there's a big discussion about scalability of block chains in general right how do we process millions of or thousands of transactions so I think the one very viable long-term solution is to use things like this because they can really offload the whole task of proving the integrity of a very big system in a way that's mathematically very clean post quantum is secure you don't need any trusted set ups and it's also very efficient on the prover and verifier side so there is a bunch of other really cool approaches scientific approaches to addressing this question of proving statements with zero knowledge and I'm just listing a few of the theoretical things that have been implemented in practice and comparing them asymptotically along these desirable properties so you would like something that has a scalable prover a scalable verifier you would want the proofs to be transparent and you would want them to be post quantum secure so the very first approach it's based on homomorphic public key cryptography there is a whole line of works here but this includes the snarks and quadratic arithmetic programs of genell so you can see it has scalable prover the verifier is scalable only after the pre-processing phase so for a computation that goes time and again that's not an issue something like the joint split circuit of Z cash but if you want you know modify circuits and generate new ones or tweak with them a little bit and you're gonna have to have this pre-processing phase that makes the verifier non-scalable for a single computation they're not transparent and post quantum secure there's a nice approach based on the discrete log problem by go off that takes away it makes the system transparent but it's not post quantum secure and the verifier isn't scalable there's one again that even is post quantum secure based on running an NPC protocol in the head and you can also apply incremental e verifiable computation on top of any system and this is something we implemented it's not transparent in post quantum secure but it is scalable theoretically and as you can see Stark is green the whole line through which is why I think you know in the long run this is the way to go and in terms of running time so I took these theoretical approaches and we actually implement take took the same computation and saw how different systems measure up on the same machine you know trying to compare apples to apples as best we could so lower is better and what you can see here is that the prover generation time is almost best for Stark I mean the NPC in the head is slightly better but the verifier running time here is pretty large 32 seconds versus 40 milliseconds now with snarks which are the yellow thing so if you take into account the time needed to generate parameters then you get really long a verifier time because the verifier is the one generating the parameters that's 28 seconds but of course assuming that you've done that and also there's a very large communication complexity for chen sending this key but once you did that and you assume everyone has it then verification time of snarks is of course fastest nine milliseconds versus 40 milliseconds and the proofs are extremely short 0.23 kilobyte versus in our case 452 and this is I forgot this is the discrete log based eight kilobytes and this 6.5 megabytes okay and as time will go on we'll see more and more implementations and even along these lines we'll see them all going down which is of course great good so I talked a little bit about the numbers we're getting right now in our proof of concept code and now the very last part I want to go back again to theory and I'm gonna tell you a little bit about arithmetician and arithmetician is this nice thing that is also part of the theory that is behind both snarks and Starks and also all those other systems that I showed you so all the implemented systems in the end there's a very strong component of arithmetician so that's gonna be the last thing I want to tell you about so everything I say now is relevant both to Snorks and the Starks and to things based on discrete log and to running an NPC in the head and a bunch of other approaches it's a very powerful and beautiful technique and I want to explain it to you just a little bit good so arithmetic is like it goes back to even together as proof of the incompleteness theorem for those of you who learned about it it's a fundamental theorem in logic and philosophy and then it was used in the 80s by was Bob of famous theoretical computer science to prove theoretical results that I won't go into and then was modified and brought into the world of these proof systems by fort now and Bob I and since then it's been used to great extent so okay now we're starting again a little bit of math so those who haven't seen these things and don't know what a polynomial is I apologize it's gonna be a little bit fast but those of you who have seen I hope it's you know you'll enjoy this ok so a polynomial is this formal sum it's really a computer program of a very special kind that allows you only to do multiplication and an addition ok and the degree is the maximal term the maximum degree so X to the 5 is a degree 5 polynomial and lines are degree 1 polynomials and these parabolas we study in high school or degree 2 polynomials so on and so forth good now we'll say that a funk that is evaluated on a set of points is called said to be of degree D if the polynomial that describes that function is a degree d polynomial so these are two slightly different objects right if I see a line on the plane okay and I take the sequence of points that that this that comprise these this line that is a function for every x value I get a Y value but we will say that it's a degree one function and the same thing with a parabola right so I'll say it's a quadratic function degree two function okay so these are some basic definitions and the fact that we're going to use is that two distinct polynomials of degree D can intersect at at most D points for instance two lines if they're not the same line they can intersect only at a single point two degree parabolas if they're not the same parabola they intersect only at two points and so on and so forth okay good and this is a very important property so this is how we're gonna use it if you have two distinct functions that have the greedy but you asked for their evaluation on a hundred times D points then they will disagree if they're not the same function they either agree completely and all of these hundred times the evaluation points or they disagree on at least 99% so if you sample a random point and they're not the same function with 99% probability you'll see that they're not the same function and we'll use this to find you know falsities or see if we're being cheated and formally you could say that the space of low degree functions form an error correcting code and it has a name the reed-solomon code was discovered this use of it was discovered and studied in the early sixties interesting fact is that it was studied in the early 60s and started getting implemented in CDs and DVDs in the mid-90s so 35 years and things like zero knowledge proof started you know were discovered and invented in the late 1980s and early 1990s and now we're in 2017 so that's roughly 35 37 years till they start getting implemented in things like Z cash you know people actually use them as opposed to just study them okay so there's this three and a half decades separation between science and realization good so here's here's here's our goal now right we're talking about I want to try and convince you that it is possible I want to show you some of the magic that goes into bar being able to prove to Alice a statement that Alice doesn't have even the time to run and verify so here's a very simple example as part of this complicated computation Bob is claiming to Alice you know there's this there's this register and it's type or its range it always has the value values between 1 and 10 and it's really important to the you know the bigger argument maybe this is the program counter and you know it's a 10 line program so it never goes be over below 1 and above 10 but the thing is that Bob is making this claim about a really large number of points he's saying there are million points or a million values in this array that all of them are between the range of 1 and 10 so the goals we would like or we would like to find a way to trust Bob's claim can he prove that he's correct and we would like later on to talk about privacy can will this proof leak information about about these million about some of these million points we would like it not to because it's part of what zero knowledge is supposed to do and the last thing is can we do it succinctly can we make sure that Alice doesn't have to work very hard and and you know query all of these million points so this is the first claim Bob claims I have a list of 10 to the 6 integers they're all in the range 1 to the 10 and the question to you is can you see a way for Alice to check this statement with just 2 queries and still have 99% probability of finding if Bob is cheating any ideas is it possible no it's not possible right because you know Alice has to check all of them there was a million of them and she doesn't check one she might be wrong with okay so so Bob really wants to convince Alice that this is the case so he says you know what I've added redundancy and more information to sort of convince you and I took and encoded this list using so what I did is I interpolated I found what is the degree 1 million polynomial that goes through these points and then I evaluated that polynomial on many many more points on a billion points 10 to the 9 will you now you know trust me with this claim so the question goes again can Alice now make 2 queries and find if this is the case what do you think what who thinks this can be done raise your hand with just this information who thinks it cannot be done with just this information no other information okay so the the second those in this it cannot be done with just this information it's not enough information ok because actually you still need to read basically a million points in order to find out this thing ok so Bob is really frustrated he says Alice what more what more do you want me to convey you know what more do you need in order to be convinced so Alice will say you know what I'm gonna ask you for a favor Bob please evaluate one more polynomial and you know give me any polynomial of degree 10 to the 7 minus 10 to the 6 so it's like 9 million that is that is the degree of the polynomial I seek you can give any one you want but if you do it well and your claim is true then I will know with 99% certainty if that's the case okay and this already works now so it seems it's almost like the second claim right it's still the same claim but there's just a little bit more information right Bob is giving two evaluations of polynomials of weird degrees one of degree a million and the other one of degree nine million and Alice says you know that's enough for me to know if you're saying the truth or not so here's how this magic can happen and she's just gonna read two points and still be convinced that this is true so let's define this weird polynomial C of X it's not so weird it's a polynomial that has exactly ten roots there are ten values that make it vanish or make it become zero and these ten values are exactly the numbers one to ten right if you take if X is 2 then this term becomes zero and zero times everything else is zero same thing with 1 up to 10 so this is a polynomial of degree 10 it's a polynomial of degree 10 and if you open it up you'll get ten terms okay good and again this is a very important polynomial to our problem because it captures the range or the type thing that we want to check right we want to check that something is in the range 1 to 10 it's really that what we want to do is check that this polynomial vanishes if you plug into it those points now similarly this this will be sort of a sort of an added construction but it's of the same flavor so there's this polynomial D of X that you construct it in the same way but it vanishes on the points 1 up to a million instead of 1 up to 10 so basically this is the polynomial that captures what are the points on which Bob is making his claim right because Bob says for the first million entries of the array for the points 1 up to a million the value of the function is between 1 and 10 so we're sort of algebraically defining what is space that we care about good so we have these two polynomials and now this is the actual test that alice is going to use okay and first I'll convince you that it makes two queries and then we're going to discuss why it actually accepts with probability one true claims whereas it rejects with 99% probability any falsity the Bob's makes which is really gonna be magical so what is the test the test is rather simple Alice tosses a coin so remember what Bob did is he wrote down these two polynomials one and both of them are evaluated on the numbers 1 up to a billion okay so you have like two tables two arrays or two USB sticks if you think of them and this is Alice's test she picks a random you know she tosses coin she picks a random number between one and a billion and then she let's call it X naught and then she queries the first function and the second function at the same point and let's suppose that the answers are alpha and beta well that's how we'll denote them and then all Alice does is she says I will accept Bob's claim that all the numbers between one and a million are in the range 1 to 10 if and only if C of alpha so she plugs alpha into this polynomial of degree 10 and she says I will accept if and only C of alpha equals B times D this weird polynomial when I plug out 4 into it sorry X 0 into it okay so let's see what we understand now this is a test that makes only 2 queries 1 to F and 1 to G that's all we know now does it work so improve systems there are two parts there's completeness proving that correct statements can be proved with high probability and the hardest part is soundness which is proving that a falsity is rejected with high probability let's start with a simpler statement where Bob is on it so really the first million values have been between 1 to 10 and then he took a low degree extension so you sort of interpolated and then valuated and a billion points and that's his f what see in a minute G should be right now on Alice said to Bob is you can give me any polynomial you want any evaluation any function of degree nine million but now we'll see what what an honest Bob would you there's just one you can use so that's what we'll see now so let's see and then we're heading towards constructing this G okay so we said that F is you know is this good function and it is of degree a million and P of X is the interpolant is the polynomial that describes it now if we plug P of X into the polynomial see we get a new polynomial but this polynomial will vanish on all points between one and a million why P we assume that P of X on all points between one a million and a million gives you a value between one and ten and if you plug a number between one and ten in to see you get zero that's exactly what C does so assuming that P of X has the range between 1 and 10 on the first million entries then C of P of X will vanish on the first million entries okay we just restated but here's a nice fact so a polynomial vanishes at a point X naught if and only if you can divide it by X minus X naught which means if and only if there exists a Q prime Q prime is not the derivative some other polynomial of degree exactly one less such that Q of x equals X minus X naught times Q prime of X and if a polynomial vanishes on a million points so there are many x knots that you can divide you can repeat dividing Q X by X minus X naught and here's the corollary so if you look at C of P of X and call it Q of X it vanishes on the domain 1 to a million only if there exists on prime that is of degree a million less than the degree of Q and that's exactly 9 million such that Q prime of X times D of X this pre-specified polynomial equals Q of X so now let me return the question to you what is G of X going to be what G of X what function will you evaluate so that this equality always holds exactly Q prime so what Bob does is he sets G to be to be the evaluation of G prime and because this equality holds sorry because Q because C of P of X equals D times Q prime of X if you have that P of X if you evaluate it you get if Q prime if you evaluate that you get G so you get that this equals this always and in particular this equals this always so the test passes with probability 1 now the harder part I said is soundness so what we've seen is that an honest Bob can convince Alice with probability 1 in a test that she makes only 2 queries about so let's look at the other case now suppose Bob is cheating and for simplicity every element in this area is between 1 and 10 but for the very first one which has the value 11 so if Alice is just gonna check some random things you won't notice this yes probability of 1 and a million of picking the first entry now again we do the same process we let P of X be a the interpolant of f and the point is that see when you plug P of x into it it does not vanish on all points between 1 and a million there's one point on which it does not vanish on 1 on the point 1 if X more FX 0 equals 1 then C of P of X does not equal 0 it equals something else ok it seems like we're in the same case as before there's just one entry out of a million on which the value of this function is 1 is not 0 doesn't Alice has a chance but you see for any other low degree polynomial Q prime that Bob would take and evaluate as his G we know that the product hew prime times D does vanish on all first million points right because why does this why does Q prime of x times D of X vanish on the first million points for any choice of Q prime X why does the product vanish in the first million points it's a product of two of two polynomials and if one of them is 0 it will that polynomial annihilates and make the other one be 0 or not matter and D of X was defined to be a polynomial that vanishes in the first million points so this product whatever Bob picks for Q prime and evaluates as G this product does vanish on the first million points so C of P of X does not value does not vanish on the first million and all of the first million points whereas D of X sorry whereas this product does vanish on all so the two polynomials are not the same you would think that they only differ on one point in the first million entries and that may be the case but recall that we said that degree D polynomials if they don't agree completely they can agree on at most D points now we took two polynomials of degree nine million but they're not the same so they can agree only on nine million points whereas we have sorry it's actually 10 million I mean this is a polynomial of ten million this is a polynomial of ten million and we actually have evaluations on a billion points so they could agree the two sides of the equation could agree on ten million points out of a billion that's one in a hundred chance they disagree on 99 percent of the domain which means the random X not the probability of failure is 99% in this case so I just want to summarize because my my time is up what have we seen we've seen that you can take a statement that discusses a very huge array a type checking statement which is a basic thing that is part of checking correctness of a computation and even though the statement refers to a million points you can ask the prover of the person making this statement to use polynomials two polynomials in this case so that you can easily distinguish between truisms and falsities with only two queries that's what we achieved and this is this is what our estimate ization does now the only remaining problem that we have and this is where snarks and Starks differ is how do you ensure that Bob gives you evaluations of low degree polynomials in the first place and I have two one my time is up but you know there's some more papers that need to be read in order to find this but you could do it the snark way or the stark way and with this Alain thank you [Applause]