Candidate Set Protocol B

protocol_b.md

Notations:

• Hash function H(.): hash function that may include signature as security requires
• Transaction t: a value submitted by a client of the FBA network that can be independently validated by each node.
• Transaction Set s^v: a set of transactions submitted by clients to node v.
• Node block b^v: of the form <s^v, H(b^v_prev)> a transaction set and a reference to a previous node block
• Master block B: of the form <s^0, s^1, s^3, ..., s^n> a set of node blocks (at most one per node)

State:

Each node v maintains:

• s^v_current: the current transaction set, to which any transaction submitted by a client is added.
• b^v_last: the lastest node block that got committed in a master block for this node
• B^v_last: the list of last committed node blocks for each known node in the network
• b^v_pending: the pending node block for node v
• B^v_candidate: the candidate master block for node v

Protocol:

Each time a node receives a client transactions:

• it appends it to s^v_current

Each time a node v sees a master block B externalised:

• it atomically updates:
  • for each b^y in B, update b^y in B^v_last
  • if b^v_pending is in B^v_last:
    • b^v_last = b^v_pending
    • b^v_pending = <s^v_current, H(b^v_last)>
    • s^v_current = {}
  • if b^v_pending is not in B^v_last but b^v_pending is incompatible with B^v_last
    • b^v_pending is updated by removing incompatible transactions
  • if b^v_pending is not in B^v_last but is still compatible
    • b^v_pending is unchanged
  • all committed or incompatible node blocks are removed from B^v_candidate
  • if b^v_pending was updated, it is updated in B^v_candidate
• if b^v_pending was updated, it pushes it to all the nodes within its quorums

Each time a node v receives a candidate node block b^y_pending:

• it updates it in B^v_candidate only if b^y_pending is compatible with its local B^v_last
• if b^y_pending was previously unkown, it pushes b^y_pending to all the nodes within its quorums

The last thing we need is an heuristic to trigger the consensus protocol. We could use a delay after externalising a value based on the order of the hash of the node blocks in B^v_last as an example. After externalizing each node order B^v_last by H(b^v) and infer its position there p. It then attempts to prepare ballot <next_master_block_idx, B^v_candidate> after (k*|B_last|+p)*D for all k where D is a fixed configurable delay (let say 1s).

Notes:

• Really, any node v with B^v_candidate non-empty could trigger the consensus protocol as the network would make progress if consensus is reached even with a small B^v_candidate.
• The dependence of node blocks on previous node-blocks of the same node instead of master blocks allows for a node-blocks to propagate through the network and eventually get picked in a master block even if that propagation is "slow" and spans multiple externalisation of master blocks:

B5: b^v0_0        b^v2_0 
B4:   |             |    b^v3_0 
B3:   |    b^v1_0   |      |
B2:   |      |    b^v2_0 b^v3_0 
B1:   |    b^v1_0   |    
B0: b^v0_0        b^v2_0