// 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"
"sort"
"testing"
"time"
"github.com/dexon-foundation/dexon-consensus-core/common"
"github.com/dexon-foundation/dexon-consensus-core/core/blockdb"
"github.com/dexon-foundation/dexon-consensus-core/core/test"
"github.com/dexon-foundation/dexon-consensus-core/core/types"
"github.com/stretchr/testify/suite"
)
type LatticeDataTestSuite struct {
suite.Suite
}
// genTestCase1 generates test case 1,
// 3
// |
// 2
// | \
// 1 | 1
// | | |
// 0 0 0 0 (block height)
// 0 1 2 3 (validator)
func (s *LatticeDataTestSuite) genTestCase1() (data *latticeData) {
// Create new reliableBroadcast instance with 4 validators
var (
round uint64
b *types.Block
delivered []*types.Block
h common.Hash
chainNum uint32 = 4
req = s.Require()
err error
)
db, err := blockdb.NewMemBackedBlockDB()
req.NoError(err)
data = newLatticeData(
db, round, s.newConfig(chainNum, 2*time.Nanosecond, 1000*time.Second))
// Add genesis blocks.
for i := uint32(0); i < chainNum; i++ {
b = s.prepareGenesisBlock(i)
delivered, err = data.addBlock(b)
// Genesis blocks are safe to be added to DAG, they acks no one.
req.Len(delivered, 1)
req.Nil(err)
}
// Add block 0-1 which acks 0-0.
h = data.chains[0].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Hash: common.NewRandomHash(),
Timestamp: time.Now().UTC(),
Position: types.Position{
ChainID: 0,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
Witness: types.Witness{
Height: 1,
},
}
s.hashBlock(b)
delivered, err = data.addBlock(b)
req.Len(delivered, 1)
req.Equal(delivered[0].Hash, b.Hash)
req.Nil(err)
req.NotNil(data.chains[0].getBlockByHeight(1))
// Add block 0-2 which acks 0-1 and 1-0.
h = data.chains[0].getBlockByHeight(1).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 0,
Height: 2,
},
Timestamp: time.Now().UTC(),
Acks: common.NewSortedHashes(common.Hashes{
h,
data.chains[1].getBlockByHeight(0).Hash,
}),
Witness: types.Witness{
Height: 2,
},
}
s.hashBlock(b)
delivered, err = data.addBlock(b)
req.Len(delivered, 1)
req.Equal(delivered[0].Hash, b.Hash)
req.Nil(err)
req.NotNil(data.chains[0].getBlockByHeight(2))
// Add block 0-3 which acks 0-2.
h = data.chains[0].getBlockByHeight(2).Hash
b = &types.Block{
ParentHash: h,
Hash: common.NewRandomHash(),
Timestamp: time.Now().UTC(),
Position: types.Position{
ChainID: 0,
Height: 3,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
Witness: types.Witness{
Height: 3,
},
}
s.hashBlock(b)
delivered, err = data.addBlock(b)
req.Len(delivered, 1)
req.Equal(delivered[0].Hash, b.Hash)
req.Nil(err)
req.NotNil(data.chains[0].getBlockByHeight(3))
// Add block 3-1 which acks 3-0.
h = data.chains[3].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Hash: common.NewRandomHash(),
Timestamp: time.Now().UTC(),
Position: types.Position{
ChainID: 3,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
Witness: types.Witness{
Height: 1,
},
}
s.hashBlock(b)
delivered, err = data.addBlock(b)
req.Len(delivered, 1)
req.Equal(delivered[0].Hash, b.Hash)
req.Nil(err)
req.NotNil(data.chains[3].getBlockByHeight(0))
return
}
func (s *LatticeDataTestSuite) newConfig(numChains uint32,
minBlockInterval, maxBlockInterval time.Duration) *latticeDataConfig {
return &latticeDataConfig{
numChains: numChains,
minBlockTimeInterval: minBlockInterval,
maxBlockTimeInterval: maxBlockInterval,
}
}
// hashBlock is a helper to hash a block and check if any error.
func (s *LatticeDataTestSuite) hashBlock(b *types.Block) {
var err error
b.Hash, err = hashBlock(b)
s.Require().Nil(err)
}
func (s *LatticeDataTestSuite) prepareGenesisBlock(
chainID uint32) (b *types.Block) {
b = &types.Block{
ParentHash: common.Hash{},
Position: types.Position{
ChainID: chainID,
Height: 0,
},
Acks: common.NewSortedHashes(common.Hashes{}),
Timestamp: time.Now().UTC(),
}
s.hashBlock(b)
return
}
func (s *LatticeDataTestSuite) TestSanityCheckInDataLayer() {
var (
b *types.Block
h common.Hash
data = s.genTestCase1()
req = s.Require()
err error
)
// Non-genesis block with no ack, should get error.
b = &types.Block{
ParentHash: common.NewRandomHash(),
Position: types.Position{
ChainID: 0,
Height: 10,
},
Acks: common.NewSortedHashes(common.Hashes{}),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(ErrNotAckParent.Error(), err.Error())
// Non-genesis block which acks its parent but the height is invalid.
h = data.chains[1].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 1,
Height: 2,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(ErrInvalidBlockHeight.Error(), err.Error())
// Invalid chain ID.
h = data.chains[1].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 100,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(ErrInvalidChainID.Error(), err.Error())
// Fork block.
h = data.chains[0].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 0,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
Timestamp: time.Now().UTC(),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(ErrForkBlock.Error(), err.Error())
// Replicated ack.
h = data.chains[0].getBlockByHeight(3).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 0,
Height: 4,
},
Acks: common.NewSortedHashes(common.Hashes{
h,
data.chains[1].getBlockByHeight(0).Hash,
}),
Timestamp: time.Now().UTC(),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(ErrDoubleAck.Error(), err.Error())
// Acking block doesn't exists.
h = data.chains[1].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 1,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{
h,
common.NewRandomHash(),
}),
Timestamp: time.Now().UTC(),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(err.Error(), ErrAckingBlockNotExists.Error())
// Parent block on different chain.
h = data.chains[1].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 2,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{
h,
data.chains[2].getBlockByHeight(0).Hash,
}),
Timestamp: time.Now().UTC(),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(err.Error(), ErrInvalidParentChain.Error())
// Ack two blocks on the same chain.
h = data.chains[2].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 2,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{
h,
data.chains[0].getBlockByHeight(0).Hash,
data.chains[0].getBlockByHeight(1).Hash,
}),
Timestamp: time.Now().UTC(),
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(err.Error(), ErrDuplicatedAckOnOneChain.Error())
// Witness height decreases.
h = data.chains[0].getBlockByHeight(3).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 0,
Height: 4,
},
Timestamp: time.Now().UTC(),
Acks: common.NewSortedHashes(common.Hashes{
h,
}),
Witness: types.Witness{
Height: 2,
},
}
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(err.Error(), ErrInvalidWitness.Error())
// Add block 3-1 which acks 3-0, and violet reasonable block time interval.
h = data.chains[2].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Hash: common.NewRandomHash(),
Position: types.Position{
ChainID: 2,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
}
b.Timestamp = data.chains[2].getBlockByHeight(0).Timestamp.Add(
data.getConfig(0).maxBlockTimeInterval + time.Nanosecond)
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(err, ErrIncorrectBlockTime)
// Violet minimum block time interval.
b.Timestamp =
data.chains[2].getBlockByHeight(0).Timestamp.Add(1 * time.Nanosecond)
s.hashBlock(b)
err = data.sanityCheck(b)
req.NotNil(err)
req.Equal(err, ErrIncorrectBlockTime)
// Normal block.
h = data.chains[1].getBlockByHeight(0).Hash
b = &types.Block{
ParentHash: h,
Position: types.Position{
ChainID: 1,
Height: 1,
},
Acks: common.NewSortedHashes(common.Hashes{h}),
Timestamp: time.Now().UTC(),
}
s.hashBlock(b)
req.Nil(data.sanityCheck(b))
}
func (s *LatticeDataTestSuite) TestRandomIntensiveAcking() {
var (
round uint64
chainNum uint32 = 19
req = s.Require()
delivered []*types.Block
extracted []*types.Block
b *types.Block
err error
)
db, err := blockdb.NewMemBackedBlockDB()
req.NoError(err)
data := newLatticeData(
db, round, s.newConfig(chainNum, 0, 1000*time.Second))
// Generate genesis blocks.
for i := uint32(0); i < chainNum; i++ {
b = s.prepareGenesisBlock(i)
delivered, err = data.addBlock(b)
req.Len(delivered, 1)
req.Nil(err)
}
for i := 0; i < 5000; i++ {
b := &types.Block{
Position: types.Position{
ChainID: uint32(rand.Intn(int(chainNum))),
},
Timestamp: time.Now().UTC(),
}
data.prepareBlock(b)
s.hashBlock(b)
delivered, err = data.addBlock(b)
req.Nil(err)
for _, b := range delivered {
req.NoError(db.Put(*b))
}
req.NoError(data.purgeBlocks(delivered))
extracted = append(extracted, delivered...)
}
// The len of array extractedBlocks should be about 5000.
req.True(len(extracted) > 4500)
// The len of data.blockInfos should be small if deleting mechanism works.
req.True(len(data.blockByHash) < 500)
}
func (s *LatticeDataTestSuite) TestRandomlyGeneratedBlocks() {
var (
round uint64
chainNum uint32 = 19
blockNum = 50
repeat = 20
delivered []*types.Block
err error
req = s.Require()
datum []*latticeData
)
if testing.Short() {
chainNum = 7
repeat = 3
}
// Prepare a randomly generated blocks.
db, err := blockdb.NewMemBackedBlockDB()
req.Nil(err)
gen := test.NewBlocksGenerator(nil, hashBlock)
_, err = gen.Generate(chainNum, blockNum, nil, db)
req.Nil(err)
iter, err := db.GetAll()
req.Nil(err)
// Setup a revealer that would reveal blocks randomly but still form
// valid DAG without holes.
revealer, err := test.NewRandomDAGRevealer(iter)
req.Nil(err)
revealedHashesAsString := map[string]struct{}{}
deliveredHashesAsString := map[string]struct{}{}
for i := 0; i < repeat; i++ {
data := newLatticeData(
nil, round, s.newConfig(chainNum, 0, 1000*time.Second))
deliveredHashes := common.Hashes{}
revealedHashes := common.Hashes{}
revealer.Reset()
for {
// Reveal next block.
b, err := revealer.Next()
if err != nil {
if err == blockdb.ErrIterationFinished {
err = nil
break
}
}
s.Require().Nil(err)
revealedHashes = append(revealedHashes, b.Hash)
// Pass blocks to lattice.
delivered, err = data.addBlock(&b)
req.Nil(err)
for _, b := range delivered {
deliveredHashes = append(deliveredHashes, b.Hash)
}
}
// To make it easier to check, sort hashes of
// strongly acked blocks, and concatenate them into
// a string.
sort.Sort(deliveredHashes)
asString := ""
for _, h := range deliveredHashes {
asString += h.String() + ","
}
deliveredHashesAsString[asString] = struct{}{}
// Compose revealing hash sequense to string.
asString = ""
for _, h := range revealedHashes {
asString += h.String() + ","
}
revealedHashesAsString[asString] = struct{}{}
datum = append(datum, data)
}
// Make sure concatenated hashes of strongly acked blocks are identical.
req.Len(deliveredHashesAsString, 1)
for h := range deliveredHashesAsString {
// Make sure at least some blocks are strongly acked.
req.True(len(h) > 0)
}
// Make sure we test for more than 1 revealing sequence.
req.True(len(revealedHashesAsString) > 1)
// Make sure each latticeData instance have identical working set.
req.True(len(datum) >= repeat)
for i, bI := range datum {
for j, bJ := range datum {
if i == j {
continue
}
for chainID, statusI := range bI.chains {
req.Equal(statusI.minHeight, bJ.chains[chainID].minHeight)
req.Equal(statusI.nextOutput, bJ.chains[chainID].nextOutput)
req.Equal(len(statusI.blocks), len(bJ.chains[chainID].blocks))
// Check nextAck.
for x, ackI := range statusI.nextAck {
req.Equal(ackI, bJ.chains[chainID].nextAck[x])
}
// Check blocks.
if len(statusI.blocks) > 0 {
req.Equal(statusI.blocks[0], bJ.chains[chainID].blocks[0])
}
}
// Check blockByHash.
req.Equal(bI.blockByHash, bJ.blockByHash)
}
}
}
func (s *LatticeDataTestSuite) TestPrepareBlock() {
var (
round uint64
chainNum uint32 = 4
req = s.Require()
minInterval = 50 * time.Millisecond
delivered []*types.Block
err error
data = newLatticeData(
nil, round, s.newConfig(chainNum, 0, 3000*time.Second))
)
// Setup genesis blocks.
b00 := s.prepareGenesisBlock(0)
time.Sleep(minInterval)
b10 := s.prepareGenesisBlock(1)
time.Sleep(minInterval)
b20 := s.prepareGenesisBlock(2)
time.Sleep(minInterval)
b30 := s.prepareGenesisBlock(3)
// Submit these blocks to lattice.
delivered, err = data.addBlock(b00)
req.Len(delivered, 1)
req.Nil(err)
delivered, err = data.addBlock(b10)
req.Len(delivered, 1)
req.Nil(err)
delivered, err = data.addBlock(b20)
req.Len(delivered, 1)
req.Nil(err)
delivered, err = data.addBlock(b30)
req.Len(delivered, 1)
req.Nil(err)
// We should be able to collect all 4 genesis blocks by calling
// prepareBlock.
b11 := &types.Block{
Position: types.Position{
ChainID: 1,
},
Timestamp: time.Now().UTC(),
}
data.prepareBlock(b11)
s.hashBlock(b11)
req.Contains(b11.Acks, b00.Hash)
req.Contains(b11.Acks, b10.Hash)
req.Contains(b11.Acks, b20.Hash)
req.Contains(b11.Acks, b30.Hash)
req.Equal(b11.ParentHash, b10.Hash)
req.Equal(b11.Position.Height, uint64(1))
delivered, err = data.addBlock(b11)
req.Len(delivered, 1)
req.Nil(err)
// Propose/Process a block based on collected info.
b12 := &types.Block{
Position: types.Position{
ChainID: 1,
},
Timestamp: time.Now().UTC(),
}
data.prepareBlock(b12)
s.hashBlock(b12)
// This time we only need to ack b11.
req.Len(b12.Acks, 1)
req.Contains(b12.Acks, b11.Hash)
req.Equal(b12.ParentHash, b11.Hash)
req.Equal(b12.Position.Height, uint64(2))
// When calling with other validator ID, we should be able to
// get 4 blocks to ack.
b01 := &types.Block{
Position: types.Position{
ChainID: 0,
},
}
data.prepareBlock(b01)
s.hashBlock(b01)
req.Len(b01.Acks, 4)
req.Contains(b01.Acks, b00.Hash)
req.Contains(b01.Acks, b11.Hash)
req.Contains(b01.Acks, b20.Hash)
req.Contains(b01.Acks, b30.Hash)
req.Equal(b01.ParentHash, b00.Hash)
req.Equal(b01.Position.Height, uint64(1))
}
func (s *LatticeDataTestSuite) TestCalcPurgeHeight() {
// Test chainStatus.calcPurgeHeight, we don't have
// to prepare blocks to test it.
var req = s.Require()
chain := &chainStatus{
minHeight: 0,
nextOutput: 0,
nextAck: []uint64{1, 1, 1, 1},
}
// When calculated safe is underflow, nok.
safe, ok := chain.calcPurgeHeight()
req.False(ok)
// height=1 is outputed, and acked by everyone else.
chain.nextOutput = 1
safe, ok = chain.calcPurgeHeight()
req.True(ok)
req.Equal(safe, uint64(0))
// Should take nextAck's height into consideration.
chain.nextOutput = 2
safe, ok = chain.calcPurgeHeight()
req.True(ok)
req.Equal(safe, uint64(0))
// When minHeight is large that safe height, return nok.
chain.minHeight = 1
chain.nextOutput = 1
safe, ok = chain.calcPurgeHeight()
req.False(ok)
}
func (s *LatticeDataTestSuite) TestPurge() {
// Make a simplest test case to test chainStatus.purge.
// Make sure status after purge 1 block expected.
b00 := &types.Block{Hash: common.NewRandomHash()}
b01 := &types.Block{Hash: common.NewRandomHash()}
b02 := &types.Block{Hash: common.NewRandomHash()}
chain := &chainStatus{
blocks: []*types.Block{b00, b01, b02},
nextAck: []uint64{1, 1, 1, 1},
nextOutput: 1,
}
chain.purge()
s.Equal(chain.minHeight, uint64(1))
s.Require().Len(chain.blocks, 2)
s.Equal(chain.blocks[0].Hash, b01.Hash)
s.Equal(chain.blocks[1].Hash, b02.Hash)
}
func (s *LatticeDataTestSuite) TestNextPosition() {
// Test 'NextPosition' method when lattice is ready.
data := s.genTestCase1()
s.Equal(data.nextPosition(0), types.Position{ChainID: 0, Height: 4})
// Test 'NextPosition' method when lattice is empty.
data = newLatticeData(nil, 0, s.newConfig(4, 0, 1000*time.Second))
s.Equal(data.nextPosition(0), types.Position{ChainID: 0, Height: 0})
}
func TestLatticeData(t *testing.T) {
suite.Run(t, new(LatticeDataTestSuite))
}
