[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0004] branch master updated: some bloom filter; some query hash
|
From: |
gnunet |
|
Subject: |
[lsd0004] branch master updated: some bloom filter; some query hash |
|
Date: |
Mon, 14 Feb 2022 22:42:20 +0100 |
This is an automated email from the git hooks/post-receive script.
martin-schanzenbach pushed a commit to branch master
in repository lsd0004.
The following commit(s) were added to refs/heads/master by this push:
new 7ba1709 some bloom filter; some query hash
7ba1709 is described below
commit 7ba1709e99bbdaa004125df05d261ca44b6ce733
Author: Martin Schanzenbach <schanzen@gnunet.org>
AuthorDate: Mon Feb 14 22:42:17 2022 +0100
some bloom filter; some query hash
---
draft-schanzen-r5n.xml | 132 +++++++++++++++++++++++++++++++------------------
1 file changed, 84 insertions(+), 48 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 5af854e..4c8797f 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -273,7 +273,7 @@ Connectivity | |Underlay| |Underlay|
<t>
Other glossary
</t>
- </section>
+ </section>
<section anchor="overlay" numbered="true" toc="default">
<name>Application API</name>
<t>
@@ -339,7 +339,7 @@ Connectivity | |Underlay| |Underlay|
<dt>Result-Filter:</dt>
<dd>
allows to indicate results which are not relevant anymore to the
- caller (see <xref target="p2p_bf"/>).
+ caller (see <xref target="result_bloomfilter"/>).
</dd>
</dl>
<t>
@@ -614,12 +614,27 @@ Connectivity | |Underlay| |Underlay|
In order to achieve O(log n) routing performance,
the data structure for managing connected nodes and their
metadata MUST 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.
+ <xref target="Kademlia"/> as defined in <xref
target="routing_table"/>.
+ </t>
+ </section>
+ <section anchor="routing_bloomfilter">
+ <name>Peer Bloom Filter</name>
+ <t>
+ The peer bloom filter is used to prevent circular routes.
+ Any peer which is forwarding GET or PUT messages
+ (<xref target="p2p_messages"/>) adds its own peer ID to the
+ message bloom filter.
+ This allows other peers to lookup next hops while excluding already
+ traversed peers (<xref target="routing_table"/>).
+ </t>
+ <t>
+ The bloom filter is a 128-bit field.
+ It 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="find_peer">
@@ -649,6 +664,13 @@ Connectivity | |Underlay| |Underlay|
</section>
<section anchor="routing_table">
<name>Routing Table</name>
+ <t>
+ 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>
<t>
The routing table consists of an array of lists of connected nodes.
The i-th list stores neighbours whose identifiers are between
@@ -762,14 +784,20 @@ Connectivity | |Underlay| |Underlay|
</dd>
</dl>
</section>
- <section anchor="p2p_bf" numbered="true" toc="default">
- <name>Bloomfilter</name>
- <!-- FIXME: also discuss result BF -->
+ <section anchor="result_bloomfilter">
+ <name>Result Bloom Filter</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.
+ 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 MUST check the result bloom filter
+ and only send a reply message if the block key is not in the
+ bloom filter set.
+ </t>
+ <t>
+ The bloom filter is a 128-bit field.
+ It 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.
@@ -885,15 +913,15 @@ Connectivity | |Underlay| |Underlay|
+-----+-----+-----+-----+-----+-----+-----+-----+
| EXPIRATION |
+-----+-----+-----+-----+-----+-----+-----+-----+
-| BLOOMFILTER /
+| PEER_BF /
/ (128 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
-| KEY /
+| BLOCK_KEY /
/ (64 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
/ PUTPATH (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
-/ BLOCK (variable length) /
+/ BLOCK (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
</figure>
@@ -941,11 +969,11 @@ Connectivity | |Underlay| |Underlay|
In microseconds since midnight (0 hour), January 1, 1970 in
network
byte order.
</dd>
- <dt>BLOOMFILTER</dt>
+ <dt>PEER_BF</dt>
<dd>
A bloomfilter (for node addresses) to stop circular routes.
</dd>
- <dt>KEY</dt>
+ <dt>BLOCK_KEY</dt>
<dd>
The key under which the PUT request wants to store content
under.
@@ -987,7 +1015,7 @@ Connectivity | |Underlay| |Underlay|
it MUST be discarded.
</li>
<li>
- The node address of the sender peer <tt>P</tt> SHOULD be in
<tt>BLOOMFILTER</tt>.
+ The node 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.
</li>
<li>
@@ -997,7 +1025,7 @@ Connectivity | |Underlay| |Underlay|
</li>
<li>
If the local node is the closest node
- (cf. <tt>IsClosestNode(N, Key)</tt>) or the
<tt>DemultiplexEverywhere</tt>
+ (cf. <tt>IsClosestNode(N, BLOCK_KEY)</tt>) or the
<tt>DemultiplexEverywhere</tt>
options flag ist set, the message MUST
be stored locally in the block storage.
</li>
@@ -1009,7 +1037,7 @@ Connectivity | |Underlay| |Underlay|
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.
+ <tt>PEER_BF</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>
@@ -1028,10 +1056,10 @@ Connectivity | |Underlay| |Underlay|
+-----+-----+-----+-----+-----+-----+-----+-----+
| OPTIONS | HOPCOUNT | REPL_LVL | XQ_SIZE |
+-----+-----+-----+-----+-----+-----+-----+-----+
-| BLOOMFILTER /
+| PEER_BF /
/ (128 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
-| KEY /
+| QUERY_HASH /
/ (64 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
/ BF_MUTATOR | XQUERY /
@@ -1077,14 +1105,19 @@ Connectivity | |Underlay| |Underlay|
is a 32-bit number indicating the length of the optional
extended query XQUERY. In network byte order.
</dd>
- <dt>BLOOMFILTER</dt>
+ <dt>PEER_BF</dt>
<dd>
A bloomfilter (for node identities) to stop circular routes.
</dd>
- <dt>KEY</dt>
+ <dt>QUERY_HASH</dt>
<dd>
- The key under which the PUT request wants to store content
- under.
+ The query used to indicate which blocks the originator is looking
+ for in this GET request.
+ The value is commonly evaluated with respect to its XOR distance
+ to a given block key when it is considered as an answer to
+ the request.
+ The block type may use a different evaluation logic to determine
+ applicable result blocks.
</dd>
<dt>XQUERY</dt>
<dd>
@@ -1108,7 +1141,8 @@ Connectivity | |Underlay| |Underlay|
</t>
<ol>
<li>
- The <tt>KEY</tt> and <tt>XQUERY</tt> is validated against the
+ The <tt>QUERY_KEY</tt> and <tt>XQUERY</tt> fields are 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
@@ -1117,13 +1151,13 @@ Connectivity | |Underlay| |Underlay|
</li>
<li>
The node address of the sender peer <tt>P</tt> SHOULD be in the
- BLOOMFILTER. If not, the
+ PEER_BF bloom filter. 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
+ (cf. <tt>IsClosestNode (N, QueryHash)</tt>) or the
<tt>DemultiplexEverywhere</tt> options flag is set, a reply
MUST be produced (if one is available) using the following
steps:
@@ -1168,8 +1202,8 @@ 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
- address <tt>N</tt>.
+ The message bloom filter PEER_BF 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>
@@ -1190,17 +1224,17 @@ Connectivity | |Underlay| |Underlay|
+-----+-----+-----+-----+-----+-----+-----+-----+
| EXPIRATION |
+-----+-----+-----+-----+-----+-----+-----+-----+
-| KEY /
+| QUERY_HASH /
/ (64 byte) |
+-----+-----+-----+-----+-----+-----+-----+-----+
-/ PUTPATH /
+/ PUTPATH /
/ (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
-/ GETPATH /
+/ GETPATH /
/ (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
-/ BLOCK /
-/ (variable length) /
+/ BLOCK /
+/ (variable length) /
+-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
</figure>
@@ -1243,10 +1277,10 @@ Connectivity | |Underlay| |Underlay|
In microseconds since midnight (0 hour), January 1, 1970 in
network
byte order.
</dd>
- <dt>KEY</dt>
+ <dt>QUERY_HASH</dt>
<dd>
- The key under which the PUT request wants to store content
- under.
+ the query hash corresponding to the GET message which
+ caused this reply message to be sent.
</dd>
<dt>PUTPATH</dt>
<dd>
@@ -1290,20 +1324,23 @@ Connectivity | |Underlay| |Underlay|
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>
+ If the <tt>QUERY_HASH</tt> of this <tt>ResultMessage</tt> is
found in the
+ list of pending local queries, the <tt>QUERY_HASH</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.
+ <!-- FIXME: "Does not match would mean equals. Is that correct?
+ <= approximate flag -->
</li>
<li>
The implementation MAY cache RESULT messages.
</li>
<li>
<t>
- If requests by other nodes for this KEY or BTYPE are known,
+ If requests by other nodes for this QUERY_HASH or BTYPE are
+ known,
the result block is validated against each request using
the respective <tt>ValidateBlockReply</tt> function.
</t>
@@ -1311,12 +1348,11 @@ Connectivity | |Underlay| |Underlay|
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
- to then check it again against the block? This does not make
sense...)
+ the request is only approximate.
</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
+ <tt>QUERY_HASH</tt> of the result message or if <tt>BLOCK</tt>
is
malformed, the message MUST be discarded.
</t>
<t>
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [lsd0004] branch master updated: some bloom filter; some query hash,
gnunet <=