6.3 Fast Probabilistic Consensus
The functionality defined in this part of the specification allows nodes to find consensus on whether a given object is elgible or not. This protocol, called Fast Probabilistic Consensus (FPC), is triggered if the eligibility of an object is uncertain. These objects can be messages or transactions. Please refer to Section 6.1 - Object of Consensus for details on the object of consensus and to Section 6.2 - Opinion Setting for more details how initial opinions on the objects are formed.
Once FPC is triggered every node must establish an initial opinion on the eligibility of the object, as described in Section 6.1. The node must then start to query other nodes about their opinions on the given object and must update its opinion according to the rules specified in this section.
This procedure shall terminate locally if a node has not changed its opinion over a specified period of time or if some maximal amount of rounds is reached.
Unlike other voting-based consensus protocols, FPC uses a sequence of global random thresholds. This randomness makes FPC robust even in Byzantine environments. We refer to FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures, Robustness and efficiency of leaderless probabilistic consensus protocols within Byzantine infrastructures, and Fast Probabilistic Consensus with Weighted Votes for more details on FPC.
The Fast Probabilistic Consensus Protocol specification depends on the following specifications:
6.3.2 FPC Protocol
The FPC protocol attempts to determine consensus on the eligibility of an object
objectID. Every node has an initial opinion
opinion on this object. These opinions are updated in rounds until the protocol terminates using a local stopping rule.
184.108.40.206 FPC Parameters
Table 6.3.1 gives a list of all parameters required for FPC.
Table 6.3.1: Parameters Required for FPC.
|integer||Number of consecutive rounds before FPC auto-terminates|
|integer||Number of consecutive rounds with non-random threshold|
|double||Threshold of the proportion of opinions in the first round|
|double||Lower random threshold bound in subsequent rounds|
|double||Upper random threshold bound in subsequent rounds|
|double||Threshold for termination phase|
|duration||Maximal waiting time (in seconds) to receive dRNG number|
|integer||Maximum number of rounds before querying stops|
|integer||Quorum size, number of nodes that are queried|
|double||Duration (in seconds) of a round|
|duration||Maximal waiting time (in seconds) to receive answers for FPC queries|
|double||Minimal amount of mana of received answers that allow to update opinion. If this amount is not reached the current round is not counted.|
|integer||Maximal size of sample.|
The proposed values of the parameters are (Table 6.3.2):
Table 6.3.2: FPC Parameter Default Values.
220.127.116.11 Local Variables
Local variables are those which may be defined at the application developer's discretion and do not form a mandatory part of the protocol. They are included here to assist in understanding the protocol defined in this section. The kind of information described for these variables must be handled by the node application in some form.
Every node shall keep the following variables (Table 6.3.3):
Table 6.3.3: Required Node Variables.
|list of nodeIDs||List of known nodes|
|list of nodeIDs||List of active consensus mana of known nodes|
|double||Active consensus mana of |
|double||Random number provided by dRNG module|
|double||Random number instance|
|list of nodeIDs||List of nodes to query|
|integer||Maximal number of queries per round|
|list of Opinions||List of opinions of nodes in |
|list of objectIDs||List of objectIDs that are under vote|
consensusManaList is a list of active consensus Mana of all known nodes. As this Mana changes over time this list has to be updated over time. Such an update is expressed with the function
GetActiveConsensusMana(time) that returns the list of active consensus Mana at time
objectID that is under vote a node shall keep the following variables (Table 6.3.4):
Table 6.3.4: Variables Required for objectID Under Vote.
|nulled boolean||Opinion of the eligibility the |
|integer||Counter of the number of consecutive rounds with unchanged opinion|
|boolean||Status if actively querying|
|integer||Counter for the number of rounds in FPC|
|boolean||Indicator whether protocol reached |
18.104.22.168 FPC Protocol Description
FPC Protocol Operation for One Object ID
This section describes how FPC works for one
objectID. Once FPC is triggered on the eligibility of the object
objectID a node establishes an initial opinion
objectID, see Section 6.2 Opinion Setting. In particular, the variables
answerStatus must be affected using the functions
The exchange and update of opinions must be done in rounds of length
ROUND_LENGTH. Rounds end and start at times (in seconds) that are multiple of
- At the beginning of each round a node must select a random sample of the other nodes and either send a query request or check if the sampled nodes published their opinions on the Tangle.
TIME_OUTthe node must calculate the proportion of the
LIKEs in the received opinions.
- At the end of the round it must set a threshold to confirm or modify its own opinion. In the first round this threshold is
FIRST_ROUND_THRESHOLDwhile in the subsequent rounds a node must retrieve a random threshold from the dRNG. If the random threshold from the dRNG is not available a node must use (
SUBSEQUENT_UPPER_THRESHOLD)/2 as threshold. If the proportion is below this obtained threshold it must set its opinion to
DISLIKE, otherwise it must set its opinion to
LIKE. In the case that the opinion did not change, the variable
cntmust be incremented by 1, otherwise it must be set to 0. If a node did not receive enough answers, i.e., the proportion of mana of the received opinions is less than
MIN_MANA_PROPORTIONof the total mana of the queried nodes, the round is not counted, i.e., neither opinion nor
- This continues until
TOTAL_ROUNDS_ENDING_THRESHOLD. FPC then enters in the "termination phase" and continues for
TOTAL_ROUNDS_ENDING_THRESHOLDrounds using the
ENDING_THRESHOLDinstead of the random threshold. If during this phase a node changes its opinion it must set
cnt=0 and use the random threshold again. The node shall stop querying if
reachedMaxRound. In case that
reachedMaxRounda node must set the final opinion to
- Once FPC terminates (for the given
objectID) a node must update the metadata
objectIDwith the outcome of FPC as
- A node must continue to respond to queries as long as
AnswerStatus(type, objectID)=TRUE, where
typeis the type of the
AnswerStatus(type, objectID)=FALSEthe variable
answerStatusmust be updated accordingly.
High consensus Mana nodes will be queried more often than nodes with low consensus Mana, since the sampling using consensus Mana as weights. Every node is given the possibility to publish their opinions in a statement on the Tangle. These messages are called FPC statements. Nodes who decide to issue FPC statements may close the port reserved for FPC queries. A close port can therefore be an indication that a node decided to disseminate its opinions through statements. Every node shall keep a list of nodes that are not answering direct queries but publish their opinions on the Tangle. If a node issues two or more conflicting FPC statements in a round, every other node shall not take these messages into account, i.e., they do not count for the Mana of received opinions neither are used for the calculation of the proportion.
FPC Protocol Operation for Multiple Object IDs
It is possible that there are more than one object to vote on. In this case, a node shall sample once per round and obtain the opinions for all objects from this one sample. Malicious or faulty nodes may not respond in a consistent way. In particular, in the case of a double-spending, a malicious node may respond
LIKE for two or more conflicting objects. These malicious messages shall be filtered after having received the responses of the queries. Therefore, upon receival of the opinions, a node shall check for every sampled node if its answers are consistent, i.e., all liked objects must form a valid ledger state. Nodes that replied inconsistently shall be filtered out and their answer shall be considered as not received, i.e., they do not count for the Mana of received opinions neither are used for the calculation of the proportion.
Note that since consensus Mana changes over time, FPC may use different consensus Mana values for different
objectIDs that are voted on at the same time. For an
objectID, FPC must use the active consensus Mana of epoch
Epoch X-2, where
Epoch X contains the timestamp of the
objectID. We refer to Section 5.3 - Mana for the specification of active consensus Mana. We use a generic function
GetActiveConsensusMana(time) that retrieves the active consensus Mana with respect to a given timestamp
22.214.171.124 FPC Pseudocode Description
The following presents some pseudo-code for a better understanding of the details of the FPC protocol.
GetRN(a, b, time) retrieves a uniform random number between a and b from the dRNG module of a given time
If the dRNG is not retrieved in time a node must use (
In each round a node must query a random sample of other nodes. The random sample is obtained using weighted (by active consensus Mana) sampling with replacement until
QUERY_SIZE distinct elements are chosen, or until a maximum sample size of
MAX_SAMPLE_SIZE is reached.
This function chooses a sample of nodeIDs for FPC queries.
FUNCTION queryList = GetSample(nodeList, manaList)
queryList = 
WHILE (queryList does not contain QUERY_SIZE different elements)
newSample = SAMPLE(nodeList, weight=manaList)
queryList = APPEND(queryList, newSample)
SAMPLE(nodeList, weight=manaList) chooses a random element from
nodeList with weights corresponding to their Mana, i.e., the probability that a
nodeID is chosen is proportional to
Once the list
queryList of nodes to query is chosen a node must obtain their opinions about the objects under voting. As there are two possibilities for nodes to communicate their opinions, via direct answers or via FPC statements, a node shall keep information on this behavior up to date. The message layout of the FPC statements is specified in Section 2.3 - Standard Payloads Layout.
At the beginning of each round every node must prepare a query and send it to those nodes in
queryList that replies directly (i.e., do not publish FPC statements).
The queries must follow the layout that follows.
|Version||uint8||The message version. The schema specified in this RFC is for version 1 only.|
|Tx count||uint8||The number of TransactionIDs.|
TransactionID, ordered by hash ASC
|Msg count||uint8||The number of MessageIDs.|
MessageID, ordered by hash ASC
The respond to a QueryRequest must take follow the following form
|Version||uint8||The message version. The schema specified in this RFC is for version 1 only.|
|Obj count||uint8||The number of objectIDs. Must equal to |
ObjectIDs, in the same order as in received QueryRequest
In the case that a certain
objectID is unknwon to the node, it must respond with
NULL. If the
objectID is currently treated by FPC a node must respond with the current opinion, otherwise, retrieve the
opinion from the
opinionField of the
objectID. If the
NULL the node must respond with
Note that since the order of the opinions in
QueryResponse is important a node may have to produce different messages QueryResponse for different querying nodes. QueryRequest and QueryResponse must be signed by the sending node. The communication channel for these messages is specified in the field "services" in the DiscoveryRequest. We write
respond[node, objectIDs] for the respond, per direct QueryResponse or FPC statement, of the
node on the
A node shall only respond to queries if all included
objectsID have status
This function sends queries to all nodes of
queryList and obtains their opinion either through QueryResponse messages of from FPC statements on the Tangle.
FUNCTION opinionQuery = GetOpinion(objectIDs, queryList)
SEND QueryRequest messages
WAIT UNTIL TIME_OUT
FOR (node IN queryList)
IF (node replied)
opinionQuery[node, objectIDs] = respond[node, objectIDs]
ELSE IF (node publishes on Tangle)
opinionQuery[node, objectIDs] = GetOpinionFromTangle[node, objectID]
ELSE opinionQuery[node, objectIDs] = NA
A node must receive a sufficient amount of replies to validate a given round; otherwise the ongoing FPC round is skipped. More precisely, the consensus Mana of the received opinions must be larger than
MIN_MANA_PROPORTION times the sum of the consensus Mana of the sampled nodes.
Once a node receives a FPC query it must prepare a response message as specified above, and shall sent the response as soon as possible. If a node decides to publish its opinions on the Tangle, it must create a so-called FPC statement message and issue it on the Tangle at the beginning of each round.
At the end of each round, i.e., after the
TIME_OUT expires, a node must update its opinion if
CheckQuerySuccessful is TRUE. The node must calculate the proportion of the
LIKEs in the obtained opinions and compare it to a certain threshold. The value of the threshold depends on the phase FPC is in. In the first round, a node must use
FIRST_ROUND_THRESHOLD as a threshold, while in the subsequent rounds the node must use a random threshold obtained by
GetRN(). Moreover, if
TOTAL_ROUNDS_ENDING_THRESHOLD the node must use
ENDING_THRESHOLD for the threshold.
The following pseudo-code describes the update of the opinion of one given
objectID. It uses
opinionQuery obtained by the functions
GetOpinion. The variable
opinion describes the current opinion on
This function updates the opinion of a node on
FUNCTION opinion = OpinionUpdate(objectID, opinion, queryList, opinionQuery, round)
manaList = GetActiveConsensusMana(timeObjectID)
answerMana = ownMana
etaStar = 0
FOR node in queryList
queriedMana += manaList[node]
IF opinionQuery[node, objectID] != NA
answerMana += manaList[node]
IF opinionQuery[node, objectID] = LIKE
IF answerMana <= MIN_MANA_PROPORTION * queriedMana
opinionNew = opinion #
eta = etaStar / LENGTH(queryList)
IF opinion = LIKE
eta = (ownMana + etaStar*(answerMana-ownMana))/answerMana
ELSE IF opinion = DISLIKE
eta = (etaStar*(answerMana-ownMana))/answerMana
WAIT UNTIL CurrentTime/ROUND_LENGTH IS INTEGER
IF round = 1
threshold = FIRST_ROUND_THRESHOLD
ELSE IF round <= TOTAL_ROUNDS_FINALIZATION-TOTAL_ROUNDS_ENDING_THRESHOLD
threshold = getRN(SUBSEQUENT_LOWER_THRESHOLD, SUBSEQUENT_UPPER_THRESHOLD, CurrentTime)
IF threshold = NIL
threshold = (SUBSEQUENT_LOWER_THRESHOLD + SUBSEQUENT_UPPER_THRESHOLD)/2
threshold = ENDING_THRESHOLD
IF eta < threshold
opinionNew = DISLIKE
opinionNew = LIKE
This function describes the FPC for one
objectID. It is triggered once
queryStatus of an object is set to
FUNCTION opinion = MainFPC(objectId, queryStatus)
IF queryStatus = TRUE
opinion = GetInitialOpinion(objectID)
cnt = 0
WAIT UNTIL CurrentTime/ROUND_LENGTH IS INTEGER
round = 1
WHILE queryStatus = TRUE
queryList = GetSample(nodeList, manaList)
opinionQuery = GetOpinion(objectID, queryList)
opinionNew = OpinionUpdate(objectID, opinion, queryList, opinionQuery, round)
IF opinion = opinionNew
opinion = opinionNew
IF cnt = TOTAL_ROUNDS_FINALIZATION
queryStatus = FALSE
IF round >= MAX_ROUND
queryStatus = FALSE
opinion = 1
6.3.3 Optimizations Suggestions
The design given above exemplifies all the mandatory elements of the FPC protocol.
There are several possible ways to optimize the performance of FPC. For example:
- FPC possibly exposes the public IP adresses of all the IOTA nodes. This can be limited by publishing statements on Tangle. However, if all nodes decide to publish their statements this may have a negative effect on the scalability of the protocol. Please refer to Fast Probabilistic Consensus with Weighted Votes for more discussions on how to optimize the message overhead.
- Monotonicity and consistency rules may be applied to reduce the sizes of the messages.
- The choice of the FPC parameters could be optimized. The optimal choice depends on the actual mana distribution and network latency.