# Topology Protocol
Thomas / guiltygyoza
07-08-2024
## Abstract
We introduce Topology Protocol, a protocol tailored for P2P real-time multiplayer applications. In the spirit of local-first software principles, we introduce a new abstraction called Conflict-free Replicated Object (CRO), leveraging the concurrency, composability, and local-first properties of Conflict-free Replicated Data Types (CRDTs). The protocol specifies a set of methods for interacting with CROs and their corresponding behavior on P2P networks. The use of threshold logical clock can enable snapshot and compaction of the states of CROs, as well as address critical threat models to make them more secure. CROs can be used to make multiplayer virtual environments, open social graphs, and many more to be imagined. Ultimately, the protocol is introducing decentralized Random Access Memory to the landscape of world-scale distributed computing infrastructure.
### Keywords
CRDTs · hash graphs · Byzantine fault tolerance · P2P · threshold logical clock
## Introduction
Multi-user applications on the Internet largely rely on centralized intermediaries to mediate user interactions. While this architecture has seen tremendous success, it suffers a number of problems. Intermediaries dictate who can access what applications when and how, limiting user agency and autonomy. Interoperability among applications is rarely possible because most intermediaries operate on the business model of building and protecting their own network effect.
Blockchains enabled peer-to-peer transactions and general-purpose computation on open networks, yet their reliance on Byzantine consensus mechanisms creates limitations in speed and costs. Operating under the strict serializability model, most modern blockchain networks require global coordination among their geo-distributed nodes to reach consistency. Yet, light only travels a few inches per clock cycle of a modern CPU. Relying on global coordination over the Internet makes the transaction throughput of blockchains heavily communication-bound. Most modern blockchains employ expensive Sybil countermeasures [Tendermint, Casper], creating price floors on transaction fees to pay node operators and limiting these systems to financial use cases.
We believe the open metaverse must operate on open decentralized networks [SIGGRAPH 2019]. The architecture of the networks should be scalable to having millions of participants interact in real time and at negligible costs. New multiplayer software can be deployed, discovered, and accessed, completely free of censorship. These requirements render monolithic blockchains impractical, where the costs of global consensus trickle down to user transaction costs. Turning up the transaction throughput dial increases node resource requirement, making it challenging for most users to participate in the blockchain's P2P network directly. One approach to increase scalability is to shard the network by applications [Cosmos, RGB]. Another approach is to batch total-ordered transactions through rollups before submitting them on blockchains [rollup]. However, the transaction throughput of each shard or rollup remains heavily communication-bound. A network architecture enabling real-time P2P interactions without global coordination may provide a crucial foundation for the open metaverse.
In this paper, we sketch out a solution that leverages the concurrency, composability, and local-first properties of Conflict-free Replicated Data Types (CRDTs). We propose Topology Protocol, a protocol dedicated to P2P applications that are real-time multiplayer, sovereign, running on open networks, and maximizing people's freedom of association on the Internet.
## Conflict-free Replicated Data Types
CRDTs encapsulate coordination-free replication strategies and expose the application programming interface (API) of ordinary data types [CRDT]. Replicas of the same CRDT can progress independently without locks. Conflicts caused by concurrent operations are automatically resolved by rules as part of the specification of the type. As a result, all replicas are guaranteed to converge eventually without ever having to coordinate.
CRDTs are expressive. One approach is to make complex CRDTs from scratch. Although notoriously tricky to get right, correct CRDTs exist for indexed sequence types [Lseq, RGA, YATA, Fugue], XML [XML-CRDT], and JSON [JSON-CRDT]. Another approach is to make complex CRDTs through class composition. A class whose fields are all typed by CRDTs, and whose methods access its fields only through the public methods of their types, is itself a CRDT. This compositionality forms the basis of our proposal.
## Conflict-free Replicated Objects
The primary abstraction of Topology Protocol is *Conflict-free Replicated Object* (CRO). Each CRO is an instance of a *blueprint*. Blueprints can be made with built-in CRDTs recognized by the protocol, and with other blueprints through composition. Blueprints can be created in the developer's programming language of choice, and compiled into suitable bytecode formats to run in nodes on the network. Finally, a blueprint specifies its function signatures in its Application Binary Interface (ABI).
Algorithm 1 shows the pseudocode of a blueprint that implements a simplistic open-access social graph [Farcaster].
**TODO: change in latex Algorithm 2 to 1, title to "Social graph as a CRO"**
[ Algorithm 1 ]
## Hash graphs
To further the expressivity of CROs, we can introduce causal ordering among the operations that are performed on them. Causal order is a partial order that can be enforced in a distributed system without coordination, different from the total order in systems that offer strict serializability. Given an operation history of a CRO, its state is derived from applying the operations in a linear order obtained from topological sort that preserves the causal order. Approaches such as vector clocks and version vectors exist for capturing causality in distributed systems. Yet, these approaches are vulnerable to equivocation, making them unsafe in the presence of Byzantine actors. We need a way to provide causal ordering while tolerating Byzantine faults.
We propose a solution based on hash graphs [BEC, BFT-CRDT, Merkle-CRDTs, Blocklace]. The hash graph approach works by encoding an operation history in a directed acyclic graph, where the edges represent causal relation among the operations, and vertices contain both operations and the hashes of their causal dependencies.
Notationally, let $op$ be an update operation, and $H(\cdot)$ be a suitable hash function. Let $\textbf{F}$ be the hash graph' frontier, or the set of vertices that are parentless. Let $H(\textbf{F})$ be the hashed frontier, or $\{H(e) | e \in \textbf{F}\}$. Let $\textbf{D}$ be the set of hashed vertices that are causal dependencies. For a newly generated $op$, its $\textbf{D}$ equals $H(\textbf{F})$ at the time of generation. We can then define a vertex of a hash graph as containing the tuple $(op, \textbf{D})$. The collision resistance of $H(\cdot)$ ensures that the hash graph contains no cycles. Figure 1 shows an example of hash graph.
(Caption) Figure 1. A hash graph for illustration purposes. Given this hash graph, the vertex $V_7$ should contain $(op_7, \{H(V_4),H(V_5)\})$. The vertices in its frontier $\textbf{F} = \{V_6, V_7, V_8\}$ are circled. For the next vertex to be added to the graph, $V_9$, its causal dependencies should be $H(\textbf{F}) = \{H(V_6), H(V_7), H(V_8)\}$
Using this approach, when two nodes synchronize their operation histories, they effectively merge their hash graphs. Having matching $H(\textbf{F})$ implies having equivalent hash graphs. Operations whose causal dependencies are unrecognizable by honest nodes will not be added to their hash graphs.
As another example, consider a distributed system comprising node A and B, separated by a network delay of 40 ms. Both nodes start from the same initial state, denoted by $\bot$. Each node generates 60 operations per second (≈16.6ms between consecutive operations), a standard frame rate for games, and reconciles its hash graph with the other node as fast as the network conditions permit. Figure 2 shows the hash graphs at node A immediately before and after A generates vertex $A_5$.
(Caption) Figure 2. The hash graphs of node A in a hypothetical system immediately before and after A generates vertex $A_5$. Node A has not learned about the grayed out vertices, $B_4$ and $B_5$
This approach is immune to Sybil attacks. As long as honest nodes form a connected subgraph in the P2P network, the system is able to function correctly. This allows CROs to tolerate arbitrarily many Sybil actors, hence the immunity. In contrast, systems with global Byzantine consensus functions correctly only if less than one third of the nodes are faulty. No expensive countermeasures are involved, making the costs of transacting with such CRDTs practically zero.
## Signaling
CROs interact by *signaling*, a CRO-level term to differentiate from messaging at the network layer. A signal originates from an operation at the sender CRO, and materializes into an operation at the receiver CRO. For causality to work, a signal needs to specify its causal dependencies in both the sender CRO and receiver CRO's hash graph. This means the node that intends to send the cross-object signal needs to have the hash graphs of both the sender and receiver CROs locally.
Figure 3 illustrates such a signal diagrammatically, where the signal “glues” together its originating operation on the sender CRO side and the operation it materializes into on the receiver CRO side.
(Caption) Figure 3. Hash graphs of CRO $X$, $Y$, $Z$ interacting by passing signals. Cross-object signals are denoted as dotted arrows. Cross-object causal dependencies are denoted as dashed pointers. The vertices where signals are originated are enclosed in diamonds, whereas those on the receiving sides are enclosed in squares. In this example, the generation of vertex $X_4$ also produces a signal to object $Y$, materializing into vertex $Y_6$. Signaling also occurred between vertices $Y_7$ and $Z_2$. The causal dependencies of $Y_6$ is $X_2$, $X_3$, and $Y_3$. The causal dependencies of $Z_2$ is $Y_4$, $Y_5$, $Y_6$, and $Z_1$.
## Interaction methods
Topology Protocol defines a set of methods, or simply *verbs*, for nodes to interact with a given CRO. At the core of the protocol is the publish/subscribe (PubSub) model for nodes in P2P networks to subscribe to CROs and publish updates on them asynchronously. CROs are identified as PubSub groups or topics. Nodes only subscribe to CROs they are interested in. This keeps CROs loosely coupled and helps reduce memory and bandwidth requirement for operating nodes. Figure 4 illustrates this interaction pattern.
(Caption) Figure 4. Alice, Bob, and Charlie are subscribed to CRO $D$. Alice, Bob, Dave, and Eve are subscribed to CRO $B$. All nodes are connected peer-to-peer.
The set of core interaction methods and their semantics is as follows:
1. **CREATE**: to announce the existence of a newly created CRO. Under the hood, a PubSub group (topic) is created for the new CRO.
2. **UPDATE**: to perform an update on a given CRO. The update is published to the corresponding group.
3. **SUBSCRIBE**: to subscribe to all updates performed on a given CRO. The node adds the corresponding group to its groups of interest.
4. **UNSUBSCRIBE**: to unsubscribe and stop receiving updates on a given CRO. The node removes the corresponding group from its groups of interest.
5. **SYNC**: to reconcile the differences the local operation history (hash graph) of a given CRO and a remote one. The SYNC method has two main purposes: for a new node to bootstrap into an existing CRO, and as an out-of-band synchronization method besides P2P gossiping.
SYNC can take a long time to complete when a node is bootstrapping into a CRO with a large-sized history. This can be viewed as a problem of set reconciliation. One common approach is to exchange bloom filters to reduce the message complexity of the sync process. A more promising approach is proposed recently to have constant overhead even when reconciling sets with very large difference [PRIBLT].
## Snapshot
A CRO snapshot is a single hash graph that represents an agreement among the CRO's replicas. Snapshots are useful in multiple ways. They can serve as "state saves" to be persisted somewhere (e.g. IPFS [IPFS]). Since these saves represent finalized agreement among replicas, they can be used to generate irreversible transactions on blockchains.
The computation of snapshots faces several problems. We must avoid involving "all nodes" in the algorithm: unanimity can be very problematic due to network conditions, dynamic membership, and Byzantine behavior. The algorithm needs to run concurrently to the underlying CRO activities without hindering or suspending them. The algorithm must complete with reasonable bandwidth consumption, thus the nodes involved must not send entire replicas over the wire.
Our current solution builds on threshold logical clock (TLC) [TLC] as a decentralized pacemaker, on top of which consensus can be reached. Each CRO has its own TLC operated by its subscriber nodes. When a node is ready to advance the TLC tick, it proposes the hashed frontier ($H(\textbf{F})$) of its own hash graph by broadcasting it to other subscribers. Instead of unanimity, the tick advances by threshold amounts of subscriber nodes signing and acknowledging messages. Three consecutive ticks can be used to form a consensus round, yielding a snapshot. The process runs continuously, allowing snapshots to be taken periodically. CRO snapshot remains an active area of research. The algorithms and their configurability supported by the protocol remain to be determined through the protocol development process.
## Compaction
Grow-only hash graphs are problematic. Unbounded memory is needed, and large graphs take longer to synchronize for new nodes. Compaction serializes the state of a CRDT by applying the operations carried by a portion of the hash graph before pruning that portion away. Compaction discards causal information and thus is perfectly safe only when performed over causally stable vertices in the hash graph [PO-CRDT]. To illustraste this, Figure 5 shows a hash graph before and after a safe compaction with vertices $F$ and $G$ confirmed to be causally stable: all future operations will have happened-after $F$ or $G$.
(Caption) Figure 5. Compaction is performed on the subgraph that precedes $F$ and $G$, the nodes that are causally stable and marked with asterisks. $S'$ is computed by applying the operations in the subgraph on $S$ in a linear order obtained from topological sort.
However, perfectly safe compaction can be impractical. A node can be certain that an operation $op$ is causally stable when it has received an operation from every other node that causally supercedes $op$. This involves the notion of "all nodes", our usual suspect. Our current solution is to use the TLC consensus rounds to drive compaction. Each round yields a hash graph, whose frontier $\textbf{F}$ comprises vertices that are considered causally stable. All preceding vertices can be compacted. The CRO's state is forwarded by applying the operations of those compacted vertices in a linear order obtained from topological sort.
Unsafe compaction is so named because it may drop causal information in the hash graph that is needed to recognize the causality of operations that have yet to arrive from the network. Thus, operations with unrecognizable causality could come from both honest and Byzantine nodes. Existing approaches from Tusk [Tusk] and Bullshark [Bullshark] choose to re-inject transactions in a later consensus round. These approaches aim to preserve some notion of fairness, ensuring that transactions generated by correct nodes are eventually delivered to all other correct nodes. However, re-injected transactions lose their original causal dependencies, requiring rewriting on top of the hash graph frontier from the previous consensus round. A consistent, deterministic policy for rewriting dependencies is needed. Compaction remains an active area of research.
However, re-injected transactions will not preserve their original causal dependencies. Their dependencies need to be rewritten on top of the frontier of the hash graph from the previous consensus round. For CROs whose semantics depend on causal ordering among operations, a deterministic policy is needed for all correct nodes to rewrite the dependencies of re-injected operations in a consistent manner. Compaction is another active area of research.
Revisiting the snapshot problem, we can see the undesirability of producing grow-only snapshots. Using compaction, we can shrink the size of snapshot. This is particularly valuable when snapshots are to be stored on blockchains, where storage is expensive.
It is possible to produce compacted snapshots that are verifiable, which are useful in scenarios where trust needs to be minimized. A compacted snapshot is verifiable when anyone can verify that (1) consensus was reached correctly (2) compaction was performed correctly. For the consensus part, we can require the proposals in each round to contain the hash of the agreed upon proposal and the aggregated signatures from the previous round. This effectively forms a chain. Verifying the aggregated signatures at the tip of the chain verifies the entire chain. For the compaction part, we can require the blueprint to be executable by a provable VM such as Cairo [Cairo], RISC0 [RISC0], Valida [Valida], and SP1 [SP1]. The state forwarding step of compaction can be proven, yielding a validity proof that sits alongside the snapshot.
## Access control
Access control is important for multiplayer applications. Social and communal spaces are much more useful when fine-grained permissions can be assigned to participants. Common access control models include level-based (lattice-based) [LBAC] and rule-based ones [RBAC]. It gets tricky when a CRO's access control logic is specified within itself or another CRO, due to eventual consistency. What happens when an operation that changes the permission level or role of a participant is concurrent to an operation generated by the same participant that depends on having the level or role assigned?
The core issue here is conflict resolution strategy that involves permission changes. A promising solution is proposed in [Matrix], where both permission roles or levels and the causal order among vertices are taken into account to topologically sort a hash graph. The solution works under the assumption that participants with higher permission roles or levels are not attackers. Another promising direction is to leverage the TLC to establish a linear order between permission-changing operations and permission-dependent operations. A CRO may require that permission-changing operations are ineffective until the next TLC tick.
## Security
Hash graphs can be polluted by vertices with garbage payload such as invalid operations. When receiving a new vertex, a node can validate its operation before adding it to the local hash graph. The nodes that published bad operations can be banned. If an operation can be validated atomically, we can be certain that all honest nodes will reach the same conclusion. It is trickier when the validity of the operation depends on the operations that happened before it. In this case, we can define operation validity as a function of the operation itself and all operations that can be transitively reached through the causal dependencies in the hash graph.
Equivocation is another threat model, under the assumption that a node is considered a single-threaded process and should never generate concurrent operations. An honest node can detect that another node has generated concurrent operations. The honest node may choose to remove the corresponding bad vertices from its hash graph, ban the Byzantine node, and expect all other honest nodes to do the same. However, downstream vertices that causally depend on these bad vertices may have been generated. It is not obvious how to graft these downstream vertices back to the hash graph. Equivocation tolerance remains an active area of research.
The trickiest threat model may be backdated dependencies: when nodes report dependencies that are older than the vertices in the frontier. The question is how can backdated dependencies be reliably detected by all honest nodes. A vertex with correct dependencies but arriving late due to network delays is indistinguishable from a vertex with backdated dependencies. One promising direction is to leverage the TLC as it introduces a notion of linear time. Denote the frontier of the hash graph from the latest TLC-based consensus round as $\textbf{F}_{-1}$. A CRO can stipulate that a vertex should not report causal dependencies that causally precede any of the vertices in $\textbf{F}_{-1}$, otherwise the vertex will be handled according to some policy that is applied consistently across all honest nodes. As such, the TLC serves as a security clock for the CRO, whose $\textbf{F}_{-1}$ serves as the backstop for backdated dependencies.
## Decentralized random access memory
A perspective we found compelling is that Topology Protocol brings "decentralized random access memory" to the table. The following properties of the protocol support this perspective:
1. **Random access**. Users can synchronize on any CROs of interest without having to synchronize every single CRO in the system, contrary to smart contracts on blockchains. This access pattern reduces the memory requirement of running a protocol node.
2. **Closeness to compute**. We envision that most users of CRO-powered applications will operate nodes on their devices, holding CRO replicas locally. In other words, the protocol champions the principles of local-first software [LoFi]. In constrast, most blockchain users access smart contracts via centralized RPC nodes, not unlike the access pattern of most cloud apps. This property is analogous to the role random access memory serves in a memory hierarchy.
3. **Ephemerality**. Persistence of CROs is out of scope of the protocol. The protocol expects the nodes to be ephemeral. Their states are volatile from the system's perspective, corresponding to the volatility of RAM. The data movement between Topology nodes and persistence providers is analagous to the data movement between RAM and disk memory which is non-volatile.
## Conclusion
In this paper, we introduced CRO and Topology Protocol for P2P real-time multiplayer applications. CRDT is a natural choice for such use cases, and the use of hash graphs allows capturing causality among operations while tolerating Byzantine faults. CRO provides the programmability of common object systems and encapsulates coordination-free replication strategies. Topology Protocol specifies a set of interaction methods for CROs to be created, updated, subscribed to, unsubscribed from, and synchronized. Their semantics correspond to behavior on the underlying P2P networks under the publish/subscribe model. Snapshot, compaction, access control, and threat models of CROs were addressed. Nodes that implement Topology Protocol keep replicas of CROs locally, bear no responsibility in persistence, and disseminate CRO updates only to nodes that are interested in them. As such, a P2P network comprised of such nodes effectively works as a decentralized random access memory. Finally, snapshot verifiability is possible with CROs, enabling trust-minimized use cases.
### Acknowledgement
We acknowledge Jihoon Song and Kunho Kim for the original discussions that motivated this paper. We appreciate the patience and feedback from Martin Kleppmann, Oskar Thorén, Matthew Weidner, Brooklyn Zelenka, Bartosz Sypytkowski, James Addison, Anderson Chen, Lev Stambler, Joon Yun, Jay Oak, Matthew Demoy, Pierre Semanne, Gregory Edison, Yu Yen, Martinet Lee, Ole Spjeldnæs, Justin Glibert, Zaki Manian, Alok Vasudev, Adam Goldberg, Colin Hong, Eric Wei, Peteris Erins, Wei Dai, Ventali Tan, Michael Gao, Ion Jo, Billy Rennekamp, Ben Jay Amin.
### Reference
[Bitcoin] https://bitcoin.org/bitcoin.pdf
[Tendermint] https://tendermint.com/static/docs/tendermint.pdf
[Casper] https://arxiv.org/abs/1710.09437
[SIGGRAPH 2019] https://blog.siggraph.org/2019/10/siggraph-spotlight-episode-30-tim-sweeney-and-the-metaverse.html/
[Cosmos] https://whitepaper.io/document/582/cosmos-whitepaper
[RGB] https://blackpaper.rgb.tech/
[rollup] https://vitalik.eth.limo/general/2021/01/05/rollup.html
[CRDT] https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf
[Lseq] https://hal.science/file/index/docid/921633/filename/fp025-nedelec.pdf
[RGA] https://www.sciencedirect.com/science/article/abs/pii/S0743731510002716
[YATA] https://dl.acm.org/doi/10.1145/2957276.2957310
[Fugue] https://arxiv.org/abs/2305.00583
[XML-CRDT] https://arxiv.org/abs/1010.3615
[JSON-CRDT] https://arxiv.org/abs/1608.03960
[BEC] https://arxiv.org/pdf/2012.00472.pdf
[BFT-CRDT] https://martin.kleppmann.com/papers/bft-crdt-papoc22.pdf
[Merkle-CRDTs] https://research.protocol.ai/publications/merkle-crdts-merkle-dags-meet-crdts/psaras2020.pdf
[Blocklace] https://arxiv.org/pdf/2402.08068.pdf
[Farcaster] https://github.com/farcasterxyz/protocol
[GossipSub] https://research.protocol.ai/blog/2019/a-new-lab-for-resilient-networks-research/PL-TechRep-gossipsub-v0.1-Dec30.pdf
[PRIBLT] https://arxiv.org/pdf/2402.02668
[IPFS] https://arxiv.org/pdf/1407.3561.pdf
[TLC] https://arxiv.org/pdf/1907.07010.pdf
[PO-CRDT] https://arxiv.org/pdf/1710.04469
[Tusk] https://arxiv.org/pdf/2105.11827.pdf
[Bullshark] https://arxiv.org/pdf/2201.05677.pdf
[Cairo] https://eprint.iacr.org/2021/1063.pdf
[RISC0] https://dev.risczero.com/proof-system-in-detail.pdf
[Valida] https://github.com/valida-xyz/valida
[SP1] https://github.com/succinctlabs/sp1
[LoFi] https://www.inkandswitch.com/local-first/
[LBAC] Ravi S. Sandhu. 1993. Lattice-based access control models. Computer, 26, 11, 9–19. https://profsandhu.com/journals/computer/i93lbacm(org).pdf
[RBAC] Ravi S Sandhu, Edward J Coyne, Hal L Feinstein, and Charles E Youman. 1996. Role-based access control models. Computer, 29, 2, 38–47. https://csrc.nist.gov/CSRC/media/Projects/Role-Based-Access-Control/documents/sandhu96.pdf
[Matrix] Matrix Decomposition: Analysis of an Access Control Approach on Transaction-based DAGs without Finality. https://dl.acm.org/doi/10.1145/3381991.3395399
Sign in with Wallet
Connect another wallet