aboutsummaryrefslogtreecommitdiffstats
path: root/core/test/blocks-generator.go
diff options
context:
space:
mode:
Diffstat (limited to 'core/test/blocks-generator.go')
-rw-r--r--core/test/blocks-generator.go304
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
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-26 10:05:41 +0800