đź’ˇ OmniDex is a novel composable Distributed Hash Table model.
The naming is still to be discussed, OmniDex is used as a placeholder.
A Distributed Hash Table (DHT) is essentially a type of hash table where the data (key-value pairs) is spread out over different nodes or computers. For a DHT to work effectively, all its nodes must form a connected graph, ensuring that connectivity to a singular node facilitates access to the entirety of data stored across the DHT.
The scalability of a DHT is particularly noteworthy when its routing and state maintenance complexities increase sub-linearly with the growth of the network. Prominent DHT architectures, such as Chord or Kademlia, exhibit a logarithmic growth in their state and routing complexities in relation to the size of the network. As a result, they are the preferred backbone for expansive systems like Bittorrent’s Mainline DHT and the IPFS Amino DHT.
A DHT operates within a defined geometric space and utilizes a specific distance metric to measure proximities within this space. A crucial component is a function that assigns elements to vertices within the geometric domain, determining the spatial positioning of items (e.g. keys, peers, content). A multitude of leading DHT algorithms employ cryptographic hash functions for this assignment.
Within the DHT’s geometric framework, each key is assigned to the node whose vertex is proximal to the key’s vertex, resulting in the formation of a Voronoi diagram. When a peer searches for a key within the DHT, it initially contacts the closest peers known to it, based on its routing table, which operates according to the predefined distance metric. This node responds either with the required data or provides the addresses of peers situated closer to the desired data vertex. Ensuring that all nodes maintain knowledge of their immediate neighbors, in addition to a subset of distantly situated nodes, guarantees successful convergence to the sought-after vertex during lookups.
Most DHT algorithms leverage cyclic geometric spaces characterized by sparse vertex population. Moreover, their indexing functions consistently yield independent and identically distributed vertices within this space. While these attributes are favorable, they are not imperatively required for the DHT’s operation.
Example: IPFS+Kademlia
Kademlia employs an XOR distance metric, which falls within the realm of non-Euclidean geometry. This geometric framework is cyclic, characterized by a confined space devoid of edges. IPFS’ kademlia DHT utilizes keys with a length of 256 bits, and it generates identities through the Sha256 digest of specific strings (e.g., peerid, cid). This approach ensures that the identities are independently and identically distributed within the keyspace. The capacity of this keyspace, given its sparsity, stands at 2256.
Kademlia’s architecture is built with a routing complexity of log(n) and a state size of log(n), where n represents the total number of nodes active within the DHT.
OmniDex is an innovative, Composable Distributed Hash Table (DHT). It introduces a dynamic structure that can build upon any DHT geometry. OmniDex seeks to provide a unique approach to DHT design, where the system can accommodate various features. Each feature represents a specific capability, like Peer Routing or Content Routing. By being composable, OmniDex allows a node or software to determine and employ a set of features, shaping its participation and behavior in the distributed network. This design aims for flexibility, scalability, and inter-network operability, making it easier for different networks to share features without the need for separate DHTs, thereby enhancing resource efficiency, interconnectivity and security.
Routing Table: Nodes keep track of another’s addresses in the routing table This data structure is designed to strategically select which nodes are recorded, striking a balance between minimizing the table’s size and simplifying routing complexities. Furthermore, routing tables are inherently geometry-aware, factoring in the relative distance between nodes. For example, Kademlia organizes its routing table in buckets where each bucket records a set of nodes located at a specific distance from the host node.
Record: Records represent data that is being stored in the DHT. They represent the value for a key-value pair. Each record is identified by a key which is a vertex in the overarching geometry.
For example, IPFS uses three types of records (1) Peer Records, (2) Provider Records and (3) IPNS Records.
Lookup mechanism: The Lookup Mechanism defines the methodology by which a peer can retrieve a particular record using its key. It establishes the response procedure nodes should adopt when addressing queries, as well as the criteria that signal the completion or termination of the lookup process. For instance, within IPFS implementations like Kubo, the completion processes for Peer Records and IPNS Records differ markedly. A lookup for a Peer Record reaches completion when a dialable multiaddress is identified for the target peer. In contrast, an IPNS Record lookup necessitates a quorum to guarantee uniformity and consistency across the corresponding records.
Feature: A feature is defined as the capability that enables nodes to process and respond to requests about a specific record type. For example, IPFS encompasses three primary features:
Each feature can have its own lookup mechanism and requires a Record type. (The same record type which can be shared with other features.) Every feature necessitates a comprehensive specification, ensuring uniformity and consistency among nodes within its affiliated consortium.
Consortium: A consortium is the set of connected nodes implementing a specific feature. It’s worth noting that a single feature can encompass several distinct consortia, in the case those consortia don’t share any common peer. A consortium must have a distinct identifier. Every node must share the consortium identifiers it’s a part of with every peer it interacts with. For instance, if the Lotus nodes in Filecoin mainnet and the Kubo nodes in the “public IPFS DHT” shared the same bootstrapper peers, the Peer Routing consortium would be made of all these Lotus and Kubo nodes.