We describe how FPCS (Fast Probabilistic Consensus on a Set) can be applied as a metastability breaking mechanism on top of OTV (On Tangle Voting).
We assume an underlying OTV mechanism that attributes AW (Approval Weight) to transactions. A detailed definition of this is not subjet of this description. For instance, it could be standard OTV, or the version where nodes do not attach a second transaction in the past cone of the conflict until it reaches a certain AW threshold.
We assume that there is a dRNG that issues a new common random variable X each \Delta second.
The underlying idea is natural and well illustrated by the standard example of a normal double spend.
In a nutshell, every \Delta seconds we check if there is a clear leader of the double spend. If yes fine, if not we choose one randomly.
Example: double spend
Let us assume that there is a double-spend, tx A and tx A^c and denote by \tau_{i, A} and \tau_{i,A^c} the arrival times of A and A^c at node i. We assume that \tau_{i, A} < \tau_{i,A^c}. At time \tau_{i,A^c} node i realizes the double spend and A, A^c are added to the conflict set with time flags \tau_{i, A} and \tau_{i, A^c}. (For implementation we could also use \tau_{i, A^c} for the time flag of A)
In the background we have the metastability breaker running that is triggered by the arrival of a new dRNG producing uniform random variables in the interval [0,1]. Say at time T a new random number X=X_T arrives. Then, for every transaction B in the conflict set with time flag \tau_{i,B} < X_T -\Delta we do the following. If the approval weight AW_{i,T}(B) of transaction B satisfies
node i must “like” B and “dislike” B^c. Here, we could, for example, choose a=10. Note that this formula is not set in stone, however, one important thing is that the threshold is >50\%.
In case that this is not in line with its current vote, node i may issue a transaction that changes its vote.
If
transaction B must be considered “confirmed” and B and B^c must be removed from the conflict set. Again the precise value of the threshold of 75\% can/should still be adjusted. But it seems reasonable that it is (strictly) larger then the random threshold above.
If neither A or A^c do statisfy this criterion, node i must calculate hash(A,X) and hash(A^c, X) and like the one with the minimal hash. If this results in a change, a node must update the eligible tip set; to those that are in the future cone of the liked transaction.
General case
The conflict set can in general form a more complicated graph. We say two transactions A and B are in conflict if their sets of consumed inputs have nonempty intersection. Or, in other words, if at least one of their inputs is the same. We define a graph with conflictings transactions as vertices and with edges between every pair of vertices/transactions that are in conflict.
The aim is to choose a subset of vertices such that none of them are conflicting (having an edge). Such a set is called an “independent set”. A maximal independent set is an independent set that is not a proper subset of any other independent set.
Every conflicting transaction B of the conflict set is assigned an arrival time \tau_{i,B}.
Now, as above if at time T a new random variable arrives we check for each transaction B with time flag \tau_{i,B} < X_T -\Delta in the conflict set if
If this is satisfied B is “liked” and added to the set W_i.
If W is already a maximal independent set we are done. Otherwise we add transactions following
In words, we add the transaction C with the smallest hash(C,X) such that W \cup \{C\} is still independent. This is continued until W=W_i is a maximal independent set.
Every B in the resulting W that satisfies
is considered “confirmed” and all directly conflicting transaction are “rejected”.
All elements in W_i must be considered as “liked” and the other conflicts as “disliked” and the elgible tip set may have to be updated. More precisely, future cones of “liked” transactions should be eligible for tip selection.
Remarks:
- The parameter \Delta has to be chosen such that transaction have a chance to obtain enough AW. Perhaps around 30s-60s.
- The choice of \Delta has no direct influence on honest txs confirmation time.
- At the current proposal no direct queries are needed. We assume that enough AW can be obtained in \Delta seconds.