ZK Study Club - STARKs overview - Session 2

Transcript

so so yeah hello good day everybody so today is the second the second study group session staying in the theme of high-level overviews we're taking another look from the stark wear group this time it's Michael Reid observe I hope I say that correctly this is a recent talk he gave in October and specifically it was about a Fibonacci example and it started to dip into the you know the mathematics around around how to construct Starks what what does it mean to have completeness and soundness as you're building these zero

knowledge proof so a bit of a pre ramble that he started with again you have two sides in this zero knowledge setup you want to you're going to have the prover who claims knowledge of a secret and a verifier who you know is skeptical about the prover and once wants to have a strong proof such that they are satisfied an example that that was lit off with is okay the prover wants to make a claim that they're possessing greater than 100 Bitcoin the verifier you know in a malicious case maybe wants to learn which Bitcoin addresses or wants to learn something about the total amount or possibly the keys of those Bitcoin addresses so the prover is going

to be able to make a zero knowledge proof such that addresses keys total amount of Bitcoin remains secret but the verifier is satisfied that the prover does in fact possess more than 100 Bitcoin so overall properties of Zeke a Stark is that the verification is a logarithmic time which as Mike Michael McHale pointed out that that means it's practically a constant time as you know as the stark circuit is getting bigger and you have the efficient proving time because it's close to naive execution it's quasi linear all right so the the main part of

this talk and of the session today is going through a construction example of the Fibonacci sequence so the statement or the claim that the prover will make is that they know two secret numbers a and B those will be the starting values of the Fibonacci sequence for some sequence length and so the constraint then is that you have an a sub I added to an a sub i1 and that will be the next value and so so we're gonna build this up over a number of you know trial rounds starting from naive and ending in zero knowledge so the naive is exactly what you might expect which is the

prover is sending a and B explicitly and so the statement is just I know secret numbers and the fifth element is 42 so a and B which are my secrets are 12 and 6 the verifier is this going to compute up to the fifth element you you know you're not getting any anything out of this so how to do better this is where you're introducing the third party so you don't just have the proven verifier eventually the notary will be a cryptographic method especially the statement is that you want the notary to be the only trusted party because both the proveer and the verifier have reasons to cheat the prove you might want to lie about the secret and the verify the verifier

might want to learn about the secret so in the second trial where we've added this third party notary the prover is passing the notary the full Fibonacci sequence so if we have a range of five values then there will be you know a sequence of five values that the notary then has the verifier is going to ask for a sample of three consecutive values and then they can verify that with those three values you know that the constraint of Fibonacci is correct you start to so the problem then is that the soundness is is very weak because this is only a probabilistic check you

know the Thera fire is sampling some cells and testament constraint holds so when you change the length of the sequence from a million to five their fire then is only reading a very small number of cells and so soundness here is the problem because even one wrong number in the sequence would change the overall outcome but you wouldn't notice that unless you were lucky and selected like lucky in the sense of the verifier having selected exactly where one of the values was changed so if you move from a sequence of length 5 to a length million then this starts to be you know a very big

problem because the prove you could inject a bad value anywhere so how to fix this well you can start to add start add some maths in particular its algebras or sorry it's polynomials so effectively it's a high school level of algebra and so the overall idea is that given a polynomial of P of X so X is one of the values in the range that the prover has proved you're going to have a poly no polynomial such that you have a P of x equal to an a of X with X minus one polynomial as well so you get this a

of X if and only if the polynomial at n is equal to zero so this is the vanishing point it's also meaning that n is a root of P which just means that it's zero and this you also have the opposite being true that n is a root of P if and only if P is factored in such a way that P of X is divisible by X minus n the second I guess core point is that you have interpolation so this means that when you have when you have D plus 1 points so the degree of the polynomial plus 1 and you have points X I Y and I there's only one polynomial of degree D that's

passing through all the points so the base case there is that if you have two points there exists only one line that passes through both points so with this simple theorem you can extrapolate it to higher degrees of polynomials and basically that's you know been basically that's it for the rest of for the rest of this example those two you know those two ideas so heading into the third trial with the intention to increase soundness what what changes is that the prover is finding a low degree polynomial which is encoding the Fibonacci sequence and so no longer is the prover sending the full

sequence of Fibonacci numbers to the notary instead it's just passing this polynomial function that is found say again so the yeah the encoding is that sorry yes you you are correct yeah the the polynomial being being defined is for the starting point in the range this

is the encoding you're correct yeah exactly and so the verifier then is being allowed to query this polynomial f of x at most three times i think the most important thing here is that the number of times the verifier is allowed to query is less than the degree of the polynomial and what's what's changed or the other important point here is that the verifier is querying outside of the sequence that the approver you know the prover was making the proof of so when we said it's a range of 5 the value sample there outside of that range of 5

so we're increasing soundness and the problem is then the the sequence the sequence of values is not what the notary has so the verifier wants to ya the verifier wants to be you know satisfied or convinced that by only sampling three values of f of X that the proof is in fact correct and so the verifier is going to request a witness which is attesting that this polynomial f of X is valid so the verifier notices that f of X is valid if and only if by walking through the range you end up at the point where all these three parts

are 0 of course and that the final value that was stated is also equal to the final part of the range all right yeah and so so at this point Nikhil was saying you know it's saying like building this up and saying exactly this more like a more general statement exists and in general this is why a low degree polynomial testing I guess is quite efficient because you can just have a small number of constraints when the degree like when the polynomial degree stays low it was my take away I could be wrong there but this is what I'm kind of remembering from that

problem statement so here's where you know here's where we start to construct or start to add in a number a number of other kind of building blocks if you will so the verifier was will define the imaginary polynomial Q of X such that Q of X is the f of X and X plus 1 minus f of X plus 2 which is following the first part of of the problem statement so the verifier the verifier is imagining Q of X the reason is because so I so the reason that it's an

imaginary polynomial is because the verifier was not allowed to sample in the range that the prover made a sequence of so every time we see X in these equations those are the real like those are values in the range that the prover has but the verifier was only allowed to sample outside of that range so so this is why the verifier does not know the values with f of X so continuing with you know kind of this polynomial math you know Q is vanishing when Q is one two or three which are the three you know draws that the verifier

gets it gets to take three values out and this is holding if and only if f of X is describing about Fibonacci sequence because this this is a property of that sequence and so additionally it is so additionally add that we're saying that Q of X are sorry at Q of 1 is 0 if and only if Q of X is divisible by X minus 1 and the same for the second and the third draws with where X minus 2 and X is minus 3 so these are all zeros these are all roots of the f of X polynomial so what you can then say is that there exists zedd of X that is equal to X

minus 1 X minus 2 X minus 3 because each of these are our zeros as well so a set of X then can will also be a 0 and we then have this imaginary Q of X so this Q I'm sorry this imaginary Q of X which we started with it's a linear combination of the f of X which is a degree 4 polynomial Q of X is also degree 4 yeah just to be said adding two polynomials together they stay the same degree however is that of X is a polynomial of degree three because the verifier was only getting

to to draw three times so the next important statement is saying then that f of X is valid if in if and only if the ratio Q of X and / is that of X is a polynomial of degree one another way to say that is that you know there's there's a ratio since Q of X is divisible by Zed of X we're going to call this ratio B of X so P of X is equal to exactly exactly this and now B of X is going to be the witness statement that f of X is describing a valid Fibonacci sequence and if you rearrange this and you move said to the

other side then we now can say that Q of X which is the polynomial that the verifier was imagining right that it's going to be equal to the ratio which is the witness multiplied by the Zed of X okay so this was this was the baseline this is the setup and this is the this is the part then that will allow us to that will allow verifier to to be satisfied if approved so the test becomes then the verifier will choose random values outside of the range so in our case the range was 5 so R is greater than 5 then the verifier is asking the

notary to draw three values for this R so our R plus 1 R plus 2 the notary will give back these values and the verifier can now make a test that yeah B of you know B of R by Z 2 bar is equal to Q of R and remember that we're in Fibonacci so we can see that Q of R will be equal to the F of R plus F of R plus 1 minus F of R plus 2 right because we know that we can we can vanish there we can get to 0 there okay so now now what can we say about the completeness of this proof the idea so the idea is that the quaint

so the idea overall is that the completeness of a proof system is that the property sorry a property of the the statement we've made is that the claim will be correct when the prover can always generate a proof that will satisfy the verifier so using only these you know using only these statements they must hold true for all the values that the verifier might draw on so what that will lead us to is saying that f of X is valid when V of X is constructed by B of X as Q of X over Zed of X and and then the verifier must be satisfied so this is this is important we do have you have

completeness at this point however we're missing soundness and soundness is the ability of the prover to cheat specifically it's the probability that the prover can again inject the value there so we need to do some additional work assuming that the f of X is not valid then there cannot exist a B of X why because when we look at the statement that we made so we have the imaginary polynomial that was that the verifier was you know imagining and then built up a statement so that B of X times that of X is equivalent to it they'd have to stay I mean if the the prover really wanted to cheat then it has to stay as at the degree four

polynomial however they're going to be different when the prover is cheating what this means is that at most only four points which are the four roots that the polynomial could share will be the same so when when when this is when this is the case there's only four possible values then that would satisfy the equation and if the verifier is drawing at this r-value from a range of a thousand so 1,000 to 2,000 because it's greater its greater than five when they're drawing in a range of a thousand then the probability of this are the verifier being able to cheat is at most

four over one thousand so for me for me this I guess this kind of intuitively made a lot of sense I had to rewatch this part of the talk a couple times does anybody have questions on that science means new ok if he talks about you me your secret cherry I'm hiding a secret and F of zero function f one enough for to being random and kind of extending the degrees of the polynomial to eight instead of

four maybe that comes right after this right it does yeah sameer secret sharing part that I'm more apparently okay yeah I think this I think this builds up on it because this is without this is without hiding values in the polynomial this is this is just this is just saying that when you have these two polynomials they can only share four points so the probability of the proof or being able to cheat those down dramatically which is which is great because we don't want we don't want that great we want we want the proof to be sound yeah I think the idea so the idea is that when when you

have the two sides of the equation right this is like this is the proof part and this is the note the quote-unquote imaginary part but they're going to be they're both they both need to be degree for polynomials because I you you want to be able to have Q of x over sine of X be a degree one polynomial so that so that means they must be degree four and these zero points right like when you're drawing parabolas when they when they cross over this is just like the I don't know I I had to remember this Rea also for my high school maths but it just means that they can only match exactly on four points if you were to plug in the zero

points then yeah you get zero otherwise you're somewhere else in that XY coordinate space so the resulting value would not be equivalent and so this right right okay so so great so we we have we have a much better property here and and then so it's just to be so there

was a bit of a discussion that happened in the talk at this point and somebody was asking you know how is it that you're encoding a program and so and this was interesting I think that when you're using starts to encode a program we're saying that the degree is linear with a number of registers in the program so you know literally assembly style where you're where you're plugging in values and then throughout the talk and saying you know Starks are using low degree polynomial so what does that mean it means it's bounded so if you had a million degree polynomial because you had a million registers through the program trace then it's bounded it's not going to you know blow up at some point if it's if it's a million degrees

polynomial you have anything between zero and that yeah like it's it's so anyways this is founded it sits inside of the range of that polynomial I didn't quite understand the part where he was saying you can choose the domain of a query to be a much larger size than the program trace he was affected and effectively sounded like something something of this statement as well I don't know if anybody had a better grasp of which will be much larger well the first place the very fire and the prover say

agree on the nature of computations so they in principle have the construction so they both know what would is the highest degree polynomial and after this and principles they can choose the field or which they will work maybe just increases house for example ok great so so with all this being said about the soundness we still don't have zero knowledge yet with with the different setups that we've had and the reason is because if the verifier can read some value it's still changing deterministically based on the secret that the prover was choosing so we then move into the final trial this wasn't I guess this was interesting for me I

didn't have a good technical understanding of Shamir's secret sharing and the fact that it's technically this but somehow extended I guess made made me feel a little more comfortable because I have an idea of how how it works even if I haven't worked through the math once before and and it's it was said that the underlying concept here is that you can hide secrets in the polynomial and this is because when f of X is a degree of D then when you only know a few of the f of X values for example we have a range of five so there's five f of X values that are that are being included in the proof you you

don't you don't necessarily know how you don't know anything about the rest of that polynomial so so the example used in the talk was that when you know for example the zero points of I'm sorry if you yeah if you only know like two points on a parabola you would know nothing about a third point or any other point in fact you don't even know where the parabola crosses the y axis if you if you have points that we're not crossing the y axis and so the principle there or the the core concept there is that you can hide a secret in the zeros which which I don't I don't really have a good you know grasp of either

mathematically or as like a mental picture if anybody else could explain that better that would be nice well first of all this is not difficult I don't remember its exact question of why it's constant terminals of polynomial is used I think mainly yes it's very easy to calculate if you know something and if you know enough numbers like you know qualities of the polynomial at different points you can much easier to calculate so you there value then some arbitrate efficient you still can calculate a coefficient but

it's much easier to calculate the zero term but the principle if you know if your polynomial in is of degree n then knowing any and this n plus 1 distinct values allows you to uniquely reconstruct a polynomial so the way that you just need well is from different people well you make the polynominal use the secret as a constant term so you make a random polynomial which is constant term somewhere you've ever waited at some points and gives these values to two different participants so if n plus one participants get together and share

their numbers they can become strikes a polynomial and gets it cancel and recalculate second Center in Sydney but this is well the secret sharing is just high school algebra in principle if you know n plus 1 points in polynomial of degree n then you can reconstruct and since reconstruction is unique okay okay yeah so then okay so we're basically not at the ending but this is this was the you know this was the secret is using Shamir's secret sharing so so when so effectively when you do not have enough

points that the number of points you have is less than the degree of the polynomial then yeah you're not going you're not going to be able to discover the secret or discover I guess the death of zero one of the roots so so when you have this range of five values so f of line up to f of n which was the chosen secret in the chosen sequence and the proof then we should do the same as Shamir and just add some random elements into the sequence before doing the interpolation which results in the polynomial that is sent to this notary actor so what that means is we have the range F of 1 to F of 5 all of those

values plus you draw some random you know you draw some random values and then you extend the range let's say we extend it up to F of 9 so we now went from degree forward to degree 8 polynomial and this doesn't change the way that the verifier will will do you know do its baseline setup or anything else the reason is because the elements that were in the sequence of 5 they were not known to the verifier it was not allowed to draw from that range our had to be greater than five and now and now it doesn't matter that there was a degree eight it's still gonna have to draw over that and so the one thing that

does change is that with degree eight when we take this range of 1000 the probability of cheating has changed from for over a thousand to eight over a thousand but this is still quite small and yeah so just to say that the f of X which is the interpolated polynomial that sent to the notary is defined different the V of X of course would also be different because Q of X is a ratio of it in the in the construction that we are doing in this baseline what I called yeah what I called baseline and so the I guess yeah the interesting part or the you know the really great

property is that the execution of the protocol results in the same soundness of before and we now have no the leaking of secrets so we've arrived at at a zero knowledge proof and then there was a long discussion at the end of the video I think there was some interesting parts there but I stopped my note-taking as he was wrapping up on the final slide and so the takeaways that Mikhail wanted the group to have was that yeah completeness is that any correct statements will have a valid proof the soundness of the proof system is that there's no valid proof for any incorrect statements fantastic --zk proofs are requiring randomness this is because we're choosing some random points to you know extend the

sequence with I presume and then that the polynomials are being used and they're useful for zero knowledge and to have soundness of the proof system and that was yeah that was it those are the notes they had so what's what questions or what kind of further things come to mind for you guys this was about about the sequence right correct so it's it were still in this idea of

the intro topics I'm not sure I'm not sure if it's Aurora when I'm very honest I haven't even looked closely at those but it's starts it is so it is it is starts the the deepest you know the deepest level here is just that there is a constraint system and so so this is how this is how the verifier will know what to do because the verifier notices that the polynomial which which is

submitted to the you know to this notary reactor right the interpolation of the prover has done is f of X and the verifier knows that all right these should hold true because there's a range of five and that fifth element must match what was what was that yeah that the fifth element must also go to zero when you complete these steps so that would that was the entire constraints so from honestly for me with pen and paper I think yes when I can when I can when I

can do this when I when I can do this I think I'd be able to get there I don't think I'd be very fast at it though also there's supposed to be a more he he kind of teased it that there's supposed to be a more general statement so I would like to know what that is when I'm honest maybe have you been reading the Aurora paper miracle I would like to know what the more general statement is that you know this this is exactly Fibonacci sequence and Mikael is saying there's a more general statement existing and this is what's used in

starts to solve these constraints so instead of because I guess this is a limitation of you know at a very high level maybe this is wrong even but that you need to construct a new circuit every time for ZK snark and this is you know this is maybe because you have to do this encoding directly but Stark is supposed to have a more general you know way to make these statements I mean sure you must you must end up with specific constraints but I thought that there is a way to give it a problem domain and and it would be not her problem if you will or or am i well maybe it was misunderstood but in principle any

bounded computation is more or less uniquely represented as a set of machine registers which be used for error reduction your interest err constraint system will be unique every program well constraint system is what is very nice and good and easy and everything but it's I think it should be so that you has a register representation of the computer program and the small yeah in principle your error is basically a tape

which which is records state of every register which is used in the machine without an external memory and you just makes low degree polynomial which bound which gives you a connection between every next register state let's say and I can easily convert it to well you know what I mean yeah in principle you do just saying that any computer program is non-trivial because

memory management's and this is the same forest narcs in first Eric's having an encoding set access to external memory is not very lousy solves the external memory read and write let's say writing assembly programs all the users might computer registers and tiny ROM it may be not as efficient but in principle is

possible okay okay so so so for me I guess this was this was nice to start heading huh you know heading deeper into the weeds if you will I I think from we used to say it out loud once to the group you know my my and my endgame or at least the first checkpoint that I'm hoping to get to is to be able to build you know to build a circuit and to have an understanding not just to use a tool and then you know deploy that it doesn't

even need to be deployed just to be able to run it on my laptop so at some point I guess at some point maybe in one one or you know one month let's say two months I would like to maybe have a session on like a software library to do this using I don't know possibly Billman or something else but I think we still have more maths to get to and it sound it seems like on this call especially some of you have a pretty good understanding does anybody have recommendations on other you know it's a fundamental maths that we need or possibly some other examples that they work through no papers or appendices of those securities summer school where he goes through I

think one talk is about earth made cessation and I think these are pretty deep into the maps as well and go over maybe some of the stuff that we've seen but also extra stuff and I think you may be useful in terms of getting a more introduction into the mast any a bit deeper than what we've looked at so far but still I think it's a logical step forward ya know I think what would Matthew meant is more kind of like putting the mass in context with with

the technology any kind of word word where it fits in and understanding the nuances within it rather than just like learning algebra because again like polynomials or even just prime field or field theory is relatively simple to to understand if you just look at I don't know another broad textbook which think like oh well the most interesting and difficult part is coming because this construction in principal words give you enormous size proofs if you just use it namely the same with every presentation

is constructed equally so next step is is the price reduction which I think download officers register but like if you imagine to tape as a table with column and rows where each row is a set of registers at time T and called well yeah each column is this is a state of some register at times from zero to end of the program and initially what we do right now is we more or less try to write a polynomial which by which binds to register states in two

different times but the FRA reduction I think it works over is the columns which makes it much more efficient the same way as reduction from rank one constraint system to quartz makes snart's quite efficient so I think this is going to be the most difficult part I personally didn't get this is the point which I don't yet know and I think is going to be most interesting and this is actually what makes starts efficient how do you how do you say that it's fries as

in Fri this is a proximity proof that you're like to encoding so that in codings of two elements are close if and only if your elements which we encode it falls in what you do is you encode following Omicron Ceti sounds like this the same is with notes rating rapping history system is more or less okay can be easily done reduction to takes a

lot of time but it's but it's still doable but I think production to you the next step is much more difficult in snart sistema de castas directly Civ group system I mean the polynomial division [Music] I mean after coops you use one of the proof systems either the cross or pinnacle and here and after the ear representation you go directly into the starts nice to use I guess out of curiosity you say that you're working on

something now is that is any of that going to be open source are you leveraging some open source stuff okay yeah I should release me maybe next week if I if I'm in time before okay yeah release it when it's ready conference driven development doesn't work so well well I mean almost everything works somewhere should be extended okay because decided yet and should have

focus on overall on starts my ultimate goal is to have some kind of recursive system like chain and so I'm sure so when I could answer your question first with another question what is like what is the difference or what it why is it that you're drawing a line in the sand between stark and Aurora train systems like stocks and Stark is more or less

we presented both ways well I think just every practical problem can be represented in both ways and I think air radar can be transformed into rain forecast rating system of necessary but in principle I think it starts with recent advancements in start friendly hash functions on a practical application side may be more useful because Aurora is easy to write because your weed actually is much easier to write and make up emitted the red content I thought I thought a I want CS was a sub-sub constraint of air as an

enormous torques that he bits us on says air is Susan a more generalized way yes yeah it's true in principle because rank one constraint system and some principle set of swing mattresses which when you multiply them gives you efficiently rank two constraints so your constraint over each variable is at maximum quadratic with air your constraints over the set of registers over two adjacent steps of computation are in principle of degree M which of degree 2 n where n is a number of registers which is in this sense it's

more general figure so it allows you to build higher degree constructions with higher degree in States but I think this is I think in principle you can take the air and convert it to rank on concerns concerning system it's just a number of constraints will equate then the question is how efficient it is well the question of efficiency your initial constraint system but how efficiently you can make this improve and starts letting start so much more efficient I think you say else is more easy preferable and people work with

starts and in the settings that most life is they will be much easier to verify in a smart hangers but if you build something separate like completely separate blockchain you can do anything yeah theoretical complexity measures right okay yeah so I guess also to answer your question now Mirko why you know why are we focusing on Starks and not Aurora or anything else I think in the you know the beginning we well we

were still the beginning it's the second session but we were we were kind of brought into the to this channel to say okay let's learn the case Starks I think Ana changed the name now to just ZK study group which for me personally I like I think that there's probably complementary you know subsets of each of these approaches each of these systems so I don't know that we're you know focusing only on stark and if you want to talk about something else you you better find another group that that's not the point it was just the first sessions and trying to do something you know before the holiday time is upon us meant that okay we're doing a high-level and we're focusing first on Stark while we build up build

up you know kind of a baseline of people who would like to present topics and lead these sessions so I think I think in any case Starks are related reading reading quickly through the introduction of tea or paper they do say or is built I mean or improving complements the work on Starks and that is just faster yeah sure coolant and that utimately with the uses is ILP interactive Oracle proof so maybe one session that we could do when we're when we feel more comfortable with Starks

which I feel like we're getting to slowly is to talk about that particular thing right Interactive Oracle group which I think it helps explain or at least helps understand the difference between normal Starks and what or is doing or were the efficiency stems from right yeah that was one of the kind of the jabs quote-unquote jobs that I heard you like say in that first talk to coda that if the proof time is so long that you are you're having more blocks

advanced then you're where there's not a big difference between proving a block and when the next block arrives and what are you doing yeah well if you want well first of all making the portal we just uses cleric so starts or whatever to prove the block correctness yes it's quite pointless just if you don't have that consensus if you prefer it's efficient everyone can make blocks just empty blocks just work in the settings the you see cerium as a consensus source and use

snark Starks or whatever to make some some practical in Tulsa so it's white well I don't know if it's even necessary without some well easily have consensus mechanism basic idea is to get rid of let's say you have a Bitcoin blockchain was their transaction in the transaction graph and you can basically get rid of them and only keeps the you takes all set more or less and I mean in a practical setting the issue in stadium or Bitcoin the largest set of data in there is just

[Applause] well in for example assume state is not hundreds of gigabytes it's just a gigabyte of - it's the amount of data required for you to take executed on a latest state so all amount of data which is required to just makes an extraction point say you tick so said as a small [Music] coin client chips is the index and all blocks which you don't want to remove in principle if you introduce the same array sinking liters or whatever to sync with the network you don't need to

download every block and apply them to your index you can just take the accumulator take a set of you take zoe's and just say well this is a accumulator which commits and which is consistent you can get it from every participant of the network you can say take any form of the accumulator and say okay this is my accumulator this is my UT Exocet you can just directly download it checks at zibolski respond check to the accumulator corresponds to the latest polling current consensus and that's it you can sync using I'm just interested in this thing in theory theory

get a Sicilian blood transform mm-hmm well I mean if you don't have the consensus some other way you don't need well I mean you need the consensus first and basically consensus is the first part which is required to even accept your proof of wallet state transition in this block without the consensus of these constructions are quite pointless and we figure out the consensus you just can use much simpler tricks and snacks and starts to verify to reduce this amount of data which clients need to keep at the point of I mean in every

book she first sounds sounds like a like a reasonable statement I don't I don't think I can unpack that further right now I'm I'm gonna end it here I'm gonna end the recording here if we want to keep talking we can but just