go-msm

go-msm contains the Golang source code related to the TCHES_3 submission 67. This is an optimized implementation of the Montgomery multiplication alongside the MSM implementation for the BLS12-377 curve.

Organization

The directory bls12-377 contains ".go" files that parametrize the curve and implements the groups G1 arithmetic with different coordinates systems. The file multiexp.go implements the MSM algorithms described in the paper. Also:
- fp/: arithmetic over Fp with x86-64 and arm64 assembly optimization for the specific value of the curve base field.
- fr/: arithmetic over Fr with x86-64 and arm64 assembly optimization for the specific value of curve scalar field.

Target architecture

The code compiles on all target supported by the Go compiler.

Some files differ for the arm64 platform, they have the suffix _arm64.go or _arm64.s:
* bls12-377/fp/element_ops_arm64.go
* bls12-377/fp/element_ops_arm64.s
* bls12-377/fr/element_ops_arm64.go

The corresponding code for other platforms is in pure Go (no assembly);
* bls12-377/fp/element_ops_noasm.go
* bls12-377/fr/element_ops_noasm.go

Build

Download and install Golang https://golang.org/doc/install. This code was tested with the last 2 major releases of Go (1.18 and 1.19).

Test

At the root of the bls12-377 directory, running the command go test -v ./... goes through all the tests. To run a specific test: go test -v -run <regex> with a specific regular expression pointing to the test.

Example

• To only test the MSM: go test -v -run TestMultiExpG1
• To only test twisted Edwards custom coordinates (conversions and arithmetic): go test -v -run TestG1EdwardsExtended
• To test the optimized Montgomery multiplication (in fp/ dir): go test -v -run TestElementMul

Bench

At the root of the bls12-377 directory, running the command go test -run NONE -bench . goes through all the benchmarks in that sub-directory. To bench a specific function: go test -run NONE -bench <regex> with a specific regular expression pointing to the bench.

Example

• benchmark MSM for different sizes: go test -run NONE -bench BenchmarkMultiExpG1
• benchmark the Montgomery multiplication (in fp\ dir): go test -run NONE -bench "BenchmarkElementMul\b"

License

This code is provided under Apache 2.0 license and uses some code from gnark-crypto, a software library publicly available under Apache 2.0 license and of which the same authors of this artifact are core authors.