BLS: sign/verify benchmarks for blst and ostracon

* Using Ed25519 signatures as reference for simple signatures
     production and (successful) verification with 1k messages.

crypto/bls/blst/blst.go

@@ -0,0 +1,87 @@
+package blst
+
+import (
+	"crypto/rand"
+
+	bls "github.com/supranational/blst/bindings/go"
+	"github.com/tendermint/tendermint/crypto"
+	"github.com/tendermint/tendermint/crypto/tmhash"
+	"github.com/tendermint/tendermint/libs/bytes"
+)
+
+const (
+	PrivKeyName   = "blst/PrivKey"
+	PubKeyName    = "blst/PubKey"
+	PrivKeySize   = 32
+	PubKeySize    = 192
+	SignatureSize = 96
+)
+
+var dst = []byte("BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_NUL_")
+
+// PrivKey implements tendermint.crypto.PrivKey.
+type PrivKey struct {
+	sk *bls.SecretKey
+}
+
+func GenPrivKey() *PrivKey {
+	var ikm [32]byte
+	_, _ = rand.Read(ikm[:])
+	return &PrivKey{bls.KeyGen(ikm[:])}
+}
+
+func (k *PrivKey) Bytes() []byte {
+	return k.sk.Serialize()
+}
+
+func (k *PrivKey) Equals(other crypto.PrivKey) bool {
+	if otherK, ok := other.(*PrivKey); ok {
+		return k.sk.Equals(otherK.sk)
+	}
+	return false
+}
+
+func (k *PrivKey) PubKey() crypto.PubKey {
+	return &PubKey{new(bls.P2Affine).From(k.sk)}
+}
+
+func (k *PrivKey) Sign(msg []byte) ([]byte, error) {
+	sig := new(bls.P1Affine).Sign(k.sk, msg, dst)
+	return sig.Serialize(), nil
+}
+
+func (k *PrivKey) Type() string {
+	return PrivKeyName
+}
+
+// PubKey implements tendermint.crypto.PubKey.
+type PubKey struct {
+	pk *bls.P2Affine
+}
+
+func (k *PubKey) Address() bytes.HexBytes {
+	return tmhash.SumTruncated(k.Bytes())
+}
+
+func (k *PubKey) Bytes() []byte {
+	return k.pk.Serialize()
+}
+
+func (k *PubKey) Equals(other crypto.PubKey) bool {
+	if otherK, ok := other.(*PubKey); ok {
+		return k.pk.Equals(otherK.pk)
+	}
+	return false
+}
+
+func (k *PubKey) Type() string {
+	return PubKeyName
+}
+
+func (k *PubKey) VerifySignature(msg []byte, bsig []byte) bool {
+	sig := new(bls.P1Affine).Deserialize(bsig)
+	if sig == nil {
+		return false
+	}
+	return sig.Verify(true, k.pk, false, msg, dst)
+}

crypto/bls/blst/blst_test.go

@@ -0,0 +1,97 @@
+package blst
+
+import "testing"
+
+func TestKeyGen(t *testing.T) {
+	key1 := GenPrivKey()
+	if key1 == nil {
+		t.Fatal("GenPrivKey() return nil")
+	}
+	b := key1.Bytes()
+	if len(b) != PrivKeySize {
+		t.Error("Serilalized private key", len(b), b)
+	}
+
+	key2 := GenPrivKey()
+	if key2 == nil {
+		t.Fatal("GenPrivKey() return nil")
+	}
+	b = key2.Bytes()
+	if len(b) != PrivKeySize {
+		t.Error("Serilalized private key", len(b), b)
+	}
+
+	if !key1.Equals(key1) {
+		t.Error("Private key not equal to itself", key1)
+	}
+	if !key2.Equals(key2) {
+		t.Error("Private key not equal to itself", key1)
+	}
+	if key1.Equals(key2) || key2.Equals(key1) {
+		t.Error("Different private keys equal", key1, key2)
+	}
+
+	pub1 := key1.PubKey()
+	if pub1 == nil {
+		t.Fatal("PubKey() return nil")
+	}
+	b = pub1.Bytes()
+	if len(b) != PubKeySize {
+		t.Error("Serilalized public key", len(b), b)
+	}
+
+	pub2 := key2.PubKey()
+	if pub2 == nil {
+		t.Fatal("PubKey() return nil")
+	}
+	b = pub2.Bytes()
+	if len(b) != PubKeySize {
+		t.Error("Serilalized public key", len(b), b)
+	}
+
+	if !pub1.Equals(pub1) {
+		t.Error("Public key not equal to itself", pub1)
+	}
+	if !pub2.Equals(pub2) {
+		t.Error("Public key not equal to itself", pub1)
+	}
+	if pub1.Equals(pub2) || pub2.Equals(pub1) {
+		t.Error("Different public keys equal", pub1, pub2)
+	}
+}
+
+func TestKeySignVerify(t *testing.T) {
+	msg := []byte("a test message")
+	key1 := GenPrivKey()
+	sig1, err := key1.Sign(msg)
+	if sig1 == nil || err != nil {
+		t.Fatal("Failed to sign message", sig1, err)
+	}
+	if len(sig1) != SignatureSize {
+		t.Error("Signature size", len(sig1), sig1)
+	}
+
+	key2 := GenPrivKey()
+	sig2, err := key2.Sign(msg)
+	if sig2 == nil || err != nil {
+		t.Fatal("Failed to sign message", sig2, err)
+	}
+	if len(sig2) != SignatureSize {
+		t.Error("Signature size", len(sig2), sig2)
+	}
+
+	pub1 := key1.PubKey()
+	pub2 := key2.PubKey()
+	if !pub1.VerifySignature(msg, sig1) {
+		t.Error("Failed to verify own signature", msg, sig1)
+	}
+	if !pub2.VerifySignature(msg, sig2) {
+		t.Error("Failed to verify own signature", msg, sig2)
+	}
+	if pub1.VerifySignature(msg, sig2) {
+		t.Error("Signature verified by wrong key", msg, sig2)
+	}
+	if pub2.VerifySignature(msg, sig1) {
+		t.Error("Signature verified by wrong key", msg, sig1)
+	}
+}

crypto/bls/go.mod

@@ -0,0 +1,21 @@
+module github.com/tendermint/tendermint/crypto/bls
+
+go 1.17
+
+require (
+	github.com/herumi/bls-eth-go-binary v0.0.0-20220216073600-600054663ec1
+	github.com/line/ostracon v1.0.4
+	github.com/stretchr/testify v1.7.1
+	github.com/supranational/blst v0.3.7
+	github.com/tendermint/tendermint v0.35.4
+)
+
+require (
+	github.com/davecgh/go-spew v1.1.1 // indirect
+	github.com/oasisprotocol/curve25519-voi v0.0.0-20210609091139-0a56a4bca00b // indirect
+	github.com/petermattis/goid v0.0.0-20180202154549-b0b1615b78e5 // indirect
+	github.com/pmezard/go-difflib v1.0.0 // indirect
+	github.com/sasha-s/go-deadlock v0.2.1-0.20190427202633-1595213edefa // indirect
+	golang.org/x/sys v0.0.0-20220412211240-33da011f77ad // indirect
+	gopkg.in/yaml.v3 v3.0.0-20210107192922-496545a6307b // indirect
+)

crypto/bls/ostracon/bls.go

@@ -0,0 +1,235 @@
+package ostracon
+
+import (
+	"bytes"
+	"crypto/sha512"
+	"crypto/subtle"
+	"fmt"
+
+	tmjson "github.com/line/ostracon/libs/json"
+
+	"github.com/herumi/bls-eth-go-binary/bls"
+
+	"github.com/tendermint/tendermint/crypto"
+	"github.com/tendermint/tendermint/crypto/tmhash"
+)
+
+var _ crypto.PrivKey = PrivKey{}
+
+const (
+	PrivKeyName   = "ostracon/PrivKeyBLS12"
+	PubKeyName    = "ostracon/PubKeyBLS12"
+	PrivKeySize   = 32
+	PubKeySize    = 48
+	SignatureSize = 96
+	KeyType       = "bls12-381"
+)
+
+func init() {
+	tmjson.RegisterType(PubKey{}, PubKeyName)
+	tmjson.RegisterType(PrivKey{}, PrivKeyName)
+
+	err := bls.Init(bls.BLS12_381)
+	if err != nil {
+		panic(fmt.Sprintf("ERROR: %s", err))
+	}
+	err = bls.SetETHmode(bls.EthModeLatest)
+	if err != nil {
+		panic(fmt.Sprintf("ERROR: %s", err))
+	}
+}
+
+// PrivKey implements crypto.PrivKey.
+type PrivKey [PrivKeySize]byte
+
+// AddSignature adds a BLS signature to the init. When the init is nil, then a new aggregate signature is built
+// from specified signature.
+func AddSignature(init []byte, signature []byte) (aggrSign []byte, err error) {
+	if init == nil {
+		blsSign := bls.Sign{}
+		init = blsSign.Serialize()
+	} else if len(init) != SignatureSize {
+		err = fmt.Errorf("invalid BLS signature: aggregated signature size %d is not valid size %d",
+			len(init), SignatureSize)
+		return
+	}
+	if len(signature) != SignatureSize {
+		err = fmt.Errorf("invalid BLS signature: signature size %d is not valid size %d",
+			len(signature), SignatureSize)
+		return
+	}
+	blsSign := bls.Sign{}
+	err = blsSign.Deserialize(signature)
+	if err != nil {
+		return
+	}
+	aggrBLSSign := bls.Sign{}
+	err = aggrBLSSign.Deserialize(init)
+	if err != nil {
+		return
+	}
+	aggrBLSSign.Add(&blsSign)
+	aggrSign = aggrBLSSign.Serialize()
+	return
+}
+
+func VerifyAggregatedSignature(aggregatedSignature []byte, pubKeys []PubKey, msgs [][]byte) error {
+	if len(pubKeys) != len(msgs) {
+		return fmt.Errorf("the number of public keys %d doesn't match the one of messages %d",
+			len(pubKeys), len(msgs))
+	}
+	if aggregatedSignature == nil {
+		if len(pubKeys) == 0 {
+			return nil
+		}
+		return fmt.Errorf(
+			"the aggregate signature was omitted, even though %d public keys were specified", len(pubKeys))
+	}
+	aggrSign := bls.Sign{}
+	err := aggrSign.Deserialize(aggregatedSignature)
+	if err != nil {
+		return err
+	}
+	blsPubKeys := make([]bls.PublicKey, len(pubKeys))
+	hashes := make([][]byte, len(msgs))
+	for i := 0; i < len(pubKeys); i++ {
+		blsPubKeys[i] = bls.PublicKey{}
+		err = blsPubKeys[i].Deserialize(pubKeys[i][:])
+		if err != nil {
+			return err
+		}
+		hash := sha512.Sum512_256(msgs[i])
+		hashes[i] = hash[:]
+	}
+	if !aggrSign.VerifyAggregateHashes(blsPubKeys, hashes) {
+		return fmt.Errorf("failed to verify the aggregated hashes by %d public keys", len(blsPubKeys))
+	}
+	return nil
+}
+
+// GenPrivKey generates a new BLS12-381 private key.
+func GenPrivKey() PrivKey {
+	sigKey := bls.SecretKey{}
+	sigKey.SetByCSPRNG()
+	sigKeyBinary := PrivKey{}
+	binary := sigKey.Serialize()
+	if len(binary) != PrivKeySize {
+		panic(fmt.Sprintf("unexpected BLS private key size: %d != %d", len(binary), PrivKeySize))
+	}
+	copy(sigKeyBinary[:], binary)
+	return sigKeyBinary
+}
+
+// Bytes marshals the privkey using amino encoding.
+func (privKey PrivKey) Bytes() []byte {
+	return privKey[:]
+}
+
+// Sign produces a signature on the provided message.
+func (privKey PrivKey) Sign(msg []byte) ([]byte, error) {
+	if msg == nil {
+		panic("Nil specified as the message")
+	}
+	blsKey := bls.SecretKey{}
+	err := blsKey.Deserialize(privKey[:])
+	if err != nil {
+		return nil, err
+	}
+	hash := sha512.Sum512_256(msg)
+	sign := blsKey.SignHash(hash[:])
+	return sign.Serialize(), nil
+}
+
+// FIXME: Type crypto.Proof not defined in Tendermint.
+//// VRFProve is not supported in BLS12.
+//func (privKey PrivKey) VRFProve(seed []byte) (crypto.Proof, error) {
+//	return nil, fmt.Errorf("VRF prove is not supported by the BLS12")
+//}
+
+// PubKey gets the corresponding public key from the private key.
+func (privKey PrivKey) PubKey() crypto.PubKey {
+	blsKey := bls.SecretKey{}
+	err := blsKey.Deserialize(privKey[:])
+	if err != nil {
+		panic(fmt.Sprintf("Not a BLS12-381 private key: %X", privKey[:]))
+	}
+	pubKey := blsKey.GetPublicKey()
+	pubKeyBinary := PubKey{}
+	binary := pubKey.Serialize()
+	if len(binary) != PubKeySize {
+		panic(fmt.Sprintf("unexpected BLS public key size: %d != %d", len(binary), PubKeySize))
+	}
+	copy(pubKeyBinary[:], binary)
+	return pubKeyBinary
+}
+
+// Equals - you probably don't need to use this.
+// Runs in constant time based on length of the keys.
+func (privKey PrivKey) Equals(other crypto.PrivKey) bool {
+	if otherEd, ok := other.(PrivKey); ok {
+		return subtle.ConstantTimeCompare(privKey[:], otherEd[:]) == 1
+	}
+	return false
+}
+
+// Type returns information to identify the type of this key.
+func (privKey PrivKey) Type() string {
+	return KeyType
+}
+
+var _ crypto.PubKey = PubKey{}
+
+// PubKey implements crypto.PubKey for the BLS12-381 signature scheme.
+type PubKey [PubKeySize]byte
+
+// Address is the SHA256-20 of the raw pubkey bytes.
+func (pubKey PubKey) Address() crypto.Address {
+	return tmhash.SumTruncated(pubKey[:])
+}
+
+// Bytes marshals the PubKey using amino encoding.
+func (pubKey PubKey) Bytes() []byte {
+	return pubKey[:]
+}
+
+func (pubKey PubKey) VerifySignature(msg []byte, sig []byte) bool {
+	// make sure we use the same algorithm to sign
+	if len(sig) != SignatureSize {
+		return false
+	}
+	blsPubKey := bls.PublicKey{}
+	err := blsPubKey.Deserialize(pubKey[:])
+	if err != nil {
+		return false
+	}
+	blsSign := bls.Sign{}
+	err = blsSign.Deserialize(sig)
+	if err != nil {
+		fmt.Printf("Signature Deserialize failed: %s", err)
+		return false
+	}
+	hash := sha512.Sum512_256(msg)
+	return blsSign.VerifyHash(&blsPubKey, hash[:])
+}
+
+// FIXME: Types crypto.Proof and crypto.Output not defined in Tendermint.
+//// VRFVerify is not supported in BLS12.
+//func (pubKey PubKey) VRFVerify(proof crypto.Proof, seed []byte) (crypto.Output, error) {
+//	return nil, fmt.Errorf("VRF verify is not supported by the BLS12")
+//}
+
+func (pubKey PubKey) String() string {
+	return fmt.Sprintf("PubKeyBLS12{%X}", pubKey[:])
+}
+
+func (pubKey PubKey) Equals(other crypto.PubKey) bool {
+	if otherEd, ok := other.(PubKey); ok {
+		return bytes.Equal(pubKey[:], otherEd[:])
+	}
+	return false
+}
+
+// Type returns information to identify the type of this key.
+func (pubKey PubKey) Type() string {
+	return KeyType
+}

crypto/bls/ostracon/bls_test.go

@@ -0,0 +1,372 @@
+package ostracon
+
+import (
+	"bytes"
+	"crypto/sha256"
+	"fmt"
+	"math/rand"
+	"reflect"
+	"testing"
+	"time"
+
+	b "github.com/herumi/bls-eth-go-binary/bls"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/stretchr/testify/require"
+
+	"github.com/tendermint/tendermint/crypto"
+)
+
+func TestBasicSignatureFunctions(t *testing.T) {
+	privateKey := b.SecretKey{}
+	privateKey.SetByCSPRNG()
+	publicKey := privateKey.GetPublicKey()
+
+	duplicatedPrivateKey := b.SecretKey{}
+	err := duplicatedPrivateKey.Deserialize(privateKey.Serialize())
+	if err != nil {
+		t.Fatalf("Private key deserialization failed.")
+	}
+
+	if len(privateKey.Serialize()) != PrivKeySize {
+		t.Fatalf("The constant size %d of the private key is different from the actual size %d.",
+			PrivKeySize, len(privateKey.Serialize()))
+	}
+
+	duplicatedPublicKey := b.PublicKey{}
+	err = duplicatedPublicKey.Deserialize(publicKey.Serialize())
+	if err != nil {
+		t.Fatalf("Public key deserialization failed.")
+	}
+
+	if len(publicKey.Serialize()) != PubKeySize {
+		t.Fatalf("The constant size %d of the public key is different from the actual size %d.",
+			PubKeySize, len(publicKey.Serialize()))
+	}
+
+	duplicatedSignature := func(sig *b.Sign) *b.Sign {
+		duplicatedSign := b.Sign{}
+		err := duplicatedSign.Deserialize(sig.Serialize())
+		if err != nil {
+			t.Fatalf("Signature deserialization failed.")
+		}
+
+		if len(sig.Serialize()) != SignatureSize {
+			t.Fatalf("The constant size %d of the signature is different from the actual size %d.",
+				SignatureSize, len(sig.Serialize()))
+		}
+		return &duplicatedSign
+	}
+
+	msg := []byte("hello, world")
+	for _, privKey := range []b.SecretKey{privateKey, duplicatedPrivateKey} {
+		for _, pubKey := range []*b.PublicKey{publicKey, &duplicatedPublicKey} {
+			signature := privKey.SignByte(msg)
+			if !signature.VerifyByte(pubKey, msg) {
+				t.Errorf("Signature verification failed.")
+			}
+
+			if !duplicatedSignature(signature).VerifyByte(pubKey, msg) {
+				t.Errorf("Signature verification failed.")
+			}
+
+			for i := 0; i < len(msg); i++ {
+				for j := 0; j < 8; j++ {
+					garbled := make([]byte, len(msg))
+					copy(garbled, msg)
+					garbled[i] ^= 1 << (8 - j - 1)
+					if bytes.Equal(msg, garbled) {
+						t.Fatalf("Not a barbled message")
+					}
+					if signature.VerifyByte(pubKey, garbled) {
+						t.Errorf("Signature verification was successful against a garbled byte sequence.")
+					}
+					if duplicatedSignature(signature).VerifyByte(pubKey, garbled) {
+						t.Errorf("Signature verification was successful against a garbled byte sequence.")
+					}
+				}
+			}
+		}
+	}
+}
+
+func TestSignatureAggregationAndVerify(t *testing.T) {
+	privKeys := make([]b.SecretKey, 25)
+	pubKeys := make([]b.PublicKey, len(privKeys))
+	msgs := make([][]byte, len(privKeys))
+	hash32s := make([][32]byte, len(privKeys))
+	signatures := make([]b.Sign, len(privKeys))
+	for i, privKey := range privKeys {
+		privKey.SetByCSPRNG()
+		pubKeys[i] = *privKey.GetPublicKey()
+		msgs[i] = []byte(fmt.Sprintf("hello, world #%d", i))
+		hash32s[i] = sha256.Sum256(msgs[i])
+		signatures[i] = *privKey.SignHash(hash32s[i][:])
+
+		// normal single-hash case
+		if !signatures[i].VerifyHash(&pubKeys[i], hash32s[i][:]) {
+			t.Fail()
+		}
+
+		// in case where 1-bit of hash was garbled
+		garbledHash := make([]byte, len(msgs[i]))
+		copy(garbledHash, msgs[i])
+		garbledHash[0] ^= 1 << 0
+		if garbledHash[0] == msgs[i][0] || signatures[i].VerifyByte(&pubKeys[i], garbledHash) {
+			t.Fail()
+		}
+
+		// Verification using an invalid public key
+	}
+
+	// aggregation
+	multiSig := b.Sign{}
+	multiSig.Aggregate(signatures)
+
+	// normal case
+	hashes := make([][]byte, len(privKeys))
+	for i := 0; i < len(hashes); i++ {
+		hashes[i] = hash32s[i][:]
+	}
+	if !multiSig.VerifyAggregateHashes(pubKeys, hashes) {
+		t.Fatalf("failed to validate the aggregate signature of the hashed message")
+	}
+
+	// in case where 1-bit of signature was garbled
+	multiSigBytes := multiSig.Serialize()
+	for i := range multiSigBytes {
+		for j := 0; j < 8; j++ {
+			garbledMultiSigBytes := make([]byte, len(multiSigBytes))
+			copy(garbledMultiSigBytes, multiSigBytes)
+			garbledMultiSigBytes[i] ^= 1 << j
+			if garbledMultiSigBytes[i] == multiSigBytes[i] {
+				t.Fail()
+			}
+			garbledMultiSig := b.Sign{}
+			err := garbledMultiSig.Deserialize(garbledMultiSigBytes)
+			if err == nil {
+				// Note that in some cases Deserialize() fails
+				if garbledMultiSig.VerifyAggregateHashes(pubKeys, hashes) {
+					t.Errorf("successfully verified the redacted signature")
+				}
+			}
+		}
+	}
+
+	// in case a public key used for verification is replaced
+	invalidPrivKey := b.SecretKey{}
+	invalidPrivKey.SetByCSPRNG()
+	invalidPubKeys := make([]b.PublicKey, len(pubKeys))
+	copy(invalidPubKeys, pubKeys)
+	invalidPubKeys[len(invalidPubKeys)-1] = *invalidPrivKey.GetPublicKey()
+	if multiSig.VerifyAggregateHashes(invalidPubKeys, hashes) {
+		t.Fatalf("successfully verified that it contains a public key that was not involved in the signing")
+	}
+
+	// in case a hash used for verification is replaced
+	invalidHashes := make([][]byte, len(hashes))
+	copy(invalidHashes, hashes)
+	invalidHash := sha256.Sum256([]byte("hello, world #99"))
+	invalidHashes[len(invalidHashes)-1] = invalidHash[:]
+	if multiSig.VerifyAggregateHashes(pubKeys, invalidHashes) {
+		t.Fatalf("successfully verified that it contains a hash that was not involved in the signing")
+	}
+}
+
+func generatePubKeysAndSigns(t *testing.T, size int) ([]PubKey, [][]byte, [][]byte) {
+	pubKeys := make([]PubKey, size)
+	msgs := make([][]byte, len(pubKeys))
+	sigs := make([][]byte, len(pubKeys))
+	for i := 0; i < len(pubKeys); i++ {
+		var err error
+		privKey := GenPrivKey()
+		pubKeys[i] = blsPublicKey(t, privKey.PubKey())
+		msgs[i] = []byte(fmt.Sprintf("hello, workd #%d", i))
+		sigs[i], err = privKey.Sign(msgs[i])
+		if err != nil {
+			t.Fatal(fmt.Sprintf("fail to sign: %s", err))
+		}
+		if !pubKeys[i].VerifySignature(msgs[i], sigs[i]) {
+			t.Fatal("fail to verify signature")
+		}
+	}
+	return pubKeys, msgs, sigs
+}
+
+func blsPublicKey(t *testing.T, pubKey crypto.PubKey) PubKey {
+	blsPubKey, ok := pubKey.(PubKey)
+	if !ok {
+		var keyType string
+		if t := reflect.TypeOf(pubKey); t.Kind() == reflect.Ptr {
+			keyType = "*" + t.Elem().Name()
+		} else {
+			keyType = t.Name()
+		}
+		t.Fatal(fmt.Sprintf("specified public key is not for BLS: %s", keyType))
+	}
+	return blsPubKey
+}
+
+func aggregateSignatures(init []byte, signatures [][]byte) (aggrSig []byte, err error) {
+	aggrSig = init
+	for _, sign := range signatures {
+		aggrSig, err = AddSignature(aggrSig, sign)
+		if err != nil {
+			return
+		}
+	}
+	return
+}
+
+func TestAggregatedSignature(t *testing.T) {
+
+	// generate BLS signatures and public keys
+	pubKeys, msgs, sigs := generatePubKeysAndSigns(t, 25)
+
+	// aggregate signatures
+	aggrSig, err := aggregateSignatures(nil, sigs)
+	if err != nil {
+		t.Errorf("fail to aggregate BLS signatures: %s", err)
+	}
+	if len(aggrSig) != SignatureSize {
+		t.Errorf("inconpatible signature size: %d != %d", len(aggrSig), SignatureSize)
+	}
+
+	// validate the aggregated signature
+	if err := VerifyAggregatedSignature(aggrSig, pubKeys, msgs); err != nil {
+		t.Errorf("fail to verify aggregated signature: %s", err)
+	}
+
+	// validate with the public keys and messages pair in random order
+	t.Run("Doesn't Depend on the Order of PublicKey-Message Pairs", func(t *testing.T) {
+		shuffledPubKeys := make([]PubKey, len(pubKeys))
+		shuffledMsgs := make([][]byte, len(msgs))
+		copy(shuffledPubKeys, pubKeys)
+		copy(shuffledMsgs, msgs)
+		rand.Seed(time.Now().UnixNano())
+		rand.Shuffle(len(shuffledPubKeys), func(i, j int) {
+			shuffledPubKeys[i], shuffledPubKeys[j] = shuffledPubKeys[j], shuffledPubKeys[i]
+			shuffledMsgs[i], shuffledMsgs[j] = shuffledMsgs[j], shuffledMsgs[i]
+		})
+		if err := VerifyAggregatedSignature(aggrSig, shuffledPubKeys, shuffledMsgs); err != nil {
+			t.Errorf("fail to verify the aggregated signature with random order: %s", err)
+		}
+	})
+
+	// validate with the public keys in random order
+	t.Run("Incorrect Public Key Order", func(t *testing.T) {
+		shuffledPubKeys := make([]PubKey, len(pubKeys))
+		copy(shuffledPubKeys, pubKeys)
+		rand.Seed(time.Now().UnixNano())
+		rand.Shuffle(len(shuffledPubKeys), func(i, j int) {
+			shuffledPubKeys[i], shuffledPubKeys[j] = shuffledPubKeys[j], shuffledPubKeys[i]
+		})
+		if err := VerifyAggregatedSignature(aggrSig, shuffledPubKeys, msgs); err == nil {
+			t.Error("successfully validated with public keys of different order")
+		}
+	})
+
+	// validate with the messages in random order
+	t.Run("Incorrect Message Order", func(t *testing.T) {
+		shuffledMsgs := make([][]byte, len(msgs))
+		copy(shuffledMsgs, msgs)
+		rand.Seed(time.Now().UnixNano())
+		rand.Shuffle(len(shuffledMsgs), func(i, j int) {
+			shuffledMsgs[i], shuffledMsgs[j] = shuffledMsgs[j], shuffledMsgs[i]
+		})
+		if err := VerifyAggregatedSignature(aggrSig, pubKeys, shuffledMsgs); err == nil {
+			t.Error("successfully validated with messages of different order")
+		}
+	})
+
+	// replace one public key with another and detect
+	t.Run("Replace One Public Key", func(t *testing.T) {
+		pubKey, _ := GenPrivKey().PubKey().(PubKey)
+		replacedPubKeys := make([]PubKey, len(pubKeys))
+		copy(replacedPubKeys, pubKeys)
+		replacedPubKeys[0] = pubKey
+		if err := VerifyAggregatedSignature(aggrSig, replacedPubKeys, msgs); err == nil {
+			t.Error("verification with an invalid key was successful")
+		}
+	})
+
+	// replace one message with another and detect
+	t.Run("Replace One Message", func(t *testing.T) {
+		msg := []byte(fmt.Sprintf("hello, world #%d replaced", len(msgs)))
+		replacedMsgs := make([][]byte, len(msgs))
+		copy(replacedMsgs, msgs)
+		replacedMsgs[0] = msg
+		if err := VerifyAggregatedSignature(aggrSig, pubKeys, replacedMsgs); err == nil {
+			t.Error("verification with an invalid message was successful")
+		}
+	})
+
+	// add new signature to existing aggregated signature and verify
+	t.Run("Incremental Update", func(t *testing.T) {
+		msg := []byte(fmt.Sprintf("hello, world #%d", len(msgs)))
+		privKey := GenPrivKey()
+		pubKey := privKey.PubKey()
+		sig, err := privKey.Sign(msg)
+		assert.Nilf(t, err, "%s", err)
+		newAggrSig, _ := aggregateSignatures(aggrSig, [][]byte{sig})
+		newPubKeys := make([]PubKey, len(pubKeys))
+		copy(newPubKeys, pubKeys)
+		newPubKeys = append(newPubKeys, blsPublicKey(t, pubKey))
+		newMsgs := make([][]byte, len(msgs))
+		copy(newMsgs, msgs)
+		newMsgs = append(newMsgs, msg)
+		if err := VerifyAggregatedSignature(newAggrSig, newPubKeys, newMsgs); err != nil {
+			t.Errorf("fail to verify the aggregate signature with the new signature: %s", err)
+		}
+	})
+
+	// nil is returned for nil and empty signature
+	nilSig, _ := aggregateSignatures(nil, [][]byte{})
+	assert.Nil(t, nilSig)
+
+	// a non-BLS signature contained
+	func() {
+		_, err = aggregateSignatures(nil, [][]byte{make([]byte, 0)})
+		assert.NotNil(t, err)
+	}()
+}
+
+func TestSignatureAggregation(t *testing.T) {
+	publicKeys := make([]b.PublicKey, 25)
+	aggregatedSignature := b.Sign{}
+	aggregatedPublicKey := b.PublicKey{}
+	msg := []byte("hello, world")
+	for i := 0; i < len(publicKeys); i++ {
+		privateKey := b.SecretKey{}
+		privateKey.SetByCSPRNG()
+		publicKeys[i] = *privateKey.GetPublicKey()
+		aggregatedSignature.Add(privateKey.SignByte(msg))
+		aggregatedPublicKey.Add(&publicKeys[i])
+	}
+
+	if !aggregatedSignature.FastAggregateVerify(publicKeys, msg) {
+		t.Errorf("Aggregated signature verification failed.")
+	}
+	if !aggregatedSignature.VerifyByte(&aggregatedPublicKey, msg) {
+		t.Errorf("Aggregated signature verification failed.")
+	}
+}
+
+func TestSignAndValidateBLS12(t *testing.T) {
+	privKey := GenPrivKey()
+	pubKey := privKey.PubKey()
+
+	msg := crypto.CRandBytes(128)
+	sig, err := privKey.Sign(msg)
+	require.Nil(t, err)
+	//fmt.Printf("restoring signature: %x\n", sig)
+
+	// Test the signature
+	assert.True(t, pubKey.VerifySignature(msg, sig))
+
+	// Mutate the signature, just one bit.
+	// TODO: Replace this with a much better fuzzer, tendermint/ed25519/issues/10
+	sig[7] ^= byte(0x01)
+
+	assert.False(t, pubKey.VerifySignature(msg, sig))
+}

crypto/bls/signatures_test.go

@@ -0,0 +1,189 @@
+package bls
+
+import (
+	"crypto/rand"
+	"testing"
+
+	"github.com/tendermint/tendermint/crypto"
+	"github.com/tendermint/tendermint/crypto/bls/blst"
+	"github.com/tendermint/tendermint/crypto/bls/ostracon"
+	"github.com/tendermint/tendermint/crypto/ed25519"
+)
+
+func TestEd25519SignVerify(t *testing.T) {
+	m := []byte("a test message to be signed")
+	privKey := ed25519.GenPrivKey()
+	pubKey := privKey.PubKey()
+
+	sig, err := privKey.Sign(m)
+	if err != nil {
+		t.Error("Unexpected nil signature or error", m, sig, err)
+	}
+	if !pubKey.VerifySignature(m, sig) {
+		t.Error("Failed to verify signature produced by the key", m, sig)
+	}
+	if pubKey.VerifySignature(scrambleBytes(m), sig) {
+		t.Error("Unexpected to verify scrambled message", scrambleBytes(m), sig)
+	}
+	if pubKey.VerifySignature(m, scrambleBytes(sig)) {
+		t.Error("Unexpected to verify scrambled signature", m, scrambleBytes(sig))
+	}
+}
+
+func TestBlstSignVerify(t *testing.T) {
+	m := []byte("a test message to be signed")
+	privKey := blst.GenPrivKey()
+	pubKey := privKey.PubKey()
+
+	sig, err := privKey.Sign(m)
+	if err != nil {
+		t.Error("Unexpected nil signature or error", m, sig, err)
+	}
+	if !pubKey.VerifySignature(m, sig) {
+		t.Error("Failed to verify signature produced by the key", m, sig)
+	}
+	if pubKey.VerifySignature(scrambleBytes(m), sig) {
+		t.Error("Unexpected to verify scrambled message", scrambleBytes(m), sig)
+	}
+	if pubKey.VerifySignature(m, scrambleBytes(sig)) {
+		t.Error("Unexpected to verify scrambled signature", m, scrambleBytes(sig))
+	}
+}
+
+func TestOstraconSignVerify(t *testing.T) {
+	m := []byte("a test message to be signed")
+	privKey := ostracon.GenPrivKey()
+	pubKey := privKey.PubKey()
+
+	sig, err := privKey.Sign(m)
+	if err != nil {
+		t.Error("Unexpected nil signature or error", m, sig, err)
+	}
+	if !pubKey.VerifySignature(m, sig) {
+		t.Error("Failed to verify signature produced by the key", m, sig)
+	}
+	if pubKey.VerifySignature(scrambleBytes(m), sig) {
+		t.Error("Unexpected to verify scrambled message", scrambleBytes(m), sig)
+	}
+	if pubKey.VerifySignature(m, scrambleBytes(sig)) {
+		t.Error("Unexpected to verify scrambled signature", m, scrambleBytes(sig))
+	}
+}
+
+// Scrambles a byte array, currently just flipping a bit.
+// TODO: implement a more complex scrambling method.
+func scrambleBytes(b []byte) []byte {
+	bb := make([]byte, len(b))
+	copy(bb, b)
+	index := len(b) / 2
+	bb[index] ^= 1
+	return bb
+}
+
+// Retrieve a set of public keys from a set of private keys.
+func pubKeysFromPrivKeys(privKeys []crypto.PrivKey) []crypto.PubKey {
+	pubKeys := make([]crypto.PubKey, len(privKeys))
+	for i := 0; i < len(privKeys); i++ {
+		pubKeys[i] = privKeys[i].PubKey()
+	}
+	return pubKeys
+}
+
+// Generate n random messages with the given size.
+func randomMessages(n, size int) [][]byte {
+	messages := make([][]byte, n)
+	for i := 0; i < n; i++ {
+		messages[i] = make([]byte, size)
+		rand.Read(messages[i])
+	}
+	return messages
+}
+
+// Sign a set of messages with a number of private keys.
+func signMessages(messages [][]byte, privKeys []crypto.PrivKey) [][]byte {
+	sigs := make([][]byte, len(messages))
+	for i := 0; i < len(messages); i++ {
+		sigs[i], _ = privKeys[i%len(privKeys)].Sign(messages[i])
+	}
+	return sigs
+}
+
+var _sig []byte
+
+func BenchmarkEd25519Sign1k(t *testing.B) {
+	messages := randomMessages(1000, 1024)
+	privKeys := make([]crypto.PrivKey, 128)
+	for i := 0; i < len(privKeys); i++ {
+		privKeys[i] = ed25519.GenPrivKey()
+	}
+	t.ResetTimer()
+	for i := 0; i < t.N; i++ {
+		_sig, _ = privKeys[i%len(privKeys)].Sign(messages[i%len(messages)])
+	}
+}
+
+func BenchmarkEd25519Verify1k(t *testing.B) {
+	messages := randomMessages(1000, 1024)
+	privKeys := make([]crypto.PrivKey, 128)
+	for i := 0; i < len(privKeys); i++ {
+		privKeys[i] = ed25519.GenPrivKey()
+	}
+	pubKeys := pubKeysFromPrivKeys(privKeys)
+	sigs := signMessages(messages, privKeys)
+	t.ResetTimer()
+	for i := 0; i < t.N; i++ {
+		pubKeys[i%len(pubKeys)].VerifySignature(messages[i%len(messages)], sigs[i%len(sigs)])
+	}
+}
+
+func BenchmarkBlstSign1k(t *testing.B) {
+	messages := randomMessages(1000, 1024)
+	privKeys := make([]crypto.PrivKey, 128)
+	for i := 0; i < len(privKeys); i++ {
+		privKeys[i] = blst.GenPrivKey()
+	}
+	t.ResetTimer()
+	for i := 0; i < t.N; i++ {
+		_sig, _ = privKeys[i%len(privKeys)].Sign(messages[i%len(messages)])
+	}
+}
+
+func BenchmarkBlstVerify1k(t *testing.B) {
+	messages := randomMessages(1000, 1024)
+	privKeys := make([]crypto.PrivKey, 128)
+	for i := 0; i < len(privKeys); i++ {
+		privKeys[i] = blst.GenPrivKey()
+	}
+	pubKeys := pubKeysFromPrivKeys(privKeys)
+	sigs := signMessages(messages, privKeys)
+	t.ResetTimer()
+	for i := 0; i < t.N; i++ {
+		pubKeys[i%len(pubKeys)].VerifySignature(messages[i%len(messages)], sigs[i%len(sigs)])
+	}
+}
+
+func BenchmarkOstraconSign1k(t *testing.B) {
+	messages := randomMessages(1000, 1024)
+	privKeys := make([]crypto.PrivKey, 128)
+	for i := 0; i < len(privKeys); i++ {
+		privKeys[i] = ostracon.GenPrivKey()
+	}
+	t.ResetTimer()
+	for i := 0; i < t.N; i++ {
+		_sig, _ = privKeys[i%len(privKeys)].Sign(messages[i%len(messages)])
+	}
+}
+
+func BenchmarkOstraconVerify1k(t *testing.B) {
+	messages := randomMessages(1000, 1024)
+	privKeys := make([]crypto.PrivKey, 128)
+	for i := 0; i < len(privKeys); i++ {
+		privKeys[i] = ostracon.GenPrivKey()
+	}
+	pubKeys := pubKeysFromPrivKeys(privKeys)
+	sigs := signMessages(messages, privKeys)
+	t.ResetTimer()
+	for i := 0; i < t.N; i++ {
+		pubKeys[i%len(pubKeys)].VerifySignature(messages[i%len(messages)], sigs[i%len(sigs)])
+	}
+}