This is a informal summary about some research question concerning mana free CA.
See previous post A problem with CA and https://govern.iota.org/c/voting
Notations and setting
Let k be the number of peers in auto-peering network.
First reasonable networks (underlying graphs) are realizations of a random k-regular graph.
Since auto-peering is not perfect and dynamic this is not quite true.
Next reasonable networks are graphs of a given degree sequence, where a positive proportion has degree k.
Communication model: we assume a synchronous setting, i.e., there is a known time \delta such that all messages are received before time \delta.
This can be weaken to a probabilistic synchronous setting. For given \varepsilon we assume that there exists some known \delta=\delta(\varepsilon) such that every message is delivered before time \delta with probability of at least 1-\varepsilon. Message arrival times are supposed to be independent.
Communications between two nodes is assumed to satisfy authentication, i.e., senders and receivers are who they claim to be, and data integrity, data is not changed from source to destination. This is achieved by signing the messages.
The protocol:
Described in [4]. More details to put here.
In the applied setting one needs a local stopping rule. That means a rule such that every node decides whether to fix its opinion and stop querying other nodes. In this way, if the protocol/dynamics is successful the protocol will terminate in some finite time. For example, if a node has kept its opinion for \ell time steps then it will fix this opinion.
QUESTION G1: What are the best (local) stopping rules? Adaptive versions?
Failures
Possible failure of the protocol are
-
Integrity failure: at the end every node has the opinion of the initial minority;
-
Agreement failure: there are at least two nodes with different opinions at the end;
-
Termination failure: the protocol does not end before some max_it time.
Previous results
Most (or all?) of previous literature does not consider adversaries.
Among the numerous results about majority dynamics in various setting we plan here a short (definitively incomplete) overview about theoretical results.
In very short, if initial opinions are chosen i.i.d. with \alpha>0.5 proportion of 1, then with high probability the consensus is achieved on opinion 1. See [1] and [2] for more quantitative bounds. Also see [5] for theoretical results and outgoing and incoming references. Also in [4] references on previous work are given.
QUESTION G2: What can be said about other initial conditions? Does worst case lead to an ``impossibility’’ result? (Might be in the literature somewhere?)
Message loss and faulty nodes:
We call \varepsilon-majority or eM the model where each node fails with probability \varepsilon (independent of the others) and won’t answer their neighbors.
QUESTION M1: Convergence, speed and probability of convergence. Integrity, agreement and termination failure rate.
We consider the model of message loss, where every message is lost with probability \varepsilon (independent of the others).
QUESTION M2: Under message loss, Convergence, speed and probability of convergence. Integrity rate.
One key heuristic in [1] (described on the bottom of page 5) is on tree-like subgraphs and I think that this could also work for eM and message loss. Either the sequence of p_i there converges to zero or not and this might give the threshold for \varepsilon. But I have to admit that I have not yet looked at the details. Might also apply for some adversarial strategies.
Adversaries
Adversaries: are supposed to be omniscient (they know the network structure and opinions of all nodes). We assume f(n) of the nodes to be adversarial.
Heartbeat (or proof of opinion), prevents Berserk behavior. However, semi-cautious strategy may be possible in not answering. In this case the node risks to be dropped immediately by its neighbor, however, since re-peering might take longer as a CA voting this might still be a viable attack strategy.
So, given heartbeat is working, an adversary can only choose the initial opinions and opinions of malicious nodes that are neighbors with more than k/2 other malicious nodes. Moreover, an adversary may disturb the connectivity of the network during CA.
Note: as mentioned below, an adversary might also have an influence on the initial opinions of the honest nodes.
QUESTION A0: What are the best strategies of an adversarial for the above failures?
For integrity failure it should be that the adversary should not reply if its opinion is not the minority opinion. Agreement failure, force locally two different regions to fix on different values, as fast as possible such that they don’t know about each other?
For termination failure. Heuristic for case without heartbeat: Assume that 0 and 1 opinions are very close say 499 for 0 and 501 for 1, then it is sufficient (at least for Erdös-Renyi graphs) to turn only 6 nodes with opinion 1 such that with high probability finally all nodes have opinion 0, see [3]. It now depends on how many nodes change from 1 to 0 in the first step. If an adversary can control an equal amount then he probably can alternate between majority of 0 and 1 for quite a long time.
QUESTION A1: Assume heartbeat not to work and adversarial nodes be chosen uniformly at random. What is critical f(n)?
QUESTION A2: Assume heartbeat not to work and adversarial nodes can choose their position. What is critical f(n)?
QUESTION A3: Assume heartbeat to work and adversarial nodes be chosen uniformly at random. What is critical f(n)?
QUESTION A4: Assume heartbeat to work and adversarial nodes can choose their position. What is critical f(n)?
Initial condition
It is not a good/realistic assumption that the initial opinions are i.i.d. since the transactions are gossiped over the same auto-peering network as the CA takes place. The adversary may therefore influence the initial opinions.
A first approach to model this could be to take two nodes at maximal distance with different opinions. Start two independent first-passage percolation on the network (or on spanning trees) (may depend on the actual gossip protocol), opinion of a node is then given by "argmin arrival time’’. "Maximal distance’’ could be replaced then by something more sophisticated.
REFERENCES:
[1] Global majority consensus by local majority polling on graphs of a given degree sequence, Abdullah and Draief https://www.sciencedirect.com/science/article/pii/S0166218X14003357
[2] Majority Model on Random Regular Graphs, Gärtner and Zehmakan, https://arxiv.org/abs/1711.07423
[3] Reaching a Consensus on Random Networks: The Power of Few, https://arxiv.org/abs/1911.10279
[4] Robustness and efficiency of leaderless probabilistic consensus protocols within Byzantine infrastructures, Capossele, Mueller and Penzkofer https://arxiv.org/abs/1911.08787
[5] Majority dynamics and aggregation of information in social networks, Mossel, Neemann, Tamuz , https://link.springer.com/article/10.1007/s10458-013-9230-4