core: lattice sync (#257)

4 files changed, 138 insertions, 11 deletions

diff --git a/core/test/app.go b/core/test/app.go
index ba949b3..546c9e5 100644
--- a/core/test/app.go
+++ b/core/test/app.go
@@ -29,7 +29,7 @@ import (
 var (
 	// ErrEmptyDeliverSequence means there is no delivery event in this App
 	// instance.
-	ErrEmptyDeliverSequence = fmt.Errorf("emptry deliver sequence")
+	ErrEmptyDeliverSequence = fmt.Errorf("empty deliver sequence")
 	// ErrMismatchBlockHashSequence means the delivering sequence between two App
 	// instances are different.
 	ErrMismatchBlockHashSequence = fmt.Errorf("mismatch block hash sequence")
@@ -43,6 +43,10 @@ var (
 	// consensus timestamp older than previous block.
 	ErrConsensusTimestampOutOfOrder = fmt.Errorf(
 		"consensus timestamp out of order")
+	// ErrConsensusHeightOutOfOrder means the later delivered block has
+	// consensus height not equal to height of previous block plus one.
+	ErrConsensusHeightOutOfOrder = fmt.Errorf(
+		"consensus height out of order")
 	// ErrDeliveredBlockNotAcked means some block delivered (confirmed) but
 	// not strongly acked.
 	ErrDeliveredBlockNotAcked = fmt.Errorf("delivered block not acked")
@@ -69,8 +73,9 @@ type AppTotalOrderRecord struct {
 // AppDeliveredRecord caches information when this application received
 // a block delivered notification.
 type AppDeliveredRecord struct {
-	ConsensusTime time.Time
-	When          time.Time
+	ConsensusTime   time.Time
+	ConsensusHeight uint64
+	When            time.Time
 }
 
 // App implements Application interface for testing purpose.
@@ -151,8 +156,9 @@ func (app *App) BlockDelivered(
 	defer app.deliveredLock.Unlock()
 
 	app.Delivered[blockHash] = &AppDeliveredRecord{
-		ConsensusTime: result.Timestamp,
-		When:          time.Now().UTC(),
+		ConsensusTime:   result.Timestamp,
+		ConsensusHeight: result.Height,
+		When:            time.Now().UTC(),
 	}
 	app.DeliverSequence = append(app.DeliverSequence, blockHash)
 }
@@ -201,6 +207,7 @@ func (app *App) Verify() error {
 	app.ackedLock.RLock()
 	defer app.ackedLock.RUnlock()
 
+	expectHeight := uint64(1)
 	prevTime := time.Time{}
 	for _, h := range app.DeliverSequence {
 		// Make sure delivered block is strongly acked.
@@ -218,6 +225,12 @@ func (app *App) Verify() error {
 			return ErrConsensusTimestampOutOfOrder
 		}
 		prevTime = rec.ConsensusTime
+
+		// Make sure the consensus height is incremental.
+		if expectHeight != rec.ConsensusHeight {
+			return ErrConsensusHeightOutOfOrder
+		}
+		expectHeight++
 	}
 	// Make sure the order of delivered and total ordering are the same by
 	// comparing the concated string.
diff --git a/core/test/app_test.go b/core/test/app_test.go
index 8f2aae5..823bde0 100644
--- a/core/test/app_test.go
+++ b/core/test/app_test.go
@@ -75,14 +75,16 @@ func (s *AppTestSuite) deliverBlockWithTimeFromSequenceLength(
 	app *App, hash common.Hash) {
 
 	s.deliverBlock(app, hash, time.Time{}.Add(
-		time.Duration(len(app.DeliverSequence))*time.Second))
+		time.Duration(len(app.DeliverSequence))*time.Second),
+		uint64(len(app.DeliverSequence)+1))
 }
 
 func (s *AppTestSuite) deliverBlock(
-	app *App, hash common.Hash, timestamp time.Time) {
+	app *App, hash common.Hash, timestamp time.Time, height uint64) {
 
 	app.BlockDelivered(hash, types.FinalizationResult{
 		Timestamp: timestamp,
+		Height:    height,
 	})
 }
 
@@ -113,7 +115,8 @@ func (s *AppTestSuite) TestCompare() {
 	wrongTime := time.Time{}.Add(
 		time.Duration(len(app3.DeliverSequence)) * time.Second)
 	wrongTime = wrongTime.Add(1 * time.Second)
-	s.deliverBlock(app3, s.to3.BlockHashes[0], wrongTime)
+	s.deliverBlock(app3, s.to3.BlockHashes[0], wrongTime,
+		uint64(len(app3.DeliverSequence)+1))
 	req.Equal(ErrMismatchConsensusTime, app1.Compare(app3))
 	req.Equal(ErrMismatchConsensusTime, app3.Compare(app1))
 	// An App without any delivered blocks.
@@ -130,9 +133,10 @@ func (s *AppTestSuite) TestVerify() {
 	s.setupAppByTotalOrderDeliver(app1, s.to1)
 	s.setupAppByTotalOrderDeliver(app1, s.to2)
 	s.setupAppByTotalOrderDeliver(app1, s.to3)
-	req.Nil(app1.Verify())
+	req.NoError(app1.Verify())
 	// A delivered block without strongly ack
-	s.deliverBlock(app1, common.NewRandomHash(), time.Time{})
+	s.deliverBlock(app1, common.NewRandomHash(), time.Time{},
+		uint64(len(app1.DeliverSequence)))
 	req.Equal(ErrDeliveredBlockNotAcked, app1.Verify())
 	// The consensus time is out of order.
 	app2 := NewApp()
@@ -141,7 +145,8 @@ func (s *AppTestSuite) TestVerify() {
 		app2.StronglyAcked(h)
 	}
 	app2.TotalOrderingDelivered(s.to2.BlockHashes, s.to2.Mode)
-	s.deliverBlock(app2, s.to2.BlockHashes[0], time.Time{})
+	s.deliverBlock(app2, s.to2.BlockHashes[0], time.Time{},
+		uint64(len(app2.DeliverSequence)+1))
 	req.Equal(ErrConsensusTimestampOutOfOrder, app2.Verify())
 	// A delivered block is not found in total ordering delivers.
 	app3 := NewApp()
@@ -164,6 +169,17 @@ func (s *AppTestSuite) TestVerify() {
 	// Witness ack on unknown block.
 	app5 := NewApp()
 	s.setupAppByTotalOrderDeliver(app5, s.to1)
+	// The conensus height is out of order.
+	app6 := NewApp()
+	s.setupAppByTotalOrderDeliver(app6, s.to1)
+	for _, h := range s.to2.BlockHashes {
+		app6.StronglyAcked(h)
+	}
+	app6.TotalOrderingDelivered(s.to2.BlockHashes, s.to2.Mode)
+	s.deliverBlock(app6, s.to2.BlockHashes[0], time.Time{}.Add(
+		time.Duration(len(app6.DeliverSequence))*time.Second),
+		uint64(len(app6.DeliverSequence)+2))
+	req.Equal(ErrConsensusHeightOutOfOrder, app6.Verify())
 }
 
 func TestApp(t *testing.T) {
diff --git a/core/test/revealer.go b/core/test/revealer.go
index 80d2a30..c9d82ce 100644
--- a/core/test/revealer.go
+++ b/core/test/revealer.go
@@ -1,6 +1,23 @@
 // 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/>.
+
+// 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,
@@ -205,3 +222,61 @@ func (r *RandomRevealer) Reset() {
 	}
 	r.remains = hashes
 }
+
+// RandomTipRevealer implements Revealer interface, which would load
+// all blocks from blockdb, and randomly pick one chain's tip to reveal.
+type RandomTipRevealer struct {
+	chainsBlock    []map[uint64]*types.Block
+	chainTip       []uint64
+	chainRevealSeq []uint32
+	revealed       int
+	randGen        *rand.Rand
+}
+
+// NewRandomTipRevealer constructs RandomTipRevealer.
+func NewRandomTipRevealer(
+	iter blockdb.BlockIterator) (r *RandomTipRevealer, err error) {
+
+	blocks, err := loadAllBlocks(iter)
+	if err != nil {
+		return
+	}
+	r = &RandomTipRevealer{
+		randGen: rand.New(rand.NewSource(time.Now().UnixNano())),
+	}
+	for _, b := range blocks {
+		for b.Position.ChainID >= uint32(len(r.chainsBlock)) {
+			r.chainsBlock = append(r.chainsBlock, make(map[uint64]*types.Block))
+			r.chainTip = append(r.chainTip, 0)
+		}
+		r.chainsBlock[b.Position.ChainID][b.Position.Height] = b
+		r.chainRevealSeq = append(r.chainRevealSeq, b.Position.ChainID)
+	}
+	r.Reset()
+	return
+}
+
+// Next implements Revealer.Next method, which would reveal blocks randomly.
+func (r *RandomTipRevealer) Next() (types.Block, error) {
+	if len(r.chainRevealSeq) == r.revealed {
+		return types.Block{}, blockdb.ErrIterationFinished
+	}
+
+	picked := r.chainRevealSeq[r.revealed]
+	r.revealed++
+	block := r.chainsBlock[picked][r.chainTip[picked]]
+	r.chainTip[picked]++
+	return *block, nil
+}
+
+// Reset implement Revealer.Reset method, which would reset revealing.
+func (r *RandomTipRevealer) Reset() {
+	r.revealed = 0
+	r.randGen.Shuffle(len(r.chainRevealSeq), func(i, j int) {
+		r.chainRevealSeq[i], r.chainRevealSeq[j] =
+			r.chainRevealSeq[j], r.chainRevealSeq[i]
+	})
+	for i := range r.chainTip {
+		r.chainTip[i] = 0
+	}
+}
diff --git a/core/test/revealer_test.go b/core/test/revealer_test.go
index 8bb46bc..4945d62 100644
--- a/core/test/revealer_test.go
+++ b/core/test/revealer_test.go
@@ -135,6 +135,29 @@ func (s *RevealerTestSuite) TestRandomDAGReveal() {
 	s.baseTest(revealer, 10, checkFunc)
 }
 
+func (s *RevealerTestSuite) TestRandomTipReveal() {
+	// This test case would make sure we could at least generate
+	// two different revealing sequence when revealing more than
+	// 10 times.
+	iter, err := s.db.GetAll()
+	s.Require().Nil(err)
+	revealer, err := NewRandomTipRevealer(iter)
+	s.Require().Nil(err)
+
+	checkFunc := func(b *types.Block, revealed map[common.Hash]struct{}) {
+		// Make sure the revealer won't reveal the same block twice.
+		_, alreadyRevealed := revealed[b.Hash]
+		s.False(alreadyRevealed)
+		// Make sure the parent is already revealed.
+		if b.Position.Height == 0 {
+			return
+		}
+		_, alreadyRevealed = revealed[b.ParentHash]
+		s.True(alreadyRevealed)
+	}
+	s.baseTest(revealer, 10, checkFunc)
+}
+
 func TestRevealer(t *testing.T) {
 	suite.Run(t, new(RevealerTestSuite))
 }