diff options
Diffstat (limited to 'core')
-rw-r--r-- | core/lattice-data.go | 2 | ||||
-rw-r--r-- | core/lattice-data_test.go | 29 | ||||
-rw-r--r-- | core/test/blocks-generator.go | 304 | ||||
-rw-r--r-- | core/test/blocks-generator_test.go | 255 | ||||
-rw-r--r-- | core/test/revealer_test.go | 28 | ||||
-rw-r--r-- | core/total-ordering_test.go | 46 |
6 files changed, 445 insertions, 219 deletions
diff --git a/core/lattice-data.go b/core/lattice-data.go index f0bda11..95e0f06 100644 --- a/core/lattice-data.go +++ b/core/lattice-data.go @@ -235,6 +235,8 @@ func (data *latticeData) sanityCheck(b *types.Block) error { if !config.isValidGenesisBlockTime(b) { return ErrIncorrectBlockTime } + // TODO(mission): make sure rounds between chainTip and current block + // don't expect blocks from this chain. } } else { if chainTip.Position.Round != b.Position.Round { diff --git a/core/lattice-data_test.go b/core/lattice-data_test.go index cb7d892..4636b0f 100644 --- a/core/lattice-data_test.go +++ b/core/lattice-data_test.go @@ -351,13 +351,13 @@ func (s *LatticeDataTestSuite) TestSanityCheck() { func (s *LatticeDataTestSuite) TestRandomlyGeneratedBlocks() { var ( - chainNum uint32 = 19 - blockNum = 50 - repeat = 20 - delivered []*types.Block - err error - req = s.Require() - datum []*latticeData + chainNum uint32 = 19 + repeat = 20 + delivered []*types.Block + err error + req = s.Require() + datum []*latticeData + genesisTime = time.Now().UTC() ) if testing.Short() { chainNum = 7 @@ -371,13 +371,20 @@ func (s *LatticeDataTestSuite) TestRandomlyGeneratedBlocks() { maxBlockTimeInterval: 1000 * time.Second, roundInterval: 1000 * time.Second, } - genesisConfig.setRoundBeginTime(time.Now().UTC()) + genesisConfig.setRoundBeginTime(genesisTime) // Prepare a randomly generated blocks. db, err := blockdb.NewMemBackedBlockDB() req.NoError(err) - gen := test.NewBlocksGenerator(nil, hashBlock) - _, err = gen.Generate(chainNum, blockNum, nil, db) - req.NoError(err) + gen := test.NewBlocksGenerator(&test.BlocksGeneratorConfig{ + NumChains: genesisConfig.numChains, + MinBlockTimeInterval: genesisConfig.minBlockTimeInterval, + MaxBlockTimeInterval: genesisConfig.maxBlockTimeInterval, + }, nil, hashBlock) + req.NoError(gen.Generate( + 0, + genesisTime, + genesisTime.Add(genesisConfig.roundInterval), + db)) iter, err := db.GetAll() req.NoError(err) // Setup a revealer that would reveal blocks randomly but still form diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go index 904ee7a..10ecc38 100644 --- a/core/test/blocks-generator.go +++ b/core/test/blocks-generator.go @@ -30,9 +30,6 @@ import ( "github.com/dexon-foundation/dexon-consensus-core/core/types" ) -// TODO(mission): blocks generator should generate blocks based on chain, -// not nodes. - // ErrParentNotAcked would be raised when some block doesn't // ack its parent block. var ErrParentNotAcked = errors.New("parent is not acked") @@ -40,110 +37,137 @@ var ErrParentNotAcked = errors.New("parent is not acked") // nodeStatus is a state holder for each node // during generating blocks. type nodeStatus struct { - blocks []*types.Block - lastAckingHeight map[types.NodeID]uint64 + blocks []*types.Block + genesisTime time.Time + prvKey crypto.PrivateKey + tip *types.Block + nextAckingIndex map[types.NodeID]uint64 } type hashBlockFn func(*types.Block) (common.Hash, error) // getAckedBlockHash would randomly pick one block between // last acked one to current head. -func (vs *nodeStatus) getAckedBlockHash( +func (ns *nodeStatus) getAckedBlockHash( ackedNID types.NodeID, ackedNode *nodeStatus, randGen *rand.Rand) ( hash common.Hash, ok bool) { - - baseAckingHeight, exists := vs.lastAckingHeight[ackedNID] - if exists { - // Do not ack the same block(height) twice. - baseAckingHeight++ - } + baseAckingIndex := ns.nextAckingIndex[ackedNID] totalBlockCount := uint64(len(ackedNode.blocks)) - if totalBlockCount <= baseAckingHeight { + if totalBlockCount <= baseAckingIndex { // There is no new block to ack. return } - ackableRange := totalBlockCount - baseAckingHeight - height := uint64((randGen.Uint64() % ackableRange) + baseAckingHeight) - vs.lastAckingHeight[ackedNID] = height - hash = ackedNode.blocks[height].Hash + ackableRange := totalBlockCount - baseAckingIndex + idx := uint64((randGen.Uint64() % ackableRange) + baseAckingIndex) + ns.nextAckingIndex[ackedNID] = idx + 1 + hash = ackedNode.blocks[idx].Hash ok = true return } +func (ns *nodeStatus) getNextBlockTime( + timePicker func(time.Time) time.Time) time.Time { + if ns.tip == nil { + return timePicker(ns.genesisTime) + } + return timePicker(ns.tip.Timestamp) +} + // nodeSetStatus is a state holder for all nodes // during generating blocks. type nodeSetStatus struct { + round uint64 status map[types.NodeID]*nodeStatus proposerChain map[types.NodeID]uint32 - timestamps []time.Time - nodeIDs []types.NodeID + endTime time.Time + nIDs []types.NodeID randGen *rand.Rand + timePicker func(time.Time) time.Time hashBlock hashBlockFn } func newNodeSetStatus( - nIDs []types.NodeID, hashBlock hashBlockFn) *nodeSetStatus { - - status := make(map[types.NodeID]*nodeStatus) - timestamps := make([]time.Time, 0, len(nIDs)) - proposerChain := make(map[types.NodeID]uint32) - for i, nID := range nIDs { + numChains uint32, + tips map[uint32]*types.Block, + round uint64, + genesisTime, endTime time.Time, + timePicker func(time.Time) time.Time, + hashBlock hashBlockFn) *nodeSetStatus { + var ( + status = make(map[types.NodeID]*nodeStatus) + proposerChain = make(map[types.NodeID]uint32) + nIDs = []types.NodeID{} + ) + for i := uint32(0); i < numChains; i++ { + prvKey, err := ecdsa.NewPrivateKey() + if err != nil { + panic(err) + } + nID := types.NewNodeID(prvKey.PublicKey()) + nIDs = append(nIDs, nID) status[nID] = &nodeStatus{ - blocks: []*types.Block{}, - lastAckingHeight: make(map[types.NodeID]uint64), + blocks: []*types.Block{}, + genesisTime: genesisTime, + prvKey: prvKey, + tip: tips[i], + nextAckingIndex: make(map[types.NodeID]uint64), } - timestamps = append(timestamps, time.Now().UTC()) - proposerChain[nID] = uint32(i) + proposerChain[nID] = i } return &nodeSetStatus{ + round: round, status: status, proposerChain: proposerChain, - timestamps: timestamps, - nodeIDs: nIDs, + endTime: endTime, + nIDs: nIDs, randGen: rand.New(rand.NewSource(time.Now().UnixNano())), + timePicker: timePicker, hashBlock: hashBlock, } } -// findIncompleteNodes is a helper to check which node -// doesn't generate enough blocks. -func (vs *nodeSetStatus) findIncompleteNodes( - blockNum int) (nIDs []types.NodeID) { - - for nID, status := range vs.status { - if len(status.blocks) < blockNum { +// findIncompleteNodes is a helper to check which node doesn't generate +// enough blocks. +func (ns *nodeSetStatus) findIncompleteNodes() (nIDs []types.NodeID) { + for nID, status := range ns.status { + if status.tip == nil { nIDs = append(nIDs, nID) + continue + } + if status.tip.Timestamp.After(ns.endTime) { + continue } + nIDs = append(nIDs, nID) } return } // prepareAcksForNewBlock collects acks for one block. -func (vs *nodeSetStatus) prepareAcksForNewBlock( +func (ns *nodeSetStatus) prepareAcksForNewBlock( proposerID types.NodeID, ackingCount int) ( acks common.Hashes, err error) { - acks = common.Hashes{} - if len(vs.status[proposerID].blocks) == 0 { + if len(ns.status[proposerID].blocks) == 0 { // The 'Acks' filed of genesis blocks would always be empty. return } // Pick nodeIDs to be acked. - ackingNIDs := map[types.NodeID]struct{}{ - proposerID: struct{}{}, // Acking parent block is always required. - } + ackingNIDs := map[types.NodeID]struct{}{} if ackingCount > 0 { ackingCount-- // We would always include ack to parent block. } - for _, i := range vs.randGen.Perm(len(vs.nodeIDs))[:ackingCount] { - ackingNIDs[vs.nodeIDs[i]] = struct{}{} + for _, i := range ns.randGen.Perm(len(ns.nIDs))[:ackingCount] { + ackingNIDs[ns.nIDs[i]] = struct{}{} } // Generate acks. for nID := range ackingNIDs { - ack, ok := vs.status[proposerID].getAckedBlockHash( - nID, vs.status[nID], vs.randGen) + if nID == proposerID { + continue + } + ack, ok := ns.status[proposerID].getAckedBlockHash( + nID, ns.status[nID], ns.randGen) if !ok { if nID == proposerID { err = ErrParentNotAcked @@ -156,44 +180,39 @@ func (vs *nodeSetStatus) prepareAcksForNewBlock( } // proposeBlock propose new block and update node status. -func (vs *nodeSetStatus) proposeBlock( - proposerID types.NodeID, - prvKey crypto.PrivateKey, - acks common.Hashes) (*types.Block, error) { - - status := vs.status[proposerID] +func (ns *nodeSetStatus) proposeBlock( + proposerID types.NodeID, acks common.Hashes) (*types.Block, error) { + status := ns.status[proposerID] parentHash := common.Hash{} - if len(status.blocks) > 0 { - parentHash = status.blocks[len(status.blocks)-1].Hash + blockHeight := uint64(0) + if status.tip != nil { + parentHash = status.tip.Hash + blockHeight = status.tip.Position.Height + 1 + acks = append(acks, parentHash) } - chainID := vs.proposerChain[proposerID] - vs.timestamps[chainID] = vs.timestamps[chainID].Add(time.Second) - + chainID := ns.proposerChain[proposerID] newBlock := &types.Block{ ProposerID: proposerID, ParentHash: parentHash, Position: types.Position{ - Height: uint64(len(status.blocks)), + Round: ns.round, + Height: blockHeight, ChainID: chainID, }, Acks: common.NewSortedHashes(acks), - Timestamp: vs.timestamps[chainID], - } - for i, nID := range vs.nodeIDs { - if nID == proposerID { - newBlock.Position.ChainID = uint32(i) - } + Timestamp: status.getNextBlockTime(ns.timePicker), } var err error - newBlock.Hash, err = vs.hashBlock(newBlock) + newBlock.Hash, err = ns.hashBlock(newBlock) if err != nil { return nil, err } - newBlock.Signature, err = prvKey.Sign(newBlock.Hash) + newBlock.Signature, err = status.prvKey.Sign(newBlock.Hash) if err != nil { return nil, err } status.blocks = append(status.blocks, newBlock) + status.tip = newBlock return newBlock, nil } @@ -201,7 +220,6 @@ func (vs *nodeSetStatus) proposeBlock( // by a normal distribution. func normalAckingCountGenerator( chainNum uint32, mean, deviation float64) func() int { - return func() int { var expected float64 for { @@ -229,99 +247,139 @@ func generateNodePicker() func([]types.NodeID) types.NodeID { } } -// BlocksGenerator could generate blocks forming valid DAGs. -type BlocksGenerator struct { - nodePicker func([]types.NodeID) types.NodeID - hashBlock hashBlockFn +// defaultTimePicker would pick a time based on reference time and +// the given minimum/maximum time range. +func generateTimePicker(min, max time.Duration) (f func(time.Time) time.Time) { + privateRand := rand.New(rand.NewSource(time.Now().UnixNano())) + return func(ref time.Time) time.Time { + return ref.Add(min + time.Duration(privateRand.Int63n(int64(max-min)))) + } } -// NewBlocksGenerator constructs BlockGenerator. -func NewBlocksGenerator(nodePicker func( - []types.NodeID) types.NodeID, - hashBlock hashBlockFn) *BlocksGenerator { +// BlocksGeneratorConfig is the configuration for BlocksGenerator. +type BlocksGeneratorConfig struct { + NumChains uint32 + MinBlockTimeInterval time.Duration + MaxBlockTimeInterval time.Duration +} - if nodePicker == nil { - nodePicker = generateNodePicker() - } - return &BlocksGenerator{ - nodePicker: nodePicker, - hashBlock: hashBlock, - } +// BlocksGenerator could generate blocks forming valid DAGs. +type BlocksGenerator struct { + config *BlocksGeneratorConfig + nodePicker func([]types.NodeID) types.NodeID + timePicker func(time.Time) time.Time + ackingCountGenerator func() int + hashBlock hashBlockFn } -// 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. +// NewBlocksGenerator constructs BlockGenerator. +// +// 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 nodeCount you provided with a normal distribution. -func (gen *BlocksGenerator) Generate( - chainNum uint32, - blockNum int, +func NewBlocksGenerator( + config *BlocksGeneratorConfig, ackingCountGenerator func() int, - writer blockdb.Writer) ( - nodePrvKeys map[types.NodeID]crypto.PrivateKey, err error) { - - var ( - prvKey crypto.PrivateKey - nodes = types.NodeIDs{} - ) + hashBlock hashBlockFn) *BlocksGenerator { if ackingCountGenerator == nil { ackingCountGenerator = normalAckingCountGenerator( - chainNum, - float64(chainNum/2), - float64(chainNum/4+1)) + config.NumChains, + float64(config.NumChains/2), + float64(config.NumChains/4+1)) + } + timePicker := generateTimePicker( + config.MinBlockTimeInterval, config.MaxBlockTimeInterval) + return &BlocksGenerator{ + config: config, + nodePicker: generateNodePicker(), + timePicker: timePicker, + ackingCountGenerator: ackingCountGenerator, + hashBlock: hashBlock, } - nodePrvKeys = map[types.NodeID]crypto.PrivateKey{} - for i := uint32(0); i < chainNum; i++ { - if prvKey, err = ecdsa.NewPrivateKey(); err != nil { +} + +// Generate is the entry point to generate blocks in one round. +func (gen *BlocksGenerator) Generate( + roundID uint64, + roundBegin, roundEnd time.Time, + db blockdb.BlockDatabase) (err error) { + // Find tips of previous round if available. + tips := make(map[uint32]*types.Block) + if roundID > 0 { + tips, err = gen.findTips(roundID-1, db) + if err != nil { return } - id := types.NewNodeID(prvKey.PublicKey()) - nodes = append(nodes, id) - nodePrvKeys[id] = prvKey } - status := newNodeSetStatus(nodes, gen.hashBlock) - + status := newNodeSetStatus(gen.config.NumChains, tips, roundID, + roundBegin, roundEnd, gen.timePicker, gen.hashBlock) // We would record the smallest height of block that could be acked // from each node's point-of-view. toAck := make(map[types.NodeID]map[types.NodeID]uint64) - for _, nID := range nodes { + for _, nID := range status.nIDs { toAck[nID] = make(map[types.NodeID]uint64) } - for { // Find nodes that doesn't propose enough blocks and // pick one from them randomly. - notYet := status.findIncompleteNodes(blockNum) + notYet := status.findIncompleteNodes() if len(notYet) == 0 { break } - // Propose a new block. var ( proposerID = gen.nodePicker(notYet) acks common.Hashes ) - acks, err = status.prepareAcksForNewBlock( - proposerID, ackingCountGenerator()) - if err != nil { + if acks, err = status.prepareAcksForNewBlock( + proposerID, gen.ackingCountGenerator()); err != nil { return } var newBlock *types.Block - if newBlock, err = status.proposeBlock( - proposerID, nodePrvKeys[proposerID], acks); err != nil { - + if newBlock, err = status.proposeBlock(proposerID, acks); err != nil { return } - // Persist block to db. - err = writer.Put(*newBlock) - if err != nil { + if err = db.Put(*newBlock); err != nil { return } } return } + +// findTips is an utility to find tips of each chain in that round in blockdb. +func (gen *BlocksGenerator) findTips( + round uint64, db blockdb.Reader) (tips map[uint32]*types.Block, err error) { + iter, err := db.GetAll() + if err != nil { + return + } + revealer, err := NewRandomRevealer(iter) + if err != nil { + return + } + tips = make(map[uint32]*types.Block) + for { + var b types.Block + if b, err = revealer.Next(); err != nil { + if err == blockdb.ErrIterationFinished { + err = nil + break + } + return + } + if b.Position.Round != round { + continue + } + tip, exists := tips[b.Position.ChainID] + if exists && tip.Position.Height > b.Position.Height { + continue + } + tips[b.Position.ChainID] = &b + } + return +} diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go index 1baa9c5..0477664 100644 --- a/core/test/blocks-generator_test.go +++ b/core/test/blocks-generator_test.go @@ -20,6 +20,7 @@ package test import ( "sort" "testing" + "time" "github.com/dexon-foundation/dexon-consensus-core/common" "github.com/dexon-foundation/dexon-consensus-core/core/blockdb" @@ -27,27 +28,29 @@ import ( "github.com/stretchr/testify/suite" ) -type BlocksGeneratorTestCase struct { +type BlocksGeneratorTestSuite struct { suite.Suite } -func (s *BlocksGeneratorTestCase) TestGenerate() { +func (s *BlocksGeneratorTestSuite) TestGenerate() { // This test case is to make sure the generated blocks are legimate. var ( - chainNum = uint32(19) - blockNum = 50 + config = &BlocksGeneratorConfig{ + NumChains: 19, + MinBlockTimeInterval: 50 * time.Millisecond, + MaxBlockTimeInterval: 400 * time.Millisecond, + } + gen = NewBlocksGenerator(config, nil, stableRandomHash) + req = s.Require() + beginTime = time.Now().UTC() + endTime = beginTime.Add(time.Minute) ) - gen := NewBlocksGenerator(nil, stableRandomHash) db, err := blockdb.NewMemBackedBlockDB() - s.Require().Nil(err) - - keys, err := gen.Generate(chainNum, blockNum, nil, db) - s.Require().Nil(err) - s.Require().Len(keys, int(chainNum)) - + req.NoError(err) + req.NoError(gen.Generate(1, beginTime, endTime, db)) // Load all blocks in that database for further checking. iter, err := db.GetAll() - s.Require().Nil(err) + req.NoError(err) blocksByNode := make(map[types.NodeID][]*types.Block) blocksByHash := make(map[common.Hash]*types.Block) for { @@ -55,34 +58,33 @@ func (s *BlocksGeneratorTestCase) TestGenerate() { if err == blockdb.ErrIterationFinished { break } - s.Nil(err) - + req.NoError(err) // TODO(mission): Make sure each block is correctly signed once // we have a way to access core.hashBlock. - s.Require().NotEqual(block.Hash, common.Hash{}) - s.Require().NotEmpty(block.Signature) - + req.NotEqual(block.Hash, common.Hash{}) + req.NotEmpty(block.Signature) + req.Equal(block.Position.Round, uint64(1)) blocksByNode[block.ProposerID] = append(blocksByNode[block.ProposerID], &block) sort.Sort(types.ByHeight(blocksByNode[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. + // - Timestamp: timestamp are increasing, and with valid interval to + // previous block. + // - The last block of each chain should pass endTime. // - No Acks in genesis bloc for _, blocks := range blocksByNode { lastAckingHeights := map[types.NodeID]uint64{} - s.Require().NotEmpty(blocks) - + req.NotEmpty(blocks) // Check genesis block. genesisBlock := blocks[0] - s.Equal(genesisBlock.ParentHash, common.Hash{}) - s.Equal(genesisBlock.Position.Height, uint64(0)) - s.Empty(genesisBlock.Acks) - + req.Equal(genesisBlock.ParentHash, common.Hash{}) + req.Equal(genesisBlock.Position.Height, uint64(0)) + req.Empty(genesisBlock.Acks) // Check normal blocks. for index, block := range blocks[1:] { parentAcked := false @@ -90,9 +92,8 @@ func (s *BlocksGeneratorTestCase) TestGenerate() { if ack == block.ParentHash { parentAcked = true } - ackedBlock := blocksByHash[ack] - s.Require().NotNil(ackedBlock) + req.NotNil(ackedBlock) prevAckingHeight, exists := lastAckingHeights[ackedBlock.ProposerID] if exists { @@ -103,61 +104,70 @@ func (s *BlocksGeneratorTestCase) TestGenerate() { // // Because we iterate blocks slice from 1, // we need to add 1 to the index. - s.Equal(block.Position.Height, uint64(index+1)) + req.Equal(block.Position.Height, uint64(index+1)) } - s.True(parentAcked) + req.True(parentAcked) } + // The block time of the last block should be after end time. + req.True(blocks[len(blocks)-1].Timestamp.After(endTime)) } } -func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() { +func (s *BlocksGeneratorTestSuite) TestGenerateWithMaxAckCount() { var ( - chainNum = uint32(13) - blockNum = 50 - gen = NewBlocksGenerator(nil, stableRandomHash) + config = &BlocksGeneratorConfig{ + NumChains: 13, + MinBlockTimeInterval: 0, + MaxBlockTimeInterval: 500 * time.Millisecond, + } req = s.Require() totalAckingCount = 0 totalBlockCount = 0 + genesisTime = time.Now().UTC() ) - // Generate with 0 acks. db, err := blockdb.NewMemBackedBlockDB() - req.Nil(err) - keys, err := gen.Generate( - chainNum, blockNum, MaxAckingCountGenerator(0), db) - req.Nil(err) - req.Len(keys, int(chainNum)) + req.NoError(err) + gen := NewBlocksGenerator( + config, MaxAckingCountGenerator(0), stableRandomHash) + req.NoError(gen.Generate( + 0, + genesisTime, + genesisTime.Add(50*time.Second), + db)) // Load blocks to check their acking count. iter, err := db.GetAll() - req.Nil(err) + req.NoError(err) for { block, err := iter.Next() if err == blockdb.ErrIterationFinished { break } - req.Nil(err) + req.NoError(err) if block.IsGenesis() { continue } req.Len(block.Acks, 1) } - // Generate with acks as many as possible. db, err = blockdb.NewMemBackedBlockDB() - req.Nil(err) - keys, err = gen.Generate( - chainNum, blockNum, MaxAckingCountGenerator(chainNum), db) - req.Nil(err) - req.Len(keys, int(chainNum)) + req.NoError(err) + gen = NewBlocksGenerator( + config, MaxAckingCountGenerator(config.NumChains), stableRandomHash) + req.NoError(gen.Generate( + 0, + genesisTime, + genesisTime.Add(50*time.Second), + db)) // Load blocks to verify the average acking count. iter, err = db.GetAll() - req.Nil(err) + req.NoError(err) for { block, err := iter.Next() if err == blockdb.ErrIterationFinished { break } - req.Nil(err) + req.NoError(err) if block.IsGenesis() { continue } @@ -165,9 +175,154 @@ func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() { totalBlockCount++ } req.NotZero(totalBlockCount) - req.True((totalAckingCount / totalBlockCount) >= int(chainNum/2)) + req.True((totalAckingCount / totalBlockCount) >= int(config.NumChains/2)) +} + +// TestFindTips make sure findTips works as expected. +func (s *BlocksGeneratorTestSuite) TestFindTips() { + var ( + config = &BlocksGeneratorConfig{ + NumChains: 10, + MinBlockTimeInterval: 0, + MaxBlockTimeInterval: 500 * time.Millisecond, + } + req = s.Require() + genesisTime = time.Now().UTC() + endTime = genesisTime.Add(100 * time.Second) + ) + gen := NewBlocksGenerator(config, nil, stableRandomHash) + db, err := blockdb.NewMemBackedBlockDB() + req.NoError(err) + req.NoError(gen.Generate( + 0, + genesisTime, + endTime, + db)) + tips, err := gen.findTips(0, db) + req.NoError(err) + req.Len(tips, int(config.NumChains)) + for _, b := range tips { + req.True(b.Timestamp.After(endTime)) + } +} + +func (s *BlocksGeneratorTestSuite) TestConcateBlocksFromRounds() { + // This test case run these steps: + // - generate blocks by round but sharing one blockdb. + // - if those rounds are continuous, they should be concated. + var ( + req = s.Require() + genesisTime = time.Now().UTC() + ) + db, err := blockdb.NewMemBackedBlockDB() + req.NoError(err) + // Generate round 0 blocks. + gen := NewBlocksGenerator(&BlocksGeneratorConfig{ + NumChains: 4, + MinBlockTimeInterval: 0, + MaxBlockTimeInterval: 500 * time.Millisecond, + }, nil, stableRandomHash) + req.NoError(gen.Generate( + 0, + genesisTime, + genesisTime.Add(10*time.Second), + db)) + tips0, err := gen.findTips(0, db) + req.NoError(err) + req.Len(tips0, 4) + // Generate round 1 blocks. + gen = NewBlocksGenerator(&BlocksGeneratorConfig{ + NumChains: 10, + MinBlockTimeInterval: 0, + MaxBlockTimeInterval: 500 * time.Millisecond, + }, nil, stableRandomHash) + req.NoError(gen.Generate( + 1, + genesisTime.Add(10*time.Second), + genesisTime.Add(20*time.Second), + db)) + tips1, err := gen.findTips(1, db) + req.NoError(err) + req.Len(tips1, 10) + // Generate round 2 blocks. + gen = NewBlocksGenerator(&BlocksGeneratorConfig{ + NumChains: 7, + MinBlockTimeInterval: 0, + MaxBlockTimeInterval: 500 * time.Millisecond, + }, nil, stableRandomHash) + req.NoError(gen.Generate( + 2, + genesisTime.Add(20*time.Second), + genesisTime.Add(30*time.Second), + db)) + tips2, err := gen.findTips(2, db) + req.NoError(err) + req.Len(tips2, 7) + // Check results, make sure tips0, tips1 are acked by correct blocks. + iter, err := db.GetAll() + req.NoError(err) + revealer, err := NewRandomRevealer(iter) + req.NoError(err) + removeTip := func(tips map[uint32]*types.Block, b *types.Block) { + toRemove := []uint32{} + for chainID, tip := range tips { + if b.ParentHash == tip.Hash { + req.Equal(b.Position.Height, tip.Position.Height+1) + req.Equal(b.Position.Round, tip.Position.Round+1) + req.True(b.IsAcking(tip.Hash)) + toRemove = append(toRemove, chainID) + } + } + for _, ID := range toRemove { + delete(tips, ID) + } + } + // Make sure all tips are acked by loading blocks from db + // and check them one by one. + for { + b, err := revealer.Next() + if err != nil { + if err == blockdb.ErrIterationFinished { + err = nil + break + } + req.NoError(err) + } + switch b.Position.Round { + case 1: + removeTip(tips0, &b) + case 2: + removeTip(tips1, &b) + } + } + req.Empty(tips0) + req.Len(tips1, 3) + req.Contains(tips1, uint32(7)) + req.Contains(tips1, uint32(8)) + req.Contains(tips1, uint32(9)) + // Check the acking frequency of last round, it might be wrong. + totalBlockCount := 0 + totalAckCount := 0 + revealer.Reset() + for { + b, err := revealer.Next() + if err != nil { + if err == blockdb.ErrIterationFinished { + err = nil + break + } + req.NoError(err) + } + if b.Position.Round != 2 { + continue + } + totalBlockCount++ + totalAckCount += len(b.Acks) + } + // At least all blocks can ack some non-parent block. + req.True(totalAckCount/totalBlockCount >= 2) } func TestBlocksGenerator(t *testing.T) { - suite.Run(t, new(BlocksGeneratorTestCase)) + suite.Run(t, new(BlocksGeneratorTestSuite)) } diff --git a/core/test/revealer_test.go b/core/test/revealer_test.go index 859438c..8bb46bc 100644 --- a/core/test/revealer_test.go +++ b/core/test/revealer_test.go @@ -19,6 +19,7 @@ package test import ( "testing" + "time" "github.com/dexon-foundation/dexon-consensus-core/common" "github.com/dexon-foundation/dexon-consensus-core/core/blockdb" @@ -35,25 +36,30 @@ type RevealerTestSuite struct { func (s *RevealerTestSuite) SetupSuite() { var ( - err error - chainNum = uint32(19) - blockNum = 50 + err error + genesisTime = time.Now().UTC() ) // Setup block database. s.db, err = blockdb.NewMemBackedBlockDB() - s.Require().Nil(err) + s.Require().NoError(err) // Randomly generate blocks. - gen := NewBlocksGenerator(nil, stableRandomHash) - nodes, err := gen.Generate(chainNum, blockNum, nil, s.db) - s.Require().Nil(err) - s.Require().Len(nodes, int(chainNum)) - + config := &BlocksGeneratorConfig{ + NumChains: 19, + MinBlockTimeInterval: 0, + MaxBlockTimeInterval: 500 * time.Millisecond, + } + gen := NewBlocksGenerator(config, nil, stableRandomHash) + s.Require().NoError(gen.Generate( + 0, + genesisTime, + genesisTime.Add(30*time.Second), + s.db)) // Cache the count of total generated block. iter, err := s.db.GetAll() - s.Require().Nil(err) + s.Require().NoError(err) blocks, err := loadAllBlocks(iter) - s.Require().Nil(err) + s.Require().NoError(err) s.totalBlockCount = len(blocks) } diff --git a/core/total-ordering_test.go b/core/total-ordering_test.go index d66a8fe..262b5d9 100644 --- a/core/total-ordering_test.go +++ b/core/total-ordering_test.go @@ -21,6 +21,7 @@ import ( "sort" "strings" "testing" + "time" "github.com/dexon-foundation/dexon-consensus-core/common" "github.com/dexon-foundation/dexon-consensus-core/core/blockdb" @@ -866,30 +867,32 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks( totalOrderingConstructor func(chainNum uint32) *totalOrdering, chainNum uint32, - blockNum int, ackingCountGenerator func() int, repeat int) { - var ( req = s.Require() - gen = test.NewBlocksGenerator(nil, hashBlock) revealingSequence = make(map[string]struct{}) orderingSequence = make(map[string]struct{}) + genesisTime = time.Now().UTC() ) - + gen := test.NewBlocksGenerator(&test.BlocksGeneratorConfig{ + NumChains: chainNum, + MinBlockTimeInterval: 0, + MaxBlockTimeInterval: 500 * time.Millisecond, + }, ackingCountGenerator, hashBlock) db, err := blockdb.NewMemBackedBlockDB() - req.Nil(err) - nodePrvKeys, err := gen.Generate( - chainNum, blockNum, ackingCountGenerator, db) - req.Nil(err) - req.Len(nodePrvKeys, int(chainNum)) + req.NoError(err) + req.NoError(gen.Generate( + 0, + genesisTime, + genesisTime.Add(20*time.Second), + db)) iter, err := db.GetAll() - req.Nil(err) + req.NoError(err) // Setup a revealer that would reveal blocks forming // valid DAGs. revealer, err := test.NewRandomDAGRevealer(iter) - req.Nil(err) - + req.NoError(err) // TODO (mission): make this part run concurrently. for i := 0; i < repeat; i++ { revealed := "" @@ -939,7 +942,6 @@ func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks( func (s *TotalOrderingTestSuite) TestRandomlyGeneratedBlocks() { var ( chainNum = uint32(23) - blockNum = 50 phi uint64 = 10 repeat = 15 ) @@ -960,26 +962,22 @@ func (s *TotalOrderingTestSuite) TestRandomlyGeneratedBlocks() { constructor := func(chainNum uint32) *totalOrdering { return newTotalOrdering(0, phi, chainNum) } - s.baseTestRandomlyGeneratedBlocks( - constructor, chainNum, blockNum, gen, repeat) - // Test for K=1, + s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) + // Test for K=1. constructor = func(chainNum uint32) *totalOrdering { return newTotalOrdering(1, phi, chainNum) } - s.baseTestRandomlyGeneratedBlocks( - constructor, chainNum, blockNum, gen, repeat) - // Test for K=2, + s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) + // Test for K=2. constructor = func(chainNum uint32) *totalOrdering { return newTotalOrdering(2, phi, chainNum) } - s.baseTestRandomlyGeneratedBlocks( - constructor, chainNum, blockNum, gen, repeat) - // Test for K=3, + s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) + // Test for K=3. constructor = func(chainNum uint32) *totalOrdering { return newTotalOrdering(3, phi, chainNum) } - s.baseTestRandomlyGeneratedBlocks( - constructor, chainNum, blockNum, gen, repeat) + s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) } } |