aboutsummaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/acking.go308
-rw-r--r--core/acking_test.go426
-rw-r--r--core/blocklattice.go24
-rw-r--r--core/blocklattice_test.go12
-rw-r--r--core/types/block.go13
5 files changed, 759 insertions, 24 deletions
diff --git a/core/acking.go b/core/acking.go
new file mode 100644
index 0000000..b244831
--- /dev/null
+++ b/core/acking.go
@@ -0,0 +1,308 @@
+// 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 (
+ "fmt"
+
+ "github.com/dexon-foundation/dexon-consensus-core/common"
+ "github.com/dexon-foundation/dexon-consensus-core/core/types"
+)
+
+// Acking is for acking module.
+type Acking struct {
+ // lattice stores blocks by its validator ID and height.
+ lattice map[types.ValidatorID]*ackingValidatorStatus
+
+ // blocks stores the hash to block map.
+ blocks map[common.Hash]*types.Block
+
+ // receivedBlocks stores blocks which is received but its acks are not all
+ // in lattice.
+ receivedBlocks map[common.Hash]*types.Block
+
+ // ackedBlocks stores blocks in status types.BlockStatusAcked, which are
+ // strongly acked but not yet being output to total ordering module.
+ ackedBlocks map[common.Hash]*types.Block
+}
+
+type ackingValidatorStatus struct {
+ // blocks stores blocks proposed by specified validator in map which key is
+ // the height of the block.
+ blocks map[uint64]*types.Block
+
+ // nextAck stores the height of next height that should be acked, i.e. last
+ // acked height + 1. Initialized to 0, when genesis blocks are still not
+ // being acked. For example, a.lattice[vid1].NextAck[vid2] - 1 is the last
+ // acked height by vid1 acking vid2.
+ nextAck map[types.ValidatorID]uint64
+
+ // nextOutput is the next output height of block, default to 0.
+ nextOutput uint64
+
+ // restricted is the flag of a validator is in restricted mode or not.
+ restricted bool
+}
+
+// Errors for sanity check error.
+var (
+ ErrInvalidProposerID = fmt.Errorf("invalid_proposer_id")
+ ErrForkBlock = fmt.Errorf("fork_block")
+ ErrNotAckParent = fmt.Errorf("not_ack_parent")
+ ErrDoubleAck = fmt.Errorf("double_ack")
+ ErrInvalidBlockHeight = fmt.Errorf("invalid_block_height")
+)
+
+// NewAcking creates a new Acking struct.
+func NewAcking() *Acking {
+ return &Acking{
+ lattice: make(map[types.ValidatorID]*ackingValidatorStatus),
+ blocks: make(map[common.Hash]*types.Block),
+ receivedBlocks: make(map[common.Hash]*types.Block),
+ ackedBlocks: make(map[common.Hash]*types.Block),
+ }
+}
+
+func (a *Acking) sanityCheck(b *types.Block) error {
+ // Check if its proposer is in validator set.
+ if _, exist := a.lattice[b.ProposerID]; !exist {
+ return ErrInvalidProposerID
+ }
+
+ // Check if it forks.
+ if bInLattice, exist := a.lattice[b.ProposerID].blocks[b.Height]; exist {
+ if b.Hash != bInLattice.Hash {
+ return ErrForkBlock
+ }
+ }
+
+ // Check non-genesis blocks if it acks its parent.
+ if b.Height > 0 {
+ if _, exist := b.Acks[b.ParentHash]; !exist {
+ return ErrNotAckParent
+ }
+ bParent := a.blocks[b.ParentHash]
+ if bParent.Height != b.Height-1 {
+ return ErrInvalidBlockHeight
+ }
+ }
+
+ // Check if it acks older blocks.
+ for hash := range b.Acks {
+ if bAck, exist := a.blocks[hash]; exist {
+ if bAck.Height < a.lattice[b.ProposerID].nextAck[bAck.ProposerID] {
+ return ErrDoubleAck
+ }
+ }
+ }
+
+ // TODO(haoping): application layer check of block's content
+
+ return nil
+}
+
+// areAllAcksReceived checks if all ack blocks of a block are all in lattice.
+func (a *Acking) areAllAcksInLattice(b *types.Block) bool {
+ for h := range b.Acks {
+ bAck, exist := a.blocks[h]
+ if !exist {
+ return false
+ }
+ if bAckInLattice, exist := a.lattice[bAck.ProposerID].blocks[bAck.Height]; !exist {
+ if bAckInLattice.Hash != bAck.Hash {
+ panic("areAllAcksInLattice: Acking.lattice has corrupted")
+ }
+ return false
+ }
+ }
+ return true
+}
+
+// ProcessBlock processes block, it does sanity check, inserts block into
+// lattice, handles strong acking and deletes blocks which will not be used.
+func (a *Acking) ProcessBlock(block *types.Block) {
+ // If a block does not pass sanity check, discard this block.
+ if err := a.sanityCheck(block); err != nil {
+ return
+ }
+ a.blocks[block.Hash] = block
+ block.AckedValidators = make(map[types.ValidatorID]struct{})
+ a.receivedBlocks[block.Hash] = block
+
+ // Check blocks in receivedBlocks if its acks are all in lattice. If a block's
+ // acking blocks are all in lattice, execute sanity check and add the block
+ // into lattice.
+ blocksToAcked := map[common.Hash]*types.Block{}
+ for {
+ blocksToLattice := map[common.Hash]*types.Block{}
+ for _, b := range a.receivedBlocks {
+ if a.areAllAcksInLattice(b) {
+ blocksToLattice[b.Hash] = b
+ }
+ }
+ if len(blocksToLattice) == 0 {
+ break
+ }
+ for _, b := range blocksToLattice {
+ // Sanity check must been executed again here for the case that several
+ // valid blocks with different content being added into blocksToLattice
+ // in the same time. For example
+ // B C Block B and C both ack A and are valid. B, C received first
+ // \ / (added in receivedBlocks), and A comes, if sanity check is
+ // A not being executed here, B and C will both be added in lattice
+ if err := a.sanityCheck(b); err != nil {
+ delete(a.blocks, b.Hash)
+ delete(a.receivedBlocks, b.Hash)
+ continue
+ }
+ a.lattice[b.ProposerID].blocks[b.Height] = b
+ delete(a.receivedBlocks, b.Hash)
+ for h := range b.Acks {
+ bAck := a.blocks[h]
+ // Update nextAck only when bAck.Height + 1 is greater. A block might
+ // ack blocks proposed by same validator with different height.
+ if a.lattice[b.ProposerID].nextAck[bAck.ProposerID] < bAck.Height+1 {
+ a.lattice[b.ProposerID].nextAck[bAck.ProposerID] = bAck.Height + 1
+ }
+ // Update AckedValidators for each ack blocks and its parents.
+ for {
+ if _, exist := bAck.AckedValidators[b.ProposerID]; exist {
+ break
+ }
+ if bAck.Status > types.BlockStatusInit {
+ break
+ }
+ bAck.AckedValidators[b.ProposerID] = struct{}{}
+ // A block is strongly acked if it is acked by more than
+ // 2 * (maximum number of byzatine validators) unique validators.
+ if len(bAck.AckedValidators) > 2*((len(a.lattice)-1)/3) {
+ blocksToAcked[bAck.Hash] = bAck
+ }
+ if bAck.Height == 0 {
+ break
+ }
+ bAck = a.blocks[bAck.ParentHash]
+ }
+ }
+ }
+ }
+
+ for _, b := range blocksToAcked {
+ a.ackedBlocks[b.Hash] = b
+ b.Status = types.BlockStatusAcked
+ }
+
+ // TODO(haoping): delete blocks in received array when it is received a long
+ // time ago
+
+ // Delete old blocks in "lattice" and "blocks" for release memory space.
+ // First, find the height that blocks below it can be deleted. This height
+ // is defined by finding minimum of validator's nextOutput and last acking
+ // heights from other validators, i.e. a.lattice[v_other].nextAck[this_vid].
+ // This works because blocks of height below this minimum are not going to be
+ // acked anymore, the ackings of these blocks are illegal.
+ for vid := range a.lattice {
+ // Find the minimum height that heights lesser can be deleted.
+ min := a.lattice[vid].nextOutput
+ for vid2 := range a.lattice {
+ if a.lattice[vid2].nextAck[vid] < min {
+ min = a.lattice[vid2].nextAck[vid]
+ }
+ }
+ // "min" is the height of "next" last acked, min - 1 is the last height.
+ // Delete blocks from min - 2 which will never be acked.
+ if min < 3 {
+ continue
+ }
+ min -= 2
+ for {
+ b, exist := a.lattice[vid].blocks[min]
+ if !exist {
+ break
+ }
+ if b.Status >= types.BlockStatusOrdering {
+ delete(a.lattice[vid].blocks, b.Height)
+ delete(a.blocks, b.Hash)
+ }
+ if min == 0 {
+ break
+ }
+ min--
+ }
+ }
+}
+
+// ExtractBlocks returns all blocks that can be inserted into total ordering's
+// DAG. This function changes the status of blocks from types.BlockStatusAcked
+// to types.BlockStatusOrdering.
+func (a *Acking) ExtractBlocks() []*types.Block {
+ ret := []*types.Block{}
+ for {
+ updated := false
+ for vid := range a.lattice {
+ b, exist := a.lattice[vid].blocks[a.lattice[vid].nextOutput]
+ if !exist || b.Status < types.BlockStatusAcked {
+ continue
+ }
+ allAcksInOrderingStatus := true
+ // 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 {
+ bAck, exist := a.blocks[ackHash]
+ if !exist {
+ continue
+ }
+ if bAck.Status < types.BlockStatusOrdering {
+ allAcksInOrderingStatus = false
+ break
+ }
+ }
+ if !allAcksInOrderingStatus {
+ continue
+ }
+ updated = true
+ b.Status = types.BlockStatusOrdering
+ delete(a.ackedBlocks, b.Hash)
+ ret = append(ret, b)
+ a.lattice[vid].nextOutput++
+ }
+ if !updated {
+ break
+ }
+ }
+ return ret
+}
+
+// AddValidator adds validator in the validator set.
+func (a *Acking) AddValidator(h types.ValidatorID) {
+ a.lattice[h] = &ackingValidatorStatus{
+ blocks: make(map[uint64]*types.Block),
+ nextAck: make(map[types.ValidatorID]uint64),
+ nextOutput: 0,
+ restricted: false,
+ }
+}
+
+// DeleteValidator deletes validator in validator set.
+func (a *Acking) DeleteValidator(h types.ValidatorID) {
+ for h := range a.lattice {
+ delete(a.lattice[h].nextAck, h)
+ }
+ delete(a.lattice, h)
+}
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))
+}
diff --git a/core/blocklattice.go b/core/blocklattice.go
index 9b43b67..e4a76cc 100644
--- a/core/blocklattice.go
+++ b/core/blocklattice.go
@@ -41,7 +41,7 @@ const (
// BlockLattice represents the local view of a single validator.
//
// blockDB stores blocks that are final. blocks stores blocks that are in ToTo
-// State.
+// Status.
type BlockLattice struct {
owner types.ValidatorID
ValidatorSet map[types.ValidatorID]struct{}
@@ -98,7 +98,7 @@ func (l *BlockLattice) AddValidator(
l.phi = 2*l.fmax + 1
// TODO: We should not make genesis blocks 'final' directly.
- genesis.State = types.BlockStatusFinal
+ genesis.Status = types.BlockStatusFinal
l.blockDB.Put(*genesis)
}
@@ -144,7 +144,7 @@ func (l *BlockLattice) processAcks(b *types.Block) {
ackedBlock.Ackeds[b.Hash] = struct{}{}
bp := ackedBlock
- for bp != nil && bp.State < types.BlockStatusAcked {
+ for bp != nil && bp.Status < types.BlockStatusAcked {
if bp.Ackeds == nil {
bp.Ackeds = make(map[common.Hash]struct{})
}
@@ -160,7 +160,7 @@ func (l *BlockLattice) processAcks(b *types.Block) {
}
if len(ackedByNodes) > 2*l.fmax {
- bp.State = types.BlockStatusAcked
+ bp.Status = types.BlockStatusAcked
l.stronglyAckedSet[bp.Hash] = bp
}
bp = l.getBlock(bp.ParentHash)
@@ -170,7 +170,7 @@ func (l *BlockLattice) processAcks(b *types.Block) {
populateAckBy = func(bx, target *types.Block) {
for ab := range bx.Acks {
abb := l.getBlock(ab)
- if abb.State < types.BlockStatusFinal {
+ if abb.Status < types.BlockStatusFinal {
if abb.Ackeds == nil {
abb.Ackeds = make(map[common.Hash]struct{})
}
@@ -220,7 +220,7 @@ func (l *BlockLattice) isValidAckCandidate(b *types.Block) bool {
if bx == nil {
return false
}
- if bx.State == types.BlockStatusFinal {
+ if bx.Status == types.BlockStatusFinal {
return true
}
}
@@ -281,11 +281,11 @@ IterateStronglyAckedSet:
for bpHash, bp := range l.stronglyAckedSet {
for ackBlockHash := range bp.Acks {
bx := l.getBlock(ackBlockHash)
- if bx == nil || bx.State < types.BlockStatusAcked {
+ if bx == nil || bx.Status < types.BlockStatusAcked {
break IterateStronglyAckedSet
}
}
- bp.State = types.BlockStatusToTo
+ bp.Status = types.BlockStatusOrdering
l.pendingSet[bp.Hash] = bp
delete(l.stronglyAckedSet, bpHash)
@@ -340,7 +340,7 @@ func (l *BlockLattice) calculateABSofBlock(b *types.Block) {
calculateABSRecursive = func(target *types.Block) {
for hash := range target.Ackeds {
ackedByBlock := l.getBlock(hash)
- if ackedByBlock.State != types.BlockStatusToTo {
+ if ackedByBlock.Status != types.BlockStatusOrdering {
continue
}
v, exists := l.ABS[b.Hash][ackedByBlock.ProposerID]
@@ -398,7 +398,7 @@ func (l *BlockLattice) totalOrdering(b *types.Block) {
acksOnlyFinal := true
for ackedBlockHash := range b.Acks {
bp := l.getBlock(ackedBlockHash)
- if bp.State != types.BlockStatusFinal {
+ if bp.Status != types.BlockStatusFinal {
acksOnlyFinal = false
break
}
@@ -515,7 +515,7 @@ func (l *BlockLattice) totalOrdering(b *types.Block) {
var output []*types.Block
for hash, x := range precedingSet {
output = append(output, x)
- x.State = types.BlockStatusFinal
+ x.Status = types.BlockStatusFinal
// Remove from pending set and candidate set.
delete(l.pendingSet, hash)
@@ -543,7 +543,7 @@ func (l *BlockLattice) totalOrdering(b *types.Block) {
acksOnlyFinal := true
for ackedBlockHash := range block.Acks {
bp := l.getBlock(ackedBlockHash)
- if bp.State != types.BlockStatusFinal {
+ if bp.Status != types.BlockStatusFinal {
acksOnlyFinal = false
break
}
diff --git a/core/blocklattice_test.go b/core/blocklattice_test.go
index be332db..3dd5a3b 100644
--- a/core/blocklattice_test.go
+++ b/core/blocklattice_test.go
@@ -244,7 +244,7 @@ func (s *BlockLatticeTest) SetupTest() {
Debugf("\n")
}
-func (s *BlockLatticeTest) TestAckAndStateTransition() {
+func (s *BlockLatticeTest) TestAckAndStatusTransition() {
// Recieve Order:
// B01 -> B12 -> B11 -> B21 -> B31 -> B02 -> B32 -> B22 -> B13 -> B33
// -> B03 -> B23
@@ -311,7 +311,7 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() {
s.Require().Equal(1, len(lattice.pendingSet))
s.Require().NotNil(lattice.pendingSet[b01.Hash])
- s.Require().Equal(types.BlockStatusToTo, b01.State)
+ s.Require().Equal(types.BlockStatusOrdering, b01.Status)
// b01 is acked.
s.Require().Equal(4, len(b01.Ackeds))
@@ -390,10 +390,10 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() {
s.Require().NotNil(lattice.pendingSet[b11.Hash])
s.Require().NotNil(lattice.pendingSet[b21.Hash])
s.Require().NotNil(lattice.pendingSet[b31.Hash])
- s.Require().Equal(types.BlockStatusToTo, b01.State)
- s.Require().Equal(types.BlockStatusToTo, b11.State)
- s.Require().Equal(types.BlockStatusToTo, b21.State)
- s.Require().Equal(types.BlockStatusToTo, b31.State)
+ s.Require().Equal(types.BlockStatusOrdering, b01.Status)
+ s.Require().Equal(types.BlockStatusOrdering, b11.Status)
+ s.Require().Equal(types.BlockStatusOrdering, b21.Status)
+ s.Require().Equal(types.BlockStatusOrdering, b31.Status)
// b02 is acked.
s.Require().Equal(2, len(b02.Ackeds))
diff --git a/core/types/block.go b/core/types/block.go
index 6762f14..217ea73 100644
--- a/core/types/block.go
+++ b/core/types/block.go
@@ -25,14 +25,14 @@ import (
"github.com/dexon-foundation/dexon-consensus-core/common"
)
-// State represents the block process state.
-type State int
+// Status represents the block process state.
+type Status int
// Block Status.
const (
- BlockStatusInit State = iota
+ BlockStatusInit Status = iota
BlockStatusAcked
- BlockStatusToTo
+ BlockStatusOrdering
BlockStatusFinal
)
@@ -45,8 +45,9 @@ type Block struct {
Timestamps map[ValidatorID]time.Time `json:"timestamps"`
Acks map[common.Hash]struct{} `json:"acks"`
- Ackeds map[common.Hash]struct{} `json:"-"`
- State State `json:"-"`
+ Ackeds map[common.Hash]struct{} `json:"-"`
+ AckedValidators map[ValidatorID]struct{} `json:"-"`
+ Status Status `json:"-"`
}
func (b *Block) String() string {
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-07 23:48:15 +0800