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:

• 2.3 - Standard Payloads Layout
• 5.3 - Mana
• 6.1 - Object of Consensus
• 6.2 - Opinion Setting
• 6.5 - dRNG

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.

Name	Type	Description
TOTAL_ROUNDS_FINALIZATION	integer	Number of consecutive rounds before FPC auto-terminates
TOTAL_ROUNDS_ENDING_THRESHOLD	integer	Number of consecutive rounds with non-random threshold
FIRST_ROUND_THRESHOLD	double	Threshold of the proportion of opinions in the first round
SUBSEQUENT_LOWER_THRESHOLD	double	Lower random threshold bound in subsequent rounds
SUBSEQUENT_UPPER_THRESHOLD	double	Upper random threshold bound in subsequent rounds
ENDING_THRESHOLD	double	Threshold for termination phase
DRNG_WAITING_TIME	duration	Maximal waiting time (in seconds) to receive dRNG number
MAX_ROUND	integer	Maximum number of rounds before querying stops
QUERY_SIZE	integer	Quorum size, number of nodes that are queried
ROUND_LENGTH	double	Duration (in seconds) of a round
TIME_OUT	duration	Maximal waiting time (in seconds) to receive answers for FPC queries
MIN_MANA_PROPORTION	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.
MAX_SAMPLE_SIZE	integer	Maximal size of sample.

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

Table 6.3.2: FPC Parameter Default Values.

Parameter	Value
TOTAL_ROUNDS_FINALIZATION	10
TOTAL_ROUNDS_ENDING_THRESHOLD	3
FIRST_ROUND_THRESHOLD	0.67
SUBSEQUENT_LOWER_THRESHOLD	0.50
SUBSEQUENT_UPPER_THRESHOLD	0.67
ENDING_THRESHOLD	0.50
DRNG_WAITING_TIME	0.20
MAX_ROUND	100
QUERY_SIZE	21
ROUND_LENGTH	10
TIME_OUT	6.5
MIN_MANA_PROPORTION	0.50
MAX_SAMPLE_SIZE	100

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.

Name	Type	Description
nodeList	list of nodeIDs	List of known nodes
consensusManaList	list of nodeIDs	List of active consensus mana of known nodes
ownMana	double	Active consensus mana of ownNode
rn	double	Random number provided by dRNG module
rnCycle	double	Random number instance
queryList	list of nodeIDs	List of nodes to query
queryMax	integer	Maximal number of queries per round
opinionQuery	list of Opinions	List of opinions of nodes in queryList, non-replies are encoded with NA
objectIDs	list of objectIDs	List 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.

Name	Type	Description
opinion	nulled boolean	Opinion of the eligibility the objectID; TRUE corresponds to LIKE and FALSE to DISLIKE
cnt	integer	Counter of the number of consecutive rounds with unchanged opinion
queryStatus	boolean	Status if actively querying
answerStatus	boolean	TRUE if answering queries, otherwise FALSE
round	integer	Counter for the number of rounds in FPC
reachedMaxRound	boolean	Indicator 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

Name	Type	Description
Version	uint8	The message version. The schema specified in this RFC is for version 1 only.
Tx count	uint8	The number of TransactionIDs.
TransactionIDs Tx count	TransactionID, ordered by hash ASC Name Type Description TransactionID ByteArray[32] The ID of the transaction.
Msg count	uint8	The number of MessageIDs.
MessageIDs Msg count	MessageID, ordered by hash ASC Name Type Description MessageID ByteArray[32] The ID of the message.

The respond to a QueryRequest must take follow the following form

QueryResponse

Name	Type	Description
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 Tx count + Msg count of the received QueryRequest
Opinions Obj count	ObjectIDs, in the same order as in received QueryRequest Name Type Description Opinion Byte 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 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
RETURN (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 = ownMana
queriedMana
etaStar = 0
FOR 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 = LIKE
RETURN 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 INTEGER
round = 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 = 1
RETURN 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.