Episode 303 - A Dive into Binius with Ulvetanna

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online this week we chat with Jim and Rody from vatana my co-host for this one is Brendan from polygon zero we discuss ulana's work on the zk/ hardware intersection and then dive in to the new proving system Bas Bas is a hardware optimized snark based on towers of

binary Fields this work brings together a number of breakthroughs in ZK that have happened in the last few years specifically it continues the trend towards the use of smaller Fields it's inspired by the development of new lookup arguments the work on multi-linear provs and some check as well as the use of recursive composition in snarks the ZK Community has been very excited about this work so it was great to get a chance to dive in now before we kick off I want to let you know about our upcoming multi-week virtual event ZK hack 4 starting on January 16th and running until February 6th 2024 we will be hosting weekly workshops with top teams in ZK showcasing the state-of-the-art in tooling for ZK

Builders every week we ALS Al host a ZK puzzle hacking competition in it we share a ZK system that has something wrong with it you are meant to find the bug and hack the protocol the fastest hacker will make their way to the top of the ZK hack leaderboard there you can find prizes and Glory now this is our fourth time running this event series The ZK hack online series is not a hackathon but rather it's a chance to learn the latest in ZK tools with members of the ZK Haack Community as well as learn the intricacies of ZK sec through the puzzle hacking competition and because it runs over a few weeks participants often make friends find Future colleagues or co-founders and we really get a chance to dive into the ZK

world together the event is free and open to all I've added the link on our website please join the mailing list so that we can let you know when we have more info to share about the event also be sure to join our Discord that's where all communication around this event will be happening so yeah hope to see you there now Tanya we'll share a little bit about this week's sponsor Alo is a new layer one blockchain that achieves the programmability of ethereum the privacy of zcash and the scalability of a rollup driven by a mission for a truly secure internet Alo has interwoven zero knowledge proofs into every facet of their stack resulting in a vertically integrated layer one blockchain that's unparalleled in its approach Alo is ZK by Design dive into their programming

language Leo and see what permissionless development looks like offering boundless opportunities for developers and innovators to build ZK apps as Alo is gearing up for their main net launch in q1 this is an invitation to be part of a transformational ZK Journey dive deeper and discover more about Alo at al.org and now here's our [Music] episode today I'm here with Jim and ratty from ol vatana welcome to the show Jim welcome R thanks Anna it's great to be here hey everybody greetings we also have Brandon farmer of polygon zero with us today as a co-host hi Brandon hey it's an

honor you may also know Brendan as one of the hosts of the ZK whiteboard sessions which we created last year so it's really fun to have you on this one so this interview came about because there is some recently released research the Bas work that the ZK Community has been really excited about now for me it was a bit funny when I saw it because I thought of Il vatana as a purely Hardware focused company and now I was seeing that it was almost like a snark system or some sort of more more on the cryptography side type of work had come out of the group so yeah I was a bit confused why you're doing this kind of work I'm really excited to dive into that work but I think as a starting

point it would be great to get to know the two of you R do you want to introduce yourself yeah i' be glad to introduce myself hi everybody my name is Ry and I'm co-founder and CEO of tovana at tovana I manage technology team and I spent past 15 years doing Hardware design across different Industries it's probably worth noting that I spent last seven or eight years in quantitative finance an industry which is also known as high frequency trading or algorithmic trading where I use Hardware acceleration to improve efficiency of market making I would let Jim introduce himself thanks yeah Jim what about you I'm Jim I have

been working in the blockchain space in some capacity or another for most the past 10 years I was at coinbase doing some combination of backend engineering and crypto Integrations and protocol engineering and then in around 2018 got really excited about all the innovation in the production of cryptographic protocols uh spent a couple years in school studying cryptography and you know ZK and proof systems and stuff also have always loved systems engineering and embedded systems and when I heard about the notion of Hardware acceleration for zero knowledge compute that both resonated immediately as as a

necessary thing and probably something that would be really fun to work on so um got in touch and uh it's been a journey ever since cool did you actually study ZK at University was there like programs teaching this I did a masters in computer science the concentration was some combination of computer science theory there's only like so many cryptography classes you can take I took exactly one but there's a whole lot of adjacent uh things that you need to learn so especially pertinent to what we're going to talk about today I took a class in coding Theory which I thought was one of like the coolest things that I studied um and was really necessary to be able to do some of the work that that we're doing now but I also so like

distributed systems and operating systems and classical algorithms um well actually I mean the question was the zero knowledge side of it like zero knowledge cryptography is that being taught in schools that's what I'm curious about oh yeah there was one Advanced cryptography class which spent maybe a week or two maybe a couple lectures talking about zero knowledge and and proof systems um I mean this was at Stanford so the you know you know the cryptography Department there is clearly very up todate on everything um and they do a great job but yeah I guess that's a good point even like the advanced cryptography class it's only a small fraction of what's happening in the

theoretical academic Community got it let's talk about UL Venna I want to know where the project comes from you've sort of mentioned Hardware Rody and I can kind of see where the initial thought for this or like some of your background maybe would have led to to having more of a hardware Focus what is vatana it's a it's a it's a good presumption here so vatana is a company which aims to accelerate zero knowledge proof by applying Hardware software code design and for the sake of wider understanding especially your audience I just spent a moment talking about Hardware software Cod design so essentially we are looking at accelerating Hardware proofs in both

software and Hardware components of it we believe that each proof can be decomposed in sort of sequential part of it which is more CPU friendly and more paralyzable part of it which is more Hardware friendly and inherently L native to Hardware execution we really believe that zero knowledge proof requires dedicated custom compute for its full adoption and for the full you know achievement of this industry the reason we think this C roots in history I would probably just mention a few of other compute problems which are very interesting for us such as computer networks computer Graphics computer

storage which then led to cloud computing so all of these verticals literally arise from ability to have dedicated compute which then mapped algorithms better to it which in consequence allowed for scaling and mass adoption so we are just trying to bring this into zero knowledge space and we believe that the best way to do it when there is software and Hardware codesign I wonder like so I did an episode series actually on Z prize and the winners of that competition it was kind of like a look at hardware and even before that I had done an episode with supranational who was also a hardware focused company I'll add the links to those two episodes

in the show notes but I remember there like we were introduced to the concept of like A6 fpgas gpus CPUs what kind of area is vatana focused on like in the hardware context is it all of it or is it like one of these short term we are probably looking in just a few of these and I will explain motivation um motivation is really to learn a little bit more by accelerating proofs end to end and we chose technology for our gen one server which is something that we are very familiar with and which is something which is highly Rec configurable and these are the fpgas one of the primary reasons we chose fpgas is due to their reconfigurability and currently research

in zero knowledge space is moving really fast so we want you to have a platform that we want to alter algorithms pretty quickly stay on top all the Innovations but also be able to integrate proofs end to endend so it was in a sense a learning platform for us this already has changed with our second generation server where we are looking more into heterogeneous comput again to just bring discussion a little bit back what I said before we don't think that there will be a single type of compute which is going to be the solution for a tire proof system so we are going to be looking for keeping you know sequential parts of the compute in some sort of CPU and moving you know paralyzable portions of compute into

Hardware I would also mention all the names that you mentioned before and Z price effort these are you know great contributors to our our ecosystem and big shout out to everybody there who is really trying to accelerate zero knowledge proofs using Hardware but we are looking really the full stack of this and you will pretty quickly connect the dots why a project like beus was possible to happen within Olana I see we never looked at zero knowledge proof as just compute Centric world we really looked end to end and we approach this from pretty much five aspects of different efforts happening within the company which are all yielding the overall acceleration of the proof top

down we have inhouse cryptographic research and if you look even our blog post or like you know Twitter activity you will see that beus wasn't the first purely cryptographic um contribution from from our team so essentially we do have in-house uh cryptographic research we believe that we will only be efficient and successful at proof acceleration if we are able to understand these things inside out and this is the effort that Jim leads so I will let him talk about this a little bit later then on top of that we have a ZK sort of software development team which is accelerating proves in the software space and connecting them with

our Hardware or API or whatever you want to call this acceleration layer then we have a little bit lower layer software development team which is system software and it has to do with the API design you know all the sort of lowlevel software which is generally required in high performance compute and which directly talks to the hardware very important obviously for our work is Hardware team and at Allana we probably do the same thing like our competitors or you know other Hardware teams that you mentioned above so we are working on accelerating cryptographic Primitives in Hardware additional to us we also have infrastructure team which deals with

Data Center rollouts and skillability cyber security and everything else which is required when you run a private Cloud so now if I can just get back you know the toletana will look things from the top level of cryptography all the way to the hardware acceleration to the bare metal got it it sounds I mean another team that we didn't mention but I want to just throw out there is ingonyama so ZK validator is an investor in ingonyama just full disclosure I sort of know their proposal quite a bit better are you guys in the same category or would you put yourselves as different from ingonyama right for the full fairness here in ecosystem I would also like to bring up competitors such as cic and fabric and ponos and a few other teams

which are participating in these ecosystems I'm not honestly very much aware how much of the cryptographic efforts this team are doing that also goes for Zed price should I say Z price but you know in Australia we say Z price say Z price too but oops Yeah with Z price we we are you know going to continue um teams such as you know jump trading or Jane Street they were focusing also on on the on the acceleration I think at alvana we put definitely bigger stress on the cryptographic research so I think that is one differentiator resistance right now and there is also this difference if Hardware teams are considering public

cloud and public Cloud resources or private Cloud there are different definitely reasons why we decided pretty early on in the process to go with a private Cloud I think one of very obvious reasons again going back to the speed at which zero knowledge proof algorithms are changing we have to have better better control over hardware and better flexibility to really utilize Hardware until it's maximum performance so that we can achieve maximum efficiency yeah with respect to the Z prize competition it was a really awesome effort that uh you know yielded great results especially I think on the GPU side and got more people involved but uh when we looked at the submissions

and looked at the structure of the competition there are some notable uh design decisions about the competition that I think validated our approach of doing endtoend analysis of the systems before acceleration so the Z prize competition focused on primarily two computational bottlenecks the multiscalar multiplication problem for uh elliptic curve snarks and the NTTS uh both for elliptic curve snarks and what I'm going to call starish protocols so you know roughly we have snarks from elliptic curve assumptions and snarks that are sort of fry based or from linear codes and hash functions so uh for full generality I'll call those

starish protocols and those are computational bottlenecks but when you actually go and when we kind of from first principles profiled the provs that are out there there are several other computational bottlenecks and depending on the system they could be even larger problems so for many of the starish protocols that are recursion friendly like Pony 2 you end up using expensive hash functions like Poseidon and actually the merization was the number one bottleneck that we found when we you know go and profile these these systems from the source code there's also another you know layer of computation which is this uh quotient polinomial computation which is sort of you take a

bunch of polinomial and you evaluate it on a number of points and both of these actually turn out to be significant bottleneck so my point is that uh the Z prize was a really good first attempt to introduce Hardware acceleration into the space but it's it's sort of far from what needs to be done to produce an overall efficient system that makes sense maybe you could talk about sort of take a step back I think that there's this misconception about Hardware that the hard part is just writing the things that we do in software on on CPUs right now for fpgas and that's like the real Challenge and if we could just do that then we would have these maximally efficient provs um and I actually don't

think that that's the case because we have worldclass Hardware people that work at all these companies and actually writing uh provs and for for fpgas is is not that difficult relative to overcoming things like bandwidth limitations of moving things between CPU and fpga you know changing snark Primitives that require huge changes or or throwing out huge amounts of Hardware code that's sensitive to those components and and and so maybe we we could just talk a little bit about the landscape uh and the challenges that sort of come up when building for Hardware yeah I think this is this is excellent this is excellent observation Brendan this is all absolutely correct so first of all when we started accelerating protocols such

as Cluny 2 you know I I bet you are familiar with that one uh we identified issues associated with hashing with poson hasher to use more precise terms and but also another aspect that you mention is the data movement so I really want to explain this a little bit to the level of the detail that people understand when we talk about Hardware acceleration currently most of provers operate under general purpose compute which are CPUs and the whole data of the proof system is contained within the system memory and the and the CPU of the system as soon as you are introducing an accelerator again historically could have been graphic accelerator or network accelerator you do need to move data outside of CPU most likely using PCI

protocol so now you are in this tradeoff space where you need to look in the data it takes to hit the accelerator time to compute and result to come back this is fundamental problem of Hardware software code design simp simply because there is huge memory bottleneck of the today's progress this total memory layout comes from the size of the trace that we identifi pretty early on in the process and this was actually one of the initiator of our research that eventually ended up with beus another point I want to make is that zkp space starish one to refer to gy term shifted a little bit to usage of non-traditional hashers so we have padon

which is not a typical Hesh function that was used in symmetric cryptography before it was primarily designed for Prime fields to be recursion friendly such hashers are not really Hardware friendly not very compute friendly so we have a problem of how many of these we can instantiate in state-ofthe-art hardware and how much we are able to paralyze the Pro system so you are hitting the nail here essentially data movement is a massive problem and once we finished accelerating basic Primitives we started integrated the whole proof together that is where real learning happen and this is where we started to redraw the software Hardware boundaries it's interesting because when we think about generating a proof we perform some computation and then we

like you said we generate the trace we're basically filling out this huge Matrix um full of finite field values and that actually ends up being huge and so if we you know send that to like an NT or like a hashing module and it's really really fast on the ch but it takes forever to to get back to the CPU that's obviously a real challenge when we think about latency so yeah I think that just sort of sets the stage for for Bas and white support maybe actually now might be a good chance to Define Bas and what it is because I had this thought that it was almost like a new proving system but actually what is BAS uh you are right Bas is a new proving system

Bas uses fundamentally different underlying mathematical Primitives which are are called binary Fields um mathematically to be more precise these are finite fields of characteristic to and this is not new to cryptography as a space at all in fact it's um sort of predates probably the use of prime fields in in a lot of symmetric Primitives uh and it's also not necessarily new to the ZK space uh the original fry protocol and the original Stark protocol were actually both defined for binary fields and and I'll get to why that essentially got dropped as a thread of sort of research and production effort but we began from the

point of view of okay we're running into all these bottlenecks that we just mentioned with the fpgas we're running into the issue that the hash functions that are used for merization which is Poseidon is not compute friendly and we're running into this issue of huge memory requirements and bandwidth limitation and moving data between the accelery and the host like from the research side what is on the horizon that could solve these problems and what could we maybe create here that can solve these issues and so we started to wonder why binary Fields weren't adopted that was the beginning of this uh research effort now why weren't they actually now I'm so curious you're sort

of saying early fry had sort of gone in that direction and then dropped it I want to know now what stopped people from using it yeah that's a great question that took us certainly some time to figure out so fry is a really elegant protocol and it works very nicely over binary Fields what doesn't work so well is Starks um so we read the original Stark paper which is the you know scalable transparent arguments of knowledge and there's uh a few things that that make prime Fields really nice here and especially made Prime Fields nice in 2019 and I think to to jump ahead in the story essentially that

actually in my mind made sense to use prime fields in 2018 or 2019 whenever these teams were trying to build this stuff but uh a few years later we have developed a lot more techniques that make Bas possible so the first issue is that the Stark protocol uses okay this is where we need to get into the math you have a trace of let's say your virtual machine execution cycle so if you're emulating a ZK evm then maybe each row of this Matrix is a ZK evm like execution step mathematically each row of the trace for a prime field Stark is mapped to a cyclic subgroup or a cyclic

group and there is a really nice way to relate the adjacent rows of a trace in this model of having a cyclic group in the Stark protocol the rows of the trace were laid out on what's known as a F2 aine Subspace and there's just not a nice way of relating adjacent rows of the trace they developed some techniques to be honest I don't fully understand uh what the Stark paper was proposing but we looked at this and decided that that wasn't the way to go now there's been a lot of research recently into multi linear provs like hyperplan and breakdown and these sort of what we call

sum Che based protocols where the trace is laid out on another mathematical structure which is the Boolean hyper Cube and this ultimately provided the solution to that challenge so if we can marry the idea of binary Fields with multi-linear provs that was the first way to overcome one of the challenges of starks so you just said the work on Su checks and the multi-linear approver is this the change that had needed to happen for the new work to make sense or is there any other like developments yeah I'm just wondering if anything we're familiar with like lookup tables or folding schemes or anything like that lookup tables is one right yeah so I would say the big unlocks here

are some check based protocols and multilinear protocols lookups and the the idea here being that if you don't have lookups having native integer addition and multiplication native in air quotes it is really powerful and in binary Fields what you get is native exor exclusive or operation but the multiplication isn't isn't really that useful to most computations so lookups are really powerful here um also the new paradigm of using a lot of recursive composition uh another issue is that if you were trying to verify a binary field Stark on the evf um that wouldn't be

that efficient because the gas costs to do binary field operations are not amortized or subsidized in any way unlike both um modular arithmetic and elliptic curve operations but we now live in a world where people extensively use recursive composition so you would take you know a stark and compress it to a point where it can then be verified with an elliptic curve snark and that's what ends up on chain so that's another unlock for us and the last one is this trend towards small fields which I I think a lot of people who aren't intimately familiar misunderstand maybe what one of the key Innovations here is

so if you have a proof system like plony 2 or or what risk zero is doing that are using 32 or 64-bit Fields you think okay great you went from 256 to 64 and that's sort of right but actually for security you're still using large fields of 128 or 192 bits but they're using what's mathematically known as a field extension so you you take a small field and then you construct a bigger field that's two or four two or three or four times the size out of that and really this construction of doing starkisha and extension fields for

cryptographic security is exactly what we need and this was not introduced in the original Stark paper they actually starkware did introduce it my view is the first time I saw this appear was in the eth Stark documentation but if we can construct Bas we construct Bas from binary fields and their extensions their field extensions so you take the smallest field which is F2 meaning the the field with zero and one as the only elements and you can construct an extension field which is uh 2 bits and then you construct an extension of that which is 4 bits you construct an extension of that which is 8 and another

16 32 64 128 and when you get up to 128 that provides enough cryptographic security to instantiate the protocol well not only that right like to me the the big innovation is that we can sort of get around embedding overhead right because like with plony 2 we move to a 64-bit field but actually a lot of the values that we care about don't take up 64 bits like we do a bit decomposition for certain things but we're still from the perspective of the commitment we're still paying to commit the full 64 bits and so I think a really interesting part of Bas is that we have this flexibility

where if you're working with bits you only pay in some sense for like F2 and same with a bite or you know whatever sort sort of variable size uh value that you're committing to which I think is really cool yeah absolutely that's one of if not like the key contribution from the research side here is what we term embedding overhead which is as Brendan said when you take a small value that you need in your circuit representation and you have to Pat it with a lot of zeros to fit the field that you're working in and uh this is another one of the reasons that Starks over binary Fields didn't make as much sense a few

years ago which is if you have to pay for embedding overhead there's a less pronounced difference if you're using a 32-bit binary field or a 32-bit Prime field you're still padding with a lot of zeros however because binary Fields have this tower construction which gives you this sort of sequence of field extensions and the fact that F2 is literally the smallest finite field what we felt was important to capture was to design a proof system where you can do F2 operations but not have to pay the embedding overhead at least in the commitment phase which is the most computationally expensive phase of of producing the proof and the original

Stark protocol it's it's very difficult without some check techniques to eliminate this embedding overhead and this is a subtle point but mathematically when you're producing a stark you do a lot of NS number theoretic transforms and this actually serves two distinct purposes in the Stark protocol one is that it's an error correcting code formly a read Solomon code to uh do these NTTS and to perform a low deegree extension operation with them but it serves another purpose which is actually this is uh what's known as The Vanishing argument this is how you prove that some constraints hold over the entire trace and you actually need to view the values at as the evaluations of some polinomial over a large domain

and when you have a sum check based protocol like bineas this decouples the purpose of the NTT from the vanishing argument in a way that you know longer need to pay this embedding overhead and this was basically the big unlock that lets us reduce the bandwidth to and from the accelerator reduce the overall system memory usage and also do more efficient arithmetic it's much more efficient to do arithmetic from elements of these small Fields like the 8bit binary field than a 32-bit binary field so if you can use the absolute smallest field you need for any given part of your proof system there's just a lot of efficiency

advantages would you call Bas now a stark then or is it a snark still like I know that those definitions are kind of like melding but yeah what kind of proving system is it it it is a snark um I I the way I I find it more useful to talk about elliptic curve snarks and uh snarks from linear codes and hash functions this is what I'm referring to as starish protocols okay so people think that like the things that define Starks as this transparency property uh and and the fact that they use fry which was a differentiator when the Stark paper was released but now we have other transparent star snarks um technically

what I see as the differentiator I mean Stark refers to a very specific construction but it's actually the s in snark vers Stark which is for snark it's succinctness for Stark it's uh scalability and uh formally what this means is that the entire circuit description of the the virtual machine that your Stark is proving execution of can be made public to the verifier uh and there's no pre-processing step whereas a snark has a pre-processing step but in in the systems that everyone uses they're all snarks there's a pre-processing step so I think it's more valuable to talk about elliptic curve snarks and starish protocols okay in this case though does Bas have the

pre-processing step then yes still okay if you didn't want to you could make a version of Bas that's scalable and doesn't have pre-processing that would do sort of the same thing as Stark so Bas supports an arithmetization that is similar to plon and this is called a plish AR ization where you have a trace Matrix and you have Global copy constraints but Bas also supports the air arithmetization which is what Starks use and there's tradeoffs between them the permutation argument that plonc uses to enforce Global copy constraints is expensive so in some cases if you are designing a virtual machine and you can avoid that you might want to use the air

arithmetization so Phineas supports both of them if you use air arithmetization you could produce something that's very similar to a Stark in its properties uh I still think it's more useful to call it a starish protocol though do we have to create like this denar like is there just a combo word or we just I know that the s means something it's two s's so it's SS n t a r k something like that it's it's more complicated than that too because according to certain academics succinct only means formally poly logarithmic uh verification time and to other academics it means sublinear uh verification time

so there's I think I just call everything a snark now and uh and you can get into the details of the particular properties that they have we also hope that this discussion will be IR relevant one day this will be known as binary proof and that's it oh that's B so far we've talked about Bas and the fact that it uses all of these breakthroughs and incorporates it to create like a snark over binary Fields but why does this have anything to do with Hardware like I know earlier on you kind of laid the groundwork for why you need something different in Hardware but you created this system I'm assuming it's efficient it's fat like but yeah

why does that make it easier to work with Hardware so the reason is that binary field operations are far more efficient in Hardware this is something that we knew ahead of time this is known within the cryptographic community there's a long line of work in efficient elliptic curves over binary Fields the AES symmetric you know encryption scheme which is a standard uses binary fields and and there's computational efficiency benefits throughout the process of developing Bas which was uh on the research side in effort uh with myself and our brilliant researcher Ben Diamond who did a lot of the theoretical work and is on the paper but we also

collaborated closely with the hardware team to prototype these underlying Primitives throughout the process so that we knew we were on the right track um and that was really valuable because binary Fields actually have many different ways of representing and Computing with them and so we had to both find the right form of binary fields to use and that was very much informed by the the hardware produ types that Rody and his team were able to produce so I'll let Rody talk about some of that that process maybe just before I enter deeply into this I will offer a little bit of retrospective from the tech team this was retrospective for cryptography team and you you know

essentially on Hardware side we are complaining oh it takes just too much time to ship this whole compute Trace to the accelerator what if we could go below essentially golden loock 64 which was plunky 2 and Cluny 3 which is mercen 31 and risk zero which is baby bear 31 what if we can go you know all the way to the minimum Quantum of information which is one bit and the guys are like yeah they're binary fields and like okay let's investigate binary Fields now the guys go like well there is a very cool trick with binary fields which is this pecking which reduces the embedded overhead meaning if I have one bit CPU flag such as overflow flag I'm still

embedding it into 64 bits in plony 2 or 31 bit in plony 3 and we like great this is reducing overall memory auto box but guess what binary fields are Hardware arithmetic friendly which is one of the reasons that sha as are essentially implemented in this logic if we can call this oi cryptography or symmetric cryptography and then on the hardware side all the alarms light and we say well we can now use the hashers which are essentially the hashers of the symmetric cryptography which is way more Hardware friendly and way better in terms of throughput performance and everything else so fundamental

limitation comes from the fact that Prime field arithmetics rely upon wide integer multiplication defined by the size of the field and it's the wide multiplier that you simply have to do and multipliers are being bottlenecks in bunch of different compute clusters hence in the prime field as well binary Fields operate on vectors of bit and there is no so-called car carry propagation so binary Fields operate on trivial logic gates and Ur what this really means for us in terms of low-level silicon implementations is that these modules can achieve much better efficiency amount of compute for the same silicon area but can also

achieve much higher clock frequency which is ability to run the pipeline or the speed of a certain module so effectively for us technologically binary Fields enable bunch of no innovations that we can pull back from 80s and 90s which are originally running in different Industries interesting Brandon now I'm curious because they mentioned plony 3 are you going to have to create a plony 4 like what's the difference now maybe you do need more space or something I don't know well no I I I think that um the sort of parlor trick for py 2 was what if we had smaller fields and you can't get smaller than characteristic two fields and so I

I I think for me like this might be sort of a like a terminal innovation in some sense like I I think that eliminating the embedding overhead is really powerful and I'm not a hardware person and I don't want to claim to to have any insight there but uh I I I think if if what Rody's saying is is correct and we can eliminate carry propagation and we see these huge efficiencies inpg then I I think that there are like some really long-term structural benefits to uh to taking this approach and so I mean certainly for for polygon it's something that we're really really interested in I mean to build off I think what what Brendan was saying like I want to have some humility because there's you know new research uh every

you know six months or every couple of months in this space and certainly Bas in his current form is not like the end product of the binary field movement but I do think there's something very fundamental about binary fields and they have a history in cryptography and I think like a lot of the ideas that Bas uses do date back quite a while so the sum Che protocol was like this really uh seminal work from the early 90s that proved a really important complexity Theory result it's not like some new thing that came out of the ZK space the the binary field tower construction that we're using is also several decades old and like the tower Field construction is

pretty much exactly in my opinion what you need uh here so using all computation that we do today is based on like power of two data types like we have bytes which are uh8 bits and we have you know 32bit integers and 64-bit words and memory addresses so I think there's something very fundamental about having data types at your arithmetization and and your proof system level that are powers of two the way that benus is able to achieve yeah I think that that's right I I don't want to claim that we've reached the sort of end of history for snarks by any means I I think that there's still plenty of innovation that can happen for the PCS but I I do think in some sense

this movement towards smaller Fields terminates with binary Fields yeah we have a lot of conviction that this is is the right way to do Prov efficient verifiable Computing and looking forward what we're trying to do is basically educate and promote this this technique and develop it and bring it into production and and work with uh the teams that we consider to be experts in the areas where we're not experts which are like arithmetization and building VMS and stuff it's not always expressed this way but basically proof systems and snarks and zero knowledge proofs have basically a front end and a back end where your front end is what translates the high level logic that you're trying

to express like uh an ethereum transaction into what is essentially a matrix of field elements and the back end takes this Matrix of field elements and like does a whole bunch of stuff and produces a proof and we consider ourselves experts at you know proof system backends uh and understand the ends and outs of that but the actual front-end engineering how do you translate a program into this this Matrix of constraints and field elements and and how do you write the framework to do that is not as much of our domain but there are other really um Stellar teams in the space that have been doing that for a while I think uh one other thing that we haven't discussed is sort

of the opening up of choice in terms of hash functions I think that many practitioners in the space have sort of varying levels of discomfort with some of the arithmetic hash functions in terms of Security in terms of performance and so one thing that using binary Fields enables is really efficient verification of symmetric hash functions like ketak or Blake two Blake three and so maybe you could talk about kind of the advantages of that from both a security perspective that we can use constructions that have been around for a very long time and then also from a hardware perspective yeah absolutely it's unambiguous that the arithmetization oriented hash functions especially

you know over Prime Fields have computational disadvantages but they're also new I am not a symmetric cryptography expert I don't you know do Crypt analysis on hash functions so I I sort of take the word of of experts on this but hash functions uh and symmetra crypto in my opinion is like a bit of a Dark Art where you just trust in the uh how battle tested it is and the total value of the systems that these Primitives have been protecting so it's a lot more comfortable to use you know not only well understood hash function Primitives but also hash functions from very conservative assumptions so in our paper we talk about the hash function

gral um this is one suggestion we also think that bineas would be great at verifying programs that use Shaw 2 and and many of the other symmetric hash functions but grol is a hash function that's probably not familiar to most people it actually has undergone a lot of Crypt analysis in the shaw 3 competition but it is also based on what I consider to be very conservative symmetric uh Primitives so it uses the same underlying techniques as AES which is a very standard uh encryption Cipher and that's like fundamentally different from what Poseidon is doing which has a sort of new type of of sbox and a new type of Crypt analysis so I think both

the security and performance advantage we get by creating a proof system that's compatible with standard hash functions is one of the main benefits like a really notable benefit of this approach um and it also is an unlock for applications that natively need to verify hash functions which you don't have control over so there's a whole effort in our industry to verify uh the ethereum virtual machine in a way that's fully compatible with the ethereum spec which uses the catac 256 hash function uh and that is you know among the things that we've learned from talking to teams like this huge bottleneck that everyone's running into that like verifying catch acts is like killing

their performance so you know if we can solve one thing we think that we have you know the best solution so far that that we've seen to that problem it's not just the binary field approach we think that there's like real just uh subtle advantages in the combination of binary fields and multi-linear protocols we develop a number of techniques for efficiently verifying cyclic shifts like bit bit rotations uh which is a an operation that you need to do in catak and how to combine the the fact that your binary field Towers uh your Tower fields are powers of two with the fact

that the hyper Cube structure of the trace also is powers of two and there's some very cool synergies of those approaches on the topic of hash functions I want to just do a quick shout out to another episode and we'll add that as well which is called what's the deal with hash functions with jpon Demetri where they talk about how they battle test those hash functions so yeah we'll we'll try to add that if somebody wants to check it out on the hardware efficiency side of hashers things are really dramatic we compared goldilock 64 implementation of padon and baby bear 31 bit implementations of padon 2 hash functions which are currently sort of

state of the art in the prime field domain and we basically see that gral outperforms these for 50 to 200 times in terms of Hardware efficiency and having said that hasher is really important performance bottleneck of current starish protocols this is a huge Advantage really for binary type arithmetization of H function so Jim you'd sort of broken it down into these two components the front and the back end and this is more focused I guess on the backend side of things what are the limitations of it or is that just not known yet because the front end part of it hasn't really been discovered or explored so this is a change to the back end so the way these interact is the

back end supports particular capabilities that are exposed to the front end so an example of this is like a lookup argument this is fundamentally a backend protocol but it exposes this feature of a lookup argument to the front end arithmetization design so the Bas paper you know exposes a number of tools to the front end we have not fleshed out a front-end like software library or like SDK yet we have uh several things sort of in progress there and and are looking for you know I think there will be a number of solutions from low complexity and sub suboptimal performance to like high performance and

takes a longer time to engineer but among the things that change like the most notable thing that changes to the front end is that you have the ability to do binary field arithmetic and multiplication natively in your constraint system but you don't have the ability to do modular multiplication natively in your constraint system which is something that the current front ends and circuit designs take advantage of so this will require like a rewrite and a re arithmetization of at least many of the lowlevel gadgets that are used in proof system front ends today hopefully some of the higher level abstractions are are able to be preserved um but

another thing that's really cool and ours is the first work to do this we think about constraint systems over a field like you write a constraint system over the the Goldilocks field or over the meren 31 field or something uh Bas exposes a whole family of fields that the person writing the constraint system is free to choose between so you have the one bit field which is F2 so if you need to do bit operations that's what you would use but you also have a field with eight bits which Maps basically to bytes of data which is really useful so if you wanted to do integer multiplication and we show how to integer multiplication fairly

efficiently in our constraint system and one of the ways you do this is you look at how would I multiply one 8bit unsigned integer with another 8bit unsigned integer well you can do that with a lookup argument so you look up the you know product of these two 8bit unsigned integers and you get that result and in your constraint system you can do this not with just bits but you can use the larger field elements that are 8 Bits and 16 bits which has efficiency advantages so there's a number of places this is useful so ours is the first proof system to expose sort of a whole family of data types in some

sense which gives people who are writing constraint systems more flexibility I was just going to touch on uh so I think for practitioners and developers in the space that are used to simulating 32bit or 64-bit or 2 56-bit operations this won't be that big a change because we sort of have to abstract away like how we simulate those operations anyway but I think for developers that are used to writing in circom or Noir and they're just able to sort of adapt to their program to do multiplication and addition over a different modulus it's going to be like a pretty big change for them right because now they suddenly have to use

lookup arguments where whereas before they could use addition and multiplication like natively in the finite field I wonder if they look at this approach and are thinking like how do I use binary or and binary and to like uh you know subtract from my balance calculation when I send a token or something and so I wonder how you think I I I don't think it's a problem at all but I I wonder how you think about that complexity yeah I I think it's the answer to software engineering problems is modularity so we give what in the paper gadgets for doing integer addition and integer multiplication and actually addition we thought that we were going to use lookup arguments more extensively

but actually addition is just really simply defined in terms of bit operations so we don't use lookups for addition we have these efficient gadgets for uh sort of carry propagation and and so on where we can efficiently do integer addition just over F2 in terms of bits and it's very efficient and so if you have that as a low-level module in your front end and you expose it as a library then hopefully the higher levels of your logic that you're building on top of that don't need to change I'd also note that we recognize in talking to uh some of the teams that the especially as you move to smaller Prime

Fields like 31 bit Prime Fields the ability to use native multiplication gets more limited so if you're trying to multiply two 16bit integers in a 31 bit Prime field constraint system you can't multiply 16bit integers without overflow and without possibly mangling your values so you kind of already need to decompose it to maybe multiplication of 8 bit limbs which is exactly what we get with a lookup argument in the binary field setting or in the Bas setting so I actually think that in the in the world we live in now which has been moving towards smaller Fields anyway and more extensive use of lookups anyway that

basically the timing is right to just totally jump over to Binary Fields yeah I think that's right and I think that there's also the the higher level problem of reducing dependency on your choice of field so so if you write a constraint system that's over like a 256bit field and you want to suddenly take advantage of the efficiency gains of moving to a smaller field you'd better hope that that program isn't deployed on chain because you won't be able to sort of seamlessly upgrade to use the new field and so I I mean personally I think that the approach makes a ton of sense I have a question a little bit on the timing of this Innovation and how maybe your team or other teams would develop it further so

the paper has come out now just sort of something for the listener if they're not as familiar with the ZK indust industry like usually what happens is research and then obviously lots of implementations it doesn't hit you know main net or like is not yet used in production for some time do you feel like now that this is out are you going to start creating an implementation that you're like aiming to have be on mayet or is this like here's the first research we're going to continue to do research and then do an implementation I'm so glad you asked Anna we released the paper a few weeks ago and we also released our software Library which is a rust implementation of vas it is not a

complete system yet we uh are progressing and going to be continuing to develop that to uh the first Milestone or the next Milestone would be a full snark that can verify the catch a hash function which is going to be really demonstrative of the performance benefits that we're able to get with this approach the state of the software implementation right now is that many of the low level Primitives including the polinomial commitment scheme are fully implemented and uh some check and actually the underlying arithmetic is fairly optimized and uses assembly and uh low-level Intel uh instruction set extensions to basically demonstrate performance of low-level operations

which is what we needed for the performance evaluation of our paper and we are going to continue developing the software Library uh hopefully be able to collaborate with other teams in the space who who also want to help push this approach forward yeah and then on the hardware side Rody can mention what we're doing there right so this is one of the proof system that we started Hardware acceleration pretty early in the process and in particular for beus proof system we identified sort of three major compute bottlenecks one of them being entity second one being hasher for leaf hashing and Merkel tree and third one to be the Su Che we here have already implemented the entity in the

binary Tower Fields And gral hasher as G mentioned for the Merkle tree leaf hashing and the third part is currently under the process of architecting and we are going to try to implement that as fast as possible so you know following the high performance rust implementation there will be a high performance Hardware implementation which will then eventually show the full potential of this Pro System I had a more general question and it it sort of goes our experience with planky 2 and in developing planky 2 there was a ton of uncertainty around whether the direction would end up like being fruitful at all because we knew that previous attempts at R to fry had been super super inefficient and so we were sort of

working along this path and it was very speculative we didn't know if it would pay off um and it did and I wonder if there's a theme here where the conventional wisdom is you know you should leave these sort of like theoretical R&D to academics or to sort of full-time researchers and you should sort of stay in your lane and focus on implementing hardware and or you know software optimization and I I wonder if that is a really big mistake given this like sample size of tube and if the sort of hardware and software code design uh approach is is really the right one and it's it's a good thing for practitioners in and and developers in industry

to really like take a broader perspective and focus on fundamentally theoretical R&D and incorporate that into how they work and I guess my my long-winded question is I wonder if it was a similar sense that you were taking on risk that was uncomfortable in the R&D phase and if you agree that it's a good thing for theoretical R&D to extend beyond academics and full-time researchers into industry I think the approach of having cryptography engineering oriented way of tackling proof systems is what has given us a lot of the performance benefits that we've seen in snarks over the past few years honestly so Brenan and I met in Spring

of 2020 at a time when I was finishing grad school and was frankly pretty pessimistic on the prospects of us having efficient proof systems like in in the next 5 years or decade and I was kind of completely proven wrong in basically the year or two years after that and the thing that changed was that you had a lot more practitioners understanding these ideas and just applying engineering principles to drive up performance so you know we we talk about Hardware software codesign I think Bas is also an example of sort of algorithm Hardware software codesign right I mean Rody talked about parallels to other Industries in the beginning a

little bit but there's this anecdote from I don't know if I'm allowed to talk about other podcasts but on the acquired podcast there was a really interesting anecdote from uh from their Nvidia episodes where they talk about how Nvidia released the revo 128 in I think the late 199s and they had to support Microsoft's uh 3D acceleration API direct 3D and they released the revo 128 and it's got monstrous performance but it supports like a fraction like a third of the feature set of the API and it's just like broken for the rest of it and they they go around and tell all the graphics developers like ah you didn't really need that extra functionality

anyway and so the developers just sort of bent around the limitations of the hardware because they needed that performance to get their games to be good so my point isn't that like Hardware should dictate what happens at the algorithm level but there needs to be a feedback loop between the algorithm design and the implementation and that's where we're going to get really efficient proof systems that can deliver zkl and type 1 EVMS and uh verifiable software builds and sort of the long tail of things that we dream that verifiable Computing can accomplish wow if I can add my my portion of the answer Brandon I think what's really important to have cost efficient and high

performance proofs this is really required for this industry to lift off and tle Tackle all of these that Jim just mentioned and I would like to use another example not from another podcast but really you're like you know true story trust me it happen when we say networks today we primarily think about ethernet the same way that when we talk about internet you know nobody really questions where it came from as a protocol right we are at this stage of protocol development where we are not sure which protocol is going to win but I like this parallelism with early days Network so what happened in 98 was introduction of Internet by company called zerx which was a big name in traditional Hardware industry and pretty

quickly two or three years later both apple and IBM came with their own versions of networks local area networks really the way to connect computers one is Apple net and the other one is token ring and I bet that like nobody ever discussed this you know in in in a podcast like this what happens though is that at conferences these particular years this was the key subject like which network protocol is going to win and is going to enable computers to connect together the reason Xerox won with ethernet because they had a network interface card or ethernet Hardware available few years before apple and IBM had a role and they reach

level of cost efficiency of this protocol to run and effectively became I standard in 1985 my point here is that when situation is a little bit volatile and liquid in terms of protocols and there is lot of different academic prospects on which one is going to win in the long term my advice is to look at the compute price efficiency and that's likely the protocol that may wi in the long run so like my last question was around what real world impact something like this could have and Jim I think you did share that you sort of said this could en like the zkl use cases and this provable compute in the ways that we want but on the sort of shorter term is

this proving system likely to be the basis of like a ZK evm or is it like do we kind of Imagine these types of Innovations of eventually entering into the designs of systems that users of maybe blockchain would see yeah I I'm as I've said fully convinced that this is the future of of pro efficient verifiable Computing and we would have liked to make more progress on the software implementation but felt like it was really important to just get these ideas out to the community as soon as they were in a state to be presented so that we could start making progress together on on implementing this vision and I think Bas is a really natural

platform to develop a lot of the ZK evm efforts that are being deployed on l2s and hopefully we can see more momentum from lots of players in the space to help push this technology forward I have a sort of very different question I don't know that this is something you guys are thinking about but there has been some chatter about the snark marketplaces these like places where people would be generating snarks for other systems if you're in the hardware intersection is that something you are thinking of as well like potentially creating the software Hardware combination for these types of things or is that completely separate from what you guys think about yes I think this is

pretty good question Anna so first of all one of the contributions that we are trying to bring to the ecosystem is actually contributing to the decentralized proving by private Cloud if you look at the proving right now most of the main Nets are running they centralized proving for this stage of the operation but running pretty much from the same public Cloud so we are actually helping decentralization by bringing private cloud in the space and in the short term we are going to be working with like you know professionals as we can put this way to bring this technology into this zero knowledge Stacks which are already designed for this in a sense to be back end for already existing fra tends but down the

road we are evaluating different platforms how we can make this technology wider accessible and I guess narket place are one of the options that we are evaluating what do you think of this brandan I think that what Rody said is completely right and and there will be providers of Hardware accelerated proving for the protocols that we use today on L2 and otherwise and I I don't think that that's controversial I think that there will have to be some recognition of this tension between decentralized proving and cost because if you want decentralized proving then you also want a liveness guarantee you want some uh assurance that you know your proof will actually be generated

and so what that ends up doing is it introduces redundancy into work your proving setup and so instead of having one party that you can depend on to generate proofs suddenly you need to have like four parties that are generating proof and the network needs to compensate the provs for actually doing this regardless of whether or not they end up providing the proof because in order for them to continue to operate they need to have some sort of financial incentive and so I think that decentralization is great I think that there just needs to be some sort of we we need to sort of navigate the cost versus decentralization tradeoff and come to a place where it sort of makes sense rather than like blindly pushing ahead to decentralization what is it

right now for a lot of ckvm is it just like a centralized proof generation from the team that had developed the thing yeah so so certain certain zkm I believe have like backup mechanism so if the approver goes offline for some period of time then anyone can submit proof and so there's like a decentralized mechanism but right now there's only one party that produces the proof and again I I I think at like a superficial level people look at that and they say oh like that's terrible we need what are we what are we even doing and and crypto if we don't have decentralization and it's like my my response to that would be like decentralization for what like

decentralization is like an instrumental goal it's a means to an end and I think for certain applications having decentral provs is really important for others I think we need to interrogate what the guarantee is that it's meant to be providing is the proof generator this is sort of dumb but is it the same role as the sequencer in a way not necessarily or that a separate thing yeah so so right now it's generally I I think for every single ZK rollup the sequencer is the same as the prover but it need not be that way well I want to say thank you ratty and Jim for coming on the show and sharing with us vatana the kind of reason for Bas the innovations that Bas brings yeah thank you so much for this conversation thank

you Anna this was a pleasure thank you Anna and greetings to all your listeners and Brandon thanks for coming on and and uh co-hosting this one with me yeah thanks for having me all right so I want to say thank you to the podcast team Henrik Rachel and Tanya and to our listeners thanks for listening