[lsd0004] branch master updated: bloom

[gnunet]

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 79acd5b  bloom
79acd5b is described below

commit 79acd5b791f4d6fd5afe6ef00efd2748e3459c53
Author: Martin Schanzenbach <schanzen@gnunet.org>
AuthorDate: Sat Mar 12 08:49:52 2022 +0100

    bloom
---
 draft-schanzen-r5n.xml | 29 ++++++++++++++++++++++++-----
 1 file changed, 24 insertions(+), 5 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 9719af5..9bb2d5e 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -741,18 +741,37 @@ bchar = *(ALPHA / DIGIT)
        on this data structure shared by the various use-cases in 
R<sup>5</sup>N.
       </t>
       <t>
-       FIXME: general intro.
+        A Bloom filter (BF) is a space-efficient probabilistic datastructure
+        to test if an element is part of a set of elements.
+        Elements are identified by an element ID.
+        Since a BF is a probabilistic datastructure, it is possible to have
+        false-positives: when asked if an element is in the set, the answer 
from
+        a BF is either "no" or "maybe".
       </t>
       <t>
-        Bloom filters are always initially empty, consisting only of zeroes.
+        Bloom filters are defined as a string of <tt>N</tt> bits always
+        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:
+        The mapping function <tt>M</tt> is defined as follows:
       </t>
       <t>
-       FIXME: actually define the operations...
+        The element <tt>e</tt> is hashed using SHA-512.
+        The resulting byte string is interpreted as a string of 16
+        32-bit integers in network byte order.
+      </t>
+      <t>
+        When adding an element to the bloom filter <tt>bf</tt> using
+        <tt>BF-SET(bf,e)</tt>, each number <tt>n</tt> in the mapping
+        <tt>M(e)</tt> is interpreted as a bit offset within <tt>bf</tt> and set
+        to 1.
+      </t>
+      <t>
+        When testing if an element is in the bloom filter <tt>bf</tt> using
+        <tt>BF-TEST(bf,e)</tt>, each number <tt>n</tt> in the mapping
+        <tt>M(e)</tt> <bcp14>MUST</bcp14> have been set to 1.
+        Otherwise, the element is not considered to be in the bloom filter.
       </t>
     </section>
     <section anchor="routing" numbered="true" toc="default">

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.