diff options
Diffstat (limited to 'core')
| -rw-r--r-- | core/acking.go | 13 | ||||
| -rw-r--r-- | core/acking_test.go | 74 | ||||
| -rw-r--r-- | core/sequencer_test.go | 122 | ||||
| -rw-r--r-- | core/test/blocks-generator.go | 267 | ||||
| -rw-r--r-- | core/test/blocks-generator_test.go | 108 | ||||
| -rw-r--r-- | core/test/interface.go | 29 | ||||
| -rw-r--r-- | core/test/revealer.go | 200 | ||||
| -rw-r--r-- | core/test/revealer_test.go | 134 | ||||
| -rw-r--r-- | core/types/block_test.go | 17 |
9 files changed, 958 insertions, 6 deletions
diff --git a/core/acking.go b/core/acking.go index b74712d..47f13fb 100644 --- a/core/acking.go +++ b/core/acking.go @@ -96,8 +96,8 @@ func (a *acking) sanityCheck(b *types.Block) error { if _, exist := b.Acks[b.ParentHash]; !exist { return ErrNotAckParent } - bParent := a.blocks[b.ParentHash] - if bParent.Height != b.Height-1 { + bParent, exists := a.blocks[b.ParentHash] + if exists && bParent.Height != b.Height-1 { return ErrInvalidBlockHeight } } @@ -123,12 +123,13 @@ func (a *acking) areAllAcksInLattice(b *types.Block) bool { if !exist { return false } - if bAckInLattice, exist := a.lattice[bAck.ProposerID].blocks[bAck.Height]; !exist { - if bAckInLattice.Hash != bAck.Hash { - panic("areAllAcksInLattice: acking.lattice has corrupted") - } + bAckInLattice, exist := a.lattice[bAck.ProposerID].blocks[bAck.Height] + if !exist { return false } + if bAckInLattice.Hash != bAck.Hash { + panic("areAllAcksInLattice: acking.lattice has corrupted") + } } return true } diff --git a/core/acking_test.go b/core/acking_test.go index c0b6402..b1f26b2 100644 --- a/core/acking_test.go +++ b/core/acking_test.go @@ -19,11 +19,14 @@ package core import ( "math/rand" + "sort" "testing" "github.com/stretchr/testify/suite" + "github.com/dexon-foundation/dexon-consensus-core/blockdb" "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/test" "github.com/dexon-foundation/dexon-consensus-core/core/types" ) @@ -421,6 +424,77 @@ func (s *AckingTest) TestRandomIntensiveAcking() { s.True(len(a.blocks) < 500) } +func (s *AckingTest) TestRandomlyGeneratedBlocks() { + var ( + validatorCount = 19 + blockCount = 50 + repeat = 20 + ) + + // Prepare a randomly generated blocks. + db, err := blockdb.NewMemBackedBlockDB("test-acking-random.blockdb") + s.Require().Nil(err) + defer func() { + // If the test fails, keep the block database for troubleshooting. + if s.T().Failed() { + s.Nil(db.Close()) + } + }() + gen := test.NewBlocksGenerator(nil) + s.Require().Nil(gen.Generate(validatorCount, blockCount, nil, db)) + iter, err := db.GetAll() + s.Require().Nil(err) + // Setup a revealer that would reveal blocks randomly. + revealer, err := test.NewRandomRevealer(iter) + s.Require().Nil(err) + + stronglyAckedHashesAsString := map[string]struct{}{} + for i := 0; i < repeat; i++ { + validators := map[types.ValidatorID]struct{}{} + acking := newAcking() + stronglyAckedHashes := common.Hashes{} + revealer.Reset() + + for { + // Reveal next block. + b, err := revealer.Next() + if err != nil { + if err == blockdb.ErrIterationFinished { + err = nil + break + } + } + s.Require().Nil(err) + + // It's a hack to add validator to Acking module. + if _, added := validators[b.ProposerID]; !added { + acking.addValidator(b.ProposerID) + validators[b.ProposerID] = struct{}{} + } + // Perform reliable broadcast process. + acking.processBlock(&b) + for _, b := range acking.extractBlocks() { + stronglyAckedHashes = append(stronglyAckedHashes, b.Hash) + } + } + // To make it easier to check, sort hashes of + // strongly acked blocks, and concatenate them into + // a string. + sort.Sort(stronglyAckedHashes) + asString := "" + for _, h := range stronglyAckedHashes { + asString += h.String() + "," + } + stronglyAckedHashesAsString[asString] = struct{}{} + } + // Make sure concatenated hashes of strongly acked blocks are identical. + s.Require().Len(stronglyAckedHashesAsString, 1) + for h := range stronglyAckedHashesAsString { + // Make sure at least some blocks are strongly acked. + s.True(len(h) > 0) + } +} + func TestAcking(t *testing.T) { suite.Run(t, new(AckingTest)) } diff --git a/core/sequencer_test.go b/core/sequencer_test.go index fa8b461..ae9cca7 100644 --- a/core/sequencer_test.go +++ b/core/sequencer_test.go @@ -1,10 +1,30 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + package core import ( "sort" + "strings" "testing" + "github.com/dexon-foundation/dexon-consensus-core/blockdb" "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/test" "github.com/dexon-foundation/dexon-consensus-core/core/types" "github.com/stretchr/testify/suite" ) @@ -869,6 +889,108 @@ func (s *SequencerTestSuite) TestBasicCaseForK0() { s.Contains(seq.candidateAckingStatusVectors, b30.Hash) } +func (s *SequencerTestSuite) baseTestRandomlyGeneratedBlocks( + seqConstructor func() *sequencer, + revealer test.Revealer, + repeat int) { + + // TODO (mission): make this part run concurrently. + revealingSequence := map[string]struct{}{} + orderingSequence := map[string]struct{}{} + for i := 0; i < repeat; i++ { + revealed := "" + ordered := "" + revealer.Reset() + seq := seqConstructor() + for { + // Reveal next block. + b, err := revealer.Next() + if err != nil { + if err == blockdb.ErrIterationFinished { + err = nil + break + } + } + s.Require().Nil(err) + revealed += b.Hash.String() + "," + + // Perform total ordering. + hashes, _, err := seq.processBlock(&b) + s.Require().Nil(err) + for _, h := range hashes { + ordered += h.String() + "," + } + } + revealingSequence[revealed] = struct{}{} + orderingSequence[ordered] = struct{}{} + } + + // Make sure we test at least two different + // revealing sequence. + s.True(len(revealingSequence) > 1) + // Make sure all ordering are equal or prefixed + // to another one. + for orderFrom := range orderingSequence { + for orderTo := range orderingSequence { + if orderFrom == orderTo { + continue + } + ok := strings.HasPrefix(orderFrom, orderTo) || + strings.HasPrefix(orderTo, orderFrom) + s.True(ok) + } + } +} + +func (s *SequencerTestSuite) TestRandomlyGeneratedBlocks() { + var ( + validatorCount = 19 + blockCount = 50 + phi uint64 = 10 + repeat = 10 + ) + + // Prepare a randomly genearated blocks. + db, err := blockdb.NewMemBackedBlockDB("test-sequencer-random.blockdb") + s.Require().Nil(err) + defer func() { + // If the test fails, keep the block database for troubleshooting. + if s.T().Failed() { + s.Nil(db.Close()) + } + }() + + gen := test.NewBlocksGenerator(nil) + s.Require().Nil(gen.Generate(validatorCount, blockCount, nil, db)) + iter, err := db.GetAll() + s.Require().Nil(err) + // Setup a revealer that would reveal blocks forming + // valid DAGs. + revealer, err := test.NewRandomDAGRevealer(iter) + s.Require().Nil(err) + + // Test for K=0. + constructor := func() *sequencer { + return newSequencer(0, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) + // Test for K=1, + constructor = func() *sequencer { + return newSequencer(1, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) + // Test for K=2, + constructor = func() *sequencer { + return newSequencer(2, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) + // Test for K=3, + constructor = func() *sequencer { + return newSequencer(2, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) +} + func TestSequencer(t *testing.T) { suite.Run(t, new(SequencerTestSuite)) } diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go new file mode 100644 index 0000000..ae41757 --- /dev/null +++ b/core/test/blocks-generator.go @@ -0,0 +1,267 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + +package test + +import ( + "errors" + "math" + "math/rand" + "time" + + "github.com/dexon-foundation/dexon-consensus-core/blockdb" + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" +) + +// ErrParentNotAcked would be raised when some block doesn't +// ack its parent block. +var ErrParentNotAcked = errors.New("parent is not acked") + +// validatorStatus is a state holder for each validator +// during generating blocks. +type validatorStatus struct { + blocks []*types.Block + lastAckingHeight map[types.ValidatorID]uint64 +} + +// getAckedBlockHash would randomly pick one block between +// last acked one to current head. +func (vs *validatorStatus) getAckedBlockHash( + ackedVID types.ValidatorID, + ackedValidator *validatorStatus, + randGen *rand.Rand) ( + hash common.Hash, ok bool) { + + baseAckingHeight, exists := vs.lastAckingHeight[ackedVID] + if exists { + // Do not ack the same block(height) twice. + baseAckingHeight++ + } + totalBlockCount := uint64(len(ackedValidator.blocks)) + if totalBlockCount <= baseAckingHeight { + // There is no new block to ack. + return + } + ackableRange := totalBlockCount - baseAckingHeight + height := uint64((randGen.Uint64() % ackableRange) + baseAckingHeight) + vs.lastAckingHeight[ackedVID] = height + hash = ackedValidator.blocks[height].Hash + ok = true + return +} + +// validatorSetStatus is a state holder for all validators +// during generating blocks. +type validatorSetStatus struct { + status map[types.ValidatorID]*validatorStatus + validatorIDs []types.ValidatorID + randGen *rand.Rand +} + +func newValidatorSetStatus(vIDs []types.ValidatorID) *validatorSetStatus { + status := make(map[types.ValidatorID]*validatorStatus) + for _, vID := range vIDs { + status[vID] = &validatorStatus{ + blocks: []*types.Block{}, + lastAckingHeight: make(map[types.ValidatorID]uint64), + } + } + return &validatorSetStatus{ + status: status, + validatorIDs: vIDs, + randGen: rand.New(rand.NewSource(time.Now().UnixNano())), + } +} + +// findIncompleteValidators is a helper to check which validator +// doesn't generate enough blocks. +func (vs *validatorSetStatus) findIncompleteValidators( + blockCount int) (vIDs []types.ValidatorID) { + + for vID, status := range vs.status { + if len(status.blocks) < blockCount { + vIDs = append(vIDs, vID) + } + } + return +} + +// prepareAcksForNewBlock collects acks for one block. +func (vs *validatorSetStatus) prepareAcksForNewBlock( + proposerID types.ValidatorID, ackingCount int) ( + acks map[common.Hash]struct{}, err error) { + + acks = make(map[common.Hash]struct{}) + if len(vs.status[proposerID].blocks) == 0 { + // The 'Acks' filed of genesis blocks would always be empty. + return + } + // Pick validatorIDs to be acked. + ackingVIDs := map[types.ValidatorID]struct{}{ + proposerID: struct{}{}, // Acking parent block is always required. + } + if ackingCount > 0 { + ackingCount-- // We would always include ack to parent block. + } + for _, i := range vs.randGen.Perm(len(vs.validatorIDs))[:ackingCount] { + ackingVIDs[vs.validatorIDs[i]] = struct{}{} + } + // Generate acks. + for vID := range ackingVIDs { + ack, ok := vs.status[proposerID].getAckedBlockHash( + vID, vs.status[vID], vs.randGen) + if !ok { + if vID == proposerID { + err = ErrParentNotAcked + } + continue + } + acks[ack] = struct{}{} + } + return +} + +// proposeBlock propose new block and update validator status. +func (vs *validatorSetStatus) proposeBlock( + proposerID types.ValidatorID, + acks map[common.Hash]struct{}) *types.Block { + + status := vs.status[proposerID] + hash := common.NewRandomHash() + parentHash := hash + if len(status.blocks) > 0 { + parentHash = status.blocks[len(status.blocks)-1].Hash + } + + newBlock := &types.Block{ + ProposerID: proposerID, + ParentHash: parentHash, + Hash: hash, + Height: uint64(len(status.blocks)), + Acks: acks, + // TODO(mission.liao): Generate timestamp randomly. + } + status.blocks = append(status.blocks, newBlock) + return newBlock +} + +// normalAckingCountGenerator would randomly pick acking count +// by a normal distribution. +func normalAckingCountGenerator( + validatorCount int, mean, deviation float64) func() int { + + return func() int { + var expected float64 + for { + expected = rand.NormFloat64()*deviation + mean + if expected >= 0 && expected <= float64(validatorCount) { + break + } + } + return int(math.Ceil(expected)) + } +} + +// generateValidatorPicker is a function generator, which would generate +// a function to randomly pick one validator ID from a slice of validator ID. +func generateValidatorPicker() func([]types.ValidatorID) types.ValidatorID { + privateRand := rand.New(rand.NewSource(time.Now().UnixNano())) + return func(vIDs []types.ValidatorID) types.ValidatorID { + return vIDs[privateRand.Intn(len(vIDs))] + } +} + +// BlocksGenerator could generate blocks forming valid DAGs. +type BlocksGenerator struct { + validatorPicker func([]types.ValidatorID) types.ValidatorID +} + +// NewBlocksGenerator constructs BlockGenerator. +func NewBlocksGenerator(validatorPicker func( + []types.ValidatorID) types.ValidatorID) *BlocksGenerator { + + if validatorPicker == nil { + validatorPicker = generateValidatorPicker() + } + return &BlocksGenerator{ + validatorPicker: validatorPicker, + } +} + +// Generate is the entry point to generate blocks. The caller is responsible +// to provide a function to generate count of acked block for each new block. +// The prototype of ackingCountGenerator is a function returning 'int'. +// For example, if you need to generate a group of blocks and each of them +// has maximum 2 acks. +// func () int { return 2 } +// The default ackingCountGenerator would randomly pick a number based on +// the validatorCount you provided with a normal distribution. +func (gen *BlocksGenerator) Generate( + validatorCount int, + blockCount int, + ackingCountGenerator func() int, + writer blockdb.Writer) (err error) { + + if ackingCountGenerator == nil { + ackingCountGenerator = normalAckingCountGenerator( + validatorCount, + float64(validatorCount/2), + float64(validatorCount/4+1)) + } + validators := []types.ValidatorID{} + for i := 0; i < validatorCount; i++ { + validators = append( + validators, types.ValidatorID{Hash: common.NewRandomHash()}) + } + status := newValidatorSetStatus(validators) + + // We would record the smallest height of block that could be acked + // from each validator's point-of-view. + toAck := make(map[types.ValidatorID]map[types.ValidatorID]uint64) + for _, vID := range validators { + toAck[vID] = make(map[types.ValidatorID]uint64) + } + + for { + // Find validators that doesn't propose enough blocks and + // pick one from them randomly. + notYet := status.findIncompleteValidators(blockCount) + if len(notYet) == 0 { + break + } + + // Propose a new block. + var ( + proposerID = gen.validatorPicker(notYet) + acks map[common.Hash]struct{} + ) + acks, err = status.prepareAcksForNewBlock( + proposerID, ackingCountGenerator()) + if err != nil { + return + } + newBlock := status.proposeBlock(proposerID, acks) + + // Persist block to db. + err = writer.Put(*newBlock) + if err != nil { + return + } + } + return +} diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go new file mode 100644 index 0000000..b9c0b35 --- /dev/null +++ b/core/test/blocks-generator_test.go @@ -0,0 +1,108 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + +package test + +import ( + "sort" + "testing" + + "github.com/dexon-foundation/dexon-consensus-core/blockdb" + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" + "github.com/stretchr/testify/suite" +) + +type BlocksGeneratorTestCase struct { + suite.Suite +} + +func (s *BlocksGeneratorTestCase) TestGenerate() { + // This test case is to make sure the generated blocks are legimate. + validatorCount := 19 + blockCount := 50 + gen := NewBlocksGenerator(nil) + db, err := blockdb.NewMemBackedBlockDB() + s.Require().Nil(err) + + err = gen.Generate( + validatorCount, blockCount, nil, db) + s.Require().Nil(err) + + // Load all blocks in that database for further checking. + iter, err := db.GetAll() + s.Require().Nil(err) + blocksByValidator := make(map[types.ValidatorID][]*types.Block) + blocksByHash := make(map[common.Hash]*types.Block) + for { + block, err := iter.Next() + if err == blockdb.ErrIterationFinished { + break + } + s.Nil(err) + + blocksByValidator[block.ProposerID] = + append(blocksByValidator[block.ProposerID], &block) + sort.Sort(types.ByHeight(blocksByValidator[block.ProposerID])) + blocksByHash[block.Hash] = &block + } + + // Make sure these two rules are hold for these blocks: + // - No backward acking: the later block should only ack new blocks + // compared to its parent block. + // - Parent Ack: always ack its parent block. + // - No Acks in genesis bloc + for _, blocks := range blocksByValidator { + lastAckingHeights := map[types.ValidatorID]uint64{} + s.Require().NotEmpty(blocks) + + // Check genesis block. + genesisBlock := blocks[0] + s.Equal(genesisBlock.Hash, genesisBlock.ParentHash) + s.Equal(genesisBlock.Height, uint64(0)) + s.Empty(genesisBlock.Acks) + + // Check normal blocks. + for index, block := range blocks[1:] { + parentAcked := false + for ack := range block.Acks { + if ack == block.ParentHash { + parentAcked = true + } + + ackedBlock := blocksByHash[ack] + s.Require().NotNil(ackedBlock) + prevAckingHeight, exists := + lastAckingHeights[ackedBlock.ProposerID] + if exists { + s.True(prevAckingHeight < ackedBlock.Height) + } + lastAckingHeights[ackedBlock.ProposerID] = ackedBlock.Height + // Block Height should always incremental by 1. + // + // Because we iterate blocks slice from 1, + // we need to add 1 to the index. + s.Equal(block.Height, uint64(index+1)) + } + s.True(parentAcked) + } + } +} + +func TestBlocksGenerator(t *testing.T) { + suite.Run(t, new(BlocksGeneratorTestCase)) +} diff --git a/core/test/interface.go b/core/test/interface.go new file mode 100644 index 0000000..6c7b22e --- /dev/null +++ b/core/test/interface.go @@ -0,0 +1,29 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + +package test + +import "github.com/dexon-foundation/dexon-consensus-core/blockdb" + +// Revealer defines the interface to reveal a group +// of pre-generated blocks. +type Revealer interface { + blockdb.BlockIterator + + // Reset the revealing. + Reset() +} diff --git a/core/test/revealer.go b/core/test/revealer.go new file mode 100644 index 0000000..f1e3d1a --- /dev/null +++ b/core/test/revealer.go @@ -0,0 +1,200 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + +package test + +import ( + "math/rand" + "sort" + "time" + + "github.com/dexon-foundation/dexon-consensus-core/blockdb" + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" +) + +// isAllAckingBlockRevealed is a helper to check if all acking blocks of +// one block are revealed. +func isAllAckingBlockRevealed( + b *types.Block, revealed map[common.Hash]struct{}) bool { + + for ack := range b.Acks { + if _, exists := revealed[ack]; !exists { + return false + } + } + return true +} + +// loadAllBlocks is a helper to load all blocks from blockdb.BlockIterator. +func loadAllBlocks(iter blockdb.BlockIterator) ( + blocks map[common.Hash]*types.Block, err error) { + + blocks = make(map[common.Hash]*types.Block) + for { + block, err := iter.Next() + if err != nil { + if err == blockdb.ErrIterationFinished { + // It's safe to ignore iteraion-finished error. + err = nil + } + break + } + blocks[block.Hash] = &block + } + return +} + +// RandomDAGRevealer implements Revealer interface, which would load +// all blocks from blockdb, and randomly pick one block to reveal if +// it still forms a valid DAG in revealed blocks. +type RandomDAGRevealer struct { + // blocksByValidator group all blocks by validators and sorting + // them by height. + blocksByValidator map[types.ValidatorID][]*types.Block + // tipIndexes store the height of next block from one validator + // to check if is candidate. + tipIndexes map[types.ValidatorID]int + // candidate are blocks that forms valid DAG with + // current revealed blocks. + candidates []*types.Block + // revealed stores block hashes of current revealed blocks. + revealed map[common.Hash]struct{} + randGen *rand.Rand +} + +// NewRandomDAGRevealer constructs RandomDAGRevealer. +func NewRandomDAGRevealer( + iter blockdb.BlockIterator) (r *RandomDAGRevealer, err error) { + + blocks, err := loadAllBlocks(iter) + if err != nil { + return + } + + // Rearrange blocks by validators and height. + blocksByValidator := make(map[types.ValidatorID][]*types.Block) + for _, block := range blocks { + blocksByValidator[block.ProposerID] = + append(blocksByValidator[block.ProposerID], block) + } + // Make sure blocks are sorted by block heights, from lower to higher. + for vID := range blocksByValidator { + sort.Sort(types.ByHeight(blocksByValidator[vID])) + } + r = &RandomDAGRevealer{ + blocksByValidator: blocksByValidator, + randGen: rand.New(rand.NewSource(time.Now().UnixNano())), + } + // Make sure this revealer is ready to use. + r.Reset() + return +} + +// pickCandidates is a helper function to pick candidates from current tips. +func (r *RandomDAGRevealer) pickCandidates() { + for vID, tip := range r.tipIndexes { + blocks, exists := r.blocksByValidator[vID] + if !exists { + continue + } + if tip >= len(blocks) { + continue + } + block := blocks[tip] + if isAllAckingBlockRevealed(block, r.revealed) { + r.tipIndexes[vID]++ + r.candidates = append(r.candidates, block) + } + } +} + +// Next implement Revealer.Next method, which would reveal blocks +// forming valid DAGs. +func (r *RandomDAGRevealer) Next() (types.Block, error) { + if len(r.candidates) == 0 { + r.pickCandidates() + if len(r.candidates) == 0 { + return types.Block{}, blockdb.ErrIterationFinished + } + } + + // Pick next block to be revealed. + picked := r.randGen.Intn(len(r.candidates)) + block := r.candidates[picked] + r.candidates = + append(r.candidates[:picked], r.candidates[picked+1:]...) + r.revealed[block.Hash] = struct{}{} + r.pickCandidates() + return *block, nil +} + +// Reset implement Revealer.Reset method, which would reset the revealing. +func (r *RandomDAGRevealer) Reset() { + r.tipIndexes = make(map[types.ValidatorID]int) + for vID := range r.blocksByValidator { + r.tipIndexes[vID] = 0 + } + r.revealed = make(map[common.Hash]struct{}) + r.candidates = []*types.Block{} +} + +// RandomRevealer implements Revealer interface, which would load +// all blocks from blockdb, and randomly pick one block to reveal. +type RandomRevealer struct { + blocks map[common.Hash]*types.Block + remains common.Hashes + randGen *rand.Rand +} + +// NewRandomRevealer constructs RandomRevealer. +func NewRandomRevealer( + iter blockdb.BlockIterator) (r *RandomRevealer, err error) { + + blocks, err := loadAllBlocks(iter) + if err != nil { + return + } + r = &RandomRevealer{ + blocks: blocks, + randGen: rand.New(rand.NewSource(time.Now().UnixNano())), + } + r.Reset() + return +} + +// Next implements Revealer.Next method, which would reveal blocks randomly. +func (r *RandomRevealer) Next() (types.Block, error) { + if len(r.remains) == 0 { + return types.Block{}, blockdb.ErrIterationFinished + } + + picked := r.randGen.Intn(len(r.remains)) + block := r.blocks[r.remains[picked]] + r.remains = + append(r.remains[:picked], r.remains[picked+1:]...) + return *block, nil +} + +// Reset implement Revealer.Reset method, which would reset revealing. +func (r *RandomRevealer) Reset() { + hashes := common.Hashes{} + for hash := range r.blocks { + hashes = append(hashes, hash) + } + r.remains = hashes +} diff --git a/core/test/revealer_test.go b/core/test/revealer_test.go new file mode 100644 index 0000000..0ef19a1 --- /dev/null +++ b/core/test/revealer_test.go @@ -0,0 +1,134 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + +package test + +import ( + "testing" + + "github.com/dexon-foundation/dexon-consensus-core/blockdb" + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" + "github.com/stretchr/testify/suite" +) + +type RevealerTestSuite struct { + suite.Suite + + db blockdb.BlockDatabase + totalBlockCount int +} + +func (s *RevealerTestSuite) SetupSuite() { + var ( + err error + validatorCount = 19 + blockCount = 50 + ) + // Setup block database. + s.db, err = blockdb.NewMemBackedBlockDB() + s.Require().Nil(err) + + // Randomly generate blocks. + gen := NewBlocksGenerator(nil) + err = gen.Generate( + validatorCount, blockCount, nil, s.db) + s.Require().Nil(err) + + // Cache the count of total generated block. + iter, err := s.db.GetAll() + s.Require().Nil(err) + blocks, err := loadAllBlocks(iter) + s.Require().Nil(err) + s.totalBlockCount = len(blocks) +} + +func (s *RevealerTestSuite) baseTest( + revealer Revealer, + repeat int, + checkFunc func(*types.Block, map[common.Hash]struct{})) { + + revealingSequence := map[string]struct{}{} + for i := 0; i < repeat; i++ { + revealed := map[common.Hash]struct{}{} + sequence := "" + for { + b, err := revealer.Next() + if err != nil { + if err == blockdb.ErrIterationFinished { + err = nil + break + } + s.Require().NotNil(err) + } + checkFunc(&b, revealed) + revealed[b.Hash] = struct{}{} + sequence += b.Hash.String() + "," + } + s.Len(revealed, s.totalBlockCount) + revealingSequence[sequence] = struct{}{} + revealer.Reset() + } + // It should be reasonable to reveal at least two + // different sequence. + s.True(len(revealingSequence) > 1) + +} + +func (s *RevealerTestSuite) TestRandomReveal() { + // This test case would make sure we could at least generate + // two different revealing sequence when revealing more than + // 10 times. + iter, err := s.db.GetAll() + s.Require().Nil(err) + revealer, err := NewRandomRevealer(iter) + s.Require().Nil(err) + + checkFunc := func(b *types.Block, revealed map[common.Hash]struct{}) { + // Make sure the revealer won't reveal the same block twice. + _, alreadyRevealed := revealed[b.Hash] + s.False(alreadyRevealed) + } + s.baseTest(revealer, 10, checkFunc) +} + +func (s *RevealerTestSuite) TestRandomDAGReveal() { + // This test case would make sure we could at least generate + // two different revealing sequence when revealing more than + // 10 times, and each of them would form valid DAGs during + // revealing. + + iter, err := s.db.GetAll() + s.Require().Nil(err) + revealer, err := NewRandomDAGRevealer(iter) + s.Require().Nil(err) + + checkFunc := func(b *types.Block, revealed map[common.Hash]struct{}) { + // Make sure this revealer won't reveal + // the same block twice. + _, alreadyRevealed := revealed[b.Hash] + s.False(alreadyRevealed) + // Make sure the newly revealed block would still + // form a valid DAG after added to revealed blocks. + s.True(isAllAckingBlockRevealed(b, revealed)) + } + s.baseTest(revealer, 10, checkFunc) +} + +func TestRevealer(t *testing.T) { + suite.Run(t, new(RevealerTestSuite)) +} diff --git a/core/types/block_test.go b/core/types/block_test.go index feca5b8..8297508 100644 --- a/core/types/block_test.go +++ b/core/types/block_test.go @@ -1,3 +1,20 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + package types import ( |