From b4af97dd8cfd5bbd7032fb5e1aff240625df06cb Mon Sep 17 00:00:00 2001 From: Mission Liao Date: Wed, 12 Sep 2018 15:35:24 +0800 Subject: core: replace acks with slice (#102) --- core/consensus.go | 1 - core/crypto.go | 10 +-- core/crypto_test.go | 10 +-- core/reliable-broadcast.go | 16 ++-- core/reliable-broadcast_test.go | 117 +++++++++++--------------- core/test/blocks-generator.go | 12 +-- core/test/blocks-generator_test.go | 2 +- core/test/revealer.go | 2 +- core/total-ordering.go | 4 +- core/total-ordering_test.go | 164 ++++++++++--------------------------- core/types/block.go | 39 ++++----- core/types/block_test.go | 14 ++++ 12 files changed, 154 insertions(+), 237 deletions(-) (limited to 'core') diff --git a/core/consensus.go b/core/consensus.go index 0bc7c7d..ef39795 100644 --- a/core/consensus.go +++ b/core/consensus.go @@ -541,7 +541,6 @@ func (con *Consensus) PrepareGenesisBlock(b *types.Block, } b.Position.Height = 0 b.ParentHash = common.Hash{} - b.Acks = make(map[common.Hash]struct{}) b.Timestamp = proposeTime b.Hash, err = hashBlock(b) if err != nil { diff --git a/core/crypto.go b/core/crypto.go index 3fe39ac..402fd2e 100644 --- a/core/crypto.go +++ b/core/crypto.go @@ -19,7 +19,6 @@ package core import ( "encoding/binary" - "sort" "github.com/dexon-foundation/dexon-consensus-core/common" "github.com/dexon-foundation/dexon-consensus-core/core/types" @@ -52,14 +51,9 @@ func verifyNotarySignature(pubkey crypto.PublicKey, func hashBlock(block *types.Block) (common.Hash, error) { hashPosition := hashPosition(block.Position) // Handling Block.Acks. - acks := make(common.Hashes, 0, len(block.Acks)) - for ack := range block.Acks { - acks = append(acks, ack) - } - sort.Sort(acks) binaryAcks := make([][]byte, len(block.Acks)) - for idx := range acks { - binaryAcks[idx] = acks[idx][:] + for idx, ack := range block.Acks { + binaryAcks[idx] = ack[:] } hashAcks := crypto.Keccak256Hash(binaryAcks...) binaryTimestamp, err := block.Timestamp.MarshalBinary() diff --git a/core/crypto_test.go b/core/crypto_test.go index 29a45f6..b96b0bd 100644 --- a/core/crypto_test.go +++ b/core/crypto_test.go @@ -35,11 +35,11 @@ type CryptoTestSuite struct { var myVID = types.ValidatorID{Hash: common.NewRandomHash()} func (s *CryptoTestSuite) prepareBlock(prevBlock *types.Block) *types.Block { - acks := make(map[common.Hash]struct{}) + acks := common.Hashes{} now := time.Now().UTC() if prevBlock == nil { return &types.Block{ - Acks: acks, + Acks: common.NewSortedHashes(acks), Timestamp: now, Notary: types.Notary{ Timestamp: time.Now(), @@ -50,10 +50,10 @@ func (s *CryptoTestSuite) prepareBlock(prevBlock *types.Block) *types.Block { parentHash, err := hashNotary(prevBlock) s.Require().Nil(err) s.Require().NotEqual(prevBlock.Hash, common.Hash{}) - acks[parentHash] = struct{}{} + acks = append(acks, parentHash) return &types.Block{ ParentHash: prevBlock.Hash, - Acks: acks, + Acks: common.NewSortedHashes(acks), Timestamp: now, Position: types.Position{ Height: prevBlock.Position.Height + 1, @@ -170,7 +170,7 @@ func (s *CryptoTestSuite) TestBlockSignature() { } // Modify Block.Acks and verify signature again. for _, block := range blocks { - block.Acks[common.NewRandomHash()] = struct{}{} + block.Acks = append(block.Acks, common.NewRandomHash()) s.False(verifyBlockSignature( pub, block, block.Signature)) } diff --git a/core/reliable-broadcast.go b/core/reliable-broadcast.go index 7d3ba2d..1681270 100644 --- a/core/reliable-broadcast.go +++ b/core/reliable-broadcast.go @@ -120,7 +120,7 @@ func (rb *reliableBroadcast) sanityCheck(b *types.Block) error { // Check non-genesis blocks if it acks its parent. if b.Position.Height > 0 { - if _, exist := b.Acks[b.ParentHash]; !exist { + if !b.IsAcking(b.ParentHash) { return ErrNotAckParent } bParentStat, exists := rb.blockInfos[b.ParentHash] @@ -130,7 +130,7 @@ func (rb *reliableBroadcast) sanityCheck(b *types.Block) error { } // Check if it acks older blocks. - for hash := range b.Acks { + for _, hash := range b.Acks { if bAckStat, exist := rb.blockInfos[hash]; exist { bAck := bAckStat.block if bAck.Position.Height < @@ -155,7 +155,7 @@ func (rb *reliableBroadcast) sanityCheck(b *types.Block) error { // areAllAcksReceived checks if all ack blocks of a block are all in lattice. func (rb *reliableBroadcast) areAllAcksInLattice(b *types.Block) bool { - for h := range b.Acks { + for _, h := range b.Acks { bAckStat, exist := rb.blockInfos[h] if !exist { return false @@ -221,7 +221,7 @@ func (rb *reliableBroadcast) processBlock(block *types.Block) (err error) { chainID := b.Position.ChainID rb.lattice[chainID].blocks[b.Position.Height] = b delete(rb.receivedBlocks, b.Hash) - for h := range b.Acks { + for _, h := range b.Acks { bAckStat := rb.blockInfos[h] // Update nextAck only when bAckStat.block.Position.Height + 1 // is greater. A block might ack blocks proposed by same validator with @@ -324,7 +324,7 @@ func (rb *reliableBroadcast) extractBlocks() []*types.Block { // Check if all acks are in ordering or above status. If a block of an ack // does not exist means that it deleted but its status is definitely Acked // or ordering. - for ackHash := range b.Acks { + for _, ackHash := range b.Acks { bAckStat, exist := rb.blockInfos[ackHash] if !exist { continue @@ -359,7 +359,7 @@ 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{} - acks := make(map[common.Hash]struct{}) + acks := common.Hashes{} for chainID := range rb.lattice { // find height of the latest block for that validator. var ( @@ -378,7 +378,7 @@ func (rb *reliableBroadcast) prepareBlock(block *types.Block) { if curBlock == nil { continue } - acks[curBlock.Hash] = struct{}{} + acks = append(acks, curBlock.Hash) if uint32(chainID) == block.Position.ChainID { block.ParentHash = curBlock.Hash if block.Timestamp.Before(curBlock.Timestamp) { @@ -390,7 +390,7 @@ func (rb *reliableBroadcast) prepareBlock(block *types.Block) { } } } - block.Acks = acks + block.Acks = common.NewSortedHashes(acks) return } diff --git a/core/reliable-broadcast_test.go b/core/reliable-broadcast_test.go index eedb634..bced96a 100644 --- a/core/reliable-broadcast_test.go +++ b/core/reliable-broadcast_test.go @@ -55,7 +55,7 @@ func (s *ReliableBroadcastTest) prepareGenesisBlock( Position: types.Position{ Height: 0, }, - Acks: make(map[common.Hash]struct{}), + Acks: common.NewSortedHashes(common.Hashes{}), Timestamp: time.Now().UTC(), } for i, vID := range validatorIDs { @@ -109,9 +109,7 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid ChainID: 0, Height: 1, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{h}), } var err error b.Hash, err = hashBlock(b) @@ -129,10 +127,10 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid Height: 2, }, Timestamp: time.Now().UTC(), - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - rb.lattice[1].blocks[0].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + h, + rb.lattice[1].blocks[0].Hash, + }), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -150,9 +148,7 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid ChainID: 0, Height: 3, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{h}), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -170,9 +166,7 @@ func genTestCase1(s *ReliableBroadcastTest, rb *reliableBroadcast) []types.Valid ChainID: 3, Height: 1, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{h}), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -208,7 +202,7 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { ChainID: 0, Height: 10, }, - Acks: make(map[common.Hash]struct{}), + Acks: common.NewSortedHashes(common.Hashes{}), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -224,9 +218,8 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { ChainID: 1, Height: 1, }, - Acks: map[common.Hash]struct{}{ - rb.lattice[2].blocks[0].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes( + common.Hashes{rb.lattice[2].blocks[0].Hash}), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -243,9 +236,7 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { ChainID: 1, Height: 2, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{h}), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -261,9 +252,7 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { Position: types.Position{ Height: 1, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{h}), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -280,9 +269,7 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { ChainID: 100, Height: 1, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{h}), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -299,9 +286,7 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { ChainID: 0, Height: 1, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{h}), Timestamp: time.Now().UTC(), } b.Hash, err = hashBlock(b) @@ -319,10 +304,10 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { ChainID: 0, Height: 4, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - rb.lattice[1].blocks[0].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + h, + rb.lattice[1].blocks[0].Hash, + }), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -339,10 +324,10 @@ func (s *ReliableBroadcastTest) TestSanityCheck() { ChainID: 1, Height: 1, }, - Acks: map[common.Hash]struct{}{ - h: struct{}{}, - common.NewRandomHash(): struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + h, + common.NewRandomHash(), + }), Timestamp: time.Now().UTC(), } b.Hash, err = hashBlock(b) @@ -358,24 +343,22 @@ func (s *ReliableBroadcastTest) TestAreAllAcksInLattice() { // Empty ack should get true, although won't pass sanity check. b = &types.Block{ - Acks: map[common.Hash]struct{}{}, + Acks: common.NewSortedHashes(common.Hashes{}), } s.Require().True(rb.areAllAcksInLattice(b)) // Acks blocks in lattice b = &types.Block{ - Acks: map[common.Hash]struct{}{ - rb.lattice[0].blocks[0].Hash: struct{}{}, - rb.lattice[0].blocks[1].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + rb.lattice[0].blocks[0].Hash, + rb.lattice[0].blocks[1].Hash, + }), } s.Require().True(rb.areAllAcksInLattice(b)) // Acks random block hash. b = &types.Block{ - Acks: map[common.Hash]struct{}{ - common.NewRandomHash(): struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{common.NewRandomHash()}), } s.Require().False(rb.areAllAcksInLattice(b)) } @@ -403,10 +386,10 @@ func (s *ReliableBroadcastTest) TestStrongAck() { Height: 1, }, Timestamp: time.Now().UTC(), - Acks: map[common.Hash]struct{}{ - rb.lattice[0].blocks[2].Hash: struct{}{}, - rb.lattice[1].blocks[0].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + rb.lattice[0].blocks[2].Hash, + rb.lattice[1].blocks[0].Hash, + }), } var err error b.Hash, err = hashBlock(b) @@ -429,10 +412,10 @@ func (s *ReliableBroadcastTest) TestStrongAck() { Height: 1, }, Timestamp: time.Now().UTC(), - Acks: map[common.Hash]struct{}{ - rb.lattice[0].blocks[2].Hash: struct{}{}, - rb.lattice[2].blocks[0].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + rb.lattice[0].blocks[2].Hash, + rb.lattice[2].blocks[0].Hash, + }), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -459,11 +442,11 @@ func (s *ReliableBroadcastTest) TestExtractBlocks() { Height: 1, }, Timestamp: time.Now().UTC(), - Acks: map[common.Hash]struct{}{ - rb.lattice[0].blocks[2].Hash: struct{}{}, - rb.lattice[1].blocks[0].Hash: struct{}{}, - rb.lattice[3].blocks[0].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + rb.lattice[0].blocks[2].Hash, + rb.lattice[1].blocks[0].Hash, + rb.lattice[3].blocks[0].Hash, + }), } var err error b.Hash, err = hashBlock(b) @@ -480,11 +463,11 @@ func (s *ReliableBroadcastTest) TestExtractBlocks() { Height: 1, }, Timestamp: time.Now().UTC(), - Acks: map[common.Hash]struct{}{ - rb.lattice[0].blocks[2].Hash: struct{}{}, - rb.lattice[2].blocks[0].Hash: struct{}{}, - rb.lattice[3].blocks[0].Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{ + rb.lattice[0].blocks[2].Hash, + rb.lattice[2].blocks[0].Hash, + rb.lattice[3].blocks[0].Hash, + }), } b.Hash, err = hashBlock(b) s.Require().Nil(err) @@ -530,10 +513,10 @@ func (s *ReliableBroadcastTest) TestRandomIntensiveAcking() { height := heights[vid] heights[vid]++ parentHash := rb.lattice[id].blocks[height-1].Hash - acks := map[common.Hash]struct{}{} + acks := common.Hashes{} for id2 := range vids { if b, exist := rb.lattice[id2].blocks[rb.lattice[id].nextAck[id2]]; exist { - acks[b.Hash] = struct{}{} + acks = append(acks, b.Hash) } } b := &types.Block{ @@ -544,7 +527,7 @@ func (s *ReliableBroadcastTest) TestRandomIntensiveAcking() { Height: height, }, Timestamp: time.Now().UTC(), - Acks: acks, + Acks: common.NewSortedHashes(acks), } var err error b.Hash, err = hashBlock(b) diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go index f3e914e..64ddfe2 100644 --- a/core/test/blocks-generator.go +++ b/core/test/blocks-generator.go @@ -116,9 +116,9 @@ func (vs *validatorSetStatus) findIncompleteValidators( // prepareAcksForNewBlock collects acks for one block. func (vs *validatorSetStatus) prepareAcksForNewBlock( proposerID types.ValidatorID, ackingCount int) ( - acks map[common.Hash]struct{}, err error) { + acks common.Hashes, err error) { - acks = make(map[common.Hash]struct{}) + acks = common.Hashes{} if len(vs.status[proposerID].blocks) == 0 { // The 'Acks' filed of genesis blocks would always be empty. return @@ -143,7 +143,7 @@ func (vs *validatorSetStatus) prepareAcksForNewBlock( } continue } - acks[ack] = struct{}{} + acks = append(acks, ack) } return } @@ -151,7 +151,7 @@ func (vs *validatorSetStatus) prepareAcksForNewBlock( // proposeBlock propose new block and update validator status. func (vs *validatorSetStatus) proposeBlock( proposerID types.ValidatorID, - acks map[common.Hash]struct{}) (*types.Block, error) { + acks common.Hashes) (*types.Block, error) { status := vs.status[proposerID] parentHash := common.Hash{} @@ -168,7 +168,7 @@ func (vs *validatorSetStatus) proposeBlock( Height: uint64(len(status.blocks)), ChainID: chainID, }, - Acks: acks, + Acks: common.NewSortedHashes(acks), Timestamp: vs.timestamps[chainID], } for i, vID := range vs.validatorIDs { @@ -283,7 +283,7 @@ func (gen *BlocksGenerator) Generate( // Propose a new block. var ( proposerID = gen.validatorPicker(notYet) - acks map[common.Hash]struct{} + acks common.Hashes ) acks, err = status.prepareAcksForNewBlock( proposerID, ackingCountGenerator()) diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go index b144100..d46a082 100644 --- a/core/test/blocks-generator_test.go +++ b/core/test/blocks-generator_test.go @@ -80,7 +80,7 @@ func (s *BlocksGeneratorTestCase) TestGenerate() { // Check normal blocks. for index, block := range blocks[1:] { parentAcked := false - for ack := range block.Acks { + for _, ack := range block.Acks { if ack == block.ParentHash { parentAcked = true } diff --git a/core/test/revealer.go b/core/test/revealer.go index f1e3d1a..95eeb7c 100644 --- a/core/test/revealer.go +++ b/core/test/revealer.go @@ -32,7 +32,7 @@ import ( func isAllAckingBlockRevealed( b *types.Block, revealed map[common.Hash]struct{}) bool { - for ack := range b.Acks { + for _, ack := range b.Acks { if _, exists := revealed[ack]; !exists { return false } diff --git a/core/total-ordering.go b/core/total-ordering.go index 0e8aad5..8bf9ad7 100644 --- a/core/total-ordering.go +++ b/core/total-ordering.go @@ -613,7 +613,7 @@ func (to *totalOrdering) buildBlockRelation(b *types.Block) { break } curBlock, toCheck = toCheck[len(toCheck)-1], toCheck[:len(toCheck)-1] - for ack = range curBlock.Acks { + for _, ack = range curBlock.Acks { if acked, exists = to.acked[ack]; !exists { acked = to.objCache.requestAckedVector() to.acked[ack] = acked @@ -728,7 +728,7 @@ func (to *totalOrdering) prepareCandidate(candidate *types.Block) { // isAckOnlyPrecedings is a helper function to check if a block // only contain acks to delivered blocks. func (to *totalOrdering) isAckOnlyPrecedings(b *types.Block) bool { - for ack := range b.Acks { + for _, ack := range b.Acks { if _, pending := to.pendings[ack]; pending { return false } diff --git a/core/total-ordering_test.go b/core/total-ordering_test.go index 8e93fd6..f0d2e34 100644 --- a/core/total-ordering_test.go +++ b/core/total-ordering_test.go @@ -36,7 +36,7 @@ type TotalOrderingTestSuite struct { func (s *TotalOrderingTestSuite) genGenesisBlock( vIDs types.ValidatorIDs, chainID uint32, - acks map[common.Hash]struct{}) *types.Block { + acks common.Hashes) *types.Block { return &types.Block{ ProposerID: vIDs[chainID], @@ -46,7 +46,7 @@ func (s *TotalOrderingTestSuite) genGenesisBlock( Height: 0, ChainID: chainID, }, - Acks: acks, + Acks: common.NewSortedHashes(acks), } } @@ -79,7 +79,7 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() { // A <- B <- C validators := test.GenerateRandomValidatorIDs(5) vID := validators[0] - blockA := s.genGenesisBlock(validators, 0, map[common.Hash]struct{}{}) + blockA := s.genGenesisBlock(validators, 0, common.Hashes{}) blockB := &types.Block{ ProposerID: vID, ParentHash: blockA.Hash, @@ -88,9 +88,7 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() { Height: 1, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - blockA.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{blockA.Hash}), } blockC := &types.Block{ ProposerID: vID, @@ -100,9 +98,7 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() { Height: 2, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - blockB.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{blockB.Hash}), } to := newTotalOrdering(1, 3, uint32(len(validators))) @@ -249,9 +245,7 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() { // create blocks with cycles in acking relation. cycledHash := common.NewRandomHash() - b00 := s.genGenesisBlock(validators, 0, map[common.Hash]struct{}{ - cycledHash: struct{}{}, - }) + b00 := s.genGenesisBlock(validators, 0, common.Hashes{cycledHash}) b01 := &types.Block{ ProposerID: validators[0], ParentHash: b00.Hash, @@ -260,9 +254,7 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() { Height: 1, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - b00.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b00.Hash}), } b02 := &types.Block{ ProposerID: validators[0], @@ -272,9 +264,7 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() { Height: 2, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - b01.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b01.Hash}), } b03 := &types.Block{ ProposerID: validators[0], @@ -284,14 +274,12 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() { Height: 3, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - b02.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b02.Hash}), } // Create a block acks self. - b10 := s.genGenesisBlock(validators, 1, map[common.Hash]struct{}{}) - b10.Acks[b10.Hash] = struct{}{} + b10 := s.genGenesisBlock(validators, 1, common.Hashes{}) + b10.Acks = append(b10.Acks, b10.Hash) // Make sure we won't hang when cycle exists. to := newTotalOrdering(1, 3, uint32(len(validators))) @@ -309,7 +297,7 @@ func (s *TotalOrderingTestSuite) TestNotValidDAGDetection() { validators := test.GenerateRandomValidatorIDs(5) to := newTotalOrdering(1, 3, uint32(len(validators))) - b00 := s.genGenesisBlock(validators, 0, map[common.Hash]struct{}{}) + b00 := s.genGenesisBlock(validators, 0, common.Hashes{}) b01 := &types.Block{ ProposerID: validators[0], ParentHash: b00.Hash, @@ -349,31 +337,23 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() { Height: b.Position.Height + 1, ChainID: b.Position.ChainID, }, - Acks: map[common.Hash]struct{}{ - b.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b.Hash}), } } - b00 := s.genGenesisBlock(validators, 0, map[common.Hash]struct{}{}) + b00 := s.genGenesisBlock(validators, 0, common.Hashes{}) b01 := genNextBlock(b00) b02 := genNextBlock(b01) - b10 := s.genGenesisBlock(validators, 1, map[common.Hash]struct{}{ - b00.Hash: struct{}{}, - }) + b10 := s.genGenesisBlock(validators, 1, common.Hashes{b00.Hash}) b11 := genNextBlock(b10) b12 := genNextBlock(b11) - b20 := s.genGenesisBlock(validators, 2, map[common.Hash]struct{}{ - b00.Hash: struct{}{}, - }) + b20 := s.genGenesisBlock(validators, 2, common.Hashes{b00.Hash}) b21 := genNextBlock(b20) b22 := genNextBlock(b21) - b30 := s.genGenesisBlock(validators, 3, map[common.Hash]struct{}{ - b00.Hash: struct{}{}, - }) + b30 := s.genGenesisBlock(validators, 3, common.Hashes{b00.Hash}) b31 := genNextBlock(b30) b32 := genNextBlock(b31) @@ -454,13 +434,11 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { validators := test.GenerateRandomValidatorIDs(5) to := newTotalOrdering(2, 3, uint32(len(validators))) // Setup blocks. - b00 := s.genGenesisBlock(validators, 0, map[common.Hash]struct{}{}) - b10 := s.genGenesisBlock(validators, 1, map[common.Hash]struct{}{}) - b20 := s.genGenesisBlock( - validators, 2, map[common.Hash]struct{}{b10.Hash: struct{}{}}) - b30 := s.genGenesisBlock( - validators, 3, map[common.Hash]struct{}{b20.Hash: struct{}{}}) - b40 := s.genGenesisBlock(validators, 4, map[common.Hash]struct{}{}) + b00 := s.genGenesisBlock(validators, 0, common.Hashes{}) + b10 := s.genGenesisBlock(validators, 1, common.Hashes{}) + b20 := s.genGenesisBlock(validators, 2, common.Hashes{b10.Hash}) + b30 := s.genGenesisBlock(validators, 3, common.Hashes{b20.Hash}) + b40 := s.genGenesisBlock(validators, 4, common.Hashes{}) b11 := &types.Block{ ProposerID: validators[1], ParentHash: b10.Hash, @@ -469,10 +447,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 1, ChainID: 1, }, - Acks: map[common.Hash]struct{}{ - b10.Hash: struct{}{}, - b00.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b10.Hash, b00.Hash}), } b01 := &types.Block{ ProposerID: validators[0], @@ -482,10 +457,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 1, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - b00.Hash: struct{}{}, - b11.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b00.Hash, b11.Hash}), } b21 := &types.Block{ ProposerID: validators[2], @@ -495,10 +467,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 1, ChainID: 2, }, - Acks: map[common.Hash]struct{}{ - b20.Hash: struct{}{}, - b01.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b20.Hash, b01.Hash}), } b31 := &types.Block{ ProposerID: validators[3], @@ -508,10 +477,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 1, ChainID: 3, }, - Acks: map[common.Hash]struct{}{ - b30.Hash: struct{}{}, - b21.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b30.Hash, b21.Hash}), } b02 := &types.Block{ ProposerID: validators[0], @@ -521,10 +487,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 2, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - b01.Hash: struct{}{}, - b21.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b01.Hash, b21.Hash}), } b12 := &types.Block{ ProposerID: validators[1], @@ -534,10 +497,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 2, ChainID: 1, }, - Acks: map[common.Hash]struct{}{ - b11.Hash: struct{}{}, - b21.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b11.Hash, b21.Hash}), } b32 := &types.Block{ ProposerID: validators[3], @@ -547,9 +507,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 2, ChainID: 3, }, - Acks: map[common.Hash]struct{}{ - b31.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b31.Hash}), } b22 := &types.Block{ ProposerID: validators[2], @@ -559,10 +517,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 2, ChainID: 2, }, - Acks: map[common.Hash]struct{}{ - b21.Hash: struct{}{}, - b32.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b21.Hash, b32.Hash}), } b23 := &types.Block{ ProposerID: validators[2], @@ -572,9 +527,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 3, ChainID: 2, }, - Acks: map[common.Hash]struct{}{ - b22.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b22.Hash}), } b03 := &types.Block{ ProposerID: validators[0], @@ -584,10 +537,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 3, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - b02.Hash: struct{}{}, - b22.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b02.Hash, b22.Hash}), } b13 := &types.Block{ ProposerID: validators[1], @@ -597,10 +547,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 3, ChainID: 1, }, - Acks: map[common.Hash]struct{}{ - b12.Hash: struct{}{}, - b22.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b12.Hash, b22.Hash}), } b14 := &types.Block{ ProposerID: validators[1], @@ -610,9 +557,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 4, ChainID: 1, }, - Acks: map[common.Hash]struct{}{ - b13.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b13.Hash}), } b41 := &types.Block{ ProposerID: validators[4], @@ -622,9 +567,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 1, ChainID: 4, }, - Acks: map[common.Hash]struct{}{ - b40.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b40.Hash}), } b42 := &types.Block{ ProposerID: validators[4], @@ -634,9 +577,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { Height: 2, ChainID: 4, }, - Acks: map[common.Hash]struct{}{ - b41.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b41.Hash}), } s.checkNotDeliver(to, b00) @@ -830,12 +771,10 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { to = newTotalOrdering(0, 3, uint32(len(validators))) ) // Setup blocks. - b00 := s.genGenesisBlock(validators, 0, map[common.Hash]struct{}{}) - b10 := s.genGenesisBlock(validators, 1, map[common.Hash]struct{}{}) - b20 := s.genGenesisBlock(validators, 2, map[common.Hash]struct{}{}) - b30 := s.genGenesisBlock(validators, 3, map[common.Hash]struct{}{ - b20.Hash: struct{}{}, - }) + b00 := s.genGenesisBlock(validators, 0, common.Hashes{}) + b10 := s.genGenesisBlock(validators, 1, common.Hashes{}) + b20 := s.genGenesisBlock(validators, 2, common.Hashes{}) + b30 := s.genGenesisBlock(validators, 3, common.Hashes{b20.Hash}) b01 := &types.Block{ ProposerID: validators[0], ParentHash: b00.Hash, @@ -844,10 +783,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { Height: 1, ChainID: 0, }, - Acks: map[common.Hash]struct{}{ - b00.Hash: struct{}{}, - b10.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b00.Hash, b10.Hash}), } b11 := &types.Block{ ProposerID: validators[1], @@ -857,10 +793,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { Height: 1, ChainID: 1, }, - Acks: map[common.Hash]struct{}{ - b10.Hash: struct{}{}, - b20.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b10.Hash, b20.Hash}), } b21 := &types.Block{ ProposerID: validators[2], @@ -870,9 +803,7 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { Height: 1, ChainID: 2, }, - Acks: map[common.Hash]struct{}{ - b20.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b20.Hash}), } b31 := &types.Block{ ProposerID: validators[3], @@ -882,14 +813,9 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { Height: 1, ChainID: 3, }, - Acks: map[common.Hash]struct{}{ - b21.Hash: struct{}{}, - b30.Hash: struct{}{}, - }, + Acks: common.NewSortedHashes(common.Hashes{b21.Hash, b30.Hash}), } - b40 := s.genGenesisBlock(validators, 4, map[common.Hash]struct{}{ - b31.Hash: struct{}{}, - }) + b40 := s.genGenesisBlock(validators, 4, common.Hashes{b31.Hash}) s.checkNotDeliver(to, b00) s.checkNotDeliver(to, b10) diff --git a/core/types/block.go b/core/types/block.go index 06712b1..e00465c 100644 --- a/core/types/block.go +++ b/core/types/block.go @@ -22,6 +22,7 @@ package types import ( "bytes" "fmt" + "sort" "sync" "time" @@ -47,24 +48,20 @@ func RecycleBlock(b *Block) { // NewBlock initiate a block. func NewBlock() (b *Block) { b = blockPool.Get().(*Block) - if b.Acks != nil { - for k := range b.Acks { - delete(b.Acks, k) - } - } + b.Acks = b.Acks[:0] 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"` - Timestamp time.Time `json:"timestamps"` - Acks map[common.Hash]struct{} `json:"acks"` - Payload []byte `json:"payload"` - 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 common.SortedHashes `json:"acks"` + Payload []byte `json:"payload"` + Signature crypto.Signature `json:"signature"` CRSSignature crypto.Signature `json:"crs_signature"` @@ -90,12 +87,8 @@ func (b *Block) Clone() (bcopy *Block) { bcopy.Notary.Timestamp = b.Notary.Timestamp bcopy.Notary.Height = b.Notary.Height bcopy.Timestamp = b.Timestamp - if bcopy.Acks == nil { - bcopy.Acks = make(map[common.Hash]struct{}, len(b.Acks)) - } - for k, v := range b.Acks { - bcopy.Acks[k] = v - } + bcopy.Acks = make(common.SortedHashes, len(b.Acks)) + copy(bcopy.Acks, b.Acks) bcopy.Payload = make([]byte, len(b.Payload)) copy(bcopy.Payload, b.Payload) return @@ -106,6 +99,14 @@ func (b *Block) IsGenesis() bool { return b.Position.Height == 0 && b.ParentHash == common.Hash{} } +// IsAcking checks if a block acking another by it's hash. +func (b *Block) IsAcking(hash common.Hash) bool { + idx := sort.Search(len(b.Acks), func(i int) bool { + return bytes.Compare(b.Acks[i][:], hash[:]) >= 0 + }) + return !(idx == len(b.Acks) || b.Acks[idx] != hash) +} + // ByHash is the helper type for sorting slice of blocks by hash. type ByHash []*Block diff --git a/core/types/block_test.go b/core/types/block_test.go index 4763ad1..2e6807d 100644 --- a/core/types/block_test.go +++ b/core/types/block_test.go @@ -86,6 +86,20 @@ func (s *BlockTestSuite) TestGenesisBlock() { s.False(b2.IsGenesis()) } +func (s *BlockTestSuite) TestIsAcking() { + // This test case would check if types.Block.IsAcking works + ack0 := common.NewRandomHash() + acks0 := common.Hashes{ + ack0, + common.NewRandomHash(), + common.NewRandomHash(), + } + b0 := &Block{Acks: common.NewSortedHashes(acks0)} + s.True(b0.IsAcking(ack0)) + s.False(b0.IsAcking(common.Hash{})) + s.False(b0.IsAcking(common.NewRandomHash())) +} + func TestBlock(t *testing.T) { suite.Run(t, new(BlockTestSuite)) } -- cgit v1.2.3