point compression design decision

[zack-bitcoin]

Looking at the pedersen version of the verkle tree. The prime field on top of BLS12-381, it is really slow to do square root in this field. It needs tonelli shanks, but there are 32 factors of 2 in (prime-1), so it is very slow. So, decompressing points from 32 byte format is slow. 0.00035 seconds per point on my CPU, which is like 10x longer than how long proof verification should take, according to Dankrad's calculator. Spending 90% of the proof verification CPU time on just decompressing points seems inefficient.

Are we going to make proofs with 64 bytes per point, or 32 bytes per point?

Is there any plan for a pedersen verkle tree that uses a different elliptic curve, so we can have faster point decompression?

[jsign]

I didn't realize this issue existed, but we've improved this situation with an optimization in go-ipa: https://github.com/crate-crypto/go-ipa/pull/38

Figuring out how that works by reading code is quite hard, so leaving an article I wrote about it as a reference for other readers—also, a summary of performance improvements here.

I'm planning to jump into proof generation and verification in the medium term, since we're focusing on optimizing the Ethereum state conversion as much as possible. When I jump into proofs generation and verification, I can see how this optimized square root impacts overall performance.

Let's leave this issue open until we have more information if the sqrt optimization is enough, so just give an update here.