commit b31cbebc4e61ffc3691b94975c8020beae5087dc
parent 46c4ebbc21be1952bb23ee3a9203d8eaa228f80a
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Mon, 21 Feb 2022 19:42:08 +0100
bcp14
Diffstat:
1 file changed, 75 insertions(+), 79 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -90,7 +90,6 @@
<middle>
<section anchor="introduction" numbered="true" toc="default">
<name>Introduction</name>
- <t>
<!--
- Lean. Can be implemented. Not overengineered.
- Path tracking (more difficult) -> Not built in
@@ -104,13 +103,12 @@
- For a PUT, reload requires that
"Each element is signed by a credential which is authorized to
write this Kind at this Resource-ID. If this check fails, the
- request MUST be rejected with an Error_Forbidden error."
+ request <bcp14>MUST</bcp14> be rejected with an Error_Forbidden error."
-->
- <!--FIXME: Here we should also cite and discuss RELOAD (https://datatracker.ietf.org/doc/html/rfc6940)-->
+ <!--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>
+ security aspects (path signatures).-->
<t>
Distributed Hash Tables (DHTs) are a key data structure for the
construction of completely decentralized applications.
@@ -244,7 +242,7 @@
R5N is an overlay network with a pluggable transport layer.
The following figure shows the R5N architecture.
</t>
- <figure>
+ <figure title="The R5N Architecture.">
<artwork><![CDATA[
| +-----------------+ +-------+
Applications | | GNU Name System | | CADET | ...
@@ -563,11 +561,11 @@ Connectivity | |Underlay| |Underlay|
least one initial connection to a peer signalled through
<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
+ While details on how the first connection is established <bcp14>MAY</bcp14>
+ depend on the specific implementation, this <bcp14>SHOULD</bcp14> 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.
+ blocks as text strings which <bcp14>SHOULD</bcp14> be supported by implementations.
</t>
<t>
Regardless of how the initial connections are established, the
@@ -583,12 +581,12 @@ Connectivity | |Underlay| |Underlay|
</t>
<t>
In order to find more close peers in the network, an
- implementation MUST now periodically send find peer messages
+ implementation <bcp14>MUST</bcp14> now periodically send find peer messages
<xref target="find_peer"/>.
</t>
<t>
In both cases the frequency of advertisements and peer discovery
- MAY be adapted according to network conditions, connected peers,
+ <bcp14>MAY</bcp14> be adapted according to network conditions, connected peers,
workload of the system and other factors which are at the discretion of
the developer.
</t>
@@ -609,11 +607,11 @@ Connectivity | |Underlay| |Underlay|
<tt>PEER_CONNECTED</tt>, information on the new peer is added to the
local peer storage.
When disconnect is indicated by the Underlay through
- <tt>PEER_DISCONNECTED</tt> the peer MUST be removed from the local
+ <tt>PEER_DISCONNECTED</tt> the peer <bcp14>MUST</bcp14> be removed from the local
peer storage.
In order to achieve O(log n) routing performance,
the data structure for managing connected peers and their
- metadata MUST be implemented using the k-buckets concept of
+ metadata <bcp14>MUST</bcp14> be implemented using the k-buckets concept of
<xref target="Kademlia"/> as defined in <xref target="routing_table"/>.
</t>
</section>
@@ -645,14 +643,14 @@ Connectivity | |Underlay| |Underlay|
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
+ These requests <bcp14>MUST</bcp14> use the FindApproximate and DemultiplexEverywhere
options. FindApproximate will ensure that other peers 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
+ To facilitate peer discovery, each peer <bcp14>MUST</bcp14> broadcast its own
HELLO data to all peers in the routing table periodically.
<!-- FIXME: CG: specify frequency? -->
Whenever a peer receives such a HELLO message from another peer,
@@ -675,10 +673,10 @@ Connectivity | |Underlay| |Underlay|
The routing table consists of an array of lists of connected peers.
The i-th list stores neighbours whose identifiers are between
distance 2^i 2^(i+1) from the local peer.
- An implementation MAY choose an upper limit on the length of the
- lists, but SHOULD try to keep at least 5 entries per bucket.
+ An implementation <bcp14>MAY</bcp14> choose an upper limit on the length of the
+ lists, but <bcp14>SHOULD</bcp14> try to keep at least 5 entries per bucket.
For example, in case of system constraints with respect to active
- connections, an implementation SHOULD evict peers in large buckets
+ connections, an implementation <bcp14>SHOULD</bcp14> evict peers in large buckets
rather than peers from shallow ones.
</t>
<t>
@@ -692,7 +690,7 @@ Connectivity | |Underlay| |Underlay|
is not included in the peer selection process.
</t>
<t>
- The R5N routing component MUST implement the following functions:
+ The R5N routing component <bcp14>MUST</bcp14> implement the following functions:
</t>
<dl>
<dt>
@@ -728,7 +726,7 @@ Connectivity | |Underlay| |Underlay|
This function selects a peer <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>SelectRandompeer()</tt> and
+ this function <bcp14>MUST</bcp14> return <tt>SelectRandompeer()</tt> and
<tt>SelectClosestpeer(K)</tt> otherwise.
peers in the bloomfilter <tt>B</tt> are not considered.
</dd>
@@ -746,7 +744,7 @@ Connectivity | |Underlay| |Underlay|
<section anchor="p2p_messages" numbered="true" toc="default">
<name>Message Processing</name>
<t>
- The implementation MUST listen for <tt>RECEIVE(P, M)</tt> signals
+ The implementation <bcp14>MUST</bcp14> 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
@@ -791,7 +789,7 @@ Connectivity | |Underlay| |Underlay|
are not of interest when processing a GET message
(<xref target="p2p_get"/>).
Any peer which is processing GET messages and has a result
- which matches the query key MUST check the result bloom filter
+ which matches the query key <bcp14>MUST</bcp14> check the result bloom filter
and only send a reply message if the block key is not in the
bloom filter set.
</t>
@@ -813,13 +811,12 @@ Connectivity | |Underlay| |Underlay|
<name>HelloMessage</name>
<section anchor="p2p_hello_wire">
<name>Wire Format</name>
- <figure anchor="figure_hellomsg">
+ <figure anchor="figure_hellomsg" title="The HelloMessage Wire Format.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSIZE | MTYPE | RESERVED | URL_CTR |
+-----+-----+-----+-----+-----+-----+-----+-----+
-+-----+-----+-----+-----+-----+-----+-----+-----+
| SIGNATURE /
/ (64 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -880,7 +877,7 @@ Connectivity | |Underlay| |Underlay|
<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:
+ An implementation <bcp14>MUST</bcp14> process it step by step as follows:
</t>
<ol>
<li>
@@ -900,7 +897,7 @@ Connectivity | |Underlay| |Underlay|
<name>PutMessage</name>
<section anchor="p2p_put_wire">
<name>Wire Format</name>
- <figure anchor="figure_putmsg">
+ <figure anchor="figure_putmsg" title="The PutMessage Wire Format.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -991,49 +988,49 @@ Connectivity | |Underlay| |Underlay|
<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:
+ An implementation <bcp14>MUST</bcp14> 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.
+ If the message is expired, it <bcp14>MUST</bcp14> 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).
+ Else, the block <bcp14>MUST</bcp14> 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.
+ it <bcp14>MUST</bcp14> be discarded.
</li>
<li>
- The peer address of the sender peer <tt>P</tt> SHOULD be in <tt>PEER_BF</tt>.
- If not, the implementation MAY log an error, but MUST continue.
+ The peer address of the sender peer <tt>P</tt> <bcp14>SHOULD</bcp14> be in <tt>PEER_BF</tt>.
+ If not, the implementation <bcp14>MAY</bcp14> log an error, but <bcp14>MUST</bcp14> continue.
</li>
<li>
If the <tt>RecordRoute</tt> flag is set in OPTIONS,
- the local peer address MUST be appended to the <tt>PUTPATH</tt>
+ the local peer address <bcp14>MUST</bcp14> be appended to the <tt>PUTPATH</tt>
of the message.
</li>
<li>
If the local peer is the closest peer
(cf. <tt>IsClosestpeer(N, BLOCK_KEY)</tt>) or the <tt>DemultiplexEverywhere</tt>
- options flag ist set, the message MUST
+ options flag ist set, the message <bcp14>MUST</bcp14>
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 <bcp14>MUST</bcp14> be calculated. If there is at least one
+ peers to forward to, the implementation <bcp14>SHOULD</bcp14> select up to this
+ number of peers to forward the message to. The implementation <bcp14>MAY</bcp14>
forward to fewer or no peers in order to handle resource constraints
such as bandwidth.
- Finally, the local peer address MUST be added to the
+ Finally, the local peer address <bcp14>MUST</bcp14> be added to the
<tt>PEER_BF</tt> of the forwarded message.
For all peers with peer address <tt>P</tt> chosen to forward the message
to, <tt>SEND(P, PutMessage)</tt> is called.
@@ -1045,7 +1042,7 @@ Connectivity | |Underlay| |Underlay|
<name>GetMessage</name>
<section anchor="p2p_get_wire">
<name>Wire Format</name>
- <figure anchor="figure_getmsg">
+ <figure anchor="figure_getmsg" title="The GetMessage Wire Format.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -1134,7 +1131,7 @@ Connectivity | |Underlay| |Underlay|
<name>Processing</name>
<t>
Upon receiving a <tt>GetMessage</tt> from a peer an
- implementation MUST process it step by step as follows:
+ implementation <bcp14>MUST</bcp14> process it step by step as follows:
</t>
<ol>
<li>
@@ -1144,25 +1141,25 @@ Connectivity | |Underlay| |Underlay|
<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.
+ the message <bcp14>MUST</bcp14> be discarded.
</li>
<li>
- The peer address of the sender peer <tt>P</tt> SHOULD be in the
+ The peer address of the sender peer <tt>P</tt> <bcp14>SHOULD</bcp14> be in the
PEER_BF bloom filter. If not, the
- implementation MAY log an error, but MUST continue.
+ implementation <bcp14>MAY</bcp14> log an error, but <bcp14>MUST</bcp14> continue.
</li>
<li>
<t>
If the local peer is the closest peer
(cf. <tt>IsClosestpeer (N, QueryHash)</tt>) or the
<tt>DemultiplexEverywhere</tt> options flag is set, a reply
- MUST be produced (if one is available) using the following
+ <bcp14>MUST</bcp14> be produced (if one is available) using the following
steps:
</t>
<ol>
<li>
If <tt>TYPE</tt> indicates a request for a HELLO block,
- the peer MUST consult the HELLOs it has cached for the
+ the peer <bcp14>MUST</bcp14> 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>
@@ -1194,12 +1191,12 @@ Connectivity | |Underlay| |Underlay|
</li>
<li>
Given the value in REPL_LVL, the number of peers to forward to
- MUST be calculated (NUM-FORWARD-peerS). If there is at least one
- peer to forward to, the implementation SHOULD select up to this
- number of peers to forward the message to. The implementation MAY
+ <bcp14>MUST</bcp14> be calculated (NUM-FORWARD-peerS). If there is at least one
+ peer to forward to, the implementation <bcp14>SHOULD</bcp14> select up to this
+ number of peers to forward the message to. The implementation <bcp14>MAY</bcp14>
forward to fewer or no peers in order to handle resource constraints
such as bandwidth.
- The message bloom filter PEER_BF MUST be updated with the local
+ The message bloom filter PEER_BF <bcp14>MUST</bcp14> be updated with the local
peer address <tt>N</tt>.
For all peers with peer address <tt>P'</tt> chosen to forward the message
to, <tt>SEND(P', PutMessage)</tt> is called.
@@ -1211,7 +1208,7 @@ Connectivity | |Underlay| |Underlay|
<name>ResultMessage</name>
<section anchor="p2p_result_wire">
<name>Wire Format</name>
- <figure anchor="figure_resmsg">
+ <figure anchor="figure_resmsg" title="The ResultMessage Wire Format">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -1300,25 +1297,25 @@ Connectivity | |Underlay| |Underlay|
<name>Processing</name>
<t>
Upon receiving a <tt>ResultMessage</tt> from a connected peer.
- An implementation MUST process it step by step as follows:
+ An implementation <bcp14>MUST</bcp14> 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.
+ If the message is expired, it <bcp14>MUST</bcp14> 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
+ The payload <bcp14>MUST</bcp14> be considered for the local routing table by
trying to establish a connection to the peer using the information
from the HELLO block. If a connection can be established,
the peer is added to the <tt>KBuckets</tt> routing table.
</li>
<li>
If the sender peer 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.
+ GETPATH, the path <bcp14>MUST</bcp14> be truncated at this position.
+ The implementation <bcp14>MAY</bcp14> log a warning in such a case.
</li>
<li>
If the <tt>QUERY_HASH</tt> of this <tt>ResultMessage</tt> is found in the
@@ -1327,12 +1324,12 @@ Connectivity | |Underlay| |Underlay|
block type implementation of <tt>ValidateBlockReply</tt>.
If the approximate flag is set and the BTYPE allows the
implementation to compute the key from the block it must match
- the QUERY_HASH. If the XQUERY is malformed, the message MUST be discarded.
+ the QUERY_HASH. If the XQUERY is malformed, the message <bcp14>MUST</bcp14> be discarded.
<!-- FIXME: This should be reviewed.
<= approximate flag -->
</li>
<li>
- The implementation MAY cache RESULT messages.
+ The implementation <bcp14>MAY</bcp14> cache RESULT messages.
</li>
<li>
<t>
@@ -1350,7 +1347,7 @@ Connectivity | |Underlay| |Underlay|
<t>
If the result message block cannot be verified against the
<tt>QUERY_HASH</tt> of the result message or if <tt>BLOCK</tt> is
- malformed, the message MUST be discarded.
+ malformed, the message <bcp14>MUST</bcp14> be discarded.
</t>
<t>
For each pending request the reply is routed to the requesting
@@ -1392,7 +1389,7 @@ Connectivity | |Underlay| |Underlay|
<section anchor="block_functions">
<name>Block Functions</name>
<t>
- Any block type implementation MUST implement the following functions.
+ Any block type implementation <bcp14>MUST</bcp14> implement the following functions.
</t>
<dl>
<dt>ValidateBlockQuery(Key, XQuery) -> RequestEvaluationResult</dt>
@@ -1401,13 +1398,13 @@ Connectivity | |Underlay| |Underlay|
<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.
+ <bcp14>MUST</bcp14> 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
+ The validation <bcp14>MUST</bcp14> 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>
@@ -1417,7 +1414,7 @@ Connectivity | |Underlay| |Underlay|
The validation of the respective <tt>Block</tt> requires a pending local query
or a previously routed request of another peer and its associated
XQuery data and Key.
- The validation MUST include a check of the block payload against the
+ The validation <bcp14>MUST</bcp14> include a check of the block payload against the
key under which it is requested to be stored.
</dd>
<dt>DeriveBlockKey(Block) -> Key</dt>
@@ -1429,7 +1426,7 @@ Connectivity | |Underlay| |Underlay|
<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
+ <tt>ResultMessages</tt> and <tt>PutMessages</tt> <bcp14>MAY</bcp14> use this
function instead of <tt>ValidateBlockReply</tt> in order to
avoid revalidation of the block and only perform filtering based on
request parameters.
@@ -1442,7 +1439,7 @@ Connectivity | |Underlay| |Underlay|
Applications can and should define their own block types.
The block type determines the format and handling of the block
payload by peers in PUT and RESULT messages.
- Block types MUST be registered with GANA <xref target="gana"/>.
+ Block types <bcp14>MUST</bcp14> be registered with GANA <xref target="gana"/>.
</t>
<t>
For bootstrapping and peer discovery, the DHT implementation uses
@@ -1453,12 +1450,12 @@ Connectivity | |Underlay| |Underlay|
<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
+ <xref target="figure_hello"/>. A query for block of type HELLO <bcp14>MUST NOT</bcp14>
+ include extended query data (XQuery). Any implementation
+ encountering a HELLO block with XQuery data <bcp14>MUST</bcp14> consider the
block invalid and ignore it.
</t>
- <figure anchor="figure_hello">
+ <figure anchor="figure_hello" title="The HELLO Block Format.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -1503,7 +1500,7 @@ Connectivity | |Underlay| |Underlay|
is a list of UTF-8 <xref target="RFC3629"/> URIs
<xref target="RFC3986"/> which can be
used as addresses to contact the peer.
- The strings MUST be 0-terminated.
+ The strings <bcp14>MUST</bcp14> be 0-terminated.
</dd>
</dl>
<t>
@@ -1513,7 +1510,7 @@ Connectivity | |Underlay| |Underlay|
The wire format is illustrated
in <xref target="figure_hellowithpseudo"/>.
</t>
- <figure anchor="figure_hellowithpseudo">
+ <figure anchor="figure_hellowithpseudo" title="The Wire Format of the HELLO for Signing.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -1532,17 +1529,16 @@ Connectivity | |Underlay| |Underlay|
+-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
</figure>
- <t>The Wire Format of the HELLO for Signing.</t>
<dl>
<dt>SIZE</dt>
<dd>
A 32-bit value containing the length of the signed data in bytes
in network byte order.
- The length of the signed data MUST be 80 bytes.
+ The length of the signed data <bcp14>MUST</bcp14> be 80 bytes.
</dd>
<dt>PURPOSE</dt>
<dd>
- A 32-bit signature purpose flag. This field MUST be 40 (in network
+ A 32-bit signature purpose flag. This field <bcp14>MUST</bcp14> be 40 (in network
byte order).
</dd>
<dt>EXPIRATION</dt>
@@ -1561,7 +1557,7 @@ Connectivity | |Underlay| |Underlay|
as provided in the HELLO block using SHA-512 <xref target="RFC4634"/>.
</t>
<t>
- A HELLO reply block MAY be empty. Otherwise, it contains the
+ A HELLO reply block <bcp14>MAY</bcp14> be empty. Otherwise, it contains the
HELLO of a peer.
</t>
<t>
@@ -1574,7 +1570,7 @@ Connectivity | |Underlay| |Underlay|
address for the given addressing scheme.
The following is a non-normative example of address strings:
</t>
- <figure>
+ <figure title="Example Address URIs.">
<artwork name="" type="" align="left" alt=""><