crypto: dkg implementation and test. (#96)

* DKG API and test.

* Change naming

* Broadcast pubShares

4 files changed, 632 insertions, 1 deletions

diff --git a/crypto/dkg/constant.go b/crypto/dkg/constant.go
new file mode 100644
index 0000000..97ab008
--- /dev/null
+++ b/crypto/dkg/constant.go
@@ -0,0 +1,26 @@
+// Copyright 2018 The dexon-consensus-core Authors
+// This file is part of the dexon-consensus-core library.
+//
+// The dexon-consensus-core library is free software: you can redistribute it
+// and/or modify it under the terms of the GNU Lesser General Public License as
+// published by the Free Software Foundation, either version 3 of the License,
+// or (at your option) any later version.
+//
+// The dexon-consensus-core library is distributed in the hope that it will be
+// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
+// General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the dexon-consensus-core library. If not, see
+// <http://www.gnu.org/licenses/>.
+
+package dkg
+
+import (
+	"github.com/herumi/bls/ffi/go/bls"
+)
+
+const (
+	curve = bls.CurveFp382_2
+)
diff --git a/crypto/dkg/dkg.go b/crypto/dkg/dkg.go
index b5e8d03..d3596e6 100644
--- a/crypto/dkg/dkg.go
+++ b/crypto/dkg/dkg.go
@@ -18,9 +18,280 @@
 package dkg
 
 import (
+	"fmt"
+
 	"github.com/herumi/bls/ffi/go/bls"
+
+	"github.com/dexon-foundation/dexon-consensus-core/common"
+	"github.com/dexon-foundation/dexon-consensus-core/crypto"
+)
+
+var (
+	// ErrDuplicatedShare is reported when adding an private key share of same id.
+	ErrDuplicatedShare = fmt.Errorf("invalid share")
+	// ErrNoIDToRecover is reported when no id is provided for recovering private
+	// key.
+	ErrNoIDToRecover = fmt.Errorf("no id to recover private key")
+	// ErrShareNotFound is reported when the private key share of id is not found
+	// when recovering private key.
+	ErrShareNotFound = fmt.Errorf("share not found")
 )
 
 func init() {
-	bls.Init(0)
+	bls.Init(curve)
+}
+
+// PrivateKey represents a private key structure implments
+// Crypto.PrivateKey interface.
+type PrivateKey struct {
+	privateKey bls.SecretKey
+	id         bls.ID
+	publicKey  PublicKey
+}
+
+// ID is the id for DKG protocol.
+type ID = bls.ID
+
+// IDs is an array of ID.
+type IDs []ID
+
+// PublicKey represents a public key structure implements
+// Crypto.PublicKey interface.
+type PublicKey struct {
+	publicKey bls.PublicKey
+}
+
+// PrivateKeyShares represents a private key shares for DKG protocol.
+type PrivateKeyShares struct {
+	shares     []PrivateKey
+	shareIndex map[ID]int
+}
+
+// PublicKeyShares represents a public key shares for DKG protocol.
+type PublicKeyShares struct {
+	shares          []PublicKey
+	shareIndex      map[ID]int
+	masterPublicKey []bls.PublicKey
+}
+
+// NewID creates a ew ID structure.
+func NewID(id []byte) ID {
+	var blsID bls.ID
+	blsID.SetLittleEndian(id)
+	return blsID
+}
+
+// NewPrivateKey creates a new PrivateKey structure.
+func NewPrivateKey() *PrivateKey {
+	var key bls.SecretKey
+	key.SetByCSPRNG()
+	return &PrivateKey{
+		privateKey: key,
+		publicKey:  *newPublicKey(&key),
+	}
+}
+
+// NewPrivateKeyShares creates a private key shares for k-of-n TSIG.
+func NewPrivateKeyShares(k int, IDs IDs) (*PrivateKeyShares, *PublicKeyShares) {
+	var prv bls.SecretKey
+	prv.SetByCSPRNG()
+	msk := prv.GetMasterSecretKey(k)
+	mpk := bls.GetMasterPublicKey(msk)
+	shares := make([]PrivateKey, len(IDs))
+	shareMap := make(map[ID]int)
+	for idx, ID := range IDs {
+		shares[idx].privateKey.Set(msk, &ID)
+		shareMap[ID] = idx
+	}
+	return &PrivateKeyShares{
+			shares:     shares,
+			shareIndex: shareMap,
+		}, &PublicKeyShares{
+			shareIndex:      make(map[ID]int),
+			masterPublicKey: mpk,
+		}
+}
+
+// NewEmptyPrivateKeyShares creates an empty private key shares.
+func NewEmptyPrivateKeyShares() *PrivateKeyShares {
+	return &PrivateKeyShares{
+		shareIndex: make(map[ID]int),
+	}
+}
+
+// AddShare adds a share.
+func (prvs *PrivateKeyShares) AddShare(ID ID, share *PrivateKey) error {
+	if idx, exist := prvs.shareIndex[ID]; exist {
+		if !share.privateKey.IsEqual(&prvs.shares[idx].privateKey) {
+			return ErrDuplicatedShare
+		}
+		return nil
+	}
+	prvs.shareIndex[ID] = len(prvs.shares)
+	prvs.shares = append(prvs.shares, *share)
+	return nil
+}
+
+// RecoverPrivateKey recovers private key from the shares.
+func (prvs *PrivateKeyShares) RecoverPrivateKey(qualifyIDs IDs) (
+	*PrivateKey, error) {
+	var prv PrivateKey
+	if len(qualifyIDs) == 0 {
+		return nil, ErrNoIDToRecover
+	}
+	for i, ID := range qualifyIDs {
+		idx, exist := prvs.shareIndex[ID]
+		if !exist {
+			return nil, ErrShareNotFound
+		}
+		if i == 0 {
+			prv.privateKey = prvs.shares[idx].privateKey
+			continue
+		}
+		prv.privateKey.Add(&prvs.shares[idx].privateKey)
+	}
+	return &prv, nil
+}
+
+// RecoverPublicKey recovers public key from the shares.
+func (prvs *PrivateKeyShares) RecoverPublicKey(qualifyIDs IDs) (
+	*PublicKey, error) {
+	var pub PublicKey
+	if len(qualifyIDs) == 0 {
+		return nil, ErrNoIDToRecover
+	}
+	for i, ID := range qualifyIDs {
+		idx, exist := prvs.shareIndex[ID]
+		if !exist {
+			return nil, ErrShareNotFound
+		}
+		if i == 0 {
+			pub.publicKey = *prvs.shares[idx].privateKey.GetPublicKey()
+			continue
+		}
+		pub.publicKey.Add(prvs.shares[idx].privateKey.GetPublicKey())
+	}
+	return &pub, nil
+}
+
+// Share returns the share for the ID.
+func (prvs *PrivateKeyShares) Share(ID ID) (*PrivateKey, bool) {
+	idx, exist := prvs.shareIndex[ID]
+	if !exist {
+		return nil, false
+	}
+	return &prvs.shares[idx], true
+}
+
+// NewEmptyPublicKeyShares creates an empty public key shares.
+func NewEmptyPublicKeyShares() *PublicKeyShares {
+	return &PublicKeyShares{
+		shareIndex: make(map[ID]int),
+	}
+}
+
+// Share returns the share for the ID.
+func (pubs *PublicKeyShares) Share(ID ID) (*PublicKey, error) {
+	idx, exist := pubs.shareIndex[ID]
+	if exist {
+		return &pubs.shares[idx], nil
+	}
+	var pk PublicKey
+	if err := pk.publicKey.Set(pubs.masterPublicKey, &ID); err != nil {
+		return nil, err
+	}
+	pubs.AddShare(ID, &pk)
+	return &pk, nil
+}
+
+// AddShare adds a share.
+func (pubs *PublicKeyShares) AddShare(ID ID, share *PublicKey) error {
+	if idx, exist := pubs.shareIndex[ID]; exist {
+		if !share.publicKey.IsEqual(&pubs.shares[idx].publicKey) {
+			return ErrDuplicatedShare
+		}
+		return nil
+	}
+	pubs.shareIndex[ID] = len(pubs.shares)
+	pubs.shares = append(pubs.shares, *share)
+	return nil
+}
+
+// VerifyPrvShare verifies if the private key shares is valid.
+func (pubs *PublicKeyShares) VerifyPrvShare(ID ID, share *PrivateKey) (
+	bool, error) {
+	var pk bls.PublicKey
+	if err := pk.Set(pubs.masterPublicKey, &ID); err != nil {
+		return false, err
+	}
+	return pk.IsEqual(share.privateKey.GetPublicKey()), nil
+}
+
+// VerifyPubShare verifies if the public key shares is valid.
+func (pubs *PublicKeyShares) VerifyPubShare(ID ID, share *PublicKey) (
+	bool, error) {
+	var pk bls.PublicKey
+	if err := pk.Set(pubs.masterPublicKey, &ID); err != nil {
+		return false, err
+	}
+	return pk.IsEqual(&share.publicKey), nil
+}
+
+// RecoverPublicKey recovers private key from the shares.
+func (pubs *PublicKeyShares) RecoverPublicKey(qualifyIDs IDs) (
+	*PublicKey, error) {
+	var pub PublicKey
+	if len(qualifyIDs) == 0 {
+		return nil, ErrNoIDToRecover
+	}
+	for i, ID := range qualifyIDs {
+		idx, exist := pubs.shareIndex[ID]
+		if !exist {
+			return nil, ErrShareNotFound
+		}
+		if i == 0 {
+			pub.publicKey = pubs.shares[idx].publicKey
+			continue
+		}
+		pub.publicKey.Add(&pubs.shares[idx].publicKey)
+	}
+	return &pub, nil
+}
+
+// newPublicKey creates a new PublicKey structure.
+func newPublicKey(prvKey *bls.SecretKey) *PublicKey {
+	return &PublicKey{
+		publicKey: *prvKey.GetPublicKey(),
+	}
+}
+
+// PublicKey returns the public key associate this private key.
+func (prv *PrivateKey) PublicKey() crypto.PublicKey {
+	return prv.publicKey
+}
+
+// Sign calculates a signature.
+func (prv *PrivateKey) Sign(hash common.Hash) (crypto.Signature, error) {
+	msg := string(hash[:])
+	sign := prv.privateKey.Sign(msg)
+	return crypto.Signature(sign.Serialize()), nil
+}
+
+// VerifySignature checks that the given public key created signature over hash.
+func (pub PublicKey) VerifySignature(
+	hash common.Hash, signature crypto.Signature) bool {
+	var sig bls.Sign
+	if err := sig.Deserialize(signature[:]); err != nil {
+		fmt.Println(err)
+		return false
+	}
+	msg := string(hash[:])
+	return sig.Verify(&pub.publicKey, msg)
+}
+
+// Bytes returns the []byte representation of public key.
+func (pub PublicKey) Bytes() []byte {
+	var bytes []byte
+	pub.publicKey.Deserialize(bytes)
+	return bytes
 }
diff --git a/crypto/dkg/dkg_test.go b/crypto/dkg/dkg_test.go
new file mode 100644
index 0000000..27fe9a8
--- /dev/null
+++ b/crypto/dkg/dkg_test.go
@@ -0,0 +1,265 @@
+// Copyright 2018 The dexon-consensus-core Authors
+// This file is part of the dexon-consensus-core library.
+//
+// The dexon-consensus-core library is free software: you can redistribute it
+// and/or modify it under the terms of the GNU Lesser General Public License as
+// published by the Free Software Foundation, either version 3 of the License,
+// or (at your option) any later version.
+//
+// The dexon-consensus-core library is distributed in the hope that it will be
+// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
+// General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the dexon-consensus-core library. If not, see
+// <http://www.gnu.org/licenses/>.
+
+package dkg
+
+import (
+	"encoding/binary"
+	"math/rand"
+	"sort"
+	"testing"
+
+	"github.com/stretchr/testify/suite"
+
+	"github.com/dexon-foundation/dexon-consensus-core/common"
+	"github.com/dexon-foundation/dexon-consensus-core/crypto"
+)
+
+type DKGTestSuite struct {
+	suite.Suite
+}
+
+type member struct {
+	id                ID
+	prvShares         *PrivateKeyShares
+	pubShares         *PublicKeyShares
+	receivedPrvShares *PrivateKeyShares
+	receivedPubShares map[ID]*PublicKeyShares
+}
+
+func (s *DKGTestSuite) genID(k int) IDs {
+	IDs := make(IDs, 0, k)
+	for i := 0; i < k; i++ {
+		id := make([]byte, 8)
+		binary.LittleEndian.PutUint64(id, rand.Uint64())
+		IDs = append(IDs, NewID(id))
+	}
+	return IDs
+}
+
+func (s *DKGTestSuite) sendKey(senders []member, receivers []member) {
+	for _, sender := range senders {
+		for _, receiver := range receivers {
+			// Here's the demonstration of DKG protocol. `pubShares` is broadcasted
+			// and all the receiver would save it to the `receivedPubShares`.
+			// Do not optimize the memory usage of this part.
+			receiver.receivedPubShares[sender.id] = sender.pubShares
+			prvShare, ok := sender.prvShares.Share(receiver.id)
+			s.Require().True(ok)
+			pubShare, err := sender.pubShares.Share(receiver.id)
+			s.Require().NoError(err)
+			valid, err := receiver.receivedPubShares[sender.id].
+				VerifyPrvShare(receiver.id, prvShare)
+			s.Require().NoError(err)
+			s.Require().True(valid)
+			valid, err = receiver.receivedPubShares[sender.id].
+				VerifyPubShare(receiver.id, pubShare)
+			s.Require().NoError(err)
+			s.Require().True(valid)
+			err = receiver.receivedPrvShares.AddShare(sender.id, prvShare)
+			s.Require().NoError(err)
+		}
+	}
+}
+
+func (s *DKGTestSuite) signWithQualifyIDs(
+	member member, qualifyIDs IDs, hash common.Hash) PartialSignature {
+	prvKey, err := member.receivedPrvShares.RecoverPrivateKey(qualifyIDs)
+	s.Require().NoError(err)
+	sig, err := prvKey.Sign(hash)
+	s.Require().NoError(err)
+	return PartialSignature(sig)
+}
+
+func (s *DKGTestSuite) verifySigWithQualifyIDs(
+	members []member, qualifyIDs IDs,
+	signer ID, hash common.Hash, sig PartialSignature) bool {
+	membersIdx := make(map[ID]int)
+	for idx, member := range members {
+		membersIdx[member.id] = idx
+	}
+	pubShares := NewEmptyPublicKeyShares()
+	for _, id := range qualifyIDs {
+		idx, exist := membersIdx[id]
+		s.Require().True(exist)
+		member := members[idx]
+		pubShare, err := member.pubShares.Share(signer)
+		s.Require().NoError(err)
+		err = pubShares.AddShare(id, pubShare)
+		s.Require().NoError(err)
+	}
+	pubKey, err := pubShares.RecoverPublicKey(qualifyIDs)
+	s.Require().NoError(err)
+	return pubKey.VerifySignature(hash, crypto.Signature(sig))
+}
+
+func (s *DKGTestSuite) TestVerifyKeyShares() {
+	invalidID := NewID([]byte{0})
+	ids := []ID{NewID([]byte{1}), NewID([]byte{2}), NewID([]byte{3})}
+	members := []member{}
+	for _, id := range ids {
+		members = append(members, member{
+			id:                id,
+			receivedPubShares: make(map[ID]*PublicKeyShares),
+		})
+	}
+
+	prvShares, pubShares := NewPrivateKeyShares(2, ids)
+
+	_, ok := prvShares.Share(invalidID)
+	s.False(ok)
+	for _, id := range ids {
+		prvShare, ok := prvShares.Share(id)
+		s.Require().True(ok)
+		valid, err := pubShares.VerifyPrvShare(id, prvShare)
+		s.Require().NoError(err)
+		s.True(valid)
+		pubShare, err := pubShares.Share(id)
+		s.Require().NoError(err)
+		valid, err = pubShares.VerifyPubShare(id, pubShare)
+		s.Require().NoError(err)
+		s.True(valid)
+	}
+
+	// Test of faulty private/public key.
+	invalidPrvShare := NewPrivateKey()
+	valid, err := pubShares.VerifyPrvShare(ids[0], invalidPrvShare)
+	s.Require().NoError(err)
+	s.False(valid)
+
+	invalidPubShare, ok := invalidPrvShare.PublicKey().(PublicKey)
+	s.Require().True(ok)
+	valid, err = pubShares.VerifyPubShare(ids[0], &invalidPubShare)
+	s.Require().NoError(err)
+	s.False(valid)
+
+	// Test of faulty signature.
+	for idx := range members {
+		members[idx].prvShares, members[idx].pubShares = NewPrivateKeyShares(2, ids)
+		members[idx].receivedPrvShares = NewEmptyPrivateKeyShares()
+	}
+	s.sendKey(members, members)
+	hash := crypto.Keccak256Hash([]byte("👾👾👾👾👾👾"))
+	sig, err := invalidPrvShare.Sign(hash)
+	s.Require().NoError(err)
+	psig := PartialSignature(sig)
+	for _, member := range members {
+		valid = s.verifySigWithQualifyIDs(members, ids, member.id, hash, psig)
+		s.False(valid)
+	}
+
+	// Test of faulty group signature.
+	groupPubShares := make([]*PublicKeyShares, 0, len(members))
+	sigs := make([]PartialSignature, 0, len(members))
+	for _, member := range members {
+		sigs = append(sigs, s.signWithQualifyIDs(member, ids, hash))
+		groupPubShares = append(groupPubShares, member.pubShares)
+	}
+	sigs[0] = psig
+	recoverSig, err := RecoverSignature(sigs, ids)
+	s.Require().NoError(err)
+
+	pubKey := RecoverGroupPublicKey(groupPubShares)
+	s.False(pubKey.VerifySignature(hash, recoverSig))
+}
+
+func (s *DKGTestSuite) TestDKGProtocol() {
+	k := 5
+	members := []member{}
+	ids := s.genID((k + 1) * 2)
+	for _, id := range ids {
+		members = append(members, member{
+			id:                id,
+			receivedPubShares: make(map[ID]*PublicKeyShares),
+		})
+	}
+
+	for idx := range members {
+		members[idx].prvShares, members[idx].pubShares = NewPrivateKeyShares(k, ids)
+		members[idx].receivedPrvShares = NewEmptyPrivateKeyShares()
+	}
+	// Randomly select non-disqualified members.
+	nums := make([]int, len(members))
+	for i := range nums {
+		nums[i] = i
+	}
+	rand.Shuffle(len(nums), func(i, j int) {
+		nums[i], nums[j] = nums[j], nums[i]
+	})
+	nums = nums[:rand.Intn(len(members))]
+	sort.Ints(nums)
+	qualify := make([]member, 0, len(nums))
+	for _, idx := range nums {
+		qualify = append(qualify, members[idx])
+	}
+	// TODO(jimmy-dexon): Remove below line after finishing test of random select.
+	qualify = members
+	// Members are partitioned into two groups.
+	grp1, grp2 := members[:k+1], members[k+1:]
+	collectIDs := func(members []member) IDs {
+		IDs := make(IDs, 0, len(members))
+		for _, member := range members {
+			IDs = append(IDs, member.id)
+		}
+		return IDs
+	}
+	signMsg := func(
+		members []member, qualify []member, hash common.Hash) []PartialSignature {
+		ids := collectIDs(qualify)
+		sigs := make([]PartialSignature, 0, len(members))
+		for _, member := range members {
+			sig := s.signWithQualifyIDs(member, ids, hash)
+			sigs = append(sigs, sig)
+		}
+		return sigs
+	}
+	verifySig := func(
+		members []member,
+		signer []ID, sig []PartialSignature, qualify []member, hash common.Hash) bool {
+		ids := collectIDs(qualify)
+		for i := range sig {
+			if !s.verifySigWithQualifyIDs(members, ids, signer[i], hash, sig[i]) {
+				return false
+			}
+		}
+		return true
+	}
+	s.sendKey(qualify, grp1)
+	s.sendKey(qualify, grp2)
+	hash := crypto.Keccak256Hash([]byte("🛫"))
+	sig1 := signMsg(grp1, qualify, hash)
+	sig2 := signMsg(grp2, qualify, hash)
+	s.True(verifySig(members, collectIDs(grp1), sig1, qualify, hash))
+	s.True(verifySig(members, collectIDs(grp2), sig2, qualify, hash))
+	recoverSig1, err := RecoverSignature(sig1, collectIDs(grp1))
+	s.Require().NoError(err)
+	recoverSig2, err := RecoverSignature(sig2, collectIDs(grp2))
+	s.Require().NoError(err)
+	s.Equal(recoverSig1, recoverSig2)
+
+	pubShares := make([]*PublicKeyShares, 0, len(members))
+	for _, member := range members {
+		pubShares = append(pubShares, member.pubShares)
+	}
+	groupPK := RecoverGroupPublicKey(pubShares)
+	s.True(groupPK.VerifySignature(hash, recoverSig1))
+	s.True(groupPK.VerifySignature(hash, recoverSig2))
+}
+
+func TestDKG(t *testing.T) {
+	suite.Run(t, new(DKGTestSuite))
+}
diff --git a/crypto/dkg/utils.go b/crypto/dkg/utils.go
new file mode 100644
index 0000000..dddb546
--- /dev/null
+++ b/crypto/dkg/utils.go
@@ -0,0 +1,69 @@
+// Copyright 2018 The dexon-consensus-core Authors
+// This file is part of the dexon-consensus-core library.
+//
+// The dexon-consensus-core library is free software: you can redistribute it
+// and/or modify it under the terms of the GNU Lesser General Public License as
+// published by the Free Software Foundation, either version 3 of the License,
+// or (at your option) any later version.
+//
+// The dexon-consensus-core library is distributed in the hope that it will be
+// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
+// General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the dexon-consensus-core library. If not, see
+// <http://www.gnu.org/licenses/>.
+
+package dkg
+
+import (
+	"fmt"
+
+	"github.com/herumi/bls/ffi/go/bls"
+
+	"github.com/dexon-foundation/dexon-consensus-core/crypto"
+)
+
+// PartialSignature is a partial signature in DKG+TSIG protocol.
+type PartialSignature crypto.Signature
+
+var (
+	// ErrEmptySignature is reported if the signature is empty.
+	ErrEmptySignature = fmt.Errorf("invalid empty signature")
+)
+
+// RecoverSignature recovers TSIG signature.
+func RecoverSignature(sigs []PartialSignature, signerIDs IDs) (
+	crypto.Signature, error) {
+	blsSigs := make([]bls.Sign, len(sigs))
+	for i, sig := range sigs {
+		if len(sig) == 0 {
+			return nil, ErrEmptySignature
+		}
+		if err := blsSigs[i].Deserialize([]byte(sig)); err != nil {
+			return nil, err
+		}
+	}
+	var recoverSig bls.Sign
+	if err := recoverSig.Recover(blsSigs, []bls.ID(signerIDs)); err != nil {
+		return nil, err
+	}
+	return crypto.Signature(recoverSig.Serialize()), nil
+}
+
+// RecoverGroupPublicKey recovers group public key.
+func RecoverGroupPublicKey(pubShares []*PublicKeyShares) *PublicKey {
+	var pub *PublicKey
+	for _, pubShare := range pubShares {
+		pk0 := pubShare.masterPublicKey[0]
+		if pub == nil {
+			pub = &PublicKey{
+				publicKey: pk0,
+			}
+		} else {
+			pub.publicKey.Add(&pk0)
+		}
+	}
+	return pub
+}