Candidate Set Protocol - A

protocol_a.md

Notations:

• 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 a particular node v.
• Node block b^v: of the form <s^v, H(B)> a transaction set and a reference to a master 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)
• Hash funciton H(.): hash function that may include signature as security requires

Definitions:

Master blocks are compatible B1 ~ B2 iif:

• any common node block is equal.
• all node blocks refer the same 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_last: the latest master block committed (as known by this node)
• b^v_pending: the pending node block for this node referencing B_last
• B_candidate: the candidate master block

Protocol:

Each time a node receives a client transactions:

• it appends it to s^v_current

Each time a node sees a master block B committed:

• it atomically updates:
  • B_last = B
  • b^v_pending = <s^v_current U (b^v_pending.s^v - B_last.s^v), H(B_last)>
  • s^v_current = {}
  • B_candidate = < b^v_pending >
• It pushes B_candidate to all the nodes within its quorums

Each time a node receives a candidate master block B_foreign:

• it merges it in B_candidate only if B_candidate ~ B_foreign
• if B_candidate was modified, it is pushed to all the nodes within this node's quorums.

After a predefined timeout the node with the smallest H(b^v) in B_last generates a ballot for the agreement protocol with its current B_candidate. After another timeout if nothing happened, the second smallest H(b^v) generates a new ballot, etc...

Notes:

• Node blocks transmission can be optimized using hash/signature. A node communicates hash of node blocks within master blocks instead of the block itself, but make sure to fetch a local copy of the block before merging a node block within its candidate master block.
• Since a node generates b^v_pending when it learns about B_last, for each mater block B there is at most one b^v_pending generated per node v.
• The condition to trigger ballots ensure that the protocol make progress, but it does not ensure "fairness" among nodes.