Tip selection variation for decentralized checkpoints

In CA as well as in FPC individual nodes may come to a different opinion to the majority (an agreement failure) in some - potentially rare - cases. Furthermore, this may occur even in an honest environment. In CA this may be caused by pockets (small metastable groups with the opposite opinion), while in FPC it may be caused by nodes reaching l consecutive rounds with the wrong opinion. Therefore, there should be an objective way, how nodes can discover that their decision was wrong.

For example, if we vote on conflicts this may be orphanage. With checkpoints the following proposes a different mechanism.

  • We require a DRNG
  • We employ Serguei’s decentralized checkpoints selection and we require that checkpoint i approves checkpoint i-1 and is directly linked through a series of trunk-edges. The latter will become more clear in the following.
  • The TSA is then modified in the following way: The trunk edge always approves a tip in the future trunk cone of the last checkpoint. The future trunk cone only considers the trunk edges.

This leads to two observations: First, if there was no major agreement failure in the voting protocol the trunk future cone will grow exponentially. Second, every tx states on the tangle which txs are the last checkpoint from its point of view . More specifically, if one traverses the trunk cone backwards there will be an increasing density of edges (approvers) close to a checkpoint. Since the effective number of edges that randomly select tips is reduced (between 1 and 2) the time of some of the txs remaining tips may increase, although not by much.


Open questions:

  • In order for this to work the majority of nodes should come to the same checkpoint candidates w.h.p… This requires that a) there is no major agreement failure on any of the candidates. b) there are not too many candidates. a) seems obvious. But can the DRNG make the time sufficiently unknown to prevent spaming? What happens if there is a significant surge of checkpoint candidates.

Due to recent discussions the following improvements are proposed:

  1. We can take advantage of mana in the following way to secure the rate of checkpoint candidates: every node issues a checkpoint candidate at t_{delta} time after the last checkpoint. Nodes then vote whether they like the candidates based on the following criteria: whether the time of a given candidate was within a certain window, and whether they agree that the candidate approves the correct last checkpoint. Since higher mana holders should have more candidates either a) the number of candidates is indexed and proportional to the mana or b) the Hashdistance Hash(Hash(tx)+RandNum) is scaled proportionally.
  2. The initial proposal above assumes that the rate of txs is proportional to the mana. However this is a weak assumption. A more safe approach would be, if nodes issue txs which indicate which checkpoint future cone they like. Nodes get one vote per checkpoint, and their vote is weight by mana. If it turns out to be necessary that nodes can change their opinion (e.g. if they are the only node that is wrong), we can index these tx. Double-index is not possible since txs are signed.
  3. In voting on conflicts a severe agreement failure can lead to a large proportion of nodes disagreeing on the candidate. Let the probability of a severe agreement failure happening be p. Since there are M candidates, the likelihood of this issue is further decreased by a factor 1/M. Severe disagreement on a checkpoint will lead to an empty liked candidate list for the next checkpoint. Therefore, the following approach is proposed: If the candidate set is empty because the network suffered a significant agreement failure on the last checkpoint, all nodes remove the previous checkpoint (the one where the agreement failure happened). If the above assumptions are correct I would expext the probability of this happening again a second time be ~p/M and this should therefore provide good probabilistic finality properties.

After review this may not work, because an adversary may censor a particular node very easily by distributing txs and after issuance of a the honest nodes’ checkpoints the adversary may rater quickly create a conflict with the tx. Therefore, a node may have to create a number of candidates proportional to its mana.