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