EPF Update 12 and 13 - Debugging my soul away :D

Nimbus Team

This week was mostly spent in writing tests, the tests are actually divided into the following parts:

• Helper math functions (in progress)
• IPA proof creation and verification tests (in progress)
• Multiproof creation and checking tests
• Polynomial interpolation tests, with Barycentric Precompute optimisations and without them as well. (in progress)
• Transcript generation tests and tests for generating a random scalar.

Apart from I found a small security vulnerability in Go-IPA. Spoke to Ignacio about it and he has already raised an issue along with a PR. I think it's closed by now.

But what was the issue about?

Firstly, here is the PR for the issue.

Some context

In go-ipa we have a couple of functions, and there are few specs to define them. As a collective decision, it was decided that every polynomial (vector here) shall have 256 elements, we call elements (or rather points for the polynomial) as DOMAIN.

computeBarycentricWeightsForElement( ) only computes A(x) and 1/A'(x) which are terms needed to compute the Barycentric Weights for points in the DOMAIN which is 256 elements. Here, X is any point in the DOMAIN and is not at all dependent on the other variable that you get to see out of DOMAIN, namely z. This function helps us to precalculate all the 256 values and use it as a cache for later usage.

computeBarycentricCoefficients(z) is a different function. It's used in runtime to evaluate the polynomial for a point z outside DOMAIN and is used to calculate the vector b_i, which is in turn needed for IPA Proof creation. This function also needs computeBarycentricWeightsForElement( ) to optimise and save time.

Hence, in totality, computeBarycentricCoefficients(z) needs computeBarycentricWeightsForElement( )

For understanding in DOMAIN and out of DOMAIN (sorry for writing this in caps, I've written this as a constant in too many places by now :") ) Any point that uses the Barycentric Formula uses points outside DOMAIN, because if you use points inside DOMAIN you may get a division by 0 error. Naturally, if you're in DOMAIN, then the evaluation of the polynomial is literally the i-th element of the polynomial.

The issue

In real life, the multiproof layer will always pull a random challenge (based on Fiat Shamir) from the transcript such probability

$$P(thepointbeinginDOMAIN)=1-256/FieldSize$$

Hence the highest probability that a random elem generated will be outside DOMAIN, will be around

$1.7686873\times {10}^{-}74$. Which is almost 0. However, not exactly.

Go-IPA didn't initially have a way to evaluate a polynomial in a case where the value was in the DOMAIN, beacause of it's very less chances. However, as this spec is being is being followed by other teams like Nim, they use a much finer seed for random term generator, where there can be a chance of generating elements for which in DOMAIN evaluation maybe needed.

Remaining TODOs

Fixes #275

• Transcript generation using Fiat Shamir style
• Barycentric form using precompute optimisation over domain
• Common Reference String generation
• Common util funs for ipa
• IPA functions for prover
• IPA functions for verifier
• Functions for creating multiproofs
• Functions for checking multiproofs
• Random element generator for Pedersen
• Assert for no duplicate elements for random elem gen
• Scalar Serialise for Banderwagon
• Scalar Deserialise for Banderwagon
• IPA proof serialisation / deserialization into a single byte array [In Progress]
• Individual tests [In progress]
• Integrated tests [In progress]
• Functions for Pedersen Commitments
• Adding more comments for explanation/ more resource links
• Refactoring to generics

Apart from that, I also have plans to sit with Daniel and Advaita to have a further discussion on converting just the Verkle dependencies into a separate nimble package (as suggested by Mamy and Zahary), and for now adding Constantine to nim-eth-verkle (Nimbus verkle trie) as a submodule and commencing the integration.

For Besu Team

I finally started working on the Java/Rust wrapper for IPA and Multiproofs and these were my overall tasks and realisations:

Fixes #42
Features for verkle state root proofs and verification:

• wrapper functions for basic state root proofs
• wrapper functions for replicating the same trie in rust and inserting key values
• out of these operations
• inserting sparse key-values
• standard key-val insertion
• inserting two different leaves under the same stem
• inserting two different leaves under the 2 different stems
• stateless updation of root
• stateless updation of root using subtree

The idea of taking this approach is as follows:

• Having different functions for different operational cases in the verkle trie
• Preserving the Rust types, as according to rust-verkle almost every type has a ser/de
• Dealing with only byte arrays in Java
• Reconstructing the verkle trie in rust if needed, as the not preserving the types and manually trying to tweak the byte arrays before deserialize may cause data loss while porting over from the Java side.

Help Needed:

• Rust uses something called MemoryDB, we need to study it's properties, as for most of the trie operations, values directly from the DB, either we mimic the properties of this DB.
• Or, we figure out a way to enter values from Bonsai.

Note:
WIP pr, contains unused imports, and maybe some logical bugs for edge cases, feel free to discuss.

Further Realisations

There were several functions in Multiproofs as well as IPA mods in the the rust-verkle repo, where Verkle's memory DB instance is passed as a parameter, which is why there can be 2 options from here on:

• Either we make a Java/Rust wrapper where the MemoryDB is exaclty mimiced/mocked up
• Or, as discussed with Josh Rudolf and Karim Taam use JNI to expose APIs of go-ipa, and add that interface as a PR in Besu Native, just the way Besu uses Gnark.