6.2 Opinion Setting
FPC is a binary voting protocol which takes a series of initial boolean values, and outputs a final value: see Section 6.3 - Fast Probabilistic Consensus. This specification describes how to set this initial Boolean value. Specification 6.1 - Object of Consensus describes how FPC interacts with other modules in the protocol, specifically how the functions
AnswerStatus react to the metadata
opinionField. Moreover, the FPC specification, Section 6.3 - Fast Probabilistic Consensus, describes how the
opinionField is updated when FPC terminates.
We need to describe how to set the initial opinion and how to trigger FPC voting. Specifically, we need to describe how the metadata
opinionField is initially set. Since the outcome of FPC respects a supermajority of initial opinions, it is important that the initial opinion is set correctly. For example, if 90% of nodes (weighted by active consensus mana) initially want to accept a transaction, the transaction is accepted with very high probablity.
Recall from specification Section 6.1 - Object of Consensus, that
opinionField consists of fields,
opinion which is a boolean,
level which is either 1,2, or 3, and
timeFormed which is a time. In this specification, we describe how these three fields are set for both messages and transactions.
In this specification, we describe how the Opinion Setter, see Section 2.4 - Data Flow, initially sets
opinionField metadata for every object being voted upon. Specifically, the opinion setter writes:
- The initial opinion, i.e. the initial boolean value.
- The level of knowledge which dictates when FPC will be triggered.
- The time the opinion was formed.
See Section 6.1 - Object of Consensus for a detailed explanation of these fields.
As discussed in Section 6.1 - Object of Consensus, FPC can potentially vote on two main object types:
- transactions in order to resolve conflicts
- timestamps in order to judge timestamps
We split this specification into two main sections: the first dealing with setting the opinion on messages and their timestamps, and the second on setting the opinion on transactions.
With regards to timestamps, we vote on whether or not the timestamp is "too old" when the message arrives to the node. As with voting on transactions, we can reset this opinion using the approval weight even if the node is out of sync.
We judge transactions based on the FCoB rule, which stands for Fast Consensus of Barcelona, in honor of the research summit where the rule was first defined. A transaction
X satisfied the FCoB rule if the node has not received any transactions conflicting with
C is the FCoB parameter. Recall from Section 6.4 - Finalization that two transactions conflict if they consume the same UTXO outputs.
Intuitively, the FCoB rule only accepts a transaction if it has arrived significantly before any other conflict. The FCoB rule guarantees that if one transaction is liked by a significant number of nodes (weighted by consensus mana), that all other conflicting transactions will be initially disliked by a supermajority of nodes, and thus rejected by FPC, guaranteeing that no two conflicting messages will be approved by FPC.
This part of the specification depends on the following specifications:
- Section 4.2 - Timestamps
- Section 5.2 - Ledger State
- Section 6.1 - Object of Consensus
- Section 6.4 - Finalization
184.108.40.206 Parameters and Lists
|duration||Gratuitous network delay estimate; set to 15 seconds|
|duration||Time window, set to 1 minute. Require W>2DLARGE|
|duration||Small estimated network delay, set to 5 seconds|
The timestamp defines the time when the message was created. Voting on timestamps ensures that nodes are issuing messages with correct timestamps, where correct means that the offset with current time is lower than a certain parameter
W. This time window is large to account for the network delay. In order to have consensus on the accuracy of the timestamp, and hence the eligibility of the message, we use FPC voting, along with the levels of knowledge.
Clearly, in order to have a correct perception of the timestamp quality, we assume the node is in sync (see section Not in Sync otherwise).
Voting on timestamps should not occur for every message. Specifically, only for those that arrive with an offset close to
W, i.e. within
220.127.116.11 Setting the Initial Opinion
In this section, we describe how the
opinionField is set for messages, and how we achieve consensus on the correctness of timestamps.
The opinion of timestamp is stored according to the rules laid out in the Object of Consensus specification. The opinion is set by the module called the
OpinionManager: see Section 2.4 - Data Flow. Refer to the FPC specification to see how the voting actually takes place.
The node shall set
messageID.opinionField=timestampOpinion(messageID), using the function defined below.
The initial opinion and level of knowledge are set according to the following rule:
FUNCTION (bool,level,time) = timestampOpinion(messageID)
time = CurrentTime()
IF messageID.arrivalTime+w >= CurrentTime()
opinion = TRUE
opinion = DISLIKE
IF |messageID.arrivalTime +W - CurrentTime() | >= DLARGE
level = 2
ELSE IF |messageID.arrivalTime +W - CurrentTime() | >= 2*DLARGE
level = 3
level = 1
Recall that the
arrivalTime.messageID is the time that the message was received by the node: see Section 2.2 - Message Layout.
The initial opinion is set based on the question "did the transaction arrive before
currentTime - W?". The level of knowledge is then set by the margin as a factor of the delay time. Specifically, under the assumption that all messages are delivered to all nodes within time
DLARGE after the arrive (with high probability), then:
|arrivalTime +W - currentTime | < DLARGE, then the node can make any conclusions about the arrival times of the message, and hence it has only level of knowledge 1.
- If one node has
|arrivalTime +W - currentTime | >= DLARGE, then all nodes must have the same opinion, and hence that node has level of knowledge at least 2.
- If one node has
|arrivalTime +W - currentTime | >= 2*DLARGE, then all nodes must have
|arrivalTime +W - currentTime | => DLARGEguaranteeing level of knowledge 3.
For example, let us set
D to 1 minute and 15 seconds respectively. Let's assume that the current time is 12:00:00 and we have to evaluate a new message with timestamp set at 11:59:45. Since 11:59:45 +1 minute>12:00:00, the node will set the opinion to
LIKE. Moreover, since |11:59:45+1 minute-12:00:00| is greater than 15 seconds, and also grater than 2*15 seconds, the node will set the level of knowledge for this opinion to 3 (i.e., the supermajority of the network should already have the same opinion).
Consider now a new message with timestamp 11:59:10. Since 11:59:10+1 minute>12:00:00, the node will set the opinion to
TRUE. However, since |11:59:10+1 minute-12:00:00| is lower than 15 seconds, the node will set the level of knowledge for to 1, meaning that this message will be voted upon by FPC.
In general, timestamps with level of knowledge 1 will be input into FPC, that will eventually trigger the
finalized event, after which we may set a message as eligible or as discarded, depending on the outcome. If instead, the timestamp the node is considering has already level of knowledge larger or equal than 2, the node does not need to vote, but has to reply to queries. Either it is eligible (marked as liked) or it is marked as disliked. If the timestamp has level of knowledge 3, the node does not reply to FPC queries.
With high probability, we can be sure that for any time
t, no node can issue a message with timestamp
t + W + 2*DLARGE, because after this time, the message would be considered to be bad with level of knowledge 3. Thus, assuming the node is in sync, after approximately 1.5 minutes, the number of messages of a particular timestamp cannot be altered.
6.2.3 Transactions and FCoB
In this section, we discuss how to set the
opinionField on transactions through the so-called FCoB rule. Recall that a transaction
X satisfies the FCoB rule if the node has not received any transactions conflicting with
18.104.22.168 FCoB function
We now define the function
FCOB which decides the opinion of the transaction. When setting the opinion, the node simply sets
FUNCTION (bool,level,time) = FCOB(transactionID)
time = currentTime
IF transactionID IS NOT a conflict
bool = TRUE
IF currentTime <= transactionID.arrivalTime + C + DSMALL
level = 1
ELSE IF currentTime <= transactionID.arrivalTime + C + 2 * DSMALL
level = 2
level = 3
FOR x IN conflict with transactionID
IF x.arrivalTime >= transactionID.arrivalTime + C OR ( x.opinionField.opinion == FALSE AND x.opinionField.level == 2 OR 3)
bool = TRUE
level = 1
conflictTime= MIN(x.arrivalTime FORALL x conflicting with transactionID)
IF transaction.arrivalTime + C <= conflictTime
bool = TRUE
bool = FALSE
If |transaction.arrivalTime + C - conflictTime| <= DSMALL
level = 1
ELSE IF |transaction.arrivalTime + C - conflictTime| <= 2DSMALL
level = 2
level = 3
We now will explain the logical behind this function. There are three cases which are treated:
- No conflicts have been detected
- Conflicts have been detected but have been rejected
- Conflicts have been detected are either pending or have been confirmed
Case 3 is the simplest case: since conflicts have been detected, we set the opinion according to the FCOB rule. Then level is set according to the difference of
transaction.arrivalTime + C and
conflictTime, the oldest arrival time of a conflicting transaction. Essentially, the level measures how many network delays there are between these two values.
In Case 1 is the most common because conflicts will never arrive for most transactions. Without conflicts, the opinion can be only set provisionally since it might change if a conflict arrives later. The opinion is set to true, but the level is set as if a conflict arrived at that time. For example, after
C + DSMALL time has elapsed since arrival time, if a conflict does arrive the opinion will remain true with level at least 2.
Lastly, Case 2 is an important special case of the FCoB rule. To see the need for this modification consider the following example. Suppose someone issues a pair of conflicting transactions where both transactions are rejected by FPC. Then, if someone ever issues a new transaction consuming those funds, FCoB, strictly speaking would reject the new transaction, since it would conflict with a previous transaction. Thus, if a pair of double spends are rejected, the funds would be locked. This is undesirable and impractical behavior: an honest but malfunctioning wallet can issue double spends. Moreover, tracking the locked funds would be onerous.
To prevent the FCoB rule from locking funds, we modify it to the following: a transaction
X satisfied the FCoB rule if all transactions
Y conflicting with
arrivalTime(X)+C has been rejected, i.e. has has opinion false and level 2 or 3. With this rule, any conflicts which are rejected will not affect the opinion on future conflicts. For simplicity case, all transactions falling under this case are treated as level 1.
22.214.171.124 When to Set the Opinion
The protocol is actually flexible on when the opinion field of a transaction is set. However, the node must do the following.
- The opinion of a transaction must be set after it is booked. When the transaction is booked, the node searches for conflicts, and if a conflict exists the node either creates a new conflict set or else it adds the transaction to an old conflict sets. If the
FCoBfunction is called before the transaction is booked, it will be impossible to tell what conflicts exist.
- The opinion field is
NULLonly if no conflicts have been detected
- Fore very valid
transactionID.opinionFieldis either NULL or "correct" at the times
transactionID.arrivalTime + C + DSMALLand
transactionID.arrivalTime + C + 2DSMALL, i.e. the opinion field would be unchanged if reset at that those two times.
There are a plethora of ways this could be implemented. We give two examples.
First, after a message is booked, its transaction, say
transactionID is added to a timed queue. At
transactionID.arrivalTime + C + DSMall the opinion is set, and then either the transaction is rejected (i.e. bad with level 2 or 3), voted upon (level 1), or goes to tip selection (good level 2). If no conflict has been detected, the transaction (i.e. the transaction is good level 2), the transaction is put in another timed queue. At time
transactionID.arrivalTime + C + 2DSMall the opinion is reset. Note, once a conflict is detected the opinion field would not change, and so only transactions which are not part of conflict sets need to enter the second timed queue.
Second, while a transaction is being booked, conflict detection can immediately trigger setting the opinion field for all the new conflicts. This would include the transaction itself and any members of its conflict set which previously had a
NULL opinion field. This implementation has a few caveats:
- Any transaction with a
NULLopinion field must be treated as a "good" transaction. At any time, the appropriate level of knowledge could be computed by looking at the arrival time.
- Before the monotonically liked flag is set, the transaction must be at least
transactionID.arrivalTime + C + DSMalland have either opinion field
NULLor (good, level 2 or 3).
Although this is an implementation detail, we remark that after a transaction is booked, it is easy to see if a message is a conflict or not. Indeed, when a conflict is detected, a new branch is created, and the ID of that new branch is the same as the
transactionID. Thus a transaction is a conflict if and only if
transactionID = transactionID.branchID. See Section 5.2 - Ledger State.