commit c7b29b045da9568cc13c3740c512d31d6ff70fde
parent 5a91d9457f0a1d465185ba381e6a26936b4c69ff
Author: Christian Grothoff <christian@grothoff.org>
Date: Sat, 13 Jul 2024 13:19:21 +0200
more editing on PutMessages
Diffstat:
1 file changed, 385 insertions(+), 262 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -1211,7 +1211,7 @@ BEGIN
<dt>4-7: Reserved</dt>
<dd>
The remaining bits are reserved for future use and
- <bcp14>MUST</bcp14> be set to 0 when initiating an operation.
+ <bcp14>MUST</bcp14> be set to zero when initiating an operation.
If non-zero bits are received, implementations <bcp14>MUST</bcp14>
preserve these bits when forwarding messages.
</dd>
@@ -1674,7 +1674,7 @@ BEGIN
<dd>
is a 16-bit number in network byte order indicating how
many hops this message has traversed to far. Set by the
- initiator to 0. <bcp14>MUST</bcp14> be incremented by 1
+ initiator to zero. <bcp14>MUST</bcp14> be incremented by one
by each peer before forwarding the request.
</dd>
<dt>REPL_LVL</dt>
@@ -1688,7 +1688,7 @@ BEGIN
is a 16-bit number in network byte order indicating the
number of path elements recorded in <tt>PUTPATH</tt>. As <tt>PUTPATH</tt>
is optional, this value may be zero. If the <tt>PUTPATH</tt> is
- enabled, set initially to 0 by the initiator. Updated
+ enabled, set initially to zero by the initiator. Updated
by processing peers to match the path length in the
message.
</dd>
@@ -1730,7 +1730,7 @@ BEGIN
<dd>
the variable-length <tt>PUT</tt> path.
The path consists of a list of <tt>PATH_LEN</tt> path elements.
- Set by the initiator to 0.
+ Set by the initiator to zero.
Incremented by processing peers.
</dd>
<dt>LAST HOP SIGNATURE</dt>
@@ -1740,7 +1740,7 @@ BEGIN
an EdDSA signature <xref target="ed25519"/> by the sender of this message
(using the same format as the signatures in PUTPATH)
affirming that the sender forwarded the message from
- the predecessor (all zeros if <tt>PATH_LEN</tt> is 0,
+ the predecessor (all zeros if <tt>PATH_LEN</tt> is zero,
otherwise the last peer in <tt>PUTPATH</tt>) to
the target peer.
Modified by processing peers (if flag is set).
@@ -1866,12 +1866,12 @@ BEGIN
<em>all</em> selected peer identities and the local peer
identity <bcp14>MUST</bcp14> be added to the
<tt>PEER_BF</tt> and the <tt>HOPCOUNT</tt>
- <bcp14>MUST</bcp14> be incremented by 1. If the
+ <bcp14>MUST</bcp14> be incremented by one. If the
<tt>RecordRoute</tt> flag is set, a new path element is
created using the predecessor peer public key and the
signature of the current peer. The path element is
added to the <tt>PUTPATH</tt> fields and the
- <tt>PATH_LEN</tt> field is incremented by 1. When
+ <tt>PATH_LEN</tt> field is incremented by one. When
creating the path element signature, the successor must
be set to the recipient peer <tt>P</tt> of the
<tt>PutMessage_P</tt>. The successor in the new path
@@ -1887,11 +1887,27 @@ BEGIN
<section anchor="p2p_get" numbered="true" toc="default">
<name>GetMessage</name>
<t>
- <tt>GetMessages</tt> are used to request information from other peers in the DHT.
- Any overlay API which allows applications to initiate <tt>GetMessages</tt> needs to provide
- sufficient, implementation-specific information needed to construct the initial <tt>GetMessage</tt>.
- For example, implementations supporting multiple applications and blocks will have block type and
- message flag parameters.
+ <tt>GetMessages</tt> are used to request information from
+ other peers in the DHT. An application-level API which
+ allows applications to initiate <tt>GetMessages</tt> needs
+ to provide sufficient, implementation-specific information
+ needed to construct the initial <tt>GetMessage</tt>. For
+ example, implementations supporting multiple applications
+ and blocks will need to be given the block type, message
+ <tt>FLAG</tt> parameters and possibly an <tt>XQUERY</tt> in
+ addition to just the <tt>QUERY_HASH</tt>. In some cases, it
+ might also be useful to enable the application to assist in
+ the construction of the <tt>RESULT_FILTER</tt> such that it
+ can filter already known results. Note that the
+ <tt>RESULT_FILTER</tt> may need to be re-constructed every
+ time the query is retransmitted by the initiator (details
+ depending on the <tt>BTYPE</tt>) and thus a
+ <tt>RESULT_FILTER</tt> can often not be passed directly as
+ an argument by the application to an application API.
+ Instead, applications would typically provide the set of
+ results to be filtered, allowing the DHT to construct the
+ <tt>RESULT_FILTER</tt> whenever it retransmits a
+ <tt>GetMessage</tt> request as initiator.
</t>
<section anchor="p2p_get_wire">
<name>Wire Format</name>
@@ -1907,10 +1923,10 @@ BEGIN
/ (128 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
| QUERY_HASH /
-/ (64 byte) |
+/ (64 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
-| RESULT_FILTER /
-/ (variable length) /
+| RESULT_FILTER /
+/ (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
/ XQUERY (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -1924,14 +1940,16 @@ BEGIN
</dd>
<dt>MTYPE</dt>
<dd>
- is the 16-bit message type. Read-only.
- It must be set to
- the value 147 in network byte order as defined in the GANA "GNUnet Message Type" registry <xref target="gana_message_type"/>.
+ is the 16-bit message type. Read-only. It must be set
+ to the value 147 in network byte order as defined in the
+ GANA "GNUnet Message Type" registry <xref
+ target="gana_message_type"/>.
</dd>
<dt>BTYPE</dt>
<dd>
- is a 32-bit block type field in network byte order. The block type indicates the content
- type of the payload. Set by the initiator. Read-only.
+ is a 32-bit block type field in network byte order. The
+ block type indicates the content type of the
+ payload. Set by the initiator. Read-only.
</dd>
<dt>VER</dt>
<dd>
@@ -1947,7 +1965,8 @@ BEGIN
<dd>
is a 16-bit number in network byte order indicating how
many hops this message has traversed to far. Set by the
- initiator to 0. Incremented by processing peers.
+ initiator to zero. Incremented by each peer by one
+ per hop.
</dd>
<dt>REPL_LVL</dt>
<dd>
@@ -1958,7 +1977,7 @@ BEGIN
<dt>RF_SIZE</dt>
<dd>
is a 16-bit number in network byte order indicating the
- length of the result filter RESULT_FILTER. Set by the
+ length of the <tt>RESULT_FILTER</tt>. Set by the
initiator. Read-only.
</dd>
<dt>PEER_BF</dt>
@@ -1969,38 +1988,43 @@ BEGIN
</dd>
<dt>QUERY_HASH</dt>
<dd>
- The query used to indicate what the key is under which the initiator is looking
- for blocks with this request.
- The block type may use a different evaluation logic to determine
- applicable result blocks.
- Set by the initiator. Read-only.
+ The query used to indicate what the key is under which
+ the initiator is looking for blocks with this request.
+ The block type may use a different evaluation logic to
+ determine applicable result blocks. Set by the
+ initiator. Read-only.
</dd>
<dt>RESULT_FILTER</dt>
<dd>
- the variable-length result filter, described in <xref target="result_filter"/>.
- Set by the initiator.
- Modified by processing peers.
+ the variable-length result filter with <tt>RF_SIZE</tt>
+ bytes as described in <xref target="result_filter"/>.
+ Set by the initiator. Modified by processing peers
+ based on results returned.
</dd>
<dt>XQUERY</dt>
<dd>
the variable-length extended query. Optional.
- Set by the initiator. Read-only.
+ Set by the initiator. Read-only. The length is
+ determined by subtracting the length of all
+ other fields from <tt>MSIZE</tt>.
</dd>
</dl>
</section>
<section anchor="result_filter">
<name>Result Filter</name>
<t>
- The result filter is used to indicate to other peers which results
- are not of interest when processing a <tt>GetMessage</tt>
- (<xref target="p2p_get"/>).
- Any peer which is processing <tt>GetMessages</tt> and has a result
- which matches the query key <bcp14>MUST</bcp14> check the result filter
- and only send a reply message if the result does not test positive
- under the result filter. Before forwarding the <tt>GetMessage</tt>, the
- result filter <bcp14>MUST</bcp14> be updated using the result of the <tt>BTYPE</tt>-specific
- <tt>FilterResult</tt> (see <xref target="block_functions"/>) function to filter
- out all results already returned by the local peer.
+ A result filter is used to indicate to other peers which
+ results are not of interest when processing a
+ <tt>GetMessage</tt> (<xref target="p2p_get"/>). Any peer
+ which is processing <tt>GetMessages</tt> and has a result
+ which matches the query key <bcp14>MUST</bcp14> check the
+ result filter and only send a reply message if the result
+ does not test positive under the result filter. Before
+ forwarding the <tt>GetMessage</tt>, the result filter
+ <bcp14>MUST</bcp14> be updated using the result of the
+ <tt>BTYPE</tt>-specific <tt>FilterResult</tt> (see <xref
+ target="block_functions"/>) function to filter out all
+ results already returned by the local peer.
</t>
<t>
How a result filter is implemented depends on the block type
@@ -2010,8 +2034,9 @@ BEGIN
filter because of a false-positive test.
</t>
<t>
- How exactly a block result is added to a result filter
- is specified as part of the definition of a block type (cf. <xref target="hello_block"/>).
+ How exactly a block result is added to a result filter is
+ specified as part of the definition of a block type
+ (cf. <xref target="hello_block"/>).
</t>
</section>
<section anchor="p2p_get_processing">
@@ -2023,28 +2048,34 @@ BEGIN
</t>
<ol>
<li>
- If the <tt>BTYPE</tt> is supported, the <tt>QUERY_HASH</tt> and <tt>XQUERY</tt> fields are validated
- as defined by the respective <tt>ValidateBlockQuery</tt> procedure for this type.
- If the result yields <tt>REQUEST_INVALID</tt>, the message <bcp14>MUST</bcp14> be discarded and
- processing ends.
- If the <tt>BTYPE</tt> is not supported, the message <bcp14>MUST</bcp14>
- be forwarded (Skip to step 4).
- If the <tt>BTYPE</tt> is <tt>ANY</tt>, the message is processed further
- without validation.
+ If the <tt>BTYPE</tt> is supported, the
+ <tt>QUERY_HASH</tt> and <tt>XQUERY</tt> fields are
+ validated as defined by the respective
+ <tt>ValidateBlockQuery()</tt> procedure for this type. If
+ the result yields <tt>REQUEST_INVALID</tt>, the message
+ <bcp14>MUST</bcp14> be discarded and processing ends.
+ If the <tt>BTYPE</tt> is not supported, the message
+ <bcp14>MUST</bcp14> be forwarded (Skip to step 4). If
+ the <tt>BTYPE</tt> is <tt>ANY</tt>, the message is
+ processed further without validation.
</li>
<li>
- The peer identity of the sender peer <tt>P</tt> <bcp14>SHOULD</bcp14> be in the
- <tt>PEER_BF</tt> Bloom filter. If not, the
- implementation <bcp14>MAY</bcp14> log an error, but <bcp14>MUST</bcp14> continue.
+ The peer identity of the sender peer <tt>P</tt>
+ <bcp14>SHOULD</bcp14> be in the <tt>PEER_BF</tt> peer
+ Bloom filter. If not, the implementation
+ <bcp14>MAY</bcp14> log an error, but <bcp14>MUST</bcp14>
+ continue.
</li>
<li>
<t>
- The local peer <bcp14>SHOULD</bcp14> try to produce a reply in any of the following cases:
- (1) If the local peer is the closest peer
- (cf. <tt>IsClosestPeer (SELF, QueryHash, PeerFilter)</tt>, or (2)
- if the <tt>DemultiplexEverywhere</tt> flag is set, or (3)
- if the local peer is not the closest and a previously
- cached <tt>ResultMessage</tt> also matches this request (<xref target="p2p_result_processing"/>).
+ The local peer <bcp14>SHOULD</bcp14> try to produce a
+ reply in any of the following cases: (1) If the local
+ peer is the closest peer (cf. <tt>IsClosestPeer(SELF,
+ QueryHash, PeerFilter)</tt>, or (2) if the
+ <tt>DemultiplexEverywhere</tt> flag is set, or (3) if
+ the local peer is not the closest and a previously
+ cached <tt>ResultMessage</tt> also matches this
+ request (<xref target="p2p_result_processing"/>).
</t>
<t>
The reply is produced (if one is available) using the following
@@ -2052,68 +2083,89 @@ BEGIN
</t>
<ol type="%c)">
<li>
- If the <tt>BTYPE</tt> is <tt>HELLO</tt>, the implementation <bcp14>MUST</bcp14> only consider
- synthesizing its own addresses and the addresses it has cached for the peers in its routing table
- as <tt>HELLO</tt> block replies.
- Otherwise, if the <tt>BTYPE</tt> does not indicate a request for a <tt>HELLO</tt> block or
- <tt>ANY</tt>,
- the implementation <bcp14>MUST</bcp14> only consider blocks in the local block storage
- and previously cached <tt>ResultMessages</tt>.
+ If the <tt>BTYPE</tt> is <tt>HELLO</tt>, the
+ implementation <bcp14>MUST</bcp14> only consider
+ synthesizing its own addresses and the addresses it
+ has cached for the peers in its routing table as
+ <tt>HELLO</tt> block replies. Otherwise, if the
+ <tt>BTYPE</tt> does not indicate a request for a
+ <tt>HELLO</tt> block or <tt>ANY</tt>, the
+ implementation <bcp14>MUST</bcp14> only consider
+ blocks in the local block storage and previously
+ cached <tt>ResultMessages</tt>.
</li>
<li>
- If the <tt>FLAGS</tt> field includes the flag <tt>FindApproximate</tt>,
- the peer <bcp14>SHOULD</bcp14> respond with the closest block (smallest value
- of <tt>GetDistance(QUERY_HASH, BLOCK_KEY)</tt>) it
- can find that is not filtered by the <tt>RESULT_BF</tt>.
- Otherwise, the peer <bcp14>MUST</bcp14> respond with the block
- with a <tt>BLOCK_KEY</tt> that matches the <tt>QUERY_HASH</tt> exactly and that is
- not filtered by the <tt>RESULT_BF</tt>.
+ If the <tt>FLAGS</tt> field includes the flag
+ <tt>FindApproximate</tt>, the peer
+ <bcp14>SHOULD</bcp14> respond with the closest block
+ (smallest value of <tt>GetDistance(QUERY_HASH,
+ BLOCK_KEY)</tt>) it can find that is not filtered by
+ the <tt>RESULT_BF</tt>. Otherwise, the peer
+ <bcp14>MUST</bcp14> respond with the block with a
+ <tt>BLOCK_KEY</tt> that matches the
+ <tt>QUERY_HASH</tt> exactly and that is not filtered
+ by the <tt>RESULT_BF</tt>.
</li>
<li>
- Any resulting (synthesized) block is encapsulated in a
- <tt>ResultMessage</tt>.
- The <tt>ResultMessage</tt> <bcp14>SHOULD</bcp14> be transmitted to the
- neighbor from which the request was received.
+ Any resulting (synthesized) block is encapsulated in
+ a <tt>ResultMessage</tt>. The
+ <tt>ResultMessage</tt> <bcp14>SHOULD</bcp14> be
+ transmitted to the neighbor from which the request
+ was received.
</li>
</ol>
<t>
- Implementations <bcp14>MAY</bcp14> not reply if they are resource-constrained.
- However, <tt>ResultMessages</tt> <bcp14>MUST</bcp14> be given the
- highest priority among competing transmissions.
+ Implementations <bcp14>MAY</bcp14> not reply if they
+ are resource-constrained. However,
+ <tt>ResultMessages</tt> <bcp14>MUST</bcp14> be given
+ the highest priority among competing transmissions.
</t>
<t>
- If the <tt>BTYPE</tt> is supported and <tt>ValidateBlockReply</tt> for the given
- query has yielded a status of <tt>FILTER_LAST</tt>, processing
- <bcp14>MUST</bcp14> end and not continue with forwarding of
- the request to other peers.
+ If the <tt>BTYPE</tt> is supported and
+ <tt>ValidateBlockReply</tt> for the given query has
+ yielded a status of <tt>FILTER_LAST</tt>, processing
+ <bcp14>MUST</bcp14> end and not continue with
+ forwarding of the request to other peers.
</t>
</li>
<li>
- <!-- FIXME: For how long? what exactly must be stored? -->
- The implementation <tt>SHOULD</tt> create (or merge) an entry in the pending table
- <xref target="pending_table"/> for the query represented by this <tt>GetMessage</tt>.
- If the peer is unable to handle an additional entry in the table, the message
- <bcp14>MUST</bcp14> be discarded and processing ends.
+ The implementation <tt>MUST</tt> create (or merge) an
+ entry in the pending table (see <xref
+ target="pending_table"/>) for the query represented by
+ this <tt>GetMessage</tt>. The pending table
+ <bcp14>MUST</bcp14> store the last <tt>MAX_RECENT</tt>
+ requests, and peers thus <bcp14>MUST</bcp14> discard the
+ oldest existing request if memory constraints on the
+ pending table are encountered. Note that peers
+ <bcp14>MAY</bcp14> clean up state for queries that had
+ response with a status of <tt>FILTER_LAST</tt> even if
+ they are not the oldest query in the pending table.
</li>
<li>
- Using the value in <tt>REPL_LVL</tt>, the number of peers to forward to
- <bcp14>MUST</bcp14> be calculated using
- <tt>ComputeOutDegree()</tt>.
- 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>SHOULD</bcp14> select up to this
- number of peers to forward the message to using the function <tt>SelectPeer()</tt> (<xref target="routing_functions"/>)
- using the <tt>QUERY_HASH</tt>, <tt>HOPCOUNT</tt>, an appropriate bloom filter (FIXME: Start with PEER_BF?).
- The implementation <bcp14>MAY</bcp14>
- forward to fewer or no peers in order to handle resource constraints
- such as bandwidth.
- The peer Bloom filter <tt>PEER_BF</tt> <bcp14>MUST</bcp14> be updated with the local
- peer identity <tt>SELF</tt> for any forwarded message.
- For all peers with peer identity <tt>P</tt> chosen to forward the message
- to, <tt>SEND(P, GetMessageP)</tt> is called. Here, <tt>GetMessageP</tt>
- is the original message with the updated fields for <tt>HOPCOUNT</tt> (incremented
- by 1), <tt>PEER_BF</tt> and <tt>RESULT_FILTER</tt>.
+ Using the value in <tt>REPL_LVL</tt>, the number of
+ peers to forward to <bcp14>MUST</bcp14> be calculated
+ using <tt>ComputeOutDegree()</tt>. 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. Furthermore, the
+ implementation <bcp14>SHOULD</bcp14> select up to this
+ number of peers to using the function
+ <tt>SelectPeer()</tt> (from <xref
+ target="routing_functions"/>) using the
+ <tt>QUERY_HASH</tt>, <tt>HOPCOUNT</tt>, and the
+ <tt>PEER_BF</tt>. The implementation <bcp14>MAY</bcp14>
+ forward to fewer or no peers in order to handle resource
+ constraints such as bandwidth. Before forwarding, the
+ peer Bloom filter <tt>PEER_BF</tt> <bcp14>MUST</bcp14>
+ be updated to filter all selected peers and the local
+ peer identity <tt>SELF</tt>. For all peers with peer
+ identity <tt>P</tt> chosen to forward the message to,
+ <tt>SEND(P, GetMessage_P)</tt> is called. Here,
+ <tt>GetMessage_P</tt> is the original message with the
+ updated fields for <tt>HOPCOUNT</tt> (incremented by
+ one), updated <tt>PEER_BF</tt> and updated
+ <tt>RESULT_FILTER</tt> (based on results already
+ returned).
</li>
</ol>
</section>
@@ -2121,10 +2173,11 @@ BEGIN
<section anchor="p2p_result" numbered="true" toc="default">
<name>ResultMessage</name>
<t>
- <tt>ResultMessages</tt> are used to return information to other peers in the DHT
- or to applications using the overlay API that previously initiated a <tt>GetMessage</tt>.
- The initiator of a <tt>ResultMessage</tt> is a peer triggered through the processing
- of a <tt>GetMessage</tt>.
+ <tt>ResultMessages</tt> are used to return information to
+ other peers in the DHT or to applications using the overlay
+ API that previously initiated a <tt>GetMessage</tt>. The
+ initiator of a <tt>ResultMessage</tt> is a peer triggered
+ through the processing of a <tt>GetMessage</tt>.
</t>
<section anchor="p2p_result_wire">
<name>Wire Format</name>
@@ -2164,9 +2217,11 @@ BEGIN
</dd>
<dt>MTYPE</dt>
<dd>
- is the 16-bit message type. Set by the initiator. Read-only.
- It must be set to
- the value 148 in network byte order as defined in the GANA "GNUnet Message Type" registry <xref target="gana_message_type"/>.
+ is the 16-bit message type. Set by the
+ initiator. Read-only. It must be set to the value 148
+ in network byte order as defined in the GANA "GNUnet
+ Message Type" registry (see <xref
+ target="gana_message_type"/>).
</dd>
<dt>BTYPE</dt>
<dd>
@@ -2188,13 +2243,13 @@ BEGIN
</dd>
<dt>FLAGS</dt>
<dd>
- is a 8-bit vector with binary options (see <xref target="route_flags"/>).
- Set by the initiator. <!-- FIXME to what? => Copied from GET?
- The code currently just sets the recorded PUT flags / overrides GET
- What should happen?
- Currently in case of HELLO => flags cleared.
- HELLO only FindApprox
- Application preserve flags from PUT-->
+ is a 8-bit vector with binary options (see <xref
+ target="route_flags"/>). Set by the initiator of the
+ response based on the flags retained from the original
+ <tt>PutMessage</tt>, possibly setting the
+ <tt>Truncated</tt> bit if the initiator is forced to
+ truncate the path. For <tt>HELLO</tt> blocks, the
+ <tt>FLAGS</tt> should simply be cleared.
</dd>
<dt>PUTPATH_L</dt>
<dd>
@@ -2212,22 +2267,24 @@ BEGIN
number of path elements recorded in <tt>GETPATH</tt>. As
<tt>GETPATH</tt> is optional, this value may be zero
even if the message has traversed several peers.
- <bcp14>MUST</bcp14> be set to 0 by the initiator.
- Modified by processing peers to match the path length in the message.
+ <bcp14>MUST</bcp14> be set to zero by the initiator.
+ Modified by processing peers to match the path length in
+ the message.
</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.
- Set by the initiator to the expiration value as recorded from
- the <tt>PutMessage</tt> from which the block originated.
+ denotes the absolute 64-bit expiration date of the
+ content in microseconds since midnight (0 hour), January
+ 1, 1970 in network byte order. Set by the initiator to
+ the expiration value as recorded from the
+ <tt>PutMessage</tt> from which the block originated.
Read-only.
</dd>
<dt>QUERY_HASH</dt>
<dd>
- the query hash corresponding to the <tt>GetMessage</tt> which
- caused this reply message to be sent.
- Set by the initiator using the value of the <tt>GetMessage</tt>.
+ the query hash corresponding to the <tt>GetMessage</tt>
+ which caused this reply message to be sent. Set by the
+ initiator using the value of the <tt>GetMessage</tt>.
Read-only.
</dd>
<dt>TRUNCATED ORIGIN</dt>
@@ -2244,147 +2301,178 @@ BEGIN
</dd>
<dt>PUTPATH</dt>
<dd>
- the variable-length PUT path.
- The path consists of a list of <tt>PUTPATH_L</tt> path elements.
- Set by the initiator to the the <tt>PUTPATH</tt> of the <tt>PutMessage</tt>
- from which the block originated.
+ the variable-length PUT path. The path consists of a
+ list of <tt>PUTPATH_L</tt> path elements. Set by the
+ initiator to the the <tt>PUTPATH</tt> of the
+ <tt>PutMessage</tt> from which the block originated.
Modified by processing peers in case of path truncation.
</dd>
<dt>GETPATH</dt>
<dd>
- the variable-length PUT path.
- The path consists of a list of <tt>GETPATH_L</tt> path elements.
- Set by processing peers.
+ the variable-length PUT path. The path consists of a
+ list of <tt>GETPATH_L</tt> path elements. Set by
+ processing peers.
</dd>
<dt>LAST HOP SIGNATURE</dt>
<dd>
- is only provided if the <tt>RecordRoute</tt> flag
- is set in FLAGS. If present, this is
- an EdDSA signature <xref target="ed25519"/> by the sender of this message
- (using the same format as the signatures in PUTPATH)
- affirming that the sender forwarded the message from
- the predecessor (all zeros if PATH_LEN is 0,
- otherwise the last peer in PUTPATH) to
- the target peer.
+ is only provided if the <tt>RecordRoute</tt> flag is set
+ in <tt>FLAGS</tt>. If present, this is an EdDSA
+ signature <xref target="ed25519"/> by the sender of this
+ message (using the same format as the signatures in
+ <tt>PUTPATH</tt>) affirming that the sender forwarded
+ the message from the predecessor (all zeros if
+ <tt>PATH_LEN</tt> is zero, otherwise the last peer in
+ <tt>PUTPATH</tt>) to the target peer.
</dd>
<dt>BLOCK</dt>
<dd>
- the variable-length resource record data payload.
- The contents are defined by the respective type of the resource record.
- Set by the initiator. Read-only.
+ the variable-length resource record data payload. The
+ contents are defined by the respective type of the
+ resource record. Set by the initiator. Read-only.
</dd>
</dl>
</section>
<section anchor="p2p_result_processing">
<name>Processing</name>
<t>
- Upon receiving a <tt>ResultMessage</tt> from a connected peer or
- triggered by the processing of a <tt>GetMessage</tt>,
- an implementation <bcp14>MUST</bcp14> process it step by step as follows:
+ Upon receiving a <tt>ResultMessage</tt> from a connected
+ peer or triggered by the processing of a
+ <tt>GetMessage</tt>, an implementation <bcp14>MUST</bcp14>
+ process it step by step as follows:
</t>
<ol>
<li>
- First, the <tt>EXPIRATION</tt> field is evaluated.
- If the message is expired, it <bcp14>MUST</bcp14> be discarded.
+ First, the <tt>EXPIRATION</tt> field is evaluated. If
+ the message is expired, it <bcp14>MUST</bcp14> be
+ discarded.
</li>
<li>
- If the <tt>BTYPE</tt> is supported, then the <tt>BLOCK</tt>
- <bcp14>MUST</bcp14> be validated against the
- requested <tt>BTYPE</tt>. To do this, the peer
- checks that the block is valid using <tt>ValidateBlockStoreRequest</tt>.
- If the result is <tt>BLOCK_INVALID</tt>, the message <bcp14>MUST</bcp14> be
- discarded.
+ If the <tt>BTYPE</tt> is supported, then the
+ <tt>BLOCK</tt> <bcp14>MUST</bcp14> be validated against
+ the requested <tt>BTYPE</tt>. To do this, the peer
+ checks that the block is valid using
+ <tt>ValidateBlockStoreRequest</tt>. If the result is
+ <tt>BLOCK_INVALID</tt>, the message <bcp14>MUST</bcp14>
+ be discarded.
</li>
<li>
- If the <tt>PUTPATH_L</tt> or the <tt>GETPATH_L</tt> are non-zero,
- the local peer <bcp14>SHOULD</bcp14> verify the signatures from the <tt>PUTPATH</tt>
- and the <tt>GETPATH</tt>.
- Verification <bcp14>MAY</bcp14> involve checking all signatures or any random
- subset of the signatures. It is <bcp14>RECOMMENDED</bcp14> that peers adapt
- their behavior to available computational resources so as to not make signature
- verification a bottleneck. If an invalid signature is found, the
- path <bcp14>MUST</bcp14> be truncated to only include the elements
- following the invalid signature. In particular, any invalid signature
- on the <tt>GETPATH</tt> will cause <tt>PUTPATH_L</tt> to be set to 0.
+ If the <tt>PUTPATH_L</tt> or the <tt>GETPATH_L</tt> are
+ non-zero, the local peer <bcp14>SHOULD</bcp14> verify
+ the signatures from the <tt>PUTPATH</tt> and the
+ <tt>GETPATH</tt>. Verification <bcp14>MAY</bcp14>
+ involve checking all signatures or any random subset of
+ the signatures. It is <bcp14>RECOMMENDED</bcp14> that
+ peers adapt their behavior to available computational
+ resources so as to not make signature verification a
+ bottleneck. If an invalid signature is found, the path
+ <bcp14>MUST</bcp14> be truncated to only include the
+ elements following the invalid signature. In
+ particular, any invalid signature on the
+ <tt>GETPATH</tt> will cause <tt>PUTPATH_L</tt> to be set
+ to zero.
</li>
<li>
- The peer also attempts to compute the
- key using <tt>DeriveBlockKey</tt>. This may result in <tt>NONE</tt>.
- The result is used later. Note that even if a key was computed, it
- does not have to match the <tt>QUERY_HASH</tt>.
+ The peer also attempts to compute the key using
+ <tt>DeriveBlockKey</tt>. This may result in
+ <tt>NONE</tt>. The result is used later. Note that
+ even if a key was computed, it does not have to match
+ the <tt>QUERY_HASH</tt>.
</li>
<li>
- If the <tt>BTYPE</tt> of the message indicates a <tt>HELLO</tt> block, the
- peer <bcp14>SHOULD</bcp14> be considered for the local routing
- table by using the peer identity computed from the block using <tt>DeriveBlockKey</tt>.
- An implementation <bcp14>MAY</bcp14> choose to ignore the <tt>HELLO</tt>, for example
- because the routing table or the respective k-bucket is already full.
- If the peer is a suitable candidate for insertion, the local peer <bcp14>MUST</bcp14> try to establish a connection
- to the peer indicated in the <tt>HELLO</tt> block using the address information
- from the <tt>HELLO</tt> block and the underlay's <tt>TRY_CONNECT()</tt> function.
- The implementation <bcp14>MUST</bcp14> instruct the underlay to connect to all provided addresses
- using <tt>TRY_CONNECT()</tt> in order to make the underlay aware of multiple addresses for this connection.
- When a connection is established, the signal <tt>PEER_CONNECTED</tt> will cause
- the peer to be added to the respective k-bucket of the routing table (<xref target="routing"/>).
+ If the <tt>BTYPE</tt> of the message indicates a
+ <tt>HELLO</tt> block, the peer <bcp14>SHOULD</bcp14> be
+ considered for the local routing table by using the peer
+ identity computed from the block using
+ <tt>DeriveBlockKey</tt>. An implementation
+ <bcp14>MAY</bcp14> choose to ignore the <tt>HELLO</tt>,
+ for example because the routing table or the respective
+ k-bucket is already full. If the peer is a suitable
+ candidate for insertion, the local peer
+ <bcp14>MUST</bcp14> try to establish a connection to the
+ peer indicated in the <tt>HELLO</tt> block using the
+ address information from the <tt>HELLO</tt> block and
+ the underlay's <tt>TRY_CONNECT()</tt> function. The
+ implementation <bcp14>MUST</bcp14> instruct the underlay
+ to connect to all provided addresses using
+ <tt>TRY_CONNECT()</tt> in order to make the underlay
+ aware of multiple addresses for this connection. When a
+ connection is established, the signal
+ <tt>PEER_CONNECTED</tt> will cause the peer to be added
+ to the respective k-bucket of the routing table (<xref
+ target="routing"/>).
</li>
<li>
- If the <tt>QUERY_HASH</tt> of this <tt>ResultMessage</tt> does not match an entry in the
- pending table (<xref target="pending_table"/>), then the message is discarded and processing ends.
- Otherwise, processing continues for each entry in the table as follows.
+ If the <tt>QUERY_HASH</tt> of this
+ <tt>ResultMessage</tt> does not match an entry in the
+ pending table (<xref target="pending_table"/>), then the
+ message is discarded and processing ends. Otherwise,
+ processing continues for each entry in the table as
+ follows.
</li>
<li>
<ol type="%c)">
<li>
- If the <tt>FindApproximate</tt> flag was not set in the query and the <tt>BTYPE</tt> allowed the
- implementation to compute the key from the block, the computed key must
- exactly match the <tt>QUERY_HASH</tt>, otherwise the result does
- not match the pending query and processing continues with the next pending query.
+ If the <tt>FindApproximate</tt> flag was not set in
+ the query and the <tt>BTYPE</tt> allowed the
+ implementation to compute the key from the block,
+ the computed key must exactly match the
+ <tt>QUERY_HASH</tt>, otherwise the result does not
+ match the pending query and processing continues
+ with the next pending query.
</li>
<li>
- If the <tt>BTYPE</tt> is supported, result block <bcp14>MUST</bcp14>
- be validated against the specific query using
- the respective <tt>FilterBlockResult</tt> function. This function
- <bcp14>MUST</bcp14> update
- the result filter if a result is returned to the originator of the
- query.
+ If the <tt>BTYPE</tt> is supported, result block
+ <bcp14>MUST</bcp14> be validated against the
+ specific query using the respective
+ <tt>FilterBlockResult</tt> function. This function
+ <bcp14>MUST</bcp14> update the result filter if a
+ result is returned to the originator of the query.
</li>
<li>
- If the <tt>BTYPE</tt> is not supported, filtering of exact duplicate
- replies <bcp14>MUST</bcp14> still be performed before forwarding
- the reply.
- Such duplicate filtering <bcp14>MAY</bcp14> be implemented
- probabilistically, for example using a Bloom filter.
- The result of this duplicate filtering is always either
- <tt>FILTER_MORE</tt> or <tt>FILTER_DUPLICATE</tt>.
+ If the <tt>BTYPE</tt> is not supported, filtering of
+ exact duplicate replies <bcp14>MUST</bcp14> still be
+ performed before forwarding the reply. Such
+ duplicate filtering <bcp14>MAY</bcp14> be
+ implemented probabilistically, for example using a
+ Bloom filter. The result of this duplicate
+ filtering is always either <tt>FILTER_MORE</tt> or
+ <tt>FILTER_DUPLICATE</tt>.
</li>
<li>
If the <tt>RecordRoute</tt> flag is set in FLAGS,
- the local peer identity <bcp14>MUST</bcp14> be appended to the <tt>GETPATH</tt>
- of the message and the respective signature <bcp14>MUST</bcp14> be
- set using the query origin as the <tt>PEER SUCCESSOR</tt> and the
- response origin as the <tt>PEER PREDECESSOR</tt>. If the flag is not set,
- the <tt>GETPATH_L</tt> and <tt>PUTPATH_L</tt>
- <bcp14>MUST</bcp14> be set to zero when forwarding the result.
+ the local peer identity <bcp14>MUST</bcp14> be
+ appended to the <tt>GETPATH</tt> of the message and
+ the respective signature <bcp14>MUST</bcp14> be set
+ using the query origin as the <tt>PEER
+ SUCCESSOR</tt> and the response origin as the
+ <tt>PEER PREDECESSOR</tt>. If the flag is not set,
+ the <tt>GETPATH_L</tt> and <tt>PUTPATH_L</tt>
+ <bcp14>MUST</bcp14> be set to zero when forwarding
+ the result.
</li>
<li>
- If the result filter result is either <tt>FILTER_MORE</tt> or <tt>FILTER_LAST</tt>,
- the message is forwarded to the origin of the query as defined in the entry
- which may either be the local peer or a remote peer.
- In case this is a query of the local peer the result may have to be provided to
- applications through the overlay API.
- Otherwise, the result is forwarded using <tt>SEND(P, ResultMessage')</tt> where
- <tt>ResultMessage'</tt> is the now modified message.
- If the result was <tt>FILTER_LAST</tt>, the query is removed from the pending table.
+ If the result filter result is either
+ <tt>FILTER_MORE</tt> or <tt>FILTER_LAST</tt>, the
+ message is forwarded to the origin of the query as
+ defined in the entry which may either be the local
+ peer or a remote peer. In case this is a query of
+ the local peer the result may have to be provided to
+ applications through the overlay API. Otherwise,
+ the result is forwarded using <tt>SEND(P,
+ ResultMessage')</tt> where <tt>ResultMessage'</tt>
+ is the now modified message. If the result was
+ <tt>FILTER_LAST</tt>, the query is removed from the
+ pending table.
</li>
</ol>
</li>
<li>
Finally, the implementation <bcp14>SHOULD</bcp14> cache
- <tt>ResultMessages</tt> in order to provide already seen replies to
- future <tt>GetMessages</tt>.
- The implementation <bcp14>MAY</bcp14> choose not no cache any or
- a limited number of <tt>ResultMessages</tt> for reasons such as resource
- limitations.
+ <tt>ResultMessages</tt> in order to provide already seen
+ replies to future <tt>GetMessages</tt>. The
+ implementation <bcp14>MAY</bcp14> choose not no cache
+ any or a limited number of <tt>ResultMessages</tt> for
+ reasons such as resource limitations.
</li>
</ol>
</section>
@@ -2430,76 +2518,108 @@ BEGIN
</t>
<dl>
<dt>REQUEST_VALID</dt>
- <dd>Query is valid.</dd>
+ <dd>
+ The query is valid.
+ </dd>
<dt>REQUEST_INVALID</dt>
<dd>
- Query format does not match block type. For example, a
- mandatory XQuery was not provided, or of the size of
- the XQuery is not appropriate for the block type.
+ Query format does not match block type. For example,
+ a mandatory <tt>XQuery</tt> was not provided, or of
+ the size of the <tt>XQuery</tt> is not appropriate
+ for the block type.
</dd>
</dl>
</dd>
<dt>DeriveBlockKey(Block) -> Key | NONE</dt>
<dd>
- is used to synthesize the block key from the block payload as
- part of <tt>PutMessage</tt> and <tt>ResultMessage</tt> processing.
- The special return value of <tt>NONE</tt> implies that this block type does not
- permit deriving the key from the block. A Key may be returned
- for a block that is ill-formed.
+ is used to synthesize the block key from the block
+ payload as part of <tt>PutMessage</tt> and
+ <tt>ResultMessage</tt> processing. The special return
+ value of <tt>NONE</tt> implies that this block type does
+ not permit deriving the key from the block. A
+ <tt>Key</tt> may be returned for a block that is
+ ill-formed.
</dd>
<dt>ValidateBlockStoreRequest(Block)
-> BlockEvaluationResult</dt>
<dd>
<t>
- is used to evaluate a block payload
- as part of <tt>PutMessage</tt> and <tt>ResultMessage</tt> processing.
- Possible values for the <tt>BlockEvaluationResult</tt> are:
+ is used to evaluate a block payload as part of
+ <tt>PutMessage</tt> and <tt>ResultMessage</tt>
+ processing. Possible values for the
+ <tt>BlockEvaluationResult</tt> are:
</t>
<dl>
<dt>BLOCK_VALID</dt>
- <dd>Block is valid.</dd>
+ <dd>
+ The block is valid.
+ </dd>
<dt>BLOCK_INVALID</dt>
- <dd>Block payload does not match the block type.
+ <dd>
+ The block payload does not match the block type.
</dd>
</dl>
</dd>
<dt>SetupResultFilter(FilterSize, Mutator) -> RF</dt>
<dd>
is used to setup an empty result filter. The arguments
- are the set of results that must be filtered at the
- initiator, and a <tt>MUTATOR</tt> value which <bcp14>MAY</bcp14>
- be used to deterministically re-randomize
- probabilistic data structures. The specification <bcp14>MUST</bcp14>
- also include the wire format for BF.
+ are the size of the set of results that must be filtered
+ at the initiator, and a <tt>Mutator</tt> value which
+ <bcp14>MAY</bcp14> be used to deterministically
+ re-randomize probabilistic data structures. <tt>RF</tt>
+ <bcp14>MUST</bcp14> be a byte sequence suitable for
+ transmission over the network.
</dd>
<dt>FilterResult(Block, Key, RF, XQuery) -> (FilterEvaluationResult, RF')</dt>
<dd>
<t>
- is used to filter results against specific queries. This function
- does not check the validity of Block itself or that it matches the given key,
- as this must have been checked earlier.
- Thus, locally stored blocks from previously observed
- <tt>ResultMessages</tt> and <tt>PutMessages</tt> use this
- function to perform filtering based on the request parameters
- of a particular GET operation.
- Possible values for the <tt>FilterEvaluationResult</tt> are:
+ is used to filter results against specific queries.
+ This function does not check the validity of
+ <tt>Block</tt> itself or that it matches the given key,
+ as this must have been checked earlier. Thus, locally
+ stored blocks from previously observed
+ <tt>ResultMessages</tt> and <tt>PutMessages</tt> use
+ this function to perform filtering based on the request
+ parameters of a particular GET operation. Possible
+ values for the <tt>FilterEvaluationResult</tt> are:
</t>
<dl>
<dt>FILTER_MORE</dt>
- <dd>Valid result, and there may be more.</dd>
+ <dd>
+ <tt>Block</tt> is a valid result, and there may be more.
+ </dd>
<dt>FILTER_LAST</dt>
- <dd>Last possible valid result.</dd>
+ <dd>
+ The given <tt>Block</tt> is the last possible valid result.
+ </dd>
<dt>FILTER_DUPLICATE</dt>
- <dd>Valid result, but duplicate (was filtered by the result filter).</dd>
+ <dd>
+ <tt>Block</tt> is a valid result, but considered to be
+ a duplicate (was filtered by the <tt>RF</tt>) and
+ <bcp17>SHOULD NOT</bcp17> be returned to the previous
+ hop. Peers that do not understand the block type
+ <bcp17>MAY</bcp17> return such duplicate results
+ anyway.
+ </dd>
<dt>FILTER_IRRELEVANT</dt>
- <dd>Block does not satisfy the constraints imposed by the XQuery.</dd>
+ <dd>
+ <tt>Block</tt> does not satisfy the constraints
+ imposed by the <tt>XQuery</tt>. The result
+ <bcp17>SHOULD NOT</bcp17> be returned to the previous
+ hop. Peers that do not understand the block type
+ <bcp17>MAY</bcp17> return such irrelevant results
+ anyway.
+ </dd>
</dl>
<t>
- If the main evaluation result is <tt>FILTER_MORE</tt>, the function also returns
- an updated result filter where the block is added to the set of
- filtered replies. An implementation is not expected to actually differenciate
- between the <tt>FILTER_DUPLICATE</tt> and <tt>FILTER_IRRELEVANT</tt> return
- values: in both cases the block is ignored for this query.
+ If the main evaluation result is <tt>FILTER_MORE</tt>,
+ the function also returns an updated result filter
+ where the <tt>Block</tt> is added to the set of
+ filtered replies. An implementation is not expected
+ to actually differenciate between the
+ <tt>FILTER_DUPLICATE</tt> and
+ <tt>FILTER_IRRELEVANT</tt> return values: in both
+ cases the <tt>Block</tt> is ignored for this query.
</t>
</dd>
</dl>
@@ -2634,7 +2754,10 @@ BEGIN
<dt>ValidateBlockQuery(Key, XQuery)
-> RequestEvaluationResult</dt>
<dd>
- To validate a block query for a <tt>HELLO</tt> is to simply check that the XQuery is empty. If it is empty, REQUEST_VALID ist returned. Otherwise, REQUEST_INVALID.
+ To validate a block query for a <tt>HELLO</tt> is to
+ simply check that the XQuery is empty. If it is empty,
+ <tt>REQUEST_VALID</tt> ist returned. Otherwise,
+ <tt>REQUEST_INVALID</tt> is returned.
</dd>
<dt>DeriveBlockKey(Block) -> Key | NONE</dt>
<dd>
