core: tune total ordering performance (#81)

- Replace map with slice
   Compared to slice, accessing to map is slower and
   the memory usage is inefficient.

9 files changed, 592 insertions, 443 deletions

diff --git a/core/consensus.go b/core/consensus.go
index 36cd57e..6c841bf 100644
--- a/core/consensus.go
+++ b/core/consensus.go
@@ -84,10 +84,14 @@ func NewConsensus(
 	}
 
 	// Setup sequencer by information returned from Governace.
+	var validators types.ValidatorIDs
+	for vID := range validatorSet {
+		validators = append(validators, vID)
+	}
 	to := newTotalOrdering(
 		uint64(gov.GetTotalOrderingK()),
 		uint64(float32(len(validatorSet)-1)*gov.GetPhiRatio()+1),
-		uint64(len(validatorSet)))
+		validators)
 
 	return &Consensus{
 		rbModule: rb,
diff --git a/core/reliable-broadcast_test.go b/core/reliable-broadcast_test.go
index c6e9400..28edda7 100644
--- a/core/reliable-broadcast_test.go
+++ b/core/reliable-broadcast_test.go
@@ -514,7 +514,8 @@ func (s *ReliableBroadcastTest) TestRandomlyGeneratedBlocks() {
 		}
 	}()
 	gen := test.NewBlocksGenerator(nil, hashBlock)
-	s.Require().Nil(gen.Generate(validatorCount, blockCount, nil, db))
+	_, err = gen.Generate(validatorCount, blockCount, nil, db)
+	s.Require().Nil(err)
 	iter, err := db.GetAll()
 	s.Require().Nil(err)
 	// Setup a revealer that would reveal blocks randomly.
diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go
index 3cd97ee..b05d08f 100644
--- a/core/test/blocks-generator.go
+++ b/core/test/blocks-generator.go
@@ -236,7 +236,8 @@ func (gen *BlocksGenerator) Generate(
 	validatorCount int,
 	blockCount int,
 	ackingCountGenerator func() int,
-	writer blockdb.Writer) (err error) {
+	writer blockdb.Writer) (
+	validators types.ValidatorIDs, err error) {
 
 	if ackingCountGenerator == nil {
 		ackingCountGenerator = normalAckingCountGenerator(
@@ -244,7 +245,7 @@ func (gen *BlocksGenerator) Generate(
 			float64(validatorCount/2),
 			float64(validatorCount/4+1))
 	}
-	validators := []types.ValidatorID{}
+	validators = types.ValidatorIDs{}
 	for i := 0; i < validatorCount; i++ {
 		validators = append(
 			validators, types.ValidatorID{Hash: common.NewRandomHash()})
diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go
index 43e994f..5c85fbd 100644
--- a/core/test/blocks-generator_test.go
+++ b/core/test/blocks-generator_test.go
@@ -39,9 +39,10 @@ func (s *BlocksGeneratorTestCase) TestGenerate() {
 	db, err := blockdb.NewMemBackedBlockDB()
 	s.Require().Nil(err)
 
-	err = gen.Generate(
+	validators, err := gen.Generate(
 		validatorCount, blockCount, nil, db)
 	s.Require().Nil(err)
+	s.Require().Len(validators, validatorCount)
 
 	// Load all blocks in that database for further checking.
 	iter, err := db.GetAll()
@@ -114,8 +115,10 @@ func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() {
 	// Generate with 0 acks.
 	db, err := blockdb.NewMemBackedBlockDB()
 	req.Nil(err)
-	req.Nil(gen.Generate(
-		validatorCount, blockCount, MaxAckingCountGenerator(0), db))
+	validators, err := gen.Generate(
+		validatorCount, blockCount, MaxAckingCountGenerator(0), db)
+	req.Nil(err)
+	req.Len(validators, validatorCount)
 	// Load blocks to check their acking count.
 	iter, err := db.GetAll()
 	req.Nil(err)
@@ -134,9 +137,11 @@ func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() {
 	// Generate with acks as many as possible.
 	db, err = blockdb.NewMemBackedBlockDB()
 	req.Nil(err)
-	req.Nil(gen.Generate(
+	validators, err = gen.Generate(
 		validatorCount, blockCount, MaxAckingCountGenerator(
-			validatorCount), db))
+			validatorCount), db)
+	req.Nil(err)
+	req.Len(validators, validatorCount)
 	// Load blocks to verify the average acking count.
 	totalAckingCount := 0
 	totalBlockCount := 0
diff --git a/core/test/revealer_test.go b/core/test/revealer_test.go
index 8087136..032cab3 100644
--- a/core/test/revealer_test.go
+++ b/core/test/revealer_test.go
@@ -45,9 +45,10 @@ func (s *RevealerTestSuite) SetupSuite() {
 
 	// Randomly generate blocks.
 	gen := NewBlocksGenerator(nil, stableRandomHash)
-	err = gen.Generate(
+	validators, err := gen.Generate(
 		validatorCount, blockCount, nil, s.db)
 	s.Require().Nil(err)
+	s.Require().Len(validators, validatorCount)
 
 	// Cache the count of total generated block.
 	iter, err := s.db.GetAll()
diff --git a/core/total-ordering.go b/core/total-ordering.go
index c7270c5..1edccdf 100644
--- a/core/total-ordering.go
+++ b/core/total-ordering.go
@@ -31,22 +31,45 @@ const (
 	infinity uint64 = math.MaxUint64
 )
 
-// ErrNotValidDAG would be reported when block subbmitted to totalOrdering
-// didn't form a DAG.
-var ErrNotValidDAG = fmt.Errorf("not a valid dag")
+var (
+	// ErrNotValidDAG would be reported when block subbmitted to totalOrdering
+	// didn't form a DAG.
+	ErrNotValidDAG = fmt.Errorf("not a valid dag")
+	// ErrValidatorNotRecognized means the validator is unknown to this module.
+	ErrValidatorNotRecognized = fmt.Errorf("validator not recognized")
+)
 
 // totalOrderinWinRecord caches which validators this candidate
 // wins another one based on their height vector.
-type totalOrderingWinRecord map[types.ValidatorID]struct{}
+type totalOrderingWinRecord struct {
+	wins  []int8
+	count uint
+}
+
+func (rec *totalOrderingWinRecord) reset() {
+	rec.count = 0
+	for idx := range rec.wins {
+		rec.wins[idx] = 0
+	}
+}
+
+func newTotalOrderingWinRecord(validatorCount int) (
+	rec *totalOrderingWinRecord) {
+
+	rec = &totalOrderingWinRecord{}
+	rec.reset()
+	rec.wins = make([]int8, validatorCount)
+	return
+}
 
 // grade implements the 'grade' potential function described in white paper.
-func (rec totalOrderingWinRecord) grade(
+func (rec *totalOrderingWinRecord) grade(
 	validatorCount, phi uint64,
 	globalAnsLength uint64) int {
 
-	if uint64(len(rec)) >= phi {
+	if uint64(rec.count) >= phi {
 		return 1
-	} else if uint64(len(rec)) < phi-validatorCount+globalAnsLength {
+	} else if uint64(rec.count) < phi-validatorCount+globalAnsLength {
 		return 0
 	} else {
 		return -1
@@ -66,38 +89,44 @@ type totalOrderingHeightRecord struct{ minHeight, count uint64 }
 // However, to reuse a map, we have no easy way to erase its content but
 // iterating its keys and delete corresponding values.
 type totalOrderingObjectCache struct {
-	ackedStatus         []map[types.ValidatorID]*totalOrderingHeightRecord
-	winRecordContainers []map[common.Hash]totalOrderingWinRecord
-	heightVectors       []map[types.ValidatorID]uint64
+	ackedStatus         [][]*totalOrderingHeightRecord
+	heightVectors       [][]uint64
+	winRecordContainers [][]*totalOrderingWinRecord
 	ackedVectors        []map[common.Hash]struct{}
 	winRecordPool       sync.Pool
+	validatorCount      int
 }
 
 // newTotalOrderingObjectCache constructs an totalOrderingObjectCache
 // instance.
-func newTotalOrderingObjectCache() *totalOrderingObjectCache {
+func newTotalOrderingObjectCache(validatorCount int) *totalOrderingObjectCache {
 	return &totalOrderingObjectCache{
 		winRecordPool: sync.Pool{
 			New: func() interface{} {
-				return make(totalOrderingWinRecord)
+				return newTotalOrderingWinRecord(validatorCount)
 			},
 		},
+		validatorCount: validatorCount,
 	}
 }
 
 // requestAckedStatus requests a structure to record acking status of one
 // candidate (or a global view of acking status of pending set).
 func (cache *totalOrderingObjectCache) requestAckedStatus() (
-	acked map[types.ValidatorID]*totalOrderingHeightRecord) {
+	acked []*totalOrderingHeightRecord) {
 
 	if len(cache.ackedStatus) == 0 {
-		acked = make(map[types.ValidatorID]*totalOrderingHeightRecord)
+		acked = make([]*totalOrderingHeightRecord, cache.validatorCount)
+		for idx := range acked {
+			acked[idx] = &totalOrderingHeightRecord{count: 0}
+		}
 	} else {
 		acked, cache.ackedStatus =
 			cache.ackedStatus[len(cache.ackedStatus)-1],
 			cache.ackedStatus[:len(cache.ackedStatus)-1]
-		for k := range acked {
-			delete(acked, k)
+		// Reset acked status.
+		for idx := range acked {
+			acked[idx].count = 0
 		}
 	}
 	return
@@ -105,43 +134,44 @@ func (cache *totalOrderingObjectCache) requestAckedStatus() (
 
 // recycleAckedStatys recycles the structure to record acking status.
 func (cache *totalOrderingObjectCache) recycleAckedStatus(
-	acked map[types.ValidatorID]*totalOrderingHeightRecord) {
+	acked []*totalOrderingHeightRecord) {
 
 	cache.ackedStatus = append(cache.ackedStatus, acked)
 }
 
 // requestWinRecord requests an totalOrderingWinRecord instance.
 func (cache *totalOrderingObjectCache) requestWinRecord() (
-	win totalOrderingWinRecord) {
+	win *totalOrderingWinRecord) {
 
-	win = cache.winRecordPool.Get().(totalOrderingWinRecord)
-	for k := range win {
-		delete(win, k)
-	}
+	win = cache.winRecordPool.Get().(*totalOrderingWinRecord)
+	win.reset()
 	return
 }
 
 // recycleWinRecord recycles an totalOrderingWinRecord instance.
 func (cache *totalOrderingObjectCache) recycleWinRecord(
-	win totalOrderingWinRecord) {
+	win *totalOrderingWinRecord) {
 
+	if win == nil {
+		return
+	}
 	cache.winRecordPool.Put(win)
 }
 
 // requestHeightVector requests a structure to record acking heights
 // of one candidate.
 func (cache *totalOrderingObjectCache) requestHeightVector() (
-	hv map[types.ValidatorID]uint64) {
+	hv []uint64) {
 
 	if len(cache.heightVectors) == 0 {
-		hv = make(map[types.ValidatorID]uint64)
+		hv = make([]uint64, cache.validatorCount)
 	} else {
 		hv, cache.heightVectors =
 			cache.heightVectors[len(cache.heightVectors)-1],
 			cache.heightVectors[:len(cache.heightVectors)-1]
-		for k := range hv {
-			delete(hv, k)
-		}
+	}
+	for idx := range hv {
+		hv[idx] = infinity
 	}
 	return
 }
@@ -149,23 +179,23 @@ func (cache *totalOrderingObjectCache) requestHeightVector() (
 // recycleHeightVector recycles an instance to record acking heights
 // of one candidate.
 func (cache *totalOrderingObjectCache) recycleHeightVector(
-	hv map[types.ValidatorID]uint64) {
+	hv []uint64) {
 
 	cache.heightVectors = append(cache.heightVectors, hv)
 }
 
 // requestWinRecordContainer requests a map of totalOrderingWinRecord.
 func (cache *totalOrderingObjectCache) requestWinRecordContainer() (
-	con map[common.Hash]totalOrderingWinRecord) {
+	con []*totalOrderingWinRecord) {
 
 	if len(cache.winRecordContainers) == 0 {
-		con = make(map[common.Hash]totalOrderingWinRecord)
+		con = make([]*totalOrderingWinRecord, cache.validatorCount)
 	} else {
 		con, cache.winRecordContainers =
 			cache.winRecordContainers[len(cache.winRecordContainers)-1],
 			cache.winRecordContainers[:len(cache.winRecordContainers)-1]
-		for k := range con {
-			delete(con, k)
+		for idx := range con {
+			con[idx] = nil
 		}
 	}
 	return
@@ -173,7 +203,7 @@ func (cache *totalOrderingObjectCache) requestWinRecordContainer() (
 
 // recycleWinRecordContainer recycles a map of totalOrderingWinRecord.
 func (cache *totalOrderingObjectCache) recycleWinRecordContainer(
-	con map[common.Hash]totalOrderingWinRecord) {
+	con []*totalOrderingWinRecord) {
 
 	cache.winRecordContainers = append(cache.winRecordContainers, con)
 }
@@ -221,26 +251,29 @@ func (cache *totalOrderingObjectCache) recycleAckedVector(
 //   - count of acking blocks from that proposer
 //  to repsent the acking status for block A.
 type totalOrderingCandidateInfo struct {
-	ackedStatus        map[types.ValidatorID]*totalOrderingHeightRecord
-	cachedHeightVector map[types.ValidatorID]uint64
-	winRecords         map[common.Hash]totalOrderingWinRecord
+	ackedStatus        []*totalOrderingHeightRecord
+	cachedHeightVector []uint64
+	winRecords         []*totalOrderingWinRecord
+	hash               common.Hash
 }
 
 // newTotalOrderingCandidateInfo constructs an totalOrderingCandidateInfo
 // instance.
 func newTotalOrderingCandidateInfo(
+	candidateHash common.Hash,
 	objCache *totalOrderingObjectCache) *totalOrderingCandidateInfo {
 
 	return &totalOrderingCandidateInfo{
 		ackedStatus: objCache.requestAckedStatus(),
 		winRecords:  objCache.requestWinRecordContainer(),
+		hash:        candidateHash,
 	}
 }
 
 // clean clear information related to another candidate, which should be called
 // when that candidate is selected as deliver set.
-func (v *totalOrderingCandidateInfo) clean(otherCandidate common.Hash) {
-	delete(v.winRecords, otherCandidate)
+func (v *totalOrderingCandidateInfo) clean(otherCandidateIndex int) {
+	v.winRecords[otherCandidateIndex] = nil
 }
 
 // recycle objects for later usage, this eases the loading of
@@ -262,13 +295,13 @@ func (v *totalOrderingCandidateInfo) recycle(
 
 // addBlock would update totalOrderingCandidateInfo, it's caller's duty
 // to make sure the input block acutally acking the target block.
-func (v *totalOrderingCandidateInfo) addBlock(b *types.Block) (err error) {
-	rec, exists := v.ackedStatus[b.ProposerID]
-	if !exists {
-		v.ackedStatus[b.ProposerID] = &totalOrderingHeightRecord{
-			minHeight: b.Height,
-			count:     1,
-		}
+func (v *totalOrderingCandidateInfo) addBlock(
+	b *types.Block, proposerIndex int) (err error) {
+
+	rec := v.ackedStatus[proposerIndex]
+	if rec.count == 0 {
+		rec.minHeight = b.Height
+		rec.count = 1
 	} else {
 		if b.Height < rec.minHeight {
 			err = ErrNotValidDAG
@@ -294,17 +327,15 @@ func (v *totalOrderingCandidateInfo) getAckingNodeSetLength(
 	global *totalOrderingCandidateInfo,
 	k uint64) (count uint64) {
 
-	var (
-		rec    *totalOrderingHeightRecord
-		exists bool
-	)
-
-	for vID, gRec := range global.ackedStatus {
-		rec, exists = v.ackedStatus[vID]
-		if !exists {
+	var rec *totalOrderingHeightRecord
+	for idx, gRec := range global.ackedStatus {
+		if gRec.count == 0 {
+			continue
+		}
+		rec = v.ackedStatus[idx]
+		if rec.count == 0 {
 			continue
 		}
-
 		// This line would check if these two ranges would overlap:
 		//  - (global minimum height + k, infinity)
 		//  - (local minimum height, local minimum height + count - 1)
@@ -322,13 +353,12 @@ func (v *totalOrderingCandidateInfo) getAckingNodeSetLength(
 func (v *totalOrderingCandidateInfo) updateAckingHeightVector(
 	global *totalOrderingCandidateInfo,
 	k uint64,
-	dirtyValidators types.ValidatorIDs,
+	dirtyValidatorIndexes []int,
 	objCache *totalOrderingObjectCache) {
 
 	var (
-		vID       types.ValidatorID
+		idx       int
 		gRec, rec *totalOrderingHeightRecord
-		exists    bool
 	)
 
 	// The reason not to merge the two loops is the iteration over map
@@ -339,42 +369,39 @@ func (v *totalOrderingCandidateInfo) updateAckingHeightVector(
 	if v.cachedHeightVector == nil {
 		// Generate height vector from scratch.
 		v.cachedHeightVector = objCache.requestHeightVector()
-		for vID, gRec = range global.ackedStatus {
+		for idx, gRec = range global.ackedStatus {
 			if gRec.count <= k {
-				delete(v.cachedHeightVector, vID)
 				continue
 			}
-			rec, exists = v.ackedStatus[vID]
-			if !exists {
-				v.cachedHeightVector[vID] = infinity
+			rec = v.ackedStatus[idx]
+			if rec.count == 0 {
+				v.cachedHeightVector[idx] = infinity
 			} else if rec.minHeight <= gRec.minHeight+k {
 				// This check is sufficient to make sure the block height:
 				//
 				//   gRec.minHeight + k
 				//
 				// would be included in this totalOrderingCandidateInfo.
-				v.cachedHeightVector[vID] = gRec.minHeight + k
+				v.cachedHeightVector[idx] = gRec.minHeight + k
 			} else {
-				v.cachedHeightVector[vID] = infinity
+				v.cachedHeightVector[idx] = infinity
 			}
 		}
 	} else {
 		// Return the cached one, only update dirty fields.
-		for _, vID = range dirtyValidators {
-			gRec, exists = global.ackedStatus[vID]
-			if !exists {
+		for _, idx = range dirtyValidatorIndexes {
+			gRec = global.ackedStatus[idx]
+			if gRec.count == 0 || gRec.count <= k {
+				v.cachedHeightVector[idx] = infinity
 				continue
 			}
-			rec, exists = v.ackedStatus[vID]
-			if gRec.count <= k {
-				delete(v.cachedHeightVector, vID)
-				continue
-			} else if !exists {
-				v.cachedHeightVector[vID] = infinity
+			rec = v.ackedStatus[idx]
+			if rec.count == 0 {
+				v.cachedHeightVector[idx] = infinity
 			} else if rec.minHeight <= gRec.minHeight+k {
-				v.cachedHeightVector[vID] = gRec.minHeight + k
+				v.cachedHeightVector[idx] = gRec.minHeight + k
 			} else {
-				v.cachedHeightVector[vID] = infinity
+				v.cachedHeightVector[idx] = infinity
 			}
 		}
 	}
@@ -383,15 +410,14 @@ func (v *totalOrderingCandidateInfo) updateAckingHeightVector(
 
 // updateWinRecord setup win records between two candidates.
 func (v *totalOrderingCandidateInfo) updateWinRecord(
-	otherCandidate common.Hash,
+	otherCandidateIndex int,
 	other *totalOrderingCandidateInfo,
-	dirtyValidators types.ValidatorIDs,
+	dirtyValidatorIndexes []int,
 	objCache *totalOrderingObjectCache) {
 
 	var (
-		vID        types.ValidatorID
-		hTo, hFrom uint64
-		exists     bool
+		idx    int
+		height uint64
 	)
 
 	// The reason not to merge the two loops is the iteration over map
@@ -399,35 +425,38 @@ func (v *totalOrderingCandidateInfo) updateWinRecord(
 	// validators is cheaper.
 	// TODO(mission): merge the code in this if/else if add a function won't
 	//                affect the performance.
-	win, exists := v.winRecords[otherCandidate]
-	if !exists {
+	win := v.winRecords[otherCandidateIndex]
+	if win == nil {
 		win = objCache.requestWinRecord()
-		v.winRecords[otherCandidate] = win
-		for vID, hFrom = range v.cachedHeightVector {
-			hTo, exists = other.cachedHeightVector[vID]
-			if !exists {
+		v.winRecords[otherCandidateIndex] = win
+		for idx, height = range v.cachedHeightVector {
+			if height == infinity {
 				continue
 			}
-			if hFrom != infinity && hTo == infinity {
-				win[vID] = struct{}{}
+			if other.cachedHeightVector[idx] == infinity {
+				win.wins[idx] = 1
+				win.count++
 			}
 		}
 	} else {
-		for _, vID = range dirtyValidators {
-			hFrom, exists = v.cachedHeightVector[vID]
-			if !exists {
-				delete(win, vID)
-				return
-			}
-			hTo, exists = other.cachedHeightVector[vID]
-			if !exists {
-				delete(win, vID)
-				return
+		for _, idx = range dirtyValidatorIndexes {
+			if v.cachedHeightVector[idx] == infinity {
+				if win.wins[idx] == 1 {
+					win.wins[idx] = 0
+					win.count--
+				}
+				continue
 			}
-			if hFrom != infinity && hTo == infinity {
-				win[vID] = struct{}{}
+			if other.cachedHeightVector[idx] == infinity {
+				if win.wins[idx] == 0 {
+					win.wins[idx] = 1
+					win.count++
+				}
 			} else {
-				delete(win, vID)
+				if win.wins[idx] == 1 {
+					win.wins[idx] = 0
+					win.count--
+				}
 			}
 		}
 	}
@@ -438,22 +467,26 @@ type totalOrderingGlobalVector struct {
 	// blocks stores all blocks grouped by their proposers and
 	// sorted by their block height.
 	//
-	// TODO: the way we use this slice would make it reallocate frequently.
-	blocks map[types.ValidatorID][]*types.Block
+	// TODO(mission): the way we use this slice would make it reallocate frequently.
+	blocks [][]*types.Block
 
 	// cachedCandidateInfo is an totalOrderingCandidateInfo instance,
 	// which is just used for actual candidates to calculate height vector.
 	cachedCandidateInfo *totalOrderingCandidateInfo
 }
 
-func newTotalOrderingGlobalVector() *totalOrderingGlobalVector {
+func newTotalOrderingGlobalVector(
+	validatorCount int) *totalOrderingGlobalVector {
+
 	return &totalOrderingGlobalVector{
-		blocks: make(map[types.ValidatorID][]*types.Block),
+		blocks: make([][]*types.Block, validatorCount),
 	}
 }
 
-func (global *totalOrderingGlobalVector) addBlock(b *types.Block) (err error) {
-	blocksFromProposer := global.blocks[b.ProposerID]
+func (global *totalOrderingGlobalVector) addBlock(
+	b *types.Block, proposerIndex int) (err error) {
+
+	blocksFromProposer := global.blocks[proposerIndex]
 	if len(blocksFromProposer) > 0 {
 		lastBlock := blocksFromProposer[len(blocksFromProposer)-1]
 		if b.Height-lastBlock.Height != 1 {
@@ -461,44 +494,43 @@ func (global *totalOrderingGlobalVector) addBlock(b *types.Block) (err error) {
 			return
 		}
 	}
-	global.blocks[b.ProposerID] = append(blocksFromProposer, b)
+	global.blocks[proposerIndex] = append(blocksFromProposer, b)
 	return
 }
 
 // updateCandidateInfo udpate cached candidate info.
 func (global *totalOrderingGlobalVector) updateCandidateInfo(
-	dirtyValidators types.ValidatorIDs, objCache *totalOrderingObjectCache) {
+	dirtyValidatorIndexes []int, objCache *totalOrderingObjectCache) {
 
 	var (
-		vID    types.ValidatorID
+		idx    int
 		blocks []*types.Block
 		info   *totalOrderingCandidateInfo
+		rec    *totalOrderingHeightRecord
 	)
 
 	if global.cachedCandidateInfo == nil {
-		info = newTotalOrderingCandidateInfo(objCache)
-		for vID, blocks = range global.blocks {
+		info = newTotalOrderingCandidateInfo(common.Hash{}, objCache)
+		for idx, blocks = range global.blocks {
 			if len(blocks) == 0 {
 				continue
 			}
-			info.ackedStatus[vID] = &totalOrderingHeightRecord{
-				minHeight: blocks[0].Height,
-				count:     uint64(len(blocks)),
-			}
+			rec = info.ackedStatus[idx]
+			rec.minHeight = blocks[0].Height
+			rec.count = uint64(len(blocks))
 		}
 		global.cachedCandidateInfo = info
 	} else {
 		info = global.cachedCandidateInfo
-		for _, vID = range dirtyValidators {
-			blocks = global.blocks[vID]
+		for _, idx = range dirtyValidatorIndexes {
+			blocks = global.blocks[idx]
 			if len(blocks) == 0 {
-				delete(info.ackedStatus, vID)
+				info.ackedStatus[idx].count = 0
 				continue
 			}
-			info.ackedStatus[vID] = &totalOrderingHeightRecord{
-				minHeight: blocks[0].Height,
-				count:     uint64(len(blocks)),
-			}
+			rec = info.ackedStatus[idx]
+			rec.minHeight = blocks[0].Height
+			rec.count = uint64(len(blocks))
 		}
 	}
 	return
@@ -531,31 +563,55 @@ type totalOrdering struct {
 
 	// candidates caches result of potential function during generating
 	// preceding sets.
-	candidates map[common.Hash]*totalOrderingCandidateInfo
+	candidates []*totalOrderingCandidateInfo
 
 	// acked cache the 'block A acked by block B' relation by
 	// keeping a record in acked[A.Hash][B.Hash]
 	acked map[common.Hash]map[common.Hash]struct{}
 
-	// dirtyValidators records which validatorID that should be updated for
-	// all cached status (win record, acking status).
-	dirtyValidators types.ValidatorIDs
+	// dirtyValidatorIndexes records which validatorID that should be updated
+	// for all cached status (win record, acking status).
+	dirtyValidatorIndexes []int
 
 	// objCache caches allocated objects, like map.
 	objCache *totalOrderingObjectCache
+
+	// validatorIndexMapping maps validatorID to an unique integer, which
+	// could be used as slice index.
+	validatorIndexMapping map[types.ValidatorID]int
+
+	// candidateIndexMapping maps block hashes of candidates to an unique
+	// integer, which could be used as slice index.
+	candidateIndexMapping map[common.Hash]int
+
+	// allocatedCandidateSlotIndexes records all used slot indexes in
+	// candidates slice.
+	allocatedCandidateSlotIndexes []int
 }
 
-func newTotalOrdering(k, phi, validatorCount uint64) *totalOrdering {
+func newTotalOrdering(
+	k, phi uint64, validators types.ValidatorIDs) *totalOrdering {
+
+	// Setup validatorID to index mapping.
+	validatorIndexMapping := make(map[types.ValidatorID]int)
+	for _, vID := range validators {
+		validatorIndexMapping[vID] = len(validatorIndexMapping)
+	}
+	validatorCount := len(validators)
 	return &totalOrdering{
-		candidates:      make(map[common.Hash]*totalOrderingCandidateInfo),
-		pendings:        make(map[common.Hash]*types.Block),
-		k:               k,
-		phi:             phi,
-		validatorCount:  validatorCount,
-		globalVector:    newTotalOrderingGlobalVector(),
-		dirtyValidators: make(types.ValidatorIDs, 0, int(validatorCount)),
-		acked:           make(map[common.Hash]map[common.Hash]struct{}),
-		objCache:        newTotalOrderingObjectCache(),
+		pendings:              make(map[common.Hash]*types.Block),
+		k:                     k,
+		phi:                   phi,
+		validatorCount:        uint64(validatorCount),
+		globalVector:          newTotalOrderingGlobalVector(validatorCount),
+		dirtyValidatorIndexes: make([]int, 0, validatorCount),
+		acked:                 make(map[common.Hash]map[common.Hash]struct{}),
+		objCache:              newTotalOrderingObjectCache(validatorCount),
+		validatorIndexMapping: validatorIndexMapping,
+		candidateIndexMapping: make(map[common.Hash]int),
+		candidates: make(
+			[]*totalOrderingCandidateInfo, validatorCount),
+		allocatedCandidateSlotIndexes: make([]int, 0, validatorCount),
 	}
 }
 
@@ -601,32 +657,41 @@ func (to *totalOrdering) clean(h common.Hash) {
 	to.objCache.recycleAckedVector(to.acked[h])
 	delete(to.acked, h)
 	delete(to.pendings, h)
-	to.candidates[h].recycle(to.objCache)
-	delete(to.candidates, h)
-	for _, info := range to.candidates {
-		info.clean(h)
+	slotIndex := to.candidateIndexMapping[h]
+	to.candidates[slotIndex].recycle(to.objCache)
+	to.candidates[slotIndex] = nil
+	delete(to.candidateIndexMapping, h)
+	// Remove this candidate from allocated slot indexes.
+	to.allocatedCandidateSlotIndexes = removeFromSortedIntSlice(
+		to.allocatedCandidateSlotIndexes, slotIndex)
+	// Clear records of this candidate from other candidates.
+	for _, idx := range to.allocatedCandidateSlotIndexes {
+		to.candidates[idx].clean(slotIndex)
 	}
 }
 
 // updateVectors is a helper function to update all cached vectors.
-func (to *totalOrdering) updateVectors(b *types.Block) (err error) {
+func (to *totalOrdering) updateVectors(
+	b *types.Block, proposerIndex int) (err error) {
 	var (
-		candidate common.Hash
-		info      *totalOrderingCandidateInfo
-		acked     bool
+		candidateHash  common.Hash
+		candidateIndex int
+		acked          bool
 	)
 	// Update global height vector
-	err = to.globalVector.addBlock(b)
+	err = to.globalVector.addBlock(b, proposerIndex)
 	if err != nil {
 		return
 	}
 
 	// Update acking status of candidates.
-	for candidate, info = range to.candidates {
-		if _, acked = to.acked[candidate][b.Hash]; !acked {
+	for candidateHash, candidateIndex = range to.candidateIndexMapping {
+		if _, acked = to.acked[candidateHash][b.Hash]; !acked {
 			continue
 		}
-		if err = info.addBlock(b); err != nil {
+		if err = to.candidates[candidateIndex].addBlock(
+			b, proposerIndex); err != nil {
+
 			return
 		}
 	}
@@ -636,20 +701,32 @@ func (to *totalOrdering) updateVectors(b *types.Block) (err error) {
 // prepareCandidate is a helper function to
 // build totalOrderingCandidateInfo for new candidate.
 func (to *totalOrdering) prepareCandidate(
-	candidate *types.Block) (info *totalOrderingCandidateInfo) {
+	candidate *types.Block, proposerIndex int) {
+
+	var (
+		info = newTotalOrderingCandidateInfo(
+			candidate.Hash, to.objCache)
+	)
+
+	to.candidates[proposerIndex] = info
+	to.candidateIndexMapping[candidate.Hash] = proposerIndex
+	// Add index to slot to allocated list, make sure the modified list sorted.
+	to.allocatedCandidateSlotIndexes = append(
+		to.allocatedCandidateSlotIndexes, proposerIndex)
+	sort.Ints(to.allocatedCandidateSlotIndexes)
 
-	info = newTotalOrderingCandidateInfo(to.objCache)
-	info.ackedStatus[candidate.ProposerID] = &totalOrderingHeightRecord{
+	info.ackedStatus[proposerIndex] = &totalOrderingHeightRecord{
 		minHeight: candidate.Height,
-		count:     uint64(len(to.globalVector.blocks[candidate.ProposerID])),
+		count:     uint64(len(to.globalVector.blocks[proposerIndex])),
 	}
 	ackedsForCandidate, exists := to.acked[candidate.Hash]
 	if !exists {
 		// This candidate is acked by nobody.
 		return
 	}
-	for vID, blocks := range to.globalVector.blocks {
-		if vID == candidate.ProposerID {
+	var rec *totalOrderingHeightRecord
+	for idx, blocks := range to.globalVector.blocks {
+		if idx == proposerIndex {
 			continue
 		}
 		for i, b := range blocks {
@@ -658,10 +735,9 @@ func (to *totalOrdering) prepareCandidate(
 			}
 			// If this block acks this candidate, all newer blocks
 			// from the same validator also 'indirect' acks it.
-			info.ackedStatus[vID] = &totalOrderingHeightRecord{
-				minHeight: b.Height,
-				count:     uint64(len(blocks) - i),
-			}
+			rec = info.ackedStatus[idx]
+			rec.minHeight = b.Height
+			rec.count = uint64(len(blocks) - i)
 			break
 		}
 	}
@@ -685,32 +761,40 @@ func (to *totalOrdering) output(precedings map[common.Hash]struct{}) (ret []*typ
 	for p := range precedings {
 		// Remove the first element from corresponding blockVector.
 		b := to.pendings[p]
-		to.globalVector.blocks[b.ProposerID] =
-			to.globalVector.blocks[b.ProposerID][1:]
+		// TODO(mission): This way to use slice makes it reallocate frequently.
+		blockProposerIndex := to.validatorIndexMapping[b.ProposerID]
+		to.globalVector.blocks[blockProposerIndex] =
+			to.globalVector.blocks[blockProposerIndex][1:]
 		ret = append(ret, b)
 
 		// Remove block relations.
 		to.clean(p)
-		to.dirtyValidators = append(to.dirtyValidators, b.ProposerID)
+		to.dirtyValidatorIndexes = append(
+			to.dirtyValidatorIndexes, blockProposerIndex)
 	}
 	sort.Sort(types.ByHash(ret))
 
 	// Find new candidates from tip of globalVector of each validator.
 	// The complexity here is O(N^2logN).
+	// TODO(mission): only those tips that acking some blocks in
+	//                the devliered set should be checked. This
+	//                improvment related to the latency introduced by K.
 	for _, blocks := range to.globalVector.blocks {
 		if len(blocks) == 0 {
 			continue
 		}
 		tip := blocks[0]
 		if _, alreadyCandidate :=
-			to.candidates[tip.Hash]; alreadyCandidate {
+			to.candidateIndexMapping[tip.Hash]; alreadyCandidate {
 			continue
 		}
 		if !to.isAckOnlyPrecedings(tip) {
 			continue
 		}
 		// Build totalOrderingCandidateInfo for new candidate.
-		to.candidates[tip.Hash] = to.prepareCandidate(tip)
+		to.prepareCandidate(
+			tip,
+			to.validatorIndexMapping[tip.ProposerID])
 	}
 	return ret
 }
@@ -722,52 +806,61 @@ func (to *totalOrdering) generateDeliverSet() (
 	delivered map[common.Hash]struct{}, early bool) {
 
 	var (
-		candidate, otherCandidate common.Hash
-		info, otherInfo           *totalOrderingCandidateInfo
-		precedings                = make(map[common.Hash]struct{})
+		candidateIndex, otherCandidateIndex int
+		info, otherInfo                     *totalOrderingCandidateInfo
+		precedings                          = make(map[int]struct{})
 	)
 
-	to.globalVector.updateCandidateInfo(to.dirtyValidators, to.objCache)
+	to.globalVector.updateCandidateInfo(to.dirtyValidatorIndexes, to.objCache)
 	globalInfo := to.globalVector.cachedCandidateInfo
-	for _, info = range to.candidates {
-		info.updateAckingHeightVector(
-			globalInfo, to.k, to.dirtyValidators, to.objCache)
+	for _, candidateIndex = range to.allocatedCandidateSlotIndexes {
+		to.candidates[candidateIndex].updateAckingHeightVector(
+			globalInfo, to.k, to.dirtyValidatorIndexes, to.objCache)
 	}
 
 	// Update winning records for each candidate.
+	// TODO(mission): It's not reasonable to
+	//                request one routine for each candidate, the context
+	//                switch rate would be high.
 	var wg sync.WaitGroup
-	wg.Add(len(to.candidates))
-	for candidate, info := range to.candidates {
-		go func(can common.Hash, canInfo *totalOrderingCandidateInfo) {
-			for otherCandidate, otherInfo := range to.candidates {
-				if can == otherCandidate {
+	wg.Add(len(to.allocatedCandidateSlotIndexes))
+	for _, candidateIndex := range to.allocatedCandidateSlotIndexes {
+		info = to.candidates[candidateIndex]
+		go func(can int, canInfo *totalOrderingCandidateInfo) {
+			for _, otherCandidateIndex := range to.allocatedCandidateSlotIndexes {
+				if can == otherCandidateIndex {
 					continue
 				}
 				canInfo.updateWinRecord(
-					otherCandidate, otherInfo, to.dirtyValidators, to.objCache)
+					otherCandidateIndex,
+					to.candidates[otherCandidateIndex],
+					to.dirtyValidatorIndexes,
+					to.objCache)
 			}
 			wg.Done()
-		}(candidate, info)
+		}(candidateIndex, info)
 	}
 	wg.Wait()
 
 	// Reset dirty validators.
-	to.dirtyValidators = to.dirtyValidators[:0]
+	to.dirtyValidatorIndexes = to.dirtyValidatorIndexes[:0]
 
 	globalAnsLength := globalInfo.getAckingNodeSetLength(globalInfo, to.k)
 CheckNextCandidateLoop:
-	for candidate = range to.candidates {
-		for otherCandidate, otherInfo = range to.candidates {
-			if candidate == otherCandidate {
+	for _, candidateIndex = range to.allocatedCandidateSlotIndexes {
+		info = to.candidates[candidateIndex]
+		for _, otherCandidateIndex = range to.allocatedCandidateSlotIndexes {
+			if candidateIndex == otherCandidateIndex {
 				continue
 			}
-			if otherInfo.winRecords[candidate].grade(
+			otherInfo = to.candidates[otherCandidateIndex]
+			if otherInfo.winRecords[candidateIndex].grade(
 				to.validatorCount, to.phi, globalAnsLength) != 0 {
 
 				continue CheckNextCandidateLoop
 			}
 		}
-		precedings[candidate] = struct{}{}
+		precedings[candidateIndex] = struct{}{}
 	}
 	if len(precedings) == 0 {
 		return
@@ -777,15 +870,15 @@ CheckNextCandidateLoop:
 	internal := func() bool {
 		var (
 			isPreceding, beaten bool
-			p                   common.Hash
+			p                   int
 		)
-		for candidate = range to.candidates {
-			if _, isPreceding = precedings[candidate]; isPreceding {
+		for _, candidateIndex = range to.allocatedCandidateSlotIndexes {
+			if _, isPreceding = precedings[candidateIndex]; isPreceding {
 				continue
 			}
 			beaten = false
 			for p = range precedings {
-				if beaten = to.candidates[p].winRecords[candidate].grade(
+				if beaten = to.candidates[p].winRecords[candidateIndex].grade(
 					to.validatorCount, to.phi, globalAnsLength) == 1; beaten {
 					break
 				}
@@ -802,15 +895,13 @@ CheckNextCandidateLoop:
 	// to lead the whole preceding set.
 	checkAHV := func() bool {
 		var (
-			height uint64
-			p      common.Hash
-			count  uint64
-			status *totalOrderingCandidateInfo
+			height, count uint64
+			p             int
 		)
 		for p = range precedings {
 			count = 0
-			status = to.candidates[p]
-			for _, height = range status.cachedHeightVector {
+			info = to.candidates[p]
+			for _, height = range info.cachedHeightVector {
 				if height != infinity {
 					count++
 					if count > to.phi {
@@ -853,7 +944,10 @@ CheckNextCandidateLoop:
 			return
 		}
 	}
-	delivered = precedings
+	delivered = make(map[common.Hash]struct{})
+	for p := range precedings {
+		delivered[to.candidates[p].hash] = struct{}{}
+	}
 	return
 }
 
@@ -864,16 +958,23 @@ func (to *totalOrdering) processBlock(b *types.Block) (
 	//       That means, all its acking blocks are during/after
 	//       total ordering stage.
 
+	blockProposerIndex, exists := to.validatorIndexMapping[b.ProposerID]
+	if !exists {
+		err = ErrValidatorNotRecognized
+		return
+	}
+
 	to.pendings[b.Hash] = b
 	to.buildBlockRelation(b)
-	if err = to.updateVectors(b); err != nil {
+	if err = to.updateVectors(b, blockProposerIndex); err != nil {
 		return
 	}
 	if to.isAckOnlyPrecedings(b) {
-		to.candidates[b.Hash] = to.prepareCandidate(b)
+		to.prepareCandidate(b, blockProposerIndex)
 	}
 	// Mark the proposer of incoming block as dirty.
-	to.dirtyValidators = append(to.dirtyValidators, b.ProposerID)
+	to.dirtyValidatorIndexes = append(
+		to.dirtyValidatorIndexes, blockProposerIndex)
 	hashes, early := to.generateDeliverSet()
 
 	// output precedings
diff --git a/core/total-ordering_test.go b/core/total-ordering_test.go
index 9fb14e7..ae6675e 100644
--- a/core/total-ordering_test.go
+++ b/core/total-ordering_test.go
@@ -66,25 +66,14 @@ func (s *TotalOrderingTestSuite) checkNotInWorkingSet(
 	s.NotContains(to.acked, b.Hash)
 }
 
-func (s *TotalOrderingTestSuite) prepareDirtyValidators(
-	validators []types.ValidatorID) types.ValidatorIDs {
-
-	dirties := types.ValidatorIDs{}
-	for _, vID := range validators {
-		dirties = append(dirties, vID)
-	}
-	return dirties
-}
-
 func (s *TotalOrderingTestSuite) TestBlockRelation() {
 	// This test case would verify if 'acking' and 'acked'
 	// accumulated correctly.
 	//
 	// The DAG used below is:
 	//  A <- B <- C
-
-	vID := types.ValidatorID{Hash: common.NewRandomHash()}
-
+	validators := test.GenerateRandomValidatorIDs(5)
+	vID := validators[0]
 	blockA := s.genGenesisBlock(vID, map[common.Hash]struct{}{})
 	blockB := &types.Block{
 		ProposerID: vID,
@@ -105,7 +94,7 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() {
 		},
 	}
 
-	to := newTotalOrdering(1, 3, 5)
+	to := newTotalOrdering(1, 3, validators)
 	s.checkNotDeliver(to, blockA)
 	s.checkNotDeliver(to, blockB)
 	s.checkNotDeliver(to, blockC)
@@ -127,66 +116,77 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() {
 
 func (s *TotalOrderingTestSuite) TestCreateAckingHeightVectorFromHeightVector() {
 	var (
-		validators = test.GenerateRandomValidatorIDs(5)
-		cache      = newTotalOrderingObjectCache()
+		cache   = newTotalOrderingObjectCache(5)
+		dirties = []int{0, 1, 2, 3, 4}
 	)
-	// Generate dirty validator set.
-	dirties := s.prepareDirtyValidators(validators)
 	// Prepare global acking status.
 	global := &totalOrderingCandidateInfo{
-		ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
-			validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
-			validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
-			validators[2]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
-			validators[3]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
+		ackedStatus: []*totalOrderingHeightRecord{
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
 		}}
 
 	// For 'not existed' record in local but exist in global,
 	// should be infinity.
 	candidate := &totalOrderingCandidateInfo{
-		ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
-			validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 2},
+		ackedStatus: []*totalOrderingHeightRecord{
+			&totalOrderingHeightRecord{minHeight: 0, count: 2},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
 		}}
 	candidate.updateAckingHeightVector(global, 0, dirties, cache)
-	s.Len(candidate.cachedHeightVector, 4)
-	s.Equal(candidate.cachedHeightVector[validators[0]], uint64(0))
-	s.Equal(candidate.cachedHeightVector[validators[1]], infinity)
-	s.Equal(candidate.cachedHeightVector[validators[2]], infinity)
-	s.Equal(candidate.cachedHeightVector[validators[3]], infinity)
+	s.Equal(candidate.cachedHeightVector[0], uint64(0))
+	s.Equal(candidate.cachedHeightVector[1], infinity)
+	s.Equal(candidate.cachedHeightVector[2], infinity)
+	s.Equal(candidate.cachedHeightVector[3], infinity)
 
 	// For local min exceeds global's min+k-1, should be infinity
 	candidate = &totalOrderingCandidateInfo{
-		ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
-			validators[0]: &totalOrderingHeightRecord{minHeight: 3, count: 1},
+		ackedStatus: []*totalOrderingHeightRecord{
+			&totalOrderingHeightRecord{minHeight: 3, count: 1},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
 		}}
 	candidate.updateAckingHeightVector(global, 2, dirties, cache)
-	s.Equal(candidate.cachedHeightVector[validators[0]], infinity)
+	s.Equal(candidate.cachedHeightVector[0], infinity)
 	candidate.updateAckingHeightVector(global, 3, dirties, cache)
-	s.Equal(candidate.cachedHeightVector[validators[0]], uint64(3))
+	s.Equal(candidate.cachedHeightVector[0], uint64(3))
 
 	candidate = &totalOrderingCandidateInfo{
-		ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
-			validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 3},
-			validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 3},
+		ackedStatus: []*totalOrderingHeightRecord{
+			&totalOrderingHeightRecord{minHeight: 0, count: 3},
+			&totalOrderingHeightRecord{minHeight: 0, count: 3},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
 		}}
 	candidate.updateAckingHeightVector(global, 5, dirties, cache)
-	s.Len(candidate.cachedHeightVector, 0)
 }
 
 func (s *TotalOrderingTestSuite) TestCreateAckingNodeSetFromHeightVector() {
-	validators := test.GenerateRandomValidatorIDs(5)
 	global := &totalOrderingCandidateInfo{
-		ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
-			validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
-			validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
-			validators[2]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
-			validators[3]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
+		ackedStatus: []*totalOrderingHeightRecord{
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 5},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
 		}}
 
 	local := &totalOrderingCandidateInfo{
-		ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
-			validators[0]: &totalOrderingHeightRecord{
-				minHeight: 1, count: 2},
+		ackedStatus: []*totalOrderingHeightRecord{
+			&totalOrderingHeightRecord{minHeight: 1, count: 2},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
+			&totalOrderingHeightRecord{minHeight: 0, count: 0},
 		}}
 	s.Equal(local.getAckingNodeSetLength(global, 1), uint64(1))
 	s.Equal(local.getAckingNodeSetLength(global, 2), uint64(1))
@@ -197,55 +197,38 @@ func (s *TotalOrderingTestSuite) TestGrade() {
 	// This test case just fake some internal structure used
 	// when performing total ordering.
 	var (
-		validators = test.GenerateRandomValidatorIDs(5)
-		cache      = newTotalOrderingObjectCache()
+		validators      = test.GenerateRandomValidatorIDs(5)
+		cache           = newTotalOrderingObjectCache(5)
+		dirtyValidators = []int{0, 1, 2, 3, 4}
 	)
-	dirtyValidators := s.prepareDirtyValidators(validators)
 	ansLength := uint64(len(map[types.ValidatorID]struct{}{
 		validators[0]: struct{}{},
 		validators[1]: struct{}{},
 		validators[2]: struct{}{},
 		validators[3]: struct{}{},
 	}))
-	candidates := common.Hashes{
-		common.NewRandomHash(),
-		common.NewRandomHash(),
-		common.NewRandomHash(),
-	}
-	candidate1 := newTotalOrderingCandidateInfo(cache)
-	candidate1.cachedHeightVector = map[types.ValidatorID]uint64{
-		validators[0]: 1,
-		validators[1]: infinity,
-		validators[2]: infinity,
-		validators[3]: infinity,
-	}
-	candidate2 := newTotalOrderingCandidateInfo(cache)
-	candidate2.cachedHeightVector = map[types.ValidatorID]uint64{
-		validators[0]: 1,
-		validators[1]: 1,
-		validators[2]: 1,
-		validators[3]: 1,
-	}
-	candidate3 := newTotalOrderingCandidateInfo(cache)
-	candidate3.cachedHeightVector = map[types.ValidatorID]uint64{
-		validators[0]: 1,
-		validators[1]: 1,
-		validators[2]: infinity,
-		validators[3]: infinity,
-	}
+	candidate1 := newTotalOrderingCandidateInfo(common.Hash{}, cache)
+	candidate1.cachedHeightVector = []uint64{
+		1, infinity, infinity, infinity, infinity}
+	candidate2 := newTotalOrderingCandidateInfo(common.Hash{}, cache)
+	candidate2.cachedHeightVector = []uint64{
+		1, 1, 1, 1, infinity}
+	candidate3 := newTotalOrderingCandidateInfo(common.Hash{}, cache)
+	candidate3.cachedHeightVector = []uint64{
+		1, 1, infinity, infinity, infinity}
 
 	candidate2.updateWinRecord(
-		candidates[0], candidate1, dirtyValidators, cache)
-	s.Equal(candidate2.winRecords[candidates[0]].grade(5, 3, ansLength), 1)
+		0, candidate1, dirtyValidators, cache)
+	s.Equal(candidate2.winRecords[0].grade(5, 3, ansLength), 1)
 	candidate1.updateWinRecord(
-		candidates[1], candidate2, dirtyValidators, cache)
-	s.Equal(candidate1.winRecords[candidates[1]].grade(5, 3, ansLength), 0)
+		1, candidate2, dirtyValidators, cache)
+	s.Equal(candidate1.winRecords[1].grade(5, 3, ansLength), 0)
 	candidate2.updateWinRecord(
-		candidates[2], candidate3, dirtyValidators, cache)
-	s.Equal(candidate2.winRecords[candidates[2]].grade(5, 3, ansLength), -1)
+		2, candidate3, dirtyValidators, cache)
+	s.Equal(candidate2.winRecords[2].grade(5, 3, ansLength), -1)
 	candidate3.updateWinRecord(
-		candidates[1], candidate2, dirtyValidators, cache)
-	s.Equal(candidate3.winRecords[candidates[1]].grade(5, 3, ansLength), 0)
+		1, candidate2, dirtyValidators, cache)
+	s.Equal(candidate3.winRecords[1].grade(5, 3, ansLength), 0)
 }
 
 func (s *TotalOrderingTestSuite) TestCycleDetection() {
@@ -291,7 +274,7 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() {
 	b10.Acks[b10.Hash] = struct{}{}
 
 	// Make sure we won't hang when cycle exists.
-	to := newTotalOrdering(1, 3, 5)
+	to := newTotalOrdering(1, 3, validators)
 	s.checkNotDeliver(to, b00)
 	s.checkNotDeliver(to, b01)
 	s.checkNotDeliver(to, b02)
@@ -303,8 +286,8 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() {
 }
 
 func (s *TotalOrderingTestSuite) TestNotValidDAGDetection() {
-	validators := test.GenerateRandomValidatorIDs(4)
-	to := newTotalOrdering(1, 3, 5)
+	validators := test.GenerateRandomValidatorIDs(5)
+	to := newTotalOrdering(1, 3, validators)
 
 	b00 := s.genGenesisBlock(validators[0], map[common.Hash]struct{}{})
 	b01 := &types.Block{
@@ -331,8 +314,14 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
 	//     A    B
 	//  Even when B is not received, A should
 	//  be able to be delivered.
-	to := newTotalOrdering(2, 3, 5)
 	validators := test.GenerateRandomValidatorIDs(5)
+	to := newTotalOrdering(2, 3, validators)
+	// Get indexes of validatorID used in total ordering module.
+	var validatorIndexes []int
+	for _, vID := range validators {
+		validatorIndexes = append(
+			validatorIndexes, to.validatorIndexMapping[vID])
+	}
 
 	genNextBlock := func(b *types.Block) *types.Block {
 		return &types.Block{
@@ -374,11 +363,10 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
 	s.checkNotDeliver(to, b01)
 	s.checkNotDeliver(to, b02)
 
-	candidate := to.candidates[b00.Hash]
+	candidate := to.candidates[to.candidateIndexMapping[b00.Hash]]
 	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 1)
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(3))
 
 	s.checkNotDeliver(to, b10)
 	s.checkNotDeliver(to, b11)
@@ -390,19 +378,18 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
 	s.checkNotDeliver(to, b31)
 
 	// Check the internal state before delivering.
-	s.Len(to.candidates, 1) // b00 is the only candidate.
+	s.Len(to.candidateIndexMapping, 1) // b00 is the only candidate.
 
-	candidate = to.candidates[b00.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b00.Hash]]
 	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 4)
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
 
 	blocks, early, err := to.processBlock(b32)
 	s.Require().Len(blocks, 1)
@@ -411,44 +398,46 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
 	s.checkHashSequence(blocks, common.Hashes{b00.Hash})
 
 	// Check the internal state after delivered.
-	s.Len(to.candidates, 4) // b01, b10, b20, b30 are candidates.
+	s.Len(to.candidateIndexMapping, 4) // b01, b10, b20, b30 are candidates.
 
 	// Check b01.
-	candidate = to.candidates[b01.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b01.Hash]]
 	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 1)
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
 
 	// Check b10.
-	candidate = to.candidates[b10.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b10.Hash]]
 	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 1)
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
 
 	// Check b20.
-	candidate = to.candidates[b20.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b20.Hash]]
 	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 1)
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
 
 	// Check b30.
-	candidate = to.candidates[b30.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b30.Hash]]
 	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 1)
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
 
 	// Make sure b00 doesn't exist in current working set:
 	s.checkNotInWorkingSet(to, b00)
 }
 
-func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
+func (s *TotalOrderingTestSuite) TestBasicCaseForK2() {
 	// It's a handcrafted test case.
-	to := newTotalOrdering(2, 3, 5)
 	validators := test.GenerateRandomValidatorIDs(5)
+	to := newTotalOrdering(2, 3, validators)
+	// Get indexes of validatorID used in total ordering module.
+	var validatorIndexes []int
+	for _, vID := range validators {
+		validatorIndexes = append(
+			validatorIndexes, to.validatorIndexMapping[vID])
+	}
 
 	b00 := s.genGenesisBlock(validators[0], map[common.Hash]struct{}{})
 	b10 := s.genGenesisBlock(validators[1], map[common.Hash]struct{}{})
@@ -631,33 +620,33 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
 	s.Contains(acked, b32.Hash)
 
 	// Make sure there are 2 candidates.
-	s.Require().Len(to.candidates, 2)
+	s.Require().Len(to.candidateIndexMapping, 2)
 
 	// Check b00's height vector.
-	candidate := to.candidates[b00.Hash]
+	candidate := to.candidates[to.candidateIndexMapping[b00.Hash]]
 	s.Require().NotNil(candidate)
-	s.NotContains(candidate.ackedStatus, validators[4])
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b31.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+	s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b11.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b21.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b31.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
 
 	// Check b10's height vector.
-	candidate = to.candidates[b10.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b10.Hash]]
 	s.Require().NotNil(candidate)
-	s.NotContains(candidate.ackedStatus, validators[4])
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
+	s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
 
 	// Check the first deliver.
 	blocks, early, err := to.processBlock(b02)
@@ -670,33 +659,33 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
 	s.checkNotInWorkingSet(to, b10)
 
 	// Check if candidates of next round are picked correctly.
-	s.Len(to.candidates, 2)
+	s.Len(to.candidateIndexMapping, 2)
 
 	// Check b01's height vector.
-	candidate = to.candidates[b11.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b11.Hash]]
 	s.Require().NotNil(candidate)
 	s.NotContains(candidate.ackedStatus, validators[4])
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b11.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b11.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b21.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b11.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
 
 	// Check b20's height vector.
-	candidate = to.candidates[b20.Hash]
+	candidate = to.candidates[to.candidateIndexMapping[b20.Hash]]
 	s.Require().NotNil(candidate)
 	s.NotContains(candidate.ackedStatus, validators[4])
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b02.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b12.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(1))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b02.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b12.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(1))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
 
 	s.checkNotDeliver(to, b13)
 
@@ -717,39 +706,39 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
 	s.checkNotDeliver(to, b14)
 
 	// Make sure b01, b30, b40 are candidate in next round.
-	s.Len(to.candidates, 3)
-	candidate = to.candidates[b01.Hash]
+	s.Len(to.candidateIndexMapping, 3)
+	candidate = to.candidates[to.candidateIndexMapping[b01.Hash]]
 	s.Require().NotNil(candidate)
-	s.NotContains(candidate.ackedStatus, validators[4])
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b12.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b31.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
-
-	candidate = to.candidates[b30.Hash]
+	s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b12.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b21.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b31.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
+
+	candidate = to.candidates[to.candidateIndexMapping[b30.Hash]]
 	s.Require().NotNil(candidate)
-	s.NotContains(candidate.ackedStatus, validators[4])
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b03.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b13.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b22.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(1))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
-
-	candidate = to.candidates[b40.Hash]
+	s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b03.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b13.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b22.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(1))
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
+
+	candidate = to.candidates[to.candidateIndexMapping[b40.Hash]]
 	s.Require().NotNil(candidate)
-	s.NotContains(candidate.ackedStatus, validators[0])
-	s.NotContains(candidate.ackedStatus, validators[1])
-	s.NotContains(candidate.ackedStatus, validators[2])
-	s.NotContains(candidate.ackedStatus, validators[3])
-	s.Equal(candidate.ackedStatus[validators[4]].minHeight, b40.Height)
-	s.Equal(candidate.ackedStatus[validators[4]].count, uint64(3))
+	s.NotContains(candidate.ackedStatus, validatorIndexes[0])
+	s.NotContains(candidate.ackedStatus, validatorIndexes[1])
+	s.NotContains(candidate.ackedStatus, validatorIndexes[2])
+	s.NotContains(candidate.ackedStatus, validatorIndexes[3])
+	s.Equal(candidate.ackedStatus[validatorIndexes[4]].minHeight, b40.Height)
+	s.Equal(candidate.ackedStatus[validatorIndexes[4]].count, uint64(3))
 
 	// Make 'Acking Node Set' contains blocks from all validators,
 	// this should trigger not-early deliver.
@@ -763,8 +752,8 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
 	s.checkNotInWorkingSet(to, b30)
 
 	// Make sure b21, b40 are candidates of next round.
-	s.Contains(to.candidates, b21.Hash)
-	s.Contains(to.candidates, b40.Hash)
+	s.Contains(to.candidateIndexMapping, b21.Hash)
+	s.Contains(to.candidateIndexMapping, b40.Hash)
 }
 
 func (s *TotalOrderingTestSuite) TestBasicCaseForK0() {
@@ -778,8 +767,17 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() {
 	//  | \ | \ |    |
 	//  v   v   v    v
 	//  o   o   o <- o        Height: 0
-	to := newTotalOrdering(0, 3, 5)
+	var (
+		req              = s.Require()
+		validatorIndexes []int
+	)
 	validators := test.GenerateRandomValidatorIDs(5)
+	to := newTotalOrdering(0, 3, validators)
+	// Get indexes of validatorID used in total ordering module.
+	for _, vID := range validators {
+		validatorIndexes = append(
+			validatorIndexes, to.validatorIndexMapping[vID])
+	}
 
 	b00 := s.genGenesisBlock(validators[0], map[common.Hash]struct{}{})
 	b10 := s.genGenesisBlock(validators[1], map[common.Hash]struct{}{})
@@ -840,46 +838,44 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() {
 	s.checkNotDeliver(to, b31)
 
 	// Check candidate status before delivering.
-	candidate := to.candidates[b00.Hash]
-	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 1)
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
-
-	candidate = to.candidates[b10.Hash]
-	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 2)
-	s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
-	s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
-
-	candidate = to.candidates[b20.Hash]
-	s.Require().NotNil(candidate)
-	s.Len(candidate.ackedStatus, 3)
-	s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height)
-	s.Equal(candidate.ackedStatus[validators[1]].count, uint64(1))
-	s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
-	s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
-	s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
-	s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+	candidate := to.candidates[to.candidateIndexMapping[b00.Hash]]
+	req.NotNil(candidate)
+	req.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+	req.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
+
+	candidate = to.candidates[to.candidateIndexMapping[b10.Hash]]
+	req.NotNil(candidate)
+	req.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+	req.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+	req.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+	req.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+
+	candidate = to.candidates[to.candidateIndexMapping[b20.Hash]]
+	req.NotNil(candidate)
+	req.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b11.Height)
+	req.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(1))
+	req.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+	req.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+	req.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+	req.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
 
 	// This new block should trigger non-early deliver.
 	blocks, early, err := to.processBlock(b40)
-	s.False(early)
-	s.Nil(err)
+	req.False(early)
+	req.Nil(err)
 	s.checkHashSequence(blocks, common.Hashes{b20.Hash})
 
 	// Make sure b20 is no long existing in working set.
 	s.checkNotInWorkingSet(to, b20)
 
 	// Make sure b10, b30 are candidates for next round.
-	s.Contains(to.candidates, b10.Hash)
-	s.Contains(to.candidates, b30.Hash)
+	req.Contains(to.candidateIndexMapping, b00.Hash)
+	req.Contains(to.candidateIndexMapping, b10.Hash)
+	req.Contains(to.candidateIndexMapping, b30.Hash)
 }
 
 func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks(
-	totalOrderingConstructor func() *totalOrdering,
+	totalOrderingConstructor func(types.ValidatorIDs) *totalOrdering,
 	validatorCount, blockCount int,
 	ackingCountGenerator func() int,
 	repeat int) {
@@ -893,8 +889,10 @@ func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks(
 
 	db, err := blockdb.NewMemBackedBlockDB()
 	req.Nil(err)
-	req.Nil(gen.Generate(
-		validatorCount, blockCount, ackingCountGenerator, db))
+	validators, err := gen.Generate(
+		validatorCount, blockCount, ackingCountGenerator, db)
+	req.Nil(err)
+	req.Len(validators, validatorCount)
 	iter, err := db.GetAll()
 	req.Nil(err)
 	// Setup a revealer that would reveal blocks forming
@@ -907,7 +905,7 @@ func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks(
 		revealed := ""
 		ordered := ""
 		revealer.Reset()
-		to := totalOrderingConstructor()
+		to := totalOrderingConstructor(validators)
 		for {
 			// Reveal next block.
 			b, err := revealer.Next()
@@ -965,26 +963,26 @@ func (s *TotalOrderingTestSuite) TestRandomlyGeneratedBlocks() {
 	// Test based on different acking frequency.
 	for _, gen := range ackingCountGenerators {
 		// Test for K=0.
-		constructor := func() *totalOrdering {
-			return newTotalOrdering(0, phi, uint64(validatorCount))
+		constructor := func(validators types.ValidatorIDs) *totalOrdering {
+			return newTotalOrdering(0, phi, validators)
 		}
 		s.baseTestRandomlyGeneratedBlocks(
 			constructor, validatorCount, blockCount, gen, repeat)
 		// Test for K=1,
-		constructor = func() *totalOrdering {
-			return newTotalOrdering(1, phi, uint64(validatorCount))
+		constructor = func(validators types.ValidatorIDs) *totalOrdering {
+			return newTotalOrdering(1, phi, validators)
 		}
 		s.baseTestRandomlyGeneratedBlocks(
 			constructor, validatorCount, blockCount, gen, repeat)
 		// Test for K=2,
-		constructor = func() *totalOrdering {
-			return newTotalOrdering(2, phi, uint64(validatorCount))
+		constructor = func(validators types.ValidatorIDs) *totalOrdering {
+			return newTotalOrdering(2, phi, validators)
 		}
 		s.baseTestRandomlyGeneratedBlocks(
 			constructor, validatorCount, blockCount, gen, repeat)
 		// Test for K=3,
-		constructor = func() *totalOrdering {
-			return newTotalOrdering(3, phi, uint64(validatorCount))
+		constructor = func(validators types.ValidatorIDs) *totalOrdering {
+			return newTotalOrdering(3, phi, validators)
 		}
 		s.baseTestRandomlyGeneratedBlocks(
 			constructor, validatorCount, blockCount, gen, repeat)
diff --git a/core/utils.go b/core/utils.go
index d023d2e..6b03f93 100644
--- a/core/utils.go
+++ b/core/utils.go
@@ -92,3 +92,14 @@ func getMedianTime(block *types.Block) (t time.Time, err error) {
 	return
 
 }
+
+func removeFromSortedIntSlice(xs []int, x int) []int {
+	indexToRemove := sort.Search(len(xs), func(idx int) bool {
+		return xs[idx] >= x
+	})
+	if indexToRemove == len(xs) || xs[indexToRemove] != x {
+		// This value is not found.
+		return xs
+	}
+	return append(xs[:indexToRemove], xs[indexToRemove+1:]...)
+}
diff --git a/core/utils_test.go b/core/utils_test.go
new file mode 100644
index 0000000..5d55de3
--- /dev/null
+++ b/core/utils_test.go
@@ -0,0 +1,27 @@
+package core
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/suite"
+)
+
+type UtilsTestSuite struct {
+	suite.Suite
+}
+
+func (s *UtilsTestSuite) TestRemoveFromSortedIntSlice() {
+	// Remove something exists.
+	xs := []int{1, 2, 3, 4, 5}
+	s.Equal(
+		removeFromSortedIntSlice(xs, 3),
+		[]int{1, 2, 4, 5})
+	// Remove something not exists.
+	s.Equal(removeFromSortedIntSlice(xs, 6), xs)
+	// Remove from empty slice, should not panic.
+	s.Equal([]int{}, removeFromSortedIntSlice([]int{}, 1))
+}
+
+func TestUtils(t *testing.T) {
+	suite.Run(t, new(UtilsTestSuite))
+}