protolambda / go-kzg

FFT, data-recovery and KZG commitments, a.k.a. Kate commitments, in Go - *super experimental*
MIT License
90 stars 26 forks source link

Use mont reduced operations #1

Closed kilic closed 3 years ago

kilic commented 3 years ago

In kilic/bls12-381 lib Fr Mul operation is not the fastest way to compute multiplication. Instead we can use Montgomerry reduced operations.

Added under the kilic_bignum_red tag.


# go test -run none -bench BenchmarkFFTSettings_FFT -v

BenchmarkFFTSettings_FFT/scale_4-8                108186             10992 ns/op
BenchmarkFFTSettings_FFT/scale_5-8                 46240             24960 ns/op
BenchmarkFFTSettings_FFT/scale_6-8                 20463             55935 ns/op

# go test -run none -bench BenchmarkFFTSettings_FFT -v -tags bignum_kilic

BenchmarkFFTSettings_FFT/scale_4-8                233720              4910 ns/op
BenchmarkFFTSettings_FFT/scale_5-8                111338             10745 ns/op
BenchmarkFFTSettings_FFT/scale_6-8                 51358             23476 ns/op

# go test -run none -bench BenchmarkFFTSettings_FFT -v -tags bignum_kilic_red

BenchmarkFFTSettings_FFT/scale_4-8                432556              2792 ns/op
BenchmarkFFTSettings_FFT/scale_5-8                191559              6056 ns/op
BenchmarkFFTSettings_FFT/scale_6-8                 90892             13125 ns/op
kilic commented 3 years ago

Hey! Thanks for your interest, your BLS library has been great. It may even become the default with all the improvements and non-CGO assembly usage. And where did you learn about this experimental Kate implementation?

Thanks :) I've been searching usage of the library here github.

while the real change could probably be more isolated

Right. Kept old kilic_bignum allow you to compare results easily.

Also planning to look at G1 add usage tomorrow. If second operand b in func g1Add(ret, b, a) is affine point then it uses mixed addition which is slightly cheaper.

protolambda commented 3 years ago

Finally integrated this via #12, thank you :)