test: check causality (#372)

4 files changed, 101 insertions, 7 deletions

diff --git a/core/test/app.go b/core/test/app.go
index d26784e..3dcbd2e 100644
--- a/core/test/app.go
+++ b/core/test/app.go
@@ -54,6 +54,21 @@ var (
 	// and delivered are different.
 	ErrMismatchTotalOrderingAndDelivered = fmt.Errorf(
 		"mismatch total ordering and delivered sequence")
+	// ErrAckingBlockNotDelivered means the delivered sequence not forming a
+	// DAG.
+	ErrAckingBlockNotDelivered = fmt.Errorf("acking block not delivered")
+)
+
+// This definition is copied from core package.
+const (
+	// TotalOrderingModeError returns mode error.
+	TotalOrderingModeError uint32 = iota
+	// TotalOrderingModeNormal returns mode normal.
+	TotalOrderingModeNormal
+	// TotalOrderingModeEarly returns mode early.
+	TotalOrderingModeEarly
+	// TotalOrderingModeFlush returns mode flush.
+	TotalOrderingModeFlush
 )
 
 // AppTotalOrderRecord caches information when this application received
@@ -233,7 +248,8 @@ func (app *App) Verify() error {
 	expectHeight := uint64(1)
 	prevTime := time.Time{}
 	for _, h := range app.DeliverSequence {
-		if _, exists := app.Confirmed[h]; !exists {
+		_, exists := app.Confirmed[h]
+		if !exists {
 			return ErrDeliveredBlockNotConfirmed
 		}
 		rec, exists := app.Delivered[h]
@@ -247,13 +263,40 @@ func (app *App) Verify() error {
 			return ErrConsensusTimestampOutOfOrder
 		}
 		prevTime = rec.ConsensusTime
-
 		// Make sure the consensus height is incremental.
 		if expectHeight != rec.ConsensusHeight {
 			return ErrConsensusHeightOutOfOrder
 		}
 		expectHeight++
 	}
+	// Check causality.
+	revealedDAG := make(map[common.Hash]struct{})
+	for _, toDeliver := range app.TotalOrdered {
+		for _, h := range toDeliver.BlockHashes {
+			b, exists := app.Confirmed[h]
+			if !exists {
+				return ErrDeliveredBlockNotConfirmed
+			}
+			for _, ack := range b.Acks {
+				if _, ackingBlockExists := revealedDAG[ack]; !ackingBlockExists {
+					return ErrAckingBlockNotDelivered
+				}
+			}
+			if toDeliver.Mode == TotalOrderingModeFlush {
+				// For blocks delivered by flushing, the acking relations would
+				// exist in one deliver set, however, only later block would
+				// ack previous block, not backward.
+				revealedDAG[h] = struct{}{}
+			}
+		}
+		// For blocks not delivered by flushing, the acking relations only exist
+		// between deliver sets.
+		if toDeliver.Mode != TotalOrderingModeFlush {
+			for _, h := range toDeliver.BlockHashes {
+				revealedDAG[h] = struct{}{}
+			}
+		}
+	}
 	// Make sure the order of delivered and total ordering are the same by
 	// comparing the concated string.
 	app.totalOrderedLock.RLock()
diff --git a/core/test/app_test.go b/core/test/app_test.go
index 61672a4..80580a3 100644
--- a/core/test/app_test.go
+++ b/core/test/app_test.go
@@ -179,6 +179,21 @@ func (s *AppTestSuite) TestVerify() {
 		time.Duration(len(app6.DeliverSequence))*time.Second),
 		uint64(len(app6.DeliverSequence)+2))
 	req.Equal(ErrConsensusHeightOutOfOrder, app6.Verify())
+	// Test the acking block doesn't delivered.
+	app7 := NewApp(nil)
+	// Patch a block's acks.
+	b7 := &types.Block{
+		Hash: common.NewRandomHash(),
+		Acks: common.NewSortedHashes(common.Hashes{common.NewRandomHash()}),
+	}
+	app7.BlockConfirmed(*b7)
+	app7.TotalOrderingDelivered(
+		common.Hashes{b7.Hash}, core.TotalOrderingModeNormal)
+	app7.BlockDelivered(b7.Hash, types.Position{}, types.FinalizationResult{
+		Timestamp: time.Now(),
+		Height:    1,
+	})
+	req.Equal(ErrAckingBlockNotDelivered, app7.Verify())
 }
 
 func TestApp(t *testing.T) {
diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go
index 78b609b..d71cd62 100644
--- a/core/test/blocks-generator_test.go
+++ b/core/test/blocks-generator_test.go
@@ -220,7 +220,7 @@ func (s *BlocksGeneratorTestSuite) TestConcateBlocksFromRounds() {
 	gen := NewBlocksGenerator(&BlocksGeneratorConfig{
 		NumChains:            4,
 		MinBlockTimeInterval: 250 * time.Millisecond,
-	}, nil, stableRandomHash)
+	}, MaxAckingCountGenerator(4), stableRandomHash)
 	req.NoError(gen.Generate(
 		0,
 		genesisTime,
@@ -233,7 +233,7 @@ func (s *BlocksGeneratorTestSuite) TestConcateBlocksFromRounds() {
 	gen = NewBlocksGenerator(&BlocksGeneratorConfig{
 		NumChains:            10,
 		MinBlockTimeInterval: 250 * time.Millisecond,
-	}, nil, stableRandomHash)
+	}, MaxAckingCountGenerator(10), stableRandomHash)
 	req.NoError(gen.Generate(
 		1,
 		genesisTime.Add(10*time.Second),
@@ -246,7 +246,7 @@ func (s *BlocksGeneratorTestSuite) TestConcateBlocksFromRounds() {
 	gen = NewBlocksGenerator(&BlocksGeneratorConfig{
 		NumChains:            7,
 		MinBlockTimeInterval: 250 * time.Millisecond,
-	}, nil, stableRandomHash)
+	}, MaxAckingCountGenerator(7), stableRandomHash)
 	req.NoError(gen.Generate(
 		2,
 		genesisTime.Add(20*time.Second),
diff --git a/core/total-ordering_test.go b/core/total-ordering_test.go
index 5cee0b0..511228e 100644
--- a/core/total-ordering_test.go
+++ b/core/total-ordering_test.go
@@ -55,6 +55,7 @@ func (s *TotalOrderingTestSuite) performOneRun(
 	to *totalOrdering, revealer test.BlockRevealer) (revealed, ordered string) {
 	revealer.Reset()
 	curRound := uint64(0)
+	revealedDAG := make(map[common.Hash]struct{})
 	for {
 		// Reveal next block.
 		b, err := revealer.NextBlock()
@@ -67,13 +68,30 @@ func (s *TotalOrderingTestSuite) performOneRun(
 		s.Require().NoError(err)
 		revealed += b.Hash.String() + ","
 		// Perform total ordering.
-		blocks, _, err := to.processBlock(&b)
+		blocks, mode, err := to.processBlock(&b)
 		s.Require().NoError(err)
 		for _, b := range blocks {
 			ordered += b.Hash.String() + ","
 			// Make sure the round ID is increasing, and no interleave.
 			s.Require().True(b.Position.Round >= curRound)
 			curRound = b.Position.Round
+			// Make sure all acking blocks are already delivered.
+			for _, ack := range b.Acks {
+				s.Require().Contains(revealedDAG, ack)
+			}
+			if mode == TotalOrderingModeFlush {
+				// For blocks delivered by flushing, the acking relations would
+				// exist in one deliver set, however, only later block would
+				// ack previous block, not backward.
+				revealedDAG[b.Hash] = struct{}{}
+			}
+		}
+		// For blocks not delivered by flushing, the acking relations only exist
+		// between deliver sets.
+		if mode != TotalOrderingModeFlush {
+			for _, b := range blocks {
+				revealedDAG[b.Hash] = struct{}{}
+			}
 		}
 	}
 	return
@@ -1300,13 +1318,22 @@ func (s *TotalOrderingTestSuite) TestSyncWithConfigChange() {
 			NumChains:     uint32(20),
 			RoundInterval: roundInterval,
 		},
+		// Sometimes all generated blocks would be delivered, thus the total
+		// ordering module would proceed to next round. We need to prepare
+		// one additional configuration for that possibility.
+		&types.Config{
+			K:             1,
+			PhiRatio:      0.7,
+			NumChains:     uint32(20),
+			RoundInterval: roundInterval,
+		},
 	}
 
 	blocks := []*types.Block{}
 	dbInst, err := db.NewMemBackedDB()
 	req.NoError(err)
 
-	for i, cfg := range configs {
+	for i, cfg := range configs[:len(configs)-1] {
 		gen := test.NewBlocksGenerator(&test.BlocksGeneratorConfig{
 			NumChains:            cfg.NumChains,
 			MinBlockTimeInterval: 250 * time.Millisecond,
@@ -1395,6 +1422,15 @@ func (s *TotalOrderingTestSuite) TestSyncWithConfigChange() {
 	}
 }
 
+func (s *TotalOrderingTestSuite) TestModeDefinition() {
+	// Make sure the copied deliver mode definition is identical between
+	// core and test package.
+	s.Require().Equal(TotalOrderingModeError, test.TotalOrderingModeError)
+	s.Require().Equal(TotalOrderingModeNormal, test.TotalOrderingModeNormal)
+	s.Require().Equal(TotalOrderingModeEarly, test.TotalOrderingModeEarly)
+	s.Require().Equal(TotalOrderingModeFlush, test.TotalOrderingModeFlush)
+}
+
 func TestTotalOrdering(t *testing.T) {
 	suite.Run(t, new(TotalOrderingTestSuite))
 }