commit a66ea2c2f512a146ffc2b18bf8771f68fc909e7c
parent 4b986ac3c1a6655f77abf75d5dcb571fab3cf240
Author: Christian Grothoff <grothoff@gnunet.org>
Date: Fri, 11 Mar 2022 05:53:12 +0100
-fix path description
Diffstat:
1 file changed, 83 insertions(+), 72 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -938,97 +938,64 @@ bchar = *(ALPHA / DIGIT)
processing are detailed.
Where required, the local peer's ID is referred to as <tt>SELF</tt>.
</t>
- <section anchor="route_flags">
- <name>Flags</name>
- <t>
- is a 16-bit vector representing binary options.
- Each flag is represented by a bit in the field starting from 0 as
- the rightmost bit to 15 as the leftmost bit.
- <!--FIXME: Actually, we set those bits and then store the resulting
- value in NBO...-->
+ <section anchor="message_components">
+ <name>Message components</name>
+ <t>
+ This section describes some data structures and fields shared
+ by various message types.
</t>
- <dl>
+ <section anchor="route_flags">
+ <name>Flags</name>
+ <t>
+ Flags is a 16-bit vector representing binary options.
+ Each flag is represented by a bit in the field starting from 0 as
+ the rightmost bit to 15 as the leftmost bit.
+ <!--FIXME: Actually, we set those bits and then store the resulting
+ value in NBO...-->
+ </t>
+ <dl>
<dt>0: DemultiplexEverywhere</dt>
<dd>
- indicates that each peer along the way should process the request.
+ This bit indicates that each peer along the way should process the request.
+ If the bit is not set, peers only route the message and do not
+ look for answers in their local storage (for GET) or cache the
+ block in their local storage (for PUT or RESULT).
</dd>
<dt>1: RecordRoute</dt>
<dd>
- indicates to keep track of the route that the message takes
- in the P2P network.
+ This bit indicates to keep track of the path that the message takes
+ in the P2P network.
</dd>
<dt>2: FindApproximate</dt>
<dd>
- This is a special flag which modifies the message processing to
- allow approximate results.
+ This bit allows results where the key does not match exactly.
</dd>
<dt>3-15: Reserved</dt>
<dd>
- For future use.
+ The remaining bits are reserved for future use and
+ <bcp14>MUST</bcp14> be set to 0 when initiating an operation.
+ If non-zero bits are received, implementations <bcp14>MUST</bcp14>
+ preserve these bits when forwarding messages.
</dd>
</dl>
</section>
- <section anchor="result_bloomfilter">
- <name>Result Bloom Filter</name>
- <t>
- The result Bloom filter is used to indicate to a peer which results
- 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 <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. <!-- FIXME: is this strictly always the block key?
- I think this is block-type dependent! -->
- </t>
- <t>
- FIXME: say something about the size of the result Bloom filter here!
- </t>
- <t>
- Bloom filters are probabilistic data structures. Thus, especially
- given the small size of the result Bloom filter, it is always possible
- that a desireable result is filtered by the Bloom filter because of
- a false-positive match created by a collision in the hash values
- between the desireable result and filtered items.
- </t>
- <t>
- To address this problem, R<sup>5</sup>N uses a mutator value
- to additionally randomize the process
- when hashing results into the result Bloom filter. The mutator
- value is set by the peer initiating the GET request, and changed
- every time the GET request is repeated by the initiator. Peers
- forwarding GET requests <bcp14>MUST</bcp14> not change the
- mutator value included in the GET message as they could not
- recalculate the Bloom filter with the new mutator value.
- </t>
- <t>
- By including the mutator value in the hashing process, repeated
- requests have statistically independent probabilities of creating
- collisions in the Bloom filter. Thus, even if for one request
- a Bloom filter collision may exclude a result as a false-positive
- match, subsequent requests are likely to not have the same
- false-positives.
- </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_pathelement">
<name>Path Element</name>
<t>
- A Path Element represents a hop in the path a message as taken
+ A Path Element represents a hop in the path a message has taken
through the network.
An ordered list of Path Elements may be appended to any routed
- message.
+ PUT or RESULT message.
A Path Element identifies a peer on the path.
- The Path Element is signed by the next peer on the path.
+ The Path Element is signed by the next peer on the path after
+ the next peer made its routing decision.
This signature is also part of the Path Element along with the
Peer ID of the previous peer.
</t>
<t>
The public key of the peer which created the signature is in the
next path element, or is the sender of the message if this was the
- last path element.
+ last path element.
The wire format of a Path Element is illustrated in
<xref target="figure_pathelement"/>.
</t>
@@ -1061,15 +1028,17 @@ bchar = *(ALPHA / DIGIT)
<dt>SIGNATURE</dt>
<dd>
is a 64 byte EdDSA signature using the current hop's private
- key affirming the previous hop.
+ key affirming the previous and next hops.
</dd>
</dl>
<t>
- The SIGNATURE covers a 64-bit pseudo header
- conceptually prefixed to the block expiration, a hash of the block
+ The SIGNATURE covers a 64-bit contextualization header, the
+ the block expiration, a hash of the block
payload, as well as the predecessor peer ID and the peer ID of the
- peer creating the signature.
- The wire format is illustrated
+ successor that the peer making the signature is routing the
+ message to. Thus, the signature made by SELF basically says that
+ SELF received the block payload from PEER PREDECESSOR and has forwarded
+ it to PEER SUCCESSOR. The wire format is illustrated
in <xref target="figure_pathelewithpseudo"/>.
</t>
<figure anchor="figure_pathelewithpseudo" title="The Wire Format of the Path Element for Signing.">
@@ -1115,7 +1084,7 @@ bchar = *(ALPHA / DIGIT)
</dd>
<dt>EXPIRATION</dt>
<dd>
- denotes the absolute 64-bit expiration date of the HELLO.
+ denotes the absolute 64-bit expiration date of the block.
In microseconds since midnight (0 hour), January 1, 1970 UTC in
network byte order.
</dd>
@@ -1129,10 +1098,11 @@ bchar = *(ALPHA / DIGIT)
</dd>
<dt>PEER SUCCECSSOR</dt>
<dd>
- the Peer ID of the signer.
+ the Peer ID of the next hop (not of the signer!).
</dd>
</dl>
</section>
+ </section>
<section anchor="p2p_hello" numbered="true" toc="default">
<name>HelloMessage</name>
<section anchor="p2p_hello_wire">
@@ -1449,10 +1419,51 @@ bchar = *(ALPHA / DIGIT)
</dd>
<dt>RESULT_BF</dt>
<dd>
- the variable-length result Bloom filter.
+ the variable-length result Bloom filter, described in <xref target="result_bloomfilter"/>.
</dd>
</dl>
</section>
+ <section anchor="result_bloomfilter">
+ <name>Result Bloom Filter</name>
+ <t>
+ The result Bloom filter is used to indicate to a peer which results
+ 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 <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. <!-- FIXME: is this strictly always the block key?
+ I think this is block-type dependent! -->
+ </t>
+ <t>
+ FIXME: say something about the size of the result Bloom filter here!
+ </t>
+ <t>
+ Bloom filters are probabilistic data structures. Thus, especially
+ given the small size of the result Bloom filter, it is always possible
+ that a desireable result is filtered by the Bloom filter because of
+ a false-positive match created by a collision in the hash values
+ between the desireable result and filtered items.
+ </t>
+ <t>
+ To address this problem, R<sup>5</sup>N uses a mutator value
+ to additionally randomize the process
+ when hashing results into the result Bloom filter. The mutator
+ value is set by the peer initiating the GET request, and changed
+ every time the GET request is repeated by the initiator. Peers
+ forwarding GET requests <bcp14>MUST</bcp14> not change the
+ mutator value included in the GET message as they could not
+ recalculate the Bloom filter with the new mutator value.
+ </t>
+ <t>
+ By including the mutator value in the hashing process, repeated
+ requests have statistically independent probabilities of creating
+ collisions in the Bloom filter. Thus, even if for one request
+ a Bloom filter collision may exclude a result as a false-positive
+ match, subsequent requests are likely to not have the same
+ false-positives.
+ </t>
+ </section>
<section anchor="p2p_get_processing">
<name>Processing</name>
<t>
