core: Leader Selector. (#80)

12 files changed, 311 insertions, 29 deletions

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
+// <http://www.gnu.org/licenses/>.
+
+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"