From 2681e011bd48ec107dedae9c7dcbc0810673298c Mon Sep 17 00:00:00 2001 From: Jimmy Hu Date: Thu, 30 Aug 2018 10:45:06 +0800 Subject: core: Leader Selector. (#80) --- core/agreement-state_test.go | 36 ++++++---- core/agreement.go | 7 +- core/crypto.go | 18 +++++ core/crypto_test.go | 16 +++++ core/governance.go | 5 ++ core/leader-selector.go | 92 +++++++++++++++++++++++--- core/leader-selector_test.go | 123 +++++++++++++++++++++++++++++++++++ core/test/governance.go | 10 +++ core/types/block.go | 3 + simulation/config/config.go | 8 +-- simulation/governance.go | 18 ++++- simulation/kubernetes/config.toml.in | 4 ++ 12 files changed, 311 insertions(+), 29 deletions(-) create mode 100644 core/leader-selector_test.go diff --git a/core/agreement-state_test.go b/core/agreement-state_test.go index 5fd6214..9d587d1 100644 --- a/core/agreement-state_test.go +++ b/core/agreement-state_test.go @@ -55,12 +55,14 @@ func (r *agreementTestReceiver) confirmBlock(block common.Hash) { r.s.confirmChan <- block } -func (s *AgreementTestSuite) blockProposer() *types.Block { +func (s *AgreementTestSuite) proposeBlock( + leader *leaderSelector) *types.Block { block := &types.Block{ ProposerID: s.ID, Hash: common.NewRandomHash(), } s.block[block.Hash] = block + s.Require().Nil(leader.prepareBlock(block, s.prvKey[s.ID])) return block } @@ -96,6 +98,11 @@ func (s *AgreementTestSuite) SetupTest() { } func (s *AgreementTestSuite) newAgreement(numValidator int) *agreement { + leader := newGenesisLeaderSelector("I ❤️ DEXON", eth.SigToPub) + blockProposer := func() *types.Block { + return s.proposeBlock(leader) + } + validators := make(types.ValidatorIDs, numValidator-1) for i := range validators { prvKey, err := eth.NewPrivateKey() @@ -108,8 +115,9 @@ func (s *AgreementTestSuite) newAgreement(numValidator int) *agreement { s.ID, &agreementTestReceiver{s}, validators, + leader, eth.SigToPub, - s.blockProposer, + blockProposer, ) return agreement } @@ -151,10 +159,12 @@ func (s *AgreementTestSuite) TestPrepareState() { // For period >= 2, if the pass-vote for block v not equal to {} // is more than 2f+1, proposing the block v. a.data.period = 3 - block := s.blockProposer() - block.ProposerID.Hash = common.NewRandomHash() - err = a.processBlock(block) + block := s.proposeBlock(a.data.leader) + prv, err := eth.NewPrivateKey() s.Require().Nil(err) + block.ProposerID = types.NewValidatorID(prv.PublicKey()) + s.Require().Nil(a.data.leader.prepareBlock(block, prv)) + s.Require().Nil(a.processBlock(block)) for vID := range a.validators { vote := s.prepareVote(vID, types.VotePass, block.Hash, 2) s.Require().Nil(a.processVote(vote)) @@ -176,10 +186,12 @@ func (s *AgreementTestSuite) TestAckState() { blocks := make([]*types.Block, 3) for i := range blocks { - blocks[i] = s.blockProposer() - blocks[i].ProposerID.Hash = common.NewRandomHash() - err := a.processBlock(blocks[i]) + blocks[i] = s.proposeBlock(a.data.leader) + prv, err := eth.NewPrivateKey() s.Require().Nil(err) + blocks[i].ProposerID = types.NewValidatorID(prv.PublicKey()) + s.Require().Nil(a.data.leader.prepareBlock(blocks[i], prv)) + s.Require().Nil(a.processBlock(blocks[i])) } // For period 1, propose ack-vote for the block having largest potential. @@ -233,7 +245,7 @@ func (s *AgreementTestSuite) TestConfirmState() { // If there are 2f+1 ack-votes for block v not equal to {}, // propose a confirm-vote for block v. a.data.period = 1 - block := s.blockProposer() + block := s.proposeBlock(a.data.leader) s.Require().Nil(a.processBlock(block)) for vID := range a.validators { vote := s.prepareVote(vID, types.VoteAck, block.Hash, 1) @@ -309,7 +321,7 @@ func (s *AgreementTestSuite) TestPass1State() { // Else, propose pass-vote for default block. a.data.period = 3 - block := s.blockProposer() + block := s.proposeBlock(a.data.leader) a.data.defaultBlock = block.Hash hash = common.NewRandomHash() for vID := range a.validators { @@ -330,7 +342,7 @@ func (s *AgreementTestSuite) TestPass1State() { a = s.newAgreement(4) state = newPass1State(a.data) a.data.period = 1 - block = s.blockProposer() + block = s.proposeBlock(a.data.leader) a.data.defaultBlock = block.Hash hash = common.NewRandomHash() vote = s.prepareVote(s.ID, types.VoteAck, common.Hash{}, 1) @@ -363,7 +375,7 @@ func (s *AgreementTestSuite) TestPass2State() { // If there are 2f+1 ack-vote for block v not equal to {}, // propose pass-vote for v. - block := s.blockProposer() + block := s.proposeBlock(a.data.leader) s.Require().Nil(a.processBlock(block)) for vID := range a.validators { vote := s.prepareVote(vID, types.VoteAck, block.Hash, 1) diff --git a/core/agreement.go b/core/agreement.go index 9d0440e..28bcc67 100644 --- a/core/agreement.go +++ b/core/agreement.go @@ -99,13 +99,14 @@ func newAgreement( ID types.ValidatorID, recv agreementReceiver, validators types.ValidatorIDs, + leader *leaderSelector, sigToPub SigToPubFn, blockProposer blockProposerFn) *agreement { agreement := &agreement{ data: &agreementData{ recv: recv, ID: ID, - leader: newLeaderSelector(), + leader: leader, blockProposer: blockProposer, }, aID: &atomic.Value{}, @@ -226,7 +227,9 @@ func (a *agreement) processBlock(block *types.Block) error { return nil } a.data.blocks[block.ProposerID] = block - a.data.leader.processBlock(block) + if err := a.data.leader.processBlock(block); err != nil { + return err + } return nil } diff --git a/core/crypto.go b/core/crypto.go index 17426f7..57aae92 100644 --- a/core/crypto.go +++ b/core/crypto.go @@ -126,6 +126,24 @@ func verifyVoteSignature(vote *types.Vote, sigToPub SigToPubFn) (bool, error) { return true, nil } +func hashCRS(block *types.Block, crs common.Hash) common.Hash { + hashPos := hashPosition(block.ShardID, block.ChainID, block.Height) + return crypto.Keccak256Hash(crs[:], hashPos[:]) +} + +func verifyCRSSignature(block *types.Block, crs common.Hash, sigToPub SigToPubFn) ( + bool, error) { + hash := hashCRS(block, crs) + pubKey, err := sigToPub(hash, block.CRSSignature) + if err != nil { + return false, err + } + if block.ProposerID != types.NewValidatorID(pubKey) { + return false, nil + } + return true, nil +} + func hashPosition(shardID, chainID, height uint64) common.Hash { binaryShardID := make([]byte, 8) binary.LittleEndian.PutUint64(binaryShardID, shardID) diff --git a/core/crypto_test.go b/core/crypto_test.go index ccfcebb..62f7daa 100644 --- a/core/crypto_test.go +++ b/core/crypto_test.go @@ -209,6 +209,22 @@ func (s *CryptoTestSuite) TestVoteSignature() { s.False(verifyVoteSignature(vote, eth.SigToPub)) } +func (s *CryptoTestSuite) TestCRSSignature() { + crs := common.NewRandomHash() + prv, err := eth.NewPrivateKey() + s.Require().Nil(err) + pub := prv.PublicKey() + vID := types.NewValidatorID(pub) + block := &types.Block{ + ProposerID: vID, + } + block.CRSSignature, err = prv.Sign(hashCRS(block, crs)) + s.Require().Nil(err) + s.True(verifyCRSSignature(block, crs, eth.SigToPub)) + block.Height++ + s.False(verifyCRSSignature(block, crs, eth.SigToPub)) +} + func TestCrypto(t *testing.T) { suite.Run(t, new(CryptoTestSuite)) } diff --git a/core/governance.go b/core/governance.go index d94fad0..9ace833 100644 --- a/core/governance.go +++ b/core/governance.go @@ -41,4 +41,9 @@ type Governance interface { // Get configuration change events after a certain epoch. GetConfigurationChangeEvent(epoch int) []types.ConfigurationChangeEvent + + // Get Genesis CRS. + GetGenesisCRS() string + // GetAgreementK returns number of blocks for a CRS. + GetAgreementK() int } diff --git a/core/leader-selector.go b/core/leader-selector.go index cea31ce..4295050 100644 --- a/core/leader-selector.go +++ b/core/leader-selector.go @@ -18,26 +18,100 @@ package core import ( - "sort" + "fmt" + "math/big" "github.com/dexon-foundation/dexon-consensus-core/common" "github.com/dexon-foundation/dexon-consensus-core/core/types" + "github.com/dexon-foundation/dexon-consensus-core/crypto" ) +// Errors for leader module. +var ( + ErrIncorrectCRSSignature = fmt.Errorf("incorrect CRS signature") +) + +// Some constant value. +var ( + maxHash *big.Int + one *big.Rat +) + +func init() { + hash := make([]byte, common.HashLength) + for i := range hash { + hash[i] = 0xff + } + maxHash = big.NewInt(0).SetBytes(hash) + one = big.NewRat(1, 1) +} + type leaderSelector struct { - common.Hashes + hashCRS common.Hash + numCRS *big.Int + minCRSBlock *big.Int + minBlockHash common.Hash + + sigToPub SigToPubFn } -func newLeaderSelector() *leaderSelector { - return &leaderSelector{} +func newGenesisLeaderSelector( + crs string, + sigToPub SigToPubFn) *leaderSelector { + hash := crypto.Keccak256Hash([]byte(crs[:])) + return newLeaderSelector(hash, sigToPub) +} + +func newLeaderSelector( + crs common.Hash, + sigToPub SigToPubFn) *leaderSelector { + numCRS := big.NewInt(0) + numCRS.SetBytes(crs[:]) + return &leaderSelector{ + numCRS: numCRS, + hashCRS: crs, + minCRSBlock: maxHash, + sigToPub: sigToPub, + } +} + +func (l *leaderSelector) distance(sig crypto.Signature) *big.Int { + hash := crypto.Keccak256Hash(sig[:]) + num := big.NewInt(0) + num.SetBytes(hash[:]) + num.Abs(num.Sub(l.numCRS, num)) + return num +} + +func (l *leaderSelector) probability(sig crypto.Signature) float64 { + dis := l.distance(sig) + prob := big.NewRat(1, 1).SetFrac(dis, maxHash) + p, _ := prob.Sub(one, prob).Float64() + return p } func (l *leaderSelector) leaderBlockHash() common.Hash { - // TODO(jimmy-dexon): return leader based on paper. - sort.Sort(l.Hashes) - return l.Hashes[len(l.Hashes)-1] + return l.minBlockHash +} + +func (l *leaderSelector) prepareBlock( + block *types.Block, prv crypto.PrivateKey) (err error) { + block.CRSSignature, err = prv.Sign(hashCRS(block, l.hashCRS)) + return } -func (l *leaderSelector) processBlock(block *types.Block) { - l.Hashes = append(l.Hashes, block.Hash) +func (l *leaderSelector) processBlock(block *types.Block) error { + ok, err := verifyCRSSignature(block, l.hashCRS, l.sigToPub) + if err != nil { + return err + } + if !ok { + return ErrIncorrectCRSSignature + } + dist := l.distance(block.CRSSignature) + if l.minCRSBlock.Cmp(dist) == 1 { + l.minCRSBlock = dist + l.minBlockHash = block.Hash + } + return nil } diff --git a/core/leader-selector_test.go b/core/leader-selector_test.go new file mode 100644 index 0000000..f6028c0 --- /dev/null +++ b/core/leader-selector_test.go @@ -0,0 +1,123 @@ +// 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 core + +import ( + "testing" + + "github.com/stretchr/testify/suite" + + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" + "github.com/dexon-foundation/dexon-consensus-core/crypto/eth" +) + +type LeaderSelectorTestSuite struct { + suite.Suite +} + +func (s *LeaderSelectorTestSuite) newLeader() *leaderSelector { + return newGenesisLeaderSelector("DEXON 🚀", eth.SigToPub) +} + +func (s *LeaderSelectorTestSuite) TestDistance() { + leader := s.newLeader() + hash := common.NewRandomHash() + prv, err := eth.NewPrivateKey() + s.Require().Nil(err) + sig, err := prv.Sign(hash) + s.Require().Nil(err) + dis := leader.distance(sig) + s.True(dis.Cmp(maxHash) == -1) +} + +func (s *LeaderSelectorTestSuite) TestProbability() { + leader := s.newLeader() + prv1, err := eth.NewPrivateKey() + s.Require().Nil(err) + prv2, err := eth.NewPrivateKey() + s.Require().Nil(err) + for { + hash := common.NewRandomHash() + sig1, err := prv1.Sign(hash) + s.Require().Nil(err) + sig2, err := prv2.Sign(hash) + s.Require().Nil(err) + dis1 := leader.distance(sig1) + dis2 := leader.distance(sig2) + prob1 := leader.probability(sig1) + prob2 := leader.probability(sig2) + s.True(prob1 <= 1 && prob1 >= 0) + s.True(prob2 <= 1 && prob2 >= 0) + cmp := dis1.Cmp(dis2) + if cmp == 0 { + s.True(dis1.Cmp(dis2) == 0) + continue + } + if cmp == 1 { + s.True(prob2 > prob1) + } else if cmp == -1 { + s.True(prob2 < prob1) + } + break + } +} + +func (s *LeaderSelectorTestSuite) TestLeaderBlockHash() { + leader := s.newLeader() + blocks := make(map[common.Hash]*types.Block) + for i := 0; i < 10; i++ { + prv, err := eth.NewPrivateKey() + s.Require().Nil(err) + block := &types.Block{ + ProposerID: types.NewValidatorID(prv.PublicKey()), + Hash: common.NewRandomHash(), + } + s.Require().Nil(leader.prepareBlock(block, prv)) + s.Require().Nil(leader.processBlock(block)) + blocks[block.Hash] = block + } + blockHash := leader.leaderBlockHash() + leaderBlock, exist := blocks[blockHash] + s.Require().True(exist) + leaderDist := leader.distance(leaderBlock.CRSSignature) + for _, block := range blocks { + if block == leaderBlock { + continue + } + dist := leader.distance(block.CRSSignature) + s.True(leaderDist.Cmp(dist) == -1) + } +} + +func (s *LeaderSelectorTestSuite) TestPrepareBlock() { + leader := s.newLeader() + prv, err := eth.NewPrivateKey() + s.Require().Nil(err) + block := &types.Block{ + ProposerID: types.NewValidatorID(prv.PublicKey()), + } + s.Require().Nil(leader.prepareBlock(block, prv)) + s.Nil(leader.processBlock(block)) + block.Height++ + s.Error(ErrIncorrectCRSSignature, leader.processBlock(block)) +} + +func TestLeaderSelector(t *testing.T) { + suite.Run(t, new(LeaderSelectorTestSuite)) +} diff --git a/core/test/governance.go b/core/test/governance.go index 58ab582..8df7e80 100644 --- a/core/test/governance.go +++ b/core/test/governance.go @@ -88,6 +88,16 @@ func (g *Governance) GetConfigurationChangeEvent( return nil } +// GetGenesisCRS returns the CRS string. +func (g *Governance) GetGenesisCRS() string { + return "🆕 DEXON" +} + +// GetAgreementK returns number of blocks for a CRS. +func (g *Governance) GetAgreementK() int { + return 20 +} + // GetPrivateKey return the private key for that validator, this function // is a test utility and not a general core.Governance interface. func (g *Governance) GetPrivateKey( diff --git a/core/types/block.go b/core/types/block.go index 78548b4..e528893 100644 --- a/core/types/block.go +++ b/core/types/block.go @@ -72,6 +72,8 @@ type Block struct { Acks map[common.Hash]struct{} `json:"acks"` Signature crypto.Signature `json:"signature"` + CRSSignature crypto.Signature `json:"crs_signature"` + Notary Notary `json:"notary"` } @@ -110,6 +112,7 @@ func (b *Block) Clone() (bcopy *Block) { bcopy.Hash = b.Hash bcopy.Height = b.Height bcopy.Signature = b.Signature.Clone() + bcopy.CRSSignature = b.CRSSignature.Clone() bcopy.Notary.Timestamp = b.Notary.Timestamp bcopy.Notary.Height = b.Notary.Height if bcopy.Timestamps == nil { diff --git a/simulation/config/config.go b/simulation/config/config.go index 6ead62e..8a804a5 100644 --- a/simulation/config/config.go +++ b/simulation/config/config.go @@ -35,8 +35,8 @@ const ( // Agreement settings. type Agreement struct { - CRS string - K int + GenesisCRS string `toml:"genesis_crs"` + K int } // Consensus settings. @@ -91,8 +91,8 @@ func GenerateDefault(path string) error { Validator: Validator{ Consensus: Consensus{ Agreement: Agreement{ - CRS: "In DEXON we trust.", - K: 50, + GenesisCRS: "In DEXON we trust.", + K: 50, }, PhiRatio: float32(2) / 3, K: 1, diff --git a/simulation/governance.go b/simulation/governance.go index 7e3f6f2..7100d4c 100644 --- a/simulation/governance.go +++ b/simulation/governance.go @@ -34,6 +34,8 @@ type simGovernance struct { expectedNumValidators int k int phiRatio float32 + crs string + agreementK int } // newSimGovernance returns a new simGovernance instance. @@ -42,8 +44,10 @@ func newSimGovernance( return &simGovernance{ validatorSet: make(map[types.ValidatorID]decimal.Decimal), expectedNumValidators: numValidators, - k: consensusConfig.K, - phiRatio: consensusConfig.PhiRatio, + k: consensusConfig.K, + phiRatio: consensusConfig.PhiRatio, + crs: consensusConfig.Agreement.GenesisCRS, + agreementK: consensusConfig.Agreement.K, } } @@ -84,6 +88,16 @@ func (g *simGovernance) GetConfigurationChangeEvent( return nil } +// GetGenesisCRS returns CRS. +func (g *simGovernance) GetGenesisCRS() string { + return g.crs +} + +// GetAgreementK returns K for agreement. +func (g *simGovernance) GetAgreementK() int { + return g.agreementK +} + // addValidator add a new validator into the simulated governance contract. func (g *simGovernance) addValidator(vID types.ValidatorID) { g.lock.Lock() diff --git a/simulation/kubernetes/config.toml.in b/simulation/kubernetes/config.toml.in index 79e662a..3019920 100644 --- a/simulation/kubernetes/config.toml.in +++ b/simulation/kubernetes/config.toml.in @@ -10,6 +10,10 @@ max_block = 1000 phi_ratio = 6.66670024394989e-01 k = 1 +[validator.consensus.agreement] +genesis_crs = "In DEXON we trust." +k = 50 + [networking] type = "tcp" peer_server = "peer-server-svc.default.svc.cluster.local" -- cgit v1.2.3