1 files changed, 681 insertions, 0 deletions
diff --git a/vendor/github.com/byzantine-lab/dexon-consensus/core/blockchain.go b/vendor/github.com/byzantine-lab/dexon-consensus/core/blockchain.go
new file mode 100644
index 000000000..579ccd44c
--- /dev/null
+++ b/vendor/github.com/byzantine-lab/dexon-consensus/core/blockchain.go
@@ -0,0 +1,681 @@
+// Copyright 2019 The dexon-consensus Authors
+// This file is part of the dexon-consensus library.
+//
+// The dexon-consensus 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 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 library. If not, see
+// <http://www.gnu.org/licenses/>.
+
+package core
+
+import (
+	"bytes"
+	"errors"
+	"fmt"
+	"math"
+	"sort"
+	"sync"
+	"time"
+
+	"github.com/byzantine-lab/dexon-consensus/common"
+	"github.com/byzantine-lab/dexon-consensus/core/crypto"
+	"github.com/byzantine-lab/dexon-consensus/core/types"
+	"github.com/byzantine-lab/dexon-consensus/core/utils"
+)
+
+// Errors for sanity check error.
+var (
+	ErrBlockFromOlderPosition   = errors.New("block from older position")
+	ErrNotGenesisBlock          = errors.New("not a genesis block")
+	ErrIsGenesisBlock           = errors.New("is a genesis block")
+	ErrIncorrectParentHash      = errors.New("incorrect parent hash")
+	ErrInvalidBlockHeight       = errors.New("invalid block height")
+	ErrInvalidRoundID           = errors.New("invalid round id")
+	ErrInvalidTimestamp         = errors.New("invalid timestamp")
+	ErrNotFollowTipPosition     = errors.New("not follow tip position")
+	ErrDuplicatedPendingBlock   = errors.New("duplicated pending block")
+	ErrRetrySanityCheckLater    = errors.New("retry sanity check later")
+	ErrRoundNotSwitch           = errors.New("round not switch")
+	ErrIncorrectAgreementResult = errors.New(
+		"incorrect block randomness result")
+	ErrMissingRandomness = errors.New("missing block randomness")
+)
+
+const notReadyHeight uint64 = math.MaxUint64
+
+type pendingBlockRecord struct {
+	position types.Position
+	block    *types.Block
+}
+
+type pendingBlockRecords []pendingBlockRecord
+
+func (pb *pendingBlockRecords) insert(p pendingBlockRecord) error {
+	idx := sort.Search(len(*pb), func(i int) bool {
+		return !(*pb)[i].position.Older(p.position)
+	})
+	switch idx {
+	case len(*pb):
+		*pb = append(*pb, p)
+	default:
+		if (*pb)[idx].position.Equal(p.position) {
+			// Allow to overwrite pending block record for empty blocks, we may
+			// need to pull that block from others when its parent is not found
+			// locally.
+			if (*pb)[idx].block == nil && p.block != nil {
+				(*pb)[idx].block = p.block
+				return nil
+			}
+			return ErrDuplicatedPendingBlock
+		}
+		// Insert the value to that index.
+		*pb = append((*pb), pendingBlockRecord{})
+		copy((*pb)[idx+1:], (*pb)[idx:])
+		(*pb)[idx] = p
+	}
+	return nil
+}
+
+func (pb pendingBlockRecords) searchByHeight(h uint64) (
+	pendingBlockRecord, bool) {
+	idx := sort.Search(len(pb), func(i int) bool {
+		return pb[i].position.Height >= h
+	})
+	if idx == len(pb) || pb[idx].position.Height != h {
+		return pendingBlockRecord{}, false
+	}
+	return pb[idx], true
+}
+
+func (pb pendingBlockRecords) searchByPosition(p types.Position) (
+	pendingBlockRecord, bool) {
+	idx := sort.Search(len(pb), func(i int) bool {
+		return !pb[i].block.Position.Older(p)
+	})
+	if idx == len(pb) || !pb[idx].position.Equal(p) {
+		return pendingBlockRecord{}, false
+	}
+	return pb[idx], true
+}
+
+type blockChainConfig struct {
+	utils.RoundBasedConfig
+
+	minBlockInterval time.Duration
+}
+
+func (c *blockChainConfig) fromConfig(round uint64, config *types.Config) {
+	c.minBlockInterval = config.MinBlockInterval
+	c.SetupRoundBasedFields(round, config)
+}
+
+func newBlockChainConfig(prev blockChainConfig, config *types.Config) (
+	c blockChainConfig) {
+	c = blockChainConfig{}
+	c.fromConfig(prev.RoundID()+1, config)
+	c.AppendTo(prev.RoundBasedConfig)
+	return
+}
+
+type tsigVerifierGetter interface {
+	UpdateAndGet(uint64) (TSigVerifier, bool, error)
+	Purge(uint64)
+}
+
+type blockChain struct {
+	lock                sync.RWMutex
+	ID                  types.NodeID
+	lastConfirmed       *types.Block
+	lastDelivered       *types.Block
+	signer              *utils.Signer
+	vGetter             tsigVerifierGetter
+	app                 Application
+	logger              common.Logger
+	pendingRandomnesses map[types.Position][]byte
+	configs             []blockChainConfig
+	pendingBlocks       pendingBlockRecords
+	confirmedBlocks     types.BlocksByPosition
+	dMoment             time.Time
+
+	// Do not access this variable besides processAgreementResult.
+	lastPosition types.Position
+}
+
+func newBlockChain(nID types.NodeID, dMoment time.Time, initBlock *types.Block,
+	app Application, vGetter tsigVerifierGetter, signer *utils.Signer,
+	logger common.Logger) *blockChain {
+	return &blockChain{
+		ID:            nID,
+		lastConfirmed: initBlock,
+		lastDelivered: initBlock,
+		signer:        signer,
+		vGetter:       vGetter,
+		app:           app,
+		logger:        logger,
+		dMoment:       dMoment,
+		pendingRandomnesses: make(
+			map[types.Position][]byte),
+	}
+}
+
+func (bc *blockChain) notifyRoundEvents(evts []utils.RoundEventParam) error {
+	bc.lock.Lock()
+	defer bc.lock.Unlock()
+	apply := func(e utils.RoundEventParam) error {
+		if len(bc.configs) > 0 {
+			lastCfg := bc.configs[len(bc.configs)-1]
+			if e.BeginHeight != lastCfg.RoundEndHeight() {
+				return ErrInvalidBlockHeight
+			}
+			if lastCfg.RoundID() == e.Round {
+				bc.configs[len(bc.configs)-1].ExtendLength()
+			} else if lastCfg.RoundID()+1 == e.Round {
+				bc.configs = append(bc.configs, newBlockChainConfig(
+					lastCfg, e.Config))
+			} else {
+				return ErrInvalidRoundID
+			}
+		} else {
+			c := blockChainConfig{}
+			c.fromConfig(e.Round, e.Config)
+			c.SetRoundBeginHeight(e.BeginHeight)
+			if bc.lastConfirmed == nil {
+				if c.RoundID() != 0 {
+					panic(fmt.Errorf(
+						"genesis config should from round 0, but %d",
+						c.RoundID()))
+				}
+			} else {
+				if c.RoundID() != bc.lastConfirmed.Position.Round {
+					panic(fmt.Errorf("incompatible config/block round %s %d",
+						bc.lastConfirmed, c.RoundID()))
+				}
+				if !c.Contains(bc.lastConfirmed.Position.Height) {
+					panic(fmt.Errorf(
+						"unmatched round-event with block %s %d %d %d",
+						bc.lastConfirmed, e.Round, e.Reset, e.BeginHeight))
+				}
+			}
+			bc.configs = append(bc.configs, c)
+		}
+		return nil
+	}
+	for _, e := range evts {
+		if err := apply(e); err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
+func (bc *blockChain) proposeBlock(position types.Position,
+	proposeTime time.Time, isEmpty bool) (b *types.Block, err error) {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	return bc.prepareBlock(position, proposeTime, isEmpty)
+}
+
+func (bc *blockChain) extractBlocks() (ret []*types.Block) {
+	bc.lock.Lock()
+	defer bc.lock.Unlock()
+	for len(bc.confirmedBlocks) > 0 {
+		c := bc.confirmedBlocks[0]
+		if c.Position.Round >= DKGDelayRound &&
+			len(c.Randomness) == 0 &&
+			!bc.setRandomnessFromPending(c) {
+			break
+		}
+		c, bc.confirmedBlocks = bc.confirmedBlocks[0], bc.confirmedBlocks[1:]
+		ret = append(ret, c)
+		bc.lastDelivered = c
+	}
+	return
+}
+
+func (bc *blockChain) sanityCheck(b *types.Block) error {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	if bc.lastConfirmed == nil {
+		// It should be a genesis block.
+		if !b.IsGenesis() {
+			return ErrNotGenesisBlock
+		}
+		if b.Timestamp.Before(bc.dMoment.Add(bc.configs[0].minBlockInterval)) {
+			return ErrInvalidTimestamp
+		}
+		return nil
+	}
+	if b.IsGenesis() {
+		return ErrIsGenesisBlock
+	}
+	if b.Position.Height != bc.lastConfirmed.Position.Height+1 {
+		if b.Position.Height > bc.lastConfirmed.Position.Height {
+			return ErrRetrySanityCheckLater
+		}
+		return ErrInvalidBlockHeight
+	}
+	tipConfig := bc.tipConfig()
+	if tipConfig.IsLastBlock(bc.lastConfirmed) {
+		if b.Position.Round != bc.lastConfirmed.Position.Round+1 {
+			return ErrRoundNotSwitch
+		}
+	} else {
+		if b.Position.Round != bc.lastConfirmed.Position.Round {
+			return ErrInvalidRoundID
+		}
+	}
+	if !b.ParentHash.Equal(bc.lastConfirmed.Hash) {
+		return ErrIncorrectParentHash
+	}
+	if b.Timestamp.Before(bc.lastConfirmed.Timestamp.Add(
+		tipConfig.minBlockInterval)) {
+		return ErrInvalidTimestamp
+	}
+	if err := utils.VerifyBlockSignature(b); err != nil {
+		return err
+	}
+	return nil
+}
+
+// addEmptyBlock is called when an empty block is confirmed by BA.
+func (bc *blockChain) addEmptyBlock(position types.Position) (
+	*types.Block, error) {
+	bc.lock.Lock()
+	defer bc.lock.Unlock()
+	add := func() *types.Block {
+		emptyB, err := bc.prepareBlock(position, time.Time{}, true)
+		if err != nil || emptyB == nil {
+			// This helper is expected to be called when an empty block is ready
+			// to be confirmed.
+			panic(err)
+		}
+		bc.confirmBlock(emptyB)
+		bc.checkIfBlocksConfirmed()
+		return emptyB
+	}
+	if bc.lastConfirmed != nil {
+		if !position.Newer(bc.lastConfirmed.Position) {
+			bc.logger.Warn("Dropping empty block: older than tip",
+				"position", &position,
+				"last-confirmed", bc.lastConfirmed)
+			return nil, ErrBlockFromOlderPosition
+		}
+		if bc.lastConfirmed.Position.Height+1 == position.Height {
+			return add(), nil
+		}
+	} else if position.Height == types.GenesisHeight && position.Round == 0 {
+		return add(), nil
+	} else {
+		return nil, ErrInvalidBlockHeight
+	}
+	return nil, bc.addPendingBlockRecord(pendingBlockRecord{position, nil})
+}
+
+// addBlock should be called when the block is confirmed by BA, we won't perform
+// sanity check against this block, it's ok to add block with skipping height.
+func (bc *blockChain) addBlock(b *types.Block) error {
+	if b.Position.Round >= DKGDelayRound &&
+		len(b.Randomness) == 0 &&
+		!bc.setRandomnessFromPending(b) {
+		return ErrMissingRandomness
+	}
+	bc.lock.Lock()
+	defer bc.lock.Unlock()
+	confirmed := false
+	if bc.lastConfirmed != nil {
+		if !b.Position.Newer(bc.lastConfirmed.Position) {
+			bc.logger.Warn("Dropping block: older than tip",
+				"block", b, "last-confirmed", bc.lastConfirmed)
+			return nil
+		}
+		if bc.lastConfirmed.Position.Height+1 == b.Position.Height {
+			confirmed = true
+		}
+	} else if b.IsGenesis() {
+		confirmed = true
+	}
+	delete(bc.pendingRandomnesses, b.Position)
+	if !confirmed {
+		return bc.addPendingBlockRecord(pendingBlockRecord{b.Position, b})
+	}
+	bc.confirmBlock(b)
+	bc.checkIfBlocksConfirmed()
+	return nil
+}
+
+func (bc *blockChain) tipRound() uint64 {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	if bc.lastConfirmed == nil {
+		return 0
+	}
+	offset, tipConfig := uint64(0), bc.tipConfig()
+	if tipConfig.IsLastBlock(bc.lastConfirmed) {
+		offset++
+	}
+	return bc.lastConfirmed.Position.Round + offset
+}
+
+func (bc *blockChain) confirmed(h uint64) bool {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	if bc.lastConfirmed != nil && bc.lastConfirmed.Position.Height >= h {
+		return true
+	}
+	r, found := bc.pendingBlocks.searchByHeight(h)
+	if !found {
+		return false
+	}
+	return r.block != nil
+}
+
+func (bc *blockChain) nextBlock() (uint64, time.Time) {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	// It's ok to access tip config directly without checking the existence of
+	// lastConfirmed block in the scenario of "nextBlock" method.
+	tip, config := bc.lastConfirmed, bc.configs[0]
+	if tip == nil {
+		return types.GenesisHeight, bc.dMoment
+	}
+	if tip != bc.lastDelivered {
+		// If tip is not delivered, we should not proceed to next block.
+		return notReadyHeight, time.Time{}
+	}
+	return tip.Position.Height + 1, tip.Timestamp.Add(config.minBlockInterval)
+}
+
+func (bc *blockChain) pendingBlocksWithoutRandomness() []*types.Block {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	blocks := make([]*types.Block, 0)
+	for _, b := range bc.confirmedBlocks {
+		if b.Position.Round < DKGDelayRound ||
+			len(b.Randomness) > 0 ||
+			bc.setRandomnessFromPending(b) {
+			continue
+		}
+		blocks = append(blocks, b)
+	}
+	for _, r := range bc.pendingBlocks {
+		if r.position.Round < DKGDelayRound {
+			continue
+		}
+		if r.block != nil &&
+			len(r.block.Randomness) == 0 &&
+			!bc.setRandomnessFromPending(r.block) {
+			blocks = append(blocks, r.block)
+		}
+	}
+	return blocks
+}
+
+func (bc *blockChain) lastDeliveredBlock() *types.Block {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	return bc.lastDelivered
+}
+
+func (bc *blockChain) lastPendingBlock() *types.Block {
+	bc.lock.RLock()
+	defer bc.lock.RUnlock()
+	if len(bc.confirmedBlocks) == 0 {
+		return nil
+	}
+	return bc.confirmedBlocks[0]
+}
+
+/////////////////////////////////////////////
+//
+// internal helpers
+//
+/////////////////////////////////////////////
+
+// findPendingBlock is a helper to find a block in either pending or confirmed
+// state by position.
+func (bc *blockChain) findPendingBlock(p types.Position) *types.Block {
+	if idx := sort.Search(len(bc.confirmedBlocks), func(i int) bool {
+		return !bc.confirmedBlocks[i].Position.Older(p)
+	}); idx != len(bc.confirmedBlocks) &&
+		bc.confirmedBlocks[idx].Position.Equal(p) {
+		return bc.confirmedBlocks[idx]
+	}
+	pendingRec, _ := bc.pendingBlocks.searchByPosition(p)
+	return pendingRec.block
+}
+
+func (bc *blockChain) addPendingBlockRecord(p pendingBlockRecord) error {
+	if err := bc.pendingBlocks.insert(p); err != nil {
+		if err == ErrDuplicatedPendingBlock {
+			// We need to ignore this error because BA might confirm duplicated
+			// blocks in position.
+			err = nil
+		}
+		return err
+	}
+	return nil
+}
+
+func (bc *blockChain) checkIfBlocksConfirmed() {
+	var err error
+	for len(bc.pendingBlocks) > 0 {
+		if bc.pendingBlocks[0].position.Height <
+			bc.lastConfirmed.Position.Height+1 {
+			panic(fmt.Errorf("unexpected case %s %s", bc.lastConfirmed,
+				bc.pendingBlocks[0].position))
+		}
+		if bc.pendingBlocks[0].position.Height >
+			bc.lastConfirmed.Position.Height+1 {
+			break
+		}
+		var pending pendingBlockRecord
+		pending, bc.pendingBlocks = bc.pendingBlocks[0], bc.pendingBlocks[1:]
+		nextTip := pending.block
+		if nextTip == nil {
+			if nextTip, err = bc.prepareBlock(
+				pending.position, time.Time{}, true); err != nil {
+				// It should not be error when prepare empty block for correct
+				// position.
+				panic(err)
+			}
+		}
+		bc.confirmBlock(nextTip)
+	}
+}
+
+func (bc *blockChain) purgeConfig() {
+	for bc.configs[0].RoundID() < bc.lastConfirmed.Position.Round {
+		bc.configs = bc.configs[1:]
+	}
+	if bc.configs[0].RoundID() != bc.lastConfirmed.Position.Round {
+		panic(fmt.Errorf("mismatched tip config: %d %d",
+			bc.configs[0].RoundID(), bc.lastConfirmed.Position.Round))
+	}
+}
+
+func (bc *blockChain) verifyRandomness(
+	blockHash common.Hash, round uint64, randomness []byte) (bool, error) {
+	if round < DKGDelayRound {
+		return bytes.Compare(randomness, NoRand) == 0, nil
+	}
+	v, ok, err := bc.vGetter.UpdateAndGet(round)
+	if err != nil {
+		return false, err
+	}
+	if !ok {
+		return false, ErrTSigNotReady
+	}
+	return v.VerifySignature(blockHash, crypto.Signature{
+		Type:      "bls",
+		Signature: randomness}), nil
+}
+
+func (bc *blockChain) prepareBlock(position types.Position,
+	proposeTime time.Time, empty bool) (b *types.Block, err error) {
+	b = &types.Block{Position: position, Timestamp: proposeTime}
+	tip := bc.lastConfirmed
+	// Make sure we can propose a block at expected position for callers.
+	if tip == nil {
+		if bc.configs[0].RoundID() != uint64(0) {
+			panic(fmt.Errorf(
+				"Genesis config should be ready when preparing genesis: %d",
+				bc.configs[0].RoundID()))
+		}
+		// It should be the case for genesis block.
+		if !position.Equal(types.Position{Height: types.GenesisHeight}) {
+			b, err = nil, ErrNotGenesisBlock
+			return
+		}
+		minExpectedTime := bc.dMoment.Add(bc.configs[0].minBlockInterval)
+		if empty {
+			b.Timestamp = minExpectedTime
+		} else {
+			bc.logger.Debug("Calling genesis Application.PreparePayload")
+			if b.Payload, err = bc.app.PreparePayload(b.Position); err != nil {
+				b = nil
+				return
+			}
+			bc.logger.Debug("Calling genesis Application.PrepareWitness")
+			if b.Witness, err = bc.app.PrepareWitness(0); err != nil {
+				b = nil
+				return
+			}
+			if proposeTime.Before(minExpectedTime) {
+				b.Timestamp = minExpectedTime
+			}
+		}
+	} else {
+		tipConfig := bc.tipConfig()
+		if tip.Position.Height+1 != position.Height {
+			b, err = nil, ErrNotFollowTipPosition
+			return
+		}
+		if tipConfig.IsLastBlock(tip) {
+			if tip.Position.Round+1 != position.Round {
+				b, err = nil, ErrRoundNotSwitch
+				return
+			}
+		} else {
+			if tip.Position.Round != position.Round {
+				b, err = nil, ErrInvalidRoundID
+				return
+			}
+		}
+		minExpectedTime := tip.Timestamp.Add(bc.configs[0].minBlockInterval)
+		b.ParentHash = tip.Hash
+		if !empty {
+			bc.logger.Debug("Calling Application.PreparePayload",
+				"position", b.Position)
+			if b.Payload, err = bc.app.PreparePayload(b.Position); err != nil {
+				b = nil
+				return
+			}
+			bc.logger.Debug("Calling Application.PrepareWitness",
+				"height", tip.Witness.Height)
+			if b.Witness, err = bc.app.PrepareWitness(
+				tip.Witness.Height); err != nil {
+				b = nil
+				return
+			}
+			if b.Timestamp.Before(minExpectedTime) {
+				b.Timestamp = minExpectedTime
+			}
+		} else {
+			b.Witness.Height = tip.Witness.Height
+			b.Witness.Data = make([]byte, len(tip.Witness.Data))
+			copy(b.Witness.Data, tip.Witness.Data)
+			b.Timestamp = minExpectedTime
+		}
+	}
+	if empty {
+		if b.Hash, err = utils.HashBlock(b); err != nil {
+			b = nil
+			return
+		}
+	} else {
+		if err = bc.signer.SignBlock(b); err != nil {
+			b = nil
+			return
+		}
+	}
+	return
+}
+
+func (bc *blockChain) tipConfig() blockChainConfig {
+	if bc.lastConfirmed == nil {
+		panic(fmt.Errorf("attempting to access config without tip"))
+	}
+	if bc.lastConfirmed.Position.Round != bc.configs[0].RoundID() {
+		panic(fmt.Errorf("inconsist config and tip: %d %d",
+			bc.lastConfirmed.Position.Round, bc.configs[0].RoundID()))
+	}
+	return bc.configs[0]
+}
+
+func (bc *blockChain) confirmBlock(b *types.Block) {
+	if bc.lastConfirmed != nil &&
+		bc.lastConfirmed.Position.Height+1 != b.Position.Height {
+		panic(fmt.Errorf("confirmed blocks not continuous in height: %s %s",
+			bc.lastConfirmed, b))
+	}
+	bc.logger.Debug("Calling Application.BlockConfirmed", "block", b)
+	bc.app.BlockConfirmed(*b)
+	bc.lastConfirmed = b
+	bc.confirmedBlocks = append(bc.confirmedBlocks, b)
+	bc.purgeConfig()
+}
+
+func (bc *blockChain) setRandomnessFromPending(b *types.Block) bool {
+	if r, exist := bc.pendingRandomnesses[b.Position]; exist {
+		b.Randomness = r
+		delete(bc.pendingRandomnesses, b.Position)
+		return true
+	}
+	return false
+}
+
+func (bc *blockChain) processAgreementResult(result *types.AgreementResult) error {
+	if result.Position.Round < DKGDelayRound {
+		return nil
+	}
+	if !result.Position.Newer(bc.lastPosition) {
+		return ErrSkipButNoError
+	}
+	ok, err := bc.verifyRandomness(
+		result.BlockHash, result.Position.Round, result.Randomness)
+	if err != nil {
+		return err
+	}
+	if !ok {
+		return ErrIncorrectAgreementResult
+	}
+	bc.lock.Lock()
+	defer bc.lock.Unlock()
+	if !result.Position.Newer(bc.lastDelivered.Position) {
+		return nil
+	}
+	bc.pendingRandomnesses[result.Position] = result.Randomness
+	bc.lastPosition = bc.lastDelivered.Position
+	return nil
+}
+
+func (bc *blockChain) addBlockRandomness(pos types.Position, rand []byte) {
+	if pos.Round < DKGDelayRound {
+		return
+	}
+	bc.lock.Lock()
+	defer bc.lock.Unlock()
+	if !pos.Newer(bc.lastDelivered.Position) {
+		return
+	}
+	bc.pendingRandomnesses[pos] = rand
+}