path: root/core/blocklattice.go

// 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"
)

// Errors for sanity check error.
var (
    ErrAckingBlockNotExists    = fmt.Errorf("acking block not exists")
    ErrInvalidParentChain      = fmt.Errorf("invalid parent chain")
    ErrDuplicatedAckOnOneChain = fmt.Errorf("duplicated ack on one chain")
    ErrChainStatusCorrupt      = fmt.Errorf("chain status corrupt")
)

// blockLattice is a module for storing blocklattice.
type blockLattice struct {
    // lattice stores chains' blocks and other info.
    chains []*chainStatus

    // blockByHash stores blocks, indexed by block hash.
    blockByHash map[common.Hash]*types.Block

    // shardID caches which shard I belongs to.
    shardID uint32
}

type chainStatus struct {
    // ID keeps the chainID of this chain status.
    ID uint32

    // blocks stores blocks proposed for this chain, sorted by height.
    blocks []*types.Block

    // minHeight keeps minimum height in blocks.
    minHeight uint64

    // nextAck stores the height of next height that should be acked, i.e. last
    // acked height + 1. Initialized to 0.
    // being acked. For example, rb.chains[vid1].nextAck[vid2] - 1 is the last
    // acked height by vid2 acking vid1.
    nextAck []uint64

    // nextOutput is the next output height of block, default to 0.
    nextOutput uint64
}

func (s *chainStatus) getBlockByHeight(height uint64) (b *types.Block) {
    if height < s.minHeight {
        return
    }
    idx := int(height - s.minHeight)
    if idx >= len(s.blocks) {
        return
    }
    b = s.blocks[idx]
    return
}

func (s *chainStatus) addBlock(b *types.Block) error {
    if len(s.blocks) > 0 {
        // Make sure the height of incoming block should be
        // plus one to current latest blocks if exists.
        if s.blocks[len(s.blocks)-1].Position.Height != b.Position.Height-1 {
            return ErrChainStatusCorrupt
        }
    } else {
        if b.Position.Height != 0 {
            return ErrChainStatusCorrupt
        }
    }
    s.blocks = append(s.blocks, b)
    return nil
}

func (s *chainStatus) calcPurgeHeight() (safe uint64, ok bool) {
    // blocks with height less than min(nextOutput, nextAck...)
    // are safe to be purged.
    safe = s.nextOutput
    for _, ackedHeight := range s.nextAck {
        if safe > ackedHeight {
            safe = ackedHeight
        }
    }
    // Both 'nextOutput' and 'nextAck' represents some block to be
    // outputed/acked. To find a block already outputed/acked, the height
    // needs to be minus 1.
    if safe == 0 {
        // Avoid underflow.
        return
    }
    safe--
    if safe < s.minHeight {
        return
    }
    ok = true
    return
}

// purge blocks if they are safe to be deleted from working set.
func (s *chainStatus) purge() (purged common.Hashes) {
    safe, ok := s.calcPurgeHeight()
    if !ok {
        return
    }
    newMinIndex := safe - s.minHeight + 1
    for _, b := range s.blocks[:newMinIndex] {
        purged = append(purged, b.Hash)
    }
    s.blocks = s.blocks[newMinIndex:]
    s.minHeight = safe + 1
    return
}

// nextPosition returns a valid position for new block in this chain.
func (s *chainStatus) nextPosition(shardID uint32) types.Position {
    return types.Position{
        ShardID: shardID,
        ChainID: s.ID,
        Height:  s.minHeight + uint64(len(s.blocks)),
    }
}

// newBlockLattice creates a new blockLattice struct.
func newBlockLattice(shardID, chainNum uint32) (bl *blockLattice) {
    bl = &blockLattice{
        shardID:     shardID,
        chains:      make([]*chainStatus, chainNum),
        blockByHash: make(map[common.Hash]*types.Block),
    }
    for i := range bl.chains {
        bl.chains[i] = &chainStatus{
            ID:      uint32(i),
            blocks:  []*types.Block{},
            nextAck: make([]uint64, chainNum),
        }
    }
    return
}

func (bl *blockLattice) sanityCheck(b *types.Block) error {
    // Check if the chain id is valid.
    if b.Position.ChainID >= uint32(len(bl.chains)) {
        return ErrInvalidChainID
    }

    // TODO(mission): Check if its proposer is in validator set somewhere,
    //                blocklattice doesn't have to know about node set.

    // Check if it forks
    if bInLattice := bl.chains[b.Position.ChainID].getBlockByHeight(
        b.Position.Height); bInLattice != nil {

        if b.Hash != bInLattice.Hash {
            return ErrForkBlock
        }
        return ErrAlreadyInLattice
    }
    // TODO(mission): check if fork by loading blocks from DB if the block
    //                doesn't exists because forking is serious.

    // Check if it acks older blocks.
    acksByChainID := make(map[uint32]struct{}, len(bl.chains))
    for _, hash := range b.Acks {
        if bAck, exist := bl.blockByHash[hash]; exist {
            if bAck.Position.Height <
                bl.chains[bAck.Position.ChainID].nextAck[b.Position.ChainID] {
                return ErrDoubleAck
            }
            // Check if ack two blocks on the same chain. This would need
            // to check after we replace map with slice for acks.
            if _, acked := acksByChainID[bAck.Position.ChainID]; acked {
                return ErrDuplicatedAckOnOneChain
            }
            acksByChainID[bAck.Position.ChainID] = struct{}{}
        } else {
            // This error has the same checking effect as areAllAcksInLattice.
            return ErrAckingBlockNotExists
        }
    }

    // Check non-genesis blocks if it acks its parent.
    if b.Position.Height > 0 {
        if !b.IsAcking(b.ParentHash) {
            return ErrNotAckParent
        }
        bParent := bl.blockByHash[b.ParentHash]
        if bParent.Position.ChainID != b.Position.ChainID {
            return ErrInvalidParentChain
        }
        if bParent.Position.Height != b.Position.Height-1 {
            return ErrInvalidBlockHeight
        }
        // Check if its timestamp is valid.
        if !b.Timestamp.After(bParent.Timestamp) {
            return ErrInvalidTimestamp
        }
    }
    return nil
}

// areAllAcksReceived checks if all ack blocks of a block are all in lattice,
// blockLattice would make sure all blocks not acked by some chain would be kept
// in working set.
func (bl *blockLattice) areAllAcksInLattice(b *types.Block) bool {
    for _, h := range b.Acks {
        bAck, exist := bl.blockByHash[h]
        if !exist {
            return false
        }
        if bAckInLattice := bl.chains[bAck.Position.ChainID].getBlockByHeight(
            bAck.Position.Height); bAckInLattice != nil {

            if bAckInLattice.Hash != bAck.Hash {
                panic("areAllAcksInLattice: blockLattice.chains has corrupted")
            }
        } else {
            return false
        }
    }
    return true
}

// addBlock processes block, it does sanity check, inserts block into
// lattice and deletes blocks which will not be used.
func (bl *blockLattice) addBlock(
    block *types.Block) (deliverable []*types.Block, err error) {

    var (
        bAck    *types.Block
        updated bool
    )
    // If a block does not pass sanity check, report error.
    if err = bl.sanityCheck(block); err != nil {
        return
    }
    if err = bl.chains[block.Position.ChainID].addBlock(block); err != nil {
        return
    }
    bl.blockByHash[block.Hash] = block
    // Update nextAcks.
    for _, ack := range block.Acks {
        bAck = bl.blockByHash[ack]
        bl.chains[bAck.Position.ChainID].nextAck[block.Position.ChainID] =
            bAck.Position.Height + 1
    }
    // Extract blocks that deliverable to total ordering.
    // A block is deliverable to total ordering iff:
    //  - All its acking blocks are delivered to total ordering.
    for {
        updated = false
        for _, status := range bl.chains {
            tip := status.getBlockByHeight(status.nextOutput)
            if tip == nil {
                continue
            }
            allAckingBlockDelivered := true
            for _, ack := range tip.Acks {
                bAck, exists := bl.blockByHash[ack]
                if !exists {
                    continue
                }
                if bl.chains[bAck.Position.ChainID].nextOutput >
                    bAck.Position.Height {

                    continue
                }
                // This acked block exists and not delivered yet.
                allAckingBlockDelivered = false
            }
            if allAckingBlockDelivered {
                deliverable = append(deliverable, tip)
                status.nextOutput++
                updated = true
            }
        }
        if !updated {
            break
        }
    }

    // Delete old blocks in "chains" and "blocks" to release memory space.
    //
    // A block is safe to be deleted iff:
    //  - It's delivered to total ordering
    //  - All chains (including its proposing chain) acks some block with
    //    higher height in its proposing chain.
    //
    // This works because blocks of height below this minimum are not going to be
    // acked anymore, the ackings of these blocks are illegal.
    for _, status := range bl.chains {
        for _, h := range status.purge() {
            delete(bl.blockByHash, h)
        }
    }
    return
}

// prepareBlock helps to setup fields of block based on its ProposerID,
// including:
//  - Set 'Acks' and 'Timestamps' for the highest block of each validator not
//    acked by this proposer before.
//  - Set 'ParentHash' and 'Height' from parent block, if we can't find a
//    parent, these fields would be setup like a genesis block.
func (bl *blockLattice) prepareBlock(block *types.Block) {
    // Reset fields to make sure we got these information from parent block.
    block.Position.Height = 0
    block.ParentHash = common.Hash{}
    acks := common.Hashes{}
    for chainID := range bl.chains {
        // find height of the latest block for that validator.
        var (
            curBlock   *types.Block
            nextHeight = bl.chains[chainID].nextAck[block.Position.ChainID]
        )
        for {
            tmpBlock := bl.chains[chainID].getBlockByHeight(nextHeight)
            if tmpBlock == nil {
                break
            }
            curBlock = tmpBlock
            nextHeight++
        }
        if curBlock == nil {
            continue
        }
        acks = append(acks, curBlock.Hash)
        if uint32(chainID) == block.Position.ChainID {
            block.ParentHash = curBlock.Hash
            block.Position.Height = curBlock.Position.Height + 1
        }
    }
    block.Acks = common.NewSortedHashes(acks)
    return
}

// TODO(mission): make more abstraction for this method.
// nextHeight returns the next height for the chain.
func (bl *blockLattice) nextPosition(chainID uint32) types.Position {
    return bl.chains[chainID].nextPosition(bl.shardID)
}