P2P Network The Graph implements a structured overlay network which builds on ideas from Content-Addressable Networks (CANs) such as IPFS3 and BitTorrent4. We introduce the concept of a Service-Addressable Network to describe our formulation; the key difference is that while CANs leverage distributed hash tables (DHTs) to locate nodes on the network storing a specic le or object5, our P2P network is used to locate nodes capable of providing a particular service, which can be any arbitrary computational work. The design of our P2P network sub-protocol is modular with respect to the service being provided, a fact which we take advantage of in other parts of the protocol stack. Figure 3: Service-Addressable Network 3Juan Benet, IPFS Content Addressed, Versioned, P2P File System (DRAFT 3), IPFS, March 5, 2018, 4Andrew Lowenstern and Arvid Norberg, DHT Protocol, BitTorrent.org, May 1,

0005.html 5Sylvia Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, A Scalable Content-Addressable Network, Proceedings of ACM SIGCOMM, August 2001, 7 2017, Query Processing The Query Processing is split into ve distinct stages: Query Splitting, Service Discovery, Query Routing, Nested Query Processing and Response Collation. Query Splitting The rst step of the Query Processing sub-protocol is to split a query into disjoint top-level Query Fragments, which may correspond to multiple Data Sources. A Query Fragment is any part of a query that can be resolved on its own. These fragments are processed separately, moving through the subsequent Query Processing stages in parallel.

Service Discovery In the Service Discovery stage, we leverage our Service-Addressable Network, to locate a P2P Node, with a routing table corresponding to a specic Service Group, as shown in Figure 4. In the context of this sub-protocol we dene the Service Group to be a group of Query Nodes capable of processing a query for a specic Data Source. Figure 4: The Service Discovery stage. 8 Query Routing In the Query Routing stage, the Gateway Node that originated the query6 decides which Query Node to forward a specic Query Fragment to, as shown in Figure 5. The Query Routing stage uses the Service Group Routing Table, which contains the location of each Node in the Service Group, as well as additional metadata.

Figure 5: The Query Routing stage. The metadata in the Service Group Routing Table is extensible to support modular routing logic. We take advantage of this in the Query Marketplace sub-protocol, but it could also be used to support operating the protocol in local networks or with trusted nodes, where payment requirements may be undesirable. Nested Query Processing Each Query Fragment corresponds to a single entity type that is indexed by The Graph. If the user wishes to traverse nested entity relationships, these are processed as separate Query Fragments which go through the steps listed above. Queries may be arbitrarily deep, and thus are processed recursively, in serial until all the Query Fragments are processed. 6From the perspective of the network, it is impossible to distinguish whether a Gateway Node originated a query itself, or on behalf of a dApp client. 9