# EPF - Nethermind/IL-EVM

- Speakers: [Siddharth Vaderaa](https://streameth.org/speakers/siddharth-vaderaa)
- Channel: [Devcon 7 SEA](https://streameth.org/devcon_7_sea)
- Date: 2024-11-13
- Duration: 11:40
- Watch: https://streameth.org/watch/673428639dbb7a90e1a39ee7

## Description

This talk will discuss my EPF work on Nethermind's IL-EVM project, which included developing tools to analyze EVM execution patterns, writing  (optimised) opcode and top pattern implementations, and conducting and writing tests.

## About the speakers

### Siddharth Vaderaa

A musician and a dev.


## Transcript

. This is my project. This is an of the loose timeline of the project. So week 6 and 8 were sort of done on some warm up tasks to kind of get a feel of the code base. Week 9 and 12 was spent on doing some research for the upcoming task, which was basically gathering N-gram stats. The core focus of the project was doing the stat analyzer implementation, which happened between week 13 and 16. And then week 17 and 18, I was basically running the stat analyzer, getting the N-grams, and then actually doing the N-gram implementations for pattern detection mode for the ILEVM. And week 19 plus, I was just basically doing bug fixing and also just generally looking at ILEvm and bugs and i found like five opcodes that had problems and i fixed those um so right so the first part was basically it was it was my first task i just joined i leave i just started the project and uh i think it was the first meeting with the mentor and I basically was, the mentor asked me do you know where I was because the mentor was sort of focusing on EOF implementation so nobody was working on IL-EVM. I just sort of took the task that was sort of remaining and I started working on it and then my mentor joined in and that was sort of finished. The next task that I did was some core DB stats. Again, this is a warm-up task. Where I just tried to get some Ngram stats from the database. So these are not execution stats. The implementation was very slow. It was done over the weekend. Again, it was a warm-up task. So now we kind of come to the, you know, the... Oh, this is the research and algorithm. So there was a lot of research and literature review that was done for basically big data analysis because we are dealing with execution stats for Ngram, which is actually a lot of data. And these were some of the papers that were run, that I read. Of note are basically the heavy keepers and also sliding sketches in time zones for data stream processing because these are both single pass algorithms. Because we wanted to implement an algorithm that is single pass for this amount of data and is efficient. So after a while, we just sort of, with some discussions with the mentors, we just settled on simple count and sketch. The basic principle of the count and sketch is that you have sort of D hash functions, and then you have like, let's say, W buckets. And whenever an item comes, that gets hashed, and it's put into one of these buckets. So for example, here you can see just data for one item. So in this case, the true count will be the lowest count. That is one. 25 would be an overestimation. That means there's a collision. But because we have many hash functions, if you take just the minimum of the count, you can actually get the true count adjusted with errors, et cetera, for the data that we need. So, additionally, you have these bounds of epsilon and delta that control the probability and the error that the data structure has. And you can actually configure the stats analyzer to use both width, depth, epsilon, and delta. So now for the main thing, which is building the stat analyzer. OK, the first part was encoding the n-grams. So to encode the task was given is that basically we just need to find two to seven opcode patterns, like two to seven, the size of the engram is two to seven, and the way to basically do it, and this could work for like up to n engrams actually, it's only limited by the data type. But basically as the engrams are coming, as the opcodes are coming in, we just basically left shift opcode and then we or it with the next opcode and we encode it into a long value. Because a long value has 8 bytes, so it can actually encode 8 opcodes. And if you have used one of the data types that is common in clients is you have a 32 byte data type like UN256. So technically it could go up to like you have a 32 byte data type like UN256. So technically it could go up to like, I don't know, 32, 32, 32 Ngram like size of the pattern can actually technically go up to. Oh, wait. Right, then comes tracking the Ngrams. So instead of like tracking n-gram separately, like of 2, 3, 4, 5, 6, 7, what we can do is we just get the n-gram, the long value that we have. We find the n-gram that is the maximum of the size. Like, for example, if we had the size 3, right? And you can actually have 0xFFFF, which is size 2. That's the maximum because you cannot have anything over this would be a size 3. And then we can actually select that out. And basically, if you have like an n-gram like pop, pop, add data, you can actually just iterate over those that long value and actually get these three n-grams that don't have to be tracked individually and saved anywhere and they just basically you have these sort of ephemeral long values that just simply go into the cm sketch for accumulation. Yeah, iterates on the basis of the core of the SAT analyzers, it's a real piece of the count-win sketches. And you have a top-k queue. You iterate over the bytecode, you encode the N-gram, you accumulate the counts in the CM sketch. Also, a new sketch is provisioned based on what our error threshold is, like what is the max error we're able to tolerate. So we can configure that and then new sketches are provisioned based on that. It provides the top K patterns and provides the error and confidence for the stats. So you can actually have varied performances for this, so you can actually make it really fast and less accurate or slower and more accurate. You have that capability. Right, so then how do we gather the data? The data is done as a trace. It's a trace plug-in. It's straight from the EVM. You can configure this to be enabled or disabled. The tracer then finally dumps the data. It calls Stats Analyzer and then it can dump the data into a file as a trace on the file. So how does that look? This is sort of the output. You can see initial block number, current block number, error per item, confidence, and these are the stats, for example. You have the pattern, you have the bytes that it is, and then you have the count that you've observed. You can go and you can specify how many you want. To give an idea of the configuration, that you can see all these are, like this is the config that you can do. You have enabled the file to write to the right frequencies, like how many blocks you want to write this to. Ignore set, like you want to ignore jump destination. That's not really useful for analysis, so you can actually write ignore set. You have an instruction queue size, the size of the queue used to gather instructions per block, right? Because that, again, it can increase as time goes, so you want that to be configurable. You have the processing queue size, how many blocks are now stored for processing. You have the number of buckets that you can put in the sketch. You have the number of hash functions that you can put in the sketch. You can put the max error that you're willing to tolerate in the CM sketch. You have the sketch minimum confidence that you want to tolerate you can analyze the top n grams to track like ten ten thousand hundred thousand you can put analyze them in support threshold this is this is sort of like a filter both of these analyzer capacity and threshold. Then you have the sketch buffer size, and you have the sketch reset and reuse threshold, which is where it gets provisioned a new sketch based on error. So that's the plugin config. The next section was pattern discovery, selection, and implementation. So, right. so, wait, right, so I used the stat analyzer. I did two sets, one was top 10 patterns of two size two, and that got merged. Then I did 11 patterns of five to eight opcodes that's still under review, but these are basically the pattern matching mode of IL-EVM. So the opcode implementation has to be in parity with the EVM implementation, but you have certain opportunities of optimizing because you have a few patterns together. But the major optimization will come in the IL implementation because we have two implementations to do. One is the pattern matching and the IL implementation. The last was testing, that was just started like a week back, so it's still like very much a work in progress. So this involved testing IL, testing the pattern implementations, also the IL implementations. And the way we were doing this was basically we have two chains, and we have an enhanced chain where we enable the IL-EVM and a normal chain where we don't, and then we compare the state route. But doing that also there are caveats because what if there's an out of gas error? Well, both those chains would be the same. What if there's a, you know, spec is not enabled. Again, you will not, you'll get the state route passing the comparison. Invalid jump destination. So all these situations were there where it would just pass the test, but it's like the implementation is incorrect. So it's quite hard to test this. So anyway, so there was some detection that happened over the weekend. I think five opcodes that I fixed while testing, and testing for the analyzer opcodes and patterns are still work in progress. And well, thanks to all these I mean, my main mentors were Shimon and Ayman. And a big thank you to Lukash, Ben Adams, Damien for being sort of weekly there in the ILVM calls. And Marik and Tomas for actually enabling at the beginning to help me meet all my mentors and setting the meetings up. So, yeah. Thanks. Thank you so much. Lovely. Thank you.