EPF Update 12 and 13

# 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: - [X] Helper math functions (in progress) - [ ] IPA proof creation and verification tests (in progress) - [ ] Multiproof creation and checking tests - [X] Polynomial interpolation tests, with Barycentric Precompute optimisations and without them as well. (in progress) - [X] Transcript generation tests and tests for generating a random scalar. Apart from I found a small security vulnerability in [Go-IPA](https://github.com/crate-crypto/go-ipa/tree/master). 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](https://github.com/crate-crypto/go-ipa/pull/64). #### 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(the \ point \ being \ in \ DOMAIN) = 1-256/Field \ Size$$ 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 - [X] Transcript generation using Fiat Shamir style - [X] Barycentric form using precompute optimisation over domain - [X] Common Reference String generation - [X] Common util funs for ipa - [X] IPA functions for prover - [X] IPA functions for verifier - [X] Functions for creating multiproofs - [X] Functions for checking multiproofs - [X] Random element generator for Pedersen - [X] Assert for no duplicate elements for random elem gen - [X] Scalar Serialise for Banderwagon - [X] Scalar Deserialise for Banderwagon - [ ] IPA proof serialisation / deserialization into a single byte array [In Progress] - [ ] Individual tests [In progress] - [ ] Integrated tests [In progress] - [X] Functions for Pedersen Commitments - [X] Adding more comments for explanation/ more resource links - [X] 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](https://github.com/Quadratic-Labs/VerkleTries_Besu/issues/42) Features for verkle state root proofs and verification: - [X] wrapper functions for basic state root proofs - [X] wrapper functions for replicating the same trie in rust and inserting key values - out of these operations - [X] inserting sparse key-values - [X] standard key-val insertion - [ ] inserting two different leaves under the same stem - [ ] inserting two different leaves under the 2 different stems - [X] 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](https://github.com/crate-crypto/rust-verkle/tree/master) 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](https://github.com/hyperledger/besu-native), just the way Besu uses Gnark.