Performance comparison of secp256 between go-ethereum and btcd

[yutianwu]

REF: cosmos/cosmos-sdk#2640 (comment)

hi, I compared performance of secp256 verifying signatures between go-ethereum and btcd. I found that go-ethereum improves about 30% over btcd.

I used my laptop(MacBook Pro (15-inch, 2018), 2.2 GHz Intel Core i7) to test. Below are the results.

go ethereum:

func BenchmarkVerifySignature(b *testing.B) {
	pubKey, secKey := generateKeyPair()
	msg := randentropy.GetEntropyCSPRNG(32)
	sig, _ := Sign(msg, secKey)

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		VerifySignature(pubKey, msg, sig[:64])
	}
}

result:

goos: darwin
goarch: amd64
pkg: github.com/ethereum/go-ethereum/crypto/secp256k1
BenchmarkVerifySignature-12    	   10000	    150459 ns/op
PASS

btcd:

func BenchmarkSignature_Verify(b *testing.B) {
	privKey, _ := NewPrivateKey(S256())
	pubKey := privKey.PubKey()
	msg := randentropy.GetEntropyCSPRNG(32)
	sig, _ := privKey.Sign(msg)

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		sig.Verify(msg, pubKey)
	}
}

result:

goos: darwin
goarch: amd64
pkg: github.com/tendermint/btcd/btcec
BenchmarkSignature_Verify-12    	    5000	    232010 ns/op
PASS

the performance is very important because if there are many txs, it will cost a lot of time to verify signatures in AnteHandler. So can we move to the version of ethereum?

[ValarDragon]

Thanks for pointing this out!

To first note, go-ethereum is getting its speed from using C code for this task. I believe the same koblitz endomorphisms as in the C / asm code are used in btcd for verification. I have not verified this though. We should check on security audits on the Ethereum's secp codebase (and not just assume its secure b/c etheruem uses it), and check its constant time guarantees. If this is the case, I am fine with switching, though we probably can't focus on the change until postlaunch.

As a side note, I think we may end up switching from C to golang with asm or pure Rust.
I suspect that secure ECDSA batch verification algorithms exist using random linear combinations of the relevant equations, along with using pippenger / bos-corter multi-scalar exponentiation algorthm. (In the same style as is done in ed25519, see dalek crypto's code for this). I also am aware of 2 asia crypt papers providing batch ecdsa verification speed-ups. Its worth exploring the speedup's to be had there, and by including things such as "shamir's trick" for the equation. We could then use a proposal like tendermint/tendermint#2639 to capitalize on this. I am unsure what are approach should be for updates to cryptography libs, but I don't think we should update the C source, but instead should update a golang w/ asm source or a Rust source.

[ebuchman]

go-ethereum uses libsecp256k1 from bitcoin. they just copied the code into their repo. we should look to do the same. I'll close this for #3163. thanks!