From aed24cf020bd11c3b20a7011b96c02e41894fa32 Mon Sep 17 00:00:00 2001 From: Wei-Ning Huang Date: Mon, 16 Jul 2018 00:12:17 +0800 Subject: Initial implementation of DEXON consensus algorithm --- simulation/app.go | 50 ++++++++++++++ simulation/config/config.go | 89 +++++++++++++++++++++++++ simulation/network-model.go | 68 +++++++++++++++++++ simulation/network-model_test.go | 31 +++++++++ simulation/network.go | 86 ++++++++++++++++++++++++ simulation/simulation.go | 58 ++++++++++++++++ simulation/validator.go | 139 +++++++++++++++++++++++++++++++++++++++ 7 files changed, 521 insertions(+) create mode 100644 simulation/app.go create mode 100644 simulation/config/config.go create mode 100644 simulation/network-model.go create mode 100644 simulation/network-model_test.go create mode 100644 simulation/network.go create mode 100644 simulation/simulation.go create mode 100644 simulation/validator.go (limited to 'simulation') 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 +// . + +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 +// . + +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 +// . + +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 +// . + +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 +// . + +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) + } +} -- cgit v1.2.3