EPF cohort 4 has come to an end and I want to wrap it up with some thought. First of all big thank you to https://github.com/taxmeifyoucan and https://github.com/JoshDavisLight for organizing and managing the program. Also special thanks to my mentor https://github.com/jsign and https://github.com/lispc who supported my research of verkle trie in-circuit. What I've done during the cohort: There are 2 projects that I’ve worked on during last 4 months:

this is a draft project-proposal, current goal of this project is to get benchmark of in-circuit pedersen hash and commitment used in verkle tries vs keccak hash used in MPT, overcomplicating things leads nowhere VKT - verkle trie MPT - merkle patricia trie Purpose of this document is to describe project proposal for creating a verkle trie data structure in-circuit which means execution of the state changes can be efficiently proven in zk circuit (because of the removal of main bottleneck - keccak-sha3) Motivation In order to make ethereum became more scalable, decentralized and secure new data structure for storage is proposed: Verkle Trie. More on that here:

This is my understanding how it should work for 1 commitment and 1 leaf: update_commitment(commitment, newValue-oldValue, index) So those are 2 32byte and 1 byte values. Total 65bytes. Rust can easily process that. Then rust takes the commitment (which is a banderwagon element) and we do new_commitment = commitment + (newValue-oldValue)*CRS[index] Where newValue and oldValue are Frs.

Updates: Last week i successfully wrapped up Kev's idea: https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/H1xXvMatq of having verkle crypto API, and posted in on separate repo: https://github.com/dragan2234/rust_verkle_crypto_api/ . So i can easy experiment with it, optimize it, and port the primitives to besu native repo: https://github.com/hyperledger/besu-native I still want to fix few things, but I'm happy with the work. I think JNI can definitely be used for besu since rust is more performant then Java for cryptography. The only issue is that there's an overhead of 5-10ms when calling a rust function. Maybe this can be optimized even more. Regarding verkle in-circuit, I was thinking if different field could be used for pedersen so it's even more SNARK/STARK friendly, but my conlcusion is that we should stick with bandersnatch since proof systems are improving so fast that there are even field agnostic proof systems and we are already commited to bandersnatch work. Very interesting work and comments: https://x.com/Charles_Chen533/status/1721359542599180406?s=20

Updates: no big updates for this week, no new PRs. I was mostly reading, writing and researching wrote a specs for updating the commitment for Java<->rust communication for besu: https://hackmd.io/bJbN9kDeSyCrMX2x3-j93g learned about proof generation for Java<->rust. Here's a comment: Finally confirmed what we need to send to crypto API to generate proofs. So it's (C_i, f_i(X), z_i, y_i)

This week I finally finished pedersen hash and commitment specified here: https://hackmd.io/kr5Gka1-S82evw4ex9_OBA And tested against go-verkle: -- Pedersen hashing: https://pastebin.com/0RrL3Ryc The format is: addr: bytes in hex treeIndex: The big int number in decimal notation (base 10). It's a "string" because I can put such a big integer in a JSON. treeKey: the result of the perdersen hash bytes

Updates: finalized correct implementation of pedersen hash in trie-key generation and tested against Ignacio test cases. https://github.com/Quadratic-Labs/VerkleTries_Besu/pull/43 worked on the commitment in the trie, but still have issues with that, commitment in the trie is not returning correct results (tested against Ignacio's test cases) it's a bit unpleasant to hear other onlydust contibutors are considering moving to go-ipa JNI, since i invested some time into rust-verkle repo and making it work with Java, writing docs how to communicate Java<->rust. will probably try to make more progress on the verkle tries in-circuit given the situation with development of this lib

This week I worked on Verkle Tries for besu, and 2 PRs are merged: https://github.com/Quadratic-Labs/VerkleTries_Besu/pull/38 https://github.com/Quadratic-Labs/VerkleTries_Besu/pull/39 So spent most of the week trying to understand serialization differences between pedersen hash used in trie-key generation and pedersen "commitment" used in the trie for commiting to children nodes (up to 256). Ignacio generated some test cases for our implementation so we can compare and see if our implementation is correct: -- Pedersen hashing: https://pastebin.com/0RrL3Ryc The format is:

Besu calls pedersen hash with Address32 and TrieIndex32 both are 32bytes What is passed to JNI is the byte slice where values are in the range [-127,128] and each decimal - we can think of it as [0,256] represent one byte In rust we need to unpack this make the 64 bytes and compute pedersen hash with this What does pedersen hash receives: /// Pedersen hash receives an address and a trie index and returns a hash calculated this way: /// H( constant \|| address_low \|| address_high \|| trie_index_low \|| trie_index_high) /// where constant = 2 + 256*64 /// address_low = first 16 bytes of the address /// address_high = last 16 bytes of the address

Updates: wrote a specs article for besu (trie<->crypto communication for pedersen hash and commitment): https://hackmd.io/kr5Gka1-S82evw4ex9_OBA?view reverted the work on pedersen hash since it was removed: https://github.com/Quadratic-Labs/VerkleTries_Besu/pull/38 researched more on potential changes of hashes in the verkle specs -> goal is to make it even more snark friendly conclusion is that verkle tries in-circuit is a complex topic: in simple words: verkle tries in ethereum separate verification from block execution, and that's kind of the same thing what zkEVMs type 1 are trying to do. So speed of development of verkle tries for ethereum will have an impact on the whole ecosystem, and i'm happy to be involved. Docs are currently all over the place and here's a copy of the message which i sent to Ignacio regarding multiple things i've been researching/thinking about: Hey yes sure, totally makes sense. Will share a few thoughts:

Saving this as a doc for learning purposes copied from https://t.me/real_crypt telegram channel Pedersen hash weaknesses Pedersen hash has been popularized by Zcash team as ZK-friendly hash function suitable for Merkle trees. Its simplest version operates on an elliptic curve with two fixed generators G and H with unknown discrete log relation. Then to hash two integers (a,b) one computes P = aG + bH and takes some compressed version of P (e.g. x-coordinate) as a result. There are several extensions of this construction to longer messages using multiple generators [1] or just by a recursive Merkle-Damgard calling. In contrast to regular hash functions like Keccak there is a formal security proof for collision resistance as any collision implies a discrete logarithm relation between G and H.

Updates for the week: feels like a productive week, pedersen hash is finally done per specs https://github.com/Quadratic-Labs/VerkleTries_Besu/pull/26 . Verkle tries lack a lot of documentation, this is definitely something that need to be worked on. Had a long call with https://github.com/thomas-quadratic regarding rust cryptography layer <-> Java trie logic layer. Although pedersen hash(PH) is the same as pedersen commitment(PC) - we are returning different values to the trie. For PH we return this: https://github.com/crate-crypto/banderwagon/blob/master/src/element.rs#L33 and for PC we return this: https://github.com/crate-crypto/banderwagon/blob/master/src/element.rs#L80 which is different and we can't do that in Java. Why is this designed in such way i don't know now, but will understand Discussed the idea of having poseidon as a hash instead of pedersen hash for trie-key generation the zk verkle telegram group. Will be interesting learning why this hash can't or can be replaced for pedersen hash and sha256 in fiat-shamir for verkle proof. Will learn more about poseidon for next week. My view is that it is becoming

benchmarks: when i say bandersnatch or banderwagon - i mean an MSM with bandersnatch or banderwagon group. There are benchmarks for bandersnatch in https://github.com/zhenfeizhang/bandersnatch: bandersnatch: cs for base var: 5 cs for scalar var: 256 cs for mul : 2869 cs for result var : 27 cs for equality : 20 total constraints : 3177

Updates: this week I mostly focused on verkle EIP and understanding specs of pedersen hash Here's the small write-up regarding generating trie-key: So in order to generate trie-key we need to pass 5 elements to wrapper: 1. a constant: "[2 + 256 * len(inp)]" inp is 31bytes so still not sure what number exactly, but it's a constant 2. lower bits of address32 (address is 32bytes -- address20 is prepended with 12 0bytes) 3. higher bits of address32

Few updates: I think that the easiest path to benchmark difference in proving time between keccak vs pedersen commitment is to use risc0 techonology, since risc0 is the only project where i could reuse existing rust implementaiton of keccak and pedersen commitment and plug in that to their prover and get benchmarks Although I already started creating this with cairo0 (garaga repo), it seems easier to do it with risc0 (rust), still not sure though halo2 library is dependent on other libraries where i asked question whether they will finish the PR which is blocking the idea of making the proof system with bls12-381 in halo2: https://github.com/zkcrypto/group/pull/48#issuecomment-1690742023 We had a call and set up weekly calls for OnlyDust <-> Verkle Implementers group for Verkle Tries in Java, so hopefully we will bootstrap more contributions by communicating more frequently. Tuesday 12th September I'll present the project proposal in the EPF call All of the projects (halo2, risc0, cairo etc.) will need this so I still think initial investigation helps Plan for next week is to try out verkle primitives with risc0, maybe finish the work for garaga repo and do some work regarding pedersen hash for Besu

Some conclustion from the last week: I have finally realized that making verkle tries in-circuit is a good project idea especially after realising Ethereum future is having zk-EVMs as a core execution clients for ethereum. Here's a blog post from Vitalik Buterin: https://vitalik.ca/general/2023/03/31/zkmulticlient.html So having zkEVMs type 1 is important for ethereum, but thinking which project should i contribute, i did a big investigation around and have some conclusions around projects, libraries, potential issues, etc. Choice has narrowed to start working either with halo2-lib or cairo. Why? Because there are so many projects around halo2 lib that i would expect it's easier to configure proof system to use bls12-381. But still halo2 is dependent on some other crypto libraries where I'm getting blocked on making proof system with bls12-381: https://github.com/privacy-scaling-explorations/halo2curves/pull/38 . Personally have more experience with cairo and my conclusions is that STARKs will win in long term over non-post-quantum SNARKs. I was in the US for Stanford blockchain week and met in person people who work around proof systems and understand them more in-depth and asked a lot of questions. Also I've been following on the debates over FRI vs EC cryptographic primitives on x.com so got some conclusions for that too. Will write more about those things too when i learn more. Updates on project proposal are still here: https://hackmd.io/l2XvogKoQOCH748T1rdWZw I wrote up a document for Kakarot zk-EVM on how to make Kakarot zkEVM type 1 with Verkle Tries: https://hackmd.io/CmCJxFBkT7u-bIQ9Y7tKyQ There is this repo which makes having bandersnatch (and then banderwagon and pedersen commitment) in STARKs "easy" to create: https://github.com/keep-starknet-strange/garaga I have been working on this last week, and continuing work this week Also had a call with OnlyDust contributors and Besu team regarding Verkle-Tries for Besu. We are progressing slowly, there are more and more PRs merged, hopefully we will finish this until end of the year and make Besu work with Verkle Tries.

Kakarot is currently proving (almost) all the precompiles and opcodes in the same way as Ethereum is running precompiles and the opcodes. Big issue for kakarot is the proving time of using storage specified by Ethereum as of August 2023. (MPT with keccak hashes of addresses and RLP values). "The verge" - officialy a roadmap for ethereum should happen in 1.5-2 years per https://github.com/gballet/ estimations. This could potentialy improve proving time of type 1 zkevm on starknet. Why? Because "the verge" removes keccak and uses PCS(polynomial commitemnte scheme) for commiting to values in the trie. PCS specified in VKT is Pedersen commitment + IPA. This document is not about VKT, you can find more here: https://verkle.info/ What's interesting is that curve which pedersen commitment uses is based on bandersnatch which has a base field same as the order of bls12-381. Currently "SNARK" zk rollups use bn254, and STARKs don't even use EC's but still i think there is some work to make STARKs work efficient over non-native fields. Also there is "EC STARK" paper, for making STARK even more friendly but nobody has worked on the implementation for the prover. Screenshot from https://vitalik.ca/general/2023/03/31/zkmulticlient.html :

Unfortunatelly having a hard time writing a weekly updates so for this time I'll wrap up 2 weeks to one. Hopefully next week I'll do it by the end of the week and not after 2 weeks. Here are updates from my side: Decided to stick with Verkle Tries in Java lib and still work on project proposal related to verkle tries in-circuit Trying to understand Pedersen commitement and pedersen hash which is actually a same thing - it's simple a multi scalar multiplication of eliptic curve points. So it's a1*A + a2*B + a3*C... where a1,a2,a3 are scalars and A,B,C are eliptic curve points. Pedersen hash is used for computing a verkle trie-key (5 EC points MSM) and pedersen commitment is used for computing a commitemnt to 256 children in a trie (256 E. I have proposed for a call with OnlyDust contributors and Karim from Besu team where we brainstormed and talked about what is needed for Verkle Tries library. Other fellows participated, Naman and Agnish. Also few other people from OnlyDust community: Matteo, Thomas and I think Dinesh was also on the call too, and maybe i forgot somebody. Made a progress on project proposal. It's still not ready but here's a draft: https://hackmd.io/l2XvogKoQOCH748T1rdWZw?view Been chatting with Kev and Ignacio, they are helping me regarding what's the best way to execute this project.

These 2 weeks were in the middle of the summer so i was on vacation all the time but managed to do some work too. I reached out to verkle trie discord channel and PSE discord and shared my ideas about project that I'm interested working on and got some feedback. Here's the doc: https://hackmd.io/l2XvogKoQOCH748T1rdWZw Also had a call with Verkle implementers for Standalone Java lib. I helped onboarding 2 new devs for that project. My plan is to work on these 2 projects during my fellowship:

This week I have mostly read about the verkle tries, pedersen commitment and IPA. I'm trying to understand how these crypto primitives work. Also, I have been trying to onboard few people from the fellowship into the Verkle Tries in Java, so hopefully we will see more progress over there in coming weeks/months. Chatted with people, we will probably organize a meeting next week(s). One thing I tried to do is to get into Axioms open source program and do the Verkle Tries crypto primitives as a member of that program where I can learn from experts on cryptography and circuit implemnetation. Task was to create a program in circom so here's the implmentation: https://gist.github.com/dragan2234/8e229506736bf5077fdd7af79a7e17f8 Not easy, spent 2-3 days trying to understand and do something, and had some output in the end (not correct still). Also asked some questions regarding verkle-tries implementation in-circuit in verkle-trie-migration eth R&D discord channel and got the answer from one person working on the rollup. So maybe it make sense to do the verkle primitives in halo2 and get some benchmarks how it compares to MPT and how long it takes to prove it.