Voting on conflicts - failures, consequences and re-synchronization

We assume either FPC or CA as a voting mechanism, and that if voting is applied, it is on the like-status of a tx. More specifically, non-conflicting txs are liked and only conflicts are considered for voting. If a tx is disliked it is not considered for tip selection any longer, see also the document “Fast consensus of Barcelona”. Furthermore, we assume monotonicity, i.e. if a tx is disliked also its future cone is disliked. Txs that are disliked are effectively orphaned.

The following failures of the voting protocol are considered: Termination-, agreement, and integrity-failure. For further reading material, see also the documents “Double voting protocol” and the paper on FPC simulations.

Termination failure
No consensus is reached after a very long period of time. Due to local termination rules liveness of the protocol is guaranteed but a termination failure can lead to individual nodes lagging behind the rest of the network. Generally the message complexity may be significantly increased by a termination failure. If a large proportion of the network is affected the network may become incapacitated. Furthermore, for most studied and simulated attack scenarios, a termination failure is often accompanied by an agreement failure.

Agreement failure
The honest nodes do not agree. We distinguish between a
1.) 0-agreement failure or False Positive: Effectively this is a situation when the node ended up accepting a transaction that was actually rejected by the majority of the Tangle. The node will use this transaction as valid until the False Positive is identified.
2.) 1-agreement failure or False Negative: This is a situation where a transaction was rejected by the node while the majority of the network accepted it. For the affected node it appears that an increasing amount of incoming txs are invalid.

Integrity failure
The protocol does not reflect the initial opinions of the honest nodes. We distinguish between
1.) 1-integrity failure, where the majority of nodes conclude with 0. A 1-integrity failure can lead to the cancellation of txs since the future cone is affected. It also can enable double-spending of funds, if a merchant accepted funds prematurely (since the adversary can spend them later again).
2.) 0-integrity failure, where the majority of nodes conclude with 1. This can enable a double-spend.

Identification of agreement failure and Re-synchronization
Identifying the problem is done by checking the Gossiping Layer for atypical behavior and then doing a testing in case the behavior reaches a certain threshold. For a more detailed description see also the document “Double voting protocol”.

  • False Positive: If after time T, if the number of received gossiped transactions approving x on the gossiping layer is lower than A_1, do a confirmation step.
  • False Negative: If after time T, if the number of received gossiped transactions approving x on the gossiping layer is greater than A_2, do a confirmation step.
  • Confirmation Step: Sample M nodes uniformly from your list of nodes in the network. The transaction x is considered synchronized if a supermajority of the sampled nodes agree with the node’s opinion on the transaction. Otherwise the transaction needs to be re-synchronized.

Open questions:

  • Agreement failure: Resynchronisation is an option if individual nodes fall out of sync. However, it is not clear if this is sufficient when a larger proportion of the network falls out of sync. Also would a more frequent occurrence of the failures, i.e. many individual failures = many nodes affected, incapacitate the protocol?
  • Integrity failure: Billy’s 3-level approach on when-to-vote (see the document “When to vote”) alleviates the severity of this problem to some extent, since older tx should less likely suffer from an integrity failure. So is it sufficient, that txs are only truly accepted once the vote is old enough? And how old is old enough?

As mentioned in the first paragraph of the above post this topic also touches the topic of Monotonicity. Lets recall that monotonicity can be enforced by requiring that txs in the future cone of a disliked tx are also disliked and excluded from the tip selection, see “Fast consensus of Barcelona”. Then some interesting edge cases can arise, when we want to decide what we should vote on.

Consider conflict sets \{A_1, A_2\} and \{B_1, B_2\}, where B_1\in futureCone(A_1) but A2\in futureCone(B_2). Assume A_1 and B_1 are visible in the tangle, and revealing A_2 and B_2 has triggered voting on the A-set on some of the nodes and on the B-set on other nodes due to asynchronous reasons. How would nodes agree what to vote on?

The simplest but heaviest version from a communication point of view is to vote on all of the conflicts \{A_1,B_1,A_2,B_2\} and decide after. However, this leads to some (or many) of the votes being cancelled, having invested unnecessary message overhead. As an alternative, we may delay votes on older conflicts and cancel already ongoing newer ones (cancel/delay \{A_2,B_2\}). However, the implications and attack vectors are not studied for this approach.

I think this is what we will have to do. I wont worry about the extra overhead: an attacker can also just issue conflicting non, ordered pairs to make people vote as much as possible.