Initial implementation of DEXON consensus algorithm

7 files changed, 521 insertions, 0 deletions

diff --git a/simulation/app.go b/simulation/app.go
new file mode 100644
index 0000000..02d1c1e
--- /dev/null
+++ b/simulation/app.go
@@ -0,0 +1,50 @@
+// 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 simulation
+
+import (
+	"fmt"
+
+	"github.com/dexon-foundation/dexon-consensus-core/core/types"
+)
+
+// SimApp is an DEXON app for simulation.
+type SimApp struct {
+	ValidatorID types.ValidatorID
+	Outputs     []*types.Block
+	Early       bool
+}
+
+// NewSimApp returns point to a new instance of SimApp.
+func NewSimApp(id types.ValidatorID) *SimApp {
+	return &SimApp{
+		ValidatorID: id,
+	}
+}
+
+// ValidateBlock validates a given block.
+func (a *SimApp) ValidateBlock(b *types.Block) bool {
+	return true
+}
+
+// Deliver is called when blocks are delivered by the total ordering algorithm.
+func (a *SimApp) Deliver(blocks []*types.Block, early bool) {
+	a.Outputs = blocks
+	a.Early = early
+	fmt.Println("OUTPUT", a.ValidatorID, a.Early, a.Outputs)
+}
diff --git a/simulation/config/config.go b/simulation/config/config.go
new file mode 100644
index 0000000..228d69b
--- /dev/null
+++ b/simulation/config/config.go
@@ -0,0 +1,89 @@
+// 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 config
+
+import (
+	"os"
+
+	"github.com/naoina/toml"
+)
+
+// Validator config for the simulation.
+type Validator struct {
+	Num                  int
+	ProposeIntervalMean  float64
+	ProposeIntervalSigma float64
+}
+
+// Networking config.
+type Networking struct {
+	Mean          float64
+	Sigma         float64
+	LossRateValue float64
+}
+
+// Config represents the configuration for simulation.
+type Config struct {
+	Title      string
+	Validator  Validator
+	Networking Networking
+}
+
+// GenerateDefault generates a default configuration file.
+func GenerateDefault(path string) error {
+	f, err := os.Create(path)
+	if err != nil {
+		return err
+	}
+	defer f.Close()
+
+	config := Config{
+		Title: "DEXON Consensus Simulation Config",
+		Validator: Validator{
+			Num:                  4,
+			ProposeIntervalMean:  500,
+			ProposeIntervalSigma: 30,
+		},
+		Networking: Networking{
+			Mean:          100,
+			Sigma:         30,
+			LossRateValue: 0,
+		},
+	}
+
+	if err := toml.NewEncoder(f).Encode(&config); err != nil {
+		return err
+	}
+	return nil
+}
+
+// Read reads the config from a file.
+func Read(path string) (*Config, error) {
+	f, err := os.Open(path)
+	if err != nil {
+		return nil, err
+	}
+	defer f.Close()
+
+	var config Config
+
+	if toml.NewDecoder(f).Decode(&config); err != nil {
+		return nil, err
+	}
+	return &config, nil
+}
diff --git a/simulation/network-model.go b/simulation/network-model.go
new file mode 100644
index 0000000..041bd12
--- /dev/null
+++ b/simulation/network-model.go
@@ -0,0 +1,68 @@
+package simulation
+
+import (
+	"math/rand"
+	"time"
+)
+
+// Model is the interface for define a given network environment.
+type Model interface {
+	// LossRate returns the message lost ratio between [0, 1)
+	LossRate() float64
+
+	// Delay returns the send delay of the message.  This function is called each
+	// time before the message is sent, so one can return different number each
+	// time.
+	Delay() time.Duration
+}
+
+// LosslessNetwork is a lossless network model.
+type LosslessNetwork struct {
+}
+
+// LossRate returns lossrate for the model.
+func (l *LosslessNetwork) LossRate() float64 {
+	return 0.0
+}
+
+// Delay returns the send delay of a given message.
+func (l *LosslessNetwork) Delay() time.Duration {
+	return time.Duration(0)
+}
+
+// FixedLostNoDelayModel is a network with no delay and a fixed lost
+// ratio.
+type FixedLostNoDelayModel struct {
+	LossRateValue float64
+}
+
+// LossRate returns lossrate for the model.
+func (f *FixedLostNoDelayModel) LossRate() float64 {
+	return f.LossRateValue
+}
+
+// Delay returns the send delay of a given message.
+func (f *FixedLostNoDelayModel) Delay() time.Duration {
+	return time.Duration(0)
+}
+
+// NormalNetwork is a model where it's delay is a normal distribution.
+type NormalNetwork struct {
+	Sigma         float64
+	Mean          float64
+	LossRateValue float64
+}
+
+// LossRate returns lossrate for the model.
+func (n *NormalNetwork) LossRate() float64 {
+	return n.LossRateValue
+}
+
+// Delay returns the send delay of a given message.
+func (n *NormalNetwork) Delay() time.Duration {
+	delay := rand.NormFloat64()*n.Sigma + n.Mean
+	if delay < 0 {
+		delay = n.Sigma / 2
+	}
+	return time.Duration(delay) * time.Millisecond
+}
diff --git a/simulation/network-model_test.go b/simulation/network-model_test.go
new file mode 100644
index 0000000..aefa3c6
--- /dev/null
+++ b/simulation/network-model_test.go
@@ -0,0 +1,31 @@
+package simulation
+
+import (
+	"testing"
+	"time"
+
+	"github.com/stretchr/testify/suite"
+)
+
+type NetworkModelsTestSuite struct {
+	suite.Suite
+}
+
+func (n *NetworkModelsTestSuite) SetupTest() {
+}
+
+func (n *NetworkModelsTestSuite) TearDownTest() {
+}
+
+// TestNormalNetwork make sure the Delay() or NormalNetwork does not
+// exceeds 200ms.
+func (n *NetworkModelsTestSuite) TestNormalNetwork() {
+	m := NormalNetwork{}
+	for i := 0; i < 1000; i++ {
+		n.Require().True(m.Delay() < 200*time.Millisecond)
+	}
+}
+
+func TestNetworkModels(t *testing.T) {
+	suite.Run(t, new(NetworkModelsTestSuite))
+}
diff --git a/simulation/network.go b/simulation/network.go
new file mode 100644
index 0000000..51eb868
--- /dev/null
+++ b/simulation/network.go
@@ -0,0 +1,86 @@
+// 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 simulation
+
+import (
+	"math/rand"
+	"sync"
+	"time"
+
+	"github.com/dexon-foundation/dexon-consensus-core/core"
+	"github.com/dexon-foundation/dexon-consensus-core/core/types"
+)
+
+const msgBufferSize = 128
+
+// Network implements the consensus.Network interface.
+type Network struct {
+	model Model
+
+	endpointMutex sync.RWMutex
+	endpoints     map[types.ValidatorID]chan interface{}
+}
+
+// NewNetwork returns pointer to a new Network instance.
+func NewNetwork(model Model) *Network {
+	return &Network{
+		model:     model,
+		endpoints: make(map[types.ValidatorID]chan interface{}),
+	}
+}
+
+// Join allow a client to join the network. It reutnrs a interface{} channel for
+// the client to recieve information.
+func (n *Network) Join(endpoint core.Endpoint) chan interface{} {
+	n.endpointMutex.Lock()
+	defer n.endpointMutex.Unlock()
+
+	if x, exists := n.endpoints[endpoint.GetID()]; exists {
+		return x
+	}
+
+	recivingChannel := make(chan interface{}, msgBufferSize)
+	n.endpoints[endpoint.GetID()] = recivingChannel
+	return recivingChannel
+}
+
+// Send sends a msg to another client.
+func (n *Network) Send(destID types.ValidatorID, msg interface{}) {
+	n.endpointMutex.RLock()
+	defer n.endpointMutex.RUnlock()
+
+	clientChannel, exists := n.endpoints[destID]
+	if !exists {
+		return
+	}
+
+	go func() {
+		if rand.Float64() > n.model.LossRate() {
+			time.Sleep(n.model.Delay())
+
+			clientChannel <- msg
+		}
+	}()
+}
+
+// BroadcastBlock broadcast blocks into the network.
+func (n *Network) BroadcastBlock(block *types.Block) {
+	for endpoint := range n.endpoints {
+		n.Send(endpoint, block.Clone())
+	}
+}
diff --git a/simulation/simulation.go b/simulation/simulation.go
new file mode 100644
index 0000000..8708293
--- /dev/null
+++ b/simulation/simulation.go
@@ -0,0 +1,58 @@
+// 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 simulation
+
+import (
+	"fmt"
+
+	"github.com/dexon-foundation/dexon-consensus-core/common"
+	"github.com/dexon-foundation/dexon-consensus-core/core/types"
+	"github.com/dexon-foundation/dexon-consensus-core/simulation/config"
+)
+
+// Run starts the simulation.
+func Run(configPath string) {
+	config, err := config.Read(configPath)
+	if err != nil {
+		panic(err)
+	}
+
+	networkModel := &NormalNetwork{
+		Sigma:         config.Networking.Sigma,
+		Mean:          config.Networking.Mean,
+		LossRateValue: config.Networking.LossRateValue,
+	}
+	network := NewNetwork(networkModel)
+
+	var vs []*Validator
+	for i := 0; i < config.Validator.Num; i++ {
+		id := types.ValidatorID(common.NewRandomHash())
+		vs = append(vs, NewValidator(id, config.Validator, network, nil))
+	}
+
+	for i := 0; i < config.Validator.Num; i++ {
+		vs[i].Bootstrap(vs)
+	}
+
+	for i := 0; i < config.Validator.Num; i++ {
+		fmt.Printf("Validator %d: %s\n", i, vs[i].ID)
+		go vs[i].Run()
+	}
+
+	select {}
+}
diff --git a/simulation/validator.go b/simulation/validator.go
new file mode 100644
index 0000000..84e5e52
--- /dev/null
+++ b/simulation/validator.go
@@ -0,0 +1,139 @@
+// 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 simulation
+
+import (
+	"time"
+
+	"github.com/syndtr/goleveldb/leveldb"
+
+	"github.com/dexon-foundation/dexon-consensus-core/blockdb"
+	"github.com/dexon-foundation/dexon-consensus-core/common"
+	"github.com/dexon-foundation/dexon-consensus-core/core"
+	"github.com/dexon-foundation/dexon-consensus-core/core/types"
+	"github.com/dexon-foundation/dexon-consensus-core/simulation/config"
+)
+
+// Validator represents a validator in DexCon.
+type Validator struct {
+	network core.Network
+	app     *SimApp
+
+	config     config.Validator
+	db         *leveldb.DB
+	msgChannel chan interface{}
+
+	ID              types.ValidatorID
+	lattice         *core.BlockLattice
+	compactionChain *core.BlockChain
+
+	genesis *types.Block
+	current *types.Block
+}
+
+// NewValidator returns a new empty validator.
+func NewValidator(
+	id types.ValidatorID,
+	config config.Validator,
+	network core.Network,
+	db *leveldb.DB) *Validator {
+
+	hash := common.NewRandomHash()
+	genesis := &types.Block{
+		ProposerID: id,
+		ParentHash: hash,
+		Hash:       hash,
+		Height:     0,
+		Acks:       map[common.Hash]struct{}{},
+	}
+
+	app := NewSimApp(id)
+	lattice := core.NewBlockLattice(blockdb.NewMemBackedBlockDB(), network, app)
+
+	return &Validator{
+		ID:      id,
+		config:  config,
+		network: network,
+		app:     app,
+		db:      db,
+		lattice: lattice,
+		genesis: genesis,
+		current: genesis,
+	}
+}
+
+// GetID returns the ID of validator.
+func (v *Validator) GetID() types.ValidatorID {
+	return v.ID
+}
+
+// Bootstrap bootstraps a validator.
+func (v *Validator) Bootstrap(vs []*Validator) {
+	for _, x := range vs {
+		v.lattice.AddValidator(x.ID, x.genesis)
+	}
+	v.lattice.SetOwner(v.ID)
+}
+
+// Run starts the validator.
+func (v *Validator) Run() {
+	v.msgChannel = v.network.Join(v)
+
+	go v.MsgServer()
+	go v.BlockProposer()
+
+	// Blocks forever.
+	select {}
+}
+
+// MsgServer listen to the network channel for message and handle it.
+func (v *Validator) MsgServer() {
+	for {
+		msg := <-v.msgChannel
+
+		switch val := msg.(type) {
+		case *types.Block:
+			//if val.ProposerID.Equal(v.ID) {
+			//	continue
+			//}
+			v.lattice.ProcessBlock(val, true)
+		}
+	}
+}
+
+// BlockProposer propose blocks to be send to the DEXON network.
+func (v *Validator) BlockProposer() {
+	model := &NormalNetwork{
+		Sigma: v.config.ProposeIntervalSigma,
+		Mean:  v.config.ProposeIntervalMean,
+	}
+
+	for {
+		time.Sleep(model.Delay())
+
+		block := &types.Block{
+			ProposerID: v.ID,
+			ParentHash: v.current.Hash,
+			Hash:       common.NewRandomHash(),
+			Height:     0,
+			Acks:       map[common.Hash]struct{}{},
+		}
+		v.current = block
+		v.lattice.ProposeBlock(block)
+	}
+}