Add acking module (#13)

* Refactor and add acking module

Extract acking module for unit testing. This commit splits functions
into small pieces for better understanding and easy unit testing.

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))
+}