- 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 nodev
. - 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.
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 nodeB^v_last
: the list of last committed node blocks for each known node in the networkb^v_pending
: the pending node block for nodev
B^v_candidate
: the candidate master block for nodev
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
inB
, updateb^y
inB^v_last
- if
b^v_pending
is inB^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 inB^v_last
butb^v_pending
is incompatible withB^v_last
b^v_pending
is updated by removing incompatible transactions
- if
b^v_pending
is not inB^v_last
but is still compatibleb^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 inB^v_candidate
- for each
- 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 ifb^y_pending
is compatible with its localB^v_last
- if
b^y_pending
was previously unkown, it pushesb^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>
wheren^v
is a random number (between 0 and RAND_MAX) andB^v_ballot = B^v_candidate
for the next master block sloti
- 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)
- it sets
- else it already pledged to abort b^y, nothing to do
- if
- 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)
- it sets
- 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)
- it sets
- if
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.
- Really, any node
v
withB^v_candidate
non-empty could trigger the consensus protocol as the network would make progress if consensus is reached even with a smallB^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