commit c42ae3ae99341c1708599900a67fa117ec553e54
parent b883bf3d0b58e9584a0b080bb6ea4d1206cef11f
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Mon, 3 Jan 2022 19:00:41 +0100
indent
Diffstat:
| M | draft-schanzen-r5n.xml | | | 2272 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
1 file changed, 1136 insertions(+), 1136 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -43,106 +43,106 @@
<country>DE</country>
</postal>
<email>schanzen@gnunet.org</email>
- </address>
- </author>
- <author fullname="Christian Grothoff" initials="C." surname="Grothoff">
- <organization>Berner Fachhochschule</organization>
- <address>
- <postal>
- <street>Hoeheweg 80</street>
- <city>Biel/Bienne</city>
- <code>2501</code>
- <country>CH</country>
- </postal>
- <email>grothoff@gnunet.org</email>
- </address>
- </author>
- <author fullname="Bernd Fix" initials="B." surname="Fix">
- <organization>GNUnet e.V.</organization>
- <address>
- <postal>
- <street>Boltzmannstrasse 3</street>
- <city>Garching</city>
- <code>85748</code>
- <country>DE</country>
- </postal>
- <email>fix@gnunet.org</email>
- </address>
- </author>
- <!-- Meta-data Declarations -->
- <area>General</area>
- <workgroup>Independent Stream</workgroup>
- <keyword>distributed hash tables</keyword>
- <abstract>
- <t>This document contains the R5N DHT technical specification.</t>
- <t>
- This document defines the normative wire format of resource records,
- resolution processes, cryptographic routines and security considerations for
- use by implementers.
- </t>
- <t>
- This specification was developed outside the IETF and does not have IETF
- consensus. It is published here to guide implementation of R5N and to
- ensure interoperability among implementations.
- </t>
- </abstract>
- </front>
- <middle>
- <section anchor="introduction" numbered="true" toc="default">
- <name>Introduction</name>
+ </address>
+ </author>
+ <author fullname="Christian Grothoff" initials="C." surname="Grothoff">
+ <organization>Berner Fachhochschule</organization>
+ <address>
+ <postal>
+ <street>Hoeheweg 80</street>
+ <city>Biel/Bienne</city>
+ <code>2501</code>
+ <country>CH</country>
+ </postal>
+ <email>grothoff@gnunet.org</email>
+ </address>
+ </author>
+ <author fullname="Bernd Fix" initials="B." surname="Fix">
+ <organization>GNUnet e.V.</organization>
+ <address>
+ <postal>
+ <street>Boltzmannstrasse 3</street>
+ <city>Garching</city>
+ <code>85748</code>
+ <country>DE</country>
+ </postal>
+ <email>fix@gnunet.org</email>
+ </address>
+ </author>
+ <!-- Meta-data Declarations -->
+ <area>General</area>
+ <workgroup>Independent Stream</workgroup>
+ <keyword>distributed hash tables</keyword>
+ <abstract>
+ <t>This document contains the R5N DHT technical specification.</t>
+ <t>
+ This document defines the normative wire format of resource records,
+ resolution processes, cryptographic routines and security considerations for
+ use by implementers.
+ </t>
+ <t>
+ This specification was developed outside the IETF and does not have IETF
+ consensus. It is published here to guide implementation of R5N and to
+ ensure interoperability among implementations.
+ </t>
+ </abstract>
+ </front>
+ <middle>
+ <section anchor="introduction" numbered="true" toc="default">
+ <name>Introduction</name>
<!-- FIXME: Here we should also cite and discuss RELOAD (https://datatracker.ietf.org/doc/html/rfc6940)
and establish why we need this spec and are not a "Topology plugin"
in RELOAD. The argumentation revolves around the trust model (openness) and
security aspects (path signatures).
-->
+ <t>
+ Distributed Hash Tables (DHTs) are a key data structure for the
+ construction of completely decentralized applications.
+ DHTs are important because they generally provide a robust and
+ efficient means to distribute the storage and retrieval of
+ key-value pairs.
+ </t>
+ <t>
+ While <xref target="RFC6940"/> already provides a peer-to-peer (P2P)
+ signaling protocol with extensible routing and topology mechanisms,
+ it also relies on strict admission control through the use of either
+ centralized enrollment servers or pre-shared keys.
+ Modern decentralized applications require a more open system that
+ enables ad-hoc participation and other means to prevent common attacks
+ on P2P overlays.
+ </t>
+ <t>
+ This document contains the technical specification
+ of the R5N DHT <xref target="R5N"/>, a secure DHT routing algorithm
+ and data structure for decentralized applications.
+ R5N is an open P2P overlay routing mechanism which supports ad-hoc
+ participation and security properties including support for
+ topologies in restricted-route environments and path signatures.
+ </t>
+ <t>
+ This document defines the normative wire format of peer-to-peer
+ messages, routing algorithms, cryptographic routines and security
+ considerations for use by implementors.
+ </t>
+ <section numbered="true" toc="default">
+ <name>Requirements Notation</name>
<t>
- Distributed Hash Tables (DHTs) are a key data structure for the
- construction of completely decentralized applications.
- DHTs are important because they generally provide a robust and
- efficient means to distribute the storage and retrieval of
- key-value pairs.
- </t>
- <t>
- While <xref target="RFC6940"/> already provides a peer-to-peer (P2P)
- signaling protocol with extensible routing and topology mechanisms,
- it also relies on strict admission control through the use of either
- centralized enrollment servers or pre-shared keys.
- Modern decentralized applications require a more open system that
- enables ad-hoc participation and other means to prevent common attacks
- on P2P overlays.
- </t>
- <t>
- This document contains the technical specification
- of the R5N DHT <xref target="R5N"/>, a secure DHT routing algorithm
- and data structure for decentralized applications.
- R5N is an open P2P overlay routing mechanism which supports ad-hoc
- participation and security properties including support for
- topologies in restricted-route environments and path signatures.
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
+ "OPTIONAL" in this document are to be interpreted as described in
+ BCP 14 <xref target="RFC2119"/> <xref target="RFC8174"/> when, and only
+ when, they appear in all capitals, as shown here.
</t>
- <t>
- This document defines the normative wire format of peer-to-peer
- messages, routing algorithms, cryptographic routines and security
- considerations for use by implementors.
- </t>
- <section numbered="true" toc="default">
- <name>Requirements Notation</name>
- <t>
- The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
- "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
- "OPTIONAL" in this document are to be interpreted as described in
- BCP 14 <xref target="RFC2119"/> <xref target="RFC8174"/> when, and only
- when, they appear in all capitals, as shown here.
- </t>
- </section>
</section>
- <section anchor="architecture" numbered="true" toc="default">
- <name>Architecture</name>
- <t>
- R5N is an overlay network with a pluggable transport layer.
- The following figure shows the R5N architecture.
- </t>
- <figure>
- <artwork><![CDATA[
+ </section>
+ <section anchor="architecture" numbered="true" toc="default">
+ <name>Architecture</name>
+ <t>
+ R5N is an overlay network with a pluggable transport layer.
+ The following figure shows the R5N architecture.
+ </t>
+ <figure>
+ <artwork><![CDATA[
| +-----------------+ +-------+
Applications | | GNU Name System | | CADET | ...
| +-----------------+ +-------+
@@ -165,466 +165,466 @@ Connectivity | |Underlay| |Underlay|
| |Link | |Link |
| +--------+ +--------+
]]>
- </artwork>
- </figure>
+ </artwork>
+ </figure>
+ <dl>
+ <dt>Applications</dt>
+ <dd>
+ Applications are components which directly use the DHT overlay
+ interfaces. Possible applications include the GNU Name System
+ <xref target="I-D.draft-schanzen-gns"/> or the CADET transport system
+ <xref target="cadet"/>.
+ </dd>
+ <dt>Overlay Interface</dt>
+ <dd>
+ The Overlay Interface exposes the core operations of the DHT overlay
+ to applications.
+ This includes querying and retrieving data from the DHT.
+ </dd>
+ <dt>Block Storage</dt>
+ <dd>
+ The Block Storage component is used to persist and manage data
+ by nodes. It includes logic for quotas, caching stragegies and
+ data validation.
+ </dd>
+ <dt>Message Processing</dt>
+ <dd>
+ The Message Processing component processes requests from and responses
+ to applications as well as messages from the underlay network.
+ </dd>
+ <dt>Routing</dt>
+ <dd>
+ The Routing component includes the routing table as well as
+ routing and node selection logic. It facilitates the R5N routing
+ algorithm with required data structures and algorithms.
+ </dd>
+ <dt>Underlay Interface</dt>
+ <dd>
+ The DHT Underlay Interface is an abstraction layer on top of the
+ supported links of a node. Nodes may be linked by a variety of
+ different transports, including "classical" protocols such as
+ TCP, UDP and TLS or advanced protocols such as GNUnet, L2P or Tor.
+ </dd>
+ </dl>
+ <t>
+ Other glossary
+ </t>
+ <dl>
+ <dt>Node</dt>
+ <dd>
+ A node is participant in the network and addressable through the
+ network overlay.
+ </dd>
+ <dt>Node Address</dt>
+ <dd>
+ The <tt>Node Address</tt> is the identifier used on the Overlay
+ to address a node.
+ </dd>
+ <dt>Node ID</dt>
+ <dd>
+ The <tt>Node ID</tt> is the identity which is used to authenticate
+ a node in the underlay.
+ The <tt>Node Address</tt> is derived from the <tt>Node ID</tt>.
+ </dd>
+ <dt>Peer</dt>
+ <dd>
+ A peer is a node which is directly connected to our peer.
+ </dd>
+ </dl>
+ </section>
+ <section anchor="overlay" numbered="true" toc="default">
+ <name>Overlay</name>
+ <t>
+ In the DHT overlay, a node is addressable by its
+ <tt>Node Address</tt>.
+ The <tt>Node Address</tt> is a SHA-512 hash <xref target="RFC4634"/>
+ of the <tt>Node ID</tt>.
+ <!-- FIXME should the node ID be agile? Should the signature then
+ also be agile?-->
+ <!--The node public key is the public key of the corresponding
+ Ed25519<xref target="ed25519" /> node private key.-->
+ </t>
+ <t>
+ Any implementation of this specification MUST expose the two API
+ procedures "GET" and "PUT".
+ </t>
+ <section>
+ <name>The GET procedure</name>
+ <t>
+ The GET procedure is defined as follows:
+ </t>
+ <t>
+ <tt>GET(Key[, GetParams]) -> Results as List</tt>
+ </t>
+ <t>
+ The procedure takes a single additional <tt>QueryParams</tt>
+ argument in order to specify detailed query parameters.
+ The <tt>GetParams</tt> consist of the following parameters:
+ </t>
<dl>
- <dt>Applications</dt>
- <dd>
- Applications are components which directly use the DHT overlay
- interfaces. Possible applications include the GNU Name System
- <xref target="I-D.draft-schanzen-gns"/> or the CADET transport system
- <xref target="cadet"/>.
- </dd>
- <dt>Overlay Interface</dt>
- <dd>
- The Overlay Interface exposes the core operations of the DHT overlay
- to applications.
- This includes querying and retrieving data from the DHT.
- </dd>
- <dt>Block Storage</dt>
+ <dt>BlockType</dt>
<dd>
- The Block Storage component is used to persist and manage data
- by nodes. It includes logic for quotas, caching stragegies and
- data validation.
+ The default setting of this parameter is to request any type of
+ block types under the key.
</dd>
- <dt>Message Processing</dt>
+ <dt>ReplicationLevel</dt>
+ <dd>The default setting of this parameter is X (FIXME).</dd>
+ <dt>RouteOptions</dt>
<dd>
- The Message Processing component processes requests from and responses
- to applications as well as messages from the underlay network.
+ are used in order to indicate certain
+ processing requirements for messages.
+ Any combination of options as defined in <xref target="route_options"/>
+ may be specificied.
+ The default setting of this parameter is that no option is set.
</dd>
- <dt>Routing</dt>
+ <dt>XQuery</dt>
<dd>
- The Routing component includes the routing table as well as
- routing and node selection logic. It facilitates the R5N routing
- algorithm with required data structures and algorithms.
- </dd>
- <dt>Underlay Interface</dt>
- <dd>
- The DHT Underlay Interface is an abstraction layer on top of the
- supported links of a node. Nodes may be linked by a variety of
- different transports, including "classical" protocols such as
- TCP, UDP and TLS or advanced protocols such as GNUnet, L2P or Tor.
+ is extended query medatadata which may be
+ required depending on the respective <tt>BlockType</tt>.
+ A <tt>BlockType</tt> must define if the <tt>XQuery</tt> can or must
+ be used and what the specific format of its contents should be.
+ See also <xref target="block_types"/>.
+ The default setting of this parameter is empty.
</dd>
</dl>
<t>
- Other glossary
+ The <tt>RouteOptions</tt> consist of the following flags:
</t>
- <dl>
- <dt>Node</dt>
- <dd>
- A node is participant in the network and addressable through the
- network overlay.
- </dd>
- <dt>Node Address</dt>
+ <dl anchor="route_options">
+ <dt>DemultiplexEverywhere</dt>
<dd>
- The <tt>Node Address</tt> is the identifier used on the Overlay
- to address a node.
+ indicates that each node along the way should process the request.
</dd>
- <dt>Node ID</dt>
+ <dt>RecordRoute</dt>
<dd>
- The <tt>Node ID</tt> is the identity which is used to authenticate
- a node in the underlay.
- The <tt>Node Address</tt> is derived from the <tt>Node ID</tt>.
+ indicates to keep track of the route that the message takes
+ in the P2P network.
</dd>
- <dt>Peer</dt>
+ <dt>FindNode</dt>
<dd>
- A peer is a node which is directly connected to our peer.
+ indicates that this is a request used to find additional nodes.
+ This is a special flag which modifies the message processing to
+ allow approximate results.
</dd>
</dl>
+ <t>
+ As the time it takes for results to arrive may vary an implementation
+ may either return a list of results after a timeout or allow the
+ caller to provide a callback function which is called for any result
+ received from the DHT until the procedure is cancelled.
+ </t>
</section>
- <section anchor="overlay" numbered="true" toc="default">
- <name>Overlay</name>
+ <section>
+ <name>The PUT procedure</name>
<t>
- In the DHT overlay, a node is addressable by its
- <tt>Node Address</tt>.
- The <tt>Node Address</tt> is a SHA-512 hash <xref target="RFC4634"/>
- of the <tt>Node ID</tt>.
- <!-- FIXME should the node ID be agile? Should the signature then
- also be agile?-->
- <!--The node public key is the public key of the corresponding
- Ed25519<xref target="ed25519" /> node private key.-->
+ The PUT procedure is defined as follows:
</t>
<t>
- Any implementation of this specification MUST expose the two API
- procedures "GET" and "PUT".
+ <tt>PUT(Key, Block, BlockType[, PutParams])</tt>
</t>
- <section>
- <name>The GET procedure</name>
- <t>
- The GET procedure is defined as follows:
- </t>
- <t>
- <tt>GET(Key[, GetParams]) -> Results as List</tt>
- </t>
- <t>
- The procedure takes a single additional <tt>QueryParams</tt>
- argument in order to specify detailed query parameters.
- The <tt>GetParams</tt> consist of the following parameters:
- </t>
- <dl>
- <dt>BlockType</dt>
- <dd>
- The default setting of this parameter is to request any type of
- block types under the key.
- </dd>
- <dt>ReplicationLevel</dt>
- <dd>The default setting of this parameter is X (FIXME).</dd>
- <dt>RouteOptions</dt>
- <dd>
- are used in order to indicate certain
- processing requirements for messages.
- Any combination of options as defined in <xref target="route_options"/>
- may be specificied.
- The default setting of this parameter is that no option is set.
- </dd>
- <dt>XQuery</dt>
- <dd>
- is extended query medatadata which may be
- required depending on the respective <tt>BlockType</tt>.
- A <tt>BlockType</tt> must define if the <tt>XQuery</tt> can or must
- be used and what the specific format of its contents should be.
- See also <xref target="block_types"/>.
- The default setting of this parameter is empty.
- </dd>
- </dl>
- <t>
- The <tt>RouteOptions</tt> consist of the following flags:
- </t>
- <dl anchor="route_options">
- <dt>DemultiplexEverywhere</dt>
- <dd>
- indicates that each node along the way should process the request.
- </dd>
- <dt>RecordRoute</dt>
- <dd>
- indicates to keep track of the route that the message takes
- in the P2P network.
- </dd>
- <dt>FindNode</dt>
- <dd>
- indicates that this is a request used to find additional nodes.
- This is a special flag which modifies the message processing to
- allow approximate results.
- </dd>
- </dl>
- <t>
- As the time it takes for results to arrive may vary an implementation
- may either return a list of results after a timeout or allow the
- caller to provide a callback function which is called for any result
- received from the DHT until the procedure is cancelled.
- </t>
- </section>
- <section>
- <name>The PUT procedure</name>
- <t>
- The PUT procedure is defined as follows:
- </t>
- <t>
- <tt>PUT(Key, Block, BlockType[, PutParams])</tt>
- </t>
- <t>
- The procedure takes three mandatory arguments.
- The first argument is the query
- key under which the block is to be stored.
- The second parameter is the block payload.
- The third parameter is the type of the block payload.
- Block types are defined in <xref target="block_types"/>.
- The PUT procedure also allows an optional <tt>PutParams</tt>
- parameter.
- </t>
- <dl>
- <dt>ReplicationLevel</dt>
- <dd>The default setting of this parameter is X (FIXME).</dd>
- <dt>RouteOptions</dt>
- <dd>
- are used in order to indicate certain
- processing requirements for messages.
- Any combination of options as defined in <xref target="route_options"/>
- may be specificied.
- The default setting of this parameter is that no option is set.
- </dd>
- <dt>Expiration</dt>
- <dd>
- is the requested expiration date for the block payload.
- </dd>
- </dl>
- </section>
- </section>
- <section anchor="underlay" numbered="true" toc="default">
- <name>Underlay</name>
<t>
- In the network underlay, a node is addressable by traditional
- means out of scope of this document. For example, the node may
- have a TCP/IP address, or a HTTPS 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 connectivity
- information to other nodes in the DHT overlay.
- This format is the "HELLO" message.
+ The procedure takes three mandatory arguments.
+ The first argument is the query
+ key under which the block is to be stored.
+ The second parameter is the block payload.
+ The third parameter is the type of the block payload.
+ Block types are defined in <xref target="block_types"/>.
+ The PUT procedure also allows an optional <tt>PutParams</tt>
+ parameter.
</t>
- <!--
- 1) The current API is always fire+forget, it doesn't allow for flow
- control. I think we need to add that, possibly for sending and receiving.
+ <dl>
+ <dt>ReplicationLevel</dt>
+ <dd>The default setting of this parameter is X (FIXME).</dd>
+ <dt>RouteOptions</dt>
+ <dd>
+ are used in order to indicate certain
+ processing requirements for messages.
+ Any combination of options as defined in <xref target="route_options"/>
+ may be specificied.
+ The default setting of this parameter is that no option is set.
+ </dd>
+ <dt>Expiration</dt>
+ <dd>
+ is the requested expiration date for the block payload.
+ </dd>
+ </dl>
+ </section>
+ </section>
+ <section anchor="underlay" numbered="true" toc="default">
+ <name>Underlay</name>
+ <t>
+ In the network underlay, a node is addressable by traditional
+ means out of scope of this document. For example, the node may
+ have a TCP/IP address, or a HTTPS 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 connectivity
+ information to other nodes in the DHT overlay.
+ This format is the "HELLO" message.
+ </t>
+ <!--
+ 1) The current API is always fire+forget, it doesn't allow for flow
+ control. I think we need to add that, possibly for sending and receiving.
- IDK.
+ IDK.
- 2) I'm not sure what to do with the crypto: mandate EdDSA or allow the
- underlay to do whatever public keys it likes.
+ 2) I'm not sure what to do with the crypto: mandate EdDSA or allow the
+ underlay to do whatever public keys it likes.
- We need keys in the overlay. (Path signatures). Do they need to
- be the same keys???
+ We need keys in the overlay. (Path signatures). Do they need to
+ be the same keys???
- 3) I think we may want to mandate that the lower layer at least
- authenticate the other node (i.e. every UDP message could be in
- cleartext, but would need to come with an EdDSA signature, alas 92 byte
- overhead and a signature verification _required_). Otherwise, I don't
- see how we can offer even the most minimal protections against node
- impersonation attacks. WDYT?
+ 3) I think we may want to mandate that the lower layer at least
+ authenticate the other node (i.e. every UDP message could be in
+ cleartext, but would need to come with an EdDSA signature, alas 92 byte
+ overhead and a signature verification _required_). Otherwise, I don't
+ see how we can offer even the most minimal protections against node
+ impersonation attacks. WDYT?
- Security considerations? Prerequisites?
- -->
+ Security considerations? Prerequisites?
+ -->
+ <t>
+ It is expected that there are basic mechanisms available to
+ manage node connectivity and addressing.
+ The required functionality are abstracted through the following
+ procedures and events:
+ </t>
+ <dl>
+ <dt>
+ <tt>PEER_CONNECTED(P)</tt>
+ </dt>
+ <dd>
+ is a signal that allows the DHT to react to a newly connected peer
+ <tt>N</tt>.
+ Such an event triggers, for example, updates in the
+ routing table.
+ </dd>
+ <dt>
+ <tt>PEER_DISCONNECTED(P)</tt>
+ </dt>
+ <dd>
+ is a signal that allows the DHT to react to a recently disconnected
+ peer.
+ Such an event triggers, for example, updates in the
+ routing table.
+ </dd>
+ <dt>
+ <tt>TRY_CONNECT(N, A)</tt>
+ </dt>
+ <dd>
+ A function which allows the local node to attempt the establishment of
+ a connection to another node <tt>N</tt> using an address <tt>A</tt>.
+ When the connection attempt is successful, information on the new
+ peer is 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 the connection
+ to a peer <tt>P</tt>. FIXME what is this needed for?
+ </dd>
+ <dt>
+ <tt>DROP(P)</tt>
+ </dt>
+ <dd>
+ A function which tells the underlay to drop the connection to a
+ peer <tt>P</tt>. FIXME what is this needed for?
+ </dd>
+ <dt>
+ <tt>RECEIVE(P, M)</tt>
+ </dt>
+ <dd>
+ A function or event that allows the local node to receive a protocol
+ message <tt>M</tt> as defined in this document from a peer <tt>P</tt>.
+ </dd>
+ <dt>
+ <tt>SEND(P, M)</tt>
+ </dt>
+ <dd>
+ A function that allows the local node to send a protocol message
+ <tt>M</tt> as defined in this document to a peer <tt>P</tt>.
+ If call to SEND fails, the message has not been sent.
+ </dd>
+ <dt>
+ <tt>NETWORK_SIZE_ESTIMATE(S)</tt>
+ </dt>
+ <dd>
+ A function or event that provides estimates on the network size
+ <tt>S</tt> for use in the DHT routing algorithms.
+ FIXME: What is S and give an example.
+ </dd>
+ <dt>
+ <tt>ADDRESS_ADDED(A)</tt>
+ </dt>
+ <dd>
+ The underlay signals us that an address <tt>A</tt> was added for our
+ local node.
+ This information is used to advertise
+ connectivity information to the local node.
+ <tt>A</tt> is a string suitable for inclusion in a HELLO payload
+ <xref target="hello_block"/>.
+ </dd>
+ <dt>
+ <tt>ADDRESS_DELETED(A)</tt>
+ </dt>
+ <dd>
+ The underlay signals us that an address <tt>A</tt> was removed.
+ This information is used, for example, to no longer advertise
+ this address.
+ </dd>
+ <dt>
+ <tt>VERIFY(blob)</tt>
+ </dt>
+ <dd>
+ Signature verification by underlay. FIXME unclear. Required?
+ </dd>
+ </dl>
+ </section>
+ <section>
+ <name>Bootstrapping</name>
+ <t>
+ It is assumed that the node is already connected to at least
+ one other node.
+ First, those initial nodes are sorted into their respective buckets.
+ </t>
+ <t>
+ In order to find the closest nodes in the network to itself, an
+ implementation MUST now periodically send HELLO GET queries for its own
+ node address.
+ Both the "record route" and "find node" message options are set in the
+ GET queries in order to learn nodes and network topology from the
+ message route and in order to receive approximate replies to the
+ query key (the node address).
+ </t>
+ <t>FIXME: Periodically -> more specific? No. Frequency may be adapted depending on network conditions, known nodes, busy/idle etc.</t>
+ <t>
+ Any implementation encountering a HELLO GET request initially
+ sends its own node address if it.
+ </t>
+ </section>
+ <section anchor="routing" numbered="true" toc="default">
+ <name>Routing</name>
+ <section anchor="peer_storage">
+ <name>Peer Storage</name>
<t>
- It is expected that there are basic mechanisms available to
- manage node connectivity and addressing.
- The required functionality are abstracted through the following
- procedures and events:
+ A R5N implementation must store the information on connected nodes
+ and update changes accordingly in a local persistance component such
+ as a database.
+ Upon receiving a connection notification from the Underlay through
+ <tt>NODE_CONNECTED</tt>, information on the new peer is added to the
+ local peer storage.
+ When disconnect is indicated by the Underlay through
+ <tt>NODE_DISCONNECTED</tt> the peer MUST be removed from the local
+ peer storage.
+ The data structure for managing connected nodes and their
+ metadata may be implemented using the k-buckets concept of
+ <xref target="Kademlia"/>.
+ In order to select nodes which are suitable destinations for
+ routing messages, R5N uses a hybrid approach:
+ Given an estimated network size N, the node selection for the
+ first N hops is random. After the initial N hops, node selection
+ follows an XOR-based node distance calculation.
+ </t>
+ </section>
+ <section anchor="routing_table">
+ <name>Routing Table</name>
+ <t>
+ As the message traverses a random path through the network for the
+ first N hops, it is essential that routing loops are avoided.
+ In R5N, a bloomfilter is used as part of the routing metadata in
+ messages. The bloomfilter is updates at each hop with the hops
+ node identity.
+ For the next hop selection in both the random and the deterministic
+ case, any node which is in the bloomfilter for the respective message
+ is not included in the node selection process.
+ </t>
+ <t>
+ The R5N routing component MUST implement the following functions:
</t>
<dl>
<dt>
- <tt>PEER_CONNECTED(P)</tt>
- </dt>
- <dd>
- is a signal that allows the DHT to react to a newly connected peer
- <tt>N</tt>.
- Such an event triggers, for example, updates in the
- routing table.
- </dd>
- <dt>
- <tt>PEER_DISCONNECTED(P)</tt>
- </dt>
- <dd>
- is a signal that allows the DHT to react to a recently disconnected
- peer.
- Such an event triggers, for example, updates in the
- routing table.
- </dd>
- <dt>
- <tt>TRY_CONNECT(N, A)</tt>
- </dt>
- <dd>
- A function which allows the local node to attempt the establishment of
- a connection to another node <tt>N</tt> using an address <tt>A</tt>.
- When the connection attempt is successful, information on the new
- peer is offered through the <tt>PEER_CONNECTED</tt> signal.
- </dd>
- <dt>
- <tt>HOLD(P)</tt>
+ <tt>GetDistance(A, B) -> Distance as Integer</tt>
</dt>
<dd>
- A function which tells the underlay to keep a hold on the connection
- to a peer <tt>P</tt>. FIXME what is this needed for?
+ this function calculates the binary XOR between A and B.
+ The resulting distance is interpreted as an integer where
+ the leftmost bit is the most significant bit.
</dd>
<dt>
- <tt>DROP(P)</tt>
+ <tt>SelectClosestNode(K, B) -> N</tt>
</dt>
<dd>
- A function which tells the underlay to drop the connection to a
- peer <tt>P</tt>. FIXME what is this needed for?
+ This function selects the connected node <tt>N</tt> from our
+ routing table with the shortest XOR-distance to the key <tt>K</tt>.
+ This means that for all other nodes <tt>N'</tt> in the routing table
+ <tt>GetDistance(N, K) < GetDistance(N',K)</tt>.
+ Nodes in the bloomfilter <tt>B</tt> are not considered.
</dd>
<dt>
- <tt>RECEIVE(P, M)</tt>
+ <tt>SelectRandomNode(B) -> N</tt>
</dt>
<dd>
- A function or event that allows the local node to receive a protocol
- message <tt>M</tt> as defined in this document from a peer <tt>P</tt>.
+ This function selects a random node <tt>N</tt> from all connected
+ nodes.
+ Nodes in the bloomfilter <tt>B</tt> are not considered.
</dd>
<dt>
- <tt>SEND(P, M)</tt>
+ <tt>SelectNode(K, H, B) -> N</tt>
</dt>
<dd>
- A function that allows the local node to send a protocol message
- <tt>M</tt> as defined in this document to a peer <tt>P</tt>.
- If call to SEND fails, the message has not been sent.
+ This function selects a node <tt>N</tt> depending on the
+ number of hops <tt>H</tt> parameter.
+ If <tt>H < NETWORK_SIZE_ESTIMATE</tt>
+ this function MUST return <tt>SelectRandomNode()</tt> and
+ <tt>SelectClosestnode(K)</tt> otherwise.
+ Nodes in the bloomfilter <tt>B</tt> are not considered.
</dd>
<dt>
- <tt>NETWORK_SIZE_ESTIMATE(S)</tt>
+ <tt>IsClosestNode(N, K, B) -> true | false</tt>
</dt>
<dd>
- A function or event that provides estimates on the network size
- <tt>S</tt> for use in the DHT routing algorithms.
- FIXME: What is S and give an example.
- </dd>
- <dt>
- <tt>ADDRESS_ADDED(A)</tt>
- </dt>
- <dd>
- The underlay signals us that an address <tt>A</tt> was added for our
- local node.
- This information is used to advertise
- connectivity information to the local node.
- <tt>A</tt> is a string suitable for inclusion in a HELLO payload
- <xref target="hello_block"/>.
- </dd>
- <dt>
- <tt>ADDRESS_DELETED(A)</tt>
- </dt>
- <dd>
- The underlay signals us that an address <tt>A</tt> was removed.
- This information is used, for example, to no longer advertise
- this address.
- </dd>
- <dt>
- <tt>VERIFY(blob)</tt>
- </dt>
- <dd>
- Signature verification by underlay. FIXME unclear. Required?
+ checks if <tt>N</tt> is the closest node for <tt>K</tt>
+ (cf. <tt>SelectClosestNode(K)</tt>).
+ Nodes in the bloomfilter <tt>B</tt> are not considered.
</dd>
</dl>
</section>
- <section>
- <name>Bootstrapping</name>
+ </section>
+ <section anchor="p2p_messages" numbered="true" toc="default">
+ <name>Message Processing</name>
+ <t>
+ The implementation MUST listen for <tt>RECEIVE(P, M)</tt> signals
+ from the Underlay and respond to the respective messages sent by
+ the peer <tt>P</tt>.
+ In the following, the wire formats of the messages and the required
+ processing are detailed.
+ The local node address is referred to as <tt>N</tt>.
+ </t>
+ <section anchor="p2p_bf" numbered="true" toc="default">
+ <name>Bloomfilter</name>
<t>
- It is assumed that the node is already connected to at least
- one other node.
- First, those initial nodes are sorted into their respective buckets.
- </t>
- <t>
- In order to find the closest nodes in the network to itself, an
- implementation MUST now periodically send HELLO GET queries for its own
- node address.
- Both the "record route" and "find node" message options are set in the
- GET queries in order to learn nodes and network topology from the
- message route and in order to receive approximate replies to the
- query key (the node address).
- </t>
- <t>FIXME: Periodically -> more specific? No. Frequency may be adapted depending on network conditions, known nodes, busy/idle etc.</t>
- <t>
- Any implementation encountering a HELLO GET request initially
- sends its own node address if it.
+ In order to prevent circular routes, GET and PUT messages contain
+ a 128-bit Bloom filter (m=128). The Bloom filter is used to detect duplicate
+ node addresses along the route.
+ A Bloom filter "bf" is initially empty, consisting only of zeroes.
+ There are two functions which can be invoked on the Bloom filter:
+ BF-SET(bf, e) and BF-TEST(bf, e) where "e" is an element which is to
+ be added to the Bloom filter or queried against the set.
+ Any bloom filter uses k=16 different hash functions each of which is
+ defined as follows:
</t>
</section>
- <section anchor="routing" numbered="true" toc="default">
- <name>Routing</name>
- <section anchor="peer_storage">
- <name>Peer Storage</name>
- <t>
- A R5N implementation must store the information on connected nodes
- and update changes accordingly in a local persistance component such
- as a database.
- Upon receiving a connection notification from the Underlay through
- <tt>NODE_CONNECTED</tt>, information on the new peer is added to the
- local peer storage.
- When disconnect is indicated by the Underlay through
- <tt>NODE_DISCONNECTED</tt> the peer MUST be removed from the local
- peer storage.
- The data structure for managing connected nodes and their
- metadata may be implemented using the k-buckets concept of
- <xref target="Kademlia"/>.
- In order to select nodes which are suitable destinations for
- routing messages, R5N uses a hybrid approach:
- Given an estimated network size N, the node selection for the
- first N hops is random. After the initial N hops, node selection
- follows an XOR-based node distance calculation.
- </t>
- </section>
- <section anchor="routing_table">
- <name>Routing Table</name>
- <t>
- As the message traverses a random path through the network for the
- first N hops, it is essential that routing loops are avoided.
- In R5N, a bloomfilter is used as part of the routing metadata in
- messages. The bloomfilter is updates at each hop with the hops
- node identity.
- For the next hop selection in both the random and the deterministic
- case, any node which is in the bloomfilter for the respective message
- is not included in the node selection process.
- </t>
- <t>
- The R5N routing component MUST implement the following functions:
- </t>
- <dl>
- <dt>
- <tt>GetDistance(A, B) -> Distance as Integer</tt>
- </dt>
- <dd>
- this function calculates the binary XOR between A and B.
- The resulting distance is interpreted as an integer where
- the leftmost bit is the most significant bit.
- </dd>
- <dt>
- <tt>SelectClosestNode(K, B) -> N</tt>
- </dt>
- <dd>
- This function selects the connected node <tt>N</tt> from our
- routing table with the shortest XOR-distance to the key <tt>K</tt>.
- This means that for all other nodes <tt>N'</tt> in the routing table
- <tt>GetDistance(N, K) < GetDistance(N',K)</tt>.
- Nodes in the bloomfilter <tt>B</tt> are not considered.
- </dd>
- <dt>
- <tt>SelectRandomNode(B) -> N</tt>
- </dt>
- <dd>
- This function selects a random node <tt>N</tt> from all connected
- nodes.
- Nodes in the bloomfilter <tt>B</tt> are not considered.
- </dd>
- <dt>
- <tt>SelectNode(K, H, B) -> N</tt>
- </dt>
- <dd>
- This function selects a node <tt>N</tt> depending on the
- number of hops <tt>H</tt> parameter.
- If <tt>H < NETWORK_SIZE_ESTIMATE</tt>
- this function MUST return <tt>SelectRandomNode()</tt> and
- <tt>SelectClosestnode(K)</tt> otherwise.
- Nodes in the bloomfilter <tt>B</tt> are not considered.
- </dd>
- <dt>
- <tt>IsClosestNode(N, K, B) -> true | false</tt>
- </dt>
- <dd>
- checks if <tt>N</tt> is the closest node for <tt>K</tt>
- (cf. <tt>SelectClosestNode(K)</tt>).
- Nodes in the bloomfilter <tt>B</tt> are not considered.
- </dd>
- </dl>
- </section>
+ <section anchor="p2p_xq" numbered="true" toc="default">
+ <name>Extended query</name>
+ <t>TODO: Talk about XQuery in the context of messages.</t>
</section>
- <section anchor="p2p_messages" numbered="true" toc="default">
- <name>Message Processing</name>
- <t>
- The implementation MUST listen for <tt>RECEIVE(P, M)</tt> signals
- from the Underlay and respond to the respective messages sent by
- the peer <tt>P</tt>.
- In the following, the wire formats of the messages and the required
- processing are detailed.
- The local node address is referred to as <tt>N</tt>.
- </t>
- <section anchor="p2p_bf" numbered="true" toc="default">
- <name>Bloomfilter</name>
- <t>
- In order to prevent circular routes, GET and PUT messages contain
- a 128-bit Bloom filter (m=128). The Bloom filter is used to detect duplicate
- node addresses along the route.
- A Bloom filter "bf" is initially empty, consisting only of zeroes.
- There are two functions which can be invoked on the Bloom filter:
- BF-SET(bf, e) and BF-TEST(bf, e) where "e" is an element which is to
- be added to the Bloom filter or queried against the set.
- Any bloom filter uses k=16 different hash functions each of which is
- defined as follows:
- </t>
- </section>
- <section anchor="p2p_xq" numbered="true" toc="default">
- <name>Extended query</name>
- <t>TODO: Talk about XQuery in the context of messages.</t>
- </section>
- <section anchor="p2p_put" numbered="true" toc="default">
- <name>PutMessage</name>
- <section anchor="p2p_put_wire">
- <name>Wire Format</name>
- <figure anchor="figure_putmsg">
- <artwork name="" type="" align="left" alt=""><![CDATA[
+ <section anchor="p2p_put" numbered="true" toc="default">
+ <name>PutMessage</name>
+ <section anchor="p2p_put_wire">
+ <name>Wire Format</name>
+ <figure anchor="figure_putmsg">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSIZE | MTYPE | BTYPE |
@@ -644,132 +644,132 @@ Connectivity | |Underlay| |Underlay|
/ BLOCK (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
- </figure>
- <t>where:</t>
- <dl>
- <dt>MSIZE</dt>
- <dd>
- denotes the size of this message in network byte order.
- </dd>
- <dt>MTYPE</dt>
- <dd>
- is the 16-bit message type. This type can be one of the DHT message
- types but for put messages it must be set to
- the value 146 in network byte order.
- </dd>
- <dt>BTYPE</dt>
- <dd>
- is a 32-bit block type field. The block type indicates the content
- type of the payload. In network byte order.
- </dd>
- <dt>OPTIONS</dt>
- <dd>
- is a 16-bit options field (see below).
- </dd>
- <dt>HOPCOUNT</dt>
- <dd>
- is a 16-bit number indicating how many hops this message has
- traversed to far. In network byte order.
- </dd>
- <dt>REPL_LVL</dt>
- <dd>
- is a 16-bit number indicating the desired replication level of
- the data. In network byte order.
- </dd>
- <dt>PATH_LEN</dt>
- <dd>
- is a 16-bit number indicating the length of the PUT path recorded
- in PUTPATH.
- As PUTPATH is optional, this value may be zero.
- In network byte order.
- </dd>
- <dt>EXPIRATION</dt>
- <dd>
- denotes the absolute 64-bit expiration date of the content.
- In microseconds since midnight (0 hour), January 1, 1970 in network
- byte order.
- </dd>
- <dt>BLOOMFILTER</dt>
- <dd>
- A bloomfilter (for node addresses) to stop circular routes.
- </dd>
- <dt>KEY</dt>
- <dd>
- The key under which the PUT request wants to store content
- under.
- </dd>
- <dt>PUTPATH</dt>
- <dd>
- the variable-length PUT path.
- The path consists of a list of PATH_LEN node addresses.
- </dd>
- <dt>BLOCK</dt>
- <dd>
- the variable-length block payload. The contents are determined
- by the BTYPE field.
- </dd>
- </dl>
- </section>
- <section anchor="p2p_put_processing">
- <name>Processing</name>
- <t>
- Upon receiving a <tt>PutMessage</tt> from a peer <tt>P</tt>.
- An implementation MUST process it step by step as follows:
- </t>
- <ol>
- <li>
- The <tt>EXPIRATION</tt> field is evaluated.
- If the message is expired, it MUST be discarded.
- </li>
- <li>
- If the <tt>BTYPE</tt> is not supported by the implementation,
- no validation of the block payload is performed and processing
- continues at (4).
- Else, the block MUST be validated as defined in (3).
- </li>
- <li>
- The block payload of the message is evaluated using according
- to the <tt>BTYPE</tt> using the respective
- <tt>ValidateBlockStoreRequest</tt> procedure.
- If the block payload is invalid or does not match the key,
- it MUST be discarded.
- </li>
- <li>
- The node address of the sender peer <tt>P</tt> SHOULD be in <tt>BLOOMFILTER</tt>.
- If not, the implementation MAY log an error, but MUST continue.
- </li>
- <li>
- If the <tt>RecordRoute</tt> flag is set in OPTIONS,
- the local node address MUST be appended to the <tt>PUTPATH</tt>
- of the message.
- </li>
- <li>
- If the local node is the closest node
- (cf. <tt>IsClosestNode(N, Key)</tt>) or the <tt>DemultiplexEverywhere</tt>
- options flag ist set, the message MUST
- be stored locally in the block storage.
- </li>
- <li>
- Given the value in <tt>REPL_LVL</tt>, the number of peers to
- forward to MUST be calculated. If there is at least one
- peers to forward to, the implementation SHOULD select up to this
- number of peers to forward the message to. The implementation MAY
- forward to fewer or no peers in order to handle resource constraints
- such as bandwidth.
- Finally, the local node address MUST be added to the
- <tt>BLOOMFILTER</tt> of the forwarded message.
- For all peers with node address <tt>P</tt> chosen to forward the message
- to, <tt>SEND(P, PutMessage)</tt> is called.
- </li>
- </ol>
- </section>
+ </figure>
+ <t>where:</t>
+ <dl>
+ <dt>MSIZE</dt>
+ <dd>
+ denotes the size of this message in network byte order.
+ </dd>
+ <dt>MTYPE</dt>
+ <dd>
+ is the 16-bit message type. This type can be one of the DHT message
+ types but for put messages it must be set to
+ the value 146 in network byte order.
+ </dd>
+ <dt>BTYPE</dt>
+ <dd>
+ is a 32-bit block type field. The block type indicates the content
+ type of the payload. In network byte order.
+ </dd>
+ <dt>OPTIONS</dt>
+ <dd>
+ is a 16-bit options field (see below).
+ </dd>
+ <dt>HOPCOUNT</dt>
+ <dd>
+ is a 16-bit number indicating how many hops this message has
+ traversed to far. In network byte order.
+ </dd>
+ <dt>REPL_LVL</dt>
+ <dd>
+ is a 16-bit number indicating the desired replication level of
+ the data. In network byte order.
+ </dd>
+ <dt>PATH_LEN</dt>
+ <dd>
+ is a 16-bit number indicating the length of the PUT path recorded
+ in PUTPATH.
+ As PUTPATH is optional, this value may be zero.
+ In network byte order.
+ </dd>
+ <dt>EXPIRATION</dt>
+ <dd>
+ denotes the absolute 64-bit expiration date of the content.
+ In microseconds since midnight (0 hour), January 1, 1970 in network
+ byte order.
+ </dd>
+ <dt>BLOOMFILTER</dt>
+ <dd>
+ A bloomfilter (for node addresses) to stop circular routes.
+ </dd>
+ <dt>KEY</dt>
+ <dd>
+ The key under which the PUT request wants to store content
+ under.
+ </dd>
+ <dt>PUTPATH</dt>
+ <dd>
+ the variable-length PUT path.
+ The path consists of a list of PATH_LEN node addresses.
+ </dd>
+ <dt>BLOCK</dt>
+ <dd>
+ the variable-length block payload. The contents are determined
+ by the BTYPE field.
+ </dd>
+ </dl>
+ </section>
+ <section anchor="p2p_put_processing">
+ <name>Processing</name>
+ <t>
+ Upon receiving a <tt>PutMessage</tt> from a peer <tt>P</tt>.
+ An implementation MUST process it step by step as follows:
+ </t>
+ <ol>
+ <li>
+ The <tt>EXPIRATION</tt> field is evaluated.
+ If the message is expired, it MUST be discarded.
+ </li>
+ <li>
+ If the <tt>BTYPE</tt> is not supported by the implementation,
+ no validation of the block payload is performed and processing
+ continues at (4).
+ Else, the block MUST be validated as defined in (3).
+ </li>
+ <li>
+ The block payload of the message is evaluated using according
+ to the <tt>BTYPE</tt> using the respective
+ <tt>ValidateBlockStoreRequest</tt> procedure.
+ If the block payload is invalid or does not match the key,
+ it MUST be discarded.
+ </li>
+ <li>
+ The node address of the sender peer <tt>P</tt> SHOULD be in <tt>BLOOMFILTER</tt>.
+ If not, the implementation MAY log an error, but MUST continue.
+ </li>
+ <li>
+ If the <tt>RecordRoute</tt> flag is set in OPTIONS,
+ the local node address MUST be appended to the <tt>PUTPATH</tt>
+ of the message.
+ </li>
+ <li>
+ If the local node is the closest node
+ (cf. <tt>IsClosestNode(N, Key)</tt>) or the <tt>DemultiplexEverywhere</tt>
+ options flag ist set, the message MUST
+ be stored locally in the block storage.
+ </li>
+ <li>
+ Given the value in <tt>REPL_LVL</tt>, the number of peers to
+ forward to MUST be calculated. If there is at least one
+ peers to forward to, the implementation SHOULD select up to this
+ number of peers to forward the message to. The implementation MAY
+ forward to fewer or no peers in order to handle resource constraints
+ such as bandwidth.
+ Finally, the local node address MUST be added to the
+ <tt>BLOOMFILTER</tt> of the forwarded message.
+ For all peers with node address <tt>P</tt> chosen to forward the message
+ to, <tt>SEND(P, PutMessage)</tt> is called.
+ </li>
+ </ol>
</section>
- <section anchor="p2p_get" numbered="true" toc="default">
- <name>GetMessage</name>
- <section anchor="p2p_get_wire">
- <name>Wire Format</name>
- <figure anchor="figure_getmsg">
- <artwork name="" type="" align="left" alt=""><![CDATA[
+ </section>
+ <section anchor="p2p_get" numbered="true" toc="default">
+ <name>GetMessage</name>
+ <section anchor="p2p_get_wire">
+ <name>Wire Format</name>
+ <figure anchor="figure_getmsg">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSIZE | MTYPE | BTYPE |
@@ -789,134 +789,134 @@ Connectivity | |Underlay| |Underlay|
/ BF_RESULT (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
- </figure>
- <t>where:</t>
- <dl>
- <dt>MSIZE</dt>
- <dd>
- denotes the size of this message in network byte order.
- </dd>
- <dt>MTYPE</dt>
- <dd>
- is the 16-bit message type. It must be set to
- the value 147 in network byte order.
- </dd>
- <dt>BTYPE</dt>
- <dd>
- is a 32-bit block type field. The block type indicates the content
- type of the payload. In network byte order.
- </dd>
- <dt>OPTIONS</dt>
- <dd>
- is a 16-bit options field (see below).
- </dd>
- <dt>HOPCOUNT</dt>
- <dd>
- is a 16-bit number indicating how many hops this message has
- traversed to far. In network byte order.
- </dd>
- <dt>REPL_LVL</dt>
- <dd>
- is a 16-bit number indicating the desired replication level of
- the data. In network byte order.
- </dd>
- <dt>XQ_SIZE</dt>
- <dd>
- is a 32-bit number indicating the length of the optional
- extended query XQUERY. In network byte order.
- </dd>
- <dt>BLOOMFILTER</dt>
- <dd>
- A bloomfilter (for node identities) to stop circular routes.
- </dd>
- <dt>KEY</dt>
- <dd>
- The key under which the PUT request wants to store content
- under.
- </dd>
- <dt>XQUERY</dt>
- <dd>
- the variable-length extended query. Optional.
- </dd>
- <dt>BF_MUTATOR</dt>
- <dd>
- The 32-bit bloomfilter mutator for the result bloomfilter.
- </dd>
- <dt>RESULT_BF</dt>
- <dd>
- the variable-length result bloomfilter.
- </dd>
- </dl>
- </section>
- <section anchor="p2p_get_processing">
- <name>Processing</name>
- <t>
- Upon receiving a <tt>GetMmessage</tt> from a peer an
- implementation MUST process it step by step as follows:
- </t>
- <ol>
- <li>
- The <tt>KEY</tt> and <tt>XQUERY</tt> is validated against the
- requested <tt>BTYPE</tt> as defined by its respective
- <tt>ValidateBlockQuery</tt> procedure.
- If the <tt>BTYPE</tt> is not supported, or if the block key
- does not match or if the <tt>XQUERY</tt> is malformed,
- the message MUST be discarded.
- </li>
- <li>
- The node address of the sender peer <tt>P</tt> SHOULD be in the
- BLOOMFILTER. If not, the
- implementation MAY log an error, but MUST continue.
- </li>
- <li>
- <t>
- If the local node is the closest node
- (cf. <tt>IsClosestNode (N, Key)</tt>) or the
- <tt>DemultiplexEverywhere</tt> options flag is set, a reply
- MUST be produced:
- </t>
- <ol>
- <li>
- If <tt>OPTIONS</tt> indicate a <tt>FindNode</tt> request,
- FIXME the node selection
- foo from buckets that probably needs fixing. Take into account
- <tt>REPLY_BF</tt>
- </li>
- <li>
- Else, if there is a block in the local Block Storage which is
- not already in the <tt>RESULT_BF</tt>,
- a ResultMessage MUST be sent.
- FIXME link to how the result is sent?
- </li>
- </ol>
- </li>
- <li>
- FIXME: We only handle if not GNUNET_BLOCK_EVALUATION_OK_LAST.
- This means that we must evaluate the Reply produced in the
- previous step using <tt>ValidateBlockReply</tt> for this
- <tt>BTYPE</tt>
- </li>
- <li>
- Given the value in REPL_LVL, the number of nodes to forward to
- MUST be calculated (NUM-FORWARD-nodeS). If there is at least one
- node to forward to, the implementation SHOULD select up to this
- number of nodes to forward the message to. The implementation MAY
- forward to fewer or no nodes in order to handle resource constraints
- such as bandwidth.
- The message BLOOMFILTER MUST be updated with the local node
- address <tt>N</tt>.
- For all peers with node address <tt>P'</tt> chosen to forward the message
- to, <tt>SEND(P', PutMessage)</tt> is called.
- </li>
- </ol>
- </section>
+ </figure>
+ <t>where:</t>
+ <dl>
+ <dt>MSIZE</dt>
+ <dd>
+ denotes the size of this message in network byte order.
+ </dd>
+ <dt>MTYPE</dt>
+ <dd>
+ is the 16-bit message type. It must be set to
+ the value 147 in network byte order.
+ </dd>
+ <dt>BTYPE</dt>
+ <dd>
+ is a 32-bit block type field. The block type indicates the content
+ type of the payload. In network byte order.
+ </dd>
+ <dt>OPTIONS</dt>
+ <dd>
+ is a 16-bit options field (see below).
+ </dd>
+ <dt>HOPCOUNT</dt>
+ <dd>
+ is a 16-bit number indicating how many hops this message has
+ traversed to far. In network byte order.
+ </dd>
+ <dt>REPL_LVL</dt>
+ <dd>
+ is a 16-bit number indicating the desired replication level of
+ the data. In network byte order.
+ </dd>
+ <dt>XQ_SIZE</dt>
+ <dd>
+ is a 32-bit number indicating the length of the optional
+ extended query XQUERY. In network byte order.
+ </dd>
+ <dt>BLOOMFILTER</dt>
+ <dd>
+ A bloomfilter (for node identities) to stop circular routes.
+ </dd>
+ <dt>KEY</dt>
+ <dd>
+ The key under which the PUT request wants to store content
+ under.
+ </dd>
+ <dt>XQUERY</dt>
+ <dd>
+ the variable-length extended query. Optional.
+ </dd>
+ <dt>BF_MUTATOR</dt>
+ <dd>
+ The 32-bit bloomfilter mutator for the result bloomfilter.
+ </dd>
+ <dt>RESULT_BF</dt>
+ <dd>
+ the variable-length result bloomfilter.
+ </dd>
+ </dl>
</section>
- <section anchor="p2p_result" numbered="true" toc="default">
- <name>ResultMessage</name>
- <section anchor="p2p_result_wire">
- <name>Wire Format</name>
- <figure anchor="figure_resmsg">
- <artwork name="" type="" align="left" alt=""><![CDATA[
+ <section anchor="p2p_get_processing">
+ <name>Processing</name>
+ <t>
+ Upon receiving a <tt>GetMmessage</tt> from a peer an
+ implementation MUST process it step by step as follows:
+ </t>
+ <ol>
+ <li>
+ The <tt>KEY</tt> and <tt>XQUERY</tt> is validated against the
+ requested <tt>BTYPE</tt> as defined by its respective
+ <tt>ValidateBlockQuery</tt> procedure.
+ If the <tt>BTYPE</tt> is not supported, or if the block key
+ does not match or if the <tt>XQUERY</tt> is malformed,
+ the message MUST be discarded.
+ </li>
+ <li>
+ The node address of the sender peer <tt>P</tt> SHOULD be in the
+ BLOOMFILTER. If not, the
+ implementation MAY log an error, but MUST continue.
+ </li>
+ <li>
+ <t>
+ If the local node is the closest node
+ (cf. <tt>IsClosestNode (N, Key)</tt>) or the
+ <tt>DemultiplexEverywhere</tt> options flag is set, a reply
+ MUST be produced:
+ </t>
+ <ol>
+ <li>
+ If <tt>OPTIONS</tt> indicate a <tt>FindNode</tt> request,
+ FIXME the node selection
+ foo from buckets that probably needs fixing. Take into account
+ <tt>REPLY_BF</tt>
+ </li>
+ <li>
+ Else, if there is a block in the local Block Storage which is
+ not already in the <tt>RESULT_BF</tt>,
+ a ResultMessage MUST be sent.
+ FIXME link to how the result is sent?
+ </li>
+ </ol>
+ </li>
+ <li>
+ FIXME: We only handle if not GNUNET_BLOCK_EVALUATION_OK_LAST.
+ This means that we must evaluate the Reply produced in the
+ previous step using <tt>ValidateBlockReply</tt> for this
+ <tt>BTYPE</tt>
+ </li>
+ <li>
+ Given the value in REPL_LVL, the number of nodes to forward to
+ MUST be calculated (NUM-FORWARD-nodeS). If there is at least one
+ node to forward to, the implementation SHOULD select up to this
+ number of nodes to forward the message to. The implementation MAY
+ forward to fewer or no nodes in order to handle resource constraints
+ such as bandwidth.
+ The message BLOOMFILTER MUST be updated with the local node
+ address <tt>N</tt>.
+ For all peers with node address <tt>P'</tt> chosen to forward the message
+ to, <tt>SEND(P', PutMessage)</tt> is called.
+ </li>
+ </ol>
+ </section>
+ </section>
+ <section anchor="p2p_result" numbered="true" toc="default">
+ <name>ResultMessage</name>
+ <section anchor="p2p_result_wire">
+ <name>Wire Format</name>
+ <figure anchor="figure_resmsg">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSIZE | MTYPE | BTYPE |
@@ -938,229 +938,229 @@ Connectivity | |Underlay| |Underlay|
/ (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
- </figure>
- <t>where:</t>
- <dl>
- <dt>MSIZE</dt>
- <dd>
- denotes the size of this message in network byte order.
- </dd>
- <dt>MTYPE</dt>
- <dd>
- is the 16-bit message type. This type can be one of the DHT message
- types but for put messages it must be set to
- the value 148 in network byte order.
- </dd>
- <dt>OPTIONS</dt>
- <dd>
- is a 16-bit options field (see below).
- </dd>
- <dt>BTYPE</dt>
- <dd>
- is a 32-bit block type field. The block type indicates the content
- type of the payload. In network byte order.
- </dd>
- <dt>PUTPATH_L</dt>
- <dd>
- is a 16-bit number indicating the length of the PUT path recorded
- in PUTPATH. As PUTPATH is optiona, this value may be zero.
- In network byte order.
- </dd>
- <dt>GET_PATH_LEN</dt>
- <dd>
- is a 16-bit number indicating the length of the GET path recorded
- in GETPATH. As PUTPATH is optiona, this value may be zero.
- In network byte order.
- </dd>
- <dt>EXPIRATION</dt>
- <dd>
- denotes the absolute 64-bit expiration date of the content.
- In microseconds since midnight (0 hour), January 1, 1970 in network
- byte order.
- </dd>
- <dt>KEY</dt>
- <dd>
- The key under which the PUT request wants to store content
- under.
- </dd>
- <dt>PUTPATH</dt>
- <dd>
- the variable-length PUT path.
- The path consists of a list of PATH_LEN node addresses.
- </dd>
- <dt>GETPATH</dt>
- <dd>
- the variable-length PUT path.
- The path consists of a list of PATH_LEN node addresses.
- </dd>
- <dt>BLOCK</dt>
- <dd>
- the variable-length resource record data payload.
- The contents are defined by the respective type of the resource record.
- </dd>
- </dl>
- </section>
- <section anchor="p2p_result_processing">
- <name>Processing</name>
- <t>
- Upon receiving a <tt>ResultMessage</tt> from a connected node.
- An implementation MUST process it step by step as follows:
- </t>
- <ol>
- <li>
- The <tt>EXPIRATION</tt> field is evaluated.
- If the message is expired, it MUST be discarded.
- </li>
- <li>
- If the MTYPE of the message indicates a HELLO block, it
- must be validated according to <xref target="hello_block"/>.
- The payload MUST be considered for the local routing table by
- trying to establish a connection to the node using the information
- from the HELLO block. If a connection can be established,
- the node is added to the <tt>KBuckets</tt> routing table.
- </li>
- <li>
- If the sender node of the message is already found in the
- GETPATH, the path MUST be truncated at this position.
- The implementation MAY log a warning in such a case.
- </li>
- <li>
- If the <tt>KEY</tt> of this <tt>ResultMessage</tt> is found in the
- list of pending local queries, the <tt>KEY</tt> and <tt>XQUERY</tt>
- are validated against the requested BTYPE using the respective
- block type implementation of <tt>ValidateBlockReply</tt>.
- If the BTYPE is not supported, or if the block key
- does not match the BTYPE or if the XQUERY is malformed,
- the message MUST be discarded.
- </li>
- <li>
- The implementation MAY cache RESULT messages.
- </li>
- <li>
- <t>
- If requests by other nodes for this KEY or BTYPE are known,
- the result block is validated against each request using
- the respective <tt>ValidateBlockReply</tt> function.
- </t>
- <t>
- If the request options include <tt>FindNode</tt> and the result
- message block type is HELLO the block validation must use the
- key derived using <tt>DeriveBlockKey</tt> as the key included in
- the request is only approximate. (FIXME: So we extract the key
- to then check it again against the block? This does not make sense...)
- </t>
- <t>
- If the result message block cannot be verified against the
- <tt>KEY</tt> of the result message or if <tt>BLOCK</tt> is
- malformed, the message MUST be discarded.
- </t>
- <t>
- For each pending request the reply is routed to the requesting
- node <tt>N'</tt>. FIXME routed to node or forwarded to peer?
- </t>
- </li>
- </ol>
- </section>
- </section>
- </section>
- <section anchor="blockstorage" numbered="true" toc="default">
- <name>Block Storage</name>
- <section>
- <name>Block Processing</name>
- <t>RequestEvaluationResult</t>
+ </figure>
+ <t>where:</t>
<dl>
- <dt>REQUEST_VALID</dt>
- <dd>Query is valid, no reply given.</dd>
- <dt>REQUEST_INVALID</dt>
+ <dt>MSIZE</dt>
<dd>
- Query format does not match block type. For example, XQuery not
- given or of size of XQuery is not appropriate for type.
+ denotes the size of this message in network byte order.
</dd>
- </dl>
- <t>ReplyEvaluationResult</t>
- <dl>
- <dt>OK_MORE</dt>
- <dd>Valid result, and there may be more.</dd>
- <dt>OK_LAST</dt>
- <dd>Last possible valid result.</dd>
- <dt>OK_DUPLICATE</dt>
- <dd>Valid result, but duplicate.</dd>
- <dt>RESULT_INVALID</dt>
- <dd>Invalid result. Block does not match query. Value = 4.</dd>
- <dt>RESULT_IRRELEVANT</dt>
- <dd>Block does not match xquery. Valid result, but not relevant for the request.</dd>
- </dl>
- </section>
- <section anchor="block_functions">
- <name>Block Functions</name>
- <t>
- Any block type implementation MUST implement the following functions.
- </t>
- <dl>
- <dt>ValidateBlockQuery(Key, XQuery) -> RequestEvaluationResult</dt>
+ <dt>MTYPE</dt>
<dd>
- is used to evaluate the request for a block. It is used as part of
- <tt>GetMessage</tt> processing, where the block payload is still unkown,
- but the block <tt>XQuery</tt> (FIXME: Undefined here) and <tt>Key</tt> can and
- MUST be verified, if possible.
+ is the 16-bit message type. This type can be one of the DHT message
+ types but for put messages it must be set to
+ the value 148 in network byte order.
</dd>
- <dt>ValidateBlockStoreRequest(Block, Key) -> RequestEvaluationResult</dt>
+ <dt>OPTIONS</dt>
<dd>
- is used to evaluate a block including its key and payload.
- It is used as part of <tt>PutMessage</tt> processing.
- The validation MUST include a check of the block payload against the
- <tt>Key</tt> under which it is requested to be stored.
+ is a 16-bit options field (see below).
</dd>
- <dt>ValidateBlockReply(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
+ <dt>BTYPE</dt>
<dd>
- is used to evaluate a block including its <tt>Key</tt> and payload.
- It is used as part <tt>ResultMessage</tt> processing.
- The validation of the respective <tt>Block</tt> requires a pending local query
- or a previously routed request of another node and its associated
- XQuery data and Key.
- The validation MUST include a check of the block payload against the
- key under which it is requested to be stored.
+ is a 32-bit block type field. The block type indicates the content
+ type of the payload. In network byte order.
</dd>
- <dt>DeriveBlockKey(Block) -> Key</dt>
+ <dt>PUTPATH_L</dt>
<dd>
- is used to synthesize the block key from the block payload
- and metadata. It is used as part of FIND-node message processing.
+ is a 16-bit number indicating the length of the PUT path recorded
+ in PUTPATH. As PUTPATH is optiona, this value may be zero.
+ In network byte order.
</dd>
- <dt>FilterResult(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
+ <dt>GET_PATH_LEN</dt>
<dd>
- is used to filter results stored in the local block storage for local
- queries. Locally stored blocks from previously observed
- <tt>ResultMessages</tt> and <tt>PutMessages</tt> MAY use this
- function instead of <tt>ValidateBlockReply</tt> in order to
- avoid revalidation of the block and only perform filtering based on
- request parameters.
+ is a 16-bit number indicating the length of the GET path recorded
+ in GETPATH. As PUTPATH is optiona, this value may be zero.
+ In network byte order.
+ </dd>
+ <dt>EXPIRATION</dt>
+ <dd>
+ denotes the absolute 64-bit expiration date of the content.
+ In microseconds since midnight (0 hour), January 1, 1970 in network
+ byte order.
+ </dd>
+ <dt>KEY</dt>
+ <dd>
+ The key under which the PUT request wants to store content
+ under.
+ </dd>
+ <dt>PUTPATH</dt>
+ <dd>
+ the variable-length PUT path.
+ The path consists of a list of PATH_LEN node addresses.
+ </dd>
+ <dt>GETPATH</dt>
+ <dd>
+ the variable-length PUT path.
+ The path consists of a list of PATH_LEN node addresses.
+ </dd>
+ <dt>BLOCK</dt>
+ <dd>
+ the variable-length resource record data payload.
+ The contents are defined by the respective type of the resource record.
</dd>
</dl>
</section>
- <section anchor="block_types">
- <name>Block Types</name>
+ <section anchor="p2p_result_processing">
+ <name>Processing</name>
<t>
- Applications can and should define their own block types.
- The block type determines the format and handling of the block
- payload by nodes in PUT and RESULT messages.
- Block types MUST be registered with GANA <xref target="gana"/>.
+ Upon receiving a <tt>ResultMessage</tt> from a connected node.
+ An implementation MUST process it step by step as follows:
</t>
+ <ol>
+ <li>
+ The <tt>EXPIRATION</tt> field is evaluated.
+ If the message is expired, it MUST be discarded.
+ </li>
+ <li>
+ If the MTYPE of the message indicates a HELLO block, it
+ must be validated according to <xref target="hello_block"/>.
+ The payload MUST be considered for the local routing table by
+ trying to establish a connection to the node using the information
+ from the HELLO block. If a connection can be established,
+ the node is added to the <tt>KBuckets</tt> routing table.
+ </li>
+ <li>
+ If the sender node of the message is already found in the
+ GETPATH, the path MUST be truncated at this position.
+ The implementation MAY log a warning in such a case.
+ </li>
+ <li>
+ If the <tt>KEY</tt> of this <tt>ResultMessage</tt> is found in the
+ list of pending local queries, the <tt>KEY</tt> and <tt>XQUERY</tt>
+ are validated against the requested BTYPE using the respective
+ block type implementation of <tt>ValidateBlockReply</tt>.
+ If the BTYPE is not supported, or if the block key
+ does not match the BTYPE or if the XQUERY is malformed,
+ the message MUST be discarded.
+ </li>
+ <li>
+ The implementation MAY cache RESULT messages.
+ </li>
+ <li>
+ <t>
+ If requests by other nodes for this KEY or BTYPE are known,
+ the result block is validated against each request using
+ the respective <tt>ValidateBlockReply</tt> function.
+ </t>
+ <t>
+ If the request options include <tt>FindNode</tt> and the result
+ message block type is HELLO the block validation must use the
+ key derived using <tt>DeriveBlockKey</tt> as the key included in
+ the request is only approximate. (FIXME: So we extract the key
+ to then check it again against the block? This does not make sense...)
+ </t>
+ <t>
+ If the result message block cannot be verified against the
+ <tt>KEY</tt> of the result message or if <tt>BLOCK</tt> is
+ malformed, the message MUST be discarded.
+ </t>
+ <t>
+ For each pending request the reply is routed to the requesting
+ node <tt>N'</tt>. FIXME routed to node or forwarded to peer?
+ </t>
+ </li>
+ </ol>
+ </section>
+ </section>
+ </section>
+ <section anchor="blockstorage" numbered="true" toc="default">
+ <name>Block Storage</name>
+ <section>
+ <name>Block Processing</name>
+ <t>RequestEvaluationResult</t>
+ <dl>
+ <dt>REQUEST_VALID</dt>
+ <dd>Query is valid, no reply given.</dd>
+ <dt>REQUEST_INVALID</dt>
+ <dd>
+ Query format does not match block type. For example, XQuery not
+ given or of size of XQuery is not appropriate for type.
+ </dd>
+ </dl>
+ <t>ReplyEvaluationResult</t>
+ <dl>
+ <dt>OK_MORE</dt>
+ <dd>Valid result, and there may be more.</dd>
+ <dt>OK_LAST</dt>
+ <dd>Last possible valid result.</dd>
+ <dt>OK_DUPLICATE</dt>
+ <dd>Valid result, but duplicate.</dd>
+ <dt>RESULT_INVALID</dt>
+ <dd>Invalid result. Block does not match query. Value = 4.</dd>
+ <dt>RESULT_IRRELEVANT</dt>
+ <dd>Block does not match xquery. Valid result, but not relevant for the request.</dd>
+ </dl>
+ </section>
+ <section anchor="block_functions">
+ <name>Block Functions</name>
+ <t>
+ Any block type implementation MUST implement the following functions.
+ </t>
+ <dl>
+ <dt>ValidateBlockQuery(Key, XQuery) -> RequestEvaluationResult</dt>
+ <dd>
+ is used to evaluate the request for a block. It is used as part of
+ <tt>GetMessage</tt> processing, where the block payload is still unkown,
+ but the block <tt>XQuery</tt> (FIXME: Undefined here) and <tt>Key</tt> can and
+ MUST be verified, if possible.
+ </dd>
+ <dt>ValidateBlockStoreRequest(Block, Key) -> RequestEvaluationResult</dt>
+ <dd>
+ is used to evaluate a block including its key and payload.
+ It is used as part of <tt>PutMessage</tt> processing.
+ The validation MUST include a check of the block payload against the
+ <tt>Key</tt> under which it is requested to be stored.
+ </dd>
+ <dt>ValidateBlockReply(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
+ <dd>
+ is used to evaluate a block including its <tt>Key</tt> and payload.
+ It is used as part <tt>ResultMessage</tt> processing.
+ The validation of the respective <tt>Block</tt> requires a pending local query
+ or a previously routed request of another node and its associated
+ XQuery data and Key.
+ The validation MUST include a check of the block payload against the
+ key under which it is requested to be stored.
+ </dd>
+ <dt>DeriveBlockKey(Block) -> Key</dt>
+ <dd>
+ is used to synthesize the block key from the block payload
+ and metadata. It is used as part of FIND-node message processing.
+ </dd>
+ <dt>FilterResult(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
+ <dd>
+ is used to filter results stored in the local block storage for local
+ queries. Locally stored blocks from previously observed
+ <tt>ResultMessages</tt> and <tt>PutMessages</tt> MAY use this
+ function instead of <tt>ValidateBlockReply</tt> in order to
+ avoid revalidation of the block and only perform filtering based on
+ request parameters.
+ </dd>
+ </dl>
+ </section>
+ <section anchor="block_types">
+ <name>Block Types</name>
+ <t>
+ Applications can and should define their own block types.
+ The block type determines the format and handling of the block
+ payload by nodes in PUT and RESULT messages.
+ Block types MUST be registered with GANA <xref target="gana"/>.
+ </t>
+ <t>
+ For bootstrapping and node discovery, the DHT implementation uses
+ its own block type called "HELLO". A block with this block type
+ contains the NodeID of the node initiating the GET request.
+ </t>
+ <section anchor="hello_block">
+ <name>HELLO</name>
<t>
- For bootstrapping and node discovery, the DHT implementation uses
- its own block type called "HELLO". A block with this block type
- contains the NodeID of the node initiating the GET request.
+ The HELLO block type wire format is illustrated in
+ <xref target="figure_hello"/>. A query for block of type HELLO MUST
+ NOT include extended query data (XQuery). Any implementation
+ encountering a HELLO block with XQuery data MUST consider the
+ block invalid and ignore it.
</t>
- <section anchor="hello_block">
- <name>HELLO</name>
- <t>
- The HELLO block type wire format is illustrated in
- <xref target="figure_hello"/>. A query for block of type HELLO MUST
- NOT include extended query data (XQuery). Any implementation
- encountering a HELLO block with XQuery data MUST consider the
- block invalid and ignore it.
- </t>
- <figure anchor="figure_hello">
- <artwork name="" type="" align="left" alt=""><![CDATA[
+ <figure anchor="figure_hello">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+---+-----+-----+-----+-----+-----+-----+-----+
| TYPE | SIZE | NODEID /
@@ -1170,198 +1170,198 @@ Connectivity | |Underlay| |Underlay|
| ADDRESSES /
/ (variable length) |
+---+-----+-----+-----+-----+-----+-----+-----+
-]]/artwork>
- </figure>
- <dl>
- <dt>TYPE</dt>
- <dd>
- is the type of HELLO. A 16-bit number in network byte order.
- This value determines the type of the NODEID field.
- </dd>
- <dt>SIZE</dt>
- <dd>
- is the SIZE of the following fields NODEID and ADDRESSES in bytes.
- In network byte order.
- </dd>
- <dt>NODEID</dt>
- <dd>
- is the Node ID of the node which has generated this HELLO.
- The length content of this field is determined by the TYPE.
- Usually, this is a cryptographic public key which allows the
- Underlay to uniquely identify and authenticate the node.
- </dd>
- <dt>ADDRESSES</dt>
- <dd>
- is a list of UTF-8 strings <xref target="RFC3629"/> which can be
- used as addresses to contact the node.
- The strings MUST be 0-terminated.
- FIXME: Examples? Format determined?
- </dd>
- </dl>
- <t>
- A HELLO reply block MAY be empty. Otherwise, it contains the
- HELLO of a node.
- </t>
- <t>
- For the string representation of the node public key,
- the base-32 encoding "StringEncode" is used.
- However, instead of following <xref target="RFC4648"/> the
- character map is based on the optical character recognition friendly
- proposal of Crockford <xref target="CrockfordB32"/>.
- The only difference to Crockford is that the letter
- "U" decodes to the same base-32 value as the letter "V" (27).
- </t>
- <t>
- The <tt>ADDRESSES</tt> part of the <tt>HELLO</tt> indicate endpoints
- which can be used by the Underlay in order to establish a connection
- with the node identified by <tt>NODEKEY</tt>.
- An example of an addressing scheme used throughout
- this document is "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 is a non-normative example of address strings:
- </t>
- <figure>
- <artwork name="" type="" align="left" alt=""><![CDATA[
-ipcp://1.2.3.4:6789 \
-gnet+tcp://12.3.4.5/ \
-i2udp://1.2.4.5:424/ \
-toonionv3://rasdflkjasdfliasduf.onion/
-]]/artwork>
- </figure>
- </section>
+ ]]></artwork>
+ </figure>
+ <dl>
+ <dt>TYPE</dt>
+ <dd>
+ is the type of HELLO. A 16-bit number in network byte order.
+ This value determines the type of the NODEID field.
+ </dd>
+ <dt>SIZE</dt>
+ <dd>
+ is the SIZE of the following fields NODEID and ADDRESSES in bytes.
+ In network byte order.
+ </dd>
+ <dt>NODEID</dt>
+ <dd>
+ is the Node ID of the node which has generated this HELLO.
+ The length content of this field is determined by the TYPE.
+ Usually, this is a cryptographic public key which allows the
+ Underlay to uniquely identify and authenticate the node.
+ </dd>
+ <dt>ADDRESSES</dt>
+ <dd>
+ is a list of UTF-8 strings <xref target="RFC3629"/> which can be
+ used as addresses to contact the node.
+ The strings MUST be 0-terminated.
+ FIXME: Examples? Format determined?
+ </dd>
+ </dl>
+ <t>
+ A HELLO reply block MAY be empty. Otherwise, it contains the
+ HELLO of a node.
+ </t>
+ <t>
+ For the string representation of the node public key,
+ the base-32 encoding "StringEncode" is used.
+ However, instead of following <xref target="RFC4648"/> the
+ character map is based on the optical character recognition friendly
+ proposal of Crockford <xref target="CrockfordB32"/>.
+ The only difference to Crockford is that the letter
+ "U" decodes to the same base-32 value as the letter "V" (27).
+ </t>
+ <t>
+ The <tt>ADDRESSES</tt> part of the <tt>HELLO</tt> indicate endpoints
+ which can be used by the Underlay in order to establish a connection
+ with the node identified by <tt>NODEKEY</tt>.
+ An example of an addressing scheme used throughout
+ this document is "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 is a non-normative example of address strings:
+ </t>
+ <figure>
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ip+tcp://1.2.3.4:6789 \
+gnunet+tcp://12.3.4.5/ \
+i2p+udp://1.2.4.5:424/ \
+tor+onionv3://rasdflkjasdfliasduf.onion/
+ ]]></artwork>
+ </figure>
</section>
</section>
- <section anchor="security" numbered="true" toc="default">
- <name>Security Considerations</name>
- <!-- FIXME: Here we should (again) discuss how the system is open and
- does not have/require a trust anchor a priori. This is (again) in contrast
- to RELOAD -->
- </section>
- <section anchor="gana" numbered="true" toc="default">
- <name>GANA Considerations</name>
- <t>
- GANA <xref target="GANA"/>
- is requested to create a "DHT Block Types" registry.
- The registry shall record for each entry:
- </t>
- <ul>
- <li>Name: The name of the block type (case-insensitive ASCII
- string, restricted to alphanumeric characters</li>
- <li>Number: 32-bit</li>
- <li>Comment: Optionally, a brief English text describing the purpose of
- the block type (in UTF-8)</li>
- <li>Contact: Optionally, the contact information of a person to contact for
- further information</li>
- <li>References: Optionally, references describing the record type
- (such as an RFC)</li>
- </ul>
- <t>
- The registration policy for this sub-registry is "First Come First
- Served", as described in <xref target="RFC8126"/>.
- GANA is requested to populate this registry as follows:
- </t>
- <figure anchor="figure_btypenums">
- <artwork name="" type="" align="left" alt=""><![CDATA[
-Nuer | Name | Contact | References | Description
------+--------+---------+------------+-------------------------
-0 ANY N/A [This.I-D] Reserved
-7 HELLO N/A [This.I-D] Type of a block that contains
-a LLO for a node
-11 GNS N/A GNS Block for storing record data
-]]/artwork>
- </figure>
- <t>
- GANA is requested to amend the "GNUnet Signature Purpose" registry
- as follows:
- </t>
- <figure anchor="figure_purposenums">
- <artwork name="" type="" align="left" alt=""><![CDATA[
-Puose | Name | References | Description
-------+-----------------+------------+--------------------------
-]]/artwork>
- </figure>
- </section>
- <!-- gana -->
- <section>
- <name>Test Vectors</name>
- </section>
- </middle>
- <back>
- <references><name>Normative References</name>
+ </section>
+ <section anchor="security" numbered="true" toc="default">
+ <name>Security Considerations</name>
+ <!-- FIXME: Here we should (again) discuss how the system is open and
+ does not have/require a trust anchor a priori. This is (again) in contrast
+ to RELOAD -->
+ </section>
+ <section anchor="gana" numbered="true" toc="default">
+ <name>GANA Considerations</name>
+ <t>
+ GANA <xref target="GANA"/>
+ is requested to create a "DHT Block Types" registry.
+ The registry shall record for each entry:
+ </t>
+ <ul>
+ <li>Name: The name of the block type (case-insensitive ASCII
+ string, restricted to alphanumeric characters</li>
+ <li>Number: 32-bit</li>
+ <li>Comment: Optionally, a brief English text describing the purpose of
+ the block type (in UTF-8)</li>
+ <li>Contact: Optionally, the contact information of a person to contact for
+ further information</li>
+ <li>References: Optionally, references describing the record type
+ (such as an RFC)</li>
+ </ul>
+ <t>
+ The registration policy for this sub-registry is "First Come First
+ Served", as described in <xref target="RFC8126"/>.
+ GANA is requested to populate this registry as follows:
+ </t>
+ <figure anchor="figure_btypenums">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+Number | Name | Contact | References | Description
+-------+--------+---------+------------+-------------------------
+0 ANY N/A [This.I-D] Reserved
+7 HELLO N/A [This.I-D] Type of a block that contains a HELLO for a node
+11 GNS N/A GNS Block for storing record data
+]]></artwork>
+ </figure>
+ <t>
+ GANA is requested to amend the "GNUnet Signature Purpose" registry
+ as follows:
+ </t>
+ <figure anchor="figure_purposenums">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+Purpose | Name | References | Description
+--------+-----------------+------------+--------------------------
+]]></artwork>
+ </figure>
+ </section>
+ <!-- gana -->
+ <section>
+ <name>Test Vectors</name>
+ </section>
+ </middle>
+ <back>
+ <references>
+ <name>Normative References</name>
- &RFC2119;
- &RFC3629;
- &RFC4634;
- &RFC4648;
- &RFC6940;
- &RFC8126;
- &RFC8174;
+ &RFC2119;
+ &RFC3629;
+ &RFC4634;
+ &RFC4648;
+ &RFC6940;
+ &RFC8126;
+ &RFC8174;
- <reference anchor="ed25519" target="http://link.springer.com/chapter/10.1007/978-3-642-23951-9_9"><front><title>High-Speed High-Security Signatures</title><author initials="D." surname="Bernstein" fullname="Daniel Bernstein"><organization>University of Illinois at Chicago</organization></author><author initials="N." surname="Duif" fullname="Niels Duif"><organization>Technische Universiteit Eindhoven</organization></author><author initials="T." surname="Lange" fullname="Tanja Lange"><organization>Technische Universiteit Eindhoven</organization></author><author initials="P." surname="Schwabe" fullname="Peter Schwabe"><organization>National Taiwan University</organization></author><author initials="B." surname="Yang" fullname="Bo-Yin Yang"><organization>Academia Sinica</organization></author><date year="2011"/></front></reference>
+ <reference anchor="ed25519" target="http://link.springer.com/chapter/10.1007/978-3-642-23951-9_9"><front><title>High-Speed High-Security Signatures</title><author initials="D." surname="Bernstein" fullname="Daniel Bernstein"><organization>University of Illinois at Chicago</organization></author><author initials="N." surname="Duif" fullname="Niels Duif"><organization>Technische Universiteit Eindhoven</organization></author><author initials="T." surname="Lange" fullname="Tanja Lange"><organization>Technische Universiteit Eindhoven</organization></author><author initials="P." surname="Schwabe" fullname="Peter Schwabe"><organization>National Taiwan University</organization></author><author initials="B." surname="Yang" fullname="Bo-Yin Yang"><organization>Academia Sinica</organization></author><date year="2011"/></front></reference>
- <reference anchor="CrockfordB32" target="https://www.crockford.com/base32.html"><front><title>Base32</title><author initials="D." surname="Douglas" fullname="Crockford">
- </author><date year="2019" month="March"/></front></reference>
+ <reference anchor="CrockfordB32" target="https://www.crockford.com/base32.html"><front><title>Base32</title><author initials="D." surname="Douglas" fullname="Crockford">
+ </author><date year="2019" month="March"/></front></reference>
- <reference anchor="GANA" target="https://gana.gnunet.org/"><front><title>GNUnet Assigned Numbers Authority (GANA)</title><author><organization>GNUnet e.V.</organization></author><date month="April" year="2020"/></front></reference>
+ <reference anchor="GANA" target="https://gana.gnunet.org/"><front><title>GNUnet Assigned Numbers Authority (GANA)</title><author><organization>GNUnet e.V.</organization></author><date month="April" year="2020"/></front></reference>
- </references>
- <references>
- <name>Informative References</name>
- <reference anchor="R5N" target="https://doi.org/10.1109/ICNSS.2011.6060022">
- <front>
- <title>R5N: Randomized recursive routing for restricted-route networks</title>
- <author initials="N. S." surname="Evans" fullname="Nathan S. Evans">
- <organization>Technische Universität München</organization>
- </author>
- <author initials="C." surname="Grothoff" fullname="Christian Grothoff">
- <organization>Technische Universität München</organization>
- </author>
- <date year="2011"/>
- </front>
- </reference>
- <reference anchor="Kademlia" target="http://css.csail.mit.edu/6.824/2014/papers/kademlia.pdf">
- <front>
- <title>Kademlia: A peer-to-peer information system based on the xor metric.</title>
- <author initials="P." surname="Maymounkov" fullname="Petar Maymounkov">
- </author>
- <author initials="D." surname="Mazieres" fullname="David Mazieres">
- </author>
- <date year="2002"/>
- </front>
- </reference>
- <reference anchor="cadet" target="https://doi.org/10.1109/MedHocNet.2014.6849107">
- <front>
- <title>CADET: Confidential ad-hoc decentralized end-to-end transport</title>
- <author initials="B." surname="Polot" fullname="Bartlomiej Polot">
- <organization>Technische Universität München</organization>
- </author>
- <author initials="C." surname="Grothoff" fullname="Christian Grothoff">
- <organization>Technische Universität München</organization>
- </author>
- <date year="2014"/>
- </front>
- </reference>
- <reference anchor="I-D.draft-schanzen-gns" target="https://datatracker.ietf.org/doc/draft-schanzen-gns/">
- <front>
- <title>The GNU Name System</title>
- <author initials="M." surname="Schanzenbach" fullname="Martin Schanzenbach">
- <organization>GNUnet e.V.</organization>
- </author>
- <author initials="C." surname="Grothoff" fullname="Christian Grothoff">
- <organization>GNUnet e.V.</organization>
- </author>
- <author initials="B." surname="Fix" fullname="Bernd Fix">
- <organization>GNUnet e.V.</organization>
- </author>
- <date year="2021"/>
- </front>
- </reference>
- </references>
- <!-- Change Log
- v00 2017-07-23 MS Initial version
- -->
- </back>
- </rfc>
+ </references>
+ <references>
+ <name>Informative References</name>
+ <reference anchor="R5N" target="https://doi.org/10.1109/ICNSS.2011.6060022">
+ <front>
+ <title>R5N: Randomized recursive routing for restricted-route networks</title>
+ <author initials="N. S." surname="Evans" fullname="Nathan S. Evans">
+ <organization>Technische Universität München</organization>
+ </author>
+ <author initials="C." surname="Grothoff" fullname="Christian Grothoff">
+ <organization>Technische Universität München</organization>
+ </author>
+ <date year="2011"/>
+ </front>
+ </reference>
+ <reference anchor="Kademlia" target="http://css.csail.mit.edu/6.824/2014/papers/kademlia.pdf">
+ <front>
+ <title>Kademlia: A peer-to-peer information system based on the xor metric.</title>
+ <author initials="P." surname="Maymounkov" fullname="Petar Maymounkov">
+ </author>
+ <author initials="D." surname="Mazieres" fullname="David Mazieres">
+ </author>
+ <date year="2002"/>
+ </front>
+ </reference>
+ <reference anchor="cadet" target="https://doi.org/10.1109/MedHocNet.2014.6849107">
+ <front>
+ <title>CADET: Confidential ad-hoc decentralized end-to-end transport</title>
+ <author initials="B." surname="Polot" fullname="Bartlomiej Polot">
+ <organization>Technische Universität München</organization>
+ </author>
+ <author initials="C." surname="Grothoff" fullname="Christian Grothoff">
+ <organization>Technische Universität München</organization>
+ </author>
+ <date year="2014"/>
+ </front>
+ </reference>
+ <reference anchor="I-D.draft-schanzen-gns" target="https://datatracker.ietf.org/doc/draft-schanzen-gns/">
+ <front>
+ <title>The GNU Name System</title>
+ <author initials="M." surname="Schanzenbach" fullname="Martin Schanzenbach">
+ <organization>GNUnet e.V.</organization>
+ </author>
+ <author initials="C." surname="Grothoff" fullname="Christian Grothoff">
+ <organization>GNUnet e.V.</organization>
+ </author>
+ <author initials="B." surname="Fix" fullname="Bernd Fix">
+ <organization>GNUnet e.V.</organization>
+ </author>
+ <date year="2021"/>
+ </front>
+ </reference>
+ </references>
+ <!-- Change Log
+ v00 2017-07-23 MS Initial version
+ -->
+ </back>
+</rfc>
