From 582a491aa0bcb784ac7b65ebbfb42139945ea703 Mon Sep 17 00:00:00 2001 From: Jimmy Hu Date: Tue, 11 Sep 2018 13:28:44 +0800 Subject: core: timestamp (#98) --- blockdb/level-db_test.go | 6 +- core/consensus-timestamp.go | 78 ++++----------- core/consensus-timestamp_test.go | 199 +++++++++++++-------------------------- core/consensus.go | 11 +-- core/consensus_test.go | 11 ++- core/crypto.go | 20 +--- core/crypto_test.go | 9 +- core/reliable-broadcast.go | 53 ++--------- core/reliable-broadcast_test.go | 53 ++++------- core/test/blocks-generator.go | 40 ++++---- core/types/block.go | 29 ++---- core/utils.go | 23 +++-- simulation/app.go | 2 +- 13 files changed, 173 insertions(+), 361 deletions(-) diff --git a/blockdb/level-db_test.go b/blockdb/level-db_test.go index d1c8146..06829f0 100644 --- a/blockdb/level-db_test.go +++ b/blockdb/level-db_test.go @@ -73,9 +73,7 @@ func (s *LevelDBTestSuite) TestBasicUsage() { // Test Update. now := time.Now().UTC() - queried.Timestamps = map[types.ValidatorID]time.Time{ - queried.ProposerID: now, - } + queried.Timestamp = now err = db.Update(queried) s.Nil(err) @@ -84,7 +82,7 @@ func (s *LevelDBTestSuite) TestBasicUsage() { queried, err = db.Get(block1.Hash) s.Nil(err) - s.Equal(now, queried.Timestamps[queried.ProposerID]) + s.Equal(now, queried.Timestamp) } func (s *LevelDBTestSuite) TestSyncIndex() { diff --git a/core/consensus-timestamp.go b/core/consensus-timestamp.go index 90489ed..62bdf0c 100644 --- a/core/consensus-timestamp.go +++ b/core/consensus-timestamp.go @@ -19,20 +19,20 @@ package core import ( "errors" + "time" "github.com/dexon-foundation/dexon-consensus-core/core/types" ) // consensusTimestamp is for Concensus Timestamp Algorithm. type consensusTimestamp struct { - lastMainChainBlock *types.Block - blocksNotInMainChain []*types.Block + chainTimestamps []time.Time } var ( - // ErrInvalidMainChain would be reported if the invalid result from - // main chain selection algorithm is detected. - ErrInvalidMainChain = errors.New("invalid main chain") + // ErrTimestampNotIncrease would be reported if the timestamp is not strickly + // increasing on the same chain. + ErrTimestampNotIncrease = errors.New("timestamp is not increasing") ) // newConsensusTimestamp create timestamper object. @@ -41,68 +41,24 @@ func newConsensusTimestamp() *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].Notary.Timestamp, err = - getMedianTime(block) +func (ct *consensusTimestamp) processBlocks(blocks []*types.Block) (err error) { + for _, block := range blocks { + if !block.IsGenesis() { + block.Notary.Timestamp, err = getMedianTime(ct.chainTimestamps) if err != nil { return } - // Process Non-MainChain blocks. - if rightMainChainIdx > leftMainChainIdx { - for idx, timestamp := range interpoTime( - blocksWithTimestamp[leftMainChainIdx].Notary.Timestamp, - blocksWithTimestamp[rightMainChainIdx].Notary.Timestamp, - rightMainChainIdx-leftMainChainIdx-1) { - blocksWithTimestamp[leftMainChainIdx+idx+1].Notary.Timestamp = - 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 - } + for uint32(len(ct.chainTimestamps)) <= block.Position.ChainID { + ct.chainTimestamps = append(ct.chainTimestamps, time.Time{}) } - nonMainChain = []*types.Block{} - mainChain = append(mainChain, block) + + if !block.Timestamp.After(ct.chainTimestamps[block.Position.ChainID]) { + return ErrTimestampNotIncrease + } + + ct.chainTimestamps[block.Position.ChainID] = block.Timestamp } return } diff --git a/core/consensus-timestamp_test.go b/core/consensus-timestamp_test.go index 6dff111..56dd306 100644 --- a/core/consensus-timestamp_test.go +++ b/core/consensus-timestamp_test.go @@ -33,174 +33,109 @@ type ConsensusTimestampTest struct { suite.Suite } -func generateBlocksWithAcks(blockNum, maxAcks int) []*types.Block { - chain := []*types.Block{ - &types.Block{ - Hash: common.NewRandomHash(), - Acks: make(map[common.Hash]struct{}), - }, +func (s *ConsensusTimestampTest) generateBlocksWithTimestamp( + blockNum, chainNum int, + step, sigma time.Duration) []*types.Block { + blocks := make([]*types.Block, blockNum) + chainIDs := make([]uint32, len(blocks)) + for i := range chainIDs { + chainIDs[i] = uint32(i % chainNum) } - 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{}{} + rand.Shuffle(len(chainIDs), func(i, j int) { + chainIDs[i], chainIDs[j] = chainIDs[j], chainIDs[i] + }) + chainTimestamps := make(map[uint32]time.Time) + for idx := range blocks { + blocks[idx] = &types.Block{} + block := blocks[idx] + if idx < chainNum { + // Genesis blocks. + block.Position.ChainID = uint32(idx) + block.ParentHash = common.Hash{} + block.Position.Height = 0 + s.Require().True(block.IsGenesis()) + chainTimestamps[uint32(idx)] = time.Now().UTC() + } else { + block.Position.ChainID = chainIDs[idx] + // Assign 1 to height to make this block non-genesis. + block.Position.Height = 1 + s.Require().False(block.IsGenesis()) } - block := &types.Block{ - Hash: common.NewRandomHash(), - Acks: acks, - } - chain = append(chain, block) + block.Timestamp = chainTimestamps[block.Position.ChainID] + // Update timestamp for next block. + diffSeconds := rand.NormFloat64() * sigma.Seconds() + diffSeconds = math.Min(diffSeconds, step.Seconds()/2.1) + diffSeconds = math.Max(diffSeconds, -step.Seconds()/2.1) + diffDuration := time.Duration(diffSeconds*1000) * time.Millisecond + chainTimestamps[block.Position.ChainID] = + chainTimestamps[block.Position.ChainID].Add(step).Add(diffDuration) + s.Require().True(block.Timestamp.Before( + chainTimestamps[block.Position.ChainID])) } - return chain + return blocks } -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()} - } +func (s *ConsensusTimestampTest) extractTimestamps( + blocks []*types.Block) []time.Time { + timestamps := make([]time.Time, 0, len(blocks)) 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) + if block.IsGenesis() { + continue } - 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.Notary.Timestamp + timestamps = append(timestamps, block.Notary.Timestamp) } return timestamps } -func (s *ConsensusTimestampTest) TestMainChainSelection() { - ct := newConsensusTimestamp() - ct2 := newConsensusTimestamp() - blockNums := []int{50, 100, 30} - maxAcks := 5 - for _, blockNum := range blockNums { - chain := generateBlocksWithAcks(blockNum, maxAcks) - mainChain, _ := ct.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, _ := ct2.selectMainChain(chain) - s.Equal(mainChain, mainChain2) - } -} - +// TestTimestampPartition verifies that processing segments of compatction chain +// should have the same result as processing the whole chain at once. func (s *ConsensusTimestampTest) 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) ct := newConsensusTimestamp() - var lastMainChainBlock *types.Block + totalBlockNum := 0 for _, blockNum := range blockNums { - chain := generateBlocksWithAcks(blockNum, maxAcks) - fillBlocksTimestamps(chain, validatorNum, time.Second, sigma) - blocksWithTimestamps, mainChain, err := ct.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], ct.lastMainChainBlock) - lastMainChainBlock = ct.lastMainChainBlock - totalMainChain = - append(totalMainChain[:len(totalMainChain)-1], mainChain...) + totalBlockNum += blockNum + } + totalChain := s.generateBlocksWithTimestamp( + totalBlockNum, validatorNum, time.Second, sigma) + for _, blockNum := range blockNums { + var chain []*types.Block + chain, totalChain = totalChain[:blockNum], totalChain[blockNum:] + err := ct.processBlocks(chain) + s.Require().NoError(err) + timestamps := s.extractTimestamps(chain) totalChain = append(totalChain, chain...) totalTimestamps = append(totalTimestamps, timestamps...) } ct2 := newConsensusTimestamp() - blocksWithTimestamps2, mainChain2, err := ct2.processBlocks(totalChain) - s.Require().Nil(err) - timestamps2 := extractTimestamps(blocksWithTimestamps2) - s.Equal(totalMainChain, mainChain2) + err := ct2.processBlocks(totalChain) + s.Require().NoError(err) + timestamps2 := s.extractTimestamps(totalChain) 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 *ConsensusTimestampTest) TestTimestampIncrease() { validatorNum := 19 sigma := 100 * time.Millisecond ct := newConsensusTimestamp() - chain := generateBlocksWithAcks(1000, 5) - fillBlocksTimestamps(chain, validatorNum, time.Second, sigma) - blocksWithTimestamps, _, err := ct.processBlocks(chain) - s.Require().Nil(err) - timestamps := extractTimestamps(blocksWithTimestamps) + chain := s.generateBlocksWithTimestamp(1000, validatorNum, time.Second, sigma) + err := ct.processBlocks(chain) + s.Require().NoError(err) + timestamps := s.extractTimestamps(chain) for i := 1; i < len(timestamps); i++ { - s.True(timestamps[i].After(timestamps[i-1])) + s.False(timestamps[i].Before(timestamps[i-1])) } // Test if the processBlocks is stable. ct2 := newConsensusTimestamp() - blocksWithTimestamps2, _, err := ct2.processBlocks(chain) - s.Require().Nil(err) - timestamps2 := extractTimestamps(blocksWithTimestamps2) + ct2.processBlocks(chain) + s.Require().NoError(err) + timestamps2 := s.extractTimestamps(chain) s.Equal(timestamps, timestamps2) } -func (s *ConsensusTimestampTest) TestByzantineBiasTime() { - // Test that Byzantine node cannot bias the timestamps. - validatorNum := 19 - sigma := 100 * time.Millisecond - tolerance := 4 * sigma - ct := newConsensusTimestamp() - chain := generateBlocksWithAcks(1000, 5) - fillBlocksTimestamps(chain, validatorNum, time.Second, sigma) - blocksWithTimestamps, _, err := ct.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{} - } - } - ctByzantine := newConsensusTimestamp() - blocksWithTimestampsB, _, err := ctByzantine.processBlocks(chain) - s.Require().Nil(err) - timestampsWithByzantine := extractTimestamps(blocksWithTimestampsB) - for idx, timestamp := range timestamps { - timestampWithByzantine := timestampsWithByzantine[idx] - s.True(timeDiffWithinTolerance( - timestamp, timestampWithByzantine, tolerance)) - } -} - func TestConsensusTimestamp(t *testing.T) { suite.Run(t, new(ConsensusTimestampTest)) } diff --git a/core/consensus.go b/core/consensus.go index 6d74bd7..a9ec6a5 100644 --- a/core/consensus.go +++ b/core/consensus.go @@ -467,8 +467,7 @@ func (con *Consensus) ProcessBlock(block *types.Block) (err error) { } con.app.TotalOrderingDeliver(hashes, earlyDelivered) // Perform timestamp generation. - deliveredBlocks, _, err = con.ctModule.processBlocks( - deliveredBlocks) + err = con.ctModule.processBlocks(deliveredBlocks) if err != nil { return } @@ -518,7 +517,7 @@ func (con *Consensus) PrepareBlock(b *types.Block, defer con.lock.RUnlock() con.rbModule.prepareBlock(b) - b.Timestamps[b.ProposerID] = proposeTime + b.Timestamp = proposeTime b.Payloads = con.app.PreparePayloads(b.Position) b.Hash, err = hashBlock(b) if err != nil { @@ -544,11 +543,7 @@ func (con *Consensus) PrepareGenesisBlock(b *types.Block, b.Position.Height = 0 b.ParentHash = common.Hash{} b.Acks = make(map[common.Hash]struct{}) - b.Timestamps = make(map[types.ValidatorID]time.Time) - for vID := range con.gov.GetValidatorSet() { - b.Timestamps[vID] = time.Time{} - } - b.Timestamps[b.ProposerID] = proposeTime + b.Timestamp = proposeTime b.Hash, err = hashBlock(b) if err != nil { return diff --git a/core/consensus_test.go b/core/consensus_test.go index aec0e4c..a66a459 100644 --- a/core/consensus_test.go +++ b/core/consensus_test.go @@ -290,7 +290,12 @@ func (s *ConsensusTestSuite) TestSimpleDeliverBlock() { // Check timestamps, there is no direct way to know which block is // selected as main chain, we can only detect it by making sure // its ConsensusTimestamp is not interpolated. - t, err := getMedianTime(b11) + timestamps := make([]time.Time, 4) + timestamps[0] = b00.Timestamp + timestamps[1] = b10.Timestamp + timestamps[2] = b20.Timestamp + timestamps[3] = b30.Timestamp + t, err := getMedianTime(timestamps) req.Nil(err) req.Equal(t, app.Delivered[b11.Hash].ConsensusTime) } @@ -355,8 +360,8 @@ func (s *ConsensusTestSuite) TestPrepareBlock() { // Make sure we would assign 'now' to the timestamp belongs to // the proposer. req.True( - b11.Timestamps[validators[1]].Sub( - b10.Timestamps[validators[1]]) > 100*time.Millisecond) + b11.Timestamp.Sub( + b10.Timestamp) > 100*time.Millisecond) for _, obj := range objs { con := obj.con req.Nil(con.ProcessBlock(b11)) diff --git a/core/crypto.go b/core/crypto.go index f097703..656dd74 100644 --- a/core/crypto.go +++ b/core/crypto.go @@ -62,22 +62,10 @@ func hashBlock(block *types.Block) (common.Hash, error) { binaryAcks[idx] = acks[idx][:] } hashAcks := crypto.Keccak256Hash(binaryAcks...) - // Handle Block.Timestamps. - // TODO(jimmy-dexon): Store and get the sorted validatorIDs. - validators := make(types.ValidatorIDs, 0, len(block.Timestamps)) - for vID := range block.Timestamps { - validators = append(validators, vID) - } - sort.Sort(validators) - binaryTimestamps := make([][]byte, len(block.Timestamps)) - for idx, vID := range validators { - var err error - binaryTimestamps[idx], err = block.Timestamps[vID].MarshalBinary() - if err != nil { - return common.Hash{}, err - } + binaryTimestamp, err := block.Timestamp.MarshalBinary() + if err != nil { + return common.Hash{}, err } - hashTimestamps := crypto.Keccak256Hash(binaryTimestamps...) payloadHash := crypto.Keccak256Hash(block.Payloads...) hash := crypto.Keccak256Hash( @@ -85,7 +73,7 @@ func hashBlock(block *types.Block) (common.Hash, error) { block.ParentHash[:], hashPosition[:], hashAcks[:], - hashTimestamps[:], + binaryTimestamp[:], payloadHash[:]) return hash, nil } diff --git a/core/crypto_test.go b/core/crypto_test.go index 4fa0e1b..29a45f6 100644 --- a/core/crypto_test.go +++ b/core/crypto_test.go @@ -36,12 +36,11 @@ var myVID = types.ValidatorID{Hash: common.NewRandomHash()} func (s *CryptoTestSuite) prepareBlock(prevBlock *types.Block) *types.Block { acks := make(map[common.Hash]struct{}) - timestamps := make(map[types.ValidatorID]time.Time) - timestamps[myVID] = time.Now().UTC() + now := time.Now().UTC() if prevBlock == nil { return &types.Block{ - Acks: acks, - Timestamps: timestamps, + Acks: acks, + Timestamp: now, Notary: types.Notary{ Timestamp: time.Now(), Height: 0, @@ -55,7 +54,7 @@ func (s *CryptoTestSuite) prepareBlock(prevBlock *types.Block) *types.Block { return &types.Block{ ParentHash: prevBlock.Hash, Acks: acks, - Timestamps: timestamps, + Timestamp: now, Position: types.Position{ Height: prevBlock.Position.Height + 1, }, diff --git a/core/reliable-broadcast.go b/core/reliable-broadcast.go index 7cca4f1..7d3ba2d 100644 --- a/core/reliable-broadcast.go +++ b/core/reliable-broadcast.go @@ -140,22 +140,11 @@ func (rb *reliableBroadcast) sanityCheck(b *types.Block) error { } } - // TODO(jimmy-dexon): verify the timestamps. - /* - // Check if its timestamp is valid. - for h := range rb.lattice { - if _, exist := b.Timestamps[h]; !exist { - return ErrInvalidTimestamp - } - } - */ - + // Check if its timestamp is valid. if bParent, exist := rb.lattice[b.Position.ChainID].blocks[b.Position.Height-1]; exist { - for hash := range b.Timestamps { - if b.Timestamps[hash].Before(bParent.Timestamps[hash]) { - return ErrInvalidTimestamp - } + if !b.Timestamp.After(bParent.Timestamp) { + return ErrInvalidTimestamp } } @@ -370,36 +359,6 @@ func (rb *reliableBroadcast) prepareBlock(block *types.Block) { // Reset fields to make sure we got these information from parent block. block.Position.Height = 0 block.ParentHash = common.Hash{} - // The helper function to accumulate timestamps. - accumulateTimestamps := func( - times map[types.ValidatorID]time.Time, b *types.Block) { - - // Update timestamps with the block's proposer time. - // TODO (mission): make epslon configurable. - times[b.ProposerID] = b.Timestamps[b.ProposerID].Add( - 1 * time.Millisecond) - - // Update timestamps from the block if it's later than - // current cached ones. - for vID, t := range b.Timestamps { - cachedTime, exists := times[vID] - if !exists { - // This means the block contains timestamps from - // removed validators. - continue - } - if cachedTime.After(t) { - continue - } - times[vID] = t - } - return - } - // Initial timestamps with current validator set. - times := make(map[types.ValidatorID]time.Time) - for vID := range rb.validators { - times[vID] = time.Time{} - } acks := make(map[common.Hash]struct{}) for chainID := range rb.lattice { // find height of the latest block for that validator. @@ -420,15 +379,17 @@ func (rb *reliableBroadcast) prepareBlock(block *types.Block) { continue } acks[curBlock.Hash] = struct{}{} - accumulateTimestamps(times, curBlock) if uint32(chainID) == block.Position.ChainID { block.ParentHash = curBlock.Hash + if block.Timestamp.Before(curBlock.Timestamp) { + // TODO (mission): make epslon configurable. + block.Timestamp = curBlock.Timestamp.Add(1 * time.Millisecond) + } if block.Position.Height == 0 { block.Position.Height = curBlock.Position.Height + 1 } } } - block.Timestamps = times block.Acks = acks return } diff --git a/core/reliable-broadcast_test.go b/core/reliable-broadcast_test.go index 2c71bcb..eedb634 100644 --- a/core/reliable-broadcast_test.go +++ b/core/reliable-broadcast_test.go @@ -55,8 +55,8 @@ func (s *ReliableBroadcastTest) prepareGenesisBlock( Position: types.Position{ Height: 0, }, - Acks: make(map[common.Hash]struct{}), - Timestamps: genTimestamps(validatorIDs), + Acks: make(map[common.Hash]struct{}), + Timestamp: time.Now().UTC(), } for i, vID := range validatorIDs { if proposerID == vID { @@ -64,24 +64,13 @@ func (s *ReliableBroadcastTest) prepareGenesisBlock( break } } - for _, vID := range validatorIDs { - b.Timestamps[vID] = time.Time{} - } - b.Timestamps[proposerID] = time.Now().UTC() + b.Timestamp = time.Now().UTC() var err error b.Hash, err = hashBlock(b) s.Require().Nil(err) return } -func genTimestamps(vids []types.ValidatorID) map[types.ValidatorID]time.Time { - ts := make(map[types.ValidatorID]time.Time) - for _, vid := range vids { - ts[vid] = time.Now().UTC() - } - return ts -} - // genTestCase1 generates test case 1, // 3 // | @@ -115,7 +104,7 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid ProposerID: vids[0], ParentHash: h, Hash: common.NewRandomHash(), - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Position: types.Position{ ChainID: 0, Height: 1, @@ -139,7 +128,7 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid ChainID: 0, Height: 2, }, - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Acks: map[common.Hash]struct{}{ h: struct{}{}, rb.lattice[1].blocks[0].Hash: struct{}{}, @@ -156,7 +145,7 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid ProposerID: vids[0], ParentHash: h, Hash: common.NewRandomHash(), - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Position: types.Position{ ChainID: 0, Height: 3, @@ -176,7 +165,7 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid ProposerID: vids[3], ParentHash: h, Hash: common.NewRandomHash(), - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Position: types.Position{ ChainID: 3, Height: 1, @@ -313,9 +302,7 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { Acks: map[common.Hash]struct{}{ h: struct{}{}, }, - Timestamps: map[types.ValidatorID]time.Time{ - vids[0]: time.Now().UTC(), - }, + Timestamp: time.Now().UTC(), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -356,7 +343,7 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { h: struct{}{}, common.NewRandomHash(): struct{}{}, }, - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -415,7 +402,7 @@ func (s *ReliableBroadcastTest) TestStrongAck() { ChainID: 1, Height: 1, }, - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Acks: map[common.Hash]struct{}{ rb.lattice[0].blocks[2].Hash: struct{}{}, rb.lattice[1].blocks[0].Hash: struct{}{}, @@ -441,7 +428,7 @@ func (s *ReliableBroadcastTest) TestStrongAck() { ChainID: 2, Height: 1, }, - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Acks: map[common.Hash]struct{}{ rb.lattice[0].blocks[2].Hash: struct{}{}, rb.lattice[2].blocks[0].Hash: struct{}{}, @@ -471,7 +458,7 @@ func (s *ReliableBroadcastTest) TestExtractBlocks() { ChainID: 1, Height: 1, }, - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Acks: map[common.Hash]struct{}{ rb.lattice[0].blocks[2].Hash: struct{}{}, rb.lattice[1].blocks[0].Hash: struct{}{}, @@ -492,7 +479,7 @@ func (s *ReliableBroadcastTest) TestExtractBlocks() { ChainID: 2, Height: 1, }, - Timestamps: genTimestamps(vids), + Timestamp: time.Now().UTC(), Acks: map[common.Hash]struct{}{ rb.lattice[0].blocks[2].Hash: struct{}{}, rb.lattice[2].blocks[0].Hash: struct{}{}, @@ -556,8 +543,8 @@ func (s *ReliableBroadcastTest) TestRandomIntensiveAcking() { ChainID: uint32(id), Height: height, }, - Timestamps: genTimestamps(vids), - Acks: acks, + Timestamp: time.Now().UTC(), + Acks: acks, } var err error b.Hash, err = hashBlock(b) @@ -687,14 +674,8 @@ func (s *ReliableBroadcastTest) TestPrepareBlock() { req.Contains(b11.Acks, b10.Hash) req.Contains(b11.Acks, b20.Hash) req.Contains(b11.Acks, b30.Hash) - req.Equal(b11.Timestamps[validators[0]], - b00.Timestamps[b00.ProposerID].Add(time.Millisecond)) - req.Equal(b11.Timestamps[validators[1]], - b10.Timestamps[b10.ProposerID].Add(time.Millisecond)) - req.Equal(b11.Timestamps[validators[2]], - b20.Timestamps[b20.ProposerID].Add(time.Millisecond)) - req.Equal(b11.Timestamps[validators[3]], - b30.Timestamps[b30.ProposerID].Add(time.Millisecond)) + req.Equal(b11.Timestamp, + b10.Timestamp.Add(time.Millisecond)) req.Equal(b11.ParentHash, b10.Hash) req.Equal(b11.Position.Height, uint64(1)) s.Require().Nil(rb.processBlock(b11)) diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go index 18e4995..f3e914e 100644 --- a/core/test/blocks-generator.go +++ b/core/test/blocks-generator.go @@ -70,25 +70,33 @@ func (vs *validatorStatus) getAckedBlockHash( // validatorSetStatus is a state holder for all validators // during generating blocks. type validatorSetStatus struct { - status map[types.ValidatorID]*validatorStatus - validatorIDs []types.ValidatorID - randGen *rand.Rand - hashBlock hashBlockFn + status map[types.ValidatorID]*validatorStatus + proposerChain map[types.ValidatorID]uint32 + timestamps []time.Time + validatorIDs []types.ValidatorID + randGen *rand.Rand + hashBlock hashBlockFn } func newValidatorSetStatus(vIDs []types.ValidatorID, hashBlock hashBlockFn) *validatorSetStatus { status := make(map[types.ValidatorID]*validatorStatus) - for _, vID := range vIDs { + timestamps := make([]time.Time, 0, len(vIDs)) + proposerChain := make(map[types.ValidatorID]uint32) + for i, vID := range vIDs { status[vID] = &validatorStatus{ blocks: []*types.Block{}, lastAckingHeight: make(map[types.ValidatorID]uint64), } + timestamps = append(timestamps, time.Now().UTC()) + proposerChain[vID] = uint32(i) } return &validatorSetStatus{ - status: status, - validatorIDs: vIDs, - randGen: rand.New(rand.NewSource(time.Now().UnixNano())), - hashBlock: hashBlock, + status: status, + proposerChain: proposerChain, + timestamps: timestamps, + validatorIDs: vIDs, + randGen: rand.New(rand.NewSource(time.Now().UnixNano())), + hashBlock: hashBlock, } } @@ -150,20 +158,18 @@ func (vs *validatorSetStatus) proposeBlock( if len(status.blocks) > 0 { parentHash = status.blocks[len(status.blocks)-1].Hash } + chainID := vs.proposerChain[proposerID] + vs.timestamps[chainID] = vs.timestamps[chainID].Add(time.Second) - ts := map[types.ValidatorID]time.Time{} - for vid := range vs.status { - ts[vid] = time.Time{} - } newBlock := &types.Block{ ProposerID: proposerID, ParentHash: parentHash, Position: types.Position{ - Height: uint64(len(status.blocks)), + Height: uint64(len(status.blocks)), + ChainID: chainID, }, - Acks: acks, - Timestamps: ts, - // TODO(mission.liao): Generate timestamp. + Acks: acks, + Timestamp: vs.timestamps[chainID], } for i, vID := range vs.validatorIDs { if vID == proposerID { diff --git a/core/types/block.go b/core/types/block.go index f02b1a0..3585a97 100644 --- a/core/types/block.go +++ b/core/types/block.go @@ -52,24 +52,19 @@ func NewBlock() (b *Block) { delete(b.Acks, k) } } - if b.Timestamps != nil { - for k := range b.Timestamps { - delete(b.Timestamps, k) - } - } return } // 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"` - Position Position `json:"position"` - Timestamps map[ValidatorID]time.Time `json:"timestamps"` - Acks map[common.Hash]struct{} `json:"acks"` - Payloads [][]byte `json:"payloads"` - Signature crypto.Signature `json:"signature"` + ProposerID ValidatorID `json:"proposer_id"` + ParentHash common.Hash `json:"parent_hash"` + Hash common.Hash `json:"hash"` + Position Position `json:"position"` + Timestamp time.Time `json:"timestamps"` + Acks map[common.Hash]struct{} `json:"acks"` + Payloads [][]byte `json:"payloads"` + Signature crypto.Signature `json:"signature"` CRSSignature crypto.Signature `json:"crs_signature"` @@ -94,13 +89,7 @@ func (b *Block) Clone() (bcopy *Block) { bcopy.CRSSignature = b.CRSSignature.Clone() bcopy.Notary.Timestamp = b.Notary.Timestamp bcopy.Notary.Height = b.Notary.Height - if bcopy.Timestamps == nil { - bcopy.Timestamps = make( - map[ValidatorID]time.Time, len(b.Timestamps)) - } - for k, v := range b.Timestamps { - bcopy.Timestamps[k] = v - } + bcopy.Timestamp = b.Timestamp if bcopy.Acks == nil { bcopy.Acks = make(map[common.Hash]struct{}, len(b.Acks)) } diff --git a/core/utils.go b/core/utils.go index 6b03f93..59aa7a4 100644 --- a/core/utils.go +++ b/core/utils.go @@ -25,7 +25,6 @@ import ( "time" "github.com/dexon-foundation/dexon-consensus-core/common" - "github.com/dexon-foundation/dexon-consensus-core/core/types" ) var ( @@ -72,25 +71,25 @@ func interpoTime(t1 time.Time, t2 time.Time, sep int) []time.Time { } return timestamps } -func getMedianTime(block *types.Block) (t time.Time, err error) { - timestamps := []time.Time{} - for _, timestamp := range block.Timestamps { - timestamps = append(timestamps, timestamp) - } + +func getMedianTime(timestamps []time.Time) (t time.Time, err error) { 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] + tscopy := make([]time.Time, 0, len(timestamps)) + for _, ts := range timestamps { + tscopy = append(tscopy, ts) + } + sort.Sort(common.ByTime(tscopy)) + if len(tscopy)%2 == 0 { + t1 := tscopy[len(tscopy)/2-1] + t2 := tscopy[len(tscopy)/2] t = interpoTime(t1, t2, 1)[0] } else { - t = timestamps[len(timestamps)/2] + t = tscopy[len(tscopy)/2] } return - } func removeFromSortedIntSlice(xs []int, x int) []int { diff --git a/simulation/app.go b/simulation/app.go index 4bf4aff..5a31273 100644 --- a/simulation/app.go +++ b/simulation/app.go @@ -124,7 +124,7 @@ func (a *simApp) TotalOrderingDeliver(blockHashes common.Hashes, early bool) { for _, block := range blocks { if block.ProposerID == a.ValidatorID { confirmLatency = append(confirmLatency, - now.Sub(block.Timestamps[a.ValidatorID])) + now.Sub(block.Timestamp)) } for hash := range block.Acks { for _, blockHash := range a.getAckedBlocks(hash) { -- cgit v1.2.3