diff options
Diffstat (limited to 'core/test/blocks-generator.go')
-rw-r--r-- | core/test/blocks-generator.go | 304 |
1 files changed, 181 insertions, 123 deletions
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 +} |