Refined FPC - A Resynchronization Proposal

🌌 Research Coordicide
1

From recent discussion we agreed on a model of resynchronization that is similar to on-tangle voting to be used on top of FPC for rare situations where we need to get nodes to correct their opinions.

Some points to be outlined here:

  • This proposal is to be used on top of FPC, this means that on the existence of conflicting realities.
  • Transaction may only be reverted up to a time t_{max}, which is lower than the BelowMaxDepth time.
  • It is based on a two steps system: A trigger (evidence gathering) and a resynchronization (large scale query).

Trigger Step

In this step we gather evidence that the reality we decided on FPC is the wrong one.

  • Consider that we are considering two conflicting realities a and b.

  • Define T(a,t_0,t_1) the percentage of the mana associated with the nodes that issued transactions in the time interval (t_0,t_1] that approved reality a.
    ** If a node issued transactions approving both realities, we consider the most recent sequence number transaction only.
    ** As an example if 10 nodes issued transactions during that time and if 2 of them issued transactions approving reality b, then T(b) will be the mana of the said 2 nodes divided by the mana of all 10 nodes.
    ** It always will hold that T(a)+T(b)\leq 1.

  • The procedure of the Trigger step read as follows:

  1. On the decision about a reality on FPC, the disliked one is added on the disliked buffer. Associated to it we will have a provisory list of nodes that will vouch for that reality, with their Mana values.
  2. After the finalization of FPC at time t, every Delta units of time we will check the mana received from time t, this means that at the k-th attempt we check if
T(b,t,t+k\Delta)- T(a,t,t+k\Delta)>0.5.
  1. If the check is successful in any of the steps, we do a resynchronization step.
  2. Resynchronizations may happen as many time as needed until t_{max} has passed. What means that we can at most do t_{max}/\Delta changes of opinion, and it is increasingly harder to trigger the resynchronization step.

Resynchronization Step

  1. If a trigger happens, we will check if our opinion is against majority of the network.
  2. We query a large number of nodes asking about their opinion on reality a or b.
  3. If a supermajority of the network (i.e. 70%) prefer transaction b, we change our opinion, moving reality a to the disliked buffer and adding reality b to the ledger state.

Critics to the proposal

  • The main critic is that we change our consensus mechanism completely with this, putting a new finalization procedure on top of FPC. For now we call the model with FPC+resynchronization by “Refined FPC”.
  • As we have a second step after FPC, this may give us more room for attack vectors that we need to verify we are safe against. Although as a payoff we become much more resistant to voting/opinion failures.
  • This resynchronization for now if only on the top of FPC problems, other sources of opinion divergence as censor attacks, DDoS and so are not covered by this. Although we theoretically could include them this opens someone to freely do resynchronization for every transaction, what could lead to problems.
  • Last but not the least this is one extra communication procedure on the top of the many we build Coordicide upon, although it is in out plans to study the possible communication overhead this could even so slightly increase the requirements for a node to join the network.
3

With regards to 2, how do you plan on doing this exactly? Are realities named in an objective way?

4

Note that Condition 2:
T(b,t,t+kΔ)−T(a,t,t+kΔ)>0.5
assures that potential switch to the rejected reality occurs only when a significant majority of mana prefers rejected reality.

Although there can be a lot of transactions that are in conflict with a certain transaction from the current reality, there can be the only one which corresponds to the reality which satisfies the condition “2”. Thus it might be reasonable to perform first the loop which identifies the problematic realities and only then we

Then the following algorithm might be used:

functions:

MANA_associated_with_tx(tx)
MANA_associated_with_reality(reality)
timestamp(tx)
find_conflicting_tx_with_max_MANA(reality1,reality2,MANA)
Resynch_query(tx1,tx2)

Function
find_conflicting_tx_with_max_MANA(reality1,reality2,MANA)
returns the transaction from reality1 which is in conflict with reality2 with the most mana.

Subroutine:
Resynch_query(tx1,tx2)
Performs the query of the nodes about two conflicting transactions and swiches to the reality associated with b if supermajority of the queried nodes prefers b

variables:
current_reality - current reality of the node
conflicting_realities - list of all of the realities conflicting with curent_reality kept in the memory
MANA - mana vector
t - current time

for i in conflicting_realities
    if (MANA_associated_with_reality(i) > 0.5) then
	    a = find_conflicting_tx_with_max_MANA(i,current_reality,MANA)
		b = find_conflicting_tx_with_max_MANA(current_reality,i,MANA)
		t_0 = min(timestamp(a),timestamp(b))
		if (T(b,t_0,t) -T(b,t_0,t) > 0.5) CALL Resynch_query(a,b)
	endif	
enddo