VIP-200.md

VIP	Title	Author	Category	Status	CreatedAt
200	Implementation of SURFACE BFT Protocol	Ziheng Zhou ([email protected]) and Zhijie Ren ([email protected])	Core	Draft	2019-08-09

Overview

This proposal outlines the implementation of the Byzantine Fault Tolerance (BFT) protocol described in [1]. The goal is to allow blocks of the Thor blockchain to reach BFT finality.

Specification

Block

The basic idea is to allow blocks to carry extra finality-related messages so that nodes can update their BFT states once they receive the blocks and reach block finality. There are four messages, each of which is a block id, representing the new-view nv, prepare pp, pre-commit pc and commit cm messages, respectively.

type headerBody struct { 
    ...
    nv  *block.Header
    pp  *block.Header
    pc  *block.Header
    cm  *block.Header
}

// Get messages
func (h *Header) NV() *block.Header
func (h *Header) PP() *block.Header
func (h *Header) PC() *block.Header
func (h *Header) CM() *block.Header

Local Finality State

Each node u maintains its own local finality state that can be defined as:

type fState struct {
    nv  *block.Header
    pp  *block.Header
    pc  *block.Header
    cm  *block.Header
    fn  *block.Header
}

where fn refers the latest finalized block.

View

A view is defined as a chain of blocks such that

• They start with block b0,
• Every block's nv message points to b0.

type view interface {
    // Get the id of the first block
    first() *block.Header

    // Method nv checks whether the view contains at least 2f+1 non-duplicate leaders and backers.
    nv() bool

    // Method nv checks whether the view contains at least 2f+1 non-duplicate leaders and backers. It returns false if no. Otherwise, it proceeds to check whether there is no pc value that refers to a block that is on another branch. If yes, it returns true or false otherwise.
    nv1() *block.Header

    // Method pp checks whether there is a pp value such that the number of non-duplicate leaders and backers of the blocks that contain the pp value is equal or larger than 2f+1. It returns nil if no. Otherwise, it proceeds to check whether there is no pc value that refers to a block that is on another branch. If yes, it returns the pp value or nil otherwise.
    pp() *block.Header

    // Method pc checks whether there is a pc value sch that the number of non-duplicate leaders and backers of the blocks that contain the pc value is equal or larger than 2f+1. It returns the pc value if yes or nil otherwise.
    pc() *block.Header

    // Method npc returns the number of blocks in the view s.t. pc == v
    npc(b *block.Header) uint
}

Finality State Update

Define

// Get the view starting from b.NV() to b.
func (r *Repository) GetView(b *block.Header) *view

// Check whether b1 and b2 are on two different branches
func (r *Repository) IfConflict(b1, b2 *thor.Byte32) bool 

Block b is called ready to pre-commit (RTPC) if there exists a view v0 such that the following conditions hold:

1. v0.pp.ID() == b.ID()
2. For any view v1 newer than v0, if v1.nv() == true then
   • v1.first().Timestamp() > v0.first().Timestamp()
   • v1.npc(b) > 0
3. b is newer than the last block committed locally

// rtpc maintains the RTPC block. The block is not necessarily on the canonical view. It is guaranteed that there would be only one block that is RTPC at one time for any honest node.
type RTPC interface { 
    update(b *block.Header, cm *block.Header)
    get() *block.Header
}

Each node maintains the following local variables:

// Local finality state
var s fState

// Info of blocks committed by other nodes, but not yet committed locally
type committedBlockInfo interface {
    update(b *block.Header, cm *block.Header) 
    get() *block.Header
}
var cmInfo committedBlockInfo

// RTPC view
var rtpc *RTPC

// Last block signed either as the leader or a backer by the node
var lastSignedBlock *block.Header
// Whether the signed pc is nullified by 2f+1 nv messages with no pc
var pcSignedExpired bool
// After the node signs a new block either as the leader or a backer, we need to set lastSignedBlock as the signed block and pcSignedExpired = false

// Previously handled last block of the cannoical chain.
var prevBestBlock *block.Header

Given a latest received valid block (not necessarily on the canonical chain)

var b *block.Header

the node updates its finality state and local variables as follows:

isOnCanonicalChain := b.ID() == repo.BestBlock.ID()
v := repo.GetView(b)

/////////////////////////////
// update s.cm
/////////////////////////////
if pc := v.pc(); pc != nil {
    s.cm = pc
    s.pc = nil
}
if cm := cmInfo.update(b, s.cm); cm != nil {
    s.cm = cm
}
if s.fn.Timestamp() < s.cm.Timestamp() {
    s.fn = s.cm
}

/////////////////////////////
// update s.pc
/////////////////////////////
// update RTPC block info
rtpc.update(b, s.cm)

// Check whether the signed pc is nullified so that node can pre-commit other blocks again
if v.nv() && v.npc(lastSignedBlock.PC()) == 0 {
    pcSignedExpired = true
}

if pc := rtpc.get(); pc != nil {
    if !repo.IsConflict(pc, lastSignedBlock.PC()) {
        s.pc = pc
    } else if pcSignedExpired {
        s.pc = pc
    }
}

/////////////////////////////
// unlock s.pc
/////////////////////////////
if s.pc != rtpc.get() {
    s.pc = nil
}

/////////////////////////////
// update s.pp
/////////////////////////////
if isOnCanonicalChain {
    if pp := v.nv1(); pp != nil {
        s.pp = pp
    }
}

/////////////////////////////
// update s.nv
/////////////////////////////
if isOnCanonicalChain {
    if b.NV().Timestamp() > s.nv.Timestamp() {
        s.nv = b.NV()
    } else if b.ParentID() != lastBestBlock.ID()
        s.nv = b
    }

    w := repo.GetView(repo.GetBlock(b.ParentID()))
    if w.nv() {
        s.nv = b
    }
}

/////////////////////////////
// unlock s.pc
/////////////////////////////
if repo.IsConflict(s.nv, s.pp) {
    s.pp = nil
}

References

[1] Ren, Z. and Z. Zhou (2020) SURFACE: A Practical Blockchain Consensus Algorithm for Real-World Networks, arXiv:2002.07565.