From 9261a3b9f3711ba736f2a143456e0b73bdfcfab8 Mon Sep 17 00:00:00 2001 From: Mission Liao Date: Mon, 30 Jul 2018 14:55:42 +0800 Subject: Implement DEXON total ordering algorithm (#16) Implement K-Level Total ordering algorithm Besides algorithm implementation, these concepts are also included: The candidate set and ackingStatusVector of each candidate won't be recalculated upon receiving each block. Make the component to calculate total ordering more self-contained. The access to block status is only required when receiving a new block. --- core/sequencer.go | 522 +++++++++++++++++++++++++++++ core/sequencer_test.go | 874 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 1396 insertions(+) create mode 100644 core/sequencer.go create mode 100644 core/sequencer_test.go (limited to 'core') diff --git a/core/sequencer.go b/core/sequencer.go new file mode 100644 index 0000000..36c1383 --- /dev/null +++ b/core/sequencer.go @@ -0,0 +1,522 @@ +// 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 +// . + +package core + +import ( + "fmt" + "sort" + + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" +) + +// ErrNotValidDAG would be reported when block subbmitted to sequencer +// didn't form a DAG. +var ErrNotValidDAG = fmt.Errorf("not a valid dag") + +// ackingStatusVector describes the acking status, either globally or just +// for one candidate. +// +// When block A acks block B, all blocks proposed from the same proposer +// as block A with higher height would also acks block B. Therefore, +// we just need to record: +// - the minimum height of acking block from that proposer +// - count of acking blocks from that proposer +// to repsent the acking status for block A. +type ackingStatusVector map[types.ValidatorID]*struct{ minHeight, count uint64 } + +// addBlock would update ackingStatusVector, it's caller's duty +// to make sure the input block acutally acking the target block. +func (v ackingStatusVector) addBlock(b *types.Block) (err error) { + rec, exists := v[b.ProposerID] + if !exists { + v[b.ProposerID] = &struct { + minHeight, count uint64 + }{ + minHeight: b.Height, + count: 1, + } + } else { + if b.Height < rec.minHeight { + err = ErrNotValidDAG + return + } + rec.count++ + } + return +} + +// getAckingNodeSet would generate the Acking Node Set. +// Only block height larger than +// +// global minimum height + k +// +// would be taken into consideration, ex. +// +// For some validator X: +// - the global minimum acking height = 1, +// - k = 1 +// then only block height >= 2 would be added to acking node set. +func (v ackingStatusVector) getAckingNodeSet( + global ackingStatusVector, k uint64) map[types.ValidatorID]struct{} { + + ret := make(map[types.ValidatorID]struct{}) + for vID, gRec := range global { + rec, exists := v[vID] + if !exists { + continue + } + + // This line would check if these two ranges would overlap: + // - (global minimum height + k, infinity) + // - (local minimum height, local minimum height + count - 1) + if rec.minHeight+rec.count-1 >= gRec.minHeight+k { + ret[vID] = struct{}{} + } + } + return ret +} + +// getAckingHeightVector would convert 'ackingStatusVector' to +// Acking Height Vector. +// +// Only block height equals to (global minimum block height + k) would be +// taken into consideration. +func (v ackingStatusVector) getAckingHeightVector( + global ackingStatusVector, k uint64) map[types.ValidatorID]uint64 { + + ret := make(map[types.ValidatorID]uint64) + for vID, gRec := range global { + rec, exists := v[vID] + + if gRec.count <= k { + continue + } else if !exists { + ret[vID] = 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 ackingStatusVector. + ret[vID] = gRec.minHeight + k + } else { + ret[vID] = infinity + } + } + return ret +} + +// blockVector stores all blocks grouped by their proposers and +// sorted by their block height. +type blockVector map[types.ValidatorID][]*types.Block + +func (v blockVector) addBlock(b *types.Block) (err error) { + blocksFromProposer := v[b.ProposerID] + if len(blocksFromProposer) > 0 { + lastBlock := blocksFromProposer[len(blocksFromProposer)-1] + if b.Height-lastBlock.Height != 1 { + err = ErrNotValidDAG + return + } + } + v[b.ProposerID] = append(blocksFromProposer, b) + return +} + +// getHeightVector would convert a blockVector to +// ackingStatusVectorAckingStatus. +func (v blockVector) getHeightVector() ackingStatusVector { + ret := ackingStatusVector{} + for vID, vec := range v { + if len(vec) == 0 { + continue + } + ret[vID] = &struct { + minHeight, count uint64 + }{ + minHeight: vec[0].Height, + count: uint64(len(vec)), + } + } + return ret +} + +// Sequencer represent a process unit to handle total ordering +// for blocks. +type sequencer struct { + // pendings stores blocks awaiting to be ordered. + pendings map[common.Hash]*types.Block + + // k represents the k in 'k-level total ordering'. + // In short, only block height equals to (global minimum height + k) + // would be taken into consideration. + k uint64 + + // phi is a const to control how strong the leading preceding block + // should be. + phi uint64 + + // validatorCount is the count of validator set. + validatorCount uint64 + + // globalVector group all pending blocks by proposers and + // sort them by block height. This structure is helpful when: + // + // - build global height vector + // - picking candidates next round + globalVector blockVector + + // candidateAckingStatusVectors caches ackingStatusVector of candidates. + candidateAckingStatusVectors map[common.Hash]ackingStatusVector + + // 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{} +} + +func newSequencer(k, phi, validatorCount uint64) *sequencer { + return &sequencer{ + candidateAckingStatusVectors: make(map[common.Hash]ackingStatusVector), + pendings: make(map[common.Hash]*types.Block), + k: k, + phi: phi, + validatorCount: validatorCount, + globalVector: blockVector{}, + acked: make(map[common.Hash]map[common.Hash]struct{}), + } +} + +// buildBlockRelation populates the acked according their acking relationships. +func (s *sequencer) buildBlockRelation(b *types.Block) { + // populateAcked would update all blocks implcitly acked + // by input block recursively. + var populateAcked func(bx, target *types.Block) + populateAcked = func(bx, target *types.Block) { + for ack := range bx.Acks { + acked, exists := s.acked[ack] + if !exists { + acked = make(map[common.Hash]struct{}) + s.acked[ack] = acked + } + + // This means we've walked this block already. + if _, alreadyPopulated := acked[target.Hash]; alreadyPopulated { + continue + } + acked[target.Hash] = struct{}{} + + // See if we need to go forward. + if nextBlock, exists := s.pendings[ack]; !exists { + continue + } else { + populateAcked(nextBlock, target) + } + } + } + populateAcked(b, b) +} + +// clean would remove a block from working set. This behaviour +// would prevent our memory usage growing infinity. +func (s *sequencer) clean(h common.Hash) { + delete(s.acked, h) + delete(s.pendings, h) + delete(s.candidateAckingStatusVectors, h) +} + +// updateVectors is a helper function to update all cached vectors. +func (s *sequencer) updateVectors(b *types.Block) (err error) { + // Update global height vector + err = s.globalVector.addBlock(b) + if err != nil { + return + } + + // Update acking status of candidates. + for candidate, vector := range s.candidateAckingStatusVectors { + if _, acked := s.acked[candidate][b.Hash]; !acked { + continue + } + if err = vector.addBlock(b); err != nil { + return + } + } + return +} + +// grade implements the 'grade' potential function described in white paper. +func (s *sequencer) grade( + hvFrom, hvTo map[types.ValidatorID]uint64, + globalAns map[types.ValidatorID]struct{}) int { + + count := uint64(0) + for vID, hFrom := range hvFrom { + hTo, exists := hvTo[vID] + if !exists { + continue + } + + if hFrom != infinity && hTo == infinity { + count++ + } + } + + if count >= s.phi { + return 1 + } else if count < s.phi-s.validatorCount+uint64(len(globalAns)) { + return 0 + } else { + return -1 + } +} + +// buildAckingStatusVectorForNewCandidate is a helper function to +// build ackingStatusVector for new candidate. +func (s *sequencer) buildAckingStatusVectorForNewCandidate( + candidate *types.Block) (hVec ackingStatusVector) { + + blocks := s.globalVector[candidate.ProposerID] + hVec = ackingStatusVector{ + candidate.ProposerID: &struct { + minHeight, count uint64 + }{ + minHeight: candidate.Height, + count: uint64(len(blocks)), + }, + } + + ackedsForCandidate, exists := s.acked[candidate.Hash] + if !exists { + // This candidate is acked by nobody. + return + } + + for vID, blocks := range s.globalVector { + if vID == candidate.ProposerID { + continue + } + + for i, b := range blocks { + if _, acked := ackedsForCandidate[b.Hash]; !acked { + continue + } + + // If this block acks this candidate, all newer blocks + // from the same validator also 'indirect' acks it. + hVec[vID] = &struct { + minHeight, count uint64 + }{ + minHeight: b.Height, + count: uint64(len(blocks) - i), + } + break + } + } + return +} + +// isAckOnlyPrecedings is a helper function to check if a block +// only contain acks to delivered blocks. +func (s *sequencer) isAckOnlyPrecedings(b *types.Block) bool { + for ack := range b.Acks { + if _, pending := s.pendings[ack]; pending { + return false + } + } + return true +} + +// output is a helper function to finish the delivery of +// deliverable preceding set. +func (s *sequencer) output(precedings map[common.Hash]struct{}) common.Hashes { + ret := common.Hashes{} + for p := range precedings { + ret = append(ret, p) + + // Remove the first element from corresponding blockVector. + b := s.pendings[p] + s.globalVector[b.ProposerID] = s.globalVector[b.ProposerID][1:] + + // Remove block relations. + s.clean(p) + } + sort.Sort(ret) + + // Find new candidates from tip of globalVector of each validator. + // The complexity here is O(N^2logN). + for _, blocks := range s.globalVector { + if len(blocks) == 0 { + continue + } + + tip := blocks[0] + if _, alreadyCandidate := + s.candidateAckingStatusVectors[tip.Hash]; alreadyCandidate { + continue + } + + if !s.isAckOnlyPrecedings(tip) { + continue + } + + // Build ackingStatusVector for new candidate. + s.candidateAckingStatusVectors[tip.Hash] = + s.buildAckingStatusVectorForNewCandidate(tip) + } + return ret +} + +// generateDeliverSet would: +// - generate preceding set +// - check if the preceding set deliverable by checking potential function +func (s *sequencer) generateDeliverSet() ( + delivered map[common.Hash]struct{}, early bool) { + + globalHeightVector := s.globalVector.getHeightVector() + ahvs := map[common.Hash]map[types.ValidatorID]uint64{} + for candidate, v := range s.candidateAckingStatusVectors { + ahvs[candidate] = v.getAckingHeightVector(globalHeightVector, s.k) + } + + globalAns := globalHeightVector.getAckingNodeSet(globalHeightVector, s.k) + precedings := make(map[common.Hash]struct{}) + +CheckNextCandidateLoop: + for candidate := range s.candidateAckingStatusVectors { + for otherCandidate := range s.candidateAckingStatusVectors { + if candidate == otherCandidate { + continue + } + if s.grade(ahvs[otherCandidate], ahvs[candidate], globalAns) != 0 { + continue CheckNextCandidateLoop + } + } + precedings[candidate] = struct{}{} + } + + if len(precedings) == 0 { + return + } + + // internal is a helper function to verify internal stability. + internal := func() bool { + for candidate := range s.candidateAckingStatusVectors { + if _, isPreceding := precedings[candidate]; isPreceding { + continue + } + + beaten := false + for p := range precedings { + if beaten = + s.grade(ahvs[p], ahvs[candidate], globalAns) == 1; beaten { + break + } + } + if !beaten { + return false + } + } + return true + } + + // checkAHV is a helper function to verify external stability. + // It would make sure some preceding block is strong enough + // to lead the whole preceding set. + checkAHV := func() bool { + for p := range precedings { + count := uint64(0) + for _, v := range ahvs[p] { + if v != infinity { + count++ + } + } + + if count > s.phi { + return true + } + } + return false + } + + // checkANS is a helper function to verify external stability. + // It would make sure all preceding blocks are strong enough + // to be delivered. + checkANS := func() bool { + for p := range precedings { + validatorAns := s.candidateAckingStatusVectors[p].getAckingNodeSet( + globalHeightVector, s.k) + if uint64(len(validatorAns)) < s.validatorCount-s.phi { + return false + } + } + + return true + } + + // Check internal stability first. + if !internal() { + return + } + + // If all validators propose enough blocks, we should force + // to deliver since the whole picture of the DAG is revealed. + if uint64(len(globalAns)) != s.validatorCount { + // The whole picture is not ready, we need to check if + // exteranl stability is met, and we can deliver earlier. + if checkAHV() && checkANS() { + early = true + } else { + return + } + } + + delivered = precedings + return +} + +// processBlock is the entry point of sequencer. +func (s *sequencer) processBlock(b *types.Block) ( + delivered common.Hashes, early bool, err error) { + + // NOTE: I assume the block 'b' is already safe for total ordering. + // That means, all its acking blocks are during/after + // total ordering stage. + + // Incremental part. + s.pendings[b.Hash] = b + s.buildBlockRelation(b) + if err = s.updateVectors(b); err != nil { + return + } + if s.isAckOnlyPrecedings(b) { + s.candidateAckingStatusVectors[b.Hash] = + s.buildAckingStatusVectorForNewCandidate(b) + } + + // Not-Incremental part (yet). + // - generate ahv for each candidate + // - generate ans for each candidate + // - generate global ans + // - find preceding set + hashes, early := s.generateDeliverSet() + + // output precedings + delivered = s.output(hashes) + return +} diff --git a/core/sequencer_test.go b/core/sequencer_test.go new file mode 100644 index 0000000..fa8b461 --- /dev/null +++ b/core/sequencer_test.go @@ -0,0 +1,874 @@ +package core + +import ( + "sort" + "testing" + + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" + "github.com/stretchr/testify/suite" +) + +type SequencerTestSuite struct { + suite.Suite +} + +func (s *SequencerTestSuite) generateValidatorIDs( + count int) []types.ValidatorID { + + validatorIDs := []types.ValidatorID{} + for i := 0; i < count; i++ { + validatorIDs = append(validatorIDs, + types.ValidatorID{Hash: common.NewRandomHash()}) + } + + return validatorIDs +} + +func (s *SequencerTestSuite) genRootBlock( + vID types.ValidatorID, acks map[common.Hash]struct{}) *types.Block { + + hash := common.NewRandomHash() + return &types.Block{ + ProposerID: vID, + ParentHash: hash, + Hash: hash, + Height: 0, + Acks: acks, + } +} + +func (s *SequencerTestSuite) checkNotDeliver(seq *sequencer, b *types.Block) { + hashes, eqrly, err := seq.processBlock(b) + s.Empty(hashes) + s.False(eqrly) + s.Nil(err) +} + +func (s *SequencerTestSuite) checkNotInWorkingSet( + seq *sequencer, b *types.Block) { + + s.NotContains(seq.pendings, b.Hash) + s.NotContains(seq.acked, b.Hash) +} + +func (s *SequencerTestSuite) 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()} + + hash := common.NewRandomHash() + blockA := &types.Block{ + ProposerID: vID, + ParentHash: hash, + Hash: hash, + Height: 0, + Acks: map[common.Hash]struct{}{}, + } + blockB := &types.Block{ + ProposerID: vID, + ParentHash: blockA.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + blockA.Hash: struct{}{}, + }, + } + blockC := &types.Block{ + ProposerID: vID, + ParentHash: blockB.Hash, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + blockB.Hash: struct{}{}, + }, + } + + seq := newSequencer(1, 3, 5) + s.checkNotDeliver(seq, blockA) + s.checkNotDeliver(seq, blockB) + s.checkNotDeliver(seq, blockC) + + // Check 'acked'. + ackedA := seq.acked[blockA.Hash] + s.Require().NotNil(ackedA) + s.Len(ackedA, 2) + s.Contains(ackedA, blockB.Hash) + s.Contains(ackedA, blockC.Hash) + + ackedB := seq.acked[blockB.Hash] + s.Require().NotNil(ackedB) + s.Len(ackedB, 1) + s.Contains(ackedB, blockC.Hash) + + s.Nil(seq.acked[blockC.Hash]) +} + +func (s *SequencerTestSuite) TestCreateAckingHeightVectorFromHeightVector() { + validators := s.generateValidatorIDs(5) + global := ackingStatusVector{ + validators[0]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + validators[1]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + validators[2]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + validators[3]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + } + + // For 'not existed' record in local but exist in global, + // should be infinity. + ahv := ackingStatusVector{ + validators[0]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 2}, + }.getAckingHeightVector(global, 0) + s.Len(ahv, 4) + s.Equal(ahv[validators[0]], uint64(0)) + s.Equal(ahv[validators[1]], infinity) + s.Equal(ahv[validators[2]], infinity) + s.Equal(ahv[validators[3]], infinity) + + // For local min exceeds global's min+k-1, should be infinity + hv := ackingStatusVector{ + validators[0]: &struct{ minHeight, count uint64 }{ + minHeight: 3, count: 1}, + } + ahv = hv.getAckingHeightVector(global, 2) + s.Equal(ahv[validators[0]], infinity) + ahv = hv.getAckingHeightVector(global, 3) + s.Equal(ahv[validators[0]], uint64(3)) + + ahv = ackingStatusVector{ + validators[0]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 3}, + validators[1]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 3}, + }.getAckingHeightVector(global, 5) + s.Len(ahv, 0) +} + +func (s *SequencerTestSuite) TestCreateAckingNodeSetFromHeightVector() { + validators := s.generateValidatorIDs(5) + global := ackingStatusVector{ + validators[0]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + validators[1]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + validators[2]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + validators[3]: &struct{ minHeight, count uint64 }{ + minHeight: 0, count: 5}, + } + + local := ackingStatusVector{ + validators[0]: &struct{ minHeight, count uint64 }{ + minHeight: 1, count: 2}, + } + s.Len(local.getAckingNodeSet(global, 1), 1) + s.Len(local.getAckingNodeSet(global, 2), 1) + s.Len(local.getAckingNodeSet(global, 3), 0) +} + +func (s *SequencerTestSuite) TestGrade() { + validators := s.generateValidatorIDs(5) + seq := newSequencer(1, 3, 5) // K doesn't matter when calculating preceding. + + ans := map[types.ValidatorID]struct{}{ + validators[0]: struct{}{}, + validators[1]: struct{}{}, + validators[2]: struct{}{}, + validators[3]: struct{}{}, + } + + ahv1 := map[types.ValidatorID]uint64{ + validators[0]: 1, + validators[1]: infinity, + validators[2]: infinity, + validators[3]: infinity, + } + ahv2 := map[types.ValidatorID]uint64{ + validators[0]: 1, + validators[1]: 1, + validators[2]: 1, + validators[3]: 1, + } + ahv3 := map[types.ValidatorID]uint64{ + validators[0]: 1, + validators[1]: 1, + validators[2]: infinity, + validators[3]: infinity, + } + s.Equal(seq.grade(ahv2, ahv1, ans), 1) + s.Equal(seq.grade(ahv1, ahv2, ans), 0) + s.Equal(seq.grade(ahv2, ahv3, ans), -1) + s.Equal(seq.grade(ahv3, ahv2, ans), 0) +} + +func (s *SequencerTestSuite) TestCycleDetection() { + // Make sure we don't get hang by cycle from + // block's acks. + validators := s.generateValidatorIDs(5) + + // create blocks with cycles in acking relation. + cycledHash := common.NewRandomHash() + hash := common.NewRandomHash() + b00 := &types.Block{ + ProposerID: validators[0], + ParentHash: hash, + Hash: hash, + Height: 0, + Acks: map[common.Hash]struct{}{ + cycledHash: struct{}{}, + }, + } + b01 := &types.Block{ + ProposerID: validators[0], + ParentHash: b00.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b00.Hash: struct{}{}, + }, + } + b02 := &types.Block{ + ProposerID: validators[0], + ParentHash: b01.Hash, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + b01.Hash: struct{}{}, + }, + } + b03 := &types.Block{ + ProposerID: validators[0], + ParentHash: b02.Hash, + Hash: cycledHash, + Height: 3, + Acks: map[common.Hash]struct{}{ + b02.Hash: struct{}{}, + }, + } + + // Create a block acks self. + hash = common.NewRandomHash() + b10 := &types.Block{ + ProposerID: validators[1], + ParentHash: hash, + Hash: hash, + Height: 0, + Acks: map[common.Hash]struct{}{ + hash: struct{}{}, + }, + } + + // Make sure we won't hang when cycle exists. + seq := newSequencer(1, 3, 5) + s.checkNotDeliver(seq, b00) + s.checkNotDeliver(seq, b01) + s.checkNotDeliver(seq, b02) + + // Should not hang in this line. + s.checkNotDeliver(seq, b03) + // Should not hang in this line + s.checkNotDeliver(seq, b10) +} + +func (s *SequencerTestSuite) TestNotValidDAGDetection() { + validators := s.generateValidatorIDs(4) + seq := newSequencer(1, 3, 5) + + hash := common.NewRandomHash() + b00 := &types.Block{ + ProposerID: validators[0], + ParentHash: hash, + Hash: hash, + Height: 0, + Acks: map[common.Hash]struct{}{}, + } + b01 := &types.Block{ + ProposerID: validators[0], + ParentHash: b00.Hash, + Hash: common.NewRandomHash(), + } + + // When submit to block with lower height to sequencer, + // caller should receive an error. + s.checkNotDeliver(seq, b01) + _, _, err := seq.processBlock(b00) + s.Equal(err, ErrNotValidDAG) +} + +func (s *SequencerTestSuite) TestEarlyDeliver() { + // The test scenario: + // + // o o o o o + // : : : : : <- (K - 1) layers + // o o o o o + // \ v / | + // o o + // A B + // Even when B is not received, A should + // be able to be delivered. + seq := newSequencer(2, 3, 5) + validators := s.generateValidatorIDs(5) + + genNextBlock := func(b *types.Block) *types.Block { + return &types.Block{ + ProposerID: b.ProposerID, + ParentHash: b.Hash, + Hash: common.NewRandomHash(), + Height: b.Height + 1, + Acks: map[common.Hash]struct{}{ + b.Hash: struct{}{}, + }, + } + } + + b00 := s.genRootBlock(validators[0], map[common.Hash]struct{}{}) + b01 := genNextBlock(b00) + b02 := genNextBlock(b01) + + b10 := s.genRootBlock(validators[1], map[common.Hash]struct{}{ + b00.Hash: struct{}{}, + }) + b11 := genNextBlock(b10) + b12 := genNextBlock(b11) + + b20 := s.genRootBlock(validators[2], map[common.Hash]struct{}{ + b00.Hash: struct{}{}, + }) + b21 := genNextBlock(b20) + b22 := genNextBlock(b21) + + b30 := s.genRootBlock(validators[3], map[common.Hash]struct{}{ + b00.Hash: struct{}{}, + }) + b31 := genNextBlock(b30) + b32 := genNextBlock(b31) + + // It's a valid block sequence to deliver + // to total ordering algorithm: DAG. + s.checkNotDeliver(seq, b00) + s.checkNotDeliver(seq, b01) + s.checkNotDeliver(seq, b02) + + vec := seq.candidateAckingStatusVectors[b00.Hash] + s.Require().NotNil(vec) + s.Len(vec, 1) + s.Equal(vec[validators[0]].minHeight, b00.Height) + s.Equal(vec[validators[0]].count, uint64(3)) + + s.checkNotDeliver(seq, b10) + s.checkNotDeliver(seq, b11) + s.checkNotDeliver(seq, b12) + s.checkNotDeliver(seq, b20) + s.checkNotDeliver(seq, b21) + s.checkNotDeliver(seq, b22) + s.checkNotDeliver(seq, b30) + s.checkNotDeliver(seq, b31) + + // Check the internal state before delivering. + s.Len(seq.candidateAckingStatusVectors, 1) // b00 is the only candidate. + + vec = seq.candidateAckingStatusVectors[b00.Hash] + s.Require().NotNil(vec) + s.Len(vec, 4) + s.Equal(vec[validators[0]].minHeight, b00.Height) + s.Equal(vec[validators[0]].count, uint64(3)) + s.Equal(vec[validators[1]].minHeight, b10.Height) + s.Equal(vec[validators[1]].count, uint64(3)) + s.Equal(vec[validators[2]].minHeight, b20.Height) + s.Equal(vec[validators[2]].count, uint64(3)) + s.Equal(vec[validators[3]].minHeight, b30.Height) + s.Equal(vec[validators[3]].count, uint64(2)) + + hashes, early, err := seq.processBlock(b32) + s.Require().Len(hashes, 1) + s.True(early) + s.Nil(err) + s.Equal(hashes[0], b00.Hash) + + // Check the internal state after delivered. + s.Len(seq.candidateAckingStatusVectors, 4) // b01, b10, b20, b30 are candidates. + + // Check b01. + vec = seq.candidateAckingStatusVectors[b01.Hash] + s.Require().NotNil(vec) + s.Len(vec, 1) + s.Equal(vec[validators[0]].minHeight, b01.Height) + s.Equal(vec[validators[0]].count, uint64(2)) + + // Check b10. + vec = seq.candidateAckingStatusVectors[b10.Hash] + s.Require().NotNil(vec) + s.Len(vec, 1) + s.Equal(vec[validators[1]].minHeight, b10.Height) + s.Equal(vec[validators[1]].count, uint64(3)) + + // Check b20. + vec = seq.candidateAckingStatusVectors[b20.Hash] + s.Require().NotNil(vec) + s.Len(vec, 1) + s.Equal(vec[validators[2]].minHeight, b20.Height) + s.Equal(vec[validators[2]].count, uint64(3)) + + // Check b30. + vec = seq.candidateAckingStatusVectors[b30.Hash] + s.Require().NotNil(vec) + s.Len(vec, 1) + s.Equal(vec[validators[3]].minHeight, b30.Height) + s.Equal(vec[validators[3]].count, uint64(3)) + + // Make sure b00 doesn't exist in current working set: + s.checkNotInWorkingSet(seq, b00) +} + +func (s *SequencerTestSuite) TestBasicCaseForK2() { + // It's a handcrafted test case. + seq := newSequencer(2, 3, 5) + validators := s.generateValidatorIDs(5) + + b00 := s.genRootBlock(validators[0], map[common.Hash]struct{}{}) + b10 := s.genRootBlock(validators[1], map[common.Hash]struct{}{}) + b20 := s.genRootBlock( + validators[2], map[common.Hash]struct{}{b10.Hash: struct{}{}}) + b30 := s.genRootBlock( + validators[3], map[common.Hash]struct{}{b20.Hash: struct{}{}}) + b40 := s.genRootBlock(validators[4], map[common.Hash]struct{}{}) + b11 := &types.Block{ + ProposerID: validators[1], + ParentHash: b10.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b10.Hash: struct{}{}, + b00.Hash: struct{}{}, + }, + } + b01 := &types.Block{ + ProposerID: validators[0], + ParentHash: b00.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b00.Hash: struct{}{}, + b11.Hash: struct{}{}, + }, + } + b21 := &types.Block{ + ProposerID: validators[2], + ParentHash: b20.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b20.Hash: struct{}{}, + b01.Hash: struct{}{}, + }, + } + b31 := &types.Block{ + ProposerID: validators[3], + ParentHash: b30.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b30.Hash: struct{}{}, + b21.Hash: struct{}{}, + }, + } + b02 := &types.Block{ + ProposerID: validators[0], + ParentHash: b01.Hash, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + b01.Hash: struct{}{}, + b21.Hash: struct{}{}, + }, + } + b12 := &types.Block{ + ProposerID: validators[1], + ParentHash: b11.Hash, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + b11.Hash: struct{}{}, + b21.Hash: struct{}{}, + }, + } + b32 := &types.Block{ + ProposerID: validators[3], + ParentHash: b31.Hash, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + b31.Hash: struct{}{}, + }, + } + b22 := &types.Block{ + ProposerID: validators[2], + ParentHash: b21.Hash, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + b21.Hash: struct{}{}, + b32.Hash: struct{}{}, + }, + } + b23 := &types.Block{ + ProposerID: validators[2], + ParentHash: b22.Hash, + Hash: common.NewRandomHash(), + Height: 3, + Acks: map[common.Hash]struct{}{ + b22.Hash: struct{}{}, + }, + } + b03 := &types.Block{ + ProposerID: validators[0], + ParentHash: b02.Hash, + Hash: common.NewRandomHash(), + Height: 3, + Acks: map[common.Hash]struct{}{ + b02.Hash: struct{}{}, + b22.Hash: struct{}{}, + }, + } + b13 := &types.Block{ + ProposerID: validators[1], + ParentHash: b12.Hash, + Hash: common.NewRandomHash(), + Height: 3, + Acks: map[common.Hash]struct{}{ + b12.Hash: struct{}{}, + b22.Hash: struct{}{}, + }, + } + b14 := &types.Block{ + ProposerID: validators[1], + ParentHash: b13.Hash, + Hash: common.NewRandomHash(), + Height: 4, + Acks: map[common.Hash]struct{}{ + b13.Hash: struct{}{}, + }, + } + b41 := &types.Block{ + ProposerID: validators[4], + ParentHash: b40.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b40.Hash: struct{}{}, + }, + } + b42 := &types.Block{ + ProposerID: validators[4], + ParentHash: b41.Hash, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + b41.Hash: struct{}{}, + }, + } + + s.checkNotDeliver(seq, b00) + s.checkNotDeliver(seq, b10) + s.checkNotDeliver(seq, b11) + s.checkNotDeliver(seq, b01) + s.checkNotDeliver(seq, b20) + s.checkNotDeliver(seq, b30) + s.checkNotDeliver(seq, b21) + s.checkNotDeliver(seq, b31) + s.checkNotDeliver(seq, b32) + s.checkNotDeliver(seq, b22) + s.checkNotDeliver(seq, b12) + + // Make sure 'acked' for current precedings is correct. + acked := seq.acked[b00.Hash] + s.Require().NotNil(acked) + s.Len(acked, 7) + s.Contains(acked, b01.Hash) + s.Contains(acked, b11.Hash) + s.Contains(acked, b12.Hash) + s.Contains(acked, b21.Hash) + s.Contains(acked, b22.Hash) + s.Contains(acked, b31.Hash) + s.Contains(acked, b32.Hash) + + acked = seq.acked[b10.Hash] + s.Require().NotNil(acked) + s.Len(acked, 9) + s.Contains(acked, b01.Hash) + s.Contains(acked, b11.Hash) + s.Contains(acked, b12.Hash) + s.Contains(acked, b20.Hash) + s.Contains(acked, b21.Hash) + s.Contains(acked, b22.Hash) + s.Contains(acked, b30.Hash) + s.Contains(acked, b31.Hash) + s.Contains(acked, b32.Hash) + + // Make sure there are 2 candidates. + s.Require().Len(seq.candidateAckingStatusVectors, 2) + + // Check b00's height vector. + vec := seq.candidateAckingStatusVectors[b00.Hash] + s.Require().NotNil(vec) + s.NotContains(vec, validators[4]) + s.Equal(vec[validators[0]].minHeight, b00.Height) + s.Equal(vec[validators[0]].count, uint64(2)) + s.Equal(vec[validators[1]].minHeight, b11.Height) + s.Equal(vec[validators[1]].count, uint64(2)) + s.Equal(vec[validators[2]].minHeight, b21.Height) + s.Equal(vec[validators[2]].count, uint64(2)) + s.Equal(vec[validators[3]].minHeight, b31.Height) + s.Equal(vec[validators[3]].count, uint64(2)) + + // Check b10's height vector. + vec = seq.candidateAckingStatusVectors[b10.Hash] + s.Require().NotNil(vec) + s.NotContains(vec, validators[4]) + s.Equal(vec[validators[0]].minHeight, b01.Height) + s.Equal(vec[validators[0]].count, uint64(1)) + s.Equal(vec[validators[1]].minHeight, b10.Height) + s.Equal(vec[validators[1]].count, uint64(3)) + s.Equal(vec[validators[2]].minHeight, b20.Height) + s.Equal(vec[validators[2]].count, uint64(3)) + s.Equal(vec[validators[3]].minHeight, b30.Height) + s.Equal(vec[validators[3]].count, uint64(3)) + + // Check the first deliver. + hashes, early, err := seq.processBlock(b02) + s.True(early) + s.Nil(err) + expected := common.Hashes{b00.Hash, b10.Hash} + sort.Sort(expected) + s.Equal(hashes, expected) + + // Make sure b00, b10 are removed from current working set. + s.checkNotInWorkingSet(seq, b00) + s.checkNotInWorkingSet(seq, b10) + + // Check if candidates of next round are picked correctly. + s.Len(seq.candidateAckingStatusVectors, 2) + + // Check b01's height vector. + vec = seq.candidateAckingStatusVectors[b11.Hash] + s.Require().NotNil(vec) + s.NotContains(vec, validators[4]) + s.Equal(vec[validators[0]].minHeight, b01.Height) + s.Equal(vec[validators[0]].count, uint64(2)) + s.Equal(vec[validators[1]].minHeight, b11.Height) + s.Equal(vec[validators[1]].count, uint64(2)) + s.Equal(vec[validators[2]].minHeight, b21.Height) + s.Equal(vec[validators[2]].count, uint64(2)) + s.Equal(vec[validators[3]].minHeight, b11.Height) + s.Equal(vec[validators[3]].count, uint64(2)) + + // Check b20's height vector. + vec = seq.candidateAckingStatusVectors[b20.Hash] + s.Require().NotNil(vec) + s.NotContains(vec, validators[4]) + s.Equal(vec[validators[0]].minHeight, b02.Height) + s.Equal(vec[validators[0]].count, uint64(1)) + s.Equal(vec[validators[1]].minHeight, b12.Height) + s.Equal(vec[validators[1]].count, uint64(1)) + s.Equal(vec[validators[2]].minHeight, b20.Height) + s.Equal(vec[validators[2]].count, uint64(3)) + s.Equal(vec[validators[3]].minHeight, b30.Height) + s.Equal(vec[validators[3]].count, uint64(3)) + + s.checkNotDeliver(seq, b13) + + // Check the second deliver. + hashes, early, err = seq.processBlock(b03) + s.True(early) + s.Nil(err) + expected = common.Hashes{b11.Hash, b20.Hash} + sort.Sort(expected) + s.Equal(hashes, expected) + + // Make sure b11, b20 are removed from current working set. + s.checkNotInWorkingSet(seq, b11) + s.checkNotInWorkingSet(seq, b20) + + // Add b40, b41, b42 to pending set. + s.checkNotDeliver(seq, b40) + s.checkNotDeliver(seq, b41) + s.checkNotDeliver(seq, b42) + s.checkNotDeliver(seq, b14) + + // Make sure b01, b30, b40 are candidate in next round. + s.Len(seq.candidateAckingStatusVectors, 3) + vec = seq.candidateAckingStatusVectors[b01.Hash] + s.Require().NotNil(vec) + s.NotContains(vec, validators[4]) + s.Equal(vec[validators[0]].minHeight, b01.Height) + s.Equal(vec[validators[0]].count, uint64(3)) + s.Equal(vec[validators[1]].minHeight, b12.Height) + s.Equal(vec[validators[1]].count, uint64(3)) + s.Equal(vec[validators[2]].minHeight, b21.Height) + s.Equal(vec[validators[2]].count, uint64(2)) + s.Equal(vec[validators[3]].minHeight, b31.Height) + s.Equal(vec[validators[3]].count, uint64(2)) + + vec = seq.candidateAckingStatusVectors[b30.Hash] + s.Require().NotNil(vec) + s.NotContains(vec, validators[4]) + s.Equal(vec[validators[0]].minHeight, b03.Height) + s.Equal(vec[validators[0]].count, uint64(1)) + s.Equal(vec[validators[1]].minHeight, b13.Height) + s.Equal(vec[validators[1]].count, uint64(2)) + s.Equal(vec[validators[2]].minHeight, b22.Height) + s.Equal(vec[validators[2]].count, uint64(1)) + s.Equal(vec[validators[3]].minHeight, b30.Height) + s.Equal(vec[validators[3]].count, uint64(3)) + + vec = seq.candidateAckingStatusVectors[b40.Hash] + s.Require().NotNil(vec) + s.NotContains(vec, validators[0]) + s.NotContains(vec, validators[1]) + s.NotContains(vec, validators[2]) + s.NotContains(vec, validators[3]) + s.Equal(vec[validators[4]].minHeight, b40.Height) + s.Equal(vec[validators[4]].count, uint64(3)) + + // Make 'Acking Node Set' contains blocks from all validators, + // this should trigger not-early deliver. + hashes, early, err = seq.processBlock(b23) + s.False(early) + s.Nil(err) + expected = common.Hashes{b01.Hash, b30.Hash} + sort.Sort(expected) + s.Equal(expected, hashes) + + // Make sure b01, b30 not in working set + s.checkNotInWorkingSet(seq, b01) + s.checkNotInWorkingSet(seq, b30) + + // Make sure b21, b40 are candidates of next round. + s.Contains(seq.candidateAckingStatusVectors, b21.Hash) + s.Contains(seq.candidateAckingStatusVectors, b40.Hash) +} + +func (s *SequencerTestSuite) TestBasicCaseForK0() { + // This is a relatively simple test for K=0. + // + // 0 1 2 3 4 + // ------------------- + // . . . . . + // . . . . . + // o o o <- o <- o Height: 1 + // | \ | \ | | + // v v v v + // o o o <- o Height: 0 + seq := newSequencer(0, 3, 5) + validators := s.generateValidatorIDs(5) + + b00 := s.genRootBlock(validators[0], map[common.Hash]struct{}{}) + b10 := s.genRootBlock(validators[1], map[common.Hash]struct{}{}) + b20 := s.genRootBlock(validators[2], map[common.Hash]struct{}{}) + b30 := s.genRootBlock(validators[3], map[common.Hash]struct{}{ + b20.Hash: struct{}{}, + }) + b01 := &types.Block{ + ProposerID: validators[0], + ParentHash: b00.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b00.Hash: struct{}{}, + b10.Hash: struct{}{}, + }, + } + b11 := &types.Block{ + ProposerID: validators[1], + ParentHash: b10.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b10.Hash: struct{}{}, + b20.Hash: struct{}{}, + }, + } + b21 := &types.Block{ + ProposerID: validators[2], + ParentHash: b20.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b20.Hash: struct{}{}, + }, + } + b31 := &types.Block{ + ProposerID: validators[3], + ParentHash: b30.Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + b21.Hash: struct{}{}, + b30.Hash: struct{}{}, + }, + } + b40 := s.genRootBlock(validators[4], map[common.Hash]struct{}{ + b31.Hash: struct{}{}, + }) + + s.checkNotDeliver(seq, b00) + s.checkNotDeliver(seq, b10) + s.checkNotDeliver(seq, b20) + s.checkNotDeliver(seq, b30) + s.checkNotDeliver(seq, b01) + s.checkNotDeliver(seq, b11) + s.checkNotDeliver(seq, b21) + s.checkNotDeliver(seq, b31) + + // Check status before delivering. + vec := seq.candidateAckingStatusVectors[b00.Hash] + s.Require().NotNil(vec) + s.Len(vec, 1) + s.Equal(vec[validators[0]].minHeight, b00.Height) + s.Equal(vec[validators[0]].count, uint64(2)) + + vec = seq.candidateAckingStatusVectors[b10.Hash] + s.Require().NotNil(vec) + s.Len(vec, 2) + s.Equal(vec[validators[0]].minHeight, b01.Height) + s.Equal(vec[validators[0]].count, uint64(1)) + s.Equal(vec[validators[1]].minHeight, b10.Height) + s.Equal(vec[validators[1]].count, uint64(2)) + + vec = seq.candidateAckingStatusVectors[b20.Hash] + s.Require().NotNil(vec) + s.Len(vec, 3) + s.Equal(vec[validators[1]].minHeight, b11.Height) + s.Equal(vec[validators[1]].count, uint64(1)) + s.Equal(vec[validators[2]].minHeight, b20.Height) + s.Equal(vec[validators[2]].count, uint64(2)) + s.Equal(vec[validators[3]].minHeight, b30.Height) + s.Equal(vec[validators[3]].count, uint64(2)) + + // This new block should trigger non-early deliver. + hashes, early, err := seq.processBlock(b40) + s.False(early) + s.Nil(err) + expected := common.Hashes{b20.Hash} + sort.Sort(expected) + s.Equal(expected, hashes) + + // Make sure b20 is no long existing in working set. + s.checkNotInWorkingSet(seq, b20) + + // Make sure b10, b30 are candidates for next round. + s.Contains(seq.candidateAckingStatusVectors, b10.Hash) + s.Contains(seq.candidateAckingStatusVectors, b30.Hash) +} + +func TestSequencer(t *testing.T) { + suite.Run(t, new(SequencerTestSuite)) +} -- cgit v1.2.3