A problem with CA

In previous documents and discussions, we have established 4 facts which, together, pose a problem for CA.

  1. CA without vote proving is not Byzantine resistant.
  2. With vote proving, we can only apply CA to transactions which satisfy objective criterion.
  3. With snapshots, solidification is a subjective criterion.
  4. We cannot vote on unsolidified transactions.

Putting these facts together, we find that while proving votes, we cannot implement CA securely.

We now go over the arguments in detail. Suppose that we want to vote on the timestamp of all solidified transactions with CA.

Facts 1 and 4 are fairly intuitive, so let us recap 2. Suppose we vote on transactions satisfying some particular condition, call it X. Suppose then that 20% of the honest nodes believe a particular transaction satisfies X and vote on it (this can happen if X is not objective). Suppose that the attacker controls 30% of nodes. Then if the attacker votes too, they hold 60% of the voting power in the vote, and thus can control the outcome. They can hold the 20% in deadlock, or force them to approve a double spend. The 50% other honest nodes cannot affect this outcome unless they fully participate in the vote (point 1).

Thus if some nodes vote using CA, then all nodes must vote.

Now we explain point 3). To enable snapshotting, and we need a rule dictating what can be snapshotted. An example of such a rule is “snap shot all transactions older than currenttime-T for a parameter T” or “snapshot all transactions which are approved by 5 milestones.” Then any transaction which satisfies these rules maybe deleted by some or all nodes. New honest transactions should not approve these transactions, but currently it is not clear

These rules regarding snapshots are inherently temporal. Indeed, new nonlazy tips are of course candidates for tips selection. But at some point in time these transactions becomes old and can be snapshotted. Thus the rules must be temporal. But because of the network delay, temporal rules cannot be objective.

Suppose we require nodes to vote on all solidified transactions. Suppose an attacker issues a transaction that approves transactions which are “the threshold” i.e. some nodes are deleting it, others are not. Then some will see it as solid, and others not. Some nodes will vote on it, and others not, rendering the vote insecure.

We can not solve this problem with solidification requests without forcing nodes redownload large chunks of the tangle on the whim of attackers.

Hans proposed one solution which might work: in this case described above, the transaction is super lazy and so wont be a candidate for tip selection (depending on how we do the TSA of course) and will get orphaned regardless of the vote. This might work, however, and attacker could use promotions to create chaos.

Recently it has also come to my attention that we have similar issue with the gossip. While gossiping, it is difficult to be sure if a transaction that you have seen will propagate through the network or not. Of course, we may want to vote on any transaction we have seen, but we cannot vote on transactions we have not seen (without opening an easy spam attack). We find ourselves in a similar dilemma: how do we determine which transactions to vote on?

Overall, I think the problem goes back to an issue raised in Serguei’s talk at Warsum. We want to design the protocol such that small changes of perception eventually converge to the same view point. In this sense, the tangle is always a stable equilibrium. However, through the hard rules involved in snapshotting, small misperceptions in time cause diverging tangles.

3 Likes

Assuming that

  1. we have (decentralized) checkpoints, and
  2. with the checkpoints, we can design the rules in such a way that the (signed) timestamps are not too much off with very high probability (as we recently discussed in the “protocol” group),

would it be easier to solve the above problems?

2 Likes

I think the problems would still exist, because the problem would still apply to the history of each milestone candidate.

Perhaps Hans’s idea (in the third to last paragraph) might work: transactions which satisfy this edge case are unlikely to be selected as milestones even if they are liked. However, I am not sure this idea can work if an attacker can just promote one of these borderline transactions.

1 Like

I want to spell doubt on this assumption and want to claim below that we can implement a system in which as certainty about opinions increase less voting has to be performed.

In “Using levels of knowledge to determine when to vote“ nodes are distinguished by their level of knowledge that they have about an opinion in the network:

  • Level 1 : The node has this opinion.
  • Level 2 : The node is sure (with high probability) that all honest users have this opinion.
  • Level 3 : The node is sure (with high probability) that all honest users know that all honest users have this opinion.

This could allow nodes to behave in the following way:

  • Level 1 : full participation
  • Level 2 : passive participation: the node does not query, but it responds to queries. The opinion will not change.
  • Level 3 means no participation

If there exists level-3 and level-1 nodes at the same time, then some assumptions for level-3 nodes must have either been made wrong (or it is faulty), or the level-1 node is badly connected (or faulty). Since this should be individual nodes and rare cases (or otherwise we are making some very bad choices for level-3) it may be ok for the node to resync.

Note, its assumed there is some objective way on the tangle to discover that the node made a bad decision and which allows it to resync. This may be orphanage of txs, or a marker on the checkpoint that is different from the one the “faulty” node would set. Such a flag should exist, since voting on a voting object cannot be 100% safe (eclipse, voting error).

Some previous discussions indicated, that the 3-level system can be applied to FPC. However it is not certain whether it also can be applied to CA. I want to argue below that with some modification this should be possible.

Lets note that CA has to work in the initial heartbeat round without vote-proof of its neighbors. Considering network delay and message loss we cannot wait for all nodes, and hence occasionally a heartbeat may even contain an incomplete list of neighbors’ opinions for a few rounds. I am not aware of any discussion on this so far, but we can apply this to a level-2-3 mix as follows.

By sending an additional information in the initial heartbeat - the level that a node believes it has - we can apply the following behaviour:

  • Level 1: Nodes participate normally. Non-reactive neighbors can be blacklisted and it doesn’t care what level its neighbors have.
  • Level 2: Nodes keep sending heartbeats to their level-1 neighbors so that they can prove that their majority of neigbhors also voted the same. Since all level-2 neighbors have the same opinion (or are malicious) the heartbeat in the first round with only the own opinion and the level-2 statement is sufficient to each other or to level-3 nodes. Some nodes may never reply (since they may be level-3) or have an incomplete neighbors’ opinion list (also due to level-3 nodes) and this is not penalized.
  • Level 3: Nodes do not participate in the voting.
1 Like

The problem is caused by nodes making localized decisions about what is below max depth and therefore dropping and seeing different parts of the tangle. If we do not “just drop” transactions that are below max-depth but instead vote on them, then this is not a problem anymore because we essentially will have consensus about what is below max depth.

So instead of being able to directly drop transaction that are below this threshold, we first need to vote on them and then can start dropping everything that attaches to these disliked transactions, leveraging on the monotonicity aspect of the tangle.

1 Like

This doesnt solve the problem, it just changes it: if you are going to vote on whether a transaction satisfies below max depth, then you have to vote on unsolidified transactions too, because incomming transactions may reference things that people have snapshotted.

1 Like

After I now actually understand how you want to set checkpoints, this maybe could work, because we do 1 single colored voting for a milestone.

However, I have no idea how colored voting would work for CA.

1 Like

I have been thinking about this idea, and this actually sounds really good and would fix the issue. In fact, nodes with level 2 opinion only need to issue a single heart beat which states their opinion is level 2. Once a node receives this, and gives it to their neighbors, it will justify their unchanging opinion.

The only question that this attack vector leaves open is the attacker can more easily attack the “integrity”. If all nodes agree on say 0, but they only have level 1 opinion, the the attacker can just set all his nodes to (1,level 2), and they would always respond 1. Without this option, this would be impossible.

1 Like

Does it matter if some people dislike it because it is below max-depth and some people dislike it because it’s not solid? If you only snapshot below a level that was voted on then this should not be problematic.

1 Like

It doesnt matter I suppose, but then you have to vote on unsolid transactions, which opens up the door to spam. But maybe this wont be an issue if CA is fast enough?

1 Like

I don’t think that we need to vote on unsolid transactions.

We communicate all “liked” and “disliked” transactions in every heartbeat. An unsolid transaction might never get disliked as part of the voting process because it is not solid, but it also never gets liked.

This means: If a node that can still solidify a transaction “dislikes” it (because it is below max-depth) and a neighboring node will refrain from making a statement (because it has snapshoted the parents already) then this will still result in the same opinion for both nodes.

The first node will dislike it because it didn’t see a majority of its neighbors liking it that would force him to change his initial opinion. And the other node will dislike it because it’s not solid.

1 Like

A quick note on the resolution of this topic: the following seems to be the best way to go forward. Nodes have the option of stating their initial opinion with the flag “Level 2 knowledge” so that they never have to respond to any opinion changes.

1 Like