Message spreading with protocols

Simple messaging

At the heart of message spreading, we have the ethp2psim.message.Message class that represents objects traveling on the P2P network (e.g., block proposal, attestation, simple transaction).

To interact with a message, first, you need to define the underlying P2P network (ethp2psim.network.Network) discussed in detail in the previous section.

Then, multiple other components haven’t been introduced so far, like protocols (e.g., ethp2psim.protocols.BroadcastProtocol, ethp2psim.protocols.DandelionProtocol) that defines the exact rules for message passing, or the adversary (ethp2psim.adversary.Adversary) that eavesdrop on the network as the message diffuses over the nodes.

Nonetheless, in the examples below, we showcase how a message originating from node zero is propagated over the network with simple broadcasts while an adversary is controlling 10% of the P2P network by constantly eavesdropping on the messages.

class ethp2psim.message.Message(source)[source]

Bases: object

Abstraction for Ethereum transactions

Parameters:

source (int) – Source node of the message

Examples

>>> from .network import *
>>> from .protocols import BroadcastProtocol
>>> from .adversary import Adversary
>>> nw_gen = NodeWeightGenerator('stake')
>>> ew_gen = EdgeWeightGenerator('normal')
>>> # random 3 regular graph with 10 nodes
>>> net = Network(nw_gen, ew_gen, 10, 3)
>>> protocol = BroadcastProtocol(net, broadcast_mode='all')
>>> adversary = Adversary(protocol, 0.1)
>>> # message originating from node 0
>>> msg = Message(0)
>>> _ = msg.process(adversary)
>>> # message was sent to 3 neighbors of node 0
>>> len(msg.queue)
3
flush_queue(adv)[source]

Process every remaining event in the message queue.

Parameters:

adv (adversary.Adversary) – Adversary that records observed messages on the P2P network

Return type:

NoReturn

Examples

This step is important to showcase the true deanonymization power of the adversary as it should get every message ever sent to its nodes in the P2P network. Later, we will see that it has a huge relevance when the adversary tries to predict message sources using the ‘first sent’ heuristic.

>>> from .network import *
>>> from .protocols import BroadcastProtocol
>>> from .adversary import Adversary
>>> nw_gen = NodeWeightGenerator('stake')
>>> ew_gen = EdgeWeightGenerator('normal')
>>> # random 3 regular graph with 10 nodes
>>> net = Network(nw_gen, ew_gen, 10, 3)
>>> protocol = BroadcastProtocol(net, broadcast_mode='all')
>>> adversary = Adversary(protocol, 0.1)
>>> # message originating from node 0
>>> msg = Message(0)
>>> _ = msg.process(adversary)
>>> # message was sent to 3 neighbors of node 0
>>> len(msg.queue)
3
>>> # empty queue
>>> msg.flush_queue(adversary)
>>> len(msg.queue)
0
process(adv)[source]

Propagate message based on the adversary. Note that adversary also contains the protocol.

Parameters:

adv (adversary.Adversary) – Adversary that records observed messages on the P2P network

Return type:

Iterable[Union[float, bool]]

Examples

Here, we present the full picture for message propagation. The message is iteratively processed until it reaches the desired fraction of nodes. Flushing the queue of unprocessed messages is still an essential final step.

>>> from .network import *
>>> from .protocols import BroadcastProtocol
>>> from .adversary import Adversary
>>> nw_gen = NodeWeightGenerator('stake')
>>> ew_gen = EdgeWeightGenerator('normal')
>>> # random 3 regular graph with 10 nodes
>>> net = Network(nw_gen, ew_gen, 10, 3)
>>> protocol = BroadcastProtocol(net, broadcast_mode='all')
>>> adversary = Adversary(protocol, 0.1)
>>> # message originating from node 0
>>> msg = Message(0)
>>> # propagate message until it reaches all nodes
>>> stop = False
>>> node_fraction = 0.0
>>> while node_fraction < 1.0 and (not stop):
...     node_fraction, _, stop = msg.process(adversary)
>>> msg.flush_queue(adversary)
>>> # remainging messages must be processed
>>> len(msg.queue)
0
>>> # all nodes were reached
>>> len(msg.history)
10

How do protocols work?

Message spreading in detail is more technical. We use the ethp2psim.protocols.ProtocolEvent class to track how a given message (ethp2psim.message.Message) spreads over the nodes of the P2P network (ethp2psim.network.Network). This is where we store valuable information (e.g., time delays and the number of hops from the message source) that are essential to evaluate the performance of different protocols in obfuscating message sources.

class ethp2psim.protocols.ProtocolEvent(sender, receiver, delay, hops, spreading_phase=False, path=None)[source]

Message information propagated through the peer-to-peer network

Parameters:

  • sender (int) – Sender node

  • receiver (int) – Receiver node

  • delay (float) – Elapsed time since the message source created this message when it reaches the receiver node

  • hops (int) – Number of hops from the source to the receiver node

  • spreading_phase (bool) – Flag to indicate whether the message entered the spreading phase

  • path (list) – Remaining path for the message (only used in OnionRoutingProtocol)

Examples

In a tiny example we show that we record message spreading with ProtocolEvents.

>>> from .network import *
>>> from .message import Message
>>> from .adversary import Adversary
>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edges_from([(1,2),(2,3),(1,3)])
>>> nw_gen = NodeWeightGenerator('stake')
>>> ew_gen = EdgeWeightGenerator('normal')
>>> seed = 42
>>> net = Network(nw_gen, ew_gen, graph=G, seed=seed)
>>> protocol = BroadcastProtocol(net, broadcast_mode='all', seed=seed)
>>> adversary = Adversary(protocol, adversaries=[3], seed=seed)
>>> msg = Message(1)
>>> for _ in range(3):
...    _ = msg.process(adversary)
>>> msg.flush_queue(adversary)
>>> # message reached node 2 only from node 1
>>> msg.history[2]
[ProtocolEvent(1, 2, 228.034291, 1, True, None)]
>>> # and it reached node 3 from node 1 and node 3
>>> msg.history[3]
[ProtocolEvent(1, 3, 242.482918, 1, True, None), ProtocolEvent(2, 3, 250.755617, 2, True, None)]

Next, let’s discuss the primary building blocks of message-passing protocols. By default, each implemented protocol stores two different graphs for message passing:

  1. A (public) graph for broadcasting messages. It is the same P2P network we initialize with network.Network at the beginning of each example. We consider this network to be constant in our experiments.

  2. An anonymity graph (e.g., a line graph in the case of Dandelion by Venkatakrishnan et al.) is used to obfuscate the source of each message. It is also public, but it can change from time to time.

In our work, we suppose that nodes can decide whether a given channel belongs to the anonymity graph or to the broadcast network. Moreover, adversary nodes heavily depend on this information when they predict possible source nodes for a given message.

For example, in ethp2psim.protocols.BroadcastProtocol, which is the most simle baseline in this package, there is no anonymity graph. Messages are spreading only on the P2P network.

class ethp2psim.protocols.BroadcastProtocol(network, broadcast_mode='sqrt', seed=None)[source]

Message propagation is only based on broadcasting

Parameters:

  • network (network.Network) – Represent the underlying P2P network used for message passing

  • broadcast_mode (str) – Use value ‘sqrt’ to broadcast the message only to a randomly selected square root of neighbors. Otherwise the message will be sent to every neighbor.

  • seed (int (optional)) – Random seed (disabled by default)

Examples

The broadcast protocol has no anonymity graph.

>>> from .network import *
>>> nw_generator = NodeWeightGenerator("random")
>>> ew_generator = EdgeWeightGenerator("normal")
>>> net = Network(nw_generator, ew_generator, num_nodes=10, k=2)
>>> broadcast = BroadcastProtocol(net, broadcast_mode='all')
>>> broadcast.anonymity_network is None
True

While for ethp2psim.protocols.DandelionProtocol, each message has a stem-phase where the message is only propagated on the underlying anonymity graph (that is a line graph in the case of the Dandelion protocol). Then, the message enters the spreading phase where it behaves identically to ethp2psim.protocols.BroadcastProtocol.

class ethp2psim.protocols.DandelionProtocol(network, spreading_proba, broadcast_mode='sqrt', seed=None)[source]

Message propagation is first based on an anonymity phase that is followed by a spreading phase

Parameters:

  • network (network.Network) – Represent the underlying P2P network used for message passing

  • spreading_proba (float) – Probability to end the anonimity phase and start the spreading phase for each message

  • broadcast_mode (str) – Use value ‘sqrt’ to broadcast the message only to a randomly selected square root of neighbors. Otherwise the message will be sent to every neighbor in the spreading phase.

  • seed (int (optional)) – Random seed (disabled by default)

Examples

The anonymity graph is a line graph where the number of edges equals to the number of nodes.

>>> from .network import *
>>> nw_generator = NodeWeightGenerator("random")
>>> ew_generator = EdgeWeightGenerator("normal")
>>> net = Network(nw_generator, ew_generator, num_nodes=10, k=2)
>>> num_edges = net.graph.number_of_edges()
>>> dandelion = DandelionProtocol(net, spreading_proba=0.5, broadcast_mode='all')
>>> dandelion.anonymity_network.num_edges == net.num_nodes
True

References

Shaileshh Bojja Venkatakrishnan, Giulia Fanti, and Pramod Viswanath. 2017. Dandelion: Redesigning the Bitcoin Network for Anonymity. In Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ‘17 Abstracts). Association for Computing Machinery, New York, NY, USA, 57. https://doi.org/10.1145/3078505.3078528

change_anonimity_graph()

Initialize or re-initialize anonymity graph for the anonymity phase of Dandelion, Dandelion++ or Onion Routing protocols

Return type:

NoReturn

propagate(pe)[source]

Propagate message based on protocol rules

Return type:

Iterable[Union[list, bool]]

In ethp2psim.protocols.DandelionPlusPlusProtocol, the anonymity graph is an approximate four regular graph suggested by Fanti et al.

class ethp2psim.protocols.DandelionPlusPlusProtocol(network, spreading_proba, broadcast_mode='sqrt', seed=None)[source]

Message propagation is first based on an anonymity phase that is followed by a spreading phase

Parameters:

  • network (network.Network) – Represent the underlying P2P network used for message passing

  • spreading_proba (float) – Probability to end the anonimity phase and start the spreading phase for each message

  • broadcast_mode (str) – Use value ‘sqrt’ to broadcast the message only to a randomly selected square root of neighbors. Otherwise the message will be sent to every neighbor in the spreading phase.

  • seed (int (optional)) – Random seed (disabled by default)

Examples

The anonymity graph is an approximate four regular graph.

>>> from .network import *
>>> nw_generator = NodeWeightGenerator("random")
>>> ew_generator = EdgeWeightGenerator("normal")
>>> net = Network(nw_generator, ew_generator, num_nodes=10, k=2)
>>> num_edges = net.graph.number_of_edges()
>>> dandelion_pp = DandelionPlusPlusProtocol(net, spreading_proba=0.5, broadcast_mode='all')
>>> dandelion_pp.anonymity_network.num_edges == (2 * net.num_nodes)
True

References

Giulia Fanti, Shaileshh Bojja Venkatakrishnan, Surya Bakshi, Bradley Denby, Shruti Bhargava, Andrew Miller, and Pramod Viswanath. 2018. Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees. Proc. ACM Meas. Anal. Comput. Syst. 2, 2, Article 29 (June 2018), 35 pages. https://doi.org/10.1145/3224424

change_anonimity_graph()

Initialize or re-initialize anonymity graph for the anonymity phase of Dandelion, Dandelion++ or Onion Routing protocols

Return type:

NoReturn

propagate(pe)[source]

Propagate messages based on the Dandelion++ protocol rules. See Algorithm 5 in Dandelion++ paper.

Return type:

Iterable[Union[list, bool]]

In the next section, we show various ways on how to configure your adversary.