diff options
author | Martin Schanzenbach <schanzen@gnunet.org> | 2022-12-24 00:56:23 +0900 |
---|---|---|
committer | Martin Schanzenbach <schanzen@gnunet.org> | 2022-12-24 00:56:23 +0900 |
commit | 30a22ea5b8f6450319e3b1d88520e7d25e5d53a7 (patch) | |
tree | a83982d38837ce55669a16f67b1da76d60a136fb | |
parent | 3f70faf531ebd101004f5b93e1c80ee1ec5bcdd1 (diff) | |
download | lsd0004-30a22ea5b8f6450319e3b1d88520e7d25e5d53a7.tar.gz lsd0004-30a22ea5b8f6450319e3b1d88520e7d25e5d53a7.zip |
Make wording consistent on bloom filters.
-rw-r--r-- | draft-schanzen-r5n.xml | 60 |
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) -> RF</dt> | 2367 | <dt>SetupResultFilter(FilterSize, Mutator) -> 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> |