summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMartin Schanzenbach <schanzen@gnunet.org>2022-12-24 00:56:23 +0900
committerMartin Schanzenbach <schanzen@gnunet.org>2022-12-24 00:56:23 +0900
commit30a22ea5b8f6450319e3b1d88520e7d25e5d53a7 (patch)
treea83982d38837ce55669a16f67b1da76d60a136fb
parent3f70faf531ebd101004f5b93e1c80ee1ec5bcdd1 (diff)
downloadlsd0004-30a22ea5b8f6450319e3b1d88520e7d25e5d53a7.tar.gz
lsd0004-30a22ea5b8f6450319e3b1d88520e7d25e5d53a7.zip
Make wording consistent on bloom filters.
-rw-r--r--draft-schanzen-r5n.xml60
1 files changed, 35 insertions, 25 deletions
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index ab5478d..60733fa 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -863,15 +863,15 @@ bchar = *(ALPHA / DIGIT)
863 <t> 863 <t>
864 As DHT <tt>GetMessage</tt>s and <tt>PutMessage</tt>s traverse a random path through the network for the 864 As DHT <tt>GetMessage</tt>s and <tt>PutMessage</tt>s traverse a random path through the network for the
865 first N hops, it is essential that routing loops are avoided. 865 first N hops, it is essential that routing loops are avoided.
866 In R<sup>5</sup>N, a Bloom filter is used as part of the routing metadata in 866 In R<sup>5</sup>N, a Bloom filter is part of the routing metadata in
867 messages. The Bloom filter is updates at each hop with the hops 867 messages in order to prevent circular routes.
868 The Bloom filter is updates at each hop with the hops
868 peer identity. 869 peer identity.
869 For the next hop selection in both the random and the deterministic 870 For the next hop selection in both the random and the deterministic
870 case, any peer which is in the Bloom filter for the respective message 871 case, any peer which is in the Bloom filter for the respective message
871 is not included in the peer selection process. 872 is not included in the peer selection process.
872 </t> 873 </t>
873 <t> 874 <t>
874 The peer Bloom filter is used to prevent circular routes.
875 Any peer which is forwarding <tt>GetMessage</tt>s or <tt>PutMessage</tt>s 875 Any peer which is forwarding <tt>GetMessage</tt>s or <tt>PutMessage</tt>s
876 (<xref target="p2p_messages"/>) adds its own peer ID to the 876 (<xref target="p2p_messages"/>) adds its own peer ID to the
877 peer Bloom filter. 877 peer Bloom filter.
@@ -879,16 +879,20 @@ bchar = *(ALPHA / DIGIT)
879 traversed peers when searching for the next hops in the routing table. 879 traversed peers when searching for the next hops in the routing table.
880 </t> 880 </t>
881 <t> 881 <t>
882 The peer Bloom filter (see <xref target="bloom_filters"/>) consists of 882 The peer Bloom filter follows the definition in <xref target="bloom_filters"/>
883 L=1024 buckets. 883 and consists of L=1024 buckets.
884 The set of elements <tt>E</tt> consists of of all possible 256-bit peer IDs.
885 The number of buckets per element <tt>e</tt> is <tt>k=16</tt>.
884 The mapping function <tt>M</tt> is defined as follows: 886 The mapping function <tt>M</tt> is defined as follows:
885 </t> 887 </t>
886 <t> 888 <t>
887 The element <tt>e</tt> is a 32 byte peer ID and is hashed using 889 <tt>M(e) -> SHA-512 (e) as uint32[]</tt>
888 SHA-512. 890 </t>
891 <t>
892 The element <tt>e</tt> is hashed using SHA-512.
889 The resulting byte string is interpreted as a string of k=16 893 The resulting byte string is interpreted as a string of k=16
890 32-bit integers in network byte order which are used to set the bucket bits 894 32-bit integers in network byte order which are used to set and check the bucket bits
891 accordingly. 895 in <tt>B</tt> using <tt>BF-SET</tt> and <tt>BF-TEST</tt>.
892 </t> 896 </t>
893 <t> 897 <t>
894 We note that the peer Bloom filter may exclude peers due to false-postive 898 We note that the peer Bloom filter may exclude peers due to false-postive
@@ -2363,31 +2367,37 @@ gnunet+tcp://12.3.4.5/ \
2363 <dt>SetupResultFilter(FilterSize, Mutator) -&gt; RF</dt> 2367 <dt>SetupResultFilter(FilterSize, Mutator) -&gt; RF</dt>
2364 <dd> 2368 <dd>
2365 <t> 2369 <t>
2370 <!-- FIXME: I do not understand this. Isn't the element set E known
2371 for HELLO blocks? Isn't it H_ADDRS XOR MUTATOR? -->
2366 The RESULT_FILTER for HELLO blocks is implemented using a 2372 The RESULT_FILTER for HELLO blocks is implemented using a
2367 Bloom filter (see <xref target="bloom_filters"/>). 2373 Bloom filter following the definition from <xref target="bloom_filters"/>
2374 and consists of a variable number of buckets <tt>L</tt>.
2368 The size <tt>S = L/8</tt> of the Bloom filter in bytes depends on 2375 The size <tt>S = L/8</tt> of the Bloom filter in bytes depends on
2369 the number of elements <tt>F</tt> known to be filtered at the 2376 the number of elements <tt>|E|</tt> known to be filtered at the
2370 initiator. If <tt>F</tt> is zero, the size <tt>S</tt> is just 8 (bytes). 2377 initiator. If <tt>|E|</tt> is zero, the size <tt>S</tt> is padded to 32 bits for alignment.
2371 Otherwise, <tt>S</tt> is set to the minimum of 2378 Otherwise, <tt>L</tt> is set to the minimum of
2372 2<sup>15</sup> and the lowest power 2379 2<sup>18</sup> bits (2<sup>15</sup> bytes) and the lowest power
2373 of 2 that is strictly larger than <tt>K*F/4</tt> 2380 of 2 that is strictly larger than <tt>2*K*|E|</tt> bits (<tt>K*|E|/4</tt> bytes).
2374 (in bytes).
2375 </t> 2381 </t>
2376 <t> 2382 <t>
2377 The <tt>k</tt>-value for the HELLO_BF 2383 The <tt>k</tt>-value for the HELLO_BF Bloom filter is always 16.
2378 Bloom filter is always 16.
2379 <tt>k</tt> is never transmitted. 2384 <tt>k</tt> is never transmitted.
2380 The elements used in the Bloom filter 2385 The elements used in the Bloom filter
2381 consist of an XOR between the <tt>H_ADDRS</tt> field (as computed using 2386 consist of an XOR between the <tt>H_ADDRS</tt> field (as computed using
2382 SHA-512 over the <tt>ADDRESSES</tt>) and the SHA-512 2387 SHA-512 over the <tt>ADDRESSES</tt>) and the SHA-512
2383 hash of the <tt>MUTATOR</tt> field from a given HELLO block. 2388 hash of the <tt>MUTATOR</tt> field from a given HELLO block.
2384 The mapping function M(<tt>H_ADDRS XOR MUTATOR</tt>) is an identity 2389 The mapping function M(<tt>H_ADDRS XOR MUTATOR</tt>) is defined as follows:
2385 function and returns the 512-bit XOR result unmodified. 2390 </t>
2391 <t>
2392 <tt>M(e = H_ADDR XOR MUTATOR) -> e as uint32[]</tt>
2393 </t>
2394 <t>
2395 <tt>M</tt> is an identity function and returns the 512-bit XOR result unmodified.
2386 This resulting byte string is interpreted as k=16 32-bit 2396 This resulting byte string is interpreted as k=16 32-bit
2387 integers in network byte order and used to set or check the bucket bits 2397 integers in network byte order which are used to set and check the bucket bits in
2388 accordingly. 2398 <tt>B</tt> using <tt>BF-SET</tt> and <tt>BF-TEST</tt>.
2389 This function returns an empty Bloom filter of length <tt>S= L/8</tt> as 2399 The Mutator is prepended to the Bloom filter <tt>B</tt> to create the result filter
2390 part of RF: 2400 for a HELLO block:
2391 </t> 2401 </t>
2392 <figure anchor="hello_rf" title="The HELLO Block Result Filter."> 2402 <figure anchor="hello_rf" title="The HELLO Block Result Filter.">
2393 <artwork name="" type="" align="left" alt=""><![CDATA[ 2403 <artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2407,7 +2417,7 @@ gnunet+tcp://12.3.4.5/ \
2407 </dd> 2417 </dd>
2408 <dt>HELLO_BF</dt> 2418 <dt>HELLO_BF</dt>
2409 <dd> 2419 <dd>
2410 The Bloom filter byte array. 2420 The Bloom filter buckets byte array.
2411 </dd> 2421 </dd>
2412 </dl> 2422 </dl>
2413 <t> 2423 <t>