UPSYCLE: Ubiquitous Publish-Subscribe Infrastructure for Collaboration on Edge Networks

Initial Protocol Design Proposal

Abstract

The UPSYCLE protocol suite enables decentralized and asynchronous topic-based publish-subscribe communication across the internet and on edge networks. To achieve this, it combines trust-aware peer sampling, privacy-preserving subscription clustering, and reliable causal delivery in a two-tier P2P system that consist of a core network of always-on nodes and edge networks of mobile nodes where core nodes provide store-and-forward proxy services to mobile nodes to ensure reliable asynchronous communication across the internet.

Design

Design requirements

The design requirements for UPSYCLE and how we achieve them are the following:

Scalability
is achieved by minimizing overlay & suboverlay maintenance and by efficient dissemination in suboverlays
Relay-free routing
is enforced by creating a suboverlay for each topic
Bounded node degrees
are achieved via interest clustering
Low latency & duplication factor
as much as the scalability constrains of suboverlay maintenance allows
Reliable delivery & causal order
is ensured by causal barriers and a reactive error recovery mechanism
Subscription privacy
subscriptions should be private and only common group membership between peers should be able to be discovered
Resiliency
the use of explicit trust networks make the protocols more resilient to attacks
Minimalism
we strive to minimize protocol complexity and hardware resources, e.g. by avoiding expensive Proof-of-Work computations and by employing a two-tier network to minimize resource requirements for mobile nodes
Offline-first
nodes on edge networks should have a copy of all the data they subscribed to and should be able to communicate directly and opportunistically synchronize with the core network

Design overview

UPSYCLE is a decentralized publish-subscribe system designed with the requirements of resource constrained and intermittently connected mobile devices in mind. Since mobile devices are bandwidth and battery constrained, we propose a two-tier P2P system, where a P2P core network runs a set of P2P protocols, while mobile devices form edge networks for local interaction and connect to one or more remote proxies, which are always-on nodes that participate in the core P2P network and act as store-and-forward proxies for mobile nodes. This way it's sufficient for a mobile node to establish a single connection to a proxy to reach remote nodes.

It's important to note here that these proxies only perform store-and-forward message relaying, and cryptographic user and group identities are independent of them. This allows a mobile node to choose a different proxy at any moment, or even to use multiple proxies for redundancy.

This approach avoids the issues of centralized and federated systems (such as Facebook and Matrix) where user data and identities are tied to a specific server provider, and thus migration to a different provider is either difficult or impossible. In addition, the use of proxies also provides location privacy to users, i.e. a user's IP address is never revealed, except to the user's own proxy, which results in VPN-like privacy protections.

Next to connecting to proxies, mobile nodes can also maintain direct P2P connections with other nodes on the local network where they participate in similar P2P protocols to the ones in the core network. This allows local collaboration, even without internet connectivity.

There can be serious privacy implications of exposing group membership, especially on local networks. Therefore, group discovery, both in core and edge networks, is based on a Private Set Intersection (PSI) protocol. In groups where pseudonymity is desired, even the discovery of other group members on local networks could be problematic, and thus users should be able to opt in to local group discovery on a per-group and per-network basis.

P2P transport

Peers in the network establish end-to-end encrypted P2P connections among each other. Gossip-based peer sampling and dissemination protocols rely on these links to reach other peers in the network. Since gossip-based protocols need to establish new connections frequently to other peers, it's important to minimize the connection setup overhead heap?, laystream?, which includes a TCP handshake, a Diffie-Hellman key exchange, and negotiation of cryptographic parameters. Using UDP instead of TCP, as well as protocols with optimized cryptographic handshakes, caching encryption keys for session resumption, and keeping connections open for reuse are techniques that help to reduce the connection setup overhead.

TLS and DTLS are two commonly used transport security protocols for TCP and UDP, respectively. The recently introduced version 1.3 of TLS brings many improvements to the handshake process, reducing it to 1-RTT for new connections and 0-RTT for connection resumption. Version 1.3 of DTLS makes similar improvements for TLS over UDP.

Wireguard [20] is a UDP-based encrypted tunnel protocol based on the Noise Protocol Framework [21]. It is a considerably simpler protocol than DTLS, with security improvements and fast, 1-RTT handshakes. However, it requires setting up static tunnels among a fixed set of hosts, and thus it is not suitable for a P2P setting where the network is dynamic and the nodes are not all known before.

For these reasons initially we rely on TLS 1.3 and later DTLS 1.3 once it becomes available.

Interest clustering

As in [4], interest clustering is based on a combination of two gossip protocols, random peer sampling [8] and a similarity-based clustering protocol.

In order to make the peer sampling protocol resilient to attacks [9][11], we employ a stream sampler as specified in [11], which filters out over-represented nodes from a stream of incoming node IDs. The peer sampling protocol also need to limit push from other peers to limit the influence of any one peer. In contrast to [10] which achieves this by using proof of work, we opt for pull-only gossip in order to reduce the computational requirements of the protocol.

The clustering protocol uses Bloom filters to represent subscriptions of a node, as in [5], to make the exchange of subscription information scalable & privacy-protecting. To provide subscription privacy with differential privacy guarantees, we randomize the Bloom filters with random bit flips as described in [13]. The clustering protocol then computes subscription similarity based on the similarity between randomized Bloom filters.

Furthermore, we employ an explicit trust network to bias peer selection both in the peer sampling in clustering protocols, as suggested by [12]. In contrast to [12], we use asymmetric trust values between peers, and omit transmitting trusted paths in the protocol in order to avoid issues regarding exposing trust relationships and values between peers, to make the protocol resilient to malicious nodes trying to spread false information, and to make the protocol simpler.

Routing

In order to route join requests to members of the target topic suboverlay, we need an efficient routing mechanism. Small-world networks have low diameter and provide fast routing and thus would be a desirable structure for the overlay.

To achieve a small-world network topology, as part of the clustering protocol each node maintains a set of fingers (nodes with the most dissimilar interest) that serve as long-distance routing links, in addition to the most similar nodes that provide short-distance routing to nodes with overlapping interest, in a similar fashion to [16]. This prevents the overlay from forming weak bridges (small number of connections between clusters) and keeps the overlay diameter low.

Event dissemination

For event dissemination in suboverlays, UPSYCLE uses a combination of two approaches: deterministic dissemination over a ring with random shortcuts, as described in [4]. This approach is simple and comes with minimal maintenance overhead, while being reasonably efficient in terms of latency and duplication factor.

By minimizing suboverlay maintenance overhead, the system can scale with the number of subscriptions per node, at the expense of being less efficient in terms of latency and duplication factor.

Reliable causal delivery

In order to ensure completeness of dissemination and causal ordering of events, UPSYCLE uses a handful of approaches.

We use causal barriers [22][24] to ensure causal ordering of events in a topic: each event includes its direct dependencies that must be delivered before. If any dependency of an event is not yet received by a node, it needs to explicitly request those from other subscribers of the topic before it can deliver the event. Since event delivery can be delayed due to the different paths events can take, requesting missing dependencies should be only done after a delay, as part of a reactive error recovery mechanism described in [17].

In practice, this means that each event has an ID based on its content hash, and the following header fields that facilitate causal ordering and allow detecting missed messages:

Direct dependencies
List of event IDs that are direct dependencies of this event. This ensures causal delivery.
Concurrent events
List of event IDs that are independent but concurrent to this event. This allows nodes to detect missed events unrelated to the current one, and also serves as an implicit acknowledgement of the receipt of the referenced events.

Explicit acknowledgements can also be used to ensure event delivery, these are empty messages that list the events to be acknowledged as their direct dependencies.

Event synchronization

Synchronization of received events among two peers is necessary in a couple of scenarios. A new subscriber who has just subscribed to a topic may want to receive past events sent to the group. Similarly, rejoining subscribers would want to synchronize events they missed. Furthermore, during normal operation of the dissemination protocol, it might happen that an event is not delivered to a subscriber, which can be detected since causal dependency information is included in each event. In this case one can request missed events from other subscribers of the topic.

Group encryption & membership

We use the decentralized secure group messaging protocol suite described in [19].

The main components of this protocol suite are:

Authenticated Causal Broadcast (ACB)
authenticated messaging service that we use over the P2P pub/sub dissemination channels
Decentralized Group Membership (DGA)
protocol that establishes an eventually consistent membership set with causal ordering despite concurrent membership changes
Two-party Secure Messaging (2SM)
end-to-end secure messaging protocol with PCS
Public Key Infrastructure (PKI)
protocol for retrieving public key material and ephemeral pre-keys for group members
Decentralized Continuous Group Key Agreement (DCGKA)
protocol for deriving keys for group members in response to messages received and membership change events, which keys are subsequently used for group message encryption.

Eventual consistency with causal delivery is a key building block for this protocol suite, as well as public key-addressed user and group identities.

Applied to the two-tier P2P setting, this protocol suite enables end-to-end secure communication channels directly between end-user devices, without proxies being able to decrypt application messages.

Edge networks

Nodes on LANs run the same set of protocols as the core network, but instead of using a peer sampling protocol for discovery that provides a partial view of the network, each node periodically announces its presence on the network by sending its public key to an IP multicast address reserved for this purpose. This allows nodes to construct a full view of the network by listening on this address for peer announcements. From this point on, the rest of the protocols are the same: the clustering protocol can use this full view of the local network to discover peers with overlapping subscriptions and join per-topic suboverlays.

References

[1]
P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M. Kermarrec, “The many faces of publish/subscribe,” ACM computing surveys (CSUR), vol. 35, no. 2, pp. 114–131, 2003 [Online]. Available: https://didattica.uniroma2.it/assets/uploads/corsi/144538/publish-subscribe.pdf
[2]
P. Savolainen, S. Juslenius, E. Andrews, M. Pokrovskii, S. Tarkoma, and H. Pihkala, “The streamr network: Performance and scalability,” 2020 [Online]. Available: http://streamr-public.s3.amazonaws.com/streamr-network-scalability-whitepaper-2020-08-20.pdf
[3]
R. Beraldi, V. Quéma, L. Querzoni, and S. Tucci-Piergiovanni, “TERA: Topic-based event routing for peer-to-peer architectures,” 2007, pp. 2–13, doi: 10.1145/1266894.1266898 [Online]. Available: http://midlab.diag.uniroma1.it/articoli/BBQQT07techrep.pdf
[4]
V. Setty, M. van Steen, R. Vitenberg, and S. Voulgaris, “PolderCast: Fast, robust, and scalable architecture for P2P topic-based pub/sub,” 2012, vol. 7662, pp. 271–291, doi: 10.1007/978-3-642-35170-9_14 [Online]. Available: https://www.distributed-systems.net/my-data/papers/2012.mw.pdf
[5]
J. Patel, É. Rivière, I. Gupta, and A.-M. Kermarrec, “Rappel: Exploiting interest and network locality to improve fairness in publish-subscribe systems,” Computer Networks, vol. 53, pp. 2304–2320, Aug. 2009, doi: 10.1016/j.comnet.2009.03.018. [Online]. Available: https://dprg.cs.uiuc.edu/data/files/2009/rappel_journal.pdf
[6]
C. Chen and Y. Tock, “Design of routing protocols and overlay topologies for topic-based publish/subscribe on small-world networks,” 2015, pp. 1–7, doi: 10.1145/2830013.2830017 [Online]. Available: http://www.msrg.org/publications/pdf_files/2015/MW15ind-Design_of_Routing_Protocols_and_Overl.pdf
[7]
A. Jégou, Harnessing the power of implicit and explicit social networks through decentralization,” Theses, Université Rennes 1, 2014 [Online]. Available: https://tel.archives-ouvertes.fr/tel-01135867/file/JEGOU_Arnaud.pdf
[8]
M. Jelasity, S. Voulgaris, R. Guerraoui, A.-M. Kermarrec, and M. Van Steen, “Gossip-based peer sampling,” ACM Transactions on Computer Systems (TOCS), vol. 25, no. 3, pp. 8–es, 2007 [Online]. Available: https://www.distributed-systems.net/my-data/papers/2007.tocs.pdf
[9]
G. P. Jesi, A. Montresor, and M. van Steen, “Secure peer sampling,” Computer Networks, vol. 54, no. 12, pp. 2086–2098, 2010 [Online]. Available: https://www.distributed-systems.net/my-data/papers/2010.cn-sps.pdf
[10]
E. Bortnikov, M. Gurevich, I. Keidar, G. Kliot, and A. Shraer, “Brahms: Byzantine resilient random membership sampling,” Computer Networks, vol. 53, no. 13, pp. 2340–2359, 2009 [Online]. Available: https://www.cs.technion.ac.il/~gabik/publications/Brahms-COMNET.pdf
[11]
E. Anceaume, Y. Busnel, and B. Sericola, “Uniform node sampling service robust against collusions of malicious nodes,” in 2013 43rd annual IEEE/IFIP international conference on dependable systems and networks (DSN), 2013, pp. 1–12 [Online]. Available: https://hal.archives-ouvertes.fr/hal-00804430/file/paper.pdf
[12]
D. Frey, A. Jégou, A.-M. Kermarrec, M. Raynal, and J. Stainer, “Trust-aware peer sampling: Performance and privacy tradeoffs,” 2013 [Online]. Available: https://hal.inria.fr/docs/00/87/29/96/PDF/Trust-aware-peer-sampling.pdf
[13]
M. Alaggan, S. Gambs, and A.-M. Kermarrec, “BLIP: Non-interactive differentially-private similarity computation on bloom filters,” in Symposium on self-stabilizing systems, 2012, pp. 202–216 [Online]. Available: https://www.academia.edu/download/32383514/Blip-LNCS-Proof.pdf
[14]
M. Nagy, E. de Cristofaro, A. Dmitrienko, N. Asokan, and A.-R. Sadeghi, “Do i know you? – efficient and privacy-preserving common friend-finder protocols and applications.” Cryptology ePrint Archive, Report 2013/620, 2013 [Online]. Available: https://eprint.iacr.org/2013/620
[15]
M. Matos, A. Nunes, R. Oliveira, and J. Pereira, “StAN: Exploiting shared interests without disclosing them in gossip-based publish/subscribe.” in IPTPS, 2010, p. 9 [Online]. Available: https://www.usenix.org/legacy/events/iptps/tech/full_papers/Matos.pdf
[16]
R. Ariyattu and F. Taı̈ani, “Filament: A cohort construction service for decentralized collaborative editing platforms,” 2017 [Online]. Available: https://ftaiani.ouvaton.org/ressources/DAIS17_Filament.pdf
[17]
J. Martori and P. Urso, Reliable causal delivery with probabilistic design,” INRIA Nancy, Research Report RR-8985, Nov. 2016 [Online]. Available: https://hal.inria.fr/hal-01405896/file/article.pdf
[18]
R. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovic, D.-A. Seredinschi, and Y. Vonlanthen, “Scalable byzantine reliable broadcast (extended version),” arXiv preprint arXiv:1908.01738, 2020 [Online]. Available: https://arxiv.org/pdf/1908.01738.pdf
[19]
M. Weidner, M. Kleppmann, D. Hugenroth, and A. R. Beresford, “Key agreement for decentralized secure group messaging with strong security guarantees.” Cryptology ePrint Archive, Report 2020/1281, 2020 [Online]. Available: https://eprint.iacr.org/2020/1281
[20]
J. A. Donenfeld, “WireGuard: Next generation kernel network tunnel.” in NDSS, 2017 [Online]. Available: https://www.wireguard.com/papers/wireguard.pdf
[21]
T. Perrin, “The noise protocol framework,” 2018 [Online]. Available: https://noiseprotocol.org/noise.html
[22]
R. Prakash, M. Raynal, and M. Singhal, “An adaptive causal ordering algorithm suited to mobile computing environments,” Journal of Parallel and Distributed Computing, vol. 41, no. 2, pp. 190–204, 1997 [Online]. Available: https://pdfs.semanticscholar.org/c6e3/ab34b770021c6cca74f4e8dd2c7e1c898b96.pdf
[23]
J. P. de Araujo, L. Arantes, E. P. Duarte Jr, L. A. Rodrigues, and P. Sens, “VCube-PS: A causal broadcast topic-based publish/subscribe system,” Journal of Parallel and Distributed Computing, vol. 125, pp. 18–30, 2019 [Online]. Available: https://arxiv.org/pdf/1706.08302.pdf
[24]
J. P. de Araujo, “A communication-efficient causal broadcast publish/subscribe system,” PhD thesis, 2019 [Online]. Available: https://tel.archives-ouvertes.fr/tel-02105743v2/document