FRI vs. KZG: Does Field Size Matter? | Eli Ben-Sasson - StarkWare

I'll just use this hey everyone welcome to the Trident stage eth Denver 2024 um I'd like to welcome to the stage Ellie Ben Sasson he's the co-founder and CEO of starkware the talk is titled Fry versus kzg does fieldside matter thank you so um I'll talk about this topic um and the tldr is that already today Starks dominate the ethereum scaling scene and uh thanks to recent breakthroughs like Circle Starks and stew which we just open sourced yesterday um Starks are going to become the new gold standard for scaling ethereum um so yesterday we released um the next phase in scaling uh in validity proof technology it is uh stew based on the meren 31-bit field with an improved Cairo virtual machine based on the mathematical breakthrough of circle Stark that was published just last week joint work by polygon zero and starware um going to use Gare lookup and mix degree trace and a lot of other bells and whistles making it yet again uh pretty darn good Pro and uh if you think about the landscape today in terms of proving technology they're roughly for things deployed in production not not just for things that are out there in academic research so they're roughly three categories of commitment schemes um fry based uh which uh most of the Stark systems lie in um inner product arguments like bulletproofspeaking.com um things like plon Roth 16 and um a bunch of teams and over time I mean it used to be that kzg dominated almost everything in the ZK and scalability space but over time fry Bay systems have been emerging and again basically my point is I think you'll see this trend of moving more towards fry based Starks uh as time goes on and why is this so so you could uh consider the efficiency of one of the main bottlenecks in constructing a proof which is to do a polinomial commitment scheme and we can do a head to-head uh kind of competition uh measuring the number of clock Cycles to commit to a word a word being 32 bits inside of stream of length roughly one Mega word so two to the 20 words that's roughly a million words and now we can measure the load um in the commitment scheme for per each word and let's um compare fry and kzg so this is based on some some comparisons that I already presented in the past both at Stark at home and at the Stanford blockchain conference uh earlier I mean this past summer so the current um status is that if you look at non vectorized instruction sets so kzg under the even most ideal algorithms that we know of today you're going to have to do roughly a cost of word length so that's 32 divided by the logarithm of the stream in our case it's 20 so 32 divided by 20 number of group operations each group operations at best and you have to do a lot of fancy work to make that work uh you need to do six modular multiplications for doing elliptic curve uh operation and each one of those roughly cost 32 uh sorry 38 to 40 clock Cycles on the other hand if you look at something like 32 31 um bit uh fry um you'll see that you pay for the fft roughly 1 half of the blowup Factor times logarithm time 20 in our case the blowup factor is uh is going to be two so half * 2 * 20 equals 10 and that's the number of clock cycles per word plus blowup Factor times hash so if you use something like uh Blake that's going to be 80 clock Cycles you see the most dominating Factor here is going to be the hashes and you have to pay two of them so out of the 220 Cycles 160 belong to the hashing however if you move to um vectorized instruction sets which are today common in all uh CPUs um then the picture changes pretty drastically because kzg probably doesn't vectorize all that well whereas uh um something like a 31 bit field fry with an fft does vectorize extremely well and then you get that each modular multiplication on the small field is oneir of a clock cycle amortised so you get a total of 31 clock Cycles versus something that is probably going to be around 10 times greater than that so you have like 10 times greater efficiency but the story doesn't end there um sorry um in practice when everything is combined if you look at fry system um to best of my knowledge this is along some of the world records even though it's like four years old so we already showed four years ago um a construction over a 64-bit field that proves 100,000 rescue hashes in less than 10 seconds on a quad core with 16 gigb RAM and this was at the time 20 times faster than the fastest known kzg based uh system snark and we still don't know what is the best proving time for something similar you know it would be a good measurement to do head by head take your favorite algebraic hashing function and see how long does it take to prove 100,000 iterations of a hash on some simple um Hardware it's probably not going to be all that simple anyways um but fry Bay systems or Starks have a bunch of other uh advantages over uh snarks they have fastest commitment time they're agile in the sense that they work overall all finite fields from binary all the way to large Prime Fields they are safest because they have no trusted setup meaning they're transparent proof systems their security assumptions really revolve only around the existence of uh some secure um hash function and in particular they're also postquantum secure kcg does have advantages snarks they have very short proof length under 200 bytes and they have additive properties which well it's a double-edged swort you can use them for doing things like folding and compressing things but they also uh this additivity is related to things like postquantum uh um insecurity so now this theory that that says that um fry Bay systems over small fields are going to be better is not just something that we believe in on the mathematical or you know back of the envelope side we're also committing oursel to it so for the last six years we've been using basically one prover uh that is Stone which stands for Stark one it is our first Stark based proving system and now we're moving uh slowly towards uh um stew which is the second Stark prover and I want to tell you a little bit about this because it's a pretty exciting um so what it's going to give you is much faster proving technology it's going to reduce the total computation cost um meaning you pay less dollars for proving stuff and it's going to have be seamlessly integrated with Stark net which means if you start deploying and building in Cairo on Stark net tomorrow you will get all of these benefits uh without uh really any modification so let's uh uh look a little bit under the hood what is uh what is stew so first of all let's talk about the 31-bit meren prime field so a meren prime has the form 2 to the K minus one and if you take K to be 31 you get the number 2 to the 31 minus 1 it is a prime number and it has a lot of uh cool properties to it I mean meren the great meren already found it probably a couple of hundred years ago and it gives you so moving to 32bit fields in our world where all computer devices you know off the shelf operate in 32-bit instructions in the fastest way means that that you get a lot of benefits one the smaller field size allows you to get your arithmetization better done because when you have large Fields you need to pack things into Big Field elements and it's inconvenient um it fits inside a computer instruction word and you even have a nice modular reductions because 2 to the 31 which in bitwise representation is just one with a bunch of zeros um happens to equal one so if you have you know if you do have the two to the if you have your 32nd bit turned on you can sort of replace that with the lowest bit turned on and that's how you do modulus so it's a very simple modular instruction and there are a lot of uh nice benefits for doing uh fast implementations both on CPUs and gpus uh for basic field operations such as modular addition and multiplication for doing ffts or NTS and for computing things like uh Stark friendly hashes like pedon um one example is if you you take uh if you take 2 32bit numbers and you just concatenate them together sorry two 31 bit numbers what you're looking at is literally uh equivalent to their sum modul um uh this Prime so uh you can concatenation at least of two uh such field members does represent the addition of them and you can do a lot of such tricks so let me tell you a little bit about this exciting uh breakthrough joint work by polygon and star quare um UL reabok from polygon David levit and Shaka papini from our team at starware uh really really spectacular result um so Circle start and the circle refers to the good old Circle that we all know and love so let's see how we get there um for Starks to work best they require a group that is of size 2 to the K we often talk about an fft friendly domain and it turns out that the multiplicative group usually we take fields and work with their multiplicative groups and find subgroups inside those multiplicative groups but for that you look you have to look at the factorization of the Prime minus one in our case that would be 2 to the 31 minus 2 and 2 to the 31 minus 2 does not have very large factors of two and in fact two is the largest power too that divides it which means you don't have uh the nice multiplicative groups that you would like now if you go to the degree to extension of meren you already have a very nice uh fft friendly group of size uh 2 to the 31 however now you'll be needing to work with uh basically um 62 bit field elements and doing all your operations so and that's a bit inconvenient we would like to get all the benefits of the meren arithmetic uh but working only over the meren field so one one possible solution is to use um some work that we did a few years ago um at starkware called elliptic curve Starks which basically replaces the group the multiplicative group of a finite field with an elliptic curve group defined over that finite field the nice thing that there's a is that there's an abundance of uh elliptic groups um of all sorts and well not of all sizes but uh there's a pretty large variety of them within the Hass whale bound um so you can find one that has a a nice subgroup of size 2 to the K which is what you want however this would be relatively complicated the lipic curves are a little bit more complex than some simpler curves that we all know in love so enter the circle curve or Circle Starks they operate over the genus zero curve that is the circle defined over M31 so what does it look like you take the good old Circle which is the set of pairs of points such that x^2 + y^2 = 1 in our case modul the meren prime and there's a bunch of examples of such number such points on the group on the uh on the circle so 1 z uh minus one0 which in our case equals uh 2 31 - 2 and uh also if you take the point that is 2 to the 15 2 to the 15 that thing if you square each one and sum them up you get one modu of the meren Prime so here are a few numbers a few points on this group and it turns out that there are exactly well there are two to the 31 groups that reside um inside the uh that are basically that are defined over the meren field meaning that the pairs X and Y both of them belong to the mercen field and it forms a group I think actually the group is a of half the size but I'm confusing myself now so it's at least of size two to the 30 um and you have a very nice operation for addition so that's the meren 31 field uh there's going to be a talk by shakar Soka um either later today or tomorrow and by OK I think it's going to be tomorrow at the Stark Meetup um sharing a lot more details about the math behind it and about uh looking deeper into stew which is already open sourced uh by now so um what are the implications this gives you the very fastest prover using new math and it's going to be crazy efficient we believe it's going to be something like a 100 times more efficient end to end than the current Stone proof and the current Stone Pro is the among the fastest proving systems end to end for production systems today today so we are extremely excited about the potential um of Stu to go even further and scaling ethereum for starnet what you need to know is that if you ride in Cairo you'll get all of this good goodness for free because it will just be adapted seamlessly this will lead to lower fees and to quicker finality hopefully we'll start seeing it already helping us with finality and reducing latency um this year in 202 for and another nice thing is that it is open source written in Rust and the open source is already um open today so you can just Google first St under starware and you'll find it under starware Libs and you can start hacking or using it um so I'll repeat the tldr Starks dominate the ethereum scaling scene already today with more and more teams moving over to using fry based systems um that are safer but also more efficient and the recent breakthroughs of circle Stark and 2 will become the new gold standard for scaling ethereum not just that starnet probably also uh um polygon zero and other teams are going to adapt to them and then we'll see a lot more in the industry so this is as good a time as ever it's the second best time to start uh looking into Stark net and CYO the first best time was probably you know a year ago but still we're early enough in the game so you can take this QR code follow the links join the ecosystem thank you very much