Tracking issue - Composable Routing

[mxinden]

Tracking all libp2p related Composable Routing efforts.

Description

See original post by @petar #339 (comment).

Composable Routing is a framework that was designed to enable the interoperability of protocols and nodes with different versions and capabilities, developed by independent teams or organizations. As a consequence, it also enables middleware components (like caching, batching, predictive fetching, and so on) and the co-existence of different content finding protocols and subnetworks.

The framework has four "pillars":

• Routing syntax and language
• Routing interface
• Smart Records
• Subnets

Routing syntax and language

The routing syntax is a common data model (with a user-facing syntactic representation) for communicating routing-related information (requests and responses). The implementation of the routing syntax provides serialization and pretty printing of routing expressions.

The routing language is a semantic that specifies how to interpret routing expressions, and specifically how to compose complex routing statements out of simpler ones.

Finally, the routing grammar is a set of rules that define the "vocabulary" of the language. In other words, the grammar defines the set of valid and recognizable routing statements. The grammar is, by design, a continuously evolving specification of the recognizable language vocabulary.

The grammar is reflected in code, as a collection of parsing functions for the valid statements in the language. When new rules are coined (and added to the grammar specification), their respective parsers are codified manually. Going forward, the project plans to have a grammar compiler, which generates parsers and checks for ambiguities.

For intuition, expressions in the routing language can represent statements, like:

• I am providing CID via bitswap.
• I am interested in having the content of CID.
• Fetch the content corresponding to IPFS_PATH.

They can also express compositions of statements, like:

• Find providers for CID, then fetch its content,
  then extract the field "foo" and view it as a CID,
  then fetch its content.

Routing interface

A routing system processes routing requests and returns routing responses. Routing requests and responses have semantics, which are unlike those of a traditional request/response protocols, that implement function call arguments and return values.

A routing request is a routing expression which represents a program to be evaluated by the routing system. In the general case, a routing system may not be able to evaluate all steps in a program, since it may have limited capabilities or a legacy version which does not understand newer routing vocabulary. For this reason, routing responses have to follow a format that allows the routing system to communicate back the results of partially evaluating the routing request.

Specifically, a routing response is definitionally a copy of the routing request with the evaluated sub-expressions substituted by the result of their evaluation or by equivalent expressions (expressions that would evaluate to the same result).

In other words, a routing request and a response are both (usually different) programs which, if evaluated fully, would produce the same result. In the realm of lambda calculus and formal verification, this is known as beta-equivalence.

Smart records

Smart Records (SR) is a technology that enables multiple decentralized parties and protocols to randevouz and share information on a topic. Specifically, SR is a key-value store service, which facilitates conflict-free updates to values by multiple writers.

SR keys are opaque strings, while SR values are hierarchical documents in the data model of the routing syntax. An SR service provides a value update operation, which enables a writer to update a subexpression of a value without interfering with the rest of the value's contents. Update operations are commutative by design, ensuring that (i) operation re-ordering due to asynchronous phenomena has no effect on semantics, and (ii) multiple physical replicas of a value can be merged unambiguously. In other words, SR values are CRDTs.

The quintessential application of SR is to use it as the store for DHT put/get operations. This enables any third-party protocol to use the DHT for its own purposes, respectively unlocking a vast diversity of applications that can be developed by the community. Some simple examples are email-over-DHT and chat-over-DHT.

More generally, a DHT with flexible value semantics is effectively a giant general-purpose, random-access storage layer. And, therefore, highly complex applications, like a crypto exchange-over-DHT, could be built on this substrate.

The current implementation of the SR virtual machine supports in-memory storage only. We hope to add support for persistence. The SR virtual machine can also be used programmatically as a Go library that implements a key-value store for routing expressions. This use comes up, for instance, when implementing a filecoin content indexer, which must store multiple different provide records for every cid.

Subnets

At present, there is a single DHT network which spans across all IPFS nodes. We would like to introduce a general standard for the co-existence of multiple network instances with individual discovery, membership and content routing semantics.

This would enable communities of users to configure custom networks that meet their physical, business, logistics, privacy, security and other application needs.

Subnets address this goal. A subnet is effectively a set of peers that run an instance of a routing protocol (e.g. DHT or pubsub) amongst themselves. Subnets can have custom membership and authentication semantics. Optionally, a subnet can have an externally-facing routing interface, allowing others to use it as a routing service.