ZK Whiteboard Sessions - S3M2: High-Performance Engineering for SNARKs with Jim Posen

Transcript

Welcome to this module of the ZK Whiteboard  Sessions. I am Nico, I'll be today's host, and today I'm super happy to have a  return guest, Jim from Irreducible. Hi, I'm Jim, I'm the CTO at Irreducible  and I'm very excited to be here. Great, what are we talking about today, Jim? Today we're going to talk about high  performance engineering for SNARKs and how we can make the best use of our technology  to implement these protocols very efficiently. So what does that entail? What are the  themes that we're going to go through? This is really a story about how we identify  bottlenecks, decide whether they're computational bottlenecks or memory bottlenecks, and break  through them by using software engineering, hardware engineering techniques, and we're  really going to pursue the story of how do

we exploit parallelism to distribute our  work over multiple resources to bring down the time it takes to produce a proof. Cool,  shall we get started? Let's get started. We need to recall a basic SNARK protocol,  so in this session I'm going to focus on hash-based SNARKs, if that's okay, or  hash-based SNARKs, for example, STARKs, and we're going to have a little toy example of  a STARK over the Baby Bear field. We, I think, spoke in our last module about small field STARKs,  so the Baby Bear field is a 32-bit prime number, and it's become very popular for STARKs  because it's compatible with the NTT,

and we'll have a STARK protocol where we have  a table that has three columns, and we want to evaluate a constraint over it, for example, a  times b minus c equals zero, and we want this to be true at all rows in our trace, and if we  recall the major steps that we're going to do in a STARK are number one: witness generation,  so this is when we arithmetize the problem and fill in the trace matrix. Number two: we need to  commit the trace and in a hash-based SNARK this is going to involve a number theoretic transform  for error correcting code and also a Merkle tree.

The third step is constraint evaluation. This is  when we take this expression and evaluate it over every row, and the number, the last step is the  PCS opening, and we'll be a little non-specific about the PCS. We can imagine this being either  Fry or something like Ligero, and as a rough sense of how costly these different operations are, if  you run Plonky3 for a Poseidon, every different constraint system might have a different profile,  but we could roughly think about this as being

10 percent of the overall time, this as being 30  percent, 30 percent, 10 percent, and 20 percent. Why is this? Number theoretic  transforms are asymptotically more expensive. They're super linear,  whereas these steps are both linear. Hashing is just a sort of different type  of operation, and it's more expensive, and our PCS opening is going to be more  expensive than constraint evaluation, because we're doing extension field operations  instead of small field operations. Makes sense.

Just to jog my memory, entity here is because  we're doing this encoding of whatever is there, and then constraint eval is when we  check everything is indeed zero. Exactly. We're also actually using the NTT for the  constraint evaluation because this is a polynomial multiplication that has  to happen over an extended domain. Makes sense. How do we go about making a STARK that's doing  this operation faster? Well, first thing we want to do is just minimise the number of instruction  cycles that it's going to take to do this. What we'll see is when you look at all of this, there's  really three operations that we care about.

Base field multiplications of Baby Bear  elements, extension field multiplications of Baby Bear 128-bit extension elements, and  the hashing, which is a sort of special thing. You'll remember that even though the entries in  our trace are 32-bit elements, we need to use Baby Bear degree four extension elements, which  are basically vectors of four Baby Bear elements, and there's a multiplication  algorithm associated with them.

Here, viewers can refer back  to your previous module, right? Exactly. In order to just reduce the number  of instruction cycles in a CPU implementation, we'll use standard techniques like turning  on compiler optimisations, inlining, looking at assembly, but we'll quickly find that we want  to increase our field multiplication throughput, and there's not really a way to do that by  reducing the number of instruction cycles. So how are we going to increase multiplication  throughput without reducing the number of cycles? We need to exploit parallelism.  So one instruction is going to do more multiplications than it did before? Exactly.

So different CPU architectures have different  instructions, but this is called SIMD parallelism. What does that stand for? SIMD is single instruction multiple data, so one instruction is going to operate  on a 128-bit register. We'll think about Arm NEON as being giving 128-bit operations,  and your 128-bit register is going to get split into four lanes. Each one is a  separate Baby Bear element, and so on. Now we'll do the same number of instruction cycles  to, say, multiply Baby Bear elements. So if we

have two of these registers, we can multiply  them, but every time we do that sequence of instructions, it's going to multiply all four of  these in parallel. These would be called lanes. So we're going to use these SIMD  instructions to exploit parallelism, and where does this help us in our STARK? Yeah, so I guess we said entity  was some multiplications. Yeah, exactly. There's field multiplications  happening really in all the steps except for hashing. We'll get back to the NTT because this is a bit of a trickier case. So let's  start with constraint evaluations.

So what does this mean again? It means we  have many rows. We could think about having several million rows or so, and we want  to evaluate this operation on each row. This looks like what we'll call an embarrassingly  parallel operation. You don't need to do any work to find the parallelism. It's just you're  doing a separate thing for each row. So how would we lay out a SIMD operation for this? We're going to treat our columns as  vectors of SIMD registers, so we might put four elements here sort of column-wise.  So into one of these, this will be 128 bits.

We'll do that for A, B, and C.  And then if we had a million rows, now we need to do a million divided  by four multiplications on these SIMD registers. So this is going to reduce the  total number of cycles we need to compute the operation over the whole matrix  because we're exploiting parallelism. There are some interesting considerations  that happen when you have to engineer one of these systems. One is that these registers  are more efficient to use if they're stored at memory addresses that are aligned with the  size of the register, meaning in the programme, the memory pointer to the beginning of A should  have its bottom. It should be a multiple of 128.

It should have its bottom seven bits  cleared, which is not something that a normal memory allocator will do for  you unless you pay specific attention to this. So alignment is one consideration.  Another interesting engineering challenge is that different CPU architectures have  different SIMD instructions, so we'll normally need to hide these behind compiler  feature flags and specifically manage that, but that's all going to be handled in the  abstraction of our field library generally.

Or have a library that's specific  to one specific processor, right? Yeah exactly. Okay, I see. So where else can we apply SIMD  optimisations? We said constraint evaluation is an easy place. Our PCS  opening is another interesting case where we have parallel operations, but  they're over extension field elements. So what does this mean? I was showing up  here that we have these Baby Bear quartic extension elements, so I'm going  to sort of write this as A,B,C,D, So these are the four Baby Bear elements that make  up the limbs of one quartic extension element.

So how do you think we should  represent this in memory? I mean, can we plug them directly into our lanes? Yeah, that seems like a very natural thing to do. We have these 128-bit registers.  We can put one limb per lane. Actually, that's going to generally harm  our ability to do parallel operations. If we were to do this, we need to take a bunch  of cross terms when we multiply two elements, and that's going to require us to use SIMD  shuffle instructions. This is possible, but it's just adding more cycles for something  where we want to maximise our throughput.

Just to be sure, this is because...  So addition would be limb by limb, but multiplication has cross-limb  things happening, right? Exactly. If I recall correctly, it's something like  17 different cross products of limbs in order to do a Baby Bear quartic extension  multiplication with reductions. So instead, we could actually think about using four SIMD  registers to represent many different Baby Bear extension elements. So think about having four  quartic extension elements and laying them out where all of the A limbs from one live in one SIMD  register, all the B limbs from this small element

live in another SIMD register, here's another  SIMD register, and here's another SIMD register. When we want to multiply two of these elements  together, it's easy to take the cross terms because we can take this register times... If  we wanted to multiply this by E, F, G, and H, it's sort of easy to take the cross term of C  times F and C times G, and we're just doing four extension field multiplications at a time. So we  are actually able to, even though our PCS opening phase is doing extension field multiplications,  if we choose our memory representation in a clever

way, we can get sort of embarrassingly  parallel speed up as well using SIMD. Okay. Is there an issue where here we've aligned  our memory in a certain way to fit, you know, ABC here, and do we need  different alignments to be working on extension fields? That's a great question. The alignment doesn't need to change because  we care about alignments for loading data from memory into a register, and that just requires  the alignment of the register size. But it's a common abstraction to have packed field elements  or objects that represent a fixed length vector of field elements. And in this case, if we  had the amount of data that it takes to store

a packed extension field element is equal to  the number of lanes times the extension field. So it's bigger than the amount of data to store  like one packed Baby Bear element, for example. We can go further with SIMD parallelism. So it actually makes sense to often  implement SIMD hash functions. If we're building a Merkle tree, then you are  performing many separate hash operations in parallel. So you could use SIMD lanes to store,  you know, different inputs to the hash every time.

Okay. Yeah. Different words in your hash, basically  one SIMD register, each lane is performing a different hash function at the same time.  And then we need to talk about the NTT. So let me erase this part. So how does the  NTT algorithm work? You basically have a, let's say a vector of elements that you want to  NTT, this will be something like 256 elements.

And we generally write this or we can visualise  this as this butterfly network. I don't know if we've talked about this before, but you're  going to to begin with every pair of adjacent elements and do an operation where something  like this, and Y is going to be computed as a linear combination of X and W, and Z is  going to be a linear combination of X and W. The memory layout of this is something  like this, where we take pairs of adjacent elements. And then on the next layer, we're  going to take kind of larger strides. I see. And then on the last layer, we're  going to take larger strides than that.

So we can parallelise through each layer, but  that isn't the easiest parallelism to exploit. Okay. So there's another way of looking at the  NTT, which makes the parallelism, I think, more apparent, which is if we have this vector,  we're going to first reshape this into a matrix. Let's call it 16 elements by 16  elements. There's an algorithm called Bailey's NTT or the four-step NTT, which  is we are going to take our matrix.

The first thing we're going to do is perform,  well, let's say we're going to transpose it. We'll do NTTs independently on each row. And so now we have 16 parallel NTTs  that we can do across each row. We have to transpose it back, and then  we will do, we'll complete it by doing 16 row-wise NTTs again. They're actually NTTs  onto different cosets in the second phase.

But it's to hold that we get to work row-wise. We get to work row-wise. We get to  introduce parallelism by reshaping into a matrix at the cost of having to do these  two transpositions. So these become the only sort of bottleneck in the NTT where we don't get  to parallelise as much as we might want to. So at this point, we've basically talked  about everything except witness generation, which we'll hold off on, and shown how there  exists parallelism in all of these operations that we can take advantage of. And the first way  we're going to do that is with SIMD instructions.

So how do you think we're going to go even  faster than just using these SIMD operations? Right. So at this point, we have one processor.  We're using as few instructions as we can. And we're making sure that each  instruction has as much data as I can treat. Exactly. So do we have more processors? We do. Modern CPUs have many different  cores, and you programme them using many execution threads that will get scheduled onto  different cores. So let me clear some space. So a modern, say, quad-core processor  means the CPU... I guess it's in the name, right? Has exactly four cores, right?

So this is our CPU and this is our CPU. And we're going to flesh out this diagram in a  little bit. But we have these different processing units. We've already shown that the algorithms we  want to do have parallelism that we can exploit. So if we took our big table,  we can just split it into, say, four segments and do the polynomial evaluation  for the first quarter of it on one CPU, on one core, the next core would handle the  second one, the next segment, and so on.

Do we then need to do some work  to put everything back together? Well, the awesome thing is they're all  going to have shared access to main memory. So here's our memory. And on a chip, you  have the main memory, which is like DDR, but then every core has a local cache. So you  may have heard about different cache types. The smallest and most local  one is called the L1 cache. Not the layer one blockchain.

Right. The L1 cache is the fastest to access.  So anytime a core needs to access memory, it will bring it into its local cache,  operate on it, and then write it back. So when we are operating on  multiple segments of the same table, you only really need to transfer each word in  the segment to the cache once if we're only using it once. So for something like constraint  evaluation, which is a sort of streaming pass, which is you're doing one pass over the  table, this has a really efficient memory access pattern. What about something like  the NTT where we had this transpose though?

So what does it mean to take a big block  of memory that's stored in main memory and then read different strides of it or different  columns of it into different CPUs? We're going to start seeing a memory bottleneck. So this  means that as we increase the number of cores, roughly all of the steps except for  the NTT should speed up pretty much proportionally to the number of cores we  have until we hit a memory bottleneck. And the first place that's going to happen is the  transpose that's happening in our NTT or however we choose to do strided accesses. Where does  this come from and what can we do about it? Well, we have a memory hierarchy in a CPU, meaning  we have layers of caching, we have memory,

and then another thing that every CPU has is  called a translation look-aside buffer, the TLB. This is when you need to resolve an address  that you have in your programme to where it lives in physical memory. And this is  basically another type of cache that if you have a cache miss on any of these different  caches it's going to slow you down. So that's why you want all of the memory accesses  to be very sequential and predictable and an access pattern like the transpose  in an NTT is going to violate that.

We'll get back to what we can do. Well,  ultimately what can we do about memory bottlenecks? Well, we can get  better technology for memory. We can find memory that instead of using  GDDR6 we'll use GDDR7 or the new generation. So do we mean it's just faster to  transfer between a core to the memory? Or generally we'll be talking about higher  bandwidth memories. So we care somewhat less about the latency of accessing memory  than the bandwidth of loading a large segment of main memory into a cache. Putting  aside the question of memory bottlenecks, if we're still compute-bound, what can we do?

If we want to lower the, you know, we  can't scale up the number of CPU cores infinitely without paying a lot more  for it. So how can we get more compute? So we can't have more cores  per CPU, we can have more CPUs? Yes, exactly. You can have more  CPUs and, well, actually we can have more cores but we need to move to a  different type of hardware which is a GPU. Okay. So now we're going to go from running operations  on a CPU to a GPU. This stands for graphics processing unit and but they've really come a  long way since the days of being only used for

graphics. You probably know that they're being  used widely in AI because and what do they do? Well they're a different processor type that  just has a lot of compute for parallel operations and they're less flexible but if you really  need high throughput of low level arithmetic operations like integer multiplications  and floating point multiplications a GPU is specially designed for that.  So to give you some rough numbers, if you look at cloud available compute  resources on AWS you could get an ARM CPU instance which would be something like a a  C8g ARM instance with 16 cores for roughly the same price as a G6 instance on AWS which has an  NVIDIA L4 and this thing has 6,144 CUDA cores.

Wow. So can we think of those CUDA cores as  almost equivalent to like a CPU core? Each CUDA core is going to be less powerful  and more limited in its functionality but we have so many more of them that the overall  throughput of arithmetic operations like integer multiplication is going to be  a lot higher for the same price point. So if we were to draw like something  similar to this diagram for the GPU? As I recall for an L4 you have what they called  many different SMs, I think those are Simultaneous Multiprocessors, so you have something like  48 SMs in a grid and each one has many cores.

So this is what our GPU will look like and  in many other regards it actually looks a lot like a CPU. You have a global memory, this  might have a different underlying technology for accessing global memory but you have a  global memory and each SM has a local memory which can be used either as a cache or in a  way that you have more manual control over. So what are some of the other, basically  is this a free speed up? Yes. Not really, we actually need to put in quite a lot of work  to figure out how to use this device efficiently.

So the first thing is it's not as  flexible as a CPU instruction set, you can't just write rust code and compile it and  run it on a GPU without doing something special and so we need a library that's going to  help us access the GPU resources for every hardware vendor is going to have some.  They have their own libraries? They're going to have their own library, so  most people in the space are using CUDA which is an NVIDIA specific compiler and tool  chain technology for programming NVIDIA hardware.

This allows you to write C++ code but you need  to think more carefully about how it's going to map onto the GPU hardware and what do we need to  do to run this from our rust code? Ultimately we need to write the C++ code and link it to  our rust library. Without going more into the tool chain aspects, the biggest conceptual  difference is that we can't deal with memory in the device in the same way that we handled  regular memory pointers to our system memory. So as I said you have a main memory in the  GPU and in our programme we need to keep track of the fact that our table that we're  actually trying to operate over does not live

in a shared memory space between the GPU and  the CPU. First we need to transfer it from our motherboard. We'll call this the host and this  would be connected over a system bus to the GPU. These are two separate pieces of hardware, two  separate chips generally. We need to actually transfer data from the main memory here to  the GPU and our software again needs to track where in the GPU's memory space each piece of  content lives and that's more code to handle.

Is this something for the software to track or the engineer to keep in mind and write  the software with that view in mind? Absolutely both. You as an engineer need to  be pretty thoughtful about where memory is going to live and one thing that could help you  manage that complexity is a hardware abstraction layer. So this is something that  a high performance cryptography library might have to introduce  themselves which is a software abstraction for running operations  over different types of hardware.

I see. Oh and I guess this also  allows to get away with you were saying each vendor will have  its own language like CUDA or yes so if you also wanted to support Apple GPUs  and like the Metal framework you could write a hardware abstraction layer that makes it so that  you as a cryptography engineer wouldn't need to know the details of these libraries. So what is  like how do we make the most efficient use of a GPU? There's a like a principle in GPU programming  that what you want to do is feed the beast.

You have all these really powerful processing  cores and the worst thing that could happen is that they're sitting around idling, waiting  for a memory transfer to happen before they can start their work. So if we have a paradigm  in which we need to transfer data from the CPU to these multi-processing cores over a  bus which is a fairly low bandwidth link, we want to make sure that either we can  generate the data in the device to begin with that we actually can avoid the memory  transfer altogether or that while we're transferring memory we're also working on  the data that we received last. So if we have like a gigabyte of memory that we  want to process in a streaming fashion

so we have a gigabyte of data here and we want  to you know send it to the GPU and get it back. But our bus doesn't have like one  gigabyte sort of bandwidth I guess. Yeah or like instantaneous. Yeah  there's some latency to doing this and even if we had you know one gigabyte  per second speed that would take a full second to process the data. So the most  naive thing we could do is send one gig, wait for that transfer to complete, do all  the processing, and then transfer it back.

And if you know let's just say we can we  can have a bandwidth of one gigabyte per second then it's one second to transfer it, our  processing time, and then one gigabyte back. Definitely not feeding the beast here. Definitely not. It's what are our processors doing  while we're transferring? Like absolutely nothing. So this is the concept of operation  pipelining. We want to pipeline our memory transfers so that it's overlapping  with processing. So as soon as we've, say, transferred the first megabyte, so we  can think about this as being like time. So let's call this host to device transfer.

So if this is our host to device transfer and  it's going to be you know this amount of time, and then on the bottom we  want to do device to host, and then in the middle we want to we want  to compute. What we'd like to do is as soon as we've transferred like the first  megabyte we can begin computing on this. And then as soon as we've computed the  first megabyte we can send it back. We can immediately start sending it back assuming  our link is bidirectional and we can send data in both directions. So what this lets us do  is for essentially the amount of time it just

takes to transfer the data as assuming that  data transfer is in fact our bottleneck here, we don't need to wait for the compute  to happen in the middle and we can overlap the transfer on the way  to the device and the way back. And in fact even we can take this this further  if our computation involves multiple steps it might make sense to partition the  processors here so that like the first half of the processors are doing the first  phase of it, they transfer data to memory, and then the second like half of  our processing cores can pick up.

So this can also be pipelined essentially? This can be pipelined. Where might that come into  play? Well for commitment we need to do these number theoretic transforms and then and then  merkle hashing and if we structure things in the right way we could potentially begin our merkle  hashing while we're still doing part of the... As soon as part of this becomes  available, hash it. Exactly. Nice. So one question that comes to mind for me  is could we have been doing this pipelining without even going to GPUs, right? Could we have  been doing this in the first place with our CPUs? Yeah that's a really interesting  question. We need to think about what pipelining is is giving us.  So what pipelining lets us do is put our compute resources to work if they  would otherwise be blocked on something.

So I gave the sort of example here of pipelining  data transfers with compute because actually the bandwidth on this bus link is is a different  resource from our compute resources. If we have algorithms like this and this which are  embarrassingly parallel, they're not really getting blocked, they're just compute bound, then  we can put all of our cores to work and it's not going to help us too much. But in other settings  we can be thinking about pipelining if we're doing signal processing streaming applications or if  we're blocked on disc IO or anything like that.

I see, or blocked on waiting for one step  to finish to the next, right? Exactly, yeah. Actually with that in mind, are there  specific SNARKs that have a structure which allow pipelining from one step to the next or are there  SNARKs that are really bad at this, for example? So a really interesting resource in SNARK  design is interaction. This idea of taking an interactive protocol where the verifier  sampling randomness allows them to avoid more work. So a STARK is an interactive protocol but  there's very few rounds of interaction actually. We need to wait for the commitment before we  proceed to this phase and then we might have some interaction rounds in our PCS opening.  But there are other SNARK designs like some check-based protocols or protocols based on  GKR that may have overall less computation

but use more interaction. And what does that  look like for a high compute environment? The GPU multiprocessors might be waiting for the  last round of interaction to complete, for the verifier to sample new randomness to get started  again. So there's an interesting design space of understanding how compute-bound our problem is.  And if it is, we might introduce more interaction. But if that's not a problem, then we might reduce  interaction in order to feed the beast. I see.

And so the reason we have to wait for  one round of interaction to finish before doing the next is because we usually  do Fiat-Shamir and we need to commit or hash everything that's happened in one step to get  the verifier challenge, right? Exactly. Okay. And so concretely you were giving examples like  something that uses a sum check protocol will use a lot more interaction than what we have here,  which is just interaction I think here, right? Yes. Okay. So here we showed a new  level of a new degree of parallelism. We took a new hardware platform that gives us  many different cores that we can operate over. And so what if we want to reduce the time  to produce a proof even beyond that? Well, we're going to scale up to multiple machines.

Right. We're going to start talking about  this whole setup multiple times. Just you could think about a rack in a  data centre with many servers, each having many GPUs connected  to different PCIe links. Okay. So how do we manage that? I mean, now we're talking about SNARK  proving over a cluster of servers. How do we feed the beast? So we have a new resource  limitation in this setting, which is network bandwidth. Okay. If  we have many servers and they're...

So this is the link between the  servers? This is... Yeah, exactly. The network links connecting  multiple servers to each other. And this, for example, becomes a big bobbleneck  in AI training where you have really advanced technology for high bandwidth data transfers  within a data centre so that you can distribute your training over a large cluster, but they're  accessing a single large data set. In the SNARK design space, we have a really interesting way  of getting around the bandwidth limitations.

So maybe I can draw a little, like a rack  of servers here or something. So we have server one and two, and these are actually just  different boxes and each one has a CPU. And a GPU. And a GPU. And its own memory. Yeah, exactly. And they're connected  generally with like a top of rack switch, but they'll be connected with Ethernet  or something like this. And so what can we do to avoid any sort of bandwidth bottlenecks?

Well, there's an amazing thing about  the SNARK setting, which is SNARKs essentially compress verification, right?  That's, in fact, the entire point of a succinct proof that you want to take some  statement and compress it into something smaller. So we can exploit a sort of compute  bandwidth trade-off by leveraging recursion. So if we want to compute a virtual machine  computation for if we're trying to prove, you know, 1 billion RISC-V cycles.

So can we think of this as our computation  trace with 1 billion rows, give or take? Yeah, you could think about this as  a computation trace with 1 billion rows. The first thing to note  is the total size of that trace, if it was all put into some memory at the same  amount of time, at the same point in time, would be enormous. Probably hundreds  of gigabytes or potentially more. So actually, total amounts of memory might  become a limitation for us as well. But using recursive techniques, what we could do is split  this into, let's call it a thousand segments, each 1 million cycles. And instead of  proving all 1 billion cycles at once,

we'll first generate independent proofs  for each segment of 1 million cycles. And then we will recursively  aggregate them. So if the, let's say the working memory size to produce  a proof for 1 million cycles is 16 gigabytes. As long as each machine has 16  gigabytes, then we can do this, I guess. Yes. Okay. As long as each machine has 16 gigabytes  and we're going to compress, the output of the proof might be 200 KB or something  like this. The next thing we need to know is how costly is it to do a recursive proof  that compresses two leaf proofs into one?

And we want to do this because, so we  have a thousand proofs for like one proof per segment. Yes. And we want to bring  it down to just one proof for the whole thing. That's exactly right. We want to compress an arbitrarily large  computation for any number of cycles into a single proof that's a manageable  size. And we're going to do this by distributing the segments of  computation over the entire cluster. And then distributing the work of  recursively compressing two proofs into one. I see.

So, you know, we can think about these being our  billion cycles and we're actually going to build, it's pretty common to just build a  binary tree of proofs where this proof is going to produce a new proof  blob here. And then at the end, as you said, we're going to take all of  these proofs and create our final proof. Okay.

And why are we doing this as a tree? The reason we're doing this, so  that's a great question. What else could we do? We could potentially  just go through this in sequence. That would be in literature, sort of like  IVC, incrementally verifiable computation, where you're updating a running proof.  And the reason we want to do this in a tree fashion is because that allows us to  have more parallelism. Always the answer. Always the answer. So how deep is this? Well, if we have  a binary tree, it's log depth in the number of segments. So it's actually, you  know, log two of the number of segments.

And this essentially dictates  our latency of computation. And also if we think about it from a  resource utilisation point of view, having more proofs to produce at any given time  means we get to put all of our servers to work, which means we get to put all of our  GPU cores to work and so on. Right. So as we move up the tree, we can use, we can free  up some GPUs, some actually servers in this case. Yeah. I mean, if we're just trying to produce  a single final proof for 1 billion cycles, as we get closer to the end of the  tree, our servers are going to start idling, but they've done a lot of  work at that point already. Fair.

Another really interesting thing happens when we  get up to the level of cluster level computing, which is we're going to run into a new  bottleneck and that's around witness generation, which is pretty much the  only thing we haven't talked about as an explicit step. So we talked about how this  is parallelizable. This is parallelizable. We talked about at this point, four different ways  to compute when you have enough parallelism. When you get up to the level of essentially having as  many servers, many GPUs as you want, what is the sequential bottleneck? It's actually just the time  to emulate the RISC-V execution and to store all of the information needed about that execution to  do the parallel work of producing segment proofs.

So to fill out the trace? Or it's  more than that? I think to begin with, it's to fill out the trace, but we  can actually be more clever than that. We don't need to fill out the entire  trace sequentially. What we're going to do is a sequential preflight  execution. This is a term that RISC Zero uses and that I first learned from them. You'll do a preflight execution, which is a pass  over the computation that is meant to be as fast as possible, but it's going to log enough  data about what happens in the middle of the execution to then produce the segment witnesses  in parallel. So if we have a thousand segments and let's just say we snapshot the entire  memory at every segment of 1000, then we'll

do a second pass over the entire execution,  but in parallel, running over every segment, doing the more expensive work of filling out the  trace table. And the other thing this is going to let us do is save memory because we can use less  memory to store the snapshot artefacts that we need during preflight execution than the amount of  memory required to store the entire segment trace. So preflight means I go over my 1  billion cycles, I mark a few checkpoints, and then it allows me to fill up traces from  each checkpoint. That's right. Brilliant.

And we can in that way also begin to  parallelise our witness generation. So are there any teams using all  these techniques that we've seen so far and implementing everything in one go? Yeah, there are several really talented  techniques that have achieved basically the unthinkable benchmark of having  real-time proving for Ethereum blocks, meaning the ability to prove an Ethereum  block execution in lower than the Ethereum slot time. So Succinct and SP1 have been able to  do this. RISC Zero has been able to do this with their STARK technology as well, using exactly  this entire set of techniques of GPU programming, cluster-level programming, fast witness  generation with preflight execution,

and achieve something really remarkable  using many servers coordinated at once. So I guess I'll keep prompting. Can we  do better? Can we be faster or get the same speed with fewer resources, fewer servers? Yeah, so what are the resources we care  about at this point? We care about the latency of computation. I think if  we tried to make that 10x smaller, we would run into new bottlenecks  using this set of techniques. But also we start to care about the cost of  computing this as well. Money is a resource, and we might care about the power required  to produce a large SNARK computation.

So really, the future of this  industry is custom hardware. When it's a big enough problem in a big enough  market, we can reduce the cost of producing many proofs by having dedicated chips that are  optimised for these types of computational problems. So where in the story does this  fit in? This is essentially about reducing, going all the way back to the  beginning, reducing the number of instruction cycles required to do  the computation in the first place. So these field multiplications  that we have to do everywhere.

Yeah, being able to do field  multiplications with either fewer resources, or in fewer instruction cycles, or at a higher clock speed. And for that, we need  to design new hardware. So let me erase this. I guess this is analogous to how  GPUs first came to be, right? Exactly. I mean, if we think back  to early graphics programming, it was a software engineering marvel to  be able to produce stuff like Doom with regular CPUs. And then now we have rich  graphics by developing custom hardware with processing units that are  adapted to that specific problem.

So what does it take to actually do a field  operation in a CPU or a GPU? For a prime field, it looks like an integer multiplication with  additional cycles to perform a modular reduction. Right. So one thing we could do is just make  the native data type of our processing unit to be field element multiplications.  We could even handle extension field multiplications using instructions instead  of many cycles of different instructions. The other thing is when we look at NVIDIA  GPUs and what they're optimised for, they are more limited than CPUs, but they  still optimise for floating point arithmetic.

Mm-hmm. And in fact, they often advertise  the number of FLOPS, floating point operations per second that they're able  to do. They have flexible control flow. So this is like if statements? Yeah. And they have a very  flexible memory hierarchy, meaning your core can access any  piece of data from global memory, and the network that's routing data between  the cores needs to be able to handle these.

So talking specifically about GPU cores, right?  I'm talking about GPU cores. That's right. Just because the word core has been  used at every layer almost. Okay. Global memory with cache. So because  if we wanted to design hardware that's specifically good for SNARK use  cases, we can adapt them to the actual types of memory access patterns and  the actual type of computation. So we might be able to get away with a memory model  that's more limited than global memory.

We also see this happening in the AI space where  you have experimentation with different types of memory models like systolic arrays that can be  targeted for these specific types of workloads. We may not need flexible control flow because  we're basically doing streaming passes over data, and no one is really using floating  point operations to do SNARK computations. We mostly care about integer  arithmetic for prime fields, and then doing bit level operations  for masking in order to do reductions.

So my company Irreducible basically investigates  this problem and is designing custom hardware for SNARKs and actually for a specific SNARK. So  one thing that we learned early on is if you're opinionated about what the protocol is so that  you can adapt the hardware really well to that use case. Some of the things that we've learned  is that there is a type of finite field that is very amenable to cryptography called binary  fields that are extremely good in hardware. We talked in our last segment a bit about the  cryptographic advantages of binary fields, but also there's hardware level advantages. So what are binary fields? They're a  different type of mathematical object.

And so Baby Bear, which is what we  began this session talking about, is an example of a prime field. So  we can put this for example. This is actually the set of integers  modulo a 32-bit prime number. A binary field, there is a 32-bit binary  field that systems like Binius use, and I'll just call this B32. There are  different representations of binary fields, but we'll treat them all as one family for  now. And one thing that we've learned in our investigations is that the hardware efficiency of  doing 32-bit binary field multiplications versus

32-bit prime field multiplications, it's about 5x  more efficient for a binary field multiplication. So here we're saying the number  of CPU instructions to do one field multiplication is smaller here than there. Actually no, it's more interesting than that.  This is talking about if we write a digital logic circuit, so we're not talking about CPU  cycles anymore, we're going to write a native Boolean digital logic circuit, which is going  to get created with transistors and gates, that the number of gates required to  perform this computation at a certain clock speed is five times lower than this.  The number of gates at the same clock speed?

Yes. And is this a secret? Actually no, this  has been well understood in cryptography, and that's why binary fields show up in standards  like AES and in various error correcting codes. So is this a pure win? Well actually we have found  that it's really hard to take advantage of this on traditional CPU and GPU architectures. So GPUs  have these dedicated circuits inside of the cores. The GPU cores are just digital circuits that do  integer multiplication. They do not do binary field multiplication, and they don't have  instructions that are particularly helpful for that. So even though at the native digital  circuit level binary fields have this advantage,

when you're trying to use widely  available hardware today, it actually makes a lot of sense to stick with prime fields. However, if we're talking about the future  of creating custom hardware for SNARKs, we think binary fields have these  advantages. So what else can we do before we have these chips?  There are devices called FPGAs. Field Programmable Gate Array. Field Programmable Gate Arrays.

I'm not going to write that all out, but it's  basically reconfigurable hardware. So Gate Arrays is, as we can think, a bunch of gates, and we  can choose what gate it is and how they're wired? Yes, and you can actually write the same  sort of hardware description language, the same sort of hardware designs that you  might go and send to a foundry or a fab and get back an actual chip. You could instantiate  these on an FPGA with some modifications. These devices are typically or  they're commonly used for prototyping in order to test out your circuit designs,  but in special cases where consumer hardware doesn't do an operation that efficiently,  you can actually run them in production.

What we've seen is the field multiplication  throughput of binary fields that we're able to achieve in an FPGA rivals the field  multiplication throughput of consumer GPUs using prime fields, which is  pretty remarkable that you have this hardware that's designed for a specific  purpose and that reconfigurable hardware, by choosing a different underlying  mathematical object, could compete with that. I see. So if you ported that  same design to an actual ASIC, you expect to see it to be faster than the GPU.

Yes, and ultimately, why is this? When  you put things into a chip and you get rid of the reconfigurability, you're able  to produce an extremely power-efficient and scalable design at the expense of it takes  a while to validate this hardware design, it takes a while to get it back from a fab,  and it's quite expensive. So I think when the space matures and stabilises, we will end up with  custom hardware to do these types of operations. That makes sense. So one thing you might ask is,  am I talking about ASICs here? What is an ASIC?

We've seen those in Bitcoin mining or  Application-Specific Integrated Circuits. We actually probably want more flexibility  than an ASIC. An ASIC is a specific circuit. We can get more flexibility by building  something that's like a GPU architecture, but with an instruction set that's adapted to  what we need. So why is this more flexible? It means that we can write software that  our custom processor is going to read in and do some type of configurable operation, but  instead of configuring it at the circuit level, we're configuring it by making it  a software programmable processor.

I've read these referred to as ASIPs,  Application-Specific Instruction Processors. So can we think of it also as like a  Binary field Processing Unit, like a BPU? Yes. Cool. So that's one way that we could get the advantages of custom  hardware with some flexibility. That makes sense. I think  that's everything I have to say about high-performance engineering for SNARKs. Amazing. So we have parallelism.  Eventually we can't throw more machines because we're limited by memory.

Then we have these pipelining ideas, and then we  saw how to split up witness generation and how to split up even just the whole statement  and make smaller proofs to be able to cluster-level parallelism and then aggregate  all this. And then custom hardware. Exactly. Cool. Thank you very much, Jim. Thank you. This was a pleasure.