diff options
| -rw-r--r-- | GNUmakefile | 2 | ||||
| -rwxr-xr-x | bin/install_dkg_dep.sh | 3 | ||||
| -rw-r--r-- | crypto/dkg/constant.go | 26 | ||||
| -rw-r--r-- | crypto/dkg/dkg.go | 273 | ||||
| -rw-r--r-- | crypto/dkg/dkg_test.go | 265 | ||||
| -rw-r--r-- | crypto/dkg/utils.go | 69 |
6 files changed, 636 insertions, 2 deletions
diff --git a/GNUmakefile b/GNUmakefile index 1152468..bbda25f 100644 --- a/GNUmakefile +++ b/GNUmakefile @@ -70,7 +70,7 @@ vet: test: @for pkg in `go list ./... | grep -v 'vendor'`; do \ - if ! go test -race $$pkg; then \ + if ! env LD_LIBRARY_PATH=`pwd`/lib DYLD_LIBRARY_PATH=`pwd`/lib go test -race $$pkg; then \ echo 'Some test failed, abort'; \ exit 1; \ fi; \ diff --git a/bin/install_dkg_dep.sh b/bin/install_dkg_dep.sh index eb41460..7b6463f 100755 --- a/bin/install_dkg_dep.sh +++ b/bin/install_dkg_dep.sh @@ -19,3 +19,6 @@ if [ ! -d .dep/dkg ]; then fi cp -r .dep/dkg/* \ vendor/github.com/herumi +mkdir lib > /dev/null +cd lib +ln -s ../vendor/github.com/herumi/bls/lib/* . 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 +} |