From 75281fcfc95434672781785ee8f70a0f319470cf Mon Sep 17 00:00:00 2001 From: Mission Liao Date: Mon, 6 Aug 2018 14:36:07 +0800 Subject: Rename names of struct and files Rename these files: - core/sequencer[_test].go -> core/total-ordering[_test].go - core/acking[_test].go -> core/reliable-broadcast[_test].go - core/timestamp[_test].go -> core/consensus-timestamp[_test].go Rename these structs: - core.sequencer -> core.totalOrdering - core.acking -> core.reliableBroadcast - core.timestamp -> core.consensusTimestamp --- core/consensus-timestamp.go | 151 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 151 insertions(+) create mode 100644 core/consensus-timestamp.go (limited to 'core/consensus-timestamp.go') diff --git a/core/consensus-timestamp.go b/core/consensus-timestamp.go new file mode 100644 index 0000000..e9b5cce --- /dev/null +++ b/core/consensus-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 +// . + +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 consensusTimestamp 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 newConsensusTimestamp() *consensusTimestamp { + return &consensusTimestamp{} +} + +// ProcessBlocks is the entry function. +func (ct *consensusTimestamp) 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(ct.blocksNotInMainChain, blocks...) + if ct.lastMainChainBlock != nil { + // TODO (jimmy-dexon): The performance here can be optimized. + blocks = append([]*types.Block{ct.lastMainChainBlock}, blocks...) + outputFirstBlock = false + } + mainChain, nonMainChain := ct.selectMainChain(blocks) + ct.blocksNotInMainChain = nonMainChain + ct.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 = ct.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 (ct *consensusTimestamp) 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 (ct *consensusTimestamp) 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 +} -- cgit v1.2.3