test: random blocks generator (#26)

* Add blocks generator.

This helper would randomly generate blocks that forms valid DAGs.

* Add revealer

Revealer is an extension of blockdb.BlockIterator. The block
sequence from 'Next' method would be either randomly (see
RandomRevealer) or meeting some specific condition (ex. forming
a DAG, see RandomDAGRevealer).

* Add test for sequencer based on random blocks.

* core: refine Application interface and add Governance interface (#24)

Add a new Governance interface for interaction with the governance contract.

Also remove the ValidateBlock call in application interface as the application should validate it before putting it into the consensus module.

A new BlockConverter interface is also added. The consensus module should accept the BlockConverter interface in future implementation, and use the Block() function to get the underlying block info.

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
+}