diff options
Diffstat (limited to 'core/acking_test.go')
-rw-r--r-- | core/acking_test.go | 426 |
1 files changed, 426 insertions, 0 deletions
diff --git a/core/acking_test.go b/core/acking_test.go new file mode 100644 index 0000000..5c89d24 --- /dev/null +++ b/core/acking_test.go @@ -0,0 +1,426 @@ +// 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/rand" + "testing" + + "github.com/stretchr/testify/suite" + + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/dexon-foundation/dexon-consensus-core/core/types" +) + +type AckingTest struct { + suite.Suite +} + +func (s *AckingTest) SetupSuite() { + +} + +func (s *AckingTest) SetupTest() { + +} + +// genTestCase1 generates test case 1, +// 3 +// | +// 2 +// | \ +// 1 | 1 +// | | | +// 0 0 0 0 (block height) +// 0 1 2 3 (validator) +func genTestCase1(s *AckingTest, a *Acking) []types.ValidatorID { + // Create new Acking instance with 4 validators + var b *types.Block + var h common.Hash + vids := []types.ValidatorID{} + for i := 0; i < 4; i++ { + vid := types.ValidatorID{Hash: common.NewRandomHash()} + a.AddValidator(vid) + vids = append(vids, vid) + } + // Add genesis blocks. + for i := 0; i < 4; i++ { + h = common.NewRandomHash() + b = &types.Block{ + ProposerID: vids[i], + ParentHash: h, + Hash: h, + Height: 0, + Acks: map[common.Hash]struct{}{}, + } + a.ProcessBlock(b) + } + + // Add block 0-1 which acks 0-0. + h = a.lattice[vids[0]].blocks[0].Hash + b = &types.Block{ + ProposerID: vids[0], + ParentHash: h, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + }, + } + a.ProcessBlock(b) + s.NotNil(a.lattice[vids[0]].blocks[1]) + + // Add block 0-2 which acks 0-1 and 1-0. + h = a.lattice[vids[0]].blocks[1].Hash + b = &types.Block{ + ProposerID: vids[0], + ParentHash: h, + Hash: common.NewRandomHash(), + Height: 2, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + a.lattice[vids[1]].blocks[0].Hash: struct{}{}, + }, + } + a.ProcessBlock(b) + s.NotNil(a.lattice[vids[0]].blocks[2]) + + // Add block 0-3 which acks 0-2. + h = a.lattice[vids[0]].blocks[2].Hash + b = &types.Block{ + ProposerID: vids[0], + ParentHash: h, + Hash: common.NewRandomHash(), + Height: 3, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + }, + } + a.ProcessBlock(b) + s.NotNil(a.lattice[vids[0]].blocks[3]) + + // Add block 3-1 which acks 3-0. + h = a.lattice[vids[3]].blocks[0].Hash + b = &types.Block{ + ProposerID: vids[3], + ParentHash: h, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + }, + } + a.ProcessBlock(b) + s.NotNil(a.lattice[vids[3]].blocks[0]) + + return vids +} + +func (s *AckingTest) TestAddValidator() { + a := NewAcking() + s.Equal(len(a.lattice), 0) + genTestCase1(s, a) + s.Equal(len(a.lattice), 4) +} + +func (s *AckingTest) TestSanityCheck() { + var b *types.Block + var h common.Hash + var vids []types.ValidatorID + var err error + a := NewAcking() + vids = genTestCase1(s, a) + + // Non-genesis block with no ack, should get error. + b = &types.Block{ + ProposerID: vids[0], + ParentHash: common.NewRandomHash(), + Height: 10, + Acks: make(map[common.Hash]struct{}), + } + err = a.sanityCheck(b) + s.NotNil(err) + s.Equal(ErrNotAckParent.Error(), err.Error()) + + // Non-genesis block which does not ack its parent. + b = &types.Block{ + ProposerID: vids[1], + ParentHash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + a.lattice[vids[2]].blocks[0].Hash: struct{}{}, + }, + } + err = a.sanityCheck(b) + s.NotNil(err) + s.Equal(ErrNotAckParent.Error(), err.Error()) + + // Non-genesis block which acks its parent but the height is invalid. + h = a.lattice[vids[1]].blocks[0].Hash + b = &types.Block{ + ProposerID: vids[1], + ParentHash: h, + Height: 2, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + }, + } + err = a.sanityCheck(b) + s.NotNil(err) + s.Equal(ErrInvalidBlockHeight.Error(), err.Error()) + + // Invalid proposer ID. + h = a.lattice[vids[1]].blocks[0].Hash + b = &types.Block{ + ProposerID: types.ValidatorID{Hash: common.NewRandomHash()}, + ParentHash: h, + Height: 1, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + }, + } + err = a.sanityCheck(b) + s.NotNil(err) + s.Equal(ErrInvalidProposerID.Error(), err.Error()) + + // Fork block. + h = a.lattice[vids[0]].blocks[0].Hash + b = &types.Block{ + ProposerID: vids[0], + ParentHash: h, + Height: 1, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + }, + } + err = a.sanityCheck(b) + s.NotNil(err) + s.Equal(ErrForkBlock.Error(), err.Error()) + + // Replicated ack. + h = a.lattice[vids[0]].blocks[3].Hash + b = &types.Block{ + ProposerID: vids[0], + ParentHash: h, + Height: 4, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + a.lattice[vids[1]].blocks[0].Hash: struct{}{}, + }, + } + err = a.sanityCheck(b) + s.NotNil(err) + s.Equal(ErrDoubleAck.Error(), err.Error()) + + // Normal block. + h = a.lattice[vids[1]].blocks[0].Hash + b = &types.Block{ + ProposerID: vids[1], + ParentHash: h, + Height: 1, + Acks: map[common.Hash]struct{}{ + h: struct{}{}, + common.NewRandomHash(): struct{}{}, + }, + } + err = a.sanityCheck(b) + s.Nil(err) +} + +func (s *AckingTest) TestAreAllAcksInLattice() { + var b *types.Block + var vids []types.ValidatorID + a := NewAcking() + vids = genTestCase1(s, a) + + // Empty ack should get true, although won't pass sanity check. + b = &types.Block{ + Acks: map[common.Hash]struct{}{}, + } + s.True(a.areAllAcksInLattice(b)) + + // Acks blocks in lattice + b = &types.Block{ + Acks: map[common.Hash]struct{}{ + a.lattice[vids[0]].blocks[0].Hash: struct{}{}, + a.lattice[vids[0]].blocks[1].Hash: struct{}{}, + }, + } + s.True(a.areAllAcksInLattice(b)) + + // Acks random block hash. + b = &types.Block{ + Acks: map[common.Hash]struct{}{ + common.NewRandomHash(): struct{}{}, + }, + } + s.False(a.areAllAcksInLattice(b)) +} + +func (s *AckingTest) TestStrongAck() { + var b *types.Block + var vids []types.ValidatorID + a := NewAcking() + vids = genTestCase1(s, a) + + // Check block 0-0 to 0-3 before adding 1-1 and 2-1. + for i := uint64(0); i < 4; i++ { + s.Equal(types.BlockStatusInit, a.lattice[vids[0]].blocks[i].Status) + } + + // Add block 1-1 which acks 1-0 and 0-2, and block 0-0 to 0-3 are still + // in BlockStatusInit, because they are not strongly acked. + b = &types.Block{ + ProposerID: vids[1], + ParentHash: a.lattice[vids[1]].blocks[0].Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + a.lattice[vids[0]].blocks[2].Hash: struct{}{}, + a.lattice[vids[1]].blocks[0].Hash: struct{}{}, + }, + } + a.ProcessBlock(b) + s.NotNil(a.lattice[vids[1]].blocks[1]) + for i := uint64(0); i < 4; i++ { + s.Equal(types.BlockStatusInit, a.lattice[vids[0]].blocks[i].Status) + } + + // Add block 2-1 which acks 0-2 and 2-0, block 0-0 to 0-2 are strongly acked but + // 0-3 is still not. + b = &types.Block{ + ProposerID: vids[2], + ParentHash: a.lattice[vids[2]].blocks[0].Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + a.lattice[vids[0]].blocks[2].Hash: struct{}{}, + a.lattice[vids[2]].blocks[0].Hash: struct{}{}, + }, + } + a.ProcessBlock(b) + s.Equal(types.BlockStatusAcked, a.lattice[vids[0]].blocks[0].Status) + s.Equal(types.BlockStatusAcked, a.lattice[vids[0]].blocks[1].Status) + s.Equal(types.BlockStatusAcked, a.lattice[vids[0]].blocks[2].Status) + s.Equal(types.BlockStatusInit, a.lattice[vids[0]].blocks[3].Status) +} + +func (s *AckingTest) TestExtractBlocks() { + var b *types.Block + a := NewAcking() + vids := genTestCase1(s, a) + + // Add block 1-1 which acks 1-0, 0-2, 3-0. + b = &types.Block{ + ProposerID: vids[1], + ParentHash: a.lattice[vids[1]].blocks[0].Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + a.lattice[vids[0]].blocks[2].Hash: struct{}{}, + a.lattice[vids[1]].blocks[0].Hash: struct{}{}, + a.lattice[vids[3]].blocks[0].Hash: struct{}{}, + }, + } + a.ProcessBlock(b) + + // Add block 2-1 which acks 0-2, 2-0, 3-0. + b = &types.Block{ + ProposerID: vids[2], + ParentHash: a.lattice[vids[2]].blocks[0].Hash, + Hash: common.NewRandomHash(), + Height: 1, + Acks: map[common.Hash]struct{}{ + a.lattice[vids[0]].blocks[2].Hash: struct{}{}, + a.lattice[vids[2]].blocks[0].Hash: struct{}{}, + a.lattice[vids[3]].blocks[0].Hash: struct{}{}, + }, + } + a.ProcessBlock(b) + + hashs := []common.Hash{ + a.lattice[vids[0]].blocks[0].Hash, + a.lattice[vids[0]].blocks[1].Hash, + a.lattice[vids[3]].blocks[0].Hash, + } + hashExtracted := map[common.Hash]*types.Block{} + for _, b := range a.ExtractBlocks() { + hashExtracted[b.Hash] = b + s.Equal(types.BlockStatusOrdering, b.Status) + } + for _, h := range hashs { + _, exist := hashExtracted[h] + s.True(exist) + } +} + +func (s *AckingTest) TestRandomIntensiveAcking() { + a := NewAcking() + vids := []types.ValidatorID{} + heights := map[types.ValidatorID]uint64{} + extractedBlocks := []*types.Block{} + + // Generate validators and genesis blocks. + for i := 0; i < 4; i++ { + vid := types.ValidatorID{Hash: common.NewRandomHash()} + a.AddValidator(vid) + vids = append(vids, vid) + h := common.NewRandomHash() + b := &types.Block{ + Hash: h, + ParentHash: h, + Acks: map[common.Hash]struct{}{}, + Height: 0, + ProposerID: vid, + } + a.ProcessBlock(b) + heights[vid] = 1 + } + + for i := 0; i < 5000; i++ { + vid := vids[rand.Int()%len(vids)] + height := heights[vid] + heights[vid]++ + parentHash := a.lattice[vid].blocks[height-1].Hash + acks := map[common.Hash]struct{}{} + for _, vid2 := range vids { + if b, exist := a.lattice[vid2].blocks[a.lattice[vid].nextAck[vid2]]; exist { + acks[b.Hash] = struct{}{} + } + } + b := &types.Block{ + ProposerID: vid, + Hash: common.NewRandomHash(), + ParentHash: parentHash, + Height: height, + Acks: acks, + } + a.ProcessBlock(b) + extractedBlocks = append(extractedBlocks, a.ExtractBlocks()...) + } + + extractedBlocks = append(extractedBlocks, a.ExtractBlocks()...) + // The len of array extractedBlocks should be about 5000. + s.True(len(extractedBlocks) > 4500) + // The len of a.blocks should be small if deleting mechanism works. + s.True(len(a.blocks) < 500) +} + +func TestAcking(t *testing.T) { + suite.Run(t, new(AckingTest)) +} |