core: add anti-complaint and nack-complaint to dkg protocol (#123)

4 files changed, 282 insertions, 35 deletions

diff --git a/core/crypto.go b/core/crypto.go
index 111f709..c95811e 100644
--- a/core/crypto.go
+++ b/core/crypto.go
@@ -151,6 +151,7 @@ func hashDKGPrivateShare(prvShare *types.DKGPrivateShare) common.Hash {
 
 	return crypto.Keccak256Hash(
 		prvShare.ProposerID.Hash[:],
+		prvShare.ReceiverID.Hash[:],
 		binaryRound,
 		prvShare.PrivateShare.Bytes(),
 	)
diff --git a/core/dkg-tsig-protocol.go b/core/dkg-tsig-protocol.go
index e1a0635..dc4e630 100644
--- a/core/dkg-tsig-protocol.go
+++ b/core/dkg-tsig-protocol.go
@@ -46,7 +46,7 @@ var (
 		"not enough of partial signatures")
 )
 
-type dkgComplaintReceiver interface {
+type dkgReceiver interface {
 	// ProposeDKGComplaint proposes a DKGComplaint.
 	ProposeDKGComplaint(complaint *types.DKGComplaint)
 
@@ -54,12 +54,15 @@ type dkgComplaintReceiver interface {
 	ProposeDKGMasterPublicKey(mpk *types.DKGMasterPublicKey)
 
 	// ProposeDKGPrivateShare propose a DKGPrivateShare.
-	ProposeDKGPrivateShare(to types.NodeID, prv *types.DKGPrivateShare)
+	ProposeDKGPrivateShare(prv *types.DKGPrivateShare)
+
+	// ProposeDKGAntiNackComplaint propose a DKGPrivateShare as an anti complaint.
+	ProposeDKGAntiNackComplaint(prv *types.DKGPrivateShare)
 }
 
 type dkgProtocol struct {
 	ID                 types.NodeID
-	recv               dkgComplaintReceiver
+	recv               dkgReceiver
 	round              uint64
 	threshold          int
 	sigToPub           SigToPubFn
@@ -68,6 +71,9 @@ type dkgProtocol struct {
 	masterPrivateShare *dkg.PrivateKeyShares
 	prvShares          *dkg.PrivateKeyShares
 	prvSharesReceived  map[types.NodeID]struct{}
+	nodeComplained     map[types.NodeID]struct{}
+	// Complaint[from][to]'s anti is saved to antiComplaint[from][to].
+	antiComplaintReceived map[types.NodeID]map[types.NodeID]struct{}
 }
 
 type dkgShareSecret struct {
@@ -96,7 +102,7 @@ func newDKGID(ID types.NodeID) dkg.ID {
 
 func newDKGProtocol(
 	ID types.NodeID,
-	recv dkgComplaintReceiver,
+	recv dkgReceiver,
 	round uint64,
 	threshold int,
 	sigToPub SigToPubFn) *dkgProtocol {
@@ -111,16 +117,18 @@ func newDKGProtocol(
 	})
 
 	return &dkgProtocol{
-		ID:                 ID,
-		recv:               recv,
-		round:              round,
-		threshold:          threshold,
-		sigToPub:           sigToPub,
-		idMap:              make(map[types.NodeID]dkg.ID),
-		mpkMap:             make(map[types.NodeID]*dkg.PublicKeyShares),
-		masterPrivateShare: prvShare,
-		prvShares:          dkg.NewEmptyPrivateKeyShares(),
-		prvSharesReceived:  make(map[types.NodeID]struct{}),
+		ID:                    ID,
+		recv:                  recv,
+		round:                 round,
+		threshold:             threshold,
+		sigToPub:              sigToPub,
+		idMap:                 make(map[types.NodeID]dkg.ID),
+		mpkMap:                make(map[types.NodeID]*dkg.PublicKeyShares),
+		masterPrivateShare:    prvShare,
+		prvShares:             dkg.NewEmptyPrivateKeyShares(),
+		prvSharesReceived:     make(map[types.NodeID]struct{}),
+		nodeComplained:        make(map[types.NodeID]struct{}),
+		antiComplaintReceived: make(map[types.NodeID]map[types.NodeID]struct{}),
 	}
 }
 
@@ -142,8 +150,9 @@ func (d *dkgProtocol) processMasterPublicKeys(
 		if !ok {
 			return ErrIDShareNotFound
 		}
-		d.recv.ProposeDKGPrivateShare(mpk.ProposerID, &types.DKGPrivateShare{
+		d.recv.ProposeDKGPrivateShare(&types.DKGPrivateShare{
 			ProposerID:   d.ID,
+			ReceiverID:   mpk.ProposerID,
 			Round:        d.round,
 			PrivateShare: *share,
 		})
@@ -167,6 +176,56 @@ func (d *dkgProtocol) proposeNackComplaints() {
 	}
 }
 
+func (d *dkgProtocol) processNackComplaints(complaints []*types.DKGComplaint) (
+	err error) {
+	for _, complaint := range complaints {
+		if !complaint.IsNack() {
+			continue
+		}
+		if complaint.PrivateShare.ProposerID != d.ID {
+			continue
+		}
+		id, exist := d.idMap[complaint.ProposerID]
+		if !exist {
+			err = ErrNotDKGParticipant
+			continue
+		}
+		share, ok := d.masterPrivateShare.Share(id)
+		if !ok {
+			err = ErrIDShareNotFound
+			continue
+		}
+		d.recv.ProposeDKGAntiNackComplaint(&types.DKGPrivateShare{
+			ProposerID:   d.ID,
+			ReceiverID:   complaint.ProposerID,
+			Round:        d.round,
+			PrivateShare: *share,
+		})
+	}
+	return
+}
+
+func (d *dkgProtocol) enforceNackComplaints(complaints []*types.DKGComplaint) {
+	for _, complaint := range complaints {
+		if !complaint.IsNack() {
+			continue
+		}
+		from := complaint.ProposerID
+		to := complaint.PrivateShare.ProposerID
+		if _, exist :=
+			d.antiComplaintReceived[from][to]; !exist {
+			d.recv.ProposeDKGComplaint(&types.DKGComplaint{
+				ProposerID: d.ID,
+				Round:      d.round,
+				PrivateShare: types.DKGPrivateShare{
+					ProposerID: to,
+					Round:      d.round,
+				},
+			})
+		}
+	}
+}
+
 func (d *dkgProtocol) sanityCheck(prvShare *types.DKGPrivateShare) error {
 	if _, exist := d.idMap[prvShare.ProposerID]; !exist {
 		return ErrNotDKGParticipant
@@ -186,7 +245,7 @@ func (d *dkgProtocol) processPrivateShare(
 	if d.round != prvShare.Round {
 		return nil
 	}
-	self, exist := d.idMap[d.ID]
+	receiverID, exist := d.idMap[prvShare.ReceiverID]
 	// This node is not a DKG participant, ignore the private share.
 	if !exist {
 		return nil
@@ -195,23 +254,37 @@ func (d *dkgProtocol) processPrivateShare(
 		return err
 	}
 	mpk := d.mpkMap[prvShare.ProposerID]
-	ok, err := mpk.VerifyPrvShare(self, &prvShare.PrivateShare)
+	ok, err := mpk.VerifyPrvShare(receiverID, &prvShare.PrivateShare)
 	if err != nil {
 		return err
 	}
-	d.prvSharesReceived[prvShare.ProposerID] = struct{}{}
+	if prvShare.ReceiverID == d.ID {
+		d.prvSharesReceived[prvShare.ProposerID] = struct{}{}
+	}
 	if !ok {
+		if _, exist := d.nodeComplained[prvShare.ProposerID]; exist {
+			return nil
+		}
 		complaint := &types.DKGComplaint{
 			ProposerID:   d.ID,
 			Round:        d.round,
 			PrivateShare: *prvShare,
 		}
+		d.nodeComplained[prvShare.ProposerID] = struct{}{}
 		d.recv.ProposeDKGComplaint(complaint)
-	} else {
+	} else if prvShare.ReceiverID == d.ID {
 		sender := d.idMap[prvShare.ProposerID]
 		if err := d.prvShares.AddShare(sender, &prvShare.PrivateShare); err != nil {
 			return err
 		}
+	} else {
+		// The prvShare is an anti complaint.
+		if _, exist := d.antiComplaintReceived[prvShare.ReceiverID]; !exist {
+			d.antiComplaintReceived[prvShare.ReceiverID] =
+				make(map[types.NodeID]struct{})
+		}
+		d.antiComplaintReceived[prvShare.ReceiverID][prvShare.ProposerID] =
+			struct{}{}
 	}
 	return nil
 }
@@ -242,11 +315,15 @@ func newDKGGroupPublicKey(
 	threshold int, sigToPub SigToPubFn) (
 	*dkgGroupPublicKey, error) {
 	// Calculate qualify members.
+	disqualifyIDs := map[types.NodeID]struct{}{}
 	complaintsByID := map[types.NodeID]int{}
 	for _, complaint := range complaints {
-		complaintsByID[complaint.PrivateShare.ProposerID]++
+		if complaint.IsNack() {
+			complaintsByID[complaint.PrivateShare.ProposerID]++
+		} else {
+			disqualifyIDs[complaint.PrivateShare.ProposerID] = struct{}{}
+		}
 	}
-	disqualifyIDs := map[types.NodeID]struct{}{}
 	for nID, num := range complaintsByID {
 		if num > threshold {
 			disqualifyIDs[nID] = struct{}{}
diff --git a/core/dkg-tsig-protocol_test.go b/core/dkg-tsig-protocol_test.go
index fc64788..2bcbe9e 100644
--- a/core/dkg-tsig-protocol_test.go
+++ b/core/dkg-tsig-protocol_test.go
@@ -41,19 +41,21 @@ type DKGTSIGProtocolTestSuite struct {
 type testDKGReceiver struct {
 	s *DKGTSIGProtocolTestSuite
 
-	prvKey     crypto.PrivateKey
-	complaints map[types.NodeID]*types.DKGComplaint
-	mpk        *types.DKGMasterPublicKey
-	prvShare   map[types.NodeID]*types.DKGPrivateShare
+	prvKey         crypto.PrivateKey
+	complaints     map[types.NodeID]*types.DKGComplaint
+	mpk            *types.DKGMasterPublicKey
+	prvShare       map[types.NodeID]*types.DKGPrivateShare
+	antiComplaints map[types.NodeID]*types.DKGPrivateShare
 }
 
 func newTestDKGReceiver(
 	s *DKGTSIGProtocolTestSuite, prvKey crypto.PrivateKey) *testDKGReceiver {
 	return &testDKGReceiver{
-		s:          s,
-		prvKey:     prvKey,
-		complaints: make(map[types.NodeID]*types.DKGComplaint),
-		prvShare:   make(map[types.NodeID]*types.DKGPrivateShare),
+		s:              s,
+		prvKey:         prvKey,
+		complaints:     make(map[types.NodeID]*types.DKGComplaint),
+		prvShare:       make(map[types.NodeID]*types.DKGPrivateShare),
+		antiComplaints: make(map[types.NodeID]*types.DKGPrivateShare),
 	}
 }
 
@@ -71,12 +73,21 @@ func (r *testDKGReceiver) ProposeDKGMasterPublicKey(
 	r.s.Require().NoError(err)
 	r.mpk = mpk
 }
+
 func (r *testDKGReceiver) ProposeDKGPrivateShare(
-	to types.NodeID, prv *types.DKGPrivateShare) {
+	prv *types.DKGPrivateShare) {
+	var err error
+	prv.Signature, err = r.prvKey.Sign(hashDKGPrivateShare(prv))
+	r.s.Require().NoError(err)
+	r.prvShare[prv.ReceiverID] = prv
+}
+
+func (r *testDKGReceiver) ProposeDKGAntiNackComplaint(
+	prv *types.DKGPrivateShare) {
 	var err error
 	prv.Signature, err = r.prvKey.Sign(hashDKGPrivateShare(prv))
 	r.s.Require().NoError(err)
-	r.prvShare[to] = prv
+	r.antiComplaints[prv.ReceiverID] = prv
 }
 
 func (s *DKGTSIGProtocolTestSuite) setupDKGParticipants(n int) {
@@ -153,6 +164,23 @@ func (s *DKGTSIGProtocolTestSuite) TestDKGTSIGProtocol() {
 		s.Require().Len(recv.complaints, 0)
 	}
 
+	for _, protocol := range protocols {
+		s.Require().NoError(protocol.processNackComplaints(
+			gov.DKGComplaints(round)))
+	}
+
+	for _, recv := range receivers {
+		s.Require().Len(recv.antiComplaints, 0)
+	}
+
+	for _, protocol := range protocols {
+		protocol.enforceNackComplaints(gov.DKGComplaints(round))
+	}
+
+	for _, recv := range receivers {
+		s.Require().Len(recv.complaints, 0)
+	}
+
 	// DKG is fininished.
 	gpk, err := newDKGGroupPublicKey(round,
 		gov.DKGMasterPublicKeys(round), gov.DKGComplaints(round),
@@ -234,6 +262,7 @@ func (s *DKGTSIGProtocolTestSuite) TestNackComplaint() {
 
 	for _, recv := range receivers {
 		complaint, exist := recv.complaints[byzantineID]
+		s.True(complaint.IsNack())
 		s.Require().True(exist)
 		s.True(verifyDKGComplaintSignature(complaint, eth.SigToPub))
 	}
@@ -267,26 +296,145 @@ func (s *DKGTSIGProtocolTestSuite) TestComplaint() {
 	// These messages are not valid.
 	err = protocol.processPrivateShare(&types.DKGPrivateShare{
 		ProposerID: types.NodeID{Hash: common.NewRandomHash()},
+		ReceiverID: targetID,
 		Round:      round,
 	})
 	s.Error(ErrNotDKGParticipant, err)
 	err = protocol.processPrivateShare(&types.DKGPrivateShare{
 		ProposerID: byzantineID,
+		ReceiverID: targetID,
 		Round:      round,
 	})
 	s.Error(ErrIncorrectPrivateShareSignature, err)
 
 	// Byzantine node is sending incorrect private share.
-	err = protocol.processPrivateShare(receivers[byzantineID].prvShare[byzantineID])
-	s.NoError(err)
+	receivers[byzantineID].ProposeDKGPrivateShare(&types.DKGPrivateShare{
+		ProposerID: byzantineID,
+		ReceiverID: targetID,
+		Round:      round,
+	})
+	invalidShare := receivers[byzantineID].prvShare[targetID]
+	s.Require().NoError(protocol.processPrivateShare(invalidShare))
 	s.Require().Len(receiver.complaints, 1)
 	complaint, exist := receiver.complaints[byzantineID]
 	s.True(exist)
 	s.Equal(byzantineID, complaint.PrivateShare.ProposerID)
+
+	// Sending the incorrect private share again should not complain.
+	delete(receiver.complaints, byzantineID)
+	s.Require().NoError(protocol.processPrivateShare(invalidShare))
+	s.Len(receiver.complaints, 0)
 }
 
-// TestQualifyIDs tests if there is a id with t+1 complaints, it should not be
-// in the qualifyIDs.
+// TestAntiComplaint tests if a nack complaint is received,
+// create an anti complaint.
+func (s *DKGTSIGProtocolTestSuite) TestAntiComplaint() {
+	k := 3
+	n := 10
+	round := uint64(1)
+	gov, err := test.NewGovernance(5, 100)
+	s.Require().NoError(err)
+
+	receivers, protocols := s.newProtocols(k, n, round)
+
+	byzantineID := s.nIDs[0]
+	targetID := s.nIDs[1]
+	thirdPerson := s.nIDs[2]
+
+	for _, receiver := range receivers {
+		gov.AddDKGMasterPublicKey(receiver.mpk)
+	}
+
+	for _, protocol := range protocols {
+		s.Require().NoError(
+			protocol.processMasterPublicKeys(gov.DKGMasterPublicKeys(round)))
+	}
+
+	// Creating Nack complaint.
+	protocols[targetID].proposeNackComplaints()
+	protocols[thirdPerson].proposeNackComplaints()
+	complaint, exist := receivers[targetID].complaints[byzantineID]
+	s.Require().True(exist)
+	s.Require().True(complaint.IsNack())
+	s.Require().Equal(byzantineID, complaint.PrivateShare.ProposerID)
+
+	complaint2, exist := receivers[thirdPerson].complaints[byzantineID]
+	s.Require().True(exist)
+	s.Require().True(complaint2.IsNack())
+	s.Require().Equal(byzantineID, complaint2.PrivateShare.ProposerID)
+
+	// Creating an anti-nack complaint.
+	err = protocols[byzantineID].processNackComplaints(
+		[]*types.DKGComplaint{complaint})
+	s.Require().NoError(err)
+	s.Require().Len(receivers[byzantineID].antiComplaints, 1)
+	antiComplaint, exist := receivers[byzantineID].antiComplaints[targetID]
+	s.Require().True(exist)
+	s.Require().Equal(targetID, antiComplaint.ReceiverID)
+
+	// The anti-complaint should be successfully verified by all others.
+	receivers[targetID].complaints = make(map[types.NodeID]*types.DKGComplaint)
+	s.Require().NoError(protocols[targetID].processPrivateShare(antiComplaint))
+	s.Len(receivers[targetID].complaints, 0)
+
+	receivers[thirdPerson].complaints = make(map[types.NodeID]*types.DKGComplaint)
+	s.Require().NoError(protocols[thirdPerson].processPrivateShare(antiComplaint))
+	s.Len(receivers[thirdPerson].complaints, 0)
+}
+
+// TestEncorceNackComplaint tests if the nack complaint is enforced properly.
+func (s *DKGTSIGProtocolTestSuite) TestEncorceNackComplaint() {
+	k := 3
+	n := 10
+	round := uint64(1)
+	gov, err := test.NewGovernance(5, 100)
+	s.Require().NoError(err)
+
+	receivers, protocols := s.newProtocols(k, n, round)
+
+	byzantineID := s.nIDs[0]
+	targetID := s.nIDs[1]
+	thirdPerson := s.nIDs[2]
+
+	for _, receiver := range receivers {
+		gov.AddDKGMasterPublicKey(receiver.mpk)
+	}
+
+	for _, protocol := range protocols {
+		s.Require().NoError(
+			protocol.processMasterPublicKeys(gov.DKGMasterPublicKeys(round)))
+	}
+
+	// Creating nack complaint.
+	protocols[targetID].proposeNackComplaints()
+	complaint, exist := receivers[targetID].complaints[byzantineID]
+	s.Require().True(exist)
+	s.Require().True(complaint.IsNack())
+	s.Require().Equal(byzantineID, complaint.PrivateShare.ProposerID)
+
+	// Encorce nack complaint.
+	protocols[thirdPerson].enforceNackComplaints([]*types.DKGComplaint{complaint})
+	complaint2, exist := receivers[thirdPerson].complaints[byzantineID]
+	s.Require().True(exist)
+	s.Require().True(complaint2.IsNack())
+	s.Require().Equal(byzantineID, complaint2.PrivateShare.ProposerID)
+
+	// Received valid private share, do not enforce nack complaint.
+	delete(receivers[thirdPerson].complaints, byzantineID)
+	err = protocols[byzantineID].processNackComplaints(
+		[]*types.DKGComplaint{complaint})
+	s.Require().NoError(err)
+	antiComplaint, exist := receivers[byzantineID].antiComplaints[targetID]
+	s.Require().True(exist)
+	s.Require().Equal(targetID, antiComplaint.ReceiverID)
+	s.Require().NoError(protocols[thirdPerson].processPrivateShare(antiComplaint))
+	protocols[thirdPerson].enforceNackComplaints([]*types.DKGComplaint{complaint})
+	_, exist = receivers[thirdPerson].complaints[byzantineID]
+	s.Require().False(exist)
+}
+
+// TestQualifyIDs tests if there is a id with t+1 nack complaints
+// or a complaint, it should not be in the qualifyIDs.
 func (s *DKGTSIGProtocolTestSuite) TestQualifyIDs() {
 	k := 3
 	n := 10
@@ -302,6 +450,7 @@ func (s *DKGTSIGProtocolTestSuite) TestQualifyIDs() {
 		gov.AddDKGMasterPublicKey(receiver.mpk)
 	}
 
+	// Test for nack complaints.
 	complaints := make([]*types.DKGComplaint, k+1)
 	for i := range complaints {
 		nID := s.nIDs[i]
@@ -313,6 +462,7 @@ func (s *DKGTSIGProtocolTestSuite) TestQualifyIDs() {
 				Round:      round,
 			},
 		}
+		s.Require().True(complaints[i].IsNack())
 	}
 
 	gpk, err := newDKGGroupPublicKey(round,
@@ -331,6 +481,19 @@ func (s *DKGTSIGProtocolTestSuite) TestQualifyIDs() {
 	)
 	s.Require().NoError(err)
 	s.Require().Len(gpk2.qualifyIDs, n)
+
+	// Test for complaint.
+	complaints[0].PrivateShare.Signature = crypto.Signature{0}
+	s.Require().False(complaints[0].IsNack())
+	gpk3, err := newDKGGroupPublicKey(round,
+		gov.DKGMasterPublicKeys(round), complaints[:1],
+		k, eth.SigToPub,
+	)
+	s.Require().NoError(err)
+	s.Require().Len(gpk3.qualifyIDs, n-1)
+	for _, id := range gpk3.qualifyIDs {
+		s.NotEqual(id, byzantineID)
+	}
 }
 
 // TestPartialSignature tests if tsigProtocol can handle incorrect partial
diff --git a/core/types/dkg.go b/core/types/dkg.go
index 78f4da6..d70bf98 100644
--- a/core/types/dkg.go
+++ b/core/types/dkg.go
@@ -25,6 +25,7 @@ import (
 // DKGPrivateShare describe a secret share in DKG protocol.
 type DKGPrivateShare struct {
 	ProposerID   NodeID           `json:"proposer_id"`
+	ReceiverID   NodeID           `json:"receiver_id"`
 	Round        uint64           `json:"round"`
 	PrivateShare dkg.PrivateKey   `json:"private_share"`
 	Signature    crypto.Signature `json:"signature"`
@@ -54,3 +55,8 @@ type DKGPartialSignature struct {
 	PartialSignature dkg.PartialSignature `json:"partial_signature"`
 	Signature        crypto.Signature     `json:"signature"`
 }
+
+// IsNack returns true if it's a nack complaint in DKG protocol.
+func (c *DKGComplaint) IsNack() bool {
+	return len(c.PrivateShare.Signature) == 0
+}