Spike: research and recommend altbn128 host function support solution

[stephenpdeos]

We need to evaluate the best path forward to support altbn128 host functions via either Rust or Go.

Benchmarking for both solutions should be part of this investigation.

[stephenpdeos]

Decisions made around this solution and the related follow-on work to implement altbn128 will close/replace #362

[linh2931]

The Go library is https://github.com/cloudflare/bn256 and Rust library is https://github.com/paritytech/bn.

[linh2931]

Here are benchmarking results.

OS: Ubuntu 20.04
Hardware: 3.50GHz, 16 cores, 64 GM main memory
One pair of G1 and G2 points

Summary:

• fc::alt_bn128_pair (G1/G2 instantiation + Miller-loop + Final exponentiation): 4 ms
• Go Pair (Miller-loop + Final exponentiation): 1.4 ms
• Rust pairing (Miller-loop + Final exponentiation): 2.2 ms

Details:

-- FC --
fc::alt_bn128_pair                      4,004,947      ns/op
fc::decode_g1_element                   750            ns/op
fc::decode_g2_element                   1,000,090      ns/op
libff::alt_bn128_precompute_G1          1,310          ns/op
libff::alt_bn128_precompute_G2          364,867        ns/op
libff::alt_bn128_miller_loop            940,728        ns/op
libff::alt_bn128_final_exponentiation   1,645,470      ns/op

-- Go --
BenchmarkG1-16                 8221     146413 ns/op
BenchmarkG2-16                 2756     462442 ns/op
BenchmarkPairing-16             842    1453806 ns/op
BenchmarkMillerLoop-16         2209     608710 ns/op
BenchmarkFinalize-16           1365     907547 ns/op

-- Rust --
test g2_creation                ... bench:     857,864 ns/iter (+/- 16,124)
test g1_creation                ... bench:     202,393 ns/iter (+/- 2,129)
test miller_loop                ... bench:     912,689 ns/iter (+/- 12,578)
test final_exponentiation       ... bench:   1,302,541 ns/iter (+/- 7,568)
test perform_pairing            ... bench:   2,272,783 ns/iter (+/- 11,790)

[linh2931]

The following benchmarking all used the same 10 pairs of points as input and run through the same initialization and pairing. Go implementation was the winner.

FC alt_bn_128

./benchmark -m alt_bn_128
function                      runs               avg              min              max

alt_bn_128:
alt_bn128_add                 1,000         5,927 ns         3,721 ns       126,858 ns
alt_bn128_mul                 1,000       238,759 ns       235,555 ns       259,195 ns
alt_bn128_pair (1 pair)       1,000     6,407,273 ns     6,359,831 ns     7,404,953 ns
alt_bn128_pair (10 pairs)     1,000    25,382,388 ns    25,245,196 ns    33,519,907 ns

Go

goos: linux
goarch: amd64
pkg: github.com/ethereum/go-ethereum/crypto/bn256/cloudflare
cpu: 11th Gen Intel(R) Core(TM) i9-11900K @ 3.50GHz
BenchmarkG1-16              	   12268	     95286 ns/op
BenchmarkG2-16              	    2616	    447901 ns/op
BenchmarkPairing1Pair-16             598	   2071564 ns/op
BenchmarkPairing10Pairs-16    	     100	  11331991 ns/op
PASS
ok  	github.com/ethereum/go-ethereum/crypto/bn256/cloudflare	6.018s

Pairing via contract

I run push_action to a pairing smart contract (pairing the same 10 pairs) and noted the elapsed from action trace for 10 times. The time ranged from 25,361,000 ns to 27,734,000. The numbers matched those from native fc::bn_128_pair function.