crypto: add DecompressPubkey, VerifySignature (#15615)

We need those operations for p2p/enr.

Also upgrade github.com/btcsuite/btcd/btcec to the latest version
and improve BenchmarkSha3. The benchmark printed extra output 
that confused tools like benchstat and ignored N.

6 files changed, 212 insertions, 15 deletions

diff --git a/crypto/crypto_test.go b/crypto/crypto_test.go
index 92302948e..b4c441e5f 100644
--- a/crypto/crypto_test.go
+++ b/crypto/crypto_test.go
@@ -20,12 +20,10 @@ import (
 	"bytes"
 	"crypto/ecdsa"
 	"encoding/hex"
-	"fmt"
 	"io/ioutil"
 	"math/big"
 	"os"
 	"testing"
-	"time"
 
 	"github.com/ethereum/go-ethereum/common"
 )
@@ -44,13 +42,9 @@ func TestKeccak256Hash(t *testing.T) {
 
 func BenchmarkSha3(b *testing.B) {
 	a := []byte("hello world")
-	amount := 1000000
-	start := time.Now()
-	for i := 0; i < amount; i++ {
+	for i := 0; i < b.N; i++ {
 		Keccak256(a)
 	}
-
-	fmt.Println(amount, ":", time.Since(start))
 }
 
 func TestSign(t *testing.T) {
diff --git a/crypto/secp256k1/ext.h b/crypto/secp256k1/ext.h
index ee759fde6..b0f30b73c 100644
--- a/crypto/secp256k1/ext.h
+++ b/crypto/secp256k1/ext.h
@@ -46,6 +46,55 @@ static int secp256k1_ecdsa_recover_pubkey(
 	return secp256k1_ec_pubkey_serialize(ctx, pubkey_out, &outputlen, &pubkey, SECP256K1_EC_UNCOMPRESSED);
 }
 
+// secp256k1_ecdsa_verify_enc verifies an encoded compact signature.
+//
+// Returns: 1: signature is valid
+//          0: signature is invalid
+// Args:    ctx:        pointer to a context object (cannot be NULL)
+//  In:     sigdata:    pointer to a 64-byte signature (cannot be NULL)
+//          msgdata:    pointer to a 32-byte message (cannot be NULL)
+//          pubkeydata: pointer to public key data (cannot be NULL)
+//          pubkeylen:  length of pubkeydata
+static int secp256k1_ecdsa_verify_enc(
+	const secp256k1_context* ctx,
+	const unsigned char *sigdata,
+	const unsigned char *msgdata,
+	const unsigned char *pubkeydata,
+	size_t pubkeylen
+) {
+	secp256k1_ecdsa_signature sig;
+	secp256k1_pubkey pubkey;
+
+	if (!secp256k1_ecdsa_signature_parse_compact(ctx, &sig, sigdata)) {
+		return 0;
+	}
+	if (!secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeydata, pubkeylen)) {
+		return 0;
+	}
+	return secp256k1_ecdsa_verify(ctx, &sig, msgdata, &pubkey);
+}
+
+// secp256k1_decompress_pubkey decompresses a public key.
+//
+// Returns: 1: public key is valid
+//          0: public key is invalid
+// Args:    ctx:        pointer to a context object (cannot be NULL)
+//  Out:    pubkey_out: the serialized 65-byte public key (cannot be NULL)
+//  In:     pubkeydata: pointer to 33 bytes of compressed public key data (cannot be NULL)
+static int secp256k1_decompress_pubkey(
+	const secp256k1_context* ctx,
+	unsigned char *pubkey_out,
+	const unsigned char *pubkeydata
+) {
+	secp256k1_pubkey pubkey;
+
+	if (!secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeydata, 33)) {
+		return 0;
+	}
+	size_t outputlen = 65;
+	return secp256k1_ec_pubkey_serialize(ctx, pubkey_out, &outputlen, &pubkey, SECP256K1_EC_UNCOMPRESSED);
+}
+
 // secp256k1_pubkey_scalar_mul multiplies a point by a scalar in constant time.
 //
 // Returns: 1: multiplication was successful
diff --git a/crypto/secp256k1/secp256.go b/crypto/secp256k1/secp256.go
index 0ffa04fe0..00a1f8aaa 100644
--- a/crypto/secp256k1/secp256.go
+++ b/crypto/secp256k1/secp256.go
@@ -38,6 +38,7 @@ import "C"
 
 import (
 	"errors"
+	"math/big"
 	"unsafe"
 )
 
@@ -55,6 +56,7 @@ var (
 	ErrInvalidSignatureLen = errors.New("invalid signature length")
 	ErrInvalidRecoveryID   = errors.New("invalid signature recovery id")
 	ErrInvalidKey          = errors.New("invalid private key")
+	ErrInvalidPubkey       = errors.New("invalid public key")
 	ErrSignFailed          = errors.New("signing failed")
 	ErrRecoverFailed       = errors.New("recovery failed")
 )
@@ -119,6 +121,33 @@ func RecoverPubkey(msg []byte, sig []byte) ([]byte, error) {
 	return pubkey, nil
 }
 
+// VerifySignature checks that the given pubkey created signature over message.
+// The signature should be in [R || S] format.
+func VerifySignature(pubkey, msg, signature []byte) bool {
+	if len(msg) != 32 || len(signature) != 64 || len(pubkey) == 0 {
+		return false
+	}
+	sigdata := (*C.uchar)(unsafe.Pointer(&signature[0]))
+	msgdata := (*C.uchar)(unsafe.Pointer(&msg[0]))
+	keydata := (*C.uchar)(unsafe.Pointer(&pubkey[0]))
+	return C.secp256k1_ecdsa_verify_enc(context, sigdata, msgdata, keydata, C.size_t(len(pubkey))) != 0
+}
+
+// DecompressPubkey parses a public key in the 33-byte compressed format.
+// It returns non-nil coordinates if the public key is valid.
+func DecompressPubkey(pubkey []byte) (X, Y *big.Int) {
+	if len(pubkey) != 33 {
+		return nil, nil
+	}
+	buf := make([]byte, 65)
+	bufdata := (*C.uchar)(unsafe.Pointer(&buf[0]))
+	pubkeydata := (*C.uchar)(unsafe.Pointer(&pubkey[0]))
+	if C.secp256k1_decompress_pubkey(context, bufdata, pubkeydata) == 0 {
+		return nil, nil
+	}
+	return new(big.Int).SetBytes(buf[1:33]), new(big.Int).SetBytes(buf[33:])
+}
+
 func checkSignature(sig []byte) error {
 	if len(sig) != 65 {
 		return ErrInvalidSignatureLen
diff --git a/crypto/signature_cgo.go b/crypto/signature_cgo.go
index feec5e7be..381d8a1bb 100644
--- a/crypto/signature_cgo.go
+++ b/crypto/signature_cgo.go
@@ -27,10 +27,12 @@ import (
 	"github.com/ethereum/go-ethereum/crypto/secp256k1"
 )
 
+// Ecrecover returns the uncompressed public key that created the given signature.
 func Ecrecover(hash, sig []byte) ([]byte, error) {
 	return secp256k1.RecoverPubkey(hash, sig)
 }
 
+// SigToPub returns the public key that created the given signature.
 func SigToPub(hash, sig []byte) (*ecdsa.PublicKey, error) {
 	s, err := Ecrecover(hash, sig)
 	if err != nil {
@@ -58,6 +60,22 @@ func Sign(hash []byte, prv *ecdsa.PrivateKey) (sig []byte, err error) {
 	return secp256k1.Sign(hash, seckey)
 }
 
+// VerifySignature checks that the given public key created signature over hash.
+// The public key should be in compressed (33 bytes) or uncompressed (65 bytes) format.
+// The signature should have the 64 byte [R || S] format.
+func VerifySignature(pubkey, hash, signature []byte) bool {
+	return secp256k1.VerifySignature(pubkey, hash, signature)
+}
+
+// DecompressPubkey parses a public key in the 33-byte compressed format.
+func DecompressPubkey(pubkey []byte) (*ecdsa.PublicKey, error) {
+	x, y := secp256k1.DecompressPubkey(pubkey)
+	if x == nil {
+		return nil, fmt.Errorf("invalid public key")
+	}
+	return &ecdsa.PublicKey{X: x, Y: y, Curve: S256()}, nil
+}
+
 // S256 returns an instance of the secp256k1 curve.
 func S256() elliptic.Curve {
 	return secp256k1.S256()
diff --git a/crypto/signature_nocgo.go b/crypto/signature_nocgo.go
index a022eef9a..17fd613b2 100644
--- a/crypto/signature_nocgo.go
+++ b/crypto/signature_nocgo.go
@@ -21,11 +21,14 @@ package crypto
 import (
 	"crypto/ecdsa"
 	"crypto/elliptic"
+	"errors"
 	"fmt"
+	"math/big"
 
 	"github.com/btcsuite/btcd/btcec"
 )
 
+// Ecrecover returns the uncompressed public key that created the given signature.
 func Ecrecover(hash, sig []byte) ([]byte, error) {
 	pub, err := SigToPub(hash, sig)
 	if err != nil {
@@ -35,6 +38,7 @@ func Ecrecover(hash, sig []byte) ([]byte, error) {
 	return bytes, err
 }
 
+// SigToPub returns the public key that created the given signature.
 func SigToPub(hash, sig []byte) (*ecdsa.PublicKey, error) {
 	// Convert to btcec input format with 'recovery id' v at the beginning.
 	btcsig := make([]byte, 65)
@@ -71,6 +75,33 @@ func Sign(hash []byte, prv *ecdsa.PrivateKey) ([]byte, error) {
 	return sig, nil
 }
 
+// VerifySignature checks that the given public key created signature over hash.
+// The public key should be in compressed (33 bytes) or uncompressed (65 bytes) format.
+// The signature should have the 64 byte [R || S] format.
+func VerifySignature(pubkey, hash, signature []byte) bool {
+	if len(signature) != 64 {
+		return false
+	}
+	sig := &btcec.Signature{R: new(big.Int).SetBytes(signature[:32]), S: new(big.Int).SetBytes(signature[32:])}
+	key, err := btcec.ParsePubKey(pubkey, btcec.S256())
+	if err != nil {
+		return false
+	}
+	return sig.Verify(hash, key)
+}
+
+// DecompressPubkey parses a public key in the 33-byte compressed format.
+func DecompressPubkey(pubkey []byte) (*ecdsa.PublicKey, error) {
+	if len(pubkey) != 33 {
+		return nil, errors.New("invalid compressed public key length")
+	}
+	key, err := btcec.ParsePubKey(pubkey, btcec.S256())
+	if err != nil {
+		return nil, err
+	}
+	return key.ToECDSA(), nil
+}
+
 // S256 returns an instance of the secp256k1 curve.
 func S256() elliptic.Curve {
 	return btcec.S256()
diff --git a/crypto/signature_test.go b/crypto/signature_test.go
index aefd9e38d..abcab425b 100644
--- a/crypto/signature_test.go
+++ b/crypto/signature_test.go
@@ -18,19 +18,95 @@ package crypto
 
 import (
 	"bytes"
-	"encoding/hex"
 	"testing"
+
+	"github.com/ethereum/go-ethereum/common"
+	"github.com/ethereum/go-ethereum/common/hexutil"
+)
+
+var (
+	testmsg     = hexutil.MustDecode("0xce0677bb30baa8cf067c88db9811f4333d131bf8bcf12fe7065d211dce971008")
+	testsig     = hexutil.MustDecode("0x90f27b8b488db00b00606796d2987f6a5f59ae62ea05effe84fef5b8b0e549984a691139ad57a3f0b906637673aa2f63d1f55cb1a69199d4009eea23ceaddc9301")
+	testpubkey  = hexutil.MustDecode("0x04e32df42865e97135acfb65f3bae71bdc86f4d49150ad6a440b6f15878109880a0a2b2667f7e725ceea70c673093bf67663e0312623c8e091b13cf2c0f11ef652")
+	testpubkeyc = hexutil.MustDecode("0x02e32df42865e97135acfb65f3bae71bdc86f4d49150ad6a440b6f15878109880a")
 )
 
-func TestRecoverSanity(t *testing.T) {
-	msg, _ := hex.DecodeString("ce0677bb30baa8cf067c88db9811f4333d131bf8bcf12fe7065d211dce971008")
-	sig, _ := hex.DecodeString("90f27b8b488db00b00606796d2987f6a5f59ae62ea05effe84fef5b8b0e549984a691139ad57a3f0b906637673aa2f63d1f55cb1a69199d4009eea23ceaddc9301")
-	pubkey1, _ := hex.DecodeString("04e32df42865e97135acfb65f3bae71bdc86f4d49150ad6a440b6f15878109880a0a2b2667f7e725ceea70c673093bf67663e0312623c8e091b13cf2c0f11ef652")
-	pubkey2, err := Ecrecover(msg, sig)
+func TestEcrecover(t *testing.T) {
+	pubkey, err := Ecrecover(testmsg, testsig)
 	if err != nil {
 		t.Fatalf("recover error: %s", err)
 	}
-	if !bytes.Equal(pubkey1, pubkey2) {
-		t.Errorf("pubkey mismatch: want: %x have: %x", pubkey1, pubkey2)
+	if !bytes.Equal(pubkey, testpubkey) {
+		t.Errorf("pubkey mismatch: want: %x have: %x", testpubkey, pubkey)
+	}
+}
+
+func TestVerifySignature(t *testing.T) {
+	sig := testsig[:len(testsig)-1] // remove recovery id
+	if !VerifySignature(testpubkey, testmsg, sig) {
+		t.Errorf("can't verify signature with uncompressed key")
+	}
+	if !VerifySignature(testpubkeyc, testmsg, sig) {
+		t.Errorf("can't verify signature with compressed key")
+	}
+
+	if VerifySignature(nil, testmsg, sig) {
+		t.Errorf("signature valid with no key")
+	}
+	if VerifySignature(testpubkey, nil, sig) {
+		t.Errorf("signature valid with no message")
+	}
+	if VerifySignature(testpubkey, testmsg, nil) {
+		t.Errorf("nil signature valid")
+	}
+	if VerifySignature(testpubkey, testmsg, append(common.CopyBytes(sig), 1, 2, 3)) {
+		t.Errorf("signature valid with extra bytes at the end")
+	}
+	if VerifySignature(testpubkey, testmsg, sig[:len(sig)-2]) {
+		t.Errorf("signature valid even though it's incomplete")
+	}
+}
+
+func TestDecompressPubkey(t *testing.T) {
+	key, err := DecompressPubkey(testpubkeyc)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if uncompressed := FromECDSAPub(key); !bytes.Equal(uncompressed, testpubkey) {
+		t.Errorf("wrong public key result: got %x, want %x", uncompressed, testpubkey)
+	}
+	if _, err := DecompressPubkey(nil); err == nil {
+		t.Errorf("no error for nil pubkey")
+	}
+	if _, err := DecompressPubkey(testpubkeyc[:5]); err == nil {
+		t.Errorf("no error for incomplete pubkey")
+	}
+	if _, err := DecompressPubkey(append(common.CopyBytes(testpubkeyc), 1, 2, 3)); err == nil {
+		t.Errorf("no error for pubkey with extra bytes at the end")
+	}
+}
+
+func BenchmarkEcrecoverSignature(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		if _, err := Ecrecover(testmsg, testsig); err != nil {
+			b.Fatal("ecrecover error", err)
+		}
+	}
+}
+
+func BenchmarkVerifySignature(b *testing.B) {
+	sig := testsig[:len(testsig)-1] // remove recovery id
+	for i := 0; i < b.N; i++ {
+		if !VerifySignature(testpubkey, testmsg, sig) {
+			b.Fatal("verify error")
+		}
+	}
+}
+
+func BenchmarkDecompressPubkey(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		if _, err := DecompressPubkey(testpubkeyc); err != nil {
+			b.Fatal(err)
+		}
 	}
 }