Benchmarking & Optimizations - Banderwagon Implementation

So this week was all about testing & discussing about possible optimizations for the Banderwagon implementation. I have also been working on the integration of the of Constantine library into nim-eth-verkle. Now this led to a long discussion with the Nimbus team, and we have decided to go with the following approach:

• Start with a PoC as Constantine as a git submodule.
• Then later we will collaborate with the Codex team to make a nimble install for the Constantine repository.

Also made another PR for the batch operations for MapToScalarField, which I missed initially and was a dependency for @agnish

Now let’s get into the benchmarks. It turns out that our implementation is faster in few cases, while being a bit slower in other cases.

Benchmarks ( in Apple Silicon M1 Chip )

Constantine Bechnmarks :-

go-ipa Benchmarks :-

Conclusions ( from tests in Apple Silicon M1 Chip )

Benchmark Operation	Constantine Impl	go-ipa Impl	Remarks
Equality Check	58 ns/op	48 ns/op	slightly slower ✅
Subgroup Check	2932 ns/op	8819 ns/op	highly faster 🚀
Serialization	1978 ns/op	1843 ns/op	slightly slower ✅
Deserialization	32530 ns/op	11175 ns/op	highly slower ❌
BatchSerialization	197112 ns/op	184184 ns/op	slightly slower ✅

What’s the problem with Deserialization?

After searching about this a lot & studying my and the go-ipa implementation & I realized that the problem lies in performing the square root of a field element. In constantine I was using the Tonelli-Shanks Algorithm which is becoming a bottleneck. Now this algorithm have been optimized in the go-ipa, which doesn not exist in the constatine library.

After discussing with @mratsim & @ignacio I found out this can be optimized using the dlog precompute table, over the Tonelli-Shanks Algorithm. To read more about this, I highly recommend reading through the blog post by @ignacio Tonelli-Shanks with PreComputed dlog tables

Upcoming

• Meeting with the Codex team for discussion regarding future of constantine, for nimp2p lib
• Working on the integration of constantine into nim-eth-verkle, meeting with danille & agnish
• Assist Agnish on finishing the ipa implementation