aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorHaoping Ku <haoping.ku@dexon.org>2018-08-17 17:57:15 +0800
committerGitHub <noreply@github.com>2018-08-17 17:57:15 +0800
commitfd8358a607ccd564a5e8158451a5d9ef9cb7b55b (patch)
treeda476d0227f9e979bc2b4bedd35407d72560d0dc
parenta146ce5ee9eea1a37d86059dcc13cdf147c9e38e (diff)
downloaddexon-consensus-fd8358a607ccd564a5e8158451a5d9ef9cb7b55b.tar
dexon-consensus-fd8358a607ccd564a5e8158451a5d9ef9cb7b55b.tar.gz
dexon-consensus-fd8358a607ccd564a5e8158451a5d9ef9cb7b55b.tar.bz2
dexon-consensus-fd8358a607ccd564a5e8158451a5d9ef9cb7b55b.tar.lz
dexon-consensus-fd8358a607ccd564a5e8158451a5d9ef9cb7b55b.tar.xz
dexon-consensus-fd8358a607ccd564a5e8158451a5d9ef9cb7b55b.tar.zst
dexon-consensus-fd8358a607ccd564a5e8158451a5d9ef9cb7b55b.zip
core: implicit fields in types.Block used in reliable broadcast (#59)
-rw-r--r--blockdb/level-db_test.go3
-rw-r--r--core/reliable-broadcast.go104
-rw-r--r--core/reliable-broadcast_test.go21
-rw-r--r--core/types/block.go24
4 files changed, 83 insertions, 69 deletions
diff --git a/blockdb/level-db_test.go b/blockdb/level-db_test.go
index 863adba..f6c14c5 100644
--- a/blockdb/level-db_test.go
+++ b/blockdb/level-db_test.go
@@ -56,7 +56,6 @@ func (s *LevelDBTestSuite) TestBasicUsage() {
ProposerID: validator1,
Hash: hash1,
Height: 1,
- Status: types.BlockStatusInit,
}
err = db.Update(block1)
s.Equal(ErrBlockDoesNotExist, err)
@@ -69,7 +68,6 @@ func (s *LevelDBTestSuite) TestBasicUsage() {
queried, err := db.Get(block1.Hash)
s.Nil(err)
s.Equal(queried.ProposerID, block1.ProposerID)
- s.Equal(queried.Status, block1.Status)
// Test Update.
now := time.Now().UTC()
@@ -105,7 +103,6 @@ func (s *LevelDBTestSuite) TestSyncIndex() {
ProposerID: types.ValidatorID{Hash: common.NewRandomHash()},
Hash: common.NewRandomHash(),
Height: uint64(i),
- Status: types.BlockStatusInit,
}
db.Put(block)
blocks[i] = block
diff --git a/core/reliable-broadcast.go b/core/reliable-broadcast.go
index 932846b..d9a469a 100644
--- a/core/reliable-broadcast.go
+++ b/core/reliable-broadcast.go
@@ -25,20 +25,31 @@ import (
"github.com/dexon-foundation/dexon-consensus-core/core/types"
)
+// Status represents the block process state.
+type blockStatus int
+
+// Block Status.
+const (
+ blockStatusInit blockStatus = iota
+ blockStatusAcked
+ blockStatusOrdering
+ blockStatusFinal
+)
+
// reliableBroadcast is a module for reliable broadcast.
type reliableBroadcast struct {
- // lattice stores blocks by its validator ID and height.
- lattice map[types.ValidatorID]*reliableBroadcastValidatorStatus
+ // lattice stores validator's blocks and other info.
+ lattice map[types.ValidatorID]*rbcValidatorStatus
- // blocks stores the hash to block map.
- blocks map[common.Hash]*types.Block
+ // blockInfos stores block infos.
+ blockInfos map[common.Hash]*rbcBlockInfo
// receivedBlocks stores blocks which is received but its acks are not all
// in lattice.
receivedBlocks map[common.Hash]*types.Block
}
-type reliableBroadcastValidatorStatus struct {
+type rbcValidatorStatus struct {
// blocks stores blocks proposed by specified validator in map which key is
// the height of the block.
blocks map[uint64]*types.Block
@@ -53,6 +64,13 @@ type reliableBroadcastValidatorStatus struct {
nextOutput uint64
}
+type rbcBlockInfo struct {
+ block *types.Block
+ receivedTime time.Time
+ status blockStatus
+ ackedValidators map[types.ValidatorID]struct{}
+}
+
// Errors for sanity check error.
var (
ErrInvalidProposerID = fmt.Errorf("invalid proposer id")
@@ -67,8 +85,8 @@ var (
// newReliableBroadcast creates a new reliableBroadcast struct.
func newReliableBroadcast() *reliableBroadcast {
return &reliableBroadcast{
- lattice: make(map[types.ValidatorID]*reliableBroadcastValidatorStatus),
- blocks: make(map[common.Hash]*types.Block),
+ lattice: make(map[types.ValidatorID]*rbcValidatorStatus),
+ blockInfos: make(map[common.Hash]*rbcBlockInfo),
receivedBlocks: make(map[common.Hash]*types.Block),
}
}
@@ -92,15 +110,16 @@ func (rb *reliableBroadcast) sanityCheck(b *types.Block) error {
if _, exist := b.Acks[b.ParentHash]; !exist {
return ErrNotAckParent
}
- bParent, exists := rb.blocks[b.ParentHash]
- if exists && bParent.Height != b.Height-1 {
+ bParentStat, exists := rb.blockInfos[b.ParentHash]
+ if exists && bParentStat.block.Height != b.Height-1 {
return ErrInvalidBlockHeight
}
}
// Check if it acks older blocks.
for hash := range b.Acks {
- if bAck, exist := rb.blocks[hash]; exist {
+ if bAckStat, exist := rb.blockInfos[hash]; exist {
+ bAck := bAckStat.block
if bAck.Height < rb.lattice[b.ProposerID].nextAck[bAck.ProposerID] {
return ErrDoubleAck
}
@@ -129,10 +148,11 @@ 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 {
- bAck, exist := rb.blocks[h]
+ bAckStat, exist := rb.blockInfos[h]
if !exist {
return false
}
+ bAck := bAckStat.block
bAckInLattice, exist := rb.lattice[bAck.ProposerID].blocks[bAck.Height]
if !exist {
@@ -152,12 +172,12 @@ func (rb *reliableBroadcast) processBlock(block *types.Block) (err error) {
if err = rb.sanityCheck(block); err != nil {
return
}
- rb.blocks[block.Hash] = block
- block.AckedValidators = make(map[types.ValidatorID]struct{})
- block.ReceivedTime = time.Now().UTC()
+ rb.blockInfos[block.Hash] = &rbcBlockInfo{
+ block: block,
+ receivedTime: time.Now().UTC(),
+ ackedValidators: make(map[types.ValidatorID]struct{}),
+ }
rb.receivedBlocks[block.Hash] = block
- block.AckedValidators = make(map[types.ValidatorID]struct{})
- block.ReceivedTime = time.Now()
// 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
@@ -181,7 +201,7 @@ func (rb *reliableBroadcast) processBlock(block *types.Block) (err error) {
// \ / (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 = rb.sanityCheck(b); err != nil {
- delete(rb.blocks, b.Hash)
+ delete(rb.blockInfos, b.Hash)
delete(rb.receivedBlocks, b.Hash)
continue
// TODO(mission): how to return for multiple errors?
@@ -189,48 +209,50 @@ func (rb *reliableBroadcast) processBlock(block *types.Block) (err error) {
rb.lattice[b.ProposerID].blocks[b.Height] = b
delete(rb.receivedBlocks, b.Hash)
for h := range b.Acks {
- bAck := rb.blocks[h]
- // Update nextAck only when bAck.Height + 1 is greater. A block might
- // ack blocks proposed by same validator with different height.
- if rb.lattice[b.ProposerID].nextAck[bAck.ProposerID] < bAck.Height+1 {
- rb.lattice[b.ProposerID].nextAck[bAck.ProposerID] = bAck.Height + 1
+ bAckStat := rb.blockInfos[h]
+ // Update nextAck only when bAckStat.block.Height + 1 is greater. A
+ // block might ack blocks proposed by same validator with different
+ // height.
+ if rb.lattice[b.ProposerID].nextAck[bAckStat.block.ProposerID] < bAckStat.block.Height+1 {
+ rb.lattice[b.ProposerID].nextAck[bAckStat.block.ProposerID] = bAckStat.block.Height + 1
}
- // Update AckedValidators for each ack blocks and its parents.
+ // Update ackedValidators for each ack blocks and its parents.
for {
- if _, exist := bAck.AckedValidators[b.ProposerID]; exist {
+ if _, exist := bAckStat.ackedValidators[b.ProposerID]; exist {
break
}
- if bAck.Status > types.BlockStatusInit {
+ if bAckStat.status > blockStatusInit {
break
}
- bAck.AckedValidators[b.ProposerID] = struct{}{}
+ bAckStat.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(rb.lattice)-1)/3) {
- blocksToAcked[bAck.Hash] = bAck
+ if len(bAckStat.ackedValidators) > 2*((len(rb.lattice)-1)/3) {
+ blocksToAcked[bAckStat.block.Hash] = bAckStat.block
}
- if bAck.Height == 0 {
+ if bAckStat.block.Height == 0 {
break
}
- bAck = rb.blocks[bAck.ParentHash]
+ bAckStat = rb.blockInfos[bAckStat.block.ParentHash]
}
}
}
}
for _, b := range blocksToAcked {
- b.Status = types.BlockStatusAcked
+ rb.blockInfos[b.Hash].status = blockStatusAcked
}
// Delete blocks in received array when it is received a long time ago.
oldBlocks := []common.Hash{}
for h, b := range rb.receivedBlocks {
- if time.Now().Sub(b.ReceivedTime) >= 30*time.Second {
+ if time.Now().Sub(rb.blockInfos[b.Hash].receivedTime) >= 30*time.Second {
oldBlocks = append(oldBlocks, h)
}
}
for _, h := range oldBlocks {
delete(rb.receivedBlocks, h)
+ delete(rb.blockInfos, h)
}
// Delete old blocks in "lattice" and "blocks" for release memory space.
@@ -258,9 +280,9 @@ func (rb *reliableBroadcast) processBlock(block *types.Block) (err error) {
if !exist {
break
}
- if b.Status >= types.BlockStatusOrdering {
+ if rb.blockInfos[b.Hash].status >= blockStatusOrdering {
delete(rb.lattice[vid].blocks, b.Height)
- delete(rb.blocks, b.Hash)
+ delete(rb.blockInfos, b.Hash)
}
if min == 0 {
break
@@ -272,15 +294,15 @@ func (rb *reliableBroadcast) processBlock(block *types.Block) (err error) {
}
// extractBlocks returns all blocks that can be inserted into total ordering's
-// DAG. This function changes the status of blocks from types.BlockStatusAcked
-// to blockStatusOrdering.
+// DAG. This function changes the status of blocks from blockStatusAcked to
+// blockStatusOrdering.
func (rb *reliableBroadcast) extractBlocks() []*types.Block {
ret := []*types.Block{}
for {
updated := false
for vid := range rb.lattice {
b, exist := rb.lattice[vid].blocks[rb.lattice[vid].nextOutput]
- if !exist || b.Status < types.BlockStatusAcked {
+ if !exist || rb.blockInfos[b.Hash].status < blockStatusAcked {
continue
}
allAcksInOrderingStatus := true
@@ -288,11 +310,11 @@ func (rb *reliableBroadcast) extractBlocks() []*types.Block {
// does not exist means that it deleted but its status is definitely Acked
// or ordering.
for ackHash := range b.Acks {
- bAck, exist := rb.blocks[ackHash]
+ bAckStat, exist := rb.blockInfos[ackHash]
if !exist {
continue
}
- if bAck.Status < types.BlockStatusOrdering {
+ if bAckStat.status < blockStatusOrdering {
allAcksInOrderingStatus = false
break
}
@@ -301,7 +323,7 @@ func (rb *reliableBroadcast) extractBlocks() []*types.Block {
continue
}
updated = true
- b.Status = types.BlockStatusOrdering
+ rb.blockInfos[b.Hash].status = blockStatusOrdering
ret = append(ret, b)
rb.lattice[vid].nextOutput++
}
@@ -385,7 +407,7 @@ func (rb *reliableBroadcast) prepareBlock(block *types.Block) {
// addValidator adds validator in the validator set.
func (rb *reliableBroadcast) addValidator(h types.ValidatorID) {
- rb.lattice[h] = &reliableBroadcastValidatorStatus{
+ rb.lattice[h] = &rbcValidatorStatus{
blocks: make(map[uint64]*types.Block),
nextAck: make(map[types.ValidatorID]uint64),
nextOutput: 0,
diff --git a/core/reliable-broadcast_test.go b/core/reliable-broadcast_test.go
index c1d0097..c6e9400 100644
--- a/core/reliable-broadcast_test.go
+++ b/core/reliable-broadcast_test.go
@@ -343,11 +343,11 @@ func (s *ReliableBroadcastTest) TestStrongAck() {
// Check block 0-0 to 0-3 before adding 1-1 and 2-1.
for i := uint64(0); i < 4; i++ {
- s.Require().Equal(types.BlockStatusInit, rb.lattice[vids[0]].blocks[i].Status)
+ s.Require().Equal(blockStatusInit, rb.blockInfos[rb.lattice[vids[0]].blocks[i].Hash].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.
+ // in blockStatusInit, because they are not strongly acked.
b = &types.Block{
ProposerID: vids[1],
ParentHash: rb.lattice[vids[1]].blocks[0].Hash,
@@ -365,7 +365,8 @@ func (s *ReliableBroadcastTest) TestStrongAck() {
s.Require().Nil(rb.processBlock(b))
s.Require().NotNil(rb.lattice[vids[1]].blocks[1])
for i := uint64(0); i < 4; i++ {
- s.Require().Equal(types.BlockStatusInit, rb.lattice[vids[0]].blocks[i].Status)
+ h := rb.lattice[vids[0]].blocks[i].Hash
+ s.Require().Equal(blockStatusInit, rb.blockInfos[h].status)
}
// Add block 2-1 which acks 0-2 and 2-0, block 0-0 to 0-2 are strongly acked but
@@ -385,10 +386,10 @@ func (s *ReliableBroadcastTest) TestStrongAck() {
s.Require().Nil(err)
s.Require().Nil(rb.processBlock(b))
- s.Require().Equal(types.BlockStatusAcked, rb.lattice[vids[0]].blocks[0].Status)
- s.Require().Equal(types.BlockStatusAcked, rb.lattice[vids[0]].blocks[1].Status)
- s.Require().Equal(types.BlockStatusAcked, rb.lattice[vids[0]].blocks[2].Status)
- s.Require().Equal(types.BlockStatusInit, rb.lattice[vids[0]].blocks[3].Status)
+ s.Require().Equal(blockStatusAcked, rb.blockInfos[rb.lattice[vids[0]].blocks[0].Hash].status)
+ s.Require().Equal(blockStatusAcked, rb.blockInfos[rb.lattice[vids[0]].blocks[1].Hash].status)
+ s.Require().Equal(blockStatusAcked, rb.blockInfos[rb.lattice[vids[0]].blocks[2].Hash].status)
+ s.Require().Equal(blockStatusInit, rb.blockInfos[rb.lattice[vids[0]].blocks[3].Hash].status)
}
func (s *ReliableBroadcastTest) TestExtractBlocks() {
@@ -439,7 +440,7 @@ func (s *ReliableBroadcastTest) TestExtractBlocks() {
hashExtracted := map[common.Hash]*types.Block{}
for _, b := range rb.extractBlocks() {
hashExtracted[b.Hash] = b
- s.Require().Equal(types.BlockStatusOrdering, b.Status)
+ s.Require().Equal(blockStatusOrdering, rb.blockInfos[b.Hash].status)
}
for _, h := range hashes {
_, exist := hashExtracted[h]
@@ -492,8 +493,8 @@ func (s *ReliableBroadcastTest) TestRandomIntensiveAcking() {
extractedBlocks = append(extractedBlocks, rb.extractBlocks()...)
// The len of array extractedBlocks should be about 5000.
s.Require().True(len(extractedBlocks) > 4500)
- // The len of rb.blocks should be small if deleting mechanism works.
- // s.True(len(rb.blocks) < 500)
+ // The len of rb.blockInfos should be small if deleting mechanism works.
+ // s.True(len(rb.blockInfos) < 500)
}
func (s *ReliableBroadcastTest) TestRandomlyGeneratedBlocks() {
diff --git a/core/types/block.go b/core/types/block.go
index 9665043..0386ed7 100644
--- a/core/types/block.go
+++ b/core/types/block.go
@@ -28,17 +28,6 @@ import (
"github.com/dexon-foundation/dexon-consensus-core/crypto"
)
-// Status represents the block process state.
-type Status int
-
-// Block Status.
-const (
- BlockStatusInit Status = iota
- BlockStatusAcked
- BlockStatusOrdering
- BlockStatusFinal
-)
-
// NotaryAck represents the acking to the compaction chain.
type NotaryAck struct {
NotaryBlockHash common.Hash `json:"notary_block_hash"`
@@ -47,6 +36,14 @@ type NotaryAck struct {
NotarySignature crypto.Signature `json:"notary_signature"`
}
+// CompactionChainAck represents the acking to the compaction chain.
+type CompactionChainAck struct {
+ AckingBlockHash common.Hash `json:"acking_block_hash"`
+ // Signature is the signature of the hash value of
+ // Block.ConsensusInfoParentHash and Block.ConsensusInfo.
+ ConsensusSignature crypto.Signature `json:"consensus_signature"`
+}
+
// Notary represents the consensus information on the compaction chain.
type Notary struct {
Timestamp time.Time `json:"timestamp"`
@@ -70,10 +67,7 @@ type Block struct {
// the compaction chain.
NotaryParentHash common.Hash `json:"notary_parent_hash"`
- Ackeds map[common.Hash]struct{} `json:"-"`
- AckedValidators map[ValidatorID]struct{} `json:"-"`
- Status Status `json:"-"`
- ReceivedTime time.Time `json:"-"`
+ ConsensusInfoParentHash common.Hash `json:"consensus_info_parent_hash"`
}
// Block implements BlockConverter interface.