commit d35439a900f8e3b66a4ee7b1a37b8519561673e5
parent 91218e0c5a3b3e5a7e60a4f74a40b8ac840306c1
Author: Christian Grothoff <christian@grothoff.org>
Date: Sun, 16 Jan 2022 20:46:24 +0100
describe HELLO message and findApproximate handling
Diffstat:
1 file changed, 146 insertions(+), 19 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -560,10 +560,20 @@ Connectivity | |Underlay| |Underlay|
<section>
<name>Bootstrapping</name>
<t>
- Initially, the implementation depends upon the Underlay to provide at
+ Initially, the implementation depends upon either the Underlay to provide at
least one initial connection to a peer signalled through
- <tt>PEER_CONNECTED</tt>.
- The initial set of peers is stored in the routing table component
+ <tt>PEER_CONNECTED</tt>, or the application/end-user providing at
+ least one working HELLO to the DHT or the Underlay for bootstrapping.
+ While details on how the first connection is established MAY
+ depend on the specific implementation, this SHOULD usually be done
+ by an out-of-band exchange of the information from a HELLO block.
+ For this, section TBD specifies a URL format for encoding HELLO
+ blocks as text strings which SHOULD be supported by implementations.
+ </t>
+ <t>
+ Regardless of how the initial connections are established, the
+ peers resulting from these initial connections
+ are subsequently stored in the routing table component
<xref target="routing_table"/>.
</t>
<t>
@@ -615,9 +625,26 @@ Connectivity | |Underlay| |Underlay|
<section anchor="find_peer">
<name>Peer Discovery</name>
<t>
- FIXME: Elaborate on FindPeer here. Why is this a route option?
- In the code we only answer with HELLO anyway and ignore the type
- of block requested.
+ To build its routing table, a peer will send out requests
+ asking for blocks of type HELLO using its own location as the key,
+ but filtering its own HELLO via the Bloom filter.
+ <!-- FIXME: CG: I think this last one is not implemented! -->
+ <!-- FIXME: CG: I also suspect we need to review how the block API filters HELLOs, to NOT use the full body / expiration time in the hash -->
+ These requests MUST use the FindApproximate and DemultiplexEverywhere
+ options. FindApproximate will ensure that other nodes will reply
+ with keys they merely consider close-enough, while DemultiplexEverywhere
+ will cause each peer on the path to respond, which is likely to yield
+ HELLOs of peers that are useful somewhere in the routing table.
+ </t>
+ <t>
+ To facilitate peer discovery, each peer MUST broadcast its own
+ HELLO data to all nodes in the routing table periodically.
+ <!-- FIXME: CG: specify frequency? -->
+ Whenever a peer receives such a HELLO message from another node,
+ it must cache it as long as that node is in its routing table
+ (or until the HELLO expires) and serve it in response to
+ Peer Discovery requests. Details about the format of the
+ HELLO message are given in section p2p_hello_wire.
</t>
</section>
<section anchor="routing_table">
@@ -724,7 +751,7 @@ Connectivity | |Underlay| |Underlay|
indicates to keep track of the route that the message takes
in the P2P network.
</dd>
- <dt>2: Allow-Approximate</dt>
+ <dt>2: Find-Approximate</dt>
<dd>
This is a special flag which modifies the message processing to
allow approximate results.
@@ -754,6 +781,93 @@ Connectivity | |Underlay| |Underlay|
<name>Extended query</name>
<t>TODO: Talk about XQuery in the context of messages.</t>
</section>
+ <section anchor="p2p_hello" numbered="true" toc="default">
+ <name>HelloMessage</name>
+ <section anchor="p2p_hello_wire">
+ <name>Wire Format</name>
+ <figure anchor="figure_hellomsg">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+0 8 16 24 32 40 48 56
++-----+-----+-----+-----+-----+-----+-----+-----+
+| MSIZE | MTYPE | RESERVED | URL_CTR |
++-----+-----+-----+-----+-----+-----+-----+-----+
++-----+-----+-----+-----+-----+-----+-----+-----+
+| SIGNATURE /
+/ (64 byte) |
++-----+-----+-----+-----+-----+-----+-----+-----+
+| EXPIRATION |
++-----+-----+-----+-----+-----+-----+-----+-----+
+/ ADDRESSES (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 HELLO messages it must be set to
+ the value 157 in network byte order.
+ </dd>
+ <dt>RESERVED</dt>
+ <dd>
+ is a 16-bit field that must be zero.
+ </dd>
+ <dt>URL_CTR</dt>
+ <dd>
+ is a 16-bit number that gives the total number of
+ addresses encoded in the ADDRESSES field.
+ In network byte order.
+ </dd>
+ <dt>SIGNATURE</dt>
+ <dd>
+ is a 64 byte EdDSA signature using the sender's private
+ key affirming the information contained in the message.
+ The signature is signing exactly the same data that is being
+ signed in a HELLO block as described in section XXX.
+ </dd>
+ <dt>EXPIRATION</dt>
+ <dd>
+ denotes the absolute 64-bit expiration date of the content.
+ The value specified is microseconds since midnight (0 hour),
+ January 1, 1970, but must be a multiple of one million
+ (so that it can be represented in seconds in a HELLO URL).
+ Stored in network byte order.
+ </dd>
+ <dt>ADDRESSES</dt>
+ <dd>
+ A sequence of exactly URL_CTR
+ 0-terminated URIs in UTF-8 encoding representing addresses
+ of this peer. Each URI must begin with a non-empty
+ URI schema terminated by "://" and followed by some
+ non-empty Underlay-specific address encoding.
+ </dd>
+ </dl>
+ </section>
+ <section anchor="p2p_hello_processing">
+ <name>Processing</name>
+ <t>
+ Upon receiving a <tt>HelloMessage</tt> from a peer <tt>P</tt>.
+ An implementation MUST process it step by step as follows:
+ </t>
+ <ol>
+ <li>
+ If <tt>P</tt> is not in its routing table, the message
+ is discarded.
+ </li>
+ <li>
+ The signature is verified, including a check that the expiration time is in the future. If the signature is invalid, the message is discarded.
+ </li>
+ <li>
+ The HELLO information is cached in the routing table until it expires, the peer is removed from the routing table, or the information is replaced by another message from the peer.
+ </li>
+ </ol>
+ </section>
+ </section>
<section anchor="p2p_put" numbered="true" toc="default">
<!-- FIXME: Blocks have KEYs. GETs only have
QueryHashes the reply refers to the QueryHash, but
@@ -989,7 +1103,7 @@ Connectivity | |Underlay| |Underlay|
<section anchor="p2p_get_processing">
<name>Processing</name>
<t>
- Upon receiving a <tt>GetMmessage</tt> from a peer an
+ Upon receiving a <tt>GetMessage</tt> from a peer an
implementation MUST process it step by step as follows:
</t>
<ol>
@@ -1011,20 +1125,33 @@ Connectivity | |Underlay| |Underlay|
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:
+ MUST be produced (if one is available) using the following
+ steps:
</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>
+ If <tt>TYPE</tt> indicates a request for a HELLO block,
+ the peer MUST consult the HELLOs it has cached for the
+ peers in its routing table instead of the local block
+ storage (while continuing to respect options like
+ <tt>DemultiplexEverywhere</tt>
+ and <tt>FindApproximate</tt>).
+ </li>
+ <li>
+ If <tt>OPTIONS</tt> indicate a <tt>FindApproximate</tt> request,
+ the peer should respond with the closest block it
+ has that is not filtered by the
+ <tt>RESULT_BF</tt>.
+ </li>
+ <li>
+ Else, the peer should only respond if it has a block
+ that matches the key exactly and that is
+ not filtered by the <tt>RESULT_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?
+ Any resulting block must be encapsulated in a
+ <tt>ResultMessage</tt> and transmitted to the
+ neighbor from which the request was received.
</li>
</ol>
</li>
@@ -1041,7 +1168,7 @@ Connectivity | |Underlay| |Underlay|
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
+ 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.
@@ -1181,7 +1308,7 @@ Connectivity | |Underlay| |Underlay|
the respective <tt>ValidateBlockReply</tt> function.
</t>
<t>
- If the request options include <tt>FindNode</tt> and the result
+ If the request options include <tt>FindApproximate</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
