ZK12: X-check: A Native Binary Tower Field ISA Design - Radi Cojbasic

Transcript

[Music] all right yeah my name is Ry I'm co-founder and CEO of irreducible company that works on high performance proof generation and I'm today going to be talking about the next check which is a custom CPU that we developed at irreducible uh I want to make it crystal clear at the very beginning that we are not talking about a custom Isa for Z K VM so I'm sorry if someone is disappointed but this talk is going to be good as well it's going to talk about different thing it's talking about actual CPU so again this has nothing to do with ZK VMS this is talking about real physical Hardware um

what I'm going to be talking today I'm going to give a little bit of a review of evolution of Hardware acceleration I'm also going to be talking about this particular instruction set architecture which is native to the binary Tower field fields which are used for binus our proof system I'll talk about the CPU design I'll talk about our performance results and I'll reflect on the future work just wait one more second still have people coming in before we get to the good stuff all right let me check if this okay this works so evolution of Hardware acceleration we are in this industry where there is quite a few Hardware teams right now who are working on

accelerating proof system systems and pretty much until this point in time Hardware acceleration followed pretty standard approach for all of for like our previous work and work of our competitors and what does this work consist in it's really starts with uh CPU profiling and bottleneck identification this is something that we historically saw with msms entities Merkel trees Etc these are like usual suspects We Run The profiles on CPU execution we identify the bottlenecks and then we try to do so-called Hardware offload Hardware offload means that you take portion of computation and you offload to hardware and this historically was done using gpus and fpgas and there is quite a few teams out

there which are also working on custom silicon Asic design for the purpose of Hardware offload and then the last thing that you need to do is to do the integration and I'm just going to mimic server here and in typical server you have a CPU you have a system memory that talks directly through dim slots to this server and then you have notion of motherboard the black stands here for uh PCI Express and then you have several Hardware accelerators plugged into PCI slots this can be gpus or fpgas or custom a cards and you really offload single module to these and try to accelerate as much as you can now there are a few challenges and these are the challenges that we've

been hitting in past two or so Years first of all you have to have a high bandwidth between the CPU and Hardware accelerations on your PCI bus this requires really low level sophisticated kernel engineering to be able to do so um second of all your Hardware modules need to follow the protocol updates so your Hardware team needs to be capable of quick iterating because Protocols are changing fast and that puts really interesting Dynamics in between Hardware design and Hardware software codesign in terms of integration development cycle is pretty bad basically that's what every Hardware team is being talking for the past two years now this is an interesting point I really need to stress this one there is a massive

disbalance in between the system memory which is right next to the CPU that basically all the stock proof systems are running in and the memory inside the hardware modules we are talking about one to two terabytes of system Ram which is sitting right next to the CPU and we are talking only about 16 to 32 to 80 gigabytes these days which are sitting on fpgas and gpus what does this mean this means that you need to find a way to design transactions from the system memory into hardware and process things in time creating some notion of pipeline like you can't just dump your entire Trace in hardware and have it all executed so these were the problems that

we typically see with custom accelerators that companies uh publish in the past two years uh we were one of them we have a working example this is polygon zkm accelerator so a typical example of profiling and successful acceleration using this approach what we have on the right hand side is a very beefy CPU server uh found in Google Cloud which has 224 virtual cores threads and basically this is the profile of execution of the ZK evm on that machine it's dominated by Merkel trees hashing and by LD which is a bunch of entities which are happening during

the low deegree extension and irreducible takes this proof system for acceleration we run it on our server which only has 64 threads and virtual cores and obviously it executes slightly slower when we run CPU only but then when we apply acceleration and we tackle lde which gets shrinker and then we tackle also Merkel tree and separate Hardware accelerator which completely basically disappears we get accelerated version now this version is two times faster than our software model it's basically 160 and 84 seconds and this is really proof that traditional approach Works um we were able to accelerate

quite a few things this way you can go to our website and find the blog post which provides detail explanation on on her on polygon ZK VM acceleration but we also have recently achieved acceleration of succinct sp1 and if you haven't passed by our boot which is on the on the ground floor and you can have the profiling numbers for sp1 done in exactly same fashion now we are the company that actively develops binus it's our proof system that we introduced in November last year and this is first time that we are talking today about actual Hardware acceleration of Banus there's been a lot of discussion about it cryptographic benefits Etc and be

obviously internally we were challenged to design a really good accelerator for beus and this is how X Che became a thing so before we go into X Che design I will just tell a few advantages of beus and binary Tower field so first of all binary Tower Fields operate uh carless arithmetics which is really Hardware friendly and there is recent blog post also found on our website which claims that binary Tower Fields when it comes to Hardware are five time more efficient that mer Center one and I also want to make it Crystal Clear we are not comparing this on CPU on GPU on any sort of existing Hardware we are comparing this in terms of Asic design

and our findings are that binary Tower fields are five times more efficient essentially if you make two chips of the same size you spend same amount of money you're going to get 5x more multiplication outside of binary Tower Fields that's intuition for this arithmetic efficiency second thing is and this is now where we start talking a little bit cryptography uh beus features reduce tray size this is really important for us because it's minimizing the memory footprint of the Pro system and this is because in benus your elements can be 1 bit 8 bit 16 all the way to 128 so unlike Prime Fields unlike plony 2 plony 3 which run on mercen or baby bear 31

you're not fixing your element size to describe your Pro system and zkm or whatever the application is you have availability to use different field element size we call this reduction of embedding overheads and this is really important um second thing which is very important about beius it brings OG hash functions hash functions which run in production for decades so far and are implemented in binary Fields everybody knows about AES there is grle which was also finalist for sha three they are all good example but there is also work that we did IR reducible in introducing a new hash function which is particularly optimized for binary Tower fields and this is also something that we wrote

about previously Vision M32 now when it comes to development this is where things SL start to differ from other proof system that we were talking about so first of all polinomial commitment scheme is fast this was the bottleneck for Halo to plony to plunky 3 like choose your own favorite snark or Stark from two years ago PCS was always the bottleneck either ntity plus MSM or ntity plus Merkel tree and whatnot quo polinomial computation here situation is completely different it's the sum check which is the new computational challenge and it's such computational challenge that requires completely new paradigm of computing and basically the previous approach cannot work so let me try to

explain why the previous approach doesn't work um this is the beus execution on CPU tool that we use is called perfetto and perfetto essentially plots this simmer Lanes of time spent to do different things so we have Trace generation proof and verify steps proof step is dominated by some check actually the zero check version that we are implementing internally and then we have another step which is not subject of this talk called L check and essentially this is what the proving consists of if you see the green bit that's basically the biggest time consumer the biggest

offender is the zero check computation now I will just also mention that software implementation of binus is completely open source and you can go to GitHub and gitlab open source forth and we are maintaining this up to date so you can literally reproduce these results anytime you want for reference we are running this on pretty beefy server it's the same one that we use for polygons Z KVM it has two CPU nodes 64 cores each running at 375 GHz it's basically a beast and this is what it takes to run this is actually ketuk proving Trace presented here so yes our goal as a hardware team essentially is to accelerate this step so let's see what are the

requirements there are quite a few and I'm going to try to go the way how we progress on the stack of computation we start from the lowlevel side where we have basic arithmetics and first thing is that here we are dealing with different elements all the way from one bit to 128 bits why then this is instantly tricky for making like custom Hardware module which does one thing and one thing only there is essentially need to support different sizes second thing is that we are supporting heterogeneous uh Trace matric evaluations with some check and zero check this again creates the problem right in certain ZK VMS or ZK EVMS that we saw before column size is fixed or

there are certain rules how how this computation goes but here here we really need to support heterogeneous side so this is another tricky requirement for our task data types so binus is an interesting system because if you have a bite in memory it could be one element of 8 Bits or it could be eight elements on one bit and this keeps changing all day long the way you are progressing through the computation so this this again introduces another Hardware challenge programmability this is where we try to stay um at the same development Pace as open source contributions to the software model so essentially we can't have Hardware

solution which is too slow to pick up the latest algorithmic change so essentially we need to have a notion of programmability without high overhead and last but very important one is the notion of compiler essentially polinomial constraints cannot be baked in into Hardware algorithm like this was the case in certain Stark before they are not known ahead of time and they are runtime changeable so basically we need to have a way to figure out dependencies and how data looks like at the moment of execution coming to a really interesting point that if you have these requirements you have no other level of freedom but to design a proper CPU and

that's exactly what we had to do at irreducible um let's go a little bit into instruction set architecture um first of all there are three groups of instructions organized by ALU and everything is beat wise because that's just how binary fields and binary Tower Fields work in general then there are instructions Associated to the data movement and obviously lot of different flavors of multiplication and proof generation in general is really just proxy for very large number of multiplications so we have to be good at these and I'm going to explain some of the Exotics which you can find in

this CPU and no other CPU out there before I get into that I'll just say that uh we have 32 register Bank each register is 128 bits because that's the maximum element size in B so this is really informed from software cryptography side our instructions are 20 156 bit wise so that they can support two operands or one operand plus immediate value we feature simd executions parallel executions obviously and it's all very low latencies so we are able to perform large multiplications together with load store operations in three clock cycle which also helps compiler work better um on the right hand side is the register bank

and what's interesting here we enable sever several ways to address registers obviously you can access single register from the compiler standpoint but you can also address the entire range of registers and also at different offsets this is very standard these days in like AI acceleration cores and advanced CPUs but basically you give this freedom to capture the whole set of registers in like one shot and execute operation on it let's go into exotic stuff um bit collect instruction is the signature is provided here there is destination register immediate value and there is pseudo code which describe what it does but I will

try to explain it using the picture here so imagine that you have eight registers each storing 128 bits values and you actually want to take a 16bit slice from each register and you want to dump all 128 bits into destination register this is a type of instruction that you really never find in any standard CPU out there but this actually makes whole ton of sense for proving and the type of computation that bin us does because again this may be a 16bit field element coming in uh row major order and you want to pick them up from the same offset and dump into register and

perform computation which is for instance in column major order so this is really how the cryptographic computation informs decisions of instructions in this CPU another interesting example is the transpose function we do tons of transpose when you start breaking down entities ffts basically operation again Pudo code is provided I'll just say that we feature 16x 16 8X 8 4x4 and 2x two but really think about this as register Bank holding data and then you have a single cycle operation that you can transpose the content of the the registers again there is no like generic CPU which

is going to do anything like this let alone in a single cycle but this is something that we really need in order to be fast in Computing these cryptographic operations um multiplication is very interesting one we do tons of multiplications we have super fast multiplier that does large field element multiplications but what happens in beius and I don't think it happens in other proof systems is that you are multiplying say small field element with a large field element and this can be very exotic you can take 8bit value multiply it by 128bit value and then your result is again 128 bits and now how you support all of these

combinations that can happen without wasting too much Hardware so we came with pretty interesting concept of uh mixed multiplication and it works in the ve vectorized style so soon code that I'm executing here is really just multiplying two 32-bit values and writing the 32-bit result so from register perspective I'm picking up 32 bits here and 32 bits here out of 128 there is network of Kat subas there is nine 8bit registers sorry 8bit multipliers then another layers of karasuba and you are able to provide result in this particular example when your operants are 32bit each you

actually end up using all nine quote unquote small multipliers which work in 8bit resolution and get the result but now this is very interesting you have the same Hardware so actual same silicon quote unquote all logic gates but this time you are doing 8 Bits times 32 bits so in software you know like if you are doing this on GP or whatever you actually need to go probably through different pipelines and registers but here we try to recycle reuse the same hardware and again example we are taking two 8bit operants from the same register 32bit value but then left hand side 8 Bits only propagates through this

circuit and right hand side 8 Bits they only propagate through this circuit this time utilizing four multipliers each M4 is not really used in this case but what this gives us two results in parallel on the same clock cycle this is another example of very exotic uh approach to multiplication which is informed by cryptographic properties and how we can mix and match small or large Fields um this wasn't just theoretical study or simulation or ulation of a design we went ahead and implemented the actual CPU now I will make it also Crystal Clear we didn't tape out custom silicon we prototyped this on our fpgas and I'm

going to share the findings of the design and the performance result that follow so we were able to prototype 48 cores CPU on single fpj card and a little bit of system information there is a bus which runs at 250 MHz clock and there is basically PCI controller to talk to the motherboard and the host and what's on the picture is like the grid of 48 cores where core zero is highlighted and the CPU here implements the instructions that I was talking about and it has Associated data and instruction memory right next to it so this was implemented on the board what you're looking at is the actual fpga

layout so this is what logic looks like when you look at the implemented multicore CPU design the yellow portion at the bottom is onchip memory this is pretty big 16 GB memory inside the fpga which we use for data and instruction storing the orange color is the PCI controller that talks about that talks with the motherboard and the host and then everything else is the logic which carries 48 of these cores in a multicore CPU so we implemented this internally tested and basically I will also share a little bit about software implementation so um this CPU requires its own compiler

right so you can't plug llvm or any other solution out there because instructions are very tricky and generally speaking when you don't have instructions such as branching or jumps stuff like that these architectures are typically known as dpu like data processing unit you kind of want to have a symbolic way to describe the code and since we are you obviously working cryptographic field it's really cool if you can describe your katchup function really through the polinomial and then having compiled to actual instructions which are operating on the CPU and this assembly here shows you Lu load pipeline sorry store Pipeline and load Pipeline

and how they look in the time domain you will see very interesting things that you have read from memory and store from memory in the same clock cycle because we are featuring through dual Port Memories We actually support this case efficiently and then if you look the computation side you will see a lot of multiplications and additions back to pack so this is really the output of compiler which was written symbolically and these are the instructions that get executed on this multicore CPU um interesting part performance results like why we are doing all of this effort um we are seeing pretty significant performance Improvement this is again catchup example that I had

peretto trays and on the next slide you will get the visual Digest of this table but what I really want to stress is this is the CPU only execution of of KET proving and this is the accelerated version if you compare the total time to compute some we see roughly 5x speed Improvement but for some of the earlier stages which are very slow we actually see like seven times speed Improvement and this is really like why Hardware should exist in this industry it's not really to try to shave off 20 30% your performance it's really to get you 5 10 20 100x over the reference software module and make it worthwhile if we go back to proofs uh to perfetto sorry on

the upper one is the CPU only this is exactly same one that I presented many slides ago this is the round zero 1 2 3 4 Etc of catch approving and this is what it looks like with Hardware acceleration so round zero corresponds to this one 7x Improvement round one corresponds to this one more like five to six times Improvement etc etc um future work this is really just the first cut of the CPU that we made and we're able to successfully prototype there is plenty of improvements that we can do across the stack so as we spoke about requirements in different stages of the computation I'll also talk about

future work so yeah we are looking to add a lot of more vectorized instructions and increase the compute density per core we are also trying to fit the entire Trace into on chip memory so that we can completely eliminate well not completely but significantly eliminate um communication to CPU and back so essentially we want to hold the whole Trace in on chip memory and yes we just need to try to get basically more cores on a single fpga and running at higher frequency so you know you just take this one if can make it run on 500 MHz we have currently design running at 250 MHz that getes you 2x out of box and we take it from there so yes there is

really a lot of room for improvement and our servers support many fpgas in the same chassis we can fit up to eight so we we think that we can distribute some other portions of the proving on more fpgas the function that I call eval check that you saw before we didn't even touch this yet so we are only focusing on some check and zero check and definitely there is a lot of room for improvement there uh compiler is a big one there is always identification of new instructions sorry like exotic ones that are not obvious and basically adding new instructions could really improve the performance and we need better support for software for vectorized computation um having said that thank you so much

for your attention and uh please check out our Twitter and website if you see anybody from irreducible there are having these stickers which are our open roles we are hiring across the team and yeah if you are interested to be part of this journey please let us know thank you thank you thank you ready we have a few minutes for questions so time for Q&A any questions from the audience okay why does the performance difference

flatten in the later round so in the first you have this increase and in the later it's almost the same yeah that's a good question so the way Su Che works there is part that you're doing first and there is also folding component and not everything is as efficient so in these rounds you do less folding in these rounds you do more folding and the more folding you progress in the later stage we get relatively speaking less efficient but yeah this is something that we want to try to tackle by adding new instructions which are tackling exactly this type of computation yeah so uh you're simulating a hypothetical CPU architecture on an fpga right yep um what would be the

performance difference if you just directly encoded like the computation doing in the fpga instead of like first simulating this CPU architecture and then doing it through that or so am I getting this right you're basically saying what if I don't do CPU on an fpga but I actually make a custom image for fpga that is just tackling ketak for say for example uh yeah yeah yeah we could do that and it would be probably similar speed but then you have this problem that for catak you need to have kind of custom images but then it's not that our prover is only proving Kat all day long like then you have the problem that if the next one is I don't know lasso or gkr or whatever you know the the proving task is then

you need to do a different circuit and that that fpj which is only doing katchuk becomes pretty much useless so that that was one of the reasons that we have to change the Paradigm and get into CPU architectures which you know just run on fpgas like because we can and because we are not yet building Asic even though we plan to have eventually custom silicon doing all of this but yeah this this justifies the call for CPU approach and not like hardened image that does only one thing I see thanks sorry kind of a follow-up question I'm not expert on fpga but what

will be the performance difference if you implement this CPU on Silicon I was hoping somebody would ask uh so basically this is kind of the name of the game so the system clock here we are pretty much Limited at 250 MHz we can do at least 1.25 GHz so you get 5x immediately just by faster clock second thing is how many of these cores you can fit that becomes the question of like how big chip you want to make depends on power budget cooling Etc but I I feel like that you can get at least 5x on the clock and probably another 10x in terms of just efficiency so it can be 50 to

100 times faster if you have a a a custom silicon for this do you have plans to do that yes we are definitely planning to make custom silicon for for beus proving and for binary Tower Fields like we feel very confident given all the research that we did that binary Tower fields are the future of verifiable computing and um also our research shows that gpus or CPUs are not really as good for this type of circuit so yes we definitely are planning to have a custom silicon for this obviously keeping all the all the programmability and compilers and software support for it but it's subject to you know ecosystem maturity and demand for

proving thank you thanks great thank you very much thank you so much thanks