search

jsign / verkle-vs-patricia

Verkle Tree vs Merkle Patricia Tries benchmarks
MIT License
9 stars 2 forks source link

Question about the Pedersen Update Commitment benchmark #6

Open yilongli opened 1 year ago

yilongli commented 1 year ago

I notice that the current benchmark inserts the same newValue at every iteration: https://github.com/jsign/verkle-vs-patricia/blob/511892e64d1c561950d39ed9b60790d572da65cc/pedersencommit_test.go#L94C26-L94C26

Is this why fp.mul doesn't show up in the CPU profile? https://hackmd.io/@jsign/verkle-tries-exploration-about-keccak-vs-pedersen-commitments#Where-is-the-main-cost-in-this-case1

Perhaps a more realistic test should use a different random value at each iteration? Did I miss anything? Thanks

jsign commented 1 year ago

@yilongli, thanks for reaching out :)
(General note: I forgot to mark this repo as archived since it's quite outdated! A lot of things happened since it was created. This repo is using old go-verkle and go-ipa repositories, and most of that doc prob can be already irrelevant).

The reason that fp.Mul isn't dominating there, is that doing the Point -> Fr transformation requires an inverse, and calculating an inverse in gnark-crypto doesn't involve fp.Mul. You'll usually see fp.Mul dominating for VKT, mostly around calculating (or diff-updating) Pedersen Hashes.

Using a different newValue per benchmark iteration isn't a bad idea. It might be a good idea to avoid L1-caching affecting some numbers, but that difference can be somewhat irrelevant in the grand scheme of things (compared to calculating inverses). But you have to make sure of pre-calculating the numbers or not counting generation time.

In any case, what we're doing now in go-verkle is batching inverses, which usually tries to amortize multiple Point -> Fr transformations (which require 1 inverse per operation) to only do 1 operation for all of them. That's done with a known trick called Montgomery trick. Here's a link if you're interested. So, in go-verkle we try to always batch inversions in any place that's possible.

So, in summary, today, most of the inverses are amortized with that trick. That doesn't mean is a negligible amount of work, but definitely not a big problem today.