# 6.3 Fast Probabilistic Consensus

## 6.3.1 Introduction​

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.

### 6.3.2.1 FPC Parameters​

Table 6.3.1 gives a list of all parameters required for FPC.

Table 6.3.1: Parameters Required for FPC.

NameTypeDescription
TOTAL_ROUNDS_FINALIZATIONintegerNumber of consecutive rounds before FPC auto-terminates
TOTAL_ROUNDS_ENDING_THRESHOLDintegerNumber of consecutive rounds with non-random threshold
FIRST_ROUND_THRESHOLDdoubleThreshold of the proportion of opinions in the first round
SUBSEQUENT_LOWER_THRESHOLDdoubleLower random threshold bound in subsequent rounds
SUBSEQUENT_UPPER_THRESHOLDdoubleUpper random threshold bound in subsequent rounds
ENDING_THRESHOLDdoubleThreshold for termination phase
DRNG_WAITING_TIMEdurationMaximal waiting time (in seconds) to receive dRNG number
MAX_ROUNDintegerMaximum number of rounds before querying stops
QUERY_SIZEintegerQuorum size, number of nodes that are queried
ROUND_LENGTHdoubleDuration (in seconds) of a round
TIME_OUTdurationMaximal waiting time (in seconds) to receive answers for FPC queries
MIN_MANA_PROPORTIONdoubleMinimal amount of mana of received answers that allow to update opinion. If this amount is not reached the current round is not counted.
MAX_SAMPLE_SIZEintegerMaximal size of sample.

The proposed values of the parameters are (Table 6.3.2):

Table 6.3.2: FPC Parameter Default Values.

ParameterValue
TOTAL_ROUNDS_FINALIZATION10
TOTAL_ROUNDS_ENDING_THRESHOLD3
FIRST_ROUND_THRESHOLD0.67
SUBSEQUENT_LOWER_THRESHOLD0.50
SUBSEQUENT_UPPER_THRESHOLD0.67
ENDING_THRESHOLD0.50
DRNG_WAITING_TIME0.20
MAX_ROUND100
 QUERY_SIZE21
ROUND_LENGTH10
TIME_OUT6.5
MIN_MANA_PROPORTION0.50
MAX_SAMPLE_SIZE100

### 6.3.2.2 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.

NameTypeDescription
nodeListlist of nodeIDsList of known nodes
consensusManaListlist of nodeIDsList of active consensus mana of known nodes
ownManadoubleActive consensus mana of ownNode
rndoubleRandom number provided by dRNG module
rnCycledoubleRandom number instance
queryListlist of nodeIDsList of nodes to query
queryMaxintegerMaximal number of queries per round
opinionQuerylist of OpinionsList of opinions of nodes in queryList, non-replies are encoded with NA
objectIDslist of objectIDsList of objectIDs that are under vote

Note that 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 time.

For each 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.

NameTypeDescription
opinionnulled booleanOpinion of the eligibility the objectID; TRUE corresponds to LIKE and FALSE to DISLIKE
cntintegerCounter of the number of consecutive rounds with unchanged opinion
queryStatusbooleanStatus if actively querying
answerStatusbooleanTRUE if answering queries, otherwise FALSE
roundintegerCounter for the number of rounds in FPC
reachedMaxRoundbooleanIndicator whether protocol reached MAX_ROUND before auto-termination, default value FALSE

### 6.3.2.3 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 opinion on objectID, see Section 6.2 Opinion Setting. In particular, the variables queryStatus and answerStatus must be affected using the functions QueryStatus and AnswerStatus. 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 ROUND_LENGTH.

1. 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.
2. After TIME_OUT the node must calculate the proportion of the LIKEs in the received opinions.
3. 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_THRESHOLD while 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_LOWER_THRESHOLD+ 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 cnt must 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_PROPORTION of the total mana of the queried nodes, the round is not counted, i.e., neither opinion nor cnt are changed.
4. This continues until cnt=TOTAL_ROUNDS_FINALIZATION-TOTAL_ROUNDS_ENDING_THRESHOLD. FPC then enters in the "termination phase" and continues for TOTAL_ROUNDS_ENDING_THRESHOLD rounds using the ENDING_THRESHOLD instead 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 cnt=TOTAL_ROUNDS_ENDING_THRESHOLD or cnt=reachedMaxRound. In case that cnt=reachedMaxRound a node must set the final opinion to DISLIKE.
5. Once FPC terminates (for the given objectID) a node must update the metadata opinionField of objectID with the outcome of FPC as opinion and level=2.
6. A node must continue to respond to queries as long as AnswerStatus(type, objectID)=TRUE, where type is the type of the objectID. If AnswerStatus(type, objectID)=FALSE the variable answerStatus must 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 time.

### 6.3.2.4 FPC Pseudocode Description​

The following presents some pseudo-code for a better understanding of the details of the FPC protocol.

The function GetRN(a, b, time) retrieves a uniform random number between a and b from the dRNG module of a given time time. If the dRNG is not retrieved in time a node must use (SUBSEQUENT_LOWER_THRESHOLD SUBSEQUENT_UPPER_THRESHOLD)/2 instead.

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.

#### GetSample​

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)RETURN queryList

The function 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 manaList[nodeID].

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.

#### QueryRequest​

NameTypeDescription
Versionuint8The message version. The schema specified in this RFC is for version 1 only.
Tx countuint8The number of TransactionIDs.
TransactionIDs Tx count
TransactionID, ordered by hash ASC
NameTypeDescription
TransactionIDByteArray[32]The ID of the transaction.
Msg countuint8The number of MessageIDs.
MessageIDs Msg count
MessageID, ordered by hash ASC
NameTypeDescription
MessageIDByteArray[32]The ID of the message.

The respond to a QueryRequest must take follow the following form

#### QueryResponse​

NameTypeDescription
Versionuint8The message version. The schema specified in this RFC is for version 1 only.
Obj countuint8The number of objectIDs. Must equal to  Tx count + Msg count of the received QueryRequest
Opinions Obj count
ObjectIDs, in the same order as in received QueryRequest
NameTypeDescription
OpinionByte The opinion on objectID.

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 opinionField is NULL the node must respond with NULL.

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 objectIDs. A node shall only respond to queries if all included objectsID have status answerQuery=TRUE.

#### GetOpinion​

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 messagesWAIT 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] = NARETURN (opinionQuery)

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 cnt > TOTAL_ROUNDS_FINALIZATION-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 queryList and opinionQuery obtained by the functions GetSample and GetOpinion. The variable opinion describes the current opinion on objectID.

#### OpinionUpdate​

This function updates the opinion of a node on objectID.

FUNCTION opinion = OpinionUpdate(objectID, opinion, queryList, opinionQuery, round)manaList = GetActiveConsensusMana(timeObjectID)answerMana = ownManaqueriedManaetaStar = 0FOR node in queryList    queriedMana += manaList[node]    IF opinionQuery[node, objectID] != NA        answerMana += manaList[node]    IF  opinionQuery[node, objectID] = LIKE            etaStar++IF answerMana <= MIN_MANA_PROPORTION * queriedMana    opinionNew = opinion # ELSE     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         WAIT DRNG_WAITING_TIME        threshold = getRN(SUBSEQUENT_LOWER_THRESHOLD, SUBSEQUENT_UPPER_THRESHOLD, CurrentTime)          IF threshold = NIL            threshold = (SUBSEQUENT_LOWER_THRESHOLD + SUBSEQUENT_UPPER_THRESHOLD)/2    ELSE         threshold = ENDING_THRESHOLD    IF eta < threshold        opinionNew = DISLIKE    ELSE        opinionNew = LIKERETURN opinioNew

#### MainFPC​

This function describes the FPC for one objectID. It is triggered once queryStatus of an object is set to TRUE.

FUNCTION opinion = MainFPC(objectId, queryStatus)IF queryStatus = TRUE      opinion = GetInitialOpinion(objectID)    cnt = 0}WAIT UNTIL CurrentTime/ROUND_LENGTH IS INTEGERround = 1 WHILE queryStatus = TRUE    queryList = GetSample(nodeList, manaList)    opinionQuery = GetOpinion(objectID, queryList)     opinionNew = OpinionUpdate(objectID, opinion, queryList, opinionQuery, round)    IF opinion = opinionNew         cnt++    ELSE         cnt=1    opinion = opinionNew    round++    IF cnt = TOTAL_ROUNDS_FINALIZATION         queryStatus = FALSE    IF round >= MAX_ROUND         queryStatus = FALSE        opinion = 1RETURN opinion

# 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.