From 441e7c082608f274a920eff64bc83ab27ab52ccb Mon Sep 17 00:00:00 2001 From: Jimmy Hu Date: Fri, 21 Sep 2018 10:07:10 +0800 Subject: core: add anti-complaint and nack-complaint to dkg protocol (#123) --- core/crypto.go | 1 + core/dkg-tsig-protocol.go | 119 ++++++++++++++++++++----- core/dkg-tsig-protocol_test.go | 191 ++++++++++++++++++++++++++++++++++++++--- core/types/dkg.go | 6 ++ 4 files changed, 282 insertions(+), 35 deletions(-) (limited to 'core') 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 +} -- cgit v1.2.3