FPC - in a Byzantine environment

Over the course of the last months the FPC introduced in https://arxiv.org/pdf/1905.10895.pdf has been studied extensively. It has been prodded from many sides and extensively tested in simulations in a Byzantine setting. This was done at different scales, with inconsistent randomness, and with nodes having only partial network views.

To test the protocol we assume a Byzantine environment, i.e. a proportion of nodes are malicious and try to interfere with the protocol. We distinguish between the following kind of adversarial behaviours: cautious, semi-cautious and Berserk. In the cautious attack an adversary responds the same opinion to the honest nodes, while in the Berserk attack the node can send different opinions to different queries in the same round. As a semi-cautious strategy the adversary may also not respond to a query.

Here we mention that detection methods against the most severe attack could be possible and also describe how the attack could be more severe if nodes have only a partial network view. Finally we we want to discuss asynchronicity at the level of the dRNG.

Berserk protection
As simulations show the Berserk attack is the more severe strategy for an agreement failure and detection methods should therefore focus on the identification of Berserk nodes. Indeed, if nodes have to sign their responses these nodes may be detectable.

For example, if node A queries node B they may in addition also communicate about their past queries. If they discover that they both queried node i in some earlier round m, they may exchange information about the communicated opinion. Similar techniques were proposed in “Safety in the FPC: Berserk, second layer and verifiable query“ by Bart K…

Open questions: Which detection mechanism can we identify and what are the probabilities for detection? What is the communication overhead? Scalability?

Partial network view attack
So far adversarial strategies are focused on achieving an agreement failure based on complete graphs. Simulations showed that these attacks to a graph with nodes having a partial network view are worse - and the severity depends on the level of partitioning of the network. More specifically attacker that have knowledge about the reduced network view of nodes can attempt to split opinions, increase the protocol running time, or even eclipse nodes.

Open questions: What are the advantages that an attacker gains from this partial network view? How partitioned is a network that is created based on a mana?

Asynchronicity of random numbers
Generally simulations showed that FPC performs very well against an adversary that attacks the agreement of the protocol, if occasionally there is a round without a random number. A similar case but one that is more concerned about the asynchronicity of the protocol is that nodes see random numbers for different rounds.

Open questions: Can effects of an asynchronicity in random numbers be reduced by introducing an index (counter) for the random numbers? Is there an equivalence to employing a higher \beta-value?

Do we actually know the number of byzantine nodes that FPC can withstand?

It depends whether you consider an attack on integrity or on agreement and which one is more important (lower \beta means agreement is more important and integrity is less). Also what is the acceptable communication overhead. Larger quorum size=safer.
Also when is a failure a failure? (E.g. is 1 node out of 10,000 being wrong a failure).

Once you have made all your choices on the parameters you can make a statement. But generally we can reach (without Mana) somewhere between 10-30% dependent on what attack is considered.

Section 4 in “Robustness and efficiency of leaderless probabilistic consensus protocols within Byzantine Infrastructures” gives you some indications on the dependency on the parameters.