Abstract Precompile contracts are subrutines that are executed on the client side for high efficiency. EIP-5988 proposes the inclusion of the Poseidon hash function to the current set of precompile contracts of the EVM. Poseidon is part of a new family of cryptographic hash functions known as arithmetization-friendly hash functions. This type of hash function allows the generation of simpler arithmetizations of programs, and hence, shorter proofs in SNARKs, STARKs, etc. Therefore, zk-rollups can benefit greatly by having access to cheaper and faster executions of Poseidon. In order to make an informed decision on whether to include Poseidon as a precompile contract, this project proposed to analize the computational costs of executing Poseidon using Rust, which is the programming language currently use in reth. In this short article, we summarize the results obtained, the progress achieved with respect to the original project proposal, and future work. Finally, we present our conclusions of the project. Current Status The aproved project proposal can be accessed from this link. For this project I received valuable feedback from mentors Ignacio and Kev.

This is the first week since the start of the program that I slowed down a bit. I spent the week rereading the yellow paper to make a proposal of the gas cost of a potential Poseidon precompile. Some precompiles have a fixed gas cost, while others have a dependency on the input size. Te table below summarizes the gas costs for each precompile contract. See the the yellow paper for details. Precompile Gas cost ECREC 3000

During this week I completed all the benchmarks I was planning to do. I found some errors in the previous benchmark I coded using criterion and I spent time this week correcting those errors and running the new benchmarks. All benchmark results can be accessed through the github repository https://github.com/mdvillagra/poseidon-benchmarks. The main comparisons are shown in the plot below. In this graphic, we have tested inputs of sizes 256, 512, 768 and 1024 bits. Risc0 have two implementations, one with the BLS12-381 scalar field of 255 bits and another with the Babybear field of 31 bits. Right now, the repository is in a state where it is very easy to add any other Poseidon instantiation as a submodule and then prepare the benchmark for it and just run it. All stats are generated using criterion. Independent of EIP-5988, this repository is useful by itself for further research into the Poseidon hash function.

This week I got prelimanry results on the benchmarks of the Poseidon hash function. These results can be accessed here: https://mdvillagra.github.io/poseidon-benchmarks/Poseidon-Xeon/report/index.html https://mdvillagra.github.io/poseidon-benchmarks/Poseidon-cryptoexperts-vs-risc0/report/index.html These benchmarks can be reproduced by forking and running cargo bench on this repository. The following steps for Week 13 are the following. The comparisons executed in the preliminary results shown above are unfair. For example, Poseidon with the babybear field only requires 32 bits for each field element while for the scalar field of BLS12-381 each element requires 256 bits. I will be preparing new figures that account for that disparity.

During this week I spend most of my time trying to make the Cryptoexperts Poseidon permutation work. Let us recall that the Cryptoexperts instantiation of Poseidon is written in C language. Hence, this required to make a C interface in Rust. In this update I will present a guideline on how to compile the Cryptoexperts Poseidon permutation and generate a static library in order to use it from Rust. This writing will also serve as a future reference on how to use the C implementation in the Cryptoexperts repository. Fork or clone the repository. In our poseidon-benchmark repository we added it as a submodule. In the sources directory run the command make only_c. This action will create 5 files: f251_int128.o, f251.o, poseidon_rc.o, poseidon.o and lib_pos.so. At this stage you can choose to use the lib_pos.so library but, in Linux, it will require you to set the environmental variable LD_LIBRARY_PATH to a directory containing lib_pos.so or to copy the file to a directory in LD_LIBRARY_PATH. It is easier, however, to generate an static library file that can be used from anywhere in the directory structure. To generate a static library file the following command suffices: ar rcs lib_pos.a poseidon.o poseidon_rc.o f251.o f251_int128.o. It is important to add the prefix lib to the .a file so that the linker recognizes it as a library file. After generating the static library file, we can start creating the Rust interface. Create a build script build.rs in the root of the repository. In the script, we should tell cargo where to find the library file and its name. It should be something like this: //build.rs

This was another week of intense coding in my repository https://github.com/mdvillagra/poseidon-benchmarks. I am not listing all the commits because there were a lot of them. I managed to integrate several important instantions of Poseidon into my repository which includes: Lambdaworks, Neptune, Dusk-network, and Risc0. Right now I am almost ready to start executing the benchmarks. All these implementations are running fine and I already was able to run some preliminary benchmarks with them.

During Week 9 I finished with the sponge function for the Poseidon permutation. Te following commits were made for this: https://github.com/mdvillagra/poseidon-rust/commit/42c52fdadb108a9947e8824b8fda9ab8e6e02964 https://github.com/mdvillagra/poseidon-rust/commit/7a47d58594666424b495ebc268f1b393a345f591 https://github.com/mdvillagra/poseidon-rust/commit/b52f2de526f12f7cd749ee489a026dbdd5fa15b3 https://github.com/mdvillagra/poseidon-rust/commit/996c33ef35f7e739714bbae6c8e106da5e99d944 https://github.com/mdvillagra/poseidon-rust/commit/4a4b66c7affc7056d441568c3b4135c66d922773 Currently, I am working on implementing most of the field instantiations from the arkworks library. After that, my plan is to start with preparing the code the benchmarks. This week I expect to finish the different instantiations of Poseidon, and start with preparing the rust benches.

This week I continued implementing a Rust version of Poseidon. The entire permutation was completed in three commits shown below: Added sbox function that computes the sbox stage. commit link. Added linear_layer function. commit link Added poseidon permutation. commit link This implementation is based on the arkworks library and it uses the BLS12-381 curve. The parameters used for this instantiation are $\alpha=5$, $N = 1275$ round constants,

During Week 7 I continued implementing several poseidon hash libraries in Rust. Until now I have kept my repositories private, but I am now making them public. I am working on two repositories listed below: Poseidon benchmarks (https://github.com/mdvillagra/poseidon-benchmarks), Poseidon Rust implementation (https://github.com/mdvillagra/poseidon-rust). The repository for Poseidon benchmarks is for gathering several Poseidon implementations and run benchmarks on them. Right know I have three working implementations working together with bench functions: (1) https://github.com/arnaucube/poseidon-ark, (2) https://github.com/dusk-network/Poseidon252, (3) https://github.com/CryptoExperts/poseidon. The last implementation from CrytoExperts is a C implementation of the Poseidon permutation. My plan to run this C code is to make a sponge function in Rust and call the C subrutine within the Rust program. A Rust Poseidon implementation is not new in the sense that there are other implementations in Rust. However, the idea behind my own implementation is to make it fully parameterizable, that is, a user would be able to select a field size, number of rounds, width of the sponge, etc. This will also be used in the benchmarks that are planned later. Is also important to note that this Rust implementation is based on arkworks. By next week, I expect to finish with my Rust implementation of Poseidon and start designing the benchmarks that I will need to make.

During Week 6 of the program I spent my time doing a lot coding with Rust. I am still learning the language and I am not going as fast as I would like. However, I still managed to learn how to use cargo bench and apply it to two Rust repositories of Poseidon: https://github.com/arnaucube/poseidon-ark and https://github.com/dusk-network/Poseidon252. Right now, I have both implementations fully working on my own private repository, and I am capable of running different benchmarks with different statistics. I also started to survey the different implementations of Poseidon that can be found on the Internet. I am planning to prepare another HackdMD post with a list of all these implemantations and check if they are covered or not by EIP-5988. For Week 7, I expect to do the following steps: Add the Rust code of precompiles SHA2-256 and RIPEMD-160. The reth client of Paradigm uses the Rust crates https://crates.io/crates/sha2 and https://crates.io/crates/ripemd. Continue collecting different implementations of Poseidon and Poseidon2 and start preparing a HackMD article summarizing their parameters.

Motivation Ethereum precompile contracts are constructed into the EVM and executed on the client side for high efficiency. Usually a precompile status is reserved for subrutines that are considered of high importance and usage. Currently there are exactly nine precompiled contracts: ecRecover (ECDSA public key recovery function), SHA2-256 (hash function), RIPEMD-160 (hash function), identity (identity function), modexp (modular exponentiation), ecAdd (point addition on the elliptic curve alt_bn128), ecMul (scalar multiplication on the elliptic curve alt_bn128),

During the 5th week of the program I did mainly two things: (1) received advice from mentors Ignacio and Kev, and (1) improved my Rust skills. Essentially, the project looks very good and intriguing. The idea of supporting EIP-5988 with complementary benchmarks can help to obtain a better understanding on the computational costs involved in running Poseidon as a precompile. Even though I am aware that including Poseidon as a precompile will take a lot of convincing on core developers, there is still work to be done regarding the hash function itself about its usage. From Week 6 onward I will start coding everyday in order to be able to finish on time what I have planned for the EPF. One of the most relevant advice I received from the mentors is to reuse the Poseidon implementations that are freely available, from example, from here. Below I present some key issues that came out from the conversations I had with mentors. The list below are some questions that I would like to research during the execution of the project and I expect to have answer by the end of the program. Number of existing implementations of Poseidon that EIP-5988 covers. Number of Poseidon hash calls needed for SNARK verification. Would it be different based on the proving system?

During week 4 I have finished with a draft of my project proposal and some slides to make a presentation. I managed to make contact with a mentor and the authors of EIP-5988. I am still waiting for some feedback of my project from the mentor. At the same time I got some interesting information on the work being done by the authors of EIP-5988. While waiting for a feedback on my project, I invested my time learning some libraries that will be important for the project, for example, FLINT and blstlib. Both libraries have code that can be used to implement finite field arithmetic with very efficient algorithms. Although blstlib is only for the BLS12-381 curve, I still feal that learning to use a well-known library for elliptic curves can be relevant. I also spent time making a deep study of the PLONK paper and repositories implementing PLONK, like this one in Python. In the future, I feel that it may be interesting to write a tutorial for implementing PLONK. Even though the paper is well-written, the presentation of the results can be challenging to developers with no background in ring theory. I will leave this for a future personal project. The main reason of using Poseidon as a hash function is to obtain smaller arithmetic circuits. This inmediately leads to less constraints in R1CS, which is an intermediate representation of arithmetic circuits in current zero-knowledge proof systems. There is also a more recent version called Poseidon2, that was published less than two months ago in the Cryptology ePrint Archive. This new version promises faster execution and less constraints for PLONK circuits. I still need to read the details of Poseidon2 and see if it will be possible to incorporate it into the project.

This week was a realization week. I went deeper into how precompiles are made and how they are executed. It turns out that precompiled smart contracts are not executed the same way as normal contracts. In Ref. 6 below, there is a really nice explanation how precompiles work. When you hear or read "smart contract" you can imagine some solidity code that is compiled to bytecode that the EVM must execute. Actually, what the EVM does is to first verify if the address of the contract corresponds to a precompiled contract or a regular contract. If the address corresponds to a regular smart contract, then the interpreter of the EVM is called, as usual. But, if the address belongs to a precompiled smart contract, then the corresponding code, which is found in the client, is executed on the client. Therefore, all precompiled contracts are executed on the client side and no EVM is required. Furthermore, in the Ethereum Yellow Paper [3] all gas costs are fixed for each precompiled. Therefore, my initial idea of doing a gas cost analysis of poseidon as a precompile makes no sense. Even though what I explained above breaks my original idea for a project, there are still many ways to contribute to EIP-5988. For example, the computational costs of poseidon as a precompile are relatively unknown compared against other existing hash functions that are also precompiled contracts. There are three precompiled hash functions: 1) SHA256, 2) RIPEMD160, and 3) BLAKE2b. Also, the gas cost of poseidon as a regular smart contract is unknown, as far as I know. In order to gain some insight into the process of creating a new precompiled contract, I read the conversations around EIP-152: Add BLAKE2 compression function F precompile. Indeed, the ideas of the previous paragraph come from these discussions about BLAKE2b; see here and here. I already have a pretty good idea of what I want to do as a project. Basically:

Introduction Block ciphers have been widely used in cryptography for many years. The idea is to separate a plaintext into fixed-sized blocks and perform transformations on these blocks in order to obtain a ciphertext. Block ciphers are also used in the construction of compression functions for the design of hash functions. More recently, a new design paradigm for hash functions has been discovered a so-called sponge construction [2]. The cryptographic funtion keccak, which is widely used in the Ethereum protocol, was the first implementation of sponge constructions [3]. The goal of this article is to introduce a general algorithm for sponge constructions without presenting any practical use. The main focus will be in giving a presentation of the algorithm for any fixed-length function with some accompanying code snippets. The idea behind this approach is to present some concrete realizations of all parts of the sponge construction. Security will not be discussed here. For more details the reader is encouraged to refer to the original references at the end of this article. The code snippets that will appear will be written in Python for the sake of claritiy. The Sponge Construction The figure below (taken from https://keccak.team/sponge_duplex.html) presents a general view of the sponge construction.

In this week I spent time doing a deeper reading of the Poseidon paper. I am currently working on an article that (hopefully) presents a simple explanation with code of the sponge construction and the Hades strategy used in Poseidon. First I will present a general algorithm of the sponge construction, and later, before the end of the week I plan to finish with an explanation of the Hades strategy. In the future I also want to make a discussion on the security and cryptanalisys of Poseidon; however, this is a more involved task and it will depend if it is really necessary to my project. I already have the following questions that I will try to have an answer by Week 3. How do I make a precompile for the EVM? There are currently nine precompiled contracts, namely, ecrecover, sha256, sha3FIPS25, ripemd-160, Bn128Add, Bn128Mul, Bn128Pairing, the identity function, and modular exponentiation; see here, here and here for more details. Is C a good option to write a precompile? There is a Go implementation in this link. I will leave this question for later. I still do not know how to make a gas cost analysis. My reading list for this week is to start and finish the readings from here and here. After reading these I hope to have a clearer picture on how to write my project proposal. Some questions I have right now, and for which I expect to have an answer by the end of the week, are: 1) the literature I found about gas cost analysis is related to "normal" smart contracts, but, do these tecniques apply the same way for precompiled contracts?; 2) what is the level of abstraction these analysis tecniques use? do they look at the opcodes or are they based on the higher level languages?; 3) will I managed to do a theoretical and experimental analysis on time by Devconn?. One of the goals I have with the EPF is to do more applied research and build things. I have been working for some years already on computational complexity, and I always touched cryptography one way or another. Advances in complexity goes hand in hand with advances in cryptographic research. I always liked my ivory tower, but now I feel that I want to go down and touch the grass. During my studies this week I found something that I really enjoyed playing with, the libraries sodium, blst, and secp256k1. I found that most if not all of blockchain networks are based on these three libraries. These are time-tested libraries for cryptographic primitives. One of the arguments against using Poseidon as a precompile is that it hasn't passed the test of time yet. This question, however, cannot be answered before Devconn this year.

Officially the EPF 4th cohort is underway and there are many interesting exchanges in the discord server. My original interest for a project was to do something related to Verkle trie migration. However, after I got more involved in conversations and reading comments in the channels inside the R&D discord server, there is just so much to do! I feel like everyone participating in the program is in a big toystore and you like all the toys but your budget is limited and you can only afford to buy one. Discipline is key. I am narrowing my potential projects to two options: (1) SSZ and (2) Poseidon hash (EIP-5988). Simple Serialize, or SSZ, is a serialization technique alternative to the classical RLP serialization. SSZ objects can also be stored in a Merkle tree. There are already many implementations of SSZ. One idea is to make an entire new implementation of SSZ in C or Haskell. Currently there are no implementations in those languages and would be nice to add those to the list. Another potencial project is to look into the issues in one of the current implementations and see what can be done. Working on SSZ is very interesting and it seems that it can add some immediate value to the protocol. My attention, however, is completely drawn to the Poseidon hash. I won't go into technical details right now (I am planning to do so in future articles), but it suffices to say that Poseidon hash is a relatively new hash technique based on a sponge construction, where the inner permutation in the sponge is constructed following a Hades strategy. The idea behind EIP-5988 is to add a precompile of Poseidon to the protocol in order to accelerate potential uses of ZK-Rollups by L2 networks. Poseidon was designed to be efficient for ZK proof systems. Right now I would say that I am inclining towards working on an implementation of the Poseidon hash, of which there are a few implementations already. EIP-5988 is in draft stage and it is missing some information in order to justify its adoption or its rejection. Besides an implementation, a gas cost analysis of Poseidon as a precompile can add value in order to make an informed decision. I have no idea on how to do a gas cost analysis, but luckily, there are already some works on the subject; see for example here, here and here. There is a really interesting discussion (here and here) on the costs of running Poseidon as a precompile.

Here I summarize my activities during this week. In order to get started in the program, I have planned the following reading list for week 0. Reading list for Week 0 Ethereum white paper. Ethereum yellow paper. Theory of KCG commitments. Patricia Tries (link 1 and link 2). The Ethereum white paper is the original presentation of the Ethereum protocol. Eventhough Ethereum has evolved since its conception, the original white paper is important for historical reasons. It is also a good simplified reference of the entire protocol.