lsd0004

LSD0004: R5N Distributed Hash Table
Log | Files | Refs

commit 311337aafa35cae0044841ece773b56899e0355f
parent 90bf72e5e98a0534d9b24e52c3b0c33b20344151
Author: Christian Grothoff <grothoff@gnunet.org>
Date:   Sun, 20 Aug 2023 16:27:13 +0200

minor edits

Diffstat:
Mdraft-schanzen-r5n.xml | 162++++++++++++++++++++++++++++++++++++++++---------------------------------------
1 file changed, 83 insertions(+), 79 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml @@ -194,12 +194,12 @@ <t> is a UTF-8 <xref target="RFC3629"/> URI <xref target="RFC3986"/> which can be - used to contact a <em>Peer</em>. + used to contact a <em>peer</em>. An example of an addressing scheme used in this document is "r5n+ip+tcp", which refers to a standard TCP/IP socket connection. The "hier"-part of the URI must provide a suitable address for the given addressing scheme. - The following are non-normative examples of <em>Address</em> strings: + The following are non-normative examples of <em>address</em> strings: </t> <figure title="Example Address URIs."> <artwork name="" type="" align="left" alt=""><![CDATA[ @@ -211,37 +211,37 @@ gnunet+tcp://12.3.4.5/ </dd> <dt>Applications</dt> <dd> - <em>Application</em>s are higher-layer components which directly use the DHT overlay - interfaces. Possible <em>Application</em>s include the GNU Name System + <em>Applications</em> are higher-layer components which directly use the DHT overlay + interfaces. Possible <em>applications</em> include the GNU Name System <xref target="I-D.schanzen-gns"/> and the GNUnet Confidential Ad-hoc Decentralized End-to-End Transport (CADET) <xref target="cadet"/>. </dd> <dt>Application API</dt> <dd> - The <em>Application API</em> exposes the core operations of the DHT overlay - to <em>Applications</em>. - This includes storing <em>Block</em>s in the DHT and retrieving - <em>Block</em>s from the DHT. + The <em>application API</em> exposes the core operations of the DHT overlay + to <em>applications</em>. + This includes storing <em>blocks</em> in the DHT and retrieving + <em>blocks</em> from the DHT. </dd> <dt>Block</dt> <dd> Variable-size unit of payload stored in the DHT - under a <em>Key</em>. + under a <em>key</em>. In the context of &quot;key-value stores&quot; this - refers to &quot;value&quot; stored under a <em>Key</em>. + refers to &quot;value&quot; stored under a <em>key</em>. </dd> <dt>Block Storage</dt> <dd> - The <em>Block Storage</em> component is used to persist and manage - <em>Block</em>s stored by <em>Peer</em>s. + The <em>block storage</em> component is used to persist and manage + <em>blocks</em> stored by <em>peers</em>. It includes logic for enforcing storage quotas, caching strategies and - <em>Block</em> validation. + block validation. </dd> <dt>Block-Type</dt> <dd> - A unique 32-bit value identifying the data format of a <em>Block</em>. - <em>Block-Types</em> are either private or registered in the GANA block type registry (see + A unique 32-bit value identifying the data format of a <em>block</em>. + <em>Block-types</em> are either private or registered in the GANA block type registry (see <xref target="gana_block_type"/>). </dd> <dt>Bootstrapping</dt> @@ -249,45 +249,45 @@ gnunet+tcp://12.3.4.5/ <em>Bootstrapping</em> is the initial process of establishing a connection to the peer-to-peer network. - This initially requires an initial, non-empty set of reachable <em>Peer</em>s and corresponding - <em>Address</em>es supported by the implementation to connect to. + This initially requires an initial, non-empty set of reachable <em>peers</em> and corresponding + <em>addresses</em> supported by the implementation to connect to. </dd> <dt>Initiator</dt> <dd> - The <em>Peer</em> that initially creates and sends a DHT protocol message (<xref target="p2p_hello"/>, + The <em>peer</em> that initially creates and sends a DHT protocol message (<xref target="p2p_hello"/>, <xref target="p2p_put"/>, <xref target="p2p_get"/>, <xref target="p2p_result"/>). </dd> <dt>HELLO block</dt> <dd> - A <tt>HELLO block</tt> is a <em>Block</em> with a <em>Block-Type</em> <tt>DHT_HELLO</tt> (13). - A <tt>HELLO block</tt> is used to store and retrieve <em>Address</em>es of a <em>Peer</em>. + A <tt>HELLO block</tt> is a <em>block</em> with a <em>block-type</em> <tt>DHT_HELLO</tt> (13). + A <tt>HELLO block</tt> is used to store and retrieve <em>addresses</em> of a <em>peer</em>. In this document, <tt>HELLO</tt> blocks are used by the peer discovery mechanism. </dd> <dt>HELLO URL</dt> <dd> <tt>HELLO</tt> URLs are <tt>HELLO</tt> blocks represented as URLs. - They can used for out-of-band exchanges of <em>Peer</em> <em>Address</em> + They can used for out-of-band exchanges of <em>peer</em> <em>address</em> information and are used for - address update signalling messages to <em>Neighbours</em>. Example HELLO URLs and their + address update signalling messages to <em>neighbours</em>. Example HELLO URLs and their format can be found in <xref target="hello_url"/>. </dd> <dt>Key</dt> <dd> 512-bit identifier of a location in the DHT. Multiple <tt>Block</tt>s can be - stored under the same <em>Key</em>. A <em>Peer Address</em> is also a <tt>Key</tt>. + stored under the same <em>key</em>. A <em>peer address</em> is also a <tt>key</tt>. In the context of &quot;key-value stores&quot; this - refers to &quot;key&quot; under which values (<em>Block</em>s) are stored. + refers to &quot;key&quot; under which values (<em>blocks</em>) are stored. </dd> <dt>Message Processing</dt> <dd> - The <em>Message Processing</em> component of the DHT implementation processes - requests from and generates responses to <em>Application</em>s - and the <em>Underlay Interface</em>. + The <em>message processing</em> component of the DHT implementation processes + requests from and generates responses to <em>applications</em> + and the <em>underlay interface</em>. </dd> <dt>Neighbor</dt> <dd> - A neighbor is a <em>Peer</em> which is directly able to communicate - with our <em>Peer</em> via the <em>Underlay Interface</em>. + A neighbor is a <em>peer</em> which is directly able to communicate + with our <em>peer</em> via the <em>underlay interface</em>. </dd> <dt>Peer</dt> <dd> @@ -295,39 +295,39 @@ gnunet+tcp://12.3.4.5/ of the DHT protocol. Each participating host is responsible for holding some portion of the data that has been stored in the overlay, and they are responsible for routing - messages on behalf of other <em>Peer</em>s as needed by the <em>Routing - Algorithm</em>. + messages on behalf of other <em>peers</em> as needed by the <em>routing + algorithm</em>. </dd> <!-- FIXME: this overloads the term 'address'. We should use 'Peer Identity'! --> <dt>Peer Address</dt> <dd> - The <em>Peer Address</em> is the identifier used on the overlay - to identify a <em>Peer</em>. It is a SHA-512 hash of the <tt>Peer ID</tt>. + The <em>peer address</em> is the identifier used on the overlay + to identify a <em>peer</em>. It is a SHA-512 hash of the <em>peer ID</em>. </dd> <!-- FIXME: this obscures the public key nature. We should use "Peer Public Key"! --> <dt>Peer ID</dt> <dd> - The <em>Peer ID</em> is the public key which is used to authenticate - a <em>Peer</em> in the underlay. - The <em>Peer ID</em> is the public key of the corresponding + The <em>peer ID</em> is the public key which is used to authenticate + a <em>peer</em> in the underlay. + The <em>peer ID</em> is the public key of the corresponding Ed25519<xref target="ed25519" /> peer private key. </dd> <dt>Routing</dt> <dd> - The <em>Routing</em> component includes the routing table as well as - routing and <em>Peer</em> selection logic. It facilitates the R<sup>5</sup>N routing + The <em>routing</em> component includes the routing table as well as + routing and <em>peer</em> selection logic. It facilitates the R<sup>5</sup>N routing algorithm with required data structures and algorithms. </dd> <dt>Responsible Peer</dt> <dd> - The <em>Peer</em> <tt>N</tt> that is responsible for a specific key <tt>K</tt>, as + The <em>peer</em> <tt>N</tt> that is responsible for a specific key <tt>K</tt>, as defined by the <tt>SelectClosestPeer(K, P)</tt> algorithm (see <xref target="routing"/>. </dd> <dt>Underlay Interface</dt> <dd> - The <em>Underlay Interface</em> is an abstraction layer on top of the - supported links of a <em>Peer</em>. Peers may be linked by a variety of + The <em>inderlay interface</em> is an abstraction layer on top of the + supported links of a <em>peer</em>. Peers may be linked by a variety of different transports, including "classical" protocols such as TCP, UDP and TLS or higher-layer protocols such as GNUnet, I2P or Tor. <!-- FIXME: add references to GNUnet/I2P/Tor here! --> @@ -342,15 +342,15 @@ gnunet+tcp://12.3.4.5/ </t> <ul> <li> - <tt>PUT</tt>: This operation stores a <em>Block</em> - under a <em>Key</em> on one or more <em>Peer</em>s with - the goal of making the <em>Block</em> availiable for queries using the <tt>GET</tt> operation. + <tt>PUT</tt>: This operation stores a <em>block</em> + under a <em>key</em> on one or more <em>peers</em> with + the goal of making the <em>block</em> availiable for queries using the <tt>GET</tt> operation. In the classical definition of a dictionary interface, this operation would be called "insert". </li> <li> - <tt>GET</tt>: This operation queries the network of peers for any number of <em>Block</em>s - previously stored under or near a <em>Key</em>. + <tt>GET</tt>: This operation queries the network of peers for any number of <em>blocks</em> + previously stored under or near a <em>key</em>. In the classical definition of a dictionary interface, this operation would be called "find". </li> @@ -361,11 +361,11 @@ gnunet+tcp://12.3.4.5/ outlined in <xref target="overlay"/>. </t> <t> - A <em>Peer</em> does not necessarily need to expose the above - operations to <em>Application</em>s, but it commonly will. A - <em>Peer</em> that does not expose the above operations could - be a host purely used for <em>Bootstrapping</em>, - <em>Routing</em> or supporting + A <em>peer</em> does not necessarily need to expose the above + operations to <em>applications</em>, but it commonly will. A + <em>peer</em> that does not expose the above operations could + be a host purely used for <em>bootstrapping</em>, + <em>routing</em> or supporting the overlay network with resources. </t> <t> @@ -374,10 +374,10 @@ gnunet+tcp://12.3.4.5/ data. Examples for such hosts would be mobile devices with limited bandwidth, battery and storage capacity. Such hosts may be used to run applications that use the DHT. However, we - will not refer to such hosts as <em>Peer</em>s. + will not refer to such hosts as <em>peers</em>. </t> <t> - In a trivial scenario where there is only one <em>Peer</em> (on the local host), + In a trivial scenario where there is only one <em>peer</em> (on the local host), R<sup>5</sup>N operates similarly to a dictionary data structure. However, the default use case is one where nodes communicate directly and indirectly in order to realize a distributed storage mechanism. @@ -397,25 +397,25 @@ gnunet+tcp://12.3.4.5/ <!-- consider moving some of this back into sec considerations --> <t> Specifics about the protocols of the underlays implementing - the <em>Underlay Interface</em> or the <em>Application</em>s + the <em>underlay interface</em> or the <em>applications</em> using the DHT are out of the scope of this document. </t> <t> To establish an initial connection to a network of R<sup>5</sup>N peers, at least one initial, addressable - <em>Peer</em> is required as part of the - <em>Bootstrapping</em> process. Further <em>Peer</em>s, - including <em>Neighbor</em>s, are then learned via a peer + <em>peer</em> is required as part of the + <em>bootstrapping</em> process. Further <em>peers</em>, + including <em>neighbors</em>, are then learned via a peer discovery process as defined in <xref target="find_peer"/>. </t> <t> Across this document, the functional components of an R<sup>5</sup>N implementation are divided into - <em>Routing</em> (<xref target="routing"/>), <em>Message - Processing</em> (<xref target="p2p_messages"/>) and - <em>Block</em> processing (<xref target="blockstorage"/>). - <em>Application</em>s that require application-specific - <em>Block</em> payloads are expected to register a + <em>routing</em> (<xref target="routing"/>), <em>message + processing</em> (<xref target="p2p_messages"/>) and + block processing (<xref target="blockstorage"/>). + <em>Applications</em> that require application-specific + <em>block</em> payloads are expected to register a <em>Block-Type</em> in the GANA <em>Block-Type</em> registry (<xref target="gana_block_type"/>) and provide a specification of the associated block operations (<xref @@ -458,13 +458,13 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... For example, a peer may have a TCP/IP address, or expose a QUIC endpoint. While the specific addressing options and mechanisms are out of scope for this document, it is necessary to define a universal addressing - format in order to facilitate the distribution of <em>Address</em> - information to other <em>Peer</em>s in the DHT overlay. + format in order to facilitate the distribution of <em>address</em> + information to other <em>peers</em> in the DHT overlay. This standardized format is the <em>HELLO Block</em> (described in <xref target="hello_block"/>), which contains sets of URIs. The scheme of each URI indicates which underlay understands the - respective <em>Address</em> details which are encoded in the rest of the URI. + respective <em>address</em> details which are encoded in the rest of the URI. </t> <!-- 1) The current API is always fire+forget, it doesn't allow for flow @@ -500,24 +500,24 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... <t> It is expected that the underlay provides basic mechanisms to manage peer connectivity and addressing. - The required functionalities can be represented by the following - API: + The essence of the <em>underlay interface</em> is + captured by the following set of API calls: </t> <dl> <dt> <tt>TRY_CONNECT(P, A)</tt> </dt> <dd> - A function which allows an implementation to signal to the underlay that + This call allows an implementation to signal to the underlay that it wants to establish a connection to another peer <tt>P</tt> using an address <tt>A</tt>. If the connection attempt is successful, information on the new - peer is offered through the <tt>PEER_CONNECTED</tt> signal. + peer will be offered through the <tt>PEER_CONNECTED</tt> signal. </dd> <dt> <tt>HOLD(P)</tt> </dt> <dd> - A function which tells the underlay to keep a hold on to a connection + This call tells the underlay to keep a hold on to a connection to a peer <tt>P</tt>. Underlays are usually limited in the number of active connections. With this function the DHT can indicate to the underlay which connections should preferably be preserved. @@ -526,29 +526,29 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... <tt>DROP(P)</tt> </dt> <dd> - A function which tells the underlay to drop the connection to a - peer <tt>P</tt>. This function is only there for symmetry and + This call tells the underlay to drop the connection to a + peer <tt>P</tt>. This call is only there for symmetry and used during the peer's shutdown to release all of the remaining HOLDs. As R<sup>5</sup>N always prefers the longest-lived connections, it would never drop an active connection that it - has called HOLD() on before. Nevertheless, underlay implementations - should not rely on this always being true. A call to DROP() also + has called <tt>HOLD()</tt> on before. Nevertheless, underlay implementations + should not rely on this always being true. A call to <tt>DROP()</tt> also does not imply that the underlay must close the connection: it merely removes the preference to preserve the connection that was established - by HOLD(). + by <tt>HOLD()</tt>. </dd> <dt> <tt>SEND(P, M)</tt> </dt> <dd> - A function that allows the local peer to send a protocol message + This call allows the local peer to send a protocol message <tt>M</tt> to a peer <tt>P</tt>. </dd> <dt> <tt>ESTIMATE_NETWORK_SIZE() -> L2NSE</tt> </dt> <dd> - A procedure that provides an estimate of the network size. + A call that provides an estimate of the network size. The result, <tt>L2NSE</tt>, must be the base-2 logarithm of the estimated number of peers in the network. It is used by the routing algorithm. If the underlay does not support a protocol for network size estimation (such as cite paper NSE) the value @@ -556,7 +556,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... </dd> </dl> <t> - The above procedures are meant to be actively + The above calls are meant to be actively executed by the implementation as part of the peer-to-peer protocol. In addition, the underlay is expected to emit the following signals (usually implemented as callbacks) @@ -570,7 +570,11 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... is a signal that allows the DHT to react to a newly connected peer <tt>P</tt>. Such an event triggers, for example, updates in the - routing table and gossiping of HELLOs to that peer. + routing table and gossiping of HELLOs to that peer. Underlays may + include meta-data about the connection, for example to indicate + that the connection is from a resource-constrained host that does + not intend to function as a full <em>peer</em> and thus should not + be considered for routing. </dd> <dt> <tt>PEER_DISCONNECTED -> P</tt>