Safety of the Tangle: Berserk Detection in the FPC

The beginning of the English Wikipedia page on Berserker states:

In the Old Norse written corpus, berserkers were those who were said to have fought in a trance-like fury, a characteristic which later gave rise to the modern English word berserk (meaning “furiously violent or out of control”). Berserkers are attested to in numerous Old Norse sources.

This nameBerserkerwas adapted in the research paper “FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures” (FPC) by Serguei Popov and William J Buchanan as a term describing one of the types of malicious actors that try to influence the binary voting protocol introduced in that paper.

To quickly recap, the Fast Probabilistic Consensus (FPC) is a leaderless protocol that allows a set of nodes to come to a consensus on the value of a single bit. The protocol is divided into epochs which are called rounds. The heart of the protocol is the fact that in each round, every node queries k other nodes about their current opinion i.e.: the preferred value of the bit. The node forms its new opinion based on the opinions of the queried nodes. If a node holds the same opinion during l consecutive rounds, then it can be reasonably sure that this opinion will be adopted by all of the honest nodes. So after this, the node finalizes its opinion. Nodes that finalized their opinions still respond to the query requests, however, they do not query other nodes. An important feature of the FPC protocol is the so-called random threshold— a random number assigned to each round which is revealed when all of the queried opinions are gathered. The new opinion formation depends on this random threshold. This provides additional protection against malicious actors as he/she cannot predict what is going to be a threshold. The level of randomness during the protocol is guided by the parameter β. In particular, β = 0.5 means that there is no randomness in the system. For more details read the following blog posts: A simulation study of FPC or One Step Closer to Coordicide: IOTA Releases Fast Probabilistic Consensus Simulator.

The FPC voting protocol is one of the foundations of Coordicide — the project undertaken by the IOTA Foundation that aims at the removal of the Coordinator from the IOTA network. Coordicide hopes to bring scalability without centralization. The FPC voting is the basis of the new consensus mechanism which brings security to the post-Coordinator Tangle. The protocol is Byzantine Fault Tolerant i.e.: it works even when part of the network nodes are malfunctioning or are controlled by an adversary who intends to either delay the consensus or break it. The FPC paper distinguishes between two types of attackers:

Cautious adversary: any adversarial node must maintain the same opinion in the same round, i.e., respond the same value to all the queries it receives in that round.

Berserk adversary: an adversarial node may respond differently to things for different queries in the same round.

The behavior of the berserk adversary may be interpreted as a sign of madness which resembles the insane behavior of legendary Scandinavian warriors (hence the name). However, as it was shown, there is a method to this madness. Mathematical proofs in the FPC paper reveal that the system is more vulnerable to attacks executed by berserkers. This is further confirmed by the FPC simulations paper (see Simulation study of FPC). The probability of the agreement failure (a situation in which there is no unanimous final decision in the system) although still small is higher when an adversary is berserk rather than cautious. Similarly, berserker has a greater chance of delaying consensus (termination failure), and the number of exchanged messages between honest network participants increases.

This can be illustrated with a figure from the FPC simulations paper where authors compare the evolution of the opinions in the system when the attacker is cautious and berserk. We can see that the system can withstand cautious attackers even when the random threshold used in the FPC protocol is turned off (top subfigure). However, when the attacker is berserk the consensus can be delayed indefinitely and only the addition of randomness for the threshold can cause the system to make the decision.

Although in the limit of the infinite number of nodes probability that there will be agreement failure, that could lead to the fork in the system is zero, for the real-life networks where the number of nodes is finite, this probability can be positive. Since we want to make it as small as possible, one of the tactics we employ is to take away from the attacker the possibility to behave in a berserk way. We want to make sure that any trace of the berserk behavior is detected fast. Then the node which is proven to behave dishonestly would be dropped from the query list and his reputation would be slashed.

Berserk detection protocol

The detection protocol is in fact very simple: we allow the nodes to exchange information about the opinions received in the previous rounds. A subsequent analysis of this information can then reveal the berserk behavior. Upon discovering malicious voting patterns, nodes would gossip the proofs such that all of the other honest network participants drop the berserk node.

A more detailed protocol description is as follows:

We allow any node can ask any other node for a list of opinions received during the previous round of FPC voting. We call such a list v-list and we may request it in several ways. For example, the full response message to the request of a v-list and the opinions could be composed of the opinion in the current round and the received opinions from the previous round. Requesting av-list would not be mandatory. E.g. each node could also ask for it with a certain probability or if it has the necessary bandwidth capacity available. Furthermore, we can set an upper bound on this probability on the protocol level so that spamming of requests for v-lists can be detected. We denote this probability that an arbitrary query request includes a request for a v-list by p.

Assume that in the last round a node y received k votes, submitted by nodes z1,z2,z3,…,zk. If a node x asks y for a v-list, then y sends votes submitted by z1,…,zk along with the identities of z1,…,zk but without their signatures. This reduces the message size. Node x compares the opinions in the v-list submitted by y with other received v-lists. If x detects any trace of a suspicious behavior it will ask node y to send it the associated signatures that would prove the malicious behavior. Having collected the proof the honest node gossips the evidence to the network and the adversary node will be dropped by everybody.

To test how reliable this detection method is and what the communication overhead would be, we carry out the following calculations.

Expected number of rounds before the detection of berserker

We are interested in the probability of detecting a berserk adversary since the inverse of this value gives us an estimation of how many rounds are required to detect malicious behavior. If the number of rounds is sufficiently small we can conclude that the protocol allows for the fast detection of a berserk attacker.

Let us consider the following scenario: Among N honest nodes there is a single berserk node. In the last round, the adverse node was queried k times, which is the expected number of received query requests (if we pick nodes with uniform probability). Furthermore, it sends kf votes with opinion 0 and(1-f) k votes with the opinion 1 to different nodes in the network. Let us call the first groupG0and the second oneG1.

The probability that an honest node x requests a v-list from a node from the groupG0equalspfk/Nandp(1-f)k/NforG1. Note that the events of receiving v-lists fromG0andG1are not independent. Calculations reveal that up to the lowest order the probability that x receives v-lists that allow for the detection of the berserk node equals

If N honest nodes follow this procedure then, using the approximation(1-x)^a = 1-ax the probability that some node detects the berserk behavior equals

The attacker is said to be “maximally berserk”’ whenf=(1-f) =1/2.

For example in a system with N=10000 nodes, k=30 and p=0.1 the detection probability is approximately≈ 0.02. In this case, the berserk node should be discovered after approximately 50 rounds. Assuming that the full FPC vote takes≈ 15rounds, berserk nodes should be detected within 4 full FPC voting cycles.

Message overhead

For simplicity, we assume here that there is one pair of conflicting transactions in the Tangle. The message overhead to apply berserk detection is then as follows. The ID of a node takes 32 bytes, which can be compressed for this application to 6 bytes; the opinion of a node requires a single bit. Furthermore, assume thatp=0.1andk=30then the message overhead for sending the v-list together with the query response (it, therefore, does not require an additional signature) would be on average 1.8 bytes. This is significantly less than 2500 bytes, which are expected to be required to receive opinions from all k queried nodes in FPC without berserk detection. We conclude that the addition of the berserk detection to the FPC protocol would result, on average and in this particular case, in less than 1% larger messages, which is negligible. In the case when more than one conflict is voted on, the relative message overhead for the detection mechanism would be increased. More specifically, each conflict increases the overhead by one bit, while the overhead for the signatures remains the same. Since the signatures component is relatively large compared to the opinion part, the signature part is the dominating factor.

Improvements: opinion history comparison

Note that in the analysis presented above, nodes compare opinions from a single, previous round. However, we can increase the efficiency of the protocol when the nodes compare opinions from more than just the last round, i.e. nodes may compare entire histories of opinions rather than only the current and last opinions. By history, we mean a list of all held opinions by a given node in consecutive rounds. For example, if a node is in the m-th round on voting on a particular conflict its history consists of m bits and each of them corresponds to the opinion in one of the m rounds. When such a node is asked to give its current opinion it would respond with the m bits message, which would be later used to construct v-lists.

Note that nodes could compare the histories of opinions of different sizes. For example, when node x receives the voting history from the same node y in the m1-th and m2-th rounds (m1 <m2) it could try to find traces of the berserk behavior on the overlapping m1 rounds. With this method, the effectiveness of the berserk detection increases greatly. An obvious drawback of this approach would be that, in order for such a protocol to work, we would require each node queried in FPC to send its entire opinion history (on a particular conflict). This opinion history would grow with each round of voting by one bit. Moreover, nodes would need to allocate some memory to keep both the history of their own opinions and the history of the opinions of other nodes. However, the additional communication cost is not very high.

Conclusions

In conclusion, we presented an optional protocol for the detection of berserk adversaries, which improves the security of the protocol. The decrease in the efficacy of possible attacks leads in turn to decreased probabilities of agreement and termination failures. As a further improvement, we propose that nodes could also vote with the entire history of collected opinions rather than only the most recent opinion. As we showed this would not change the message size in a significant way.

As always, if you want to get involved with us, or have any comments, questions or feedback, please do not hesitate to get in contact with the IOTA team on our Discord server.