Candidate Set Protocol C

protocol_c.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)

We define B1 < B2 by a total lexicographic order on:

• the number of node-block in each master-block
• the natural order on the hash of each master block.

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:

Node block propagation

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

Master block preparation

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

• It waits for a predefined period (let say 1s, to let B^v_candidate build up)
• It creates a ballot b^v = <n^v,B^v_ballot> where n^v is a random number (between 0 and RAND_MAX) and B^v_ballot = B^v_candidate for the next master block slot i
• It emits PREPARE v i b^v B_c Q(v)

We then use these heuristics for ballot generation:

Whenever a node v receives a PREPARE statement with ballot b^y = <n^y, B^y_ballot> and B^y_ballot is compatible with the knowledge of the node:

• if B^y_ballot < B^v_ballot
  • if n^y > n^v
    • it sets b^v = <n^v + n^y, B^v_ballot>
    • it emits PREPARE v i b^v B_c Q(v)
  • else it already pledged to abort b^y, nothing to do
• if B^y_ballot > B^v_ballot
  • if n^y > n^v
    • it sets b^v = <n^y, B^y_ballot>
    • it emits PREPARE v i b^v B_c Q(v)
  • if n^y < n^v
    • it sets b^v = <n^y + n^v, B^y_ballot>
    • it emits PREPARE v i b^v B_c Q(v)

The idea here is for each node to only make one initial ballot proposition in each round of the consensus protocol, and have the consensus protocol "converge" along the total order on proposed master blocks.

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. That's why we let everynode do so with proper heuristics for ballot generation / convergence.
• 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