CINXE.COM

<!doctype html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <link rel="stylesheet" href="/css/layout.css?1718759055581"> <link rel="stylesheet" href="/css/nav.css?1718759055581"> <link rel="stylesheet" href="/css/style.css?1718759055581"> <link rel="stylesheet" href="/css/prismjs@1.24-themes-prism.css"> <title>IPLD ♦ Graphsync</title> </head> <body> <header> <div class="sidebar-button" onclick="document.getElementById('sidebar').classList.toggle('sidebar-open')"> <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"> <path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path> </svg> </div> <a href="/" class="logo">IPLD</a> <aside id=breadcrumbs> <ul> <li><a href="/specs">specs</a></li> <li><a href="/specs/transport">transport</a></li> <li><a href="/specs/transport/graphsync/">graphsync</a></li> </ul> </aside> </header> <aside id=sidebar> <nav> <ul> <li> <a href="/docs/">Docs</a><ul> <li> <a href="/docs/intro/">Intro</a><ul> <li> <a href="/docs/intro/hello-world/">Hello, World</a></li> <li> <a href="/docs/intro/primer/">The Brief Primer</a></li> <li> <a href="/docs/intro/ecosystem/">InterPlanetary Ecosystem Overview</a></li> <li> <a href="/docs/intro/community/">Finding Community</a></li></ul></li> <li> <a href="/docs/motivation/">Motivation</a><ul> <li> <a href="/docs/motivation/benefits-of-content-addressing/">Benefits of Content Addressing</a></li> <li> <a href="/docs/motivation/data-to-data-structures/">From Data to Data Structures</a></li></ul></li> <li> <a href="/docs/codecs/">Codecs</a><ul> <li> <a href="/docs/codecs/known/">Known Codecs</a><ul> <li> <a href="/docs/codecs/known/dag-cbor/">DAG-CBOR</a></li> <li> <a href="/docs/codecs/known/dag-json/">DAG-JSON</a></li> <li> <a href="/docs/codecs/known/dag-pb/">DAG-PB</a></li></ul></li></ul></li> <li> <a href="/docs/data-model/">Data Model</a><ul> <li> <a href="/docs/data-model/node/">Nodes</a></li> <li> <a href="/docs/data-model/kinds/">Kinds</a></li> <li> <a href="/docs/data-model/pathing/">Pathing</a></li> <li> <a href="/docs/data-model/traversal/">Traversal</a></li></ul></li> <li> <a href="/docs/advanced-data-layouts/">Advanced Data Layouts</a><ul> <li> <a href="/docs/advanced-data-layouts/intro/">Intro to ADLs</a></li> <li> <a href="/docs/advanced-data-layouts/naming/">ADL Naming</a></li> <li> <a href="/docs/advanced-data-layouts/signalling/">Signalling ADLs</a></li> <li> <a href="/docs/advanced-data-layouts/dynamic-loading/">Dynamic Loading</a></li> <li> <a href="/docs/advanced-data-layouts/known/">Known ADLs</a></li></ul></li> <li> <a href="/docs/schemas/">Schemas</a><ul> <li> <a href="/docs/schemas/intro/">Introduction</a><ul> <li> <a href="/docs/schemas/intro/compare/">compare</a></li> <li> <a href="/docs/schemas/intro/goals/">Goals</a></li> <li> <a href="/docs/schemas/intro/feature-summary/">Feature Summary</a></li></ul></li> <li> <a href="/docs/schemas/features/">Features</a><ul> <li> <a href="/docs/schemas/features/typekinds/">Type Kinds</a></li> <li> <a href="/docs/schemas/features/representation-strategies/">Representation Strategies</a></li> <li> <a href="/docs/schemas/features/links/">Links</a></li> <li> <a href="/docs/schemas/features/indicating-adls/">Using ADLs in Schemas</a></li></ul></li> <li> <a href="/docs/schemas/using/">Using Wisely</a><ul> <li> <a href="/docs/schemas/using/authoring-guide/">Authoring Guide</a></li> <li> <a href="/docs/schemas/using/migrations/">Migrations</a></li></ul></li></ul></li> <li> <a href="/docs/synthesis/">Synthesis</a><ul> <li> <a href="/docs/synthesis/gtd/">Getting Things Done</a></li> <li> <a href="/docs/synthesis/building-in-alignment/">Building in Alignment</a></li> <li> <a href="/docs/synthesis/how-ipfs-web-gateways-work/">How IPFS Web Gateways Work</a></li> <li> <a href="/docs/synthesis/encryption/">Working With Encryption</a></li></ul></li></ul></li> <li> <a href="/specs/">Specs</a><ul> <li> <a href="/specs/about/">About the Specifications</a></li> <li> <a href="/specs/codecs/">Codecs</a><ul> <li> <a href="/specs/codecs/dag-cbor/">DAG-CBOR</a><ul> <li> <a href="/specs/codecs/dag-cbor/fixtures/">DAG-CBOR Test Fixtures</a><ul> <li> <a href="/specs/codecs/dag-cbor/fixtures/cross-codec/">cross-codec</a></li></ul></li> <li> <a href="/specs/codecs/dag-cbor/spec/">Spec</a></li></ul></li> <li> <a href="/specs/codecs/dag-cosmos/">DAG-COSMOS</a><ul> <li> <a href="/specs/codecs/dag-cosmos/basic_types/">basic_types</a></li> <li> <a href="/specs/codecs/dag-cosmos/cosmos_state/">cosmos_state</a></li> <li> <a href="/specs/codecs/dag-cosmos/crypto_types/">crypto_types</a></li> <li> <a href="/specs/codecs/dag-cosmos/tendermint_chain/">tendermint_chain</a></li> <li> <a href="/specs/codecs/dag-cosmos/typed_protobuf/">typed_protobuf</a></li></ul></li> <li> <a href="/specs/codecs/dag-eth/">DAG-ETH</a><ul> <li> <a href="/specs/codecs/dag-eth/basic_types/">basic_types</a></li> <li> <a href="/specs/codecs/dag-eth/chain/">chain</a></li> <li> <a href="/specs/codecs/dag-eth/convenience_types/">convenience_types</a></li> <li> <a href="/specs/codecs/dag-eth/state/">state</a></li></ul></li> <li> <a href="/specs/codecs/dag-jose/">DAG-JOSE</a><ul> <li> <a href="/specs/codecs/dag-jose/fixtures/">fixtures</a></li> <li> <a href="/specs/codecs/dag-jose/spec/">Spec</a></li></ul></li> <li> <a href="/specs/codecs/dag-json/">DAG-JSON</a><ul> <li> <a href="/specs/codecs/dag-json/fixtures/">DAG-JSON Test Fixtures</a><ul> <li> <a href="/specs/codecs/dag-json/fixtures/cross-codec/">cross-codec</a></li></ul></li> <li> <a href="/specs/codecs/dag-json/spec/">Spec</a></li></ul></li> <li> <a href="/specs/codecs/dag-pb/">DAG-PB</a><ul> <li> <a href="/specs/codecs/dag-pb/fixtures/">DAG-PB Test Fixtures</a><ul> <li> <a href="/specs/codecs/dag-pb/fixtures/cross-codec/">cross-codec</a></li></ul></li> <li> <a href="/specs/codecs/dag-pb/spec/">Spec</a></li></ul></li></ul></li> <li> <a href="/specs/advanced-data-layouts/">Advanced Data Layouts</a><ul> <li> <a href="/specs/advanced-data-layouts/fbl/">FBL ADL</a><ul> <li> <a href="/specs/advanced-data-layouts/fbl/spec/">spec</a></li></ul></li> <li> <a href="/specs/advanced-data-layouts/hamt/">HAMT ADL</a><ul> <li> <a href="/specs/advanced-data-layouts/hamt/fixture/">HashMap (HAMT) Test Fixtures</a><ul> <li> <a href="/specs/advanced-data-layouts/hamt/fixture/alice-words/">alice-words</a></li></ul></li> <li> <a href="/specs/advanced-data-layouts/hamt/spec/">spec</a></li></ul></li></ul></li> <li> <a href="/specs/schemas/">Schemas</a><ul> <li> <a href="/specs/schemas/prelude/">prelude</a></li></ul></li> <li> <a href="/specs/transport/">Transports</a><ul> <li> <a href="/specs/transport/car/">CAR</a><ul> <li> <a href="/specs/transport/car/carv1/">CARv1 Specification</a></li> <li> <a href="/specs/transport/car/carv2/">CARv2 Specification</a></li> <li> <a href="/specs/transport/car/fixture/">CAR Test Fixtures</a><ul> <li> <a href="/specs/transport/car/fixture/carv1-basic/">carv1-basic</a></li> <li> <a href="/specs/transport/car/fixture/carv2-basic/">carv2-basic</a></li></ul></li></ul></li> <li class="active-page"> <a href="/specs/transport/graphsync/">Graphsync</a><ul> <li> <a href="/specs/transport/graphsync/known_extensions/">known_extensions</a></li></ul></li> <li> <a href="/specs/transport/trustless-pathing/">Trustless Pathing</a><ul> <li> <a href="/specs/transport/trustless-pathing/fixtures/">Trustless Pathing Fixtures</a><ul> <li> <a href="/specs/transport/trustless-pathing/fixtures/unixfs_20m_variety/">unixfs_20m_variety</a></li></ul></li></ul></li></ul></li> <li> <a href="/specs/selectors/">Selectors</a><ul> <li> <a href="/specs/selectors/fixtures/">fixtures</a><ul> <li> <a href="/specs/selectors/fixtures/selector-fixtures-1/">selector-fixtures-1</a></li> <li> <a href="/specs/selectors/fixtures/selector-fixtures-adl/">selector-fixtures-adl</a></li> <li> <a href="/specs/selectors/fixtures/selector-fixtures-recursion/">selector-fixtures-recursion</a></li></ul></li></ul></li> <li> <a href="/specs/patch/">Patch</a><ul> <li> <a href="/specs/patch/fixtures/">IPLD Patch Test Fixtures</a><ul> <li> <a href="/specs/patch/fixtures/fixtures-1/">fixtures-1</a></li></ul></li></ul></li></ul></li> <li> <a href="/libraries/">Libraries</a><ul> <li> <a href="/libraries/golang/">Golang</a></li> <li> <a href="/libraries/javascript/">JavaScript</a></li> <li> <a href="/libraries/python/">Python</a></li> <li> <a href="/libraries/rust/">Rust</a></li></ul></li> <li> <a href="/design/">Design</a><ul> <li> <a href="/design/objectives/">Objectives</a></li> <li> <a href="/design/concepts/">Concepts</a><ul> <li> <a href="/design/concepts/type-theory-glossary/">type-theory-glossary</a></li></ul></li> <li> <a href="/design/libraries/">Libraries</a><ul> <li> <a href="/design/libraries/nodes-and-kinds/">nodes-and-kinds</a></li></ul></li> <li> <a href="/design/tricky-choices/">Tricky Choices</a><ul> <li> <a href="/design/tricky-choices/dag-pb-forms-impl-and-use/">dag-pb-forms-impl-and-use</a></li> <li> <a href="/design/tricky-choices/map-key-domain/">map-key-domain</a></li> <li> <a href="/design/tricky-choices/numeric-domain/">numeric-domain</a></li> <li> <a href="/design/tricky-choices/ordering/">ordering</a></li> <li> <a href="/design/tricky-choices/string-domain/">string-domain</a></li></ul></li> <li> <a href="/design/open-research/">Open Research</a><ul> <li> <a href="/design/open-research/ADL-autoexecution/">ADL autoexecution</a></li></ul></li></ul></li> <li> <a href="/tools/">Tools</a></li> <li> <a href="/glossary/">Glossary</a></li> <li> <a href="/media/">Media</a></li> <li> <a href="/FAQ/">FAQ</a></li></ul> </nav> </aside> <main> <div class=content> <h1>Graphsync</h1> A protocol to synchronize graphs across peers. Graphsync uses <a href="/specs/selectors/">IPLD Selectors</a> to effeciently transfer graphs (or selections of parts of graphs) with a minimal number of independent requests, and thus seeks to attain low overhead for high latency situations. <h2 id="[meta-status-of-this-doc]" tabindex="-1"><a class="header-anchor" href="#[meta-status-of-this-doc]">[Meta: Status of this doc]</a></h2> <ul> <li>This was written around 2018-10-16 (<a href="https://drive.google.com/file/d/1NbbVxZQFKXwW6mdodxgTaftsI8eID-c1/view">video presentation</a>)</li> <li>This document is unfortunately far from complete.</li> <li>But this document provides enough information for an implementation to be made by someone who has already implemented bitswap (or understands it well).</li> <li>It relies heavily on an understanding of bitswap as it is now. It likely won't be useful to people without a good understanding of how Bitswap works at the moment.</li> <li>This requires IPLD Selectors to exist and be implemented.</li> </ul> <h2 id="concepts-and-glossary" tabindex="-1"><a class="header-anchor" href="#concepts-and-glossary">Concepts and Glossary</a></h2> <ul> <li><code>peer</code> - a program or process participating in the graphsync protocol. It can connect to other peers.</li> <li><code>graph</code> - an authenticated directed acyclic graph (DAG) of content. an IPLD dag. consists of nodes with hash (content addressed, authenticated) links to other nodes. ($$ G $$)</li> <li><code>dag</code> - a directed acyclic graph. For our purposes, our DAGs are all IPLD (connected by hash links, authenticated, content addressed, etc.)</li> <li><code>selector</code> - an expression that identifies a specific subset of a graph. ($$ S(G) \subset G $$)</li> <li><code>selector language</code> - the language defining a family of selectors</li> <li><code>request</code> - a request for content from one <code>peer</code> to another. This is similar to HTTP, RPC, or API requests.</li> <li><code>response</code> - the content sent from <code>responder</code> to <code>requester</code> fulfilling a <code>request</code>.</li> <li><code>requester</code> - the peer which initiates a <code>request</code> (wants content).</li> <li><code>responder</code> - the peer receiving a <code>request</code>, and providing content in a <code>response</code> (provides content).</li> <li><code>request process</code> - a request and its fulfillment is a sub-process, a procedure call across peers with the following phases (at a high level): <ul> <li>(1) The <code>requester</code> initiates by sending a request message (<code>req</code>) to the <code>responder</code>, specifying desired content and other request parameters.</li> <li>(2) Upon receiving a request message, the <code>responder</code> adds the request to a set of active requests, and starts processing it.</li> <li>(3) The <code>responder</code> fulfills the request by sending content to the <code>requester</code> (the <code>response</code>) .</li> <li>(4) The <code>responder</code> and <code>requester</code> can terminate the request process at any time.</li> <li>Notes: <ul> <li>We are explicitly avoiding the <code>client-server</code> terminology to make it clear that <code>requester</code> and <code>responder</code> are "roles" that any peer might play, and to avoid failing in the two-sided client-server model of the web..</li> <li><code>requests</code> may be short or long-lived -- requests may be as short as microseconds or last indefinitely.</li> </ul> </li> </ul> </li> <li><code>priority</code> - a numeric label associated with a <code>request</code> implying the relative ordering of importance for requests. This is a <code>requester's</code> way of expressing to a <code>responder</code> the order in which the <code>requester</code> wishes the <code>requests</code> to be fulfilled. The <code>responder</code> SHOULD respect <code>priority</code>, though may return <code>responses</code> in any order.</li> </ul> <h2 id="interfaces" tabindex="-1"><a class="header-anchor" href="#interfaces">Interfaces</a></h2> This is a listing of the data structures and process interfaces involved in the graphsync protocol. For simplicity, we use Go type notation, though of course graphsync is language agnostic. <pre class="language-go"><code class="language-go">type Graphsync interface { Request(req Request) (Response, error) } type Request struct { Selector Selector Priority Priority // optional Expires time.Duration // optional } type GraphSyncNet interface { SendMessage(m Message) RecvMessage(m Message) }</code></pre> <h2 id="network-messages" tabindex="-1"><a class="header-anchor" href="#network-messages">Network Messages</a></h2> <pre class="language-protobuf"><code class="language-protobuf">message GraphsyncMessage { message Request { int32 id = 1; // unique id set on the requester side bytes root = 2; // a CID for the root node in the query bytes selector = 3; // ipld selector to retrieve map<string, bytes> extensions = 4; // side channel information int32 priority = 5; // the priority (normalized). default to 1 bool cancel = 6; // whether this cancels a request bool update = 7; // whether this is an update to an in progress request } message Response { int32 id = 1; // the request id int32 status = 2; // a status code. map<string, bytes> extensions = 3; // side channel information } message Block { bytes prefix = 1; // CID prefix (cid version, multicodec and multihash prefix (type + length) bytes data = 2; } // the actual data included in this message bool completeRequestList = 1; // This request list includes *all* requests, replacing outstanding requests. repeated Request requests = 2; // The list of requests. repeated Response responses = 3; // The list of responses. repeated Block data = 4; // Blocks related to the responses }</code></pre> <h3 id="extensions" tabindex="-1"><a class="header-anchor" href="#extensions">Extensions</a></h3> The Graphsync protocol is extensible. A graphsync request and a graphsync response contain an <code>extensions</code> field, which is a map type. Each key of the extensions field specifies the name of the extension, while the value is data (serialized as bytes) relevant to that extension. Extensions help make Graphsync operate more efficiently, or provide a mechanism for exchanging side channel information for other protocols. An implementation can choose to support one or more extensions, but it does not have to. A list of well known extensions is found <a href="./known_extensions/">here</a> <h3 id="updating-requests" tabindex="-1"><a class="header-anchor" href="#updating-requests">Updating requests</a></h3> A client may send an updated version of a request. An update contains ONLY extension data, which the responder can use to modify an in progress request. For example, if a responder supports the Do Not Send CIDs extension, it could choose to also accept an update to this list and ignore CIDs encountered later. It is not possible to modify the original root and selector of a request through this mechanism. If this is what is needed, you should cancel the request and send a new one. The update mechanism in conjunction with the paused response code can also be used to support incremental payment protocols. <h3 id="response-status-codes" tabindex="-1"><a class="header-anchor" href="#response-status-codes">Response Status Codes</a></h3> <pre><code># info - partial 10 Request Acknowledged. Working on it. 11 Additional Peers. PeerIDs in extra. 12 Not enough vespene gas ($) 13 Other Protocol - info in extra. 14 Partial Response w/ metadata, may include blocks 15 Request Paused, pending update, see extensions for info # success - terminal 20 Request Completed, full content. 21 Request Completed, partial content. # error - terminal 30 Request Rejected. NOT working on it. 31 Request failed, busy, try again later (getting dosed. backoff in extra). 32 Request failed, for unknown reason. Extra may have more info. 33 Request failed, for legal reasons. 34 Request failed, content not found. </code></pre> <h2 id="example-use-cases" tabindex="-1"><a class="header-anchor" href="#example-use-cases">Example Use Cases</a></h2> <h3 id="syncing-a-blockchain" tabindex="-1"><a class="header-anchor" href="#syncing-a-blockchain">Syncing a Blockchain</a></h3> Requests we would like to make for this: <ul> <li>Give me <code><hash>/Parent</code>, <code><hash>/Parent/Parent</code> and so on, up to a depth of <code>N</code>.</li> <li>Give me nodes that exist in <code><hash1></code> but not <code><hash2></code> <ul> <li>In addition to this, the ability to say "Give me some range of (the above query) is very important". For example: "Give me the second 1/3 of the nodes that are children of <code><hash1></code> but not <code><hash2></code>"</li> </ul> </li> </ul> <h3 id="downloading-package-dependencies" tabindex="-1"><a class="header-anchor" href="#downloading-package-dependencies">Downloading Package Dependencies</a></h3> <ul> <li>Give me everything within <code><hash>/foo/v1.0.0</code></li> </ul> <h3 id="loading-content-from-deep-within-a-giant-dataset" tabindex="-1"><a class="header-anchor" href="#loading-content-from-deep-within-a-giant-dataset">Loading content from deep within a giant dataset</a></h3> <ul> <li>Give me the nodes for the path <code><hash>/a/b/c/d/e/f/g</code></li> </ul> <h3 id="loading-a-large-video-optimizing-for-playback-and-seek" tabindex="-1"><a class="header-anchor" href="#loading-a-large-video-optimizing-for-playback-and-seek">Loading a large video optimizing for playback and seek</a></h3> <ul> <li>First, give me the first few data blocks <code><hash>/data/*</code></li> <li>Second, give me all of the tree except for leaves <code><hash>/**/!</code></li> <li>Third, give me everything else. <code><hash>/**/*</code></li> </ul> <h3 id="looking-up-an-entry-in-a-sharded-directory" tabindex="-1"><a class="header-anchor" href="#looking-up-an-entry-in-a-sharded-directory">Looking up an entry in a sharded directory</a></h3> Given a directory entry I think might exist in a sharded directory, I should be able to specify the speculative hamt path for that item, and get back as much of that path that exists. For example: "Give me <code><shardhash>/AB/F5/3E/B7/11/C3/B9</code>" And if the item I want is actually just at <code>/AB/F5/3E</code>, I should get that back. <h2 id="other-notes" tabindex="-1"><a class="header-anchor" href="#other-notes">Other notes</a></h2> Cost to the responder. The graphsync protocol will require a non-zero additional overhead of CPU and memory. This cost must be very clearly articulated, and accounted for, otherwise we will end up opening ugly DoS vectors </div> </main> </body> </html>