core: DEXON Consensus Timestamp Algorithm. (#29)

4 files changed, 377 insertions, 10 deletions

diff --git a/common/types.go b/common/types.go
index 0a78111..9dc9f1c 100644
--- a/common/types.go
+++ b/common/types.go
@@ -20,6 +20,7 @@ package common
 import (
 	"bytes"
 	"encoding/hex"
+	"time"
 )
 
 const (
@@ -58,3 +59,10 @@ type Hashes []Hash
 func (hs Hashes) Len() int           { return len(hs) }
 func (hs Hashes) Less(i, j int) bool { return bytes.Compare(hs[i][:], hs[j][:]) < 0 }
 func (hs Hashes) Swap(i, j int)      { hs[i], hs[j] = hs[j], hs[i] }
+
+// ByTime implements sort.Interface for time.Time.
+type ByTime []time.Time
+
+func (t ByTime) Len() int           { return len(t) }
+func (t ByTime) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }
+func (t ByTime) Less(i, j int) bool { return t[i].Before(t[j]) }
diff --git a/core/timestamp.go b/core/timestamp.go
new file mode 100644
index 0000000..896d137
--- /dev/null
+++ b/core/timestamp.go
@@ -0,0 +1,151 @@
+// 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 (
+	"errors"
+	"sort"
+	"time"
+
+	"github.com/dexon-foundation/dexon-consensus-core/common"
+	"github.com/dexon-foundation/dexon-consensus-core/core/types"
+)
+
+// Timestamp is for Concensus Timestamp Algorithm.
+type Timestamp struct {
+	lastMainChainBlock   *types.Block
+	blocksNotInMainChain []*types.Block
+}
+
+var (
+	// ErrInvalidMainChain would be reported if the invalid result from
+	// main chain selection algorithm is detected.
+	ErrInvalidMainChain = errors.New("invalid main chain")
+	// ErrEmptyTimestamps would be reported if Block.timestamps is empty.
+	ErrEmptyTimestamps = errors.New("timestamp vector should not be empty")
+)
+
+// NewTimestamp create Timestamp object.
+func NewTimestamp() *Timestamp {
+	return &Timestamp{}
+}
+
+// ProcessBlocks is the entry function.
+func (ts *Timestamp) ProcessBlocks(blocks []*types.Block) (
+	blocksWithTimestamp []*types.Block, mainChain []*types.Block, err error) {
+	if len(blocks) == 0 {
+		// TODO (jimmy-dexon): Remove this panic before release.
+		panic("Unexpected empty block list.")
+	}
+	outputFirstBlock := true
+	blocks = append(ts.blocksNotInMainChain, blocks...)
+	if ts.lastMainChainBlock != nil {
+		// TODO (jimmy-dexon): The performance here can be optimized.
+		blocks = append([]*types.Block{ts.lastMainChainBlock}, blocks...)
+		outputFirstBlock = false
+	}
+	mainChain, nonMainChain := ts.selectMainChain(blocks)
+	ts.blocksNotInMainChain = nonMainChain
+	ts.lastMainChainBlock = mainChain[len(mainChain)-1]
+	blocksWithTimestamp = blocks[:len(blocks)-len(nonMainChain)]
+	leftMainChainIdx := 0
+	rightMainChainIdx := 0
+	idxMainChain := 0
+	for idx, block := range blocksWithTimestamp {
+		if idxMainChain >= len(mainChain) {
+			err = ErrInvalidMainChain
+			return
+		} else if block.Hash == mainChain[idxMainChain].Hash {
+			rightMainChainIdx = idx
+			blocksWithTimestamp[idx].ConsensusTime, err = ts.getMedianTime(block)
+			if err != nil {
+				return
+			}
+			// Process Non-MainChain blocks.
+			if rightMainChainIdx > leftMainChainIdx {
+				for idx, timestamp := range interpoTime(
+					blocksWithTimestamp[leftMainChainIdx].ConsensusTime,
+					blocksWithTimestamp[rightMainChainIdx].ConsensusTime,
+					rightMainChainIdx-leftMainChainIdx-1) {
+					blocksWithTimestamp[leftMainChainIdx+idx+1].ConsensusTime = timestamp
+				}
+			}
+			leftMainChainIdx = idx
+			idxMainChain++
+		}
+	}
+	if !outputFirstBlock {
+		blocksWithTimestamp = blocksWithTimestamp[1:]
+	}
+	return
+}
+
+func (ts *Timestamp) selectMainChain(blocks []*types.Block) (
+	mainChain []*types.Block, nonMainChain []*types.Block) {
+	for _, block := range blocks {
+		if len(mainChain) != 0 {
+			if _, exists := block.Acks[mainChain[len(mainChain)-1].Hash]; !exists {
+				nonMainChain = append(nonMainChain, block)
+				continue
+			}
+		}
+		nonMainChain = []*types.Block{}
+		mainChain = append(mainChain, block)
+	}
+	return
+}
+
+func (ts *Timestamp) getMedianTime(block *types.Block) (
+	timestamp time.Time, err error) {
+	timestamps := []time.Time{}
+	for _, timestamp := range block.Timestamps {
+		timestamps = append(timestamps, timestamp)
+	}
+	if len(timestamps) == 0 {
+		err = ErrEmptyTimestamps
+		return
+	}
+	sort.Sort(common.ByTime(timestamps))
+	if len(timestamps)%2 == 0 {
+		t1 := timestamps[len(timestamps)/2-1]
+		t2 := timestamps[len(timestamps)/2]
+		timestamp = interpoTime(t1, t2, 1)[0]
+	} else {
+		timestamp = timestamps[len(timestamps)/2]
+	}
+	return
+}
+
+func interpoTime(t1 time.Time, t2 time.Time, sep int) []time.Time {
+	if sep == 0 {
+		return []time.Time{}
+	}
+	if t1.After(t2) {
+		return interpoTime(t2, t1, sep)
+	}
+	timestamps := make([]time.Time, sep)
+	duration := t2.Sub(t1)
+	period := time.Duration(
+		(duration.Nanoseconds() / int64(sep+1))) * time.Nanosecond
+	prevTime := t1
+	for idx := range timestamps {
+		prevTime = prevTime.Add(period)
+		timestamps[idx] = prevTime
+	}
+	return timestamps
+}
diff --git a/core/timestamp_test.go b/core/timestamp_test.go
new file mode 100644
index 0000000..d47c776
--- /dev/null
+++ b/core/timestamp_test.go
@@ -0,0 +1,206 @@
+// 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 (
+	"math"
+	"math/rand"
+	"testing"
+	"time"
+
+	"github.com/stretchr/testify/suite"
+
+	"github.com/dexon-foundation/dexon-consensus-core/common"
+	"github.com/dexon-foundation/dexon-consensus-core/core/types"
+)
+
+type TimestampTest struct {
+	suite.Suite
+}
+
+func generateBlocksWithAcks(blockNum, maxAcks int) []*types.Block {
+	chain := []*types.Block{
+		&types.Block{
+			Hash: common.NewRandomHash(),
+			Acks: make(map[common.Hash]struct{}),
+		},
+	}
+	for i := 1; i < blockNum; i++ {
+		acks := make(map[common.Hash]struct{})
+		ackNum := rand.Intn(maxAcks) + 1
+		for j := 0; j < ackNum; j++ {
+			ack := rand.Intn(len(chain))
+			acks[chain[ack].Hash] = struct{}{}
+		}
+		block := &types.Block{
+			Hash: common.NewRandomHash(),
+			Acks: acks,
+		}
+		chain = append(chain, block)
+	}
+	return chain
+}
+
+func fillBlocksTimestamps(blocks []*types.Block, validatorNum int,
+	step, sigma time.Duration) {
+	curTime := time.Now().UTC()
+	vIDs := make([]types.ValidatorID, validatorNum)
+	for i := 0; i < validatorNum; i++ {
+		vIDs[i] = types.ValidatorID{Hash: common.NewRandomHash()}
+	}
+	for _, block := range blocks {
+		block.Timestamps = make(map[types.ValidatorID]time.Time)
+		for _, vID := range vIDs {
+			diffSeconds := rand.NormFloat64() * sigma.Seconds()
+			diffSeconds = math.Min(diffSeconds, step.Seconds()/2)
+			diffSeconds = math.Max(diffSeconds, -step.Seconds()/2)
+			diffDuration := time.Duration(diffSeconds*1000) * time.Millisecond
+			block.Timestamps[vID] = curTime.Add(diffDuration)
+		}
+		curTime = curTime.Add(step)
+	}
+}
+
+func extractTimestamps(blocks []*types.Block) []time.Time {
+	timestamps := make([]time.Time, len(blocks))
+	for idx, block := range blocks {
+		timestamps[idx] = block.ConsensusTime
+	}
+	return timestamps
+}
+
+func (s *TimestampTest) TestMainChainSelection() {
+	ts := NewTimestamp()
+	ts2 := NewTimestamp()
+	blockNums := []int{50, 100, 30}
+	maxAcks := 5
+	for _, blockNum := range blockNums {
+		chain := generateBlocksWithAcks(blockNum, maxAcks)
+		mainChain, _ := ts.selectMainChain(chain)
+		// Verify the selected main chain.
+		for i := 1; i < len(mainChain); i++ {
+			_, exists := mainChain[i].Acks[mainChain[i-1].Hash]
+			s.True(exists)
+		}
+		// Verify if selectMainChain is stable.
+		mainChain2, _ := ts2.selectMainChain(chain)
+		s.Equal(mainChain, mainChain2)
+	}
+}
+
+func (s *TimestampTest) TestTimestampPartition() {
+	blockNums := []int{50, 100, 30}
+	validatorNum := 19
+	sigma := 100 * time.Millisecond
+	maxAcks := 5
+	totalMainChain := make([]*types.Block, 1)
+	totalChain := make([]*types.Block, 0)
+	totalTimestamps := make([]time.Time, 0)
+	ts := NewTimestamp()
+	var lastMainChainBlock *types.Block
+	for _, blockNum := range blockNums {
+		chain := generateBlocksWithAcks(blockNum, maxAcks)
+		fillBlocksTimestamps(chain, validatorNum, time.Second, sigma)
+		blocksWithTimestamps, mainChain, err := ts.ProcessBlocks(chain)
+		s.Require().Nil(err)
+		timestamps := extractTimestamps(blocksWithTimestamps)
+		if lastMainChainBlock != nil {
+			s.Require().Equal(mainChain[0], lastMainChainBlock)
+		}
+		s.Require().Equal(mainChain[len(mainChain)-1], ts.lastMainChainBlock)
+		lastMainChainBlock = ts.lastMainChainBlock
+		totalMainChain =
+			append(totalMainChain[:len(totalMainChain)-1], mainChain...)
+		totalChain = append(totalChain, chain...)
+		totalTimestamps = append(totalTimestamps, timestamps...)
+	}
+	ts2 := NewTimestamp()
+	blocksWithTimestamps2, mainChain2, err := ts2.ProcessBlocks(totalChain)
+	s.Require().Nil(err)
+	timestamps2 := extractTimestamps(blocksWithTimestamps2)
+	s.Equal(totalMainChain, mainChain2)
+	s.Equal(totalTimestamps, timestamps2)
+}
+
+func timeDiffWithinTolerance(t1, t2 time.Time, tolerance time.Duration) bool {
+	if t1.After(t2) {
+		return timeDiffWithinTolerance(t2, t1, tolerance)
+	}
+	return t1.Add(tolerance).After(t2)
+}
+
+func (s *TimestampTest) TestTimestampIncrease() {
+	validatorNum := 19
+	sigma := 100 * time.Millisecond
+	ts := NewTimestamp()
+	chain := generateBlocksWithAcks(1000, 5)
+	fillBlocksTimestamps(chain, validatorNum, time.Second, sigma)
+	blocksWithTimestamps, _, err := ts.ProcessBlocks(chain)
+	s.Require().Nil(err)
+	timestamps := extractTimestamps(blocksWithTimestamps)
+	for i := 1; i < len(timestamps); i++ {
+		s.True(timestamps[i].After(timestamps[i-1]))
+	}
+	// Test if the ProcessBlocks is stable.
+	ts2 := NewTimestamp()
+	blocksWithTimestamps2, _, err := ts2.ProcessBlocks(chain)
+	s.Require().Nil(err)
+	timestamps2 := extractTimestamps(blocksWithTimestamps2)
+	s.Equal(timestamps, timestamps2)
+}
+
+func (s *TimestampTest) TestByzantineBiasTime() {
+	// Test that Byzantine node cannot bias the timestamps.
+	validatorNum := 19
+	sigma := 100 * time.Millisecond
+	tolerance := 4 * sigma
+	ts := NewTimestamp()
+	chain := generateBlocksWithAcks(1000, 5)
+	fillBlocksTimestamps(chain, validatorNum, time.Second, sigma)
+	blocksWithTimestamps, _, err := ts.ProcessBlocks(chain)
+	s.Require().Nil(err)
+	timestamps := extractTimestamps(blocksWithTimestamps)
+	byzantine := validatorNum / 3
+	validators := make([]types.ValidatorID, 0, validatorNum)
+	for vID := range chain[0].Timestamps {
+		validators = append(validators, vID)
+	}
+	// The number of Byzantine node is at most N/3.
+	for i := 0; i < byzantine; i++ {
+		// Pick one validator to be Byzantine node.
+		// It is allowed to have the vID be duplicated,
+		// because the number of Byzantine node is between 1 and N/3.
+		vID := validators[rand.Intn(validatorNum)]
+		for _, block := range chain {
+			block.Timestamps[vID] = time.Time{}
+		}
+	}
+	tsByzantine := NewTimestamp()
+	blocksWithTimestampsB, _, err := tsByzantine.ProcessBlocks(chain)
+	s.Require().Nil(err)
+	timestampsWithByzantine := extractTimestamps(blocksWithTimestampsB)
+	for idx, timestamp := range timestamps {
+		timestampWithByzantine := timestampsWithByzantine[idx]
+		s.True(timeDiffWithinTolerance(
+			timestamp, timestampWithByzantine, tolerance))
+	}
+}
+
+func TestTimestamp(t *testing.T) {
+	suite.Run(t, new(TimestampTest))
+}
diff --git a/core/types/block.go b/core/types/block.go
index c445fd2..56b456c 100644
--- a/core/types/block.go
+++ b/core/types/block.go
@@ -2,16 +2,16 @@
 // 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 Pubic License as
-// pubished by the Free Software Foundation, either version 3 of the License,
+// 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 Pubic License for more details.
+// General Public License for more details.
 //
-// You should have received a copy of the GNU Lesser General Pubic License
+// 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/>.
 
@@ -38,12 +38,14 @@ const (
 
 // Block represents a single event broadcasted on the network.
 type Block struct {
-	ProposerID ValidatorID               `json:"proposer_id"`
-	ParentHash common.Hash               `json:"parent_hash"`
-	Hash       common.Hash               `json:"hash"`
-	Height     uint64                    `json:"height"`
-	Timestamps map[ValidatorID]time.Time `json:"timestamps"`
-	Acks       map[common.Hash]struct{}  `json:"acks"`
+	ProposerID      ValidatorID               `json:"proposer_id"`
+	ParentHash      common.Hash               `json:"parent_hash"`
+	Hash            common.Hash               `json:"hash"`
+	Height          uint64                    `json:"height"`
+	Timestamps      map[ValidatorID]time.Time `json:"timestamps"`
+	Acks            map[common.Hash]struct{}  `json:"acks"`
+	ConsensusTime   time.Time                 `json:"consensus_time"`
+	ConsensusHeight uint64                    `json:"consensus_height"`
 
 	Ackeds          map[common.Hash]struct{} `json:"-"`
 	AckedValidators map[ValidatorID]struct{} `json:"-"`