EIP-7939: Count leading zeros CLZ opcode

Transcript

you can make it very cheap to compute like 63 times cheaper compared to the most efficient solidity code right now. So I would say it's one of if not the lowest hanging fruit we can implement today to speed up the EDM as in the computation not stick assess SS is the main bottleneck but for the computation part uh I think CLZ is one of the lowest hanging fruits and this actually has a advantage like this convention makes some operations like string searching easier. I will argue that it's more than 63 times cheaper. And of course, you get a smaller bike code.

[Music] Hello everyone and welcome to Penney, the series where we unpack Ethereum improvement proposal with people who are shaping Ethereum's future. [Music] This is episode 153 brought to you by ECH Institute. I'm your host Puja Randan and I'm joined by my colleagues Vilin and Akash.

Today we are diving into EIP 7939 which proposes a new op code count leading zero documented in April 2025. This is a standards track core EIP currently in draft status and SFID for Fusaka network upgrade. The proposal is co-authored by vectorized Georgios Yan Ben Adams and Julio. Joining us today is one of the co-author vectorzed to walk us through the importance of this op code, how it can reduce compute and proof cost and what we can expect from it in the upcoming Fusaka upgrade.

Welcome Vectorized. >> Okay, good morning everyone. >> Could you tell us a bit about yourself, your professional background, how you found Ethereum and what are you currently working on? Okay. So my main project which most people know me for is soul lady.org. You can visit sady.org. So um it's like a library of solidity slippers. It's a very highly guest optimized library. So most of it is written in inline assembly because we want to really make things fast and cheap and small and it has some cool cutting edge features a bit experimental but we do our testing very rigorously.

So lady is free open source software but to make money into it I work for it. So which is a paradigm popco they are trying to make some accounts and they also they also maintain ref which is one of the most popular L2 clients. Another job is uh I work at clusters clusters.xyz which is kind of like a a multi-chain identity system. We also maintain like delegate cache and other utilities. Yeah. So most of my work s can be overlapping and so lady is in the middle of the overlaps and because in so lady I have so many occurrences where I

have to do this count leading zeros um I would say sub procedure I decided like why not just make an op code for it and how how did I come into Ethereum this is a story I have to tell everyone every time the long story short There was one of my friends uh I think he's like a product lead at mentor right now he's called Joshua Chung he went to the same university as me and he was like you are so into all this optimizing stuff you spend so much time optimizing weird useful stuff in your university you are such a perfect fit for Ethereum because everything is needed to the op code level you have to optimize

everything so I was very skeptical then one day somehow I was requested to make a NFD project and I was somehow have requested to learn solidly. >> So >> interesting backstory. >> We love to hear these back stories because it always connect us from the community and we know that any developer and every developer is coming from community itself. Thank you for sharing it with us. Well, we want to make this EIP easy to understand for the broader Ethereum ecosystem. And the goal here is to explain what it does, why it matters in a way that people understand what to expect with the upcoming upgrade. We hope this episode helps simplify the concept for everyone. So without further

ado, let's peep in. >> Okay, let's go. So EIP7939 leading zeros CLZ. This is a op code that you can find in most modern processors like your Apple M4 chip, your Intel latest chips, your Ryzen, I think most of them have CLZ because it's such a important bit wise operation but the EVM doesn't have it yet. So upcoming Fusaka for hope gets in and the adoption will be fast. So what is cow needing zeros? What what does it do? So you have a number uh it can be maybe 32 64 bit but for the EVM we are using 256 bits.

So CLZ in the EVM it will return it will count the binary zeros. This is in binary format. So assume that this is a 256 bit number in binary form. Start from the most significant bit and count the number of consecutive zeros. So for this example the count leading zeros is three and we have a special case say the number is zero for the EDM we define the result as 256. So this is to keep in convention with CLZ on uh like modern chips. So if you use CLZ on modern chips if it's 64-bit it will return 64. If the CLZ is 32 bit

it will return 32. Yeah. So you're trying to keep in convention with what processes have implemented and this actually has a advantage like this convention makes some operations like string searching easier. Okay. So there are some identities for CLZ. So for two 256 bits so to compute log two the base 2 logarithm of a number x just take 255 minus cz x. So we don't need a lock two op code because it's very simple to to get lo two from a CLZ ctz is also very simple you just take 255 minus this down here is basically isolating the this least significant bit

so it's quite trivial to get cz so you can get lo you can get count trailing zeros so for count trailing zeros you just isolate this smallest bit and then you count the leading zeros and you subtract it from 255. So you don't need to implement this CDC. It's a waste of not space. So CLZ is a very general mathematical operation. In math is used in log two, square root, cube root. A lot of sublinear functions they can be you can use CLZ as a way to find the

initial approximation and then you refine it from there. For square root you can use CLZ to find the log to in constant time maybe a few op codes then you use some Newton ruxon to converge to a nicer result. It's used in data structures like big maps. skip these. I heard uh more and more CL obs like order book onchain. They like to use feedbacks. So maybe CLZ will make their life faster. It's also used in some algorithms like in so we have a run length encoding compression.

It uses CLZ. We have a string search which uses some form of CLZ too and it's like you can find everywhere once you recognize it. So for example down here this is Pascal's triangle and if you represent it in binary form it somehow produced this nice looking shape and retardic being the genius he is he sees all this relationship like immediately so he said yeah the logarithm because the length of this binary string is essentially lo it's a parable yeah so cz is like lo you can just uh comput we sell that and it's like used everywhere you can see everywhere once you see you

can't unsee it so why do we want to make it a op code even though we can emulate it today uh you can make it very cheap to compute like 63 times cheaper compared to the most efficient solidity code right now it's cheaper to prove for SP1 I will argue that it's more than 63 times cheaper and Of course you get a smaller bite code. Why you get smaller bite code? Okay. Uh later I will show you uh because the way CLZ is implemented today we use quite a lot of giant magic constants and all these magic constants they occupy a lot of by code space. So there are some considerations why I propose this op code one is

stateless. You can understand the cost you can profile the cost very well and it's very easy to implement. So back then at interop in bing well after the first day I think everyone implemented it in just like one day. So CLZ is available in most modern processes and I believe that we can learn a lot from how all these modern processors evolve because if you look at um a modern processor they also face like you face the same constraints as a EVM.

You can only implement so many op codes on the modern processor and therefore you want to select the most useful op codes to be included and CLZ is available in most of them. So because uh it's so universal it hints to us that yes this is a good code to include. So I would say it's one of if not the lowest hanging fruit we can implement today to speed up the EDM as in the computation not STS access state SS is the main bottleneck but for the computation part uh I think CZ is one of the lowest hanging fruit can have maximum impact with just one op code.

Okay so the initial idea has been conceived way back in 2022. If you view the forums post on Ethereum magions, it's all the way back in September 11. But then I didn't have the motivation to push it because I asked about people say to get a op code into mainet you have to implement in all the clients you have to get a lot of support here and there which is very difficult. So I thought okay maybe considering the difficulty and everything maybe it's not time yet.

But then after I maintain so and build up so more and more I realized that there are too many places where CZ appears. So after EOF has been removed from Fusaka people are like so the idea is like EF makes things makes the execution part faster and without EF how can we make things faster why not just implement one CLZ code since it's everywhere. So a few days after I quickly draft out 7939 CLZ went to Berlin and convince everyone to implement it and somehow by sheer luck and community support very strong community support

CZ is selected for inclusion foraka and I'm very thankful for all the people who supported this o right now today if you want to implement CZ you have to do this chunk of code is quite intimidating looking. It's quite scary looking. And this I would say this crazy magic numbers down here. There's a way to find them. I use something called the Z3 solver in Python to find them. This stuff is like 184 guess. See how ZZ op code is like three guess. So 184ide by three around I think 63 or 64. Yeah, that's how I got the I approximated it to be 64 times speed up. So this uh implementation I think

unis swap v4 use it. Most people who use bitmap they also will use it because it's like you can only get so fast. This is the fastest you can get today and it has been like for money verified. So yeah, you probably want to use it. So there are a few variants of CLZ. There are some areas where you don't need like the full precision of CLZ. Maybe you just want to use CLZ to find to count the number of leading zero bytes. You can use this. So this is a specialized variant of CLZ. In CD compress, we want to count the number of leading zero bytes. We do all these magic down here. And the thing about specializing CLZ is that each time we specialize, we have to compute new

magic constants for it. And uh this leads to more work and also a risk a possibility that you can introduce bugs because you have to find new magic constants. So in another location in so we have another variant of CLZ somehow uh this constant I did some magic so that this lookup is essentially this magic thing down here. Yeah. So I adjust the magic constant so that I can shortcut some operations. And for square root you don't need the full precision of CLZ. You can do a approximate version and let the Newton bson

somehow correct the results. You just need a good enough approximation. So different areas we specialize CLZ differently and all these like it looks cool but in the end you could have one simple up code to replace all them. So let's say we have CZ tomorrow. Well so lady might not have the flexing power anymore because all these easy math can be just they can be replaced by a single up code. So I'm sort of like saying okay I give up my 3x for the back so that everyone can be faster and also sometimes we tend to avoid algorithms because they need to use CLZ. So for example if you can think of some

algorithm that uh use CLZ. So right now CLZ cost 18 for 184 gas I think and you will need to repeat it many times. You will be like okay this is expensive because you use CLZ. Maybe I will use some other suboptimal algorithms that doesn't have CLZ because it's just so difficult to implement CLZ in EDM today. So next time we won't have this restriction anymore. We won't be restricted to some algorithms just because of the essence of this op code.

And finally, I believe it can u make compilers perform better. Like for example, if you go back to this giant uh chunk of code, the compiler might have some difficulty inlining this. Although this is completely branchless because all these constants are quite big. It occupies a lot of space if you inline it here and there. So the compiler might choose to not inline this function. And if it's just one op code, the compiler can inline it very easily, very triggery and it can therefore optimize it easier because if you inline the big chunk of code previously,

the compiler need to find out what is the stack ordering such that things the stack operations are minimal. They have to shuffle the stack all this weird stuff. So if you have one op code, you don't need to like do all these st shuffling to optimize the code. It's just one op code. So your compiler uh your compiler will have an easier time to inline and optimize. So your compiler your compilation time might be faster. So to implement a CLZ, you can do it in a very SP1 friendly way. So right now I think to prove the EDM uh most people I think the cutting edge is SP. So ref is compilable to SP1 the RV32 IM subset and

SP1 can prove it. So uh the idea is that instead of so previously we have all those giant op codes here and there all those giant constants and all those uh like fancy math in the application layer but now we push to the native layer and because we push everything to the native to the client layer instead of the application layer you can avoid some operation that are not very zk friendly. D. I intentionally wrote it using branching code instead of CIMD because this makes it easier to compile for RV32 and also once it compiles to RV32 IM is

faster if you have branching code and also this implementation doesn't use any dynamic right shifts which is one of the most expensive operations in SP1. If you implement it uh this way is quite fast for regular compute as fast as the regular 256 bit app. So it's like it's fast for regular compute but for SP1 proving it's actually faster cheaper than yeah so if you look at the table of S1 RB32 IM cost you'll find that shift right is very expensive and if we want to go use this uh thing to compute CLZ you see all this shift right shift right

shift right shift right this is going to be a headache for SP1 so we make it native we avoid all the shift right it becomes much easier to prove. So I anticipate that compilers can support this on day one because we have in the past solidate has supported like push zero on day one and I think transient storage on day one. So I think it's possible this is like a single op code with a single operand like transient storage. Wait, I think transition storage. Yeah, T load also has a single right. So we we know what to do to implement to support it. The thing is L2s maybe L2s will take a few

months to catch up because some L2s do a lot of customization here and there. So pulling from the minute clients, maybe they need a few months to merge everything. Yep. I think uh that's it about CLZ and hopefully in the upcoming months to years the problem of fully utilizing all the 256 bits of the EVM will not be that much of a hassle anymore. >> Thank you for sharing this. I was uh really interested to learn about your motivation like why you make this push after EU is out of pusaka but you very well explained that and your story for

going to Berlin and convincing developer to implement this in client is pretty interesting I am happy that things worked out we don't think that EVM is dead there would be proposals which would be coming up this support and there are certain proposals which are helping the present developer community as well. Once again uh thank you so much for sharing this presentation. I do have a few followup questions. If you're fine we can perhaps go ahead with that.

>> Okay, let's go. >> All right. So you are proposing this EZ as a native op code. I'm wondering why you just did not leave it for compiler. You mentioned that solidity and viper compiler will be compatible from day one. Do we really need to have this as a native op code? >> Okay. So back then in the very ancient days there is no shift left and shift right in the EDM and people have to emulate shift left and shift right using multiplication and is actually very tedious to do that and expensive. So they introduce shift left and shift right op code. I think for CLZ is even worse because it's not just a simple

multiplication. You have to do all these crazy acrobatics just to count the leading views. So yeah, you can do this today. It cost 184 guess. But if your algorithm needs to implement this in the loop, uh you're going to rake up a lot of gas. >> That is interesting. You already have explained that it makes things cheaper. Argued for 16 times cheaper. wonder does having a native CLZ also makes things safer. >> It makes I I think it'll make things safer because right now a low-level developers like me, we like to flex our bitwise

techniques by creating variance of CLZ and all these constants uh we have to use this thing called Z3 to hunt for all these constants for each specific case. And if a developer doesn't know how to do that, okay, I think the developer should know how to do that. But anyway, it introduce more effort and room for error. What if they forgot to update a magic constant? Yeah, something like that. >> Yeah, sure. Decreasing the room for error will definitely make the code more safer. Well, my next question is with respect to gas and performance. In the proposal, you have mentioned or proposed a gas cost for CLZ. I wonder how did you benchmark this? Maybe you can talk a

little about the proposed gas cost. >> Okay, so today there's a code called app add is let me see that takes in A and B A plus B two operants and it cost three gas. So TZ takes in one operand and that's also one operand should be cheaper because every time you take in an operand you have to plop things from the stack. The EVM emulator has to do more operations. So yeah one operand is cheaper than two operants and okay let's say we ignore the all the overheads of the operand popping of popping the operants how fast is CZ just for regular compute. So we

implement this. We implement like some kind of dumb program to do 1 million x some dumb program to do 1 million clz and we time it. And both of them took approximately the same amount of time like 17 seconds versus 19 seconds. CLZ is slightly slower like 19 seconds compared to AD but it's not like uh if CLZ is say 30 seconds then maybe I will propose a guess cost of five but because it's so close to the runtime of ad I think a reasonable guess cost is three >> all right and just trying to understand

this better so when we are comparing with any other op course like add for me this gas cost that we are having it per se it makes it cheaper that's why we have this proposal is that a correct understanding of it okay >> yes >> I noticed a conversation in fellowship of ethereum magician where a developer suggests that when we are using gas cost of CLZ with respect to any other proposal I think he mentioned a particular EIP7904 which is general repricing is suggesting the gas cost should be one. So do you suggest that the gas cost proposed with this proposal should not be a fixed value but it can be arranged?

>> Okay. I think in the future if somehow all the op codes are repriced to one guess all the arithmetic op codes are just one guess will definitely be one guess. But there's one op code I'm a bit worried about which is shift right. Shift right is very unfriendly for SQ1. Maybe shift right need to cost two gas if we replace everything. But that's just my uh two cents. Maybe uh further benchmarking can give tighter bounce and maybe we can safely put everything as one guess. Maybe we can do that. But basically to decide on a safe bound we just have to benchmark everything in the future again. But for now free guess is

a safe bound for SP1. know the sourc even considering ZK proving uh it should be cheaper in SP. >> Yeah, sure. I mean uh it's good to have a safe bound and we can perhaps continue more optimization research and uh we can come up with other variants of it in upcoming EAS if needed. Well, we know that this proposal is now considered for KUFA. You did talk about your story for going to convince each client team collecting feedback for the proposal.

>> Okay. Uh it almost didn't get into Fusaka because I by the time I wrote the EIP, I drafted the EIP, it was already past the deadline for consideration. >> So I have to really uh convince everyone. But because it's so easy to implement like they everyone implemented it uh in a day if but if you sit beside uh them and you see them actually implementing it maybe it's just like 15 minutes and it's done. >> I mean I would say you became very lucky here or the proposal is like really really trivial that people have accepted it because at this point we generally see proposal going out not getting in.

Yeah, I I think it's I'm very happy that the Ethereum core developers uh community all the client teams are very primatic. Okay, so the thing about EIP to uh these days is that they are I would say getting more and more complicated because all the low hanging fruits have been already eaten up and CZ is one of the remaining low hanging fruits that can be just sneak in in a like a afternoon's work. So I think this is one of the last few no hanging fruits that we can find and luckily uh I'm so glad that they included this in Fusaka because if it's not going to gamster them it will be bottlenecked by all the other heavy EIPs that are aiming for

gangster them and wow the EIP for gamster them are I say non trivial >> right very true well at this stage I hope the answer is no but still I have to ask my question do you see any blocker or any open question that that needs to be answered before this proposal is moved forward with the AIP process. I think uh we have profiled it. We have um make the spam test net to make sure that this doesn't open up any DOS risk. So I think everything is ironed out. Just go ahead. Uh I think solidity maybe implement it because there might be some code base that have

a function called CLZ. it might clash with uh some existing code bases if they have CLZ as a global identifier. Yeah. But other than this so the two adoption issues is that maybe it might break some existing code base but highly unlikely because CZ is such a lowlevel codes only optimizers and like very low-level math experts will need to touch it but it's used everywhere and I think L2s maybe they will take a few times uh months to catch up so there might be some fragmentation but in the end like key store we have a maybe six or seven months where everybody uh it's fragmented here and there but eventually

everybody supported T store trans storage yeah I think maybe in 2026 [Music] June probably you can use it everywhere >> that's good to know but when we are talking about the use case I'm wondering outside the devet testing are you by nishans aware of any real contract or tool which either is already using this proposal or is going to be benefited from this up code >> so the thing about op code is that minute has to go first. uh this for pre-ompiles L2s can go first but for op codes once a compiler supports it you can't conditionally

disable the support say for certain networks solid doesn't support uh conditional disabling of op codes so if you want to introduce a code minute has to go first so right now uh nobody has no code base out has CLZ uses CLZ as a native op code. Yeah, there has isn't any L2 that uses CLZ right now. Main has to go first. >> Yeah, and thank you for sharing this very good difference between the O code and the pre-ompile like up code is definitely dependent upon the mainet before that projects may not be able to use it. Well, my next question is with

respect to proposal status. We notice that the proposal is currently in review status which is fair because this is a relatively new proposal and you are still working on it. But because this has already been SFI it is eligible to go to the review status but it depends upon the author and like if there is a co set of co-authors they can decide on it if this is ready or are you expecting any changes before this can be moved to the review status. >> I think yeah I have to make a PR to move it to review status. So right now I think I have to maybe I will clarify like some grammar in the maybe some word phrasing in the EIP. It's mostly like editorial issues because like u people

are confident about the course and everything else. So it's more of like tidying up the EIP before we get ready for review then last call and final. Maybe there's no last call for EIP. Yeah, >> that depends upon the stages. When the proposal will move to the public test net, then it will become last call. But for now, you can rest and review status. >> Yeah, I make uh you have to complete the review. >> Whenever you are ready, please feel free to make a PR and we should see the proposal and review status.

>> Well, that concluded all the questions which were with respect to the proposal. I do have a set of rapid fire round. [Music] We want to have this questions answered in one word, one sentence phrases as small as possible. So, are you ready for it? >> Okay, let's go. >> What's one EIP you wish more people paid attention to? >> Just to Eve. I forgot the number. It's by Charles Cooper, the Viper maintainer.

My next question is what is more fun to optimize gas zk proof or compiler internals? >> I think yes because you have freedom to even new >> and people love gas optimization. Well, >> thank you. >> What is one dev tool you can't live without? Definitely. Foundry. >> Cool. What is your favorite thing about working on Ethereum? >> The community really cares and is intellectually honest.

>> Right. We have a very good community here. If you could instantly ship one change to Ethereum, what would it be? I think this has some overlaps with what is the most under considered EIP. I will immediately ship gas to E but with a catch 10% of the gas that is burned will go to the validators. >> Mhm. People use the up code to burn gas to convert to E and everyone all the way earn helps the network earn more fees.

>> That's right. Well, if you have to uh say what would you say is the most underrated op code so far in Athereum's history? >> Mod multiply module. I think without M implementing custom cryptography will be impossible and it's used in quite a lot of fancy meth. >> Very well. My next question is uh EIP you have changed your mind about recently like earlier you didn't like the proposal now you like it or earlier you like the proposal but you don't like it anymore.

Yeah, see I have more but EIP I think I don't have much regrets on any EIP. Wait, wait, wait. Hold on, hold on, hold on. I think there is one but it's a very it's a you know written data copy. Yeah. So written data copy is proposed after stuff like core data copy has been proposed and code copy Xcode copy. So sore copy, code copy, core data copy, all of them have a very consistent behavior. When you copy out of bound byes, any bytes that are out of bounds, it returns zero for any out of bound by bites. And sometimes I abuse this

behavior to a zero memory memory with very efficient in the most efficient way as possible. But return data copy, if you copy any out of bound byes, it reverts. It does a revert. I think that's inconsistent. It also leads to some difficulties in implementing it in the compiler. >> Thank you for that. And my last question for today is one word that describe your coding style. >> Okay. I think it's a bit cheesy to say like uh is formless uh like you imagine. Okay. formless like jikundo. You just do what is the most

efficient way to get to the result and you do it in a way that is somehow maintainable and also in a way that allows you to improvise and discover new optimizations easier, >> right? And everyone has different style. It's good to know how each person deal with it like how they prefer it. Very well. That brings us to the end of today's episode. Huge thanks to Victor for joining us on Penep and breaking down EA79.

If you want to dive deeper into this proposal, please check out the EIP as well as join the discussion on Ethereum Magician. Dear List, if you find this episode helpful, please share it with fellow Ethereum builders and users. Let us know which EIP you would like to cover in our next episode. Please check out description for ways to support our way. Until next time, keep learning, stay curious, and keep perfecting Ethereum. Cheers.